Concestion control system and method for packet switched networks providing max-min fairness

Claim 2

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein said determining, said operating and said changing steps are applied for a data flow from a given source contemporaneous with a receipt of said indicators for each said data flow.

Claim 3

The congestion control method of claim 1 wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for said competing data flows.

Claim 4

The congestion control method of claim 1 wherein said allocation criterion of said determining step is max-rain fairness.

Claim 5

The congestion control method of claim 1 wherein said data flow from said source is simultaneously transmitted to multiple destinations, said allocation is determined for each said data flow transmitted to each of said multiple destinations, and said maximum data transmission rate for said source is determined as a minimum of said maximum rate allocations among all of said data flows transmitted to said multiple destinations.

Claim 6

The congestion control method of claim 1 wherein said application of said determining, operating and changing steps is carried out for each said data flow from each said given source with an execution time that is independent of the number of said competing data flows.

Claim 7

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein said determining step, said operating step and said changing step are carried out by an algorithm characterized in that its execution is independent of a number of competing data flows at a transmission link within said network.

Claim 8

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein said determining step, said operating step and said changing step are carried out by an algorithm characterized in that its execution is independent of a number of competing data flows at a transmission link within said network.

Claim 9

The congestion control method of claim 6 wherein said algorithm is further characterized as storing parameter values for said competing data flows.

Claim 10

The congestion control method of claim 6 wherein said algorithm is further characterized as being of algorithmic order Θ(1).

Claim 11

The congestion control method of claim 6 wherein execution of said algorithm carries out the following steps: extracting a value of said first and said second indicators and an identification of said source for members of said competing data flows; causing a state of a member of said competing data flows with a largest bandwidth request to be identified as bottlenecked; determining if a current value of said second indicator causes a state change for said data flow from said source; updating a state of said current data flow from said source; computing a new bandwidth allocation for said current data flow from said source and recording said allocation in a storage means; revising said value of said second indicator where a requested value exceeds said allocation; and causing said first and said second indicators to be transmitted to a successive switch in said transmission path.

Claim 12

