Link-by-link congestion control for packet transmission systems

• US 5,319,638 A
• Filed: 09/12/1991
• Issued: 06/07/1994
• Est. Priority Date: 09/12/1991
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Lin, Huai-An
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Kizou, Hassan
• Application Number:
  US07/758,734
• Time in Patent Office: 999 Days
• Field of Search: 370/60, 370/60.1, 370/94.1, 370/94.2, 370/94.3, 370/84, 370/79, 370/17, 340/825.02
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control

Abstract

A packet transmission system includes a mechanism for controling congestion (30, FIG. 2) in the transmission system by comparing, at each switching node of the system (52, FIG. 5), the traffic load at that node and the traffic loads at all immediately neighboring switching nodes. Such traffic loads can be measured by node buffer utilization, either discretely or continuously, and loading information exchanged by the use of messages between the switching nodes (42, 54). The packet transmission speed between any two adjacent switching nodes is then adjusted (47, 62) in response to the relative traffic loads so as to reduce the traffic incoming to the more congested node. The transmission speed is never reduced to zero, however, to insure that a mechanism remains in place to relieve congestion at every transmitting switching node.

Claims

1. A packet transmission system comprising

a plurality of packet switching nodes interconnected by transmission links between pairs of switching nodes,

monitoring means at each of said nodes for monitoring the traffic intended for each other of said nodes, and

adjusting means at each of said nodes responsive to said monitoring means at two adjacent nodes for adjusting the transmission rate for packets transmitted between said two adjacent nodes.

2. The packet transmission system according to claim 1 further comprising

buffering means at each of said switching nodes for buffering data packets intended for transmission to each neighboring switching node connected by one of said transmission links,

said monitoring means comprising means for measuring the buffer utilization factor for said buffering means.

3. The packet transmission system according to claim 2 further comprising

means for reporting the crossing of any one of a plurality of preselected thresholds in occupancy of said means for buffering for one neighboring node to said one neighboring node.

4. A method for controling congestion in a packet transmission system comprising the steps of

interconnecting a plurality of packet switching nodes by transmission links between pairs of said switching nodes,

monitoring at each of said nodes the traffic intended for each other of said nodes, and

in response to the relative monitored traffic between two adjacent nodes, adjusting the transmission rate for packets transmitted between said two adjacent nodes.

5. The method according to claim 4 further comprising the step of

buffering, at each of said switching nodes, data packets intended for transmission to each neighboring switching node connected by one of said transmission links.

said step of monitoring comprising the step of measuring the buffer utilization factor during said buffering step.

6. The method according to claim 5 further comprising the step of

reporting every execution of said buffering step to at least one neighboring node.

7. The method according to claim 5 further comprising the step of

reporting the crossing of any one of a plurality of preselected thresholds in the number of data packets simultaneously buffered in said buffering step to at least one neighboring node.

9. The method according to claim 6 further comprising the step of

utilizing a transmission rate from the node S to the adjacent node X given by ##EQU10## where BU_S is the buffer utilization of a node S,

BU_X is the buffer utilization of an adjacent node X,

f is a weighting function designed to gradually increase the transmission rate to full speed as BU_S and BU_X approach each other, and

fullspeed is the maximum transmission rate from node S to node X.

8. The method according to claim 12 further comprising the step of

measuring, at said each of said switching nodes, the traffic arriving from each respective neighboring node.

10. The method according to claim 8 further comprising the step of

utilizing a transmission rate Y_X (S,i) from the node X to the adjacent node S given by ##EQU11## where S is one of said switching nodes,

X is an immediate neighbor switching node to node S,

B_X (S,i) is the buffer utilization of node X reported to node

Y_X (S,i) is the rate of transmission from node X to node S, and

OUT_S (i) is the output rate from node S, where ##EQU12## where N_S is the set of all immediate neighbors of S,

X_n (S,i) is the number of data packets which S transmits to an immediate neighbor n during f_i,

f_i is a fixed period of time in a succession of periods of time having an index i,

D_S (i) is the number of data packets which terminate as S during f_i, i.e., D_S (i) is the number of packets which arrives at S as the final destination during f_i, and

r is a pre-defined reduction rate between zero and one.

11. The method according to claim 8 further comprising the step of

utilizing a transmission rate Y_X (S,i) from the node X to the adjacent node S given by ##EQU13## where S is one of said switching nodes,

X is an immediate neighbor switching node to node S,

B_X (S,i) is the buffer utilization of node X reported to node

Y_X (S,i) is the rate of transmission from node X to node S, and

OUT_S (i) is the output rate from node S, where ##EQU14## where N_S is the set of all immediate neighbors of S,

X_n (S,i) is the number of data packets which S transmits to an immediate neighbor n during f_i,

f_i is a fixed period of time in a succession of periods of time having an index i,

D_S (i) is the number of data packets which terminate as S during f_i, i.e., D_S (i) is the number of packets which arrives at S as the final destination during f_i,

Δ

is a pre-defined increment rate greater than zero, and

fs is the maximum available transmission rate from node X to node S.