CN104009915A - A Novel Routing Algorithm Using Bandwidth Allocation to Simplify Complex Networks - Google Patents

Abstract

The present invention provides a brand-new bandwidth-based traffic distribution algorithm—TDBB (Traffic Distribution Based on Bandwidth). The TDBB algorithm uses bandwidth allocation to gradually simplify a complex network into an equivalent simple network, so as to perform traffic allocation. By dividing the source traffic into multiple shares according to a certain proportion (this proportion is determined by the bandwidth of each path), they are respectively distributed to The transmission of multiple paths (the bandwidth of each path is determined by the minimum bandwidth of the path) maximizes the use of network resources. Adopt the present invention, can realize three purposes: A. Make the utilization rate of network bandwidth improve to the greatest extent: the situation that resources will not be idle; B. Use the shortest time to send traffic from the source end to the The traffic is transmitted through multiple paths instead of a single path, and the transmission rate is greatly improved; C. Realize traffic balance: Congestion will only occur when the traffic exceeds the total load of the entire network resource.

Description

A kind of novel routing algorithm that utilizes allocated bandwidth to simplify complex network

Technical field

The present invention relates to optical communication technique field, the thinking of wherein introducing traffic engineering in light packet switching is carried out the equalization of assignment of traffic.A kind of novel routing algorithm that utilizes allocated bandwidth to simplify complex network of special design.

Technical background

1, light packet switching refers in the process from information source to the stay of two nights, the payload part of packet remains in light territory, and according to exchange, the technology difference controlled, the control section (expense) of packet can be at middle switching node place through or without the conversion of O/E/O.In other words, the transmission of packet is carried out in wide area, and route is carried out in electric territory or light territory.Light packet switching is all used the solution of this mixing at present, and transmission realizes in light territory with exchange, and route and forwarding capability are realized in electric mode.

2, the key technology of light packet switching is: the generation of light grouping, it is synchronous that light divides into groups, and solves method and the light buffer memory of competition, the regeneration of light grouping.

3, the main implementation method of traffic engineering is to utilize constraint route to calculate to show paths, and the recycling mode of showing paths is set up label switched path (LSP) and utilizes label switched path to carry out assignment of traffic.Adopt the benefit of traffic engineering to have: to support explicit routing, not selected by the restriction realizing route that forwards grouping according to object, flow equalization, self-healing recovery, path priority etc.Traffic engineering generally has two kinds of implementations: line model and off-line mode.

Introduce GMPLS traffic engineering control plane; can simplify the process of control information processing Route Selection in optical packet switch network; simultaneously; the perfect traffic engineering mechanism of GMPLS can reduce network traffics traffic congestion rate and reduce packet loss; thereby the load balancing of realization, and protection and Restoration Mechanism.

Summary of the invention

(1) technical problem that will solve

The algorithm of tradition traffic engineering is the shortest path finding in network, then data are just only along this shortest path transmission, until volume of transmitted data reaches the maximum load in this path, cause the congested of this path, just unnecessary data are forwarded by all the other paths.Known, conventional flow quantity algorithm has three problems:

A. only transmit the idle one waste to Internet resources beyond doubt in all the other paths by shortest path;

B. a certain amount of flow, from source to egress, if only by a paths (even shortest path), and separates flow by a certain percentage, transmits respectively by mulitpath, and the time used must be that the former is far longer than the latter;

C. after shortest path appearance is congested, just considers data to forward by other paths, and judge that whether certain paths is congested and all can expend a lot of unnecessary time to congested processing.

(2) technical scheme

Be different from traditional algorithm, the invention provides one and utilize allocated bandwidth, progressively a complex network is reduced to an equivalent simple network, thereby carry out the novel routing algorithm of assignment of traffic.It is characterized in that according to the network of simplifying, by the flow of source by a certain percentage (this ratio is determined by the bandwidth in each path) be divided into n part, be distributed to respectively n paths (bandwidth of every paths is determined by this path minimum bandwidth) transmission.Specifically there are following steps.

Step 1, a given network G ₁=(V, E), has certain flow need to pass through source v _ssend to egress v _t;