The congestion control method of claim 6 wherein said algorithm is of the form __________________________________________________________________________ 1 i ←cell (VC) /* get the VC number */ 2 r.sub.i.sup.a ←cell (CCR) /* get the current cell rate */ 3 ρ.sub.i.sup.a ←cell (ER) /* get the amount of requested bandwidth */ 4 if (M.sup.a < r.sub.i.sup.a) then /* if the maximum registered requested bandwidth is less than connection i's allocation */ 5 M.sup.a ←r.sub.i.sup.a /* set the maximum requested bandwidth to connection i's CCR */ 6 m.sup.a ←i /* register connection i as the one with the maximum request */ 7 if state.sub.i.sup.a =satisfied then /* if connection i is marked as satisfied */ 8 state.sub.i.sup.a ←bottlenecked /* initially mark it as bottlenecked */ 9 N.sub.b.sup.a ←N.sub.b.sup.a + 1 /* increase the number of bottlenecked connections by one */ 10 end if 11 else if (M.sup.a >r.sub.i.sup.a) then /* if the registered maximum request is larger than i's CCR */ 12 if (m.sup.a = i) /* if it was i that had the maximum request */ 13 M.sup.a ←r.sub.i.sup.a /* update the maximum request */ 14 end if 15 end if 16 R.sup.a ←R.sup.a + ρ.sub.i.sup.a - l.sub.i.sup.a /* Update the estimate of the total requested bandwidth */ 17 l.sub.i.sup.a ←ρ.sub.i.sup.a /* Update the recorded value for i's requests */ 18 if (R.sup.a > B.sup.a) then /* if the total requested bandwidth is larger than the bandwidth available to data traffic */ 19 if state.sub.i.sup.a = satisfied then /* if connection i is marked as satisfied */ 20 temp ←N.sub.b.sup.a + 1 /* increase the number of bottlenecked connections by one and treat i as bottlenecked*/ 21 else 22 temp ←N.sub.b.sup.a /* else the number of bottlenecked connections is not affected */ 23 end if 24 ##STR1## /* compute a new maximum fair allocation for connection i */ 25 if A.sub.max.sup.a < B.sub.eq.sup.a then /* if the newly computed allocation is less than the equal share */ 26 A.sub.max.sup.a ←B.sub.eq /* set the allocation at least equal to the new fair share */ 27 end if 28 if (ρ.sub.i.sup.a ≦A.sub.max.sup.a) then /* if connection i requests less bandwidth than what is allocated above */ 29 A.sub.max.sup.a ←ρ.sub.i.sup.a /* connection i gets what it requested */ 30 if (m.sup.a ≠ i) then /* if this is not the connection with the maximum request */ 31 if state.sub.i.sup.a = bottlenecked then /* if connection i is not marked as satisfied */ 32 state.sub.i.sup.a ←satisfied /* mark connection i as satisfied */ 33 N.sub.b.sup.a ←N.sub.b.sup.a - 1 /* decrease number of bottlenecked connections by one */ 34 end if 35 end if 36 else /* else if connection i asks for more bandwidth than what can be allocated to it */ 37 if state.sub.i.sup.a =satisfied then /* if connection i is marked as satisfied */ \\ 38 state.sub.i.sup.a ←bottlenecked /* unmark connection i */ 39 N.sub.b.sup.a ←N.sub.b.sup.a + 1 /* increase number of bottlenecked connections by one */ 40 end if 41 end if 42 else /* if the total requested bandwidth is less than the bandwidth available for data traffic */ ifstate.sub.i.sup.a =bottlenecked then /* if connection i is bottlenecked */ 44 state.sub.i.sup.a ←satisfied /* mark connection i as satisfied */ 45 N.sub.b.sup.a ←N.sub.b.sup.a - 1 /* decrease the number of bottlenecked connection by one */ 46 A.sub.max.sup.a ←ρ.sub.i.sup.a /* allocate to connection i what it requests */ 47 end if 48 end if 49 if (A.sub.max.sup.a >r.sub.i.sup.a)and(r.sub.i.sup.a >0) then /* if the allocated bandwidth is larger than the current rate and the current rate is non-zero */ 50 if (m.sup.a ≠ i) then /* if i is not the connection with the maximum request */ 51 if state.sub.i.sup.a =bottlenecked then /* if i is marked as bottlenecked */ 52 state.sub.i.sup.a ←satisfied /* mark connection i as satisfied since i is bottlenecked at another link */ 53 N.sub.b.sup.a ←N.sub.b.sup.a - 1 /* decrease the number of bottlenecked connections by one */ 54 end if 55 end if 56 end if 57 if state.sub.i.sup.a =bottlenecked then /* if connection i is marked as bottlenecked after all */ 58 r.sub.i.sup.a ←B.sub.eq.sup.a /* record connection i as getting only the equal share */ 59 end if 60 B.sub.f.sup.a ←B.sub.f.sup.a + A.sub.i.sup.a - r.sub.i.sup.a /* update the estimate of the bandwidth that can be allocated to the bottlenecked connections */ 61 A.sub.i.sup.a ←r.sub.i.sup.a /* record the allocated bandwidth as the minimum from current rate and computed allocation */ 62 cell (ER) ←A.sub.max.sup.a /* set the explicit rate field of the current resource management cell */ 63 forward (cell ) /* forward this cell to the next switch __________________________________________________________________________ */.

Claim 13

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein said determining, said operating and said changing means are applied to a data flow from a given source contemporaneous with a receipt of said indicators for each said data flow.

Claim 14

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein said determining, said operating and said changing means are applied to a data flow from a given source contemporaneous with a receipt of said indicators for each said data flow.

Claim 15

The congestion control system of claim 11 wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for said competing data flows.

Claim 16

The congestion control system of claim 11 wherein said allocation criterion of said determining means is max-min fairness.

Claim 17

The congestion control system of claim 11 wherein said data flow from said source is simultaneously transmitted to multiple destinations, said allocation is determined for each said data flow transmitted to each of said multiple destinations, and further including means for establishing a maximum data transmission rate for said source as a minimum of said maximum rate allocations among all of said data flows transmitted to said multiple destinations.

