RESILIENT ROUTE GENERATION SYSTEM FOR RELIABLE COMMUNICATION IN POWER GRID PHASOR MEASUREMENT SYSTEM

Abstract

Disclosed is a resilient route generation system for reliable communication of a phasor measurement system of a power grid. A named data network is a new network architecture to improve the communication reliability between a phasor measurement unit and a phasor measurement concentrator in power transmission and distribution networks. The lost data packets in a current router can be directly recovered from an upstream router with resilient route, and the optimal RR selection will maximize the success rate of retransmission of lost data packets, thus maximizing the network reliability. The mesh network and ring network structure of the power grid are fully utilized, and a resilient route generation system is provided, wherein the resilient route of each communication pair includes a corresponding primary path and a plurality of redundant sub paths, so that the success rate of retransmission of lost data packets and the network reliability are maximized.

Claims

1. A resilient route RR generation system for reliable communication in a phasor measurement system of a power grid, comprising a resilient route vector generation module, an RR communication pair generation module and an RSP path generation module; wherein an input of the resilient route generation system comprises a network topology, a RR configuration, a current router r.sub.j and a destination router r.sub.k, and an output is resilient route Y from r.sub.j to r.sub.k, comprising a primary path p.sub.prim from r.sub.j to r.sub.k and the a mapping X between a redundant sub-path set starting from a primary path router and a corresponding starting point; the RR configuration comprises a maximum number of retransmission times η, a deviation coefficient α, a maximum number of redundant sub-paths β of a single router, and a maximum allowable end-to-end delay D; the deviation coefficient α is a sum of a maximum queuing time and a maximum processing time when a data packet arrives at each router node; the network topology G comprises a router set R and a link set L.sup.0; the resilient route vector generation module obtains an intermediate calculation result according to the input network topology, the RR configuration and the current router, and sends the intermediate calculation result to the RR communication pair generation module together with the network topology, the maximum number of retransmission times and the deviation coefficient to obtain a preselected path p of redundant sub-paths, and finally generates a RR vector corresponding to the current router, including recording a sequence prev.sub.1 of a last hop router and a mapping X.sup.0 between a desirable router and the redundant sub-path set with the router as a starting point; the intermediate calculation result comprises a candidate redundant sub-path starting point r.sub.v, a path sequence X′, a path sequence link set {circumflex over (L)}, a historically generated redundant sub-path link set {tilde over (L)}, a current primary path link maximum delay τ.sup.l.sub.max, a current primary path total delay τ.sub.prim and a current primary path maximum allowable retransmission delay τ.sub.retrans.sup.max; the RSP path generation module generates a maximum non-overlapping path, as the preselected path p, from a source router node to all nodes in a destination router node set according to the network topology, the maximum number of retransmission times, the deviation coefficient and the intermediate calculation result provided by the resilient route vector generation module; the RR communication pair generation module outputs Y according to the input RR configuration, the current router, the destination router and the RR vector generated by the resilient route vector generation module and generates the resilient route, which comprises the following steps: (3.1) taking r.sub.k as the destination router, repeatedly searching the last hop router from prev.sub.1 of the RR vector output by the resilient route vector generation module until prev.sub.1[r.sub.j]=−1, and obtaining a router sequence from r.sub.j to r.sub.k as the primary path p.sub.prim; (3.2) creating a hash table X={ }, obtaining P.sub.rsp(r.sub.p) corresponding to r.sub.p from X.sup.0 of the RR vector output by the resilient route vector generation module for each router r.sub.p in the p.sub.prim obtained in step (3.1), and putting P.sub.rsp(r.sub.p) obtained each time into X; (3.3) outputting Y={p.sub.prim,X}.

2. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 1, wherein the resilient route vector generation module is configured to: (a1) add all routers in the network to a heap q.sub.1; traverse the routers in the heap q.sub.1, and take out the router r.sub.u with a current minimum packet loss rate L in the current heap q.sub.1 every time; (a2) for an output link l.sub.uv of r.sub.u extracted in step (a1), obtain a router r.sub.v opposite to r.sub.u on l.sub.uv; traverse the router r.sub.v opposite to r.sub.u, searching for all path sequences from r.sub.j to r.sub.u according to prev.sub.1, and take r.sub.v as a next path node of r.sub.u to obtain the current primary path; wherein the total delay τ.sub.prim of each primary path cannot exceed the maximum allowable end-to-end delay D, and prev.sub.1 records a last hop router of each router; (a3) for each primary path, call the RSP path generation module to obtain the redundant sub-path set P.sub.rsp with r.sub.v as a starting point; wherein, there are no more than β redundant sub-paths in P.sub.rsp and redundant sub-paths do not overlap as much as possible; the current minimum packet loss rate of r.sub.v should be reduced after adding the redundant sub-paths; (a4) finally, obtain the updated prev.sub.1 and the mapping X.sup.0 between the desirable router and the redundant sub-path set with the router as a starting point to form the RR vector.

3. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 2, wherein the RSP path generation module is configured to: (b1) add a virtual router r.sub.vir in the network to make r.sub.vir bidirectionally connect to each point r.sub.v,s in X′, with both a connection delay and a packet loss rate being zero; push all routers in the current network into a heap q.sub.2; traverse the routers in the heap q.sub.2, and take out a router r.sub.w with a smallest value of ψ′ from the current heap q.sub.2 every time; (b2) traverse an output link l.sub.wx of r.sub.w extracted in step (b1) and an opposite node r.sub.x; select redundant sub-path links and nodes under the condition that a logarithmic value of a reliability should be as large as possible; wherein, the redundant sub-paths cannot pass through the link in the primary path, and the selected redundant sub-path links cannot make a retransmission delay of the node exceed the maximum allowable retransmission delay; the selected redundant sub-path links should make the logarithmic value of the reliability of the node larger; when a link is repeatedly considered as a redundant sub-path link, the overlapping of redundant sub-paths can be avoided as much as possible by minimizing the logarithmic value of the reliability of the link; (b3) select, by prev.sub.2, the redundant sub-path links and record, by the node, a last hop router according to step (b2), and search for a router sequence from r.sub.v to r.sub.vir according to prev.sub.2, wherein r.sub.v can reach any node in X′ through r.sub.vir; and then remove r.sub.vir to obtain the preselected path p; (b4) finally, feed back the preselected path p and a packet loss rate ϵ.sub.data and a retransmission timeout θ.sub.r(p) of the redundant sub-paths in the case of η retransmissions to the resilient route vector generation module.

4. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 3, wherein the RR communication pair generation module is specifically configured to search for the primary path from r.sub.j to r.sub.k according to the prev.sub.1 output by the resilient route vector generation module, and obtain a mapping between a primary path router and the redundant sub-path set with the router as a starting point from the mapping X.sup.0 to obtain the output Y of the system.

5. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 4, wherein the resilient route vector generation module is specifically implemented by the following steps: (1.1) creating a hash function: L[r.sub.i] is a current minimum packet loss rate of r.sub.i, ψ[r.sub.i] is a RR packet loss rate of r.sub.i, ϕ[r.sub.i] is a maximum estimated packet loss rate from an upstream router of r.sub.i to r.sub.i in the primary path when multiple retransmission paths are considered, T.sub.prim[r.sub.i] is a primary path delay of r.sub.i, and T[r.sub.i] represents a RR delay of r.sub.i; P.sub.rsp(r.sub.i) is a set of redundant sub-paths with r.sub.i as a starting point, and X.sup.0 is the mapping between r.sub.i and P.sub.rsp(r.sub.i) on the current primary path; prev.sub.1[r.sub.i] records a last hop router of r.sub.i; where r.sub.i is an i.sup.th router in R, i=1˜n, and n is a number of routers; (1.2) initialization: L=[1.0].sub.1×n, ψ=[1.0].sub.1×n, ϕ[0].sub.1×n, T.sub.prim=[0].sub.1×n, T=[0].sub.1×n; prev.sub.1=[−1].sub.1×n; wherein L[r.sub.j]=0, ψ[r.sub.j]=1, ϕ[r.sub.j]=0, T.sub.prim[r.sub.j]=0, T[r.sub.j]=0; (1.3) adding all r.sub.i∈R to the heap q.sub.1; (1.4) taking out the router r.sub.u with the smallest L in the current heap q.sub.1; (1.5) for output link l.sub.uv of r.sub.u extracted in step (1.4), obtaining a router r.sub.v opposite to r.sub.u on l.sub.uv; (1.6) if the r.sub.v obtained in step (1.5) is not in the current heap q.sub.1, skipping to step (1.5) to calculate the r.sub.v corresponding to a next output link until all output links l.sub.uv of r.sub.u are traversed, and skipping to step (1.17); (1.7) calculating the maximum delay τ.sup.l.sub.max, the total delay τ.sub.prim and the maximum allowable retransmission delay τ.sub.retrans.sup.max of the current primary path; (1.8) if τ.sub.prim≥D, skipping to step (1.5) to calculate r.sub.v corresponding to another l.sub.uv until all output links of r.sub.u are traversed, and skipping to step (1.17); (1.9) taking r.sub.u as the destination router, repeatedly searching the last hop router according to prev.sub.1, and obtaining the path sequence X′ from r.sub.j to r.sub.u; defining {circumflex over (L)} as a set of all links in X′; (1.10) defining i.sub.step=0 for step counting, initializing the set {tilde over (L)}={ }, and circularly executing the following substeps: (1.10.1) if i.sub.step≥β, terminating the circulation and executing step (1.11); (1.10.2) calling the RSP path generation module, and passing the current G, r.sub.v, X′, {circumflex over (L)}, {tilde over (L)}, η, α, τ.sup.l.sub.max, τ.sub.prim and τ.sub.retrans.sup.max as parameters to the RSP path generation module to obtain the preselected path p fed back by the RSP path generation module; (1.10.3) if p obtained in step (1.10.2) is empty or belongs to the current redundant sub-path set P.sub.rsp, terminating the circulation and executing step (1.11); (1.10.4) adding p obtained in step (1.10.2) to P.sub.rsp; (1.10.5) if i.sub.step<β−1, adding all links in p obtained in step (1.10.2) to the set {tilde over (L)}; (1.10.6) defining i.sub.step=i.sub.step+1, and skipping to step (1.10.1) to enter the next cycle; (1.11) calculating the current minimum packet loss rate L′ when r.sub.v is a next path node of X′; (1.12) if L′<L[r.sub.v], updating T[r.sub.v], L[r.sub.v], ϕ[r.sub.v], ψ[r.sub.v], T.sub.prim[r.sub.v] and T.sub.prim[r.sub.v] and recording r.sub.u as a last hop router of r.sub.v; and if L′≥L[r.sub.v], skipping to step (1.4) until the routers in the heap q.sub.1 have been traversed, and executing step (1.18); (1.13) defining X.sup.0[r.sub.v]=P.sub.rsp; then skipping to step (1.5) to calculate r.sub.v corresponding to another output link until all output links l.sub.uv of r.sub.u have been traversed; (1.17) skipping to step (1.4) until the routers in the heap q.sub.1 have been traversed, and executing step (1.18); (1.18) storing the calculation result (prev.sub.1,X.sup.0) in the RR vector.

6. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 5, wherein the RSP path generation module is specifically implemented by the following steps: (2.1) adding a virtual router r.sub.vir in the network to make r.sub.vir connect bidirectionally to each point r.sub.v,s in X′, wherein both the connection delay and packet loss rate being 0, and the number of routers in the current network is n′=n+1; (2.2) creating a hash function: ψ′ indicates a logarithmic value of a data packet transmission success rate of the current redundant sub-path under the condition of considering the exclusion of {tilde over (L)} as much as possible, ϕ′ indicates a logarithmic value of a data packet transmission success rate of the redundant sub-paths in a current real case; τ.sub.up and τ.sub.down respectively record the forwarding delays of the upstream and downstream paths of each router node; θ.sub.retrans records a retransmission timeout time of each router node; prev.sub.2 records the last hop router; (2.3) initialization: ψ′=[−∞].sub.1×n′, ϕ′=[−∞].sub.1×n′, τ.sub.up={ }, τ.sub.down={ }, θ.sub.retrans=[0].sub.1×n′, prev.sub.2=[−1].sub.1×n′; wherein ϕ′[r.sub.v]=0, ψ′[r.sub.v]=0, τ.sub.up[r.sub.v]=0, τ.sub.down[r.sub.v]=0; (2.4) pushing all routers in the current network into the heap q.sub.2; if the number of routers in the current heap q.sub.2 satisfies |q.sub.2|≤0, skipping to step (2.10); (2.5) taking out the router r.sub.w with a smallest ψ′ value from the current heap q.sub.2; (2.6) obtaining the opposite node r.sub.x on an egress link l.sub.wx of r.sub.w; or if l.sub.wx∈{circumflex over (L)} or r.sub.x does not belong to the current heap q.sub.2, skipping to step (2.5) and directly entering the next cycle; (2.7) calculating an uplink delay τ.sub.up′, a downlink delay τ.sub.down′ of the current redundant sub-path, a retransmission timeout θ.sub.retrans′ and a retransmission delay τ.sub.retrans′ of the current router node; if τ.sub.retrans′>τ.sub.retrans.sup.max, skipping to step (2.5) until the routers in the heap q.sub.2 are traversed; (2.8) calculating the logarithmic value of a true reliability from r.sub.w to r.sub.x in a real situation, and the logarithmic value of a conversion reliability from r.sub.w to r.sub.x when {tilde over (L)} is excluded as much as possible; (2.9) if >ψ′[r.sub.x], updating ϕ′[r.sub.x], ψ′[r.sub.x], τ.sub.up[r.sub.x], τ.sub.down[r.sub.x], and recording r.sub.w as the last hop router of r.sub.x; and if ≤ψ′[r.sub.x], skipping to step (2.5) until the routers in the heap q.sub.2 are traversed, and executing step (2.10); (2.10) taking r.sub.vir as the destination router, repeatedly searching the last hop router according to prev.sub.2, and obtaining the router sequence (r.sub.v, . . . , r.sub.vir) from r.sub.v to r.sub.vir; and then removing r.sub.vir to obtain the preselected path p; (2.11) calculating the packet loss rate ϵ.sub.data and retransmission timeout time θ.sub.r(p) of the redundant sub-path when r.sub.v arrives at r.sub.vir in a case of r/retransmissions; then removing r.sub.vir from G; finally, feeding (p,ϵ.sub.data(p),θ.sub.r(p)) back to the resilient route vector generation module.

7. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 6, wherein: in step (1.3), the heap q.sub.1 is a Fibonacci heap, which is used to sort the routers from small to large according to the value of L[r.sub.i]; and the order is updated synchronously with the value of L[r.sub.i]; in step (1.7): when a maximum link delay τ.sup.l.sub.max of a current primary path is:
τ.sup.l.sub.max=(τ(r.sub.u,r.sub.v)−τ.sub.trans(r.sub.u,r.sub.v))×α+τ(r.sub.u,r.sub.v) when a total delay τ.sub.prim of the current primary path is:
τ.sub.prim=T.sub.prim[r.sub.u]+τ(r.sub.u,r.sub.v) under the selection of the current primary path, the maximum allowable retransmission delay τ.sub.retrans.sup.max;
τ.sub.retrans.sup.max=D−T[r.sub.u]−τ.sub.prim where τ(r.sub.u,r.sub.v) represents a total delay from r.sub.u to r.sub.v, which is the sum of a transmission delay, a processing delay and a queuing delay; τ.sub.trans(r.sub.u,r.sub.v) represents a transmission delay from r.sub.u to r.sub.v; in step (1.9), prev.sub.1[r.sub.j]=−1; in step (1.11), the current minimum packet loss rate L′ when r.sub.v is a next path node of X′: ${\varphi }^0=\in \left(r_u,r_v\right).Math.\underset{p\in P_{rsp}}{.Math.}{ϵ}_{data}\left(p\right)$ $L’={\varphi }^0.Math.\psi \left[r_u\right]+L\left[r_u\right]$ where ϵ(r.sub.u,r.sub.v) represents the packet loss rate from r.sub.u to r.sub.v, and ϵ.sub.data(p) is the packet loss rate of the preselected path p; the update parameters of step (1.12) are as follows:
T[r.sub.v]=T[r.sub.u]+τ(r.sub.u,r.sub.v)+τ(r.sub.u,r.sub.v).Math.(1+α)+θ.sub.r(p′).Math.(η−1)+τ.sub.d(p′)
L[r.sub.v]=L′
ϕ[r.sub.v]=ϕ.sup.0
ψ[r.sub.v]=ψ[r.sub.u].Math.(1−ϕ[r.sub.u])
T.sub.prim[r.sub.v]=τ.sub.prim
prev.sub.1[r.sub.v]=r.sub.u where p′ represents a preselected path with the smallest retransmission timeout in the set P.sub.rsp, θ.sub.r(p′) represents the retransmission timeout of p′, and τ.sub.d(p′) represents the total downlink delay of p′.

8. The resilient route RR generation system for reliable communication in a phasor measurement system of a power grid according to claim 7, wherein: in step (2.4), the heap q.sub.2 is a Fibonacci heap, which is used to sort the routers from small to large according to the value of ψ′[r.sub.i], and the order is updated synchronously with the value of ψ′[r.sub.i]; in step (2.8): the upstream delay τ.sub.up′ and the downstream delay τ.sub.down′ of the current redundant sub-path:
τ.sub.up′=τ(r.sub.w,r.sub.x)+τ.sub.up[r.sub.w]
τ.sub.down′=τ(r.sub.x,r.sub.w)+τ.sub.down[r.sub.w] the retransmission timeout θ.sub.retrans′ of the current router node:
θ.sub.retrans′=θ.sub.retrans[r.sub.w]+(τ.sub.queue(l.sub.wx)+τ.sub.process(l.sub.wx))×α+τ.sub.trans(l.sub.wx) the retransmission delay τ.sub.retrans′ of the current router node:
τ.sub.retrans′=τ.sup.l.sub.max+τ.sub.prim+θ.sub.retrans′×(η−1)+τ.sub.down′ where τ.sub.queue(l.sub.wx) and τ.sub.process(l.sub.wx) respectively represent the queuing delay and processing delay from r.sub.w to r.sub.x; in step (2.9), the logarithmic value ψ.sub.1 of a true reliability and the logarithmic value of a conversion reliability:
ψ.sub.1=log((1−ϵ(r.sub.w,r.sub.x)1−ϵ(r.sub.x,r.sub.w)))
={circumflex over (ψ)}+ψ′[r.sub.w] wherein if l.sub.wx∈{tilde over (L)}, then {circumflex over (ψ)}=∈.sub.expell, but if l.sub.wx.Math.{tilde over (L)}, {circumflex over (ψ)}=ψ.sub.1; ϵ.sub.expell is the logarithmic value of a minimum link reliability in the current network:
∈.sub.expell=log[min.sub.l.sub.z.sub.∈L.sub.0((1−∈(l.sub.z))/C)] where L.sup.0 comprises a newly added link l=(r.sub.v,s,r.sub.vir) in step (2.1), and l.sub.z is a z.sup.th link in L.sup.0; ϵ(l.sub.z) indicates a packet loss rate of a path l.sub.z, and C is a constant greater than 1; the update parameters of step (2.11) are as follows:
prev.sub.2[r.sub.x]=r.sub.w
ϕ′[r.sub.x]=
ψ′[r.sub.x]=ψ.sub.1+ψ′[r.sub.w]
τ.sub.up[r.sub.x]=τ(r.sub.w,r.sub.x)+τ.sub.up[r.sub.w]
τ.sub.down[r.sub.x]=τ(r.sub.x,r.sub.w)+τ.sub.down[r.sub.w] in step (2.12), prev.sub.2[r.sub.v]=−1; in step (2.13), the packet loss rate ϵ.sub.data and retransmission timeout θ.sub.r(p) of the redundant sub-path:
∈.sub.one-way=1−e.sup.ψ′[r.sup.vir.sup.]
ϵ.sub.data(P)ϵ.sub.one-way.sup.η
θ.sub.r(p)=α.Math.(τ.sub.up[r.sub.vir]+τ.sub.down[r.sub.vir]) where ϵ.sub.one-way represents a one-way packet loss rate of the redundant sub-path from r.sub.v to r.sub.vir.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0081] FIG. 1 is an architecture diagram of a resilient route generation system;

[0082] FIG. 2 is a communication network topology diagram of the power grid according to an embodiment of the present application.

DESCRIPTION OF EMBODIMENTS

[0083] The present disclosure relates to a resilient route generation system for reliable communication of a phasor measurement system of a power grid. In view of the business characteristics of phasor measurement of the power grid, a resilient route (RR) generation system is given by fully utilizing the mesh network and ring network structures of a power grid, which can be deployed in NDN routers. Based on the network topology provided by NDN, the system can calculate RR, so that the routers can transmit data according to PP, such as data packet loss, and the routers can request the upstream routers on their PP to retransmit the lost data packets through RSP, so as to realize the recovery of the packets and maximize the success rate of retransmission of the lost packets and the network reliability.

[0084] Assuming that the network is formally defined as:

G=(R,L.sup.0)

R={r.sub.1,r.sub.2, . . . ,r.sub.n}

L.sup.0={l.sub.1,l.sub.2, . . . ,l.sub.m}

[0085] where R is a set of NDN routers, r.sub.i is the i.sup.th router in R, and i=1˜n; a phasor measurement unit PMU is connected with a source router, and a phasor measurement concentrator PDC is connected with a destination router; L.sup.0 is a set of links l.sub.z, l.sub.z∈=L.sup.0, z=1˜m, and m is the number of links in the current network.

[0086] FIG. 1 shows the architecture of the resilient route generation system, which is mainly composed of a RR vector generation module, a RR communication pair generation module and a RSP path generation module. A RR vector is a storage structure for storing intermediate calculation results. The input of the resilient route generation system includes a network topology G, a RR configuration, a current router and a destination router, and the output is RR, the RR configuration includes a maximum number of retransmission times η, a deviation coefficient α, a maximum number of redundant sub-paths β of a single router, and a maximum allowable end-to-end delay D; the deviation coefficient α is the sum of a maximum queuing time and a maximum processing time when the data packet arrives at each router node. The resilient route RR is defined as Y:

Y={p.sub.prim,X}

X={r.sub.i.fwdarw.P.sub.rsp(r.sub.i)|r.sub.i∈p.sub.prim}

[0087] where p.sub.prim is a primary path from the current router to the destination router, which represents the sequence of routers on the primary path; P.sub.rsp(r.sub.i) is a RSP set whose endpoint begins with r.sub.i∈p.sub.prim; X is a mapping of all r.sub.i∈p.sub.prim to a corresponding P.sub.rsp(r.sub.i), i.e., X[r.sub.i]=P.sub.rsp(r.sub.i),r.sub.i∈P.sub.prim.