Step 2, network G ₁each limit e ₁(i, j) has two attributes:

A. the cost w of this edge ₁(i, j);

B. this edge flow f that can pass through at most per second ₁(i, j), i.e. bandwidth;

Step 3, according to the cost w on every limit ₁(i, j), finds out source v with shortest path first _sto egress v _tshortest path P ₁;

Step 4, at shortest path P ₁in, find out the limit of bandwidth minimum, using the bandwidth on this limit as shortest path P ₁bandwidth; So this shortest path is reduced to a limit e ₁(s, t), the two ends of this edge are source v _swith egress v _t, and:

Limit e ₁the cost of (s, t) is as shown in formula (1)

$w_1(s,t)=\mathrm{\Σ}{w}_1(i,j),e_1(i,j)\∈E_{P_1}---\left(1\right)$

Limit e ₁the bandwidth of (s, t) is as shown in formula (2)

$f_1(s,t)=\min f_1(i,j),e_1(i,j)\∈E_{P_1}---\left(2\right)$

Wherein, p ₁the set on all limits.

Step 5, in network G ₁in,

If limit the bandwidth value after this edge renewal is as shown in formula (3):

f ₂(i,j)＝f ₁(i,j)-f ₁(s,t) (3)

Like this, obtain a new network G ₂=(V, E).At G ₂in:

w ₂(i,j)＝w ₁(i,j)

$f_2(i,j)=f_1(i,j)-f_1(s,t),e_1(i,j)\∈E_{P_1}$

$f_2(i,j)=f_1(i,j),e_1(i,j)\∉E_{P_1}$

Step 6, at G ₂in, (easily know, these limits are exactly shortest path P to remove all bandwidth and be 0 limit ₁the limit of middle bandwidth minimum).Find out G ₂in by source v _sto egress v _tshortest path P ₂.

Step 7, at shortest path P ₂in, find out the limit (may more than) of bandwidth minimum, using the bandwidth on this limit as shortest path P ₂bandwidth; So this shortest path is reduced to a limit e ₂(s, t), the two ends of this edge are source v _swith egress v _t, and:

Limit e ₂the cost of (s, t) is as shown in formula (4):

$w_2(s,t)=\mathrm{\Σ}{w}_2(i,j),e_2(i,j)\∈E_{P_2}---\left(4\right)$

Limit e ₂the bandwidth of (s, t) is as shown in formula (5):

$f_2(s,t)=\min f_2(i,j),e_2(i,j)\∈E_{P_2}---\left(5\right)$

Wherein, p ₂the set on all limits.

Step 8, repetition above-mentioned steps, can obtain new network, new shortest path P, and new limit e (s, t).Suppose in new network G _n+1in, do not have path can make v _sarrive v _t, stop; The now network G of " remaining " of record _n+1, like this, just obtained n bar from v _sto v _tpath.

Step 9, network G ₁finally can be reduced to such network G (V, E):

Only has v _sand v _ttwo end points, and between these two end points, have n bar limit to be connected: e ₁(s, t), e ₂(s, t) ... e _n(s, t).

Step 10, at every paths P _ion the flow value that should distribute as shown in formula (6)

$F_i=F*\frac{f_i(s,t)}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{f}_i(s,t)}---\left(6\right)$

Wherein, F is total flow, f _i(s, t) is path P _ibandwidth

Step 11, New Algorithm can draw following result

From v _sto v _tspeed as shown in formula (7)

v＝∑f _i(s,t) (7)

Utilize New Algorithm, can be with the flow that is F by size of the shortest time from source v _spass to egress v _t, the time used is as shown in formula (8)

$t=\frac{F}{v}=\frac{F}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{f}_i(s,t)}---\left(8\right)$

Network bandwidth utilization factor is as shown in formula (9)

$\mathrm{\η}=\frac{\mathrm{\Σ}{f}_1(i,j)-\mathrm{\Σ}{f}_{n+1}(i,j)}{\mathrm{\Σ}{f}_1(i,j)}---\left(9\right)$

