Predictive congestion control of high-speed wide area networks

• US 5,276,677 A
• Filed: 06/26/1992
• Issued: 01/04/1994
• Est. Priority Date: 06/26/1992
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC USA (NEC Corporation)
• Inventors: Sengupta, Bhaskar, Ramamurthy, Gopalakrishnan
• Primary Examiner(s): Safourek, Benedict V.
• Application Number:
  US07/905,287
• Time in Patent Office: 557 Days
• Field of Search: 370/13, 370/58.2, 370/58.3, 370/60, 370/68.1, 370/84, 370/94.1
• US Class Current: 370/232
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

To control congestion in packet switching networks, control of the traffic sent by a given station to each of the downstream nodes to which it is directly connected is effected by control of the traffic that the upstream nodes to which it is directly connected are permitted to send to it. In this regard, a predictive model is used to predict the cross traffic, one round trip delay in advance that the given station can expect. The parameters for the predictive model are obtained by measurements in real time and by the use of moving averages. Using the predicted cross traffic, the amount of controlled traffic that the proximate downstream nodes can accommodate from the given node, and the correct state of the given node, the state of the given node one round trip delay into the future is predicted. This prediction is used to schedule the amount of traffic to be sent by each of its proximate upstream nodes.

Claims

1. A process for the control of traffic for reducing congestion on a transmission path that includes a plurality of nodes between an upstream source of the traffic and a downstream destination for the traffic comprising the steps at a given node of:

predicting, on the basis of recently measured cross traffic, the amounts of cross traffic that it will receive over each of the next three time frames;

estimating, on the basis of measured controlled traffic being received from each upstream node to which it is directly connected, the amounts of controlled traffic that will be available to it over the next two time frames;

based on (1) the said previously predicted amounts of cross traffic it will be receiving over the next three time frames, (2) said previously estimated amounts of controlled traffic that will be available to it from said upstream nodes over the next two time frames, (3) the estimated capacity to accept controlled traffic from it of the downstream nodes directly connected to it, and (4) the present state of its queue, predicting the amounts of traffic that will keep its queue at a desired level over the next three time frames;

based on the predictions of said last recited step, estimating the total amount of traffic it should accept from said upstream nodes two time frames later;

based on the estimates of the last step, the controlled traffic backlog at each of said upstream nodes and the available link capacity of each, scheduling the rate of controlled traffic it is willing to accept from each of said upstream nodes;

forwarding the information as to the scheduled rates to each of said upstream nodes;

receiving from each of the downstream nodes directly connected to it the information as to the scheduled rate of controlled traffic it can send to each of said downstream nodes; and

transmitting its cross traffic and controlled traffic to each of said downstream nodes in accordance with the information received from each of the said downstream nodes.

2. The process of claim 1 in which the prediction of the amount of cross traffic that the given node will receive over the next three time frames uses the average of the cross traffic over a window of several time frames.

3. The process of claim 2 in which the traffic is in the form of signal packets and the cross traffic is primarily voice and video traffic and the controlled traffic is primarily data traffic.

4. The process of claim 3 in which the time frame approximates the average time it takes the traffic to travel between adjacent nodes of the transmission path.

5. In a packet switching transmission system including a plurality of nodes that are separated an average propagation delay time and where traffic may be added or subtracted from the path, a process for hop-by-hop congestion control that comprises at each node the steps of

predicting the queue size at said node three propagation delay times in advance,

estimating the amount of traffic it can accept from its proximate upstream nodes two propagation delay times in advance based on such prediction,

based on these estimates and predictions, transmitting to its proximate upstream nodes the amount of traffic it can accept for controlling the rate at which each transmits traffic to it,

receiving from its proximate downstream nodes the traffic they are willing to accept from it, and

transmitting to its proximate downstream nodes the amount of traffic each can accept from it.

6. A packet switching transmission network that includes a plurality of nodes separated by an average delay time and interconnected to provide hop-by-hop transmission flow between sources and destinations characterized in that hop-by-hop control of the flow is provided at each node by control means comprising

means for predicting the queue size at said node three delay times in advance and for estimating the maximum amount of traffic it can accordingly accept from its proximate upstream nodes two delay times in advance,

means for transmitting these estimates of amount of traffic it can expect to each of its proximate upstream nodes,

means for receiving from its proximate downstream nodes similar information as to the amount of traffic that each will accept from it, and

means for scheduling and transmitting to each of its downstream nodes traffic in accordance with the information received of the amount of traffic each can accept.