Claim 18

The congestion control system of claim 11 wherein said application of said determining, operating and changing means is carried out for each said data flow from each said given source with an execution time that is independent of the number of said competing data flows.

Claim 19

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein said determining means, said operating means and said changing means are implemented in a rate allocation algorithm processor carrying out an algorithm characterized in that its execution is independent of a number of competing data flows at a transmission link within said network.

Claim 20

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein said determining means, said operating means and said changing means are implemented in a rate allocation algorithm processor carrying out an algorithm characterized in that its execution is independent of a number of competing data flows at a transmission link within said network.

Claim 21

The congestion control system of claim 16 wherein said algorithm carried out by said rate allocation algorithm processor is further characterized as storing parameter values for said competing data flows.

Claim 22

The congestion control system of claim 16 wherein said algorithm carried ont by said rate allocation algorithm processor is further characterized as being of algorithmic order Θ(1).

Claim 23

The congestion control system of claim 16 wherein execution of said algorithm carries out the following steps: extracting a value of said first and said second indicators and an identification of said source for members of said competing data flows; causing a state of a member of said competing data flows with a largest bandwidth request to be identified as bottlenecked; determining if a current value of said second indicator causes a state change for said data flow from said source; updating a state of said current data flow from said source; computing a new bandwidth allocation for said current data flow from said source and recording said allocation in a storage means; revising said value of said second indicator where a requested value exceeds said allocation; and causing said first and said second indicators to be transmitted to a successive switch in said transmission path.

Claim 24

The congestion control system of claim 16 wherein said algorithm is of the form __________________________________________________________________________ 1 i ←cell (VC) /* get the VC number */ 2 r.sub.i.sup.a ←cell (CCR) /* get the current cell rate */ 3 ρ.sub.i.sup.a ←cell (ER) /* get the amount of requested bandwidth */ 4 if (M.sup.a < r.sub.i.sup.a) then /* if the maximum registered requested bandwidth is less than connection i's allocation */ 5 M.sup.a ←r.sub.i.sup.a /* set the maximum requested bandwidth to connection i's CCR */ 6 m.sup.a ←i /* register connection i as the one with the maximum request */ 7 if state.sub.i.sup.a =satisfied then /* if connection i is marked as satisfied */ 8 state.sub.i.sup.a ←bottlenecked /* initially mark it as bottlenecked */ 9 N.sub.b.sup.a ←N.sub.b.sup.a + 1 /* increase the number of bottlenecked connections by one */ 10 end if 11 else if (M.sup.a >r.sub.i.sup.a) then /* if the registered maximum request is larger than i's CCR */ 12 if (m.sup.a = i) /* if it was i that had the maximum request */ 13 M.sup.a ←r.sub.i.sup.a /* update the maximum request */ 14 end if 15 end if 16 R.sup.a ←R.sup.a + ρ.sub.i.sup.a - l.sub.i.sup.a /* Update the estimate of the total requested bandwidth */ 17 l.sub.i.sup.a ←ρ.sub.i.sup.a /* Update the recorded value for i's requests */ 18 if (R.sup.a > B.sup.a) then /* if the total requested bandwidth is larger than the bandwidth available to data traffic */ 19 if state.sub.i.sup.a = satisfied then /* if connection i is marked as satisfied */ 20 temp ←N.sub.b.sup.a + 1 /* increase the number of bottlenecked connections by one and treat i as bottlenecked*/ 21 else 22 temp ←N.sub.b.sup.a /* else the number of bottlenecked connections is not affected */ 23 end if 24 ##STR2## /* compute a new maximum fair allocation for connection i */ 25 if A.sub.max.sup.a < B.sub.eq.sup.a then /* if the newly computed allocation is less than the equal share */ 26 A.sub.max.sup.a ←B.sub.eq /* set the allocation at least equal to the new fair share */ 27 end if 28 if (ρ.sub.i.sup.a ≦A.sub.max.sup.a) then /* if connection i requests less bandwidth than what is allocated above */ 29 A.sub.max.sup.a ←ρ.sub.i.sup.a /* connection i gets what it requested */ 30 if (m.sup.a ≠ i) then /* if this is not the connection with the maximum request */ 31 if state.sub.i.sup.a = bottlenecked then /* if connection i is not marked as satisfied */ 32 state.sub.i.sup.a ←satisfied /* mark connection i as satisfied */ 33 N.sub.b.sup.a ←N.sub.b.sup.a - 1 /* decrease number of bottlenecked connections by one */ 34 end if 35 end if 36 else /* else if connection i asks for more bandwidth than what can be allocated to it */ 37 if state.sub.i.sup.a =satisfied then /* if connection i is marked as satisfied */ \\ 38 state.sub.i.sup.a ←bottlenecked /* unmark connection i */ 39 N.sub.b.sup.a ←N.sub.b.sup.a + 1 /* increase number of bottlenecked connections by one */ 40 end if 41 end if 42 else /* if the total requested bandwidth is less than the bandwidth available for data traffic */ ifstate.sub.i.sup.a =bottlenecked then /* if connection i is bottlenecked */ 44 state.sub.i.sup.a ←satisfied /* mark connection i as satisfied */ 45 N.sub.b.sup.a ←N.sub.b.sup.a - 1 /* decrease the number of bottlenecked connection by one */ 46 A.sub.max.sup.a ←ρ.sub.i.sup.a /* allocate to connection i what it requests */ 47 end if 48 end if 49 if (A.sub.max.sup.a >r.sub.i.sup.a)and(r.sub.i.sup.a >0) then /* if the allocated bandwidth is larger than the current rate and the current rate is non-zero */ 50 if (m.sup.a ≠ i) then /* if i is not the connection with the maximum request */ 51 if state.sub.i.sup.a =bottlenecked then /* if i is marked as bottlenecked */ 52 state.sub.i.sup.a ←satisfied /* mark connection i as satisfied since i is bottlenecked at another link */ 53 N.sub.b.sup.a ←N.sub.b.sup.a - 1 /* decrease the number of bottlenecked connections by one */ 54 end if 55 end if 56 end if 57 if state.sub.i.sup.a =bottlenecked then /* if connection i is marked as bottlenecked after all */ 58 r.sub.i.sup.a ←B.sub.eq.sup.a /* record connection i as getting only the equal share */ 59 end if 60 B.sub.f.sup.a ←B.sub.f.sup.a + A.sub.i.sup.a - r.sub.i.sup.a /* update the estimate of the bandwidth that can be allocated to the bottlenecked connections */ 61 A.sub.i.sup.a ←r.sub.i.sup.a /* record the allocated bandwidth as the minimum from current rate and computed allocation */ 62 cell (ER) ←A.sub.max.sup.a /* set the explicit rate field of the current resource management cell */ 63 forward (cell ) /* forward this cell to the next switch __________________________________________________________________________ */.

Claim 25

In a method of congestion control in a communications network, said network including a first plurality of switches and a second plurality of transmission links interconnecting said switches, each said link being characterized by a maximum data transmission rate which can be handled by said link, and wherein a data source is caused to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data, the improvement comprising: an algorithm operative to determine, at each switch in said network traversed by said data flow, an allocation of a data transmission rate for said data flow and to modify said second indicator when said rate represented thereby exceeds said allocated data transmission rate, wherein said algorithm operates on a state of said data flow, as being unconstrained or bottlenecked, and rate parameters for said data flow, said maximum data transmission rate for a link including said data flow and a numerical value of a number of competing data flows sharing said link including said data flow, said operation of said algorithm being thereby independent of any state or rate parameters for said competing data flows.

Claim 26

In a method of congestion control in a communications network, said network including a first plurality of switches and a second plurality of transmission links interconnecting said switches, each said link being characterized by a maximum data transmission rate which can be handled by said link, and wherein a data source is caused to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data, the improvement comprising: an algorithm operative to determine, at each switch in said network traversed by said data flow, an allocation of a data transmission rate for said data flow and to modify said second indicator when said rate represented thereby exceeds said allocated data transmission rate, wherein said algorithm operates on a state of said data flow, as being unconstrained or bottlenecked, and rate parameters for said data flow, said maximum data transmission rate for a link including said data flow and a numerical value of a number of competing data flows sharing said link including said data flow, said operation of said algorithm being thereby independent of any state or rate parameters for said competing data flows.

Claim 27

The congestion control algorithm of claim 21 wherein said algorithm is characterized as being of algorithmic order Θ(1).

Claim 28

The congestion control algorithm of claim 21 wherein said algorithm operates on each receipt of said first and second indicators for a given data flow.

Claim 29

The congestion control algorithm of claim 21 wherein said algorithm performs a constant number of computational steps on receipt of said first and second indicators for a given data flow, independent of the number of competing data flows sharing a transmission link with said given data flow.

Claim 30

The congestion control algorithm of claim 21 wherein said algorithm maintains a record of a rate allocation parameter for each competing data flow included in a transmission link, but operates only on a rate allocation parameter represented by said second indicator for a data flow under consideration.

Claim 31

The congestion control algorithm of claim 21 wherein a rate allocation made for a data flow under consideration is set at the lesser of said rate represented by said first indicator and a maximum rate allocation computed for said data flow under consideration according to a predetermined criterion.

Claim 32

The congestion control algorithm of claim 21 wherein a change in a rate allocation of a data flow under consideration at a given switch occurs only upon receipt at said given switch of a one of said first or said second indicators for said data flow under consideration.

Claim 33

The congestion control algorithm of claim 21 wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for competing data flows sharing a link with said data flow under consideration.

Claim 34

The congestion control algorithm of claim 21 wherein said algorithm causes an initial rate allocation to be established in a switch for a given data flow at start-up of said given data flow.

Claim 35

The congestion control algorithm of claim 29 wherein said start-up of said given data flow occurs when a set up request for said given data flow arrives at said switch in a transmission path for said given data flow.

Claim 36

The congestion control algorithm of claim 21 wherein execution of said algorithm carries out the following steps at a switch where said algorithm is operating: extracting a value of said first and said second indicators for, and an identification of a data flow under consideration; causing a state of a member of said competing data flows with a largest bandwidth request to be identified as bottlenecked; determining if a value of said second indicator causes a state change for said data flow under consideration at said switch; updating a state of said data flow under consideration; computing a new rate allocation for said data flow under consideration and recording said allocation in a storage means; revising said value of said second indicator where a requested value exceeds said allocation; and causing said first and said second indicators to be transmitted to a successive switch in said transmission path.

Claim 37

The congestion control algorithm of claim 21 wherein said algorithm is of the form: __________________________________________________________________________ 1 i ← cell (VC) /* get the VC number */ 2 ER.sub.i ←cell(ER);CCR.sub.i ←cell(CCR) /* read ER and CCR fields of RM cell */ 3 ρ.sub.i ←min(ER.sub.i,CCR.sub.i) /* ρ.sub.i is the request of connection i */ /* Compute maximum local allocation A.sub.max. /* 4 B.sub.eq ←B/N /* compute equal share */ 5 if state.sub.i = bottlenecked then ##STR3## 7 else 8 ##STR4## /* Determine new state of connection */ 9 A.sub.max ← max(A.sub.max,B.sub.eq) 10 if (A.sub.max < ρ.sub.i) and (state.sub.i = satisfied) then 11 state.sub.i ← bottlenecked; N.sub.b ← N.sub.b + 1 12 if (A.sub.max > ρ.sub.i) and (state.sub.i = bottlenecked) then 13 state.sub.i ← satisfied; N.sub.b ← N.sub.b - 1 /* Compute the local allocation A.sub.i */ 14 if (state.sub.i = satisfied) then A.sub.i ← ρ.sub.i 15 else A.sub.i ← A.sub.max /* Update ER field of RM cell */ 16 cell(ER) ← min(A.sub.max,ER.sub.i) /* Maintain state of connection with the largest allocation as bottlenecked */ 17 if (A.sub.i > MaxAllocation) then /* mark this connection ("VC") as the one with the largest allocation */ 18 MaxVC ← i; MaxAllocation ← A.sub.i 19 if (state.sub.i = satisfied) then /* mark it as bottlenecked */ 20 state.sub.i ← bottlenecked; N.sub.b ← N.sub.b + 1 21 if(MaxVC =i)and(A.sub.i <MaxAllocation) 22 /* This is the VC with the largest allocation and its allocation went down */ 23 MaxAllocation ← A.sub.i /* update the largest allocation */ /* Update local allocation maintained in the switch */ 24 A.sub.old ←A.sub.i ' /* save old allocation */ 25 if (state.sub.i = satisfied) then A.sub.i ' ← A.sub.i 26 else A.sub.i ' ← B.sub.eq 27 /* Update free bandwidth B.sub.f */ 28 B.sub.f ←B.sub.f +A.sub.old -A.sub.i ' 29 forward(cell) /* forward RM cell to the next switch */. __________________________________________________________________________

Claim 38

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein said data flow from said source is simultaneously transmitted to multiple destinations, said allocation is determined for each said data flow transmitted to each of said multiple destinations, and said maximum data transmission rate for said source is determined as a minimum of said maximum rate allocations among all of said data flows transmitted to said multiple destinations.

Claim 39

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein said data flow from said source is simultaneously transmitted to multiple destinations, said allocation is determined for each said data flow transmitted to each of said multiple destinations, and said maximum data transmission rate for said source is determined as a minimum of said maximum rate allocations among all of said data flows transmitted to said multiple destinations.

Claim 40

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for said competing data flows.

Claim 41

A congestion control method for communications networks comprising the steps of: causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination, whereby any modification of said rate represented by said second indicator by any of said traversed switches operates to establish a maximum data transmission rate for said source; and wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for said competing data flows.

Claim 42

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein said data flow from said source is simultaneously transmitted to multiple destinations, said allocation is determined for each said data flow transmitted to each of said multiple destinations, and further including means for establishing a maximum data transmission rate for said source as a minimum of said maximum rate allocations among all of said data flows transmitted to said multiple destinations.

Claim 43

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for returning said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein said data flow from said source is simultaneously transmitted to multiple destinations, said allocation is determined for each said data flow transmitted to each of said multiple destinations, and further including means for establishing a maximum data transmission rate for said source as a minimum of said maximum rate allocations among all of said data flows transmitted to said multiple destinations.

Claim 44

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for remaining said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for said competing data flows.

Claim 45

A congestion control system for communications networks comprising: means for causing a data source to periodically inject into a data flow from said source a first indicator representative of a rate at which said source is currently transmitting data to said network and a second indicator representative of a rate at which said source is desirous of transmitting data; means for determining an allocation according to a predetermined criterion for bandwidth to be apportioned among competing data flows at switches within said network; means for operating on said second indicator at successive switches in a transmission path in said network between said source and a destination to compare said rate represented by said second indicator with a maximum rate allocation determined by said switch; means for changing said rate representation in said second indicator to said maximum rate allocation where said rate represented by said second indicator is greater than said maximum rate allocation; means for remaining said first and said second indicators to said source after said indicators have traversed all switches in said network transmission path between said source and said destination; and wherein a rate allocation made for a data flow under consideration at a given switch is independent of frequency of receipt at said switch of said first and second indicators for said competing data flows.

Claim 46

In a method of congestion control in a communications switch, said switch including at least one port having connected there at a plurality of communications paths carrying signals having non-zero bandwidth requirements, wherein said plurality of said signals compete for a total bandwidth available at said at least one port, and whereby a source for a given signal carried by a one of said plurality of communications paths is caused to periodically inject into said given signal a first indicator representative of a rate at which said source is currently transmitting information to said communications path and a second indicator representative of a rate at which said source is desirous of transmitting information, the improvement therein comprising a step of: determining an allocation of a transmission rate for said given signal and modifying said second indicator when said rate represented thereby exceeds said allocated transmission rate, wherein said determining step operates on a state of said given signal, as being unconstrained or bottlenecked, rate parameters for said given signal, said total bandwidth available at said at least one port, and a stored value of a transmission rate for each of said competing communications paths sharing said port, said operation of said determining step being thereby independent of any current state or rate parameters for said competing communications paths.