Preferably, two of the network described in step 2 attributes: cost and bandwidth.It is characterized in that: so-called " bandwidth ", refer to this link flow that can transmit at most per second, wherein consider the time of the processing to data of router, so be not simple bandwidth.But discuss for convenient, regarded for the time being as bandwidth here.Such as, A is to the 80M/s that can transmit at most per second between B, and these data are that the factor such as bandwidth and route A and the time of B to data processing that has considered link draws, also can be described as in actual transmissions, A, to the B maximum stream flow that can transmit per second, is the value that can measure.Determine the factor of cost and " bandwidth ", some is common, also have impact even between the two, but how do not need specifically to know between them affects, because the shortest path (comprising former network) of the new network constantly generating on former network foundation is just found in the effect of this parameter of cost.Meanwhile, also it should be noted that any is, is not that cost is higher, and " bandwidth " is just necessarily less, because be not the relation of positive inverse ratio between the two.

Preferably, in described step 4, shortest path is reduced to a limit, it is characterized in that: the limit end points of this simplification is source v _swith egress v _t, cost is each limit cost sum of this shortest path, bandwidth is on this shortest path, the bandwidth on the limit of bandwidth minimum.

Preferably, the new network being obtained by legacy network in described step 5, is characterized in that: newly-generated network is to obtain after some limit of former network changes bandwidth value.These limits are the limits on shortest path, and its new bandwidth value is that original bandwidth has deducted on this shortest path minimum bandwidth and obtains.So just obtain new network.In new network, the bandwidth value on inevitable some limit has become 0, can remove these bandwidth and be 0 limit.

Preferably, described step 6, seven, eight, is on the basis of new network, finds the shortest path of new network, and according to similar before step, it is source v that new shortest path can be simplified to again an end points _swith egress v _tlimit, then new network is carried out according to new shortest path " transformation ", just generated the network of a renewal, like this, repeat down, until new network is the network of " remaining " always.The feature of the network of " remaining " is: in described step H, the network of " remaining " does not have path can make v _sarrive v _t.

Preferably, in described step 9, legacy network can be simplified to a very simple network, it is characterized in that: the network after simplification only has v _sand v _ttwo end points, and between these two end points, have n bar limit to be connected: e ₁(s, t), e ₂(s, t) ... e _n(s, t).

Preferably, the flow of source is divided into n part by described step 10, transmits respectively by n paths, between the data volume of every paths transmission, is proportional, it is characterized in that: every paths P _ion the flow value that should distribute be

$F_i=F*\frac{f_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{f}_i}$

Wherein, F is total flow, f _iit is path P in the network of simplifying _ibandwidth.

Preferably, three data (transmission rate, transmission time and network bandwidth utilization factor) that described step 11 obtains, it is characterized in that: these three data obtain after flow distributes according to step J, compare with traditional algorithm, there is transmission rate faster, shorter transmission time and the network bandwidth utilization factor of Geng Gao.

Accompanying drawing 1 is algorithm flow chart.

(3) beneficial effect

Adopt the present invention, can solve three problems of conventional data transmission algorithm, can realize following three beneficial effects:

A. make network bandwidth utilization factor be improved to greatest extent: all links are utilized, there will not be the situation of resources idle;

B. with the shortest time, flow is sent to egress from source: a certain amount of flow is transmitted by mulitpath, instead of single-pathway, transmission rate improves greatly;

C. make network bandwidth utilization factor be improved to greatest extent and realize flow equalization: only have in the time that flow exceedes the total load of whole Internet resources, just there will be congestion situation, instead of in traditional algorithm, the load that flow exceedes single path just there will be congested.

Brief description of the drawings

Accompanying drawing 1 is the flow chart of New Algorithm (TDBB algorithm).

Accompanying drawing 2 is that A is source, the example network that F is egress.

Accompanying drawing 3 is the new networks that obtain on the basis of accompanying drawing 2.

Accompanying drawing 4 is the new networks that obtain on the basis of accompanying drawing 3.

Accompanying drawing 5 is the new networks that obtain on the basis of accompanying drawing 4.