[0088] I. RR Vector Generation Module

[0089] The module generates a RR vector corresponding to r.sub.j of the current router according to the network topology, the RR configuration and the current router, and it configured to: firstly, add all routers in the network to a heap q.sub.1; traverse the routers in the heap q.sub.1, and take out the router r.sub.u with a current minimum packet loss rate L in the current heap q.sub.1 every time; then, for an output link l.sub.uv of r.sub.u extracted in step (a1), obtain a router r.sub.v opposite to r.sub.u on l.sub.uv; traverse the router r.sub.v opposite to r.sub.u, searching for all path sequences from r.sub.j to r.sub.u according to prev.sub.1, and take r.sub.v as a next path node of r.sub.u to obtain the current primary path; the total delay τ.sub.prim of each primary path cannot exceed the maximum allowable end-to-end delay D, and prev.sub.1 records a last hop router of each router; afterwards, for each primary path, call the RSP path generation module to obtain the redundant sub-path set P.sub.rsp with r.sub.v as a starting point; there are no more than β redundant sub-paths in P.sub.rsp and redundant sub-paths do not overlap as much as possible; the current minimum packet loss rate of r.sub.v should be reduced after adding the redundant sub-paths; finally, obtain the updated prev.sub.1 and the mapping X.sup.0 between the desirable router and the redundant sub-path set with the router as a starting point to form the RR vector. The specific steps are as follows:

[0090] (1.1) Five hash functions L, ψ, ϕ, T.sub.prim and T are initialized, the key values of these hash functions are corresponding routers, and the result mapped is a certain floating point value. For any r.sub.i∈R, L[r.sub.i] is a current minimum packet loss rate of the router r.sub.i, ψ[r.sub.i] is a RR packet loss rate of the router r.sub.i, ϕ[r.sub.i] is a maximum estimated packet loss rate from an upstream router of r.sub.i to the router r.sub.i in the primary path when multiple retransmission paths are considered, T.sub.prim[r.sub.i] is a primary path delay of the router r.sub.i, and T[r.sub.i] represents a RR delay of r.sub.i; where T[r.sub.i] covers the retransmission time superposition value of each router in the path.

[0091] (1.2) Under the initial condition, L=[1.0].sub.1×n, ψ=[1.0].sub.1×n, ϕ=[0].sub.1×n, T.sub.prim=[0].sub.1×n, T=[0].sub.1×n; let L[r.sub.j]=0, ψ[r.sub.j]=1, ϕ[r.sub.j]=0, T.sub.prim[r.sub.j]=0, T[r.sub.j]=0;

[0092] (1.3) A hash function P.sub.rsp is initialized, whose key value is a certain router r.sub.i, and the mapped result is a set of paths composed of RSPs, where the starting point of each RSP is r.sub.i and the ending point is a router other than r.sub.i.

[0093] The created hash function X.sup.0 represents a mapping from the router r.sub.i on the current primary path to the set P.sub.rsp(r.sub.i) corresponding to the redundant sub-path starting from r.sub.i.

[0094] (1.4) A Fibonacci heap q.sub.1 is created to sort routers, all routers in the set R are added to the heap q.sub.1, and are sorted according to the value of L[r.sub.i] from small to large; meanwhile, a vector prev.sub.1[r.sub.i] is created to record the last hop router of r.sub.i, which is initialized as prev.sub.1=[−1].sub.1×n;

[0095] (1.5) The first router r.sub.u in the current heap q.sub.1 is extracted; when the heap q.sub.1 is empty, it means that all routers in the heap q.sub.1 have been traversed, and skip to the step (1.18).

[0096] (1.6) For each output link l.sub.uv of r.sub.u extracted in step (1.5), the router r.sub.v opposite to r.sub.u on the output link l.sub.uv is calculated. Perform the iterative process of steps (1.7) to (1.16) until all links l.sub.uv of r.sub.u are traversed, and then skip to step (1.17) after the iteration.

[0097] If the r.sub.v obtained in step (1.6) is not in the current heap q.sub.1, skip to step (1.6) to calculate the r.sub.v corresponding to a next output link;

[0098] The maximum link delay τ′.sub.max of the current primary path is calculated as below:

τ′.sub.max=(τ(r.sub.u,r.sub.v)−τ.sub.trans(r.sub.u,r.sub.v))×α+τ(r.sub.u,r.sub.v)

[0099] where τ(r.sub.u,r.sub.v) represents the total delay from r.sub.u to r.sub.v, which is the sum of the transmission delay, the processing delay and the queuing delay; τ.sub.trans(r.sub.u,r.sub.v) represents the transmission delay from r.sub.u to r.sub.v;

[0100] (1.9) The total delay τ.sub.prim of the current primary path is calculated:

τ.sub.prim=T.sub.prim[r.sub.u]+τ(r.sub.u,r.sub.v)

[0101] where T.sub.prim[r.sub.u] indicates the primary path delay of the router r.sub.u.

[0102] The maximum allowable retransmission delay τ.sub.retrans.sup.max under the current selection of the primary path is calculated:

τ.sub.retrans.sup.max=D−T[r.sub.u]−τ.sub.prim

[0103] where D is the maximum allowable end-to-end delay.

[0104] (1.10) If τ.sub.prim≥D, skip to step (1.6) to calculate r.sub.v corresponding to another output link until all output links l.sub.uv of r.sub.u have been traversed, and skip to step (1.17);

[0105] (1.11) with r.sub.u as the destination router, the last hop router of the last search result is repeatedly searched according to prev.sub.1, and the router sequence X′ from r.sub.j to r.sub.u is obtained, which is specifically as below:

[0106] establishing a sequence X′, obtaining the last hop router prev.sub.1[r.sub.u] of r.sub.u according to prev.sub.1, and adding it to the sequence X′=(prev.sub.1[r.sub.u]); then finding the last hop router prev.sub.1[prev.sub.1[r.sub.u] of prev.sub.1[r.sub.u] from prev.sub.1, adding it to the current sequence and putting it in the first bit X′=(prev.sub.1[prev.sub.1[r.sub.u]],prev.sub.1[r.sub.u]); according to prev.sub.1, repeating the operation of searching for the last hop router, adding it to the current sequence X′ and putting it in the first bit until the obtained last hop router prev.sub.1[r.sub.j] is −1, stopping the cyclic operation and not putting −1 into the sequence X′; adding the destination router r.sub.u to the current sequence X′ and putting it in the last bit, X′=(r.sub.j, . . . , r.sub.u).

[0107] {circumflex over (L)} is defined to be a set of all links in the current primary path corresponding to the sequence X′.

[0108] (1.12) Let the variable P.sub.rsp=( ) to be used to record the generated RSP. Let i.sub.step=0, to be used for step counting. {tilde over (L)}={ } is a set of links to be excluded as much as possible, and the following steps are executed circularly:

[0109] (1.12.1) If i.sub.step≥β, the circulation is terminated and step (1.13) is executed.

[0110] (1.12.2) The RSP path generation module is called, and the current G, r.sub.v, X′, {circumflex over (L)}, {tilde over (L)}, η, α, τ.sup.l.sub.max, τ.sub.prim and τ.sub.retrans.sup.max are passed as parameters to the RSP path generation module to obtain the corresponding preselected path p.

[0111] (1.12.3) If the p generated in step (1.12.2) is empty or belongs to the current RSP set P.sub.rsp, the circulation is terminated and step (1.13) is executed.

[0112] (1.12.4) The p generated in step (1.12.2) is added to the set P.sub.rsp.

[0113] (1.12.5) If i.sub.step<β−1, all links in the p generated in step (1.12.2) are added to the set {tilde over (L)}.

[0114] (1.12.6) Let i.sub.step=i.sub.step+1, and skip to step (1.12.1) to enter the next cycle.

[0115] (1.13) Calculation:

ϕ.sup.0=∈(r.sub.u,r.sub.v).Math.Π.sub.p∈P.sub.rspϵ.sub.data(p)

L′=ϕ.sup.0.Math.ψ[r.sub.u]+L[r.sub.u]

[0116] where p′ is an intermediate variable, and ϵ(r.sub.u,r.sub.v) indicates the packet loss rate of a single link from r.sub.u to r.sub.v; ϵ.sub.data(p) is the packet loss rate of p under the condition of η retransmissions; L′ represents the current minimum packet loss rate when r.sub.v is selected as the next path node, ψ[r.sub.u] is the RR packet loss rate of the router r.sub.u, and L(r.sub.u) is the current minimum packet loss rate of the router r.sub.u.

[0117] (1.14) If L′≥L[r.sub.v], skip to step (1.5) to extract the next router r.sub.u; otherwise, continue to execute step (1.15); where L[r.sub.v] is the current minimum packet loss rate of the router r.sub.v.

[0118] (1.15) The following parameters are updated:

T[r.sub.v]=T[r.sub.u]+τ(r.sub.u,r.sub.v)+τ(r.sub.u,r.sub.v).Math.(1+α)+θ.sub.r(p′).Math.(η−1)+τ.sub.d(p′)

L[r.sub.v]=L′

ϕ[r.sub.v]=ϕ.sup.0

ψ[r.sub.v]=ψ[r.sub.u].Math.(1−ϕ[r.sub.u])

T.sub.prim[r.sub.v]=τ.sub.prim

prev.sub.1[r.sub.v]=r.sub.u

[0119] where p′ represents the preselected path with the smallest retransmission timeout in the set P.sub.rsp, θ.sub.r(p′) represents the retransmission timeout of p′, and r.sub.d(p′) represents the total downlink delay of p′; ψ[r.sub.v] is the RR packet loss rate of the router r.sub.v; T.sub.prim[r.sub.v] indicates the primary path delay of the router r.sub.v; prev.sub.1[r.sub.v] is the last hop router of r.sub.v.

[0120] (1.16) The operation is updated according to the standard key value of the Fibonacci heap, the key value L[r.sub.v] corresponding to the router r.sub.v in heap q.sub.1 is updated; let X.sup.0[r.sub.v]=P.sub.rsp, which means that the RSP set corresponding to a starting point of r.sub.v is P.sub.rsp. Then skip to step (1.6) to calculate the r.sub.v corresponding to another link.

[0121] (1.17) Skip to step (1.5) until the routers in the heap q.sub.1 have been traversed, the circulation ends, and step (1.18) is executed.

[0122] (1.18) The calculation result (prev.sub.1,X.sup.0) is assigned to the RR vector of the system.

[0123] II. RSP Path Generation Module

[0124] The module generates a maximum non-overlapping path from the router r.sub.v to all nodes in X′ according to G, r.sub.v, X′, {circumflex over (L)}, {tilde over (L)}, η, α, τ.sup.l.sub.max, τ.sub.prim, τ.sub.retrans.sup.max, where {circumflex over (L)} is a set of excluded invalid links, {tilde over (L)} is a set of links excluded from network topology G as much as possible. Firstly, a virtual router r.sub.vir is added in the network, so that r.sub.vir can be bidirectionally connected to each point r.sub.v,s in X′, and both the connection delay and packet loss rate are 0; all routers in the current network are pushed into the heap q.sub.2; the routers in the heap q.sub.2 are traversed, and a router r.sub.w with the smallest ψ′ value is taken from the current heap q.sub.2 every time; then, the output link l.sub.wx of the extracted r.sub.w and the opposite node r.sub.x are traversed; the redundant sub-path links and nodes are selected under the condition that the logarithmic value of the reliability should be as large as possible; the redundant sub-paths cannot pass through the link in the primary path, and the selected redundant sub-path links cannot make the retransmission delay of the node exceed the maximum allowable retransmission delay; the selected redundant sub-path links should make the logarithmic value of node reliability become larger; when a link is repeatedly considered as a redundant sub-path link, the overlapping of redundant sub-paths can be avoided as much as possible by minimizing the logarithmic value of the reliability of the link; prev.sub.2 is configured to record the last hop router according to the selected redundant sub-path links and nodes, and then search according to prev.sub.2 to get the router sequence from r.sub.v to r.sub.vir, and r.sub.v can reach any node in X′ through r.sub.vir; and then r.sub.vir is removed to obtain a preselected path p; finally, the preselected path p, the packet loss rate ϵ.sub.data and retransmission timeout θ.sub.r(p) of the redundant sub-paths in the case of η retransmissions are fed back to the RR vector generation module. The generation steps are as follows:

[0125] (2.1) A virtual router r.sub.vir is added in G, and the outer is bidirectionally connected to each point r.sub.v,s in X′, and the connection delay and packet loss rate are both 0. The adding method is as follows:

G=G∪{l=(r.sub.v,s,r.sub.vir)r.sub.v,s∈X′}

n′=|R|+1

[0126] where r.sub.v,s represents the opposite router of the s.sup.th RSP path of the router r.sub.vir; n′ indicates the number of routers in the current network, | | indicates modulo, and |R| indicates the number of routers.

[0127] (2.2) ψ′ and ψ′ vectors are created and their values are initialized to negative infinity. ψ′ represents the logarithmic value of the data packet transmission success rate corresponding to the current RSP under the condition of considering the exclusion of {tilde over (L)} as much as possible, in which the excluded link error rate will increase to ϵ.sub.expell; ϕ′ indicates a logarithmic value of the success rate of data packet transmission corresponding to the RSP in the current real situation; two hash tables τ.sub.up and τ.sub.down are created to record forwarding delays of upstream and downstream paths of each router node respectively; a retransmission timeout hash table θ.sub.retrans of each router node is created as follows:

ψ′=[−∞].sub.1×n′

ϕ′=[−∞].sub.1×n′

τ.sub.up={ }

τ.sub.down={ }

θ.sub.retrans=[0].sub.1×n′

[0128] (2.3) The values of τ.sub.up, τ.sub.down, ϕ′ and ψ′ corresponding to the router r.sub.v are initialized to 0, and a prev.sub.2 vector is created to record the previous hop router. ϵ.sub.expell is the logarithmic value of the minimum link reliability of L.sup.0 appearing in the current network G:

ϕ′[r.sub.v]=0

ψ′[r.sub.v]=0

τ.sub.up[r.sub.v]=0

τ.sub.down[r.sub.v]=0

prev.sub.2=[−1].sub.1×n′

ϵ.sub.expell=log[min.sub.l.sub.z.sub.∈L.sub.0((1−∈(l.sub.z))/C)]

[0129] where ϵ(l.sub.z) represents the packet loss rate of the path l.sub.z, and C is a constant greater than 1; at this time, L.sup.0 includes the newly added link l in step (2.1).

[0130] (2.4) q2 is initialized into a standard Fibonacci heap, and the key value of the heapψ′ is the value in ψ′. Then, each element in the router set R of the current network is pushed into the heap q.sub.2; the routers in the heap q.sub.2 are sorted according to the ψ′ value from small to large. The initial ψ′[r.sub.v]=0 is the minimum.

[0131] (2.5) If the number of routers in the current heap |q.sub.2|≤0, skip to step (2.12).

[0132] (2.6) The first router r.sub.w is taken out from the current heap q.sub.2. Steps (2.7) to (2.11) are cyclically executed for each egress link l.sub.wx of r.sub.w.

[0133] (2.7) The opposite node r.sub.x of r.sub.w on the link l.sub.wx is obtained. If l.sub.wx∈{circumflex over (L)} or r.sub.x is not in the heap q.sub.2, skip to step (2.6) and directly enter the next circulation.

[0134] (2.8) Firstly, the uplink delay τ.sub.up′ and the downlink delay τ.sub.down′ of the current RSP are calculated, which is specifically as follows:

τ.sub.up′=τ(r.sub.w,r.sub.x)+τ.sub.up[r.sub.w]

τ.sub.down′=τ(r.sub.x,r.sub.w)+τ.sub.down[r.sub.w]

[0135] where τ(r.sub.w,r.sub.x) represents the total delay from r.sub.w to r.sub.x, that is, the sum of a transmission delay, a processing delay and a queuing delay.

[0136] Then the retransmission timeout time θ.sub.retrans′ of the current router node is calculated:

θ.sub.retrans′=θ.sub.retrans[r.sub.w]+(τ.sub.queue(l.sub.wx)+τ.sub.process(l.sub.wx))×α+τ.sub.trans(l.sub.wx)

[0137] where τ.sub.queue(l.sub.wx) and τ.sub.process(l.sub.wx) represent the queuing delay and processing delay from r to r.sub.x, respectively.

[0138] Finally, the retransmission delay τ.sub.retrans′ of the current router node is calculated. If τ.sub.retrans′>τ.sub.retrans.sup.max, skip to step (2.6) until the routers in the heap q.sub.2 have been traversed:

τ.sub.retrans′=τ.sup.l.sub.max+τ.sub.prim+θ.sub.retrans′×(η−1)+τ.sub.down′

[0139] (2.9) The logarithmic value of the true reliability from r.sub.w to r.sub.x in real situation is calculated:

ψ.sub.1=log((1−ϵ(r.sub.w,r.sub.x))(1−ϵ(r.sub.x,r.sub.w)))

[0140] (2.10) The logarithmic value of the conversion reliability from r.sub.w to r.sub.x when calculating exclusion of L as much as possible:

={circumflex over (ψ)}+ψ′[r.sub.w]

[0141] where if l.sub.wx∈{tilde over (L)}, then {circumflex over (ψ)}=ϵ.sub.expell; otherwise {circumflex over (ψ)}=ψ.sub.1.

[0142] (2.11) If >ψ′[r.sub.x], then:

prev.sub.2[r.sub.x]=r.sub.w

ϕ′[r.sub.x]=

ψ′[r.sub.x]=ψ.sub.1+ψ′[r.sub.w]

[0143] Then, r.sub.x in the heap q.sub.2 is updated according to its corresponding key value ψ′[r.sub.x]. And τ.sub.up[r.sub.x] and τ.sub.down[r.sub.x] are updated:

τ.sub.up[r.sub.x]=τ(r.sub.w,r.sub.x)+τ.sub.up[r.sub.w]

τ.sub.down[r.sub.x]=τ(r.sub.x,r.sub.w)+τ.sub.down[r.sub.w]

[0144] where τ(r.sub.w,r.sub.x) represents the total delay from r.sub.w to r.sub.x. r.sub.w extracted next time in step (2.6) is r.sub.x here.

[0145] If ≤ψ′[r.sub.x], skip to step (2.6) until the routers in the heap q2 have been traversed, and execute step (2.12);

[0146] (2.12) The path from r.sub.v to r.sub.vir node is extracted from prev.sub.2, to obtain the preselected path p composed of a router sequence, which is specifically:

[0147] creating a sequence p, taking r.sub.vir as the destination node, obtaining the last hop router prev.sub.2[r.sub.vir] of r.sub.vir according to prev.sub.2, and adding it to the sequence p=(prev.sub.2[r.sub.vir]); then finding the last hop router prev.sub.2[prev.sub.2[r.sub.vir]] of prev.sub.2[r.sub.vir] in prev.sub.2, adding it to the current sequence and put it in the first bit p=(prev.sub.2[prev.sub.2[r.sub.vir]],prev.sub.2[r.sub.vir]); according to prev.sub.2, repeated the operation of searching for the last hop router, adding it to the current sequence P and putting it in the first bit, until the obtained prev.sub.1[r.sub.v] of the last hop router is −1, stopping the circulation operation, and obtaining p=(r.sub.v, . . . , r.sub.vir);

[0148] then remove r.sub.vir from p.

[0149] (2.13) Calculation:

∈.sub.one-way=1−e.sup.ψ′[r.sup.vir.sup.]

ϵ.sub.data(p)=ϵ.sub.one-way.sup.η

θ.sub.r(p)=α.Math.(τ.sub.up[r.sub.vir]+τ.sub.down[r.sub.vir])

[0150] where ϵ.sub.one-way indicates the one-way packet loss rate of the RSP from r.sub.v to r.sub.vir, ϵ.sub.data(p) indicates the packet loss rate of the RSP from r.sub.v to r.sub.vir in the case of η retransmissions, and θ.sub.r(p) indicates the retransmission timeout from r.sub.v to r.sub.vir.

[0151] (2.14) r.sub.vir is removed from G.

[0152] (2.15) The calculated p.sub.rsp=(p,ϵ.sub.data(p),θ.sub.r(p)) is returned to the caller, i.e., the RR vector generation module.

[0153] III. RR Communication Pair Generation Module

[0154] The module generates a resilient route RR according to a RR vector, a RR configuration, a current router and a destination router. Firstly, the primary path from r.sub.j to r.sub.k is searched according to prev.sub.1 output by the RR vector generation module, and the mapping of a primary path router and the redundant sub-path set starting from it is obtained from mapping X.sup.0, and an output Y of the system is obtained. The steps are as follows:

[0155] (3.1) The primary path p.sub.prim between the source router r.sub.j and the destination router r.sub.k from prev.sub.1 of the RR vector. The extraction method is as follows:

[0156] establishing a sequence p.sub.prim, taking r.sub.k as the destination router, obtaining the last hop router prev.sub.1[r.sub.k] of r.sub.k according to prev.sub.1, and adding it to a sequence p.sub.prim=(prev.sub.1[r.sub.k]); then find the last hop router prev.sub.1[prev.sub.1[r.sub.k]] of prev.sub.1[r.sub.k] from prev.sub.1, and adding it to the current sequence and putting it in the first bit p.sub.prim(prev.sub.1[prev.sub.1[r.sub.k]],prev.sub.1[r.sub.k]); according to prev.sub.1, repeating the operation of searching for the last hop router, adding it to the current sequence p.sub.prim and putting it in the first bit until the obtained prev.sub.1[r.sub.j] of the last hop router is −1, stopping the cyclic operation and not putting −1 into the sequence p.sub.prim; adding the destination router r.sub.k to the current sequence p.sub.prim and putting it in the last bit, p.sub.prim=(r.sub.j, . . . , r.sub.k).

[0157] (3.2) according to the input RR vector (prev.sub.1,X.sup.0) of this module and the prim calculated in step (3.1), the execution result Y of this module, that is, the RR path from r.sub.j to r.sub.k is calculated; the calculation method is as follows:

[0158] first, creating an empty hash table X={ }; for each router r.sub.p in p.sub.prim, obtaining P.sub.rsp(r.sub.p) corresponding to r.sub.p from X.sup.0, X=X∪{r.sub.p.fwdarw.P.sub.rsp(r.sub.p)|r.sub.p∈p.sub.prim}; at last, obtaining Y=(p.sub.prim,X).

[0159] (3.3) Y is fed back to the caller.

[0160] An embodiment of one embodiment of the present disclosure is as follows:

[0161] It is assuming that the communication network topology of a certain power grid is constructed by the standard IEEE 14 bus (bus). FIG. 2 shows the topology of this network. Suppose that a PMU is connected to r.sub.1 and A PDC is connected to r.sub.8. The topology is defined as G=(R,L.sup.0), n=14 and m=19. When the NDN router is running, the network topology provided by the router is input into the resilient route generation system. It is assuming that the delay and packet loss rate of any link in the topology are 171 μs and 2% respectively; the RR configuration parameters are as follows: η=3, α=3, β=5, D=50 ms; the current router is r.sub.1; if the destination router is r.sub.8, the RR generation process is as follows:

[0162] firstly, the RR vector generation module generates the corresponding RR vector according to the RR configuration, the current router, the destination router and G, and the steps are as follows:

[0163] I. RR Vector Generation Module

[0164] (1.1) Five hash functions L={ }, ψ={ }, ϕ={ }, T={ } and T.sub.prim={ } are created; L=[1.0].sub.1×n, ψ=[1.0].sub.1×n, ϕ=[0].sub.1×n, T.sub.prim=[0].sub.1×n, T=[0].sub.1×n, then let L(r.sub.1)=0, ψ(r.sub.1)=1, ϕ(r.sub.1)=0, T.sub.prim(r.sub.1)=0, T(r.sub.1)=0; a hash function X.sup.0={ } is created.

[0165] (1.2) A standard Fibonacci heap is created as q.sub.1, all routers in R are added to q.sub.1, and q.sub.1 sorts the routers according to the L value corresponding to each router, then q.sub.1=(r.sub.1,r.sub.2,r.sub.3,r.sub.4,r.sub.5,r.sub.6,r.sub.7,r.sub.8,r.sub.9,r.sub.10,r.sub.11,r.sub.12,r.sub.13,r.sub.14). Meanwhile, prev.sub.1=[−1].sub.1×n is created.

[0166] (1.3) The router with the lowest packet loss rate is extracted from q.sub.1 and recorded as r.sub.u, where r.sub.u=r.sub.1, and execution is continued because r.sub.u is not empty.

[0167] (1.4) For each link l.sub.uv of r.sub.u, such as (r.sub.1,r.sub.5), its opposite router r.sub.5 is calculated, and because r.sub.5 is in q, then τ.sup.l.sub.max=(τ(r.sub.1,r.sub.5)−τ.sub.trans(r.sub.1,r.sub.5))×α+τ(r.sub.1,r.sub.5)=(171−167)×3+171=179 μs is calculated; the maximum allowable retransmission delay τ.sub.retrans.sup.max=D−T[r.sub.1]−τ.sub.prim=49829 μs is calculated, where τ.sub.prim=171 μs. Since τ.sub.prim≥D is not valid, the execution will continue.

[0168] (1.5) The prev.sub.1 vector converted into a vector X′=(r.sub.1) from r.sub.1 to r.sub.1, since prev.sub.1[r.sub.1]=−1. {circumflex over (L)}={ }, {tilde over (L)}={ } is calculated.

[0169] (1.6) Let the variables P.sub.rsp=( ), i.sub.step=0. At this time, G, r.sub.v, X′, {circumflex over (L)}, {tilde over (L)}, η, α, τ.sup.l.sub.max, τ.sub.prim, τ.sub.retrans.sup.max are passed to the RSP path generation module, and the preselected path p=(r.sub.2,r.sub.5,r.sub.1) is obtained. Since p is not empty and does not belong to P.sub.rsp, then P.sub.rsp={(p=(r.sub.2,r.sub.5,r.sub.1),ϵ.sub.data (p)=0.0000621,τ.sub.down[r.sub.vir]=342 us,θ.sub.r(p)=716 us)}. Since i.sub.step0<β−1=4, all links in p, namely {(r.sub.2,r.sub.5),(r.sub.5,r.sub.1)}, are added to {tilde over (L)}, then {tilde over (L)}={(r.sub.2, r.sub.5), (r.sub.5, r.sub.1)}, then i.sub.step=i.sub.step+1=1; this step is repeated until the i.sub.step≥β, thus obtaining P.sub.rsp={(r.sub.2,r.sub.5,r.sub.1),(r.sub.2,r.sub.4,r.sub.5,r.sub.1),(r.sub.2,r.sub.3,r.sub.4,r.sub.9,r.sub.14,r.sub.13,r.sub.6,r.sub.5,r.sub.1)}.

[0170] (1.7) ϕ.sup.0=∈(r.sub.1, r.sub.2).Math.Π.sub.p∈P.sub.rsp∈.sub.data(p)=1.173292e−13, L′=ϕ.sup.0.Math.ψ(r.sub.1)+L(r.sub.1)=(1.173292e−13).Math.1+0=1.173292e−13 are calculated.

[0171] (1.8) Because L′<L(r.sub.2)=1.0, T(r.sub.2)=T(r.sub.1)+τ(r.sub.1,r.sub.2)+τ(r.sub.1,r.sub.2).Math.(1+α)+θ.sub.r(p′).Math.(η−1)+τ.sub.d(p′)=7617 μs, L(r.sub.1)=1.173292e−13, ϕ(r.sub.2)=1.173292e−13, ψ(r.sub.2)=ψ(r.sub.1).Math.(1−ϕ(r.sub.1))=1, T.sub.prim[r.sub.2]=171 μs, prev.sub.1[r.sub.2]=r.sub.1 are calculated.

[0172] (1.9) The key value corresponding to r.sub.2 in q.sub.1 is calculated, and X.sup.0[r.sub.2]=P.sub.rsp.

[0173] (1.10) For each link of r.sub.1, the related operation results are calculated according to the above steps (1.4) to (1.9), until all output links l.sub.uv of r.sub.u have been traversed.

[0174] (1.11) Skip to step (1.3), and calculate the related operation results until the routers in the heap q.sub.1 have been traversed.

[0175] (1.12) Finally, prev.sub.1=[−1,r.sub.1,r.sub.4,r.sub.5,r.sub.1,r.sub.5,r.sub.4,r.sub.7,r.sub.4,r.sub.11,r.sub.1,r.sub.6,r.sub.6,r.sub.6,r.sub.13], X.sup.0={r.sub.2.fwdarw.(r.sub.2,r.sub.5,r.sub.1),r.sub.3.fwdarw.(r.sub.3,r.sub.2,r.sub.1),r.sub.4.fwdarw.(r.sub.4,r.sub.2,r.sub.1),r.sub.5.fwdarw.(r.sub.5,r.sub.2,r.sub.1),r.sub.6.fwdarw.(r.sub.6,r.sub.11,r.sub.10,r.sub.9,r.sub.4,r.sub.5),r.sub.7.fwdarw.(r.sub.7,r.sub.9,r.sub.4),r.sub.9.fwdarw.(r.sub.9,r.sub.7,r.sub.4),r.sub.10.fwdarw.(r.sub.10,r.sub.9,r.sub.4,r.sub.5),r.sub.11.fwdarw.(r.sub.11,r.sub.10,r.sub.9,r.sub.4,r.sub.5),r.sub.12.fwdarw.(r.sub.12,r.sub.13,r.sub.6),r.sub.13.fwdarw.(r.sub.13,r.sub.12,r.sub.6),r.sub.14.fwdarw.(r.sub.14,r.sub.9,r.sub.4,r.sub.5)} is calculated, and (prev.sub.1,X.sup.0) is assigned to the RR vector of this system.

[0176] II. RSP Path Generation Module

[0177] In step (1.6) of the RR vector generation module, by taking the first execution of this step as an example, the input parameters of the RSP path generation module are G, r.sub.v=r.sub.2, X′=(1), {circumflex over (L)}={ }, {tilde over (L)}={ }, η=3, α=3, τ.sup.l.sub.max=179 ρs, τ.sub.prim171 μs and τ.sub.retrans.sup.max=49829 μs, respectively, which is executed as follows:

[0178] (2.1) Because r.sub.v,s is each point in X′, r.sub.vir is connected to {r.sub.1} (as shown in FIG. 2), and the related connection delay and packet loss rate are both 0, and the adding method is as follows: G=G∪{l=(r.sub.v,s,r.sub.vir)|x.sub.s∈X′}; meanwhile, n′=|R|+1=15 is calculated.

[0179] (2.2) ψ′=[−∞].sub.1×n′, ϕ′=[−∞].sub.1×n′, τ.sub.up={ } and τ.sub.down={ } are calculated.

[0180] (2.3) Because r.sub.v=r.sub.2, ϕ′(r.sub.2)=0, ψ′(r.sub.2)=0, τ.sub.up[r.sub.2]=0, τ.sub.down[r.sub.2]=0, prev.sub.2=[−1].sub.1×n′, ϵ.sub.expell=−1.118815, where C=3.

[0181] (2.4) q.sub.2 is initialized to a standard Fibonacci heap, and the key value of the heap is the value in ψ′. Then, each element in R is pushed into q.sub.2, where |q.sub.2|=15.

[0182] (2.5) As |q.sub.2|=15>0 at this time, execution is continued.

[0183] (2.6) An element drawn from q.sub.2 is named r.sub.w. For example, in the first cycle, r.sub.w=r.sub.2, and for each egress link l.sub.wx of r.sub.w, steps (2.7) to (2.11) are cyclically executed until |q|≤0.

[0184] (2.7) The opposite node r.sub.x of r.sub.w on l.sub.wx is obtained, for example, in the first cycle, r.sub.x=r.sub.3, at this time, the execution will be continued since l.sub.wx.Math.{circumflex over (L)} and r.sub.2 is included in q.sub.2.

[0185] (2.8) τ.sub.up′, τ.sub.down′, θ.sub.retrans′ and τ.sub.retrans′ are calculated. For example, in one cycle, τ.sub.up′=171 μs, τ.sub.down′=171 μs, θ.sub.retrans′=358 μs, τ.sub.retrans′=1237 μs are calculated. Since τ.sub.retrans′≤τ.sub.retrans.sup.max, the execution will be continued.

[0186] (2.9) ψ1 is calculated, for example, in the first cycle, ψ.sub.1=log((1−ϵ(r.sub.2,r.sub.3))(1−ϵ(r.sub.2,r.sub.3)))=−0.0404054 is calculated.

[0187] (2.10) is calculated, and for example, in the first cycle, since l.sub.wx.Math.{tilde over (L)}, then {circumflex over (ψ)}=−0.0404054; ={circumflex over (ψ)}+ψ[r.sub.2]=−0.0404054 is calculated.

[0188] (2.11) The values of prev.sub.2[r.sub.x], ϕ′[r.sub.x], ψ′[r.sub.x], τ.sub.up[r.sub.x], τ.sub.down[r.sub.x] are calculated; since >ψ[r.sub.v]=−∞, prev.sub.2[r.sub.3]=r.sub.2, ϕ′[r.sub.3]=−0.0404054, ψ′[r.sub.3]=ψ.sub.1+ψ[r.sub.2]=−0.0404054; the heap q.sub.2 is updated according to the key value corresponding to r.sub.3.

[0189] (2.12) The path p=(r.sub.2,r.sub.5,r.sub.1) from r.sub.2 to the node r.sub.vir is extracted from prev.sub.2.

[0190] (2.13) ϵ.sub.one-way=0.077632, ϵ.sub.data(p)=0.0004679, θ.sub.r(p)=α.Math.(τ.sub.up[r.sub.vir]+τ.sub.down[r.sub.vir])=716 μs are calculated.

[0191] (2.14) r.sub.vir is removed from G.

[0192] (2.15) The calculated result p.sub.rsp=(p=(r.sub.2,r.sub.5,r.sub.1),ϵ.sub.data(p)=0.0000621,τ.sub.down[r.sub.vir]=342 μs,θ.sub.r(p)=716 μs) is returned to the caller.

[0193] III. RR Communication Pair Generation Module

[0194] Assuming that the RR vector and RR configuration are the same as the input of the RR vector generation module mentioned above, the source router r.sub.j=r.sub.1 and the destination router r.sub.k=r.sub.8, and the RR generation steps are as follows:

[0195] (3.1) The path between r.sub.1 and r.sub.8 is extracted from prev.sub.3, p.sub.prim(r.sub.1,r.sub.5,r.sub.4,r.sub.7,r.sub.8).

[0196] (3.2) The RR path from r.sub.1 to r.sub.8 is obtained by calculation:

Y=(p.sub.prim=(r.sub.1,r.sub.5,r.sub.4,r.sub.7,r.sub.8),X={{r.sub.5.fwdarw.{(r.sub.5,r.sub.2,r.sub.1),(r.sub.5,r.sub.4,r.sub.2,r.sub.1),(r.sub.5,r.sub.6,r.sub.11,r.sub.10,r.sub.9,r.sub.4,r.sub.3,r.sub.2,r.sub.1)},{r.sub.4.fwdarw.{(r.sub.4,r.sub.2,r.sub.1),(r.sub.4,r.sub.3,r.sub.2,r.sub.5),(r.sub.4,r.sub.9,r.sub.14,r.sub.13,r.sub.6,r.sub.5),(r.sub.4,r.sub.7,r.sub.9,r.sub.10,r.sub.11,r.sub.6,r.sub.5)}},{r.sub.7.fwdarw.{(r.sub.7,r.sub.9,r.sub.4),(r.sub.7,r.sub.9,r.sub.10,r.sub.11,r.sub.6,r.sub.5)}}}).

[0197] (3.3) At this time, the maximum data delivery delay of Y is τ[r.sub.k]=18937 μs, which meets the requirement of the maximum delay D=50 ms, and Y is fed back to the caller.

[0198] It should be noted that when the data compression apparatus provided in the foregoing embodiment performs data compression, division into the foregoing functional modules is used only as an example for description. In an actual application, the foregoing functions can be allocated to and implemented by different functional modules based on a requirement, that is, an inner structure of the apparatus is divided into different functional modules, to implement all or some of the functions described above. For details about a specific implementation process, refer to the method embodiment. Details are not described herein again.

[0199] All or some of the foregoing embodiments may be implemented by using software, hardware, firmware, or any combination thereof. When the software is used for implementation, all or some of the embodiments may be implemented in a form of a computer program product. The computer program product includes one or more computer instructions. When the computer program instructions are loaded and executed on a server or a terminal, all or some of the procedures or functions according to the embodiments of this application are generated. The computer instructions may be stored in a computer-readable storage medium or may be transmitted from a computer-readable storage medium to another computer-readable storage medium. For example, the computer instructions may be transmitted from a website, computer, server, or data center to another website, computer, server, or data center in a wired (for example, a coaxial optical cable, an optical fiber, or a digital subscriber line) or wireless (for example, infrared, radio, or microwave) manner. The computer-readable storage medium may be any usable medium accessible by a server or a terminal, or a data storage device, such as a server or a data center, integrating one or more usable media. The usable medium may be a magnetic medium (for example, a floppy disk, a hard disk, or a magnetic tape), an optical medium (for example, a digital video disk (DVD)), or a semiconductor medium (for example, a solid-state drive).