Claim 47

In a method of congestion control in a communications switch, said switch including at least one port having connected there at a plurality of communications paths carrying signals having non-zero bandwidth requirements, wherein said plurality of said signals compete for a total bandwidth available at said at least one port, and whereby a source for a given signal carried by a one of said plurality of communications paths is caused to periodically inject into said given signal a first indicator representative of a rate at which said source is currently transmitting information to said communications path and a second indicator representative of a rate at which said source is desirous of transmitting information, the improvement therein comprising a step of: determining an allocation of a transmission rate for said given signal and modifying said second indicator when said rate represented thereby exceeds said allocated transmission rate, wherein said determining step operates on a state of said given signal, as being unconstrained or bottlenecked, rate parameters for said given signal, said total bandwidth available at said at least one port, and a stored value of a transmission rate for each of said competing communications paths sharing said port, said operation of said determining step being thereby independent of any current state or rate parameters for said competing communications paths.

Claim 48

The congestion control method of claim 37 wherein said determining step performs a constant number of computational steps on receipt of said first and second indicators for said given signal, independent of the number of competing communications paths sharing said port.

Claim 49

The congestion control method of claim 37 wherein said determining step maintains a record of a rate allocation parameter for each competing communications paths sharing said port, but operates only on a rate allocation parameter represented by said second indicator for said given signal.

Claim 50

The congestion control method of claim 37 wherein a rate allocation made for said given signal is set at the lesser of said rate represented by said first indicator and a maximum rate allocation computed for said given signal according to a predetermined criterion.

Claim 51

The congestion control method of claim 37 wherein a rate allocation made for said given signal is independent of frequency of receipt at said port of said first and second indicators for competing communications paths sharing said port.

Claim 52

The congestion control method of claim 37 wherein execution of said determining step carries out the following steps: extracting a value of said first and said second indicators for, and an identification of said given signal; causing a state of a member of said competing communications paths sharing said port with a largest bandwidth request to be identified as bottlenecked; determining if a value of said second indicator causes a state change for said given signal at said switch; updating a state of said given signal; computing a new rate allocation for said given signal and recording said allocation in a storage means; and revising said value of said second indicator where a requested value exceeds said allocation.

Claim 53

A congestion control method for controlling bandwidth allocations among a plurality of competing communications paths connected at a port of a communications switch, said paths carrying signals having non-zero bandwidth requirements, wherein at least one source for a signal carried by a one of said plurality of communications paths is caused to periodically inject into said signal a first indicator representative of a rate at which said source is currently transmitting information to said communications path and a second indicator representative of a rate at which said source is desirous of transmitting information, said congestion control method carrying out the steps of: extracting a value of said first and said second indicators for, and an identification of a given signal; causing a state of a member of said competing communications paths sharing said port with a largest bandwidth request to be identified as bottlenecked; determining if a value of said second indicator causes a state change for said given signal at said switch; updating a state of said given signal; computing a new rate allocation for said given signal and recording said allocation in a storage means; and revising said value of said second indicator where a requested value exceeds said allocation.

Claim 54

A congestion control method for controlling bandwidth allocations among a plurality of competing communications paths connected at a port of a communications switch, said paths carrying signals having non-zero bandwidth requirements, wherein at least one source for a signal carried by a one of said plurality of communications paths is caused to periodically inject into said signal a first indicator representative of a rate at which said source is currently transmitting information to said communications path and a second indicator representative of a rate at which said source is desirous of transmitting information, said congestion control method carrying out the steps of: extracting a value of said first and said second indicators for, and an identification of a given signal; causing a state of a member of said competing communications paths sharing said port with a largest bandwidth request to be identified as bottlenecked; determining if a value of said second indicator causes a state change for said given signal at said switch; updating a state of said given signal; computing a new rate allocation for said given signal and recording said allocation in a storage means; and revising said value of said second indicator where a requested value exceeds said allocation.