Accompanying drawing 6 is the new networks that obtain on the basis of accompanying drawing 5, is the network of " remaining ".

Accompanying drawing 7 be adopt TDBB algorithm that obtain with simple and easy network Fig. 2 equivalence.

Accompanying drawing 8 be with reference to the accompanying drawings 6 on accompanying drawing 2 bases improved bandwidth availability ratio can reach 100% network.

Embodiment

Below in conjunction with drawings and Examples, the specific embodiment of the present invention is described in further detail.Following examples are used for illustrating the present invention, but are not used for limiting the scope of the invention.

Network by algorithm application in accompanying drawing 2, step is as follows.

1) utilize shortest path first to find out the shortest path P in accompanying drawing 2 ₁:

A→B→D→E→F

Path P ₁total cost be 7, bandwidth is 50M/s (getting the minimum bandwidth on path).

2), according to algorithm, on the basis of accompanying drawing 2, obtain accompanying drawing 3

Accompanying drawing 3 is with the difference of accompanying drawing 2, belongs to P ₁the bandwidth value on the limit in path has deducted 50M/s, and wherein DE limit bandwidth value has become 0, so DE limit is removed.Find out the shortest path P in accompanying drawing 3 with shortest path first ₂:

A→B→C→F

Path P ₂total cost be 10, bandwidth is 60M/s.

3), according to algorithm, on the basis of accompanying drawing 3, obtain accompanying drawing 4

Find out the shortest path P in accompanying drawing 4 ₃:

A→D→C→F

P ₃cost is 12, and bandwidth is 30M/s.

4), according to algorithm, on the basis of accompanying drawing 4, obtain accompanying drawing 5

Find out the shortest path P in accompanying drawing 5 ₄:

A→D→B→C→E→F

P ₄cost is 19, and bandwidth is 10M/s

5), according to algorithm, on the basis of accompanying drawing 5, obtain accompanying drawing 6

In accompanying drawing 6, having can not find the path from A to F, is " the remaining network " defining in algorithm, so to this termination.

6) final, network accompanying drawing 2 is simplified for as shown in Figure 7

Suppose to have 300M flow to pass to F from A, according to formula

$F_i=F*\frac{f_i}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{f}_i}$

Known, the flow that need to distribute respectively to path P 1, P2, P3, P4 is 100M, 120M, 60M and 20M.

By formula

$v=\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{f}_i(s,t)$

Known, the transmission rate from A to F is 150M/s.

By formula

$t=\frac{F}{v}=\frac{F}{\underset{i=1}{\overset{n}{\mathrm{\Σ}}}{f}_i(s,t)}$

Known, 300M flow passes to F from A, only needs the time of 2 seconds.

By formula

$\mathrm{\η}=\frac{\mathrm{\Σ}{f}_1(i,j)-\mathrm{\Σ}{f}_{n+1}(i,j)}{\mathrm{\Σ}{f}_1(i,j)}$

Known, network broadband utilance is 91.23%.

For network manager, need make 33.3% flow walk P1 path,

A→B→D→E→F

Make 40% flow walk P2 path,

A→B→C→F

Make 20% flow walk P3 path,

A→D→C→F

Make 6.7% flow walk P4 path,

A→D→B→C→E→F

Further application of the present invention

From example above, can see, network bandwidth utilization factor has reached 91.23%, can network bandwidth utilization factor reach 100% so?

If according to the network of accompanying drawing 2,91.23% the utilance that TDBB algorithm obtains is exactly the peak use rate of this network, can not promote again.But, can consider now so a kind of situation, with reference to accompanying drawing 6, accompanying drawing 2 is carried out to some amendments, amended network is as shown in Figure 8

Comparative drawings figs 2 and accompanying drawing 8 can be found, limit AD, and BD, CE has reduced respectively 10M/s, the bandwidth of 10M/s and 30M/s (note that accompanying drawing 6 only has three limit: AD, BD, CE, the bandwidth on these three limits is respectively 10M/s, 10M/s and 30M/s).Now accompanying drawing 8 is used to TDBB algorithm, we can find, the result finally obtaining and the result of using TDBB algorithm to obtain to accompanying drawing 2 are in full accord, unique difference is, the network bandwidth utilization factor of accompanying drawing 8 has reached 100%, and (network of final " remaining " has only been left end points, do not have limit, i.e. the set on limit is empty set).It can be seen, build a network in real life time, can adjust according to TDBB algorithm the bandwidth of each link completely, make network bandwidth utilization factor reach 100%, such as the network in accompanying drawing 2, its AD link, BD link and CE link are many respectively 10M/s, the unnecessary bandwidth of 10M/s and 30M/s.That is to say that the network in accompanying drawing 2 can reconstruct as the network in accompanying drawing 8, thereby Internet resources are utilized to the fullest.

Claims (8)

1. A new routing algorithm that utilizes bandwidth allocation to gradually simplify a complex network into an equivalent simple network, thereby carrying out traffic distribution. decision) is divided into n parts and distributed to n paths (the bandwidth of each path is determined by the minimum bandwidth of the path) respectively for transmission. The specific steps are as follows: A: Given a network G ₁ = (V, E), there is a certain amount of traffic that needs to be sent to the sink v _t through the source end v _s ; B: Each edge e ₁ (i,j) of network G ₁ has two properties: a. The cost of this edge w ₁ (i,j); b. The maximum flow f ₁ (i,j) that can pass through this edge per second, that is, the bandwidth; C: According to the cost w ₁ (i, j) of each edge, use the shortest path algorithm to find the shortest path P ₁ from the source end v _s to the sink end v _t ; D: In the shortest path P ₁ , find the edge with the smallest bandwidth, and use the bandwidth of this edge as the bandwidth of the shortest path P ₁ ; thus, this shortest path is simplified to an edge e ₁ (s, t), that is, this The two ends of the edge are the source end v _s and the sink end v _t , and: The cost of edge e ₁ (s,t) is shown in formula (1) ${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$ The bandwidth of edge e ₁ (s,t) is shown in formula (2) ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; min</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$ in, is the set of all edges of P ₁ ; E: In network G ₁ , Wakabe Then the updated bandwidth value of this edge is shown in formula (3): f ₂ (i,j)=f ₁ (i,j)-f ₁ (s,t) (3) In this way, a new network G ₂ =(V,E) is obtained, in G ₂ : w ₂ (i,j)=w ₁ (i,j) ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}$ ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&NotElement;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}$ F: In G ₂ , remove all edges with a bandwidth of 0 (it is easy to know that these edges are the edges with the smallest bandwidth in the shortest path P ₁ ), and find the shortest path from the source end v _s to the sink end v _t in G ₂ path _P2 ; G: In the shortest path P ₂ , find the edge with the smallest bandwidth (maybe more than one), and use the bandwidth of this edge as the bandwidth of the shortest path P ₂ ; thus, this shortest path is simplified to an edge e ₂ (s,t ), that is, the two ends of this edge are the source end v _s and the sink end v _t , and: The cost of edge e ₂ (s,t) is shown in formula (4): ${\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; w</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$ The bandwidth of edge e ₂ (s,t) is shown in formula (5): ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; min</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; e</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; E.</span>}}_{{\mathrm{<span\; class="notranslate">\; P</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$ in, is the set of all edges of P ₂ ; H: Repeat the above steps to get a new network, a new shortest path P, and a new edge e(s,t); assuming that in the new network G _n+1 , there is no path that can make v _s reach v _t , Then terminate; record the "surviving" network G _n+1 at this time, so that n paths from v _s to v _t are obtained; I: The network G ₁ will eventually be reduced to such a network G(V,E): There are only two endpoints v _s and v _t , and there are n edges connecting these two endpoints: e ₁ (s,t), e ₂ (s,t),...e _n (s,t); J: The flow value that should be distributed on each path P _i is shown in formula (6) ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; *</span>\frac{{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 6</span>}<span\; class="notranslate">\; )</span>$ where F is the total traffic, f _i (s,t) is the bandwidth of path P _i K: The new algorithm can get the following results The rate from v _s to v _t is given by equation (7) v=∑f _i (s,t) (7) Using the new algorithm, the flow of size F can be transmitted from the source end v _s to the sink end v _t in the shortest time, and the time used is shown in formula (8) $\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; f</span>}}{\mathrm{<span\; class="notranslate">\; v</span>}}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; f</span>}}{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 8</span>}<span\; class="notranslate">\; )</span>$ Network bandwidth utilization is shown in formula (9) $\mathrm{<span\; class="notranslate">\; \&eta;</span>}<span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 9</span>}<span\; class="notranslate">\; )</span>$ In formula (9), ∑f ₁ (i,j) represents the bandwidth sum of all edges in the original network, and ∑f _n+1 (i,j) represents the G _n+1 network (the path from v _s to v The sum of the bandwidths of all edges in the residual network of the path of _t ) (for the edge e _n+1 (i,j) that does not exist in G _n+1 , its bandwidth is 0); it is not difficult to see that if G _n+1 If the set of middle edges is empty, it means that the bandwidth of each edge of the network is just utilized, and the utilization rate of network bandwidth is 100%. It can be seen from this that the new algorithm taps out the maximum potential of the network. 2. Two attributes of the network as claimed in claim 1: cost and bandwidth, characterized in that: "bandwidth" in the step B refers to the maximum flow that this link can transmit per second, where considering The data processing time of the router is limited, so it is not pure bandwidth; but for the convenience of discussion, here it is regarded as bandwidth for the time being: for example, a maximum of 80M/s can be transmitted per second between A and B, and this data is Considering the bandwidth of the link and the data processing time of routes A and B, it can also be said that in actual transmission, the maximum flow that can be transmitted from A to B per second is a measurable value; Some of the factors that determine the cost and "bandwidth" are common, and even have an impact between the two, but it is not necessary to know how they affect each other, because the role of the cost parameter is only to find the original network basis. The shortest path (including the original network) of the new network constantly generated on the network; at the same time, it should be noted that the higher the cost, the smaller the "bandwidth" must be, because the two are not directly proportional relation. 3. Simplify the shortest path into a side as claimed in claim 1, characterized in that: the side in the step D, the end points are the source end v _s and the sink end v _t , the cost of this simplified side is this The sum of the cost of each edge of the shortest path; the bandwidth of this simplified edge is the bandwidth of the edge with the smallest bandwidth on this shortest path. 4. as the new network that obtains by original network among the claim 1, it is characterized in that: the newly generated network in the described step E is obtained after some sides of the original network change the bandwidth value; These sides are the shortest The new bandwidth value of the edge on the path is obtained by subtracting the minimum bandwidth on the shortest path from the original bandwidth, so that a new network is obtained, and the bandwidth value of some edges in the new network must become 0, which can be Remove these edges with a bandwidth of 0. 5. As in claim 1, on the basis of the new network, search for the shortest path of the new network, according to similar steps before, the new shortest path can be simplified into an end point that is the edge of the source end _vs and the sink end v _t , and then "reform" the new network according to the new shortest path, and an updated network is generated. In this way, it is repeated until the new network is a "survival"network; the characteristics of the "survival" network are: The "surviving" network in step H has no path from v _s to v _t . 6. as described in claim 1, original network can be simplified into a very simple network, it is characterized in that: the network after the simplification of described step 1 has only v _s and v _t two endpoints, and these two endpoints There are n edges connected between them: e ₁ (s, t), e ₂ (s, t), ... e _n (s, t). 7. As claimed in claim 1, the traffic at the source end is divided into n parts, which are transmitted through n paths respectively, and the amount of data transmitted by each path is proportional, and it is characterized in that: each path P _i of the step J The flow value that should be assigned on is ${\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; *</span>\frac{{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}{\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; f</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}}$ Among them, F is the total traffic, and f _i is the bandwidth of path P _i in the simplified network. 8. as the last three data (transmission rate, transmission time and network bandwidth utilization rate) that obtain in claim 1, it is characterized in that: these three data obtain after flow is distributed according to step J, compare with traditional algorithm , with faster transmission rate, shorter transmission time and higher network bandwidth utilization.