CN101485104B - System for rate-control of aggregate-rate communication services - Google Patents
System for rate-control of aggregate-rate communication services Download PDFInfo
- Publication number
- CN101485104B CN101485104B CN200780025604.XA CN200780025604A CN101485104B CN 101485104 B CN101485104 B CN 101485104B CN 200780025604 A CN200780025604 A CN 200780025604A CN 101485104 B CN101485104 B CN 101485104B
- Authority
- CN
- China
- Prior art keywords
- port
- rate
- aggregation group
- speed
- inlet
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
A method of rate-control for a group of ports in a communication network. Ramping is performed for allowed-rate of each of the group of ports, if sum of the ingress-rates of the group of ports is less than a given rate threshold; and adjusting is performed for allowed-rate of each of the group of ports, if sum of the ingress-rates of the group of ports is greater than or equal to the given rate threshold, such that the sum of allowed-rates of the group of ports is equal to the given rate threshold.
Description
Technical field
The present invention relates generally to the network communications technology, relate in particular to a kind of multiplex system of the speed control for aggregate-rate communication services.
Background technology
Ethernet is to dispose one of local area network (LAN) (LAN) technology the most widely.Some advantages that user is Ethernet service are attracted, and comprise easy to use, cost benefit, flexibility and service selection etc. on a large scale.Ethernet service has expanded to metropolitan area and farther scope.
Ethernet service can change to some extent aspect a lot.Metro Ethernet Forum (MEF) has defined the Ethernet service of two types: E-Line business and E-LAN business, wherein E-Line business is point to point service, PTP, and E-LAN business is multipoint service and makes each srvice instance share the use of common lower layer physical network.MEF has specified different 1 layer and 2 layers of E-LAN business.1 layer of E-LAN business is called as ethernet lan (ELAN) business, and 2 layers of E-LAN business are called as ethernet virtual lan (EVLAN) business.EVLAN allows user's switching frame as being connected to the LAN of shared medium.
Two kinds of methods of the committed rate of the current EVLAN of being used to specify business are that port-to-port is promised to undertake and every port guarantee.Port-to-port is promised to undertake as the flow appointment definite undertaking bandwidth from particular port to another particular port.This is that a kind of routine providing in frame relay and private line service is promised to undertake.In the time that the flow rate of port-to-port is comparatively constant, this method may be more effective.
Every port guarantee is the specifies distinct bandwidth guaranteed for traffic that is derived from each port, and where does not consider destination interface.This promise is easier to maintain, because only need the information of local port inlet flow rate.
Summary of the invention
The invention provides a kind of method of the port set in communication network being carried out to speed control.If the inlet rate sum of port set is less than given rate-valve value, the permission speed of the each port to port set is carried out oblique ascension; And if the inlet rate sum of port set is more than or equal to given rate-valve value, regulate the permission speed of each port of port set, make the permission speed sum of port set equal described given rate-valve value.
In one embodiment, for sharing one group of port of committed rate, each port obtains the inlet rate information of all of the port of this group port; If the inlet rate sum of all of the port is less than committed rate, improves it and allow speed; And if the inlet rate sum of all of the port is more than or equal to committed rate, regulate it to allow speed, make the inlet rate sum of all of the port be less than or equal to committed rate.The present invention also provides other embodiment of the speed control system for implementing above-outlined.
The following description and accompanying drawing have elaborated some exemplary embodiments of the present invention.These embodiment only represent to use the several of variety of way of the present invention.
Brief description of the drawings
In order more completely to understand the disclosure and advantage thereof, now by reference to the accompanying drawings by reference to the following description, parts like similar Reference numeral representation class in the accompanying drawings:
Fig. 1 shows according to aggregate-rate service model of the present invention;
Fig. 2 shows the behavior according to rate control algorithm of the present invention;
Fig. 3 shows the operation according to rate control algorithm of the present invention;
Fig. 4 shows according to the present invention the bandwidth using in " ideal " situation, in " ideal " situation, port provide speed in the same manner (in lock step) change and all communication delay all identical;
Fig. 5 shows the bandwidth using according under truth of the present invention, and under truth, the speed that provides of port is asynchronous, and all communication latencies between two-port are independent of the time of delay between other port; And
Fig. 6 shows according to service provider's the capacity that the invention provides capacity allowance.
Embodiment
Provide following discussion, to have enabled those skilled in the art to and to have used the present invention.Can not depart under the prerequisite of the spirit and scope of the present invention defined herein, universal principle as herein described is being applied to embodiment and the application embodiment and the application except below describing in detail.The present invention is not intended to be limited to illustrated embodiment, but will be interpreted as meeting herein the wide region of the principle that discloses and feature.
In the following description of the present invention, use following term:
Regulate: when the inlet rate sum recording is enough high, while making the lasting rising of speed may cause exhausting the capacity relevant to aggregation group, the method for the permission rate-allocation of use.
Aggregation group: share the port set of committed rate.
Entrance: the direction from service-user to service provider.
Port: the interface of the business of user's access service provider network.Example is 802.1adProvider Edge Bridge (PEB) port or Metropolitan Ethernet Forum (MEF) User-Network Interface (UNI).
Greedy port: in the time that a) current inlet rate sum is greater than the value of being allowed to; And b) be while reducing the permission speed with the port (or multiple port) of high current inlet rate for reducing the countermeasure of speed, the port that inlet rate is lowered.
Non-greedy port: not greedy port.
Local port: some describe in for censuring the term of aggregation group port set particular port.For example, local port can be said into " rate value receiving is stored in the array R of local port maintenance ".
Service provider's network (SPN): for example, for client provides the network of connection business, IEEE 802.1adProvider Bridged Network (PBN) or MEF Metropolitan Ethernet (MEN).
Oblique ascension: a kind of method that allows speed of distributing, by allow rate-allocation be greater than the value of survey inlet rate currency.
Speed message: be distributed to periodically the message of other all of the port relevant with aggregation group from the port relevant to aggregation group, carrying (and may through smoothing or filtering) inlet rate value of being measured by this port.
Srvice instance: the example of the connection business being provided by service provider's network.Only between the port relevant with same service instance, allow to connect.Example is IEEE 802.1ad Service VirtualLocal Area network (SVLAN) or MEF Ethernet Virtual Connection (EVC).Below introduce symbol used in the present invention.In order to represent conveniently, the representative of symbol ∑
unless otherwise specified.I (i, t) is illustrated in the I value that period t end is relevant to port i.
Other identifier is as follows:
A
i(permission speed): the maximum rate that allows to enter from user's flow service provider's network at the port i place of aggregation group.I
ialways≤A
i.O
i> A
irepresent I
i=A
i.
B: in the time carrying out the oblique ascension that allows speed, for the A of next period
ivalue should exceed I
ithe minimum of currency.
C (rated capacity): on the link within service provider's network that service provider promises to undertake for the capacity of aggregation group.Capacity promises to undertake that C guarantees to cash at any time the business promise of appointment.Service provider can promise to undertake the bandwidth less than C, and bears the risk of sometimes not fulfilling one's commitments.
D
ij(delay): with the time durations that measure second, measure its inlet rate I at nearest period port i
itime, in the time that calculating S, quotes port j analog value R
iin time, finishes.
D (delay): the d of all of the port to (i, j) in aggregation group
ijmaximum.
F (speed sum is provided): all of the port i provides speed (O
i) value sum.
G (committed rate): in the time that inlet rate reaches stable state, make ∑ I
ithe setting of>=G.It is the promise rate of polymerization of aggregation group.
I
i(inlet rate): flow reality (measurement) speed of being introduced by the port i of aggregation group.This speed can be through low-pass filtering or through smoothing, to realize stability.
M
low(low allowance): for providing allowance or buffering area to follow the value of rate limit to guarantee S>=G.
M
high(high allowance): for providing allowance or buffering area to promise to undertake the value of the capacity requirement that exceedes calculating to guarantee service provider's capacity.
O
i(speed providing): the flow rate that is offered service provider at the port i place of aggregation group by user.
N (port number): the port number relevant to aggregation group.
Q: in aggregation group, Ri exceedes the port number of the maximum permission speed X of calculating.
R
i: the I that local port receives recently in the speed message from port i
ivalue.R
localbe assigned with I
localcurrency.
S: the R of all of the port i in aggregation group
isum.
S
max: the maximum that S obtains.
T: the number count of the period that the duration in past is T.
T: the port i broadcast I of aggregation group
ithe fixing period of value.On this event horizon, also carry out and allow recalculating of speed.
X: the A that can distribute to arbitrary port i in aggregation group after rate adaptation
imaximum.
With reference now to Fig. 1,, show the example of aggregate-rate service model (100).Service provider's network (110) provides aggregate-rate communication services to client (120).Client (120) and 7 ports, port (131)-(137) are relevant, with access service provider network (110).Committed rate G of these 7 ports share, forms aggregation group.Can use the inlet rate of each port within rate control algorithm control aggregation group, to guarantee that the aggregate-rate services that service provider's network (110) provides meets service-level agreement (SLA).Service provider's network (110) can have arbitrary topology.Port in aggregation group is shared the capacity of aggregation group liberally.
Recruitment B and the period length T of the rate of polymerization that aggregate-rate services can allow by committed rate G, during each period T characterize.SLA can specify aggregate-rate service model to guarantee:
1) total inlet rate ∑ I
ibe more than or equal to G; Or
2) have and be more than or equal to current inlet rate I
ispeed O is provided
iany port during next period T, its inlet rate can be increased to the amount that be at least B.
In one embodiment, each port is measured I during current period t
i.In the time that the period, t finished, port i, for example port (131) dispense rate message, this message contains (and may through smoothing and/or filtering) the inlet rate value I recording
iand the mark of port i.Can utilize the mode dispense rate message of broadcast, multicast or clean culture.
The port being associated with the aggregation group that comprises n port receives the speed message of each initiation of other port in aggregation group.Time delay between port i transmission rate message and another port j receipt message mostly is D second most.The port j of for example port (137) safeguards the array R of n element, and it comprises the rate value receiving from other n-1 port recently.For example the port of port j (137) is not to himself transmission rate message.On the contrary, the element j that port j (137) locates array R is included in the up-to-date inlet rate that port j measures.When censuring particular port, for example, when port j (137), this port can be called to local port at this.It is the permission speed of oneself determining next period that local port can utilize the inlet rate recording at local port and the rate information receiving from other port of aggregation group.Can use respectively A
localand I
localrepresent permission speed and the inlet rate of local port.
By receiving the speed message of all other port distributions in aggregation group, each port can obtain the inlet rate information of all other ports, and uses the permission speed of its next period of method of rate control control.On the end of each period t the each port i in aggregation group, calculate the inlet rate sum receiving recently, be shown below:
S＝∑R
i。
After S is calculated at the end of period t, calculate A
local.Therefore, in aggregation group, each port receives entrance rate information via speed message from all other ports within aggregation group, then calculates and allows speed.Can use one of two kinds of computational methods according to the relative value of S and G.
If (S < G), carries out oblique ascension; Otherwise, if (S >=G) regulates.
In one embodiment, in the time of oblique ascension, can divide two stages to calculate the A of next period t
localvalue.First stage is:
A
local＝I
local+B。
That is, can by during period t with speed I
ithe port i sending is restricted to A during period t+1
i=I
i+ B.Can in service-level agreement, define B.In the situation that not postponing, this ramping method is guaranteed (∑ I during period t+1
i< G+nB) because in period t ∑ I
i< G, the each of n port can increase its inlet rate to be no more than B.
Second stage is:
If(S+nB＜G){
A
local＝A
local+(G-(S+nB))/(nD)；
}
(S+nB) maximum that can reach for S in next period.If this value is less than G, can further make so A
localincrease (G-(S+nB))/(nD), this does not have next and postpones the risk that flow during D exceedes C.
In the present invention, the alternative embodiment of oblique ascension has saved the oblique ascension of second stage.In this case, with the fixing amount B of the each period t permission speed of each port that raises, and do not consider may be available overhead provision.This technology is called as " linearity " oblique ascension, to differentiate with " acceleration " oblique ascension, the latter comprise the first and second stage oblique ascensions both.Linear oblique ascension is than accelerating oblique ascension more slowly near maximum rate.But business is confirmed to be simplified, because the expection speed increase during oblique ascension is constant.
For adjusting, an embodiment calculates the maximum that allows speed X, makes
G=∑ R
i(for R
i< X)+∑ X is (for R
i>=X).
Expression formula " ∑ X (for R above
i>=X) " there is identical meanings with " Q*X ", wherein Q has I in aggregation group
ithe port number of>=X attribute.
If determined the value of X, so
A
local＝MIN(I
local，X)+B。
An embodiment who is used for the method for calculating X sorts to Rn to the element R1 of array R according to descending (R1 maximum), and wherein array R is by the R of all n port within aggregation group
iform.Then from greatest member to least member, pass through one by one array R.In each step, all elements (being the element in array with less index value) that rate value is greater than to currentElement replaces with the value of currentElement.In the time that all elements sum in array R is less than or equal to rate of polymerization G, end this stepping process.In the time that this thing happens, " greediness " port that index allows speed to be lowered lower than the element representative of current index.
Can utilize the embodiment of the above-mentioned algorithm of Implementation of pseudocode of following form:
Press the R1 of descending array R to Rn;
i＝1；
while(i*Ri+∑Rj(for j＝(i+1)to n)＞G){
i++；
}
Array element 1 is to speed representative " greediness " port of (i-1).Greedy port is shared equably rate of polymerization G and is deducted array element i to remaining bandwidth after the speed of n, and X is calculated as:
X=(G-∑ R
j(j=i to n))/(i-1).
The second embodiment of the method for calculating X presses the element R1 of descending (R1 maximum) arrangement array R to Rn; And all values of R is sued for peace.In the time receiving speed message, can carry out progressively above-mentioned two operations (sequence and summation).Then pass through one by one array R from maximum element (i=1) to minimum value element (i=n).In each step, with the value (R of currentElement
i) logically replace all elements (without physically upgrading these array elements) that index is less than i.Element 1 is calculated as (i-1) * R to (i-1) sum
i.By making the current sumAtOrAboveI R that successively decreases
iin each step, element i is safeguarded as sumAtOrAboveI to n sum.As ((i-1) * R
i+ sumAtOrAboveI) value end stepping process while being less than or equal to committed rate G.In the time that this thing happens, " greediness " port that index allows speed to be lowered lower than the element representative of current index.
Can utilize the embodiment of this algorithm of Implementation of pseudocode of following form:
Press the R1 of descending array R to Rn;
Value sum in sum=array R;
i＝1；
//sumAtOrAboveI represents that index is more than or equal to the array element value sum of current index i.
sumAtOrAboveI＝sum；
while(((i-1)*Ri+sumAtOrAboveI)＞G){
i++；
sumAtOrAboveI＝sumAtOrAboveI-Ri；
}
Array element 1 is to speed representative " greediness " port of (i-1).Greedy port is shared equably committed rate G and is deducted array element i to remaining bandwidth after the speed of n, and X is calculated as:
X＝(G-sumAtOrAboveI)/(i-1)。
The 3rd embodiment that calculates the method for X is impartial part by the probable value spatial division of X, and judges that the desired value of X is positioned at part or lower part.In selected part, recursively carry out this program, until the speed sum of utilizing the currency of X to obtain is substantially equal to G.This algorithm moves in the mode that is similar to binary search.
The false code of implementing this algorithm can be as follows:
interval＝G/2；
X＝G/2；
temp＝∑R
i(for R
i＜X)+∑X(for R
i≥X)；
while(temp！≈G){
interval＝interval/2；
if(temp＞G){
X＝X-interval；
}else {
X＝X+interval；
}
temp＝∑R
i(for R
i＜X)+∑X(for R
i≥X)；
}
// determine to represent the not index of the first array element of greedy port.
while(R
j＞X){
j++；
}
// determine the quantity of greedy port:
Q＝j-1；
Greedy ports share rate of polymerization deducts the remaining bandwidth of non-greedy port speed, and X is calculated as:
X＝(G-∑R
i(for R
i＜X))/Q。
The 4th embodiment by following false code exemplified with the method for calculating X.The present embodiment does not need array value to sort.
//Q is the quantity of " greediness " port
Q＝1；
temp＝∑R
i；
The current speed sum of // non-greedy port
temp＝temp-max(R
i)；
j＝index(max(R
i))；
// by 0 maximum replacing in array
R
i＝0；
//X was once the second largest rate value in array, was maximum now
X＝max(R
i)；
// in the time that providing than the higher speed of non-greedy port, exits greedy port circulation:
loop until((G-temp)/Q＞X)
{
The surplus value of maximum in // array
j＝index(max(R
i))；
// replace maximum residual value with 0
R
j＝0；
The present rate sum of // non-greedy port
temp＝temp-X；
the number of“greedy”ports
Q++；
//X was once the Second Largest Value in array, was now maximum
X＝max(R
i)；
}
// distribute to the speed of greedy port
X＝(G-temp)/Q；
Above-mentioned rate control algorithm comprises the criterion of assessment X value:
G=∑ R
i(for R
i< X)+∑ X is (for R
i>=X);
Or
G ≈ ∑ R
i(for R
i< X)+∑ X is (for R
i>=X);
This rate control algorithm comprises above-mentioned specific algorithm and embodies the modification of these algorithms of algorithm substantial principle.
For the behavior exemplified with rate control algorithm in Fig. 2 of following situation: client has the aggregation group of ten ports, the maximum path distance between port is 1000km, and committed rate is 1Gbps.Every 10ms carries out first time rate broadcast and allows rate calculations.Allow the every 10ms of the inlet rate interval of each port to increase 10Mbps.Meeting the required total capacity of rate guarantee is 1.3Gbps.If guarantee 1Gbps speed at each port simultaneously, at least need the promise of 5Gbps, can be by this compared with this situation.In Fig. 2, curve (210) shows from the inlet flow rate of the first file of first end port transmission, and curve (220) shows from the inlet flow rate of the second file of the second port transmission.Inlet flow rate actual and being illustrated by curve (230).The inlet flow rate sum of curve (240) for learning from the speed message postponing.
Analog result shown in Fig. 3 shows the operation of the rate control algorithm under simple scenario, and aggregation group comprises ten member ports in this case.In this example, port 2, curve (310) starts Transmit message, after spending some times, port 9, curve (320) starts Transmit message, and after some times, port 2 completes the transmission of file.Curve (330) shows the inlet flow rate sum of port 2 and 9.The maximum of curve (330) expresses support for the required capacity C of committed rate G.When only having single port in the time sending, curve (330) is consistent with the speed of single transmit port.In the time once having two ports to send, due to the delay that port experiences when from other port receiving velocity information, entrance discharge curve (330) sum exceedes committed rate.
Figure 4 and 5 illustrate, port working provides conservative situation or the worst case of D value result in the hypothesis of " walking in step with each other " state (activity that is them is synchronized with each other).Loosen this hypothesis and port activity is considered as asynchronous, only can reduce the value of D.Fig. 4 shows " ideal " situation, wherein at each port in the variation that speed mutually occurs to allow in the same time, and all communication delays between port are all identical.There are four ports that are called as A (410), B (420), C (430) and D (440).Only show speed message from A (410) to other port, it comprises speed message (460), (470) and (480).Parameter is as follows: G=12, B=2, n=4, nB=8, D=2, (n-1) BD=12, G+nB+ (n-1) BD=32.Fig. 4 shows each port and has maximum inlet rate 8 and inlet rate and 32.
But in fact, as shown in Figure 5, port is asynchronous, and port between all communication delays be different.In Fig. 5, also have four ports that are called as A (510), B (520), C (530) and D (540).Only show speed message from A to other port, comprise speed message (560), (570) and (580).Fig. 5 shows three ports to be had 8, one ports of inlet rate and has inlet rate 6.In this case, reduced required capacity C.This is than the worst case scenario shown in Fig. 4 good (, needing still less capacity).
Can use rate control algorithm and SLA to determine the worst case capacity of supporting that in the system that aggregate-rate services is provided committed rate is required.
In the situation that not postponing, use one of above-mentioned rate control algorithm to guarantee the permission rate value in each next period of port assignment, make ∑ A
i≤ S+nB, wherein S is the ∑ R relevant to the current period
ivalue.Can not allow the value of S to increase to the value that exceedes G.Therefore,, in the situation that not postponing (being D=0), on the link on the data path of all communications in network between group membership, required capacity (being the cutpoint in network graph) is no more than G+nB.
In the situation that there is delay (D > 0), the speed message of n-1 port is delayed.The speed message that local port (place of computation rate) is located is not delayed, because do not send physical message.For each remote port, the inlet rate B that can raise in each period T.Postponing there is the period that D/T duration is T during D.D can be calculated as to the half of two round-trip delaies between port.Postponing during D the speed of the remote port BD/T that can raise.Therefore, the value of S (based on received speed) by ∑ Ii value underestimated (n-1) BD/T.Can know capacity required on this link by inference is G+nB+ (n-1) BD/T.
Importantly will point out, this capacity is all to pass through for all flows the worst-case computation of being examined link.If delivery flow rate on different paths, according to the understanding of the traffic distribution to through different paths, the capacity requirement that can reduce to calculate above.
May worry that the rate of polymerization that cannot provide agreement to promise to undertake may be provided transient network situation (variation of the ports physical position of for example not reflecting in D value).
With reference now to Fig. 6,, C indicates to postpone the total capacity demand in the situation of D, and (n-1) BD/T indicates the capacity of concrete needs in the situation of delay.It is the capacity requirement of 1 o'clock that Smax represents to postpone, and nB is that the inlet rate allowing during the current period increases.G represents committed rate.Cause exceeding because of desired volume fluctuation the possibility of capacity in order to reduce the transient changing of service provider's network, the capacity M that service provider can transfer extra
lowand/or M
high, to provide buffering area between the nominal committed rate of specifying and the promise of the actual enforcement of service provider in client agreement.If M
low> 0, can revise rate control algorithm, makes all examples of G become (G+M
low).Capacity requirement can be changed into (G+M
low)+nB+ (n-1) BD/T+M
high.
Can apply method of rate control of the present invention to be totally independent of the mode of aggregate-rate service model or any specific committed rate.Port can for example, be recognized preferably the polymerization amount that reduces (or increase) Web portal flow by some unspecific means (congestion notification).G value in rate control algorithm can be arranged to than current inlet rate sum or the value of the G value lower (or higher) using in the past.Effect is to reduce liberally (or increase) inlet rate, makes the port that (for example) sends with low rate can be because congested generation rate reduces, because this port can not be responsible for congested.
Provide the aforementioned description of the disclosed embodiments, to have enabled those skilled in the art to or to have used the present invention.Do not departing under the prerequisite of the spirit or scope of the present invention, those skilled in the art will be easy to expect the various amendments to these embodiment, and General Principle defined herein can be applied to other embodiment.Therefore, the present invention is not intended to be limited to illustrated embodiment, but will be interpreted as meeting herein the wide region of the principle that discloses and novel feature.
Claims (56)
1. a method of the group of the port of n in communication network being carried out to speed control, comprises the steps:
If the inlet rate sum s of a described n port is less than given rate-valve value G, each the permission speed in a described n port is carried out to oblique ascension; Described oblique ascension is specifically included as the value that described permission rate-allocation is greater than surveyed inlet rate currency; And
If the inlet rate sum s of a described n port is more than or equal to described given rate-valve value G, regulate a described n port in each permission speed, make permission speed described of a described n port and equal described given rate-valve value G;
Wherein, the group of a described n port forms aggregation group, described oblique ascension step comprises: for the local port in described aggregation group, the described inlet rate and amount B sum of the described permission speed of local port described in next period being arranged to equal to the described local port of measuring during the current period, wherein B is to be the speed recruitment of each period t of T the duration.
2. method of rate control according to claim 1, also comprises the inlet rate information of each port of the group that obtains n port.
3. method of rate control according to claim 1, also comprises the distribution operation of each port executive communication message of the group of a described n port, the inlet rate information that described communication information comprises the port of carrying out described distribution operation.
4. method of rate control according to claim 1, wherein said given rate-valve value is the shared committed rate of group by a described n port.
5. method of rate control according to claim 4, described n port in wherein said aggregation group shared described committed rate liberally.
6. method of rate control according to claim 1, wherein said communication network has arbitrary topology.
7. method of rate control according to claim 1, also comprises: each port of described aggregation group contains the speed message of the inlet rate information of described dispatch ports to other port distributing packets in described aggregation group.
8. method of rate control according to claim 7, wherein said speed message comprises the mark of entrance rate value and described dispatch ports.
9. method of rate control according to claim 7, wherein said speed message is by broadcast distribution.
10. method of rate control according to claim 7, wherein said speed message is by multicast distribution.
11. method of rate control according to claim 7, wherein said speed message is distributed by clean culture.
12. method of rate control according to claim 7, wherein said speed message was distributed in the given period.
13. method of rate control according to claim 1, wherein carry out described oblique ascension or regulating step by each port of described aggregation group.
14. method of rate control according to claim 1, wherein carry out described oblique ascension or regulating step in the given period.
15. method of rate control according to claim 1, wherein definition B in service-level agreement (SLA).
16. method of rate control according to claim 1, also comprise the steps: if the described permission speed of described local port is increased (G-(S+nB)/nD), the delay maximum between any two ports that wherein D is described aggregation group by (s+nB < G).
17. method of rate control according to claim 16 are wherein the half of the round-trip delay between described two ports by the described Delay computing between any two ports of described aggregation group.
18. method of rate control according to claim 1, wherein for the local port in described aggregation group, described regulating step also comprises the steps:
Determine the maximum speed X that allows, make X meet G and equal R
i∑ R under < X condition
iadd R
i∑ X under>=X condition, or approximate R
i∑ R under < X condition
iadd R
i∑ X under>=X condition, wherein R
ifor described aggregation group middle port i (i=1 ... n) inlet rate, R
ito obtain in the speed message of being distributed by port i; And
For the described permission rate-allocation value (MIN (I of described local port
local, X) and+B), wherein B is to be the speed recruitment of each period of T the duration, I
localfor the described inlet rate of local port described in the described current period.
19. method of rate control according to claim 18 wherein define B in service-level agreement.
20. method of rate control according to claim 18, the step of wherein said definite X also comprises:
Determine greedy port, wherein, described greedy port comprises in the time that a) current inlet rate sum is greater than the value of being allowed to; And b) be while reducing the permission speed with the most one or more ports of high current inlet rate for reducing the countermeasure of speed, the port that inlet rate is lowered; And
Calculate X, making X is the described permission speed that is assigned to each greedy port, and the permission speed of non-greedy port is constant, and in described aggregation group, the permission speed sum of all of the port equals G.
21. method of rate control according to claim 20, wherein determine described greedy port by the algorithm comprising the steps:
Use the inlet rate R being distributed by the port i in described aggregation group
i(i=1 ... n) form array R;
With descending, array R is sorted;
From greatest member to least member, pass through one by one array R;
The all elements that inlet rate value is greater than to currentElement replaces with the described inlet rate value of described currentElement;
Repeat the first two step, until all elements sum in array R is less than or equal to described given rate-valve value G; And
Described greedy port is defined as to the port that index is less than the described currentElement index in array R.
22. method of rate control according to claim 20, wherein utilize the algorithm comprising the steps to determine described greedy port:
Use the inlet rate R being distributed by the port i in described aggregation group
i(i=1 ... n) form array R;
With descending, array R is sorted;
From greatest member to least member, pass through one by one array R;
Index in array R is greater than to all elements summation of the described index of currentElement, obtains sumAtOrAboveI;
Repeat the first two step, until (sumAtOrAboveI+k* currentElement) is less than or equal to described given rate-valve value G, wherein k is the quantity that index is less than or equal to the element of the described index of described currentElement; And
Described greedy port is defined as to the port that index is less than or equal to the described index of described currentElement.
23. method of rate control according to claim 20, wherein determine greedy port by the algorithm comprising the steps:
Be two moieties by the probable value spatial division of X;
Which part is the desired value of determining X be arranged in;
Repeat the first two step, until R
i∑ R under < X condition
iadd R
itill ∑ X under>=X condition is substantially equal to described given rate-valve value G; And
Described greedy port is defined as to the port that inlet rate is more than or equal to X.
24. method of rate control according to claim 20, wherein utilize the algorithm comprising the steps to determine described greedy port:
Determine the maximum of the described inlet rate of the port in described aggregation group;
For X distributes described maximum;
The described inlet rate with peaked port is replaced with to 0;
Storage inlet rate equals 0 port number and is expressed as Q;
Repeat first three step, until ((all inlet rate sums of G-)/Q) is less than or equal to X; And
Described greedy port is defined as to the port that inlet rate equals 0.
25. methods according to claim 24, wherein calculate X according to (all non-greedy inlet rate sums of G-)/Q.
26. method of rate control according to claim 1, wherein in the situation that not postponing, the worst case capacity of supporting the signal post between the port of described aggregation group to need is (G+nB), and wherein B is to be the amount that the speed of each period t of T increases the duration.
27. method of rate control according to claim 1, wherein in the situation that there is delay D, the worst case capacity of supporting the signal post between the port of described aggregation group to need is ((G+nB)+(n-1) BD/T), and wherein B is the amount that duration each period t medium-rate that is T increases.
28. method of rate control according to claim 1, wherein provide extra capacity M
lowor M
high.
29. method of rate control according to claim 28, wherein change described given rate-valve value G into (G+M
low).
30. method of rate control according to claim 28, wherein postpone D in the situation that existing, and the worst case capacity of supporting the signal post between the port of described aggregation group to need is ((G+M
low+ nB)+(n-1) BD/T+M
high), wherein B is to be the amount of each period t medium-rate increase of T the duration.
31. 1 kinds of systems for the speed control of aggregate-rate communication services, comprising:
At least one aggregation group, it comprises the port of n shared committed rate G;
Each port in wherein said aggregation group obtains the inlet rate information of all other ports in described aggregation group; Described aggregation group comprises:
If the inlet rate sum S of all of the port is less than described committed rate G in described aggregation group,, to allowing speed to carry out the module of oblique ascension, described oblique ascension is specifically included as the value that described permission rate-allocation is greater than surveyed inlet rate currency; And
If the inlet rate sum S of all of the port is more than or equal to described committed rate G in described aggregation group, regulate and allow speed, make the permission speed sum of next period of all of the port in described aggregation group equal the module of G;
Each port in wherein said aggregation group carrys out oblique ascension by B that its current inlet rate is accelerated and allows speed, make the permission speed sum of all of the port in described aggregation group equal described committed rate G, wherein B is to be the amount of each period t medium-rate increase of T the duration.
32. systems according to claim 31, the port of wherein said aggregation group is shared the described committed rate of described aggregation group liberally.
33. systems according to claim 31, also comprise the provider network with arbitrary topology.
34. systems according to claim 31, the each port in wherein said aggregation group is also carried out the distribution operation of speed message, the inlet rate information that described speed message comprises the port of carrying out described distribution operation.
35. systems according to claim 34, each port of wherein said aggregation group is by speed message described in broadcast distribution.
36. systems according to claim 34, each port of wherein said aggregation group is by speed message described in multicast distribution.
37. systems according to claim 34, each port of wherein said aggregation group is distributed described speed message by clean culture.
38. systems according to claim 34, wherein said speed message comprises the mark of entrance rate value and described dispatch ports.
39. systems according to claim 34, wherein said speed message was distributed in the given period.
40. systems according to claim 31 wherein define B in service-level agreement.
41. systems according to claim 31, wherein (if S+nB < G), each port in described aggregation group further increases described permission speed the amount of (G-(S+nB)/nD), the maximum postponing between any two ports that wherein D is described aggregation group.
42. according to the system described in claim 41, is wherein the half of the round-trip delay between described two ports by the Delay computing between any two ports of described aggregation group.
43. systems according to claim 31, the each port in wherein said aggregation group is at given period oblique ascension or regulate permission speed.
44. systems according to claim 31, wherein, for the local port in described aggregation group, the method that the each port utilization in described aggregation group comprises the steps regulates and allows speed:
Determine the maximum speed X that allows, make X meet G and equal R
i∑ R under < X condition
iadd R
i∑ X under>=X condition, or approximate R
i∑ R under < X condition
iadd R
i∑ X under>=X condition, wherein R
ifor the described aggregation group middle port i that obtains in the speed message of port i distribution (i=1 ... n) inlet rate; And
For the permission rate-allocation value MIN (I of described local port
local, X) and+B, wherein B is to be the amount of each period t medium-rate increase of T the duration, I
localfor the inlet rate of current period local port.
45. according to the system described in claim 44, wherein in service-level agreement, defines B.
46. according to the system described in claim 44, wherein determines that the described step of X also comprises:
Determine greedy port; Wherein, described greedy port comprises in the time that a) current inlet rate sum is greater than the value of being allowed to; And b) be while reducing the permission speed with the most one or more ports of high current inlet rate for reducing the countermeasure of speed, the port that inlet rate is lowered; And
Calculate X, making X is the permission speed that is assigned to each greedy port, and the permission speed of non-greedy port is constant, and in described aggregation group, the permission speed sum of all of the port equals G.
47. according to the system described in claim 46, wherein determines greedy port by the algorithm comprising the steps:
Use the inlet rate R being distributed by the port i in described aggregation group
i(i=1 ... n) form array R;
With descending, array R is sorted;
From greatest member to least member, pass through one by one array R;
The all elements that inlet rate value is greater than to currentElement replaces with the inlet rate value of described currentElement;
Repeat the first two step, until all elements sum in array R is less than or equal to committed rate G; And
Described greedy port is defined as to the port that index is less than the index of the described currentElement in array R.
48. according to the system described in claim 46, wherein determines greedy port by the algorithm comprising the steps:
Use the inlet rate R being distributed by the port i in described aggregation group
i(i=1 ... n) form array R;
With descending, array R is sorted;
From greatest member to least member, pass through one by one array R;
Index in array R is greater than to all elements summation of the index of currentElement, obtains sumAtOrAboveI;
Repeat the first two step, until (sumAtOrAboveI+k* currentElement) is less than or equal to described committed rate G, wherein k is the element speed of the index index that is less than or equal to described currentElement; And
Described greedy port is defined as to the port that index is less than or equal to the index of described currentElement.
49. according to the system described in claim 46, wherein determines greedy port by the algorithm comprising the steps:
Be two moieties by the probable value spatial division of X;
Which part is the desired value of determining X be arranged in;
Repeat the first two step, until R
i∑ R under < X condition
iadd R
itill ∑ X under>=X condition is substantially equal to described committed rate G; And
Described greedy port is defined as to the port that inlet rate is more than or equal to X.
50. according to the system described in claim 46, wherein determines described greedy port by the algorithm comprising the steps:
Determine the maximum of the described inlet rate of the port in described aggregation group;
For X distributes maximum;
The inlet rate with peaked port is replaced with to 0;
Storage inlet rate equals the quantity of 0 port, and it is represented by Q;
Repeat first three step, until ((all inlet rate sums of G-)/Q) is less than or equal to X; And
Described greedy port is defined as to the port that inlet rate equals 0.
51. systems according to claim 31, wherein in the situation that not postponing, the worst case capacity of supporting the signal post between the port of described aggregation group to need is (G+nB), and wherein B is to be the amount that the speed of each period t of T increases the duration.
52. systems according to claim 31, wherein in the situation that there is delay D, the worst case capacity of supporting the signal post between the port of described aggregation group to need is (G+nB+ (n-1) BD/T), and wherein B is to be the amount that each period t medium-rate of T increases the duration.
53. systems according to claim 31, wherein provide extra capacity M
lowor M
high.
54. according to the system described in claim 53, wherein changes described committed rate G into (G+M
low).
55. according to the system described in claim 53, wherein postpones D in the situation that existing, and the worst case capacity of supporting the signal post between the port of described aggregation group to need is ((G+M
low+ nB)+(n-1) BD/T+M
high), wherein B is to be the amount of each period t medium-rate increase of T the duration.
56. 1 kinds of methods for the speed control of the aggregation group of communication network, wherein said aggregation group comprises the port of n Fairshare committed rate G, described method comprises the following steps for each local port:
Obtain the inlet rate information of all other ports in described aggregation group;
If the inlet rate sum S of all of the port is less than described committed rate G in described aggregation group, by the permission speed of next period is arranged to (I
local+ B) carry out the controlled increase of the permission speed of described local port; And
If the inlet rate sum S of described aggregation group is more than or equal to described committed rate G, regulate the permission speed of described local port, make described permission speed equal (MIN (I
local, X) and+B), wherein X meets G and equals R
i∑ R under < X condition
iadd R
i∑ X under>=X condition, or approximate R
i∑ R under < X condition
iadd R
i∑ X under>=X condition;
Wherein B is to be the amount of each period t medium-rate increase of T the duration; R
ifor the described aggregation group middle port i that obtains in the speed message of port i distribution (i=1 ... n) inlet rate; And I
localfor the inlet rate of local port described in the current period;
Wherein said communication network has arbitrary topology.
Applications Claiming Priority (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US82020206P | 2006-07-24 | 2006-07-24 | |
| US60/820,202 | 2006-07-24 | ||
| US11/622,646 US7817550B2 (en) | 2006-01-13 | 2007-01-12 | System for rate-control of aggregate-rate communication services |
| US11/622,646 | 2007-01-12 | ||
| PCT/CN2007/070350 WO2008014712A1 (en) | 2006-07-24 | 2007-07-24 | System for rate-control of aggregate-rate communication services |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101485104A CN101485104A (en) | 2009-07-15 |
| CN101485104B true CN101485104B (en) | 2014-11-05 |
Family
ID=40572843
Family Applications (3)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN200780025604.XA Active CN101485104B (en) | 2006-07-24 | 2007-07-24 | System for rate-control of aggregate-rate communication services |
| CNA2007800105162A Pending CN101411132A (en) | 2006-07-24 | 2007-07-24 | System for rate management of aggregate-rate communication services |
| CN200780028193XA Active CN101496349B (en) | 2006-07-24 | 2007-07-24 | System for providing aggregate-rate communication services |
Family Applications After (2)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CNA2007800105162A Pending CN101411132A (en) | 2006-07-24 | 2007-07-24 | System for rate management of aggregate-rate communication services |
| CN200780028193XA Active CN101496349B (en) | 2006-07-24 | 2007-07-24 | System for providing aggregate-rate communication services |
Country Status (2)
| Country | Link |
|---|---|
| CN (3) | CN101485104B (en) |
| ES (1) | ES2352524T3 (en) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102594671B (en) * | 2012-02-08 | 2018-03-20 | 中兴通讯股份有限公司 | A kind of method and apparatus that speed limit is carried out to user |
| CN105939283B (en) * | 2016-03-17 | 2019-03-15 | 杭州迪普科技股份有限公司 | The method and device of network flow quantity shunting |
| CN106878116B (en) * | 2016-12-06 | 2019-12-06 | 新华三技术有限公司 | flow rate limiting method and device |
| CN114793209B (en) * | 2021-01-07 | 2024-05-24 | 大唐移动通信设备有限公司 | Data transmission method and device and SDN device |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0878938A2 (en) * | 1997-05-16 | 1998-11-18 | Nec Corporation | System for conducting rate control of ATM traffic |
| CN1274218A (en) * | 1999-05-12 | 2000-11-22 | 日本电气株式会社 | Asynchronous transmitting mode switching device with jam control function |
| CN1422042A (en) * | 2001-11-30 | 2003-06-04 | 深圳市中兴通讯股份有限公司上海第二研究所 | Communication network bandwidth controlling method |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6665733B1 (en) * | 1996-12-30 | 2003-12-16 | Hewlett-Packard Development Company, L.P. | Network communication device including bonded ports for increased bandwidth |
| US7102997B2 (en) * | 2002-03-04 | 2006-09-05 | Fujitsu Limited | Aggregate rate transparent LAN service for closed user groups over optical rings |
| CN1319326C (en) * | 2003-04-01 | 2007-05-30 | 华为技术有限公司 | Band width statistical multiplex method based on acknowledged cut in speed |
| US7391769B2 (en) * | 2003-06-27 | 2008-06-24 | Lucent Technologies Inc. | Packet aggregation for real time services on packet data networks |
| CN1333605C (en) * | 2003-08-22 | 2007-08-22 | 华为技术有限公司 | Method for controlling service transmitting speed ratio of 3G mobile communication system |
-
2007
- 2007-07-24 CN CN200780025604.XA patent/CN101485104B/en active Active
- 2007-07-24 CN CNA2007800105162A patent/CN101411132A/en active Pending
- 2007-07-24 ES ES07764273T patent/ES2352524T3/en active Active
- 2007-07-24 CN CN200780028193XA patent/CN101496349B/en active Active
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0878938A2 (en) * | 1997-05-16 | 1998-11-18 | Nec Corporation | System for conducting rate control of ATM traffic |
| CN1274218A (en) * | 1999-05-12 | 2000-11-22 | 日本电气株式会社 | Asynchronous transmitting mode switching device with jam control function |
| CN1422042A (en) * | 2001-11-30 | 2003-06-04 | 深圳市中兴通讯股份有限公司上海第二研究所 | Communication network bandwidth controlling method |
Also Published As
| Publication number | Publication date |
|---|---|
| ES2352524T3 (en) | 2011-02-21 |
| CN101485104A (en) | 2009-07-15 |
| CN101496349A (en) | 2009-07-29 |
| CN101411132A (en) | 2009-04-15 |
| CN101496349B (en) | 2013-09-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP1958344B1 (en) | System for rate-control of aggregate-rate communication services | |
| Kelly et al. | Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling | |
| CN100562006C (en) | The system and method for difference queuing in the route system | |
| US6385168B1 (en) | Fair share bandwidth allocation algorithm and device | |
| Figueira et al. | Leave-in-time: A new service discipline for real-time communications in a packet-switching network | |
| US5285442A (en) | Traffic supervisory method and traffic supervisory apparatus | |
| CN101485104B (en) | System for rate-control of aggregate-rate communication services | |
| US6754177B1 (en) | Method and system for burst congestion control in an ATM network | |
| EP1932298B1 (en) | System for rate management of aggregate-rate communication services | |
| Potter et al. | Analysis of a discrete multipriority queueing system involving a central shared processor serving many local queues | |
| Nahrstedt et al. | Coexistence of QoS and best-effort flows | |
| US20030117955A1 (en) | Flow propagation analysis using iterative signaling | |
| Turhan et al. | Optimal admission control in two-class preemptive loss systems | |
| US7333436B2 (en) | Network device with traffic shaping functions and bandwidth control method using leaky bucket algorithm | |
| LeBlanc et al. | Topology design and bridge-capacity assignment for interconnecting token ring LANs: A simulated annealing approach | |
| Nordström et al. | CAC and routing for multi‐service networks with blocked wide‐band calls delayed, part I: exact link MDP framework | |
| Towsley et al. | Congestion avoidance in high-speed interconnection systems | |
| US6377545B1 (en) | Open loop adaptive access control of ATM networks using a neural network | |
| Kelly et al. | Heavy traffic on a controlled motorway | |
| Al-Wakeel Sami et al. | Evaluation of fairness strategies for ATM congestion control policing mechanisms | |
| Chang et al. | Hierarchical QoS routing in ATM networks based on MDP cost function | |
| Balakrishnan et al. | Rate guarantees and overload protection in input-queued switches | |
| Li | Analysis on conformance deterioration for QoS provisioning: A stochastic approach | |
| Tayan | A proposed model for optimizing the flow of pilgrims between Holy sites during Hajj using traffic congestion control | |
| Sahoo et al. | Research Article Optimization of Data Distributed Network System under Uncertainty |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant |