Congestion avoidance in high-speed network carrying bursty traffic

• US 5,029,164 A
• Filed: 04/13/1990
• Issued: 07/02/1991
• Est. Priority Date: 04/13/1990
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Callon, Ross, Goldstein, Fred R.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): KIZOU, HASSAN
• Application Number:
  US07/509,605
• Time in Patent Office: 445 Days
• Field of Search: 370/94.1, 370/85.7, 370/95.1, 370/118, 370/79
• US Class Current: 370/235
• CPC Class Codes: H04J 3/1629 Format building algorithm
• CPC Class Codes: H04J 3/247 ATM or packet multiplexing
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5632 Bandwidth allocation
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/724 at intermediate nodes, e.g. resource reservation protocol [RSVP]
• CPC Class Codes: H04L 47/748 Negotiation of resources, e.g. modification of a request
• CPC Class Codes: H04L 47/826 Involving periods of time
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A data communication network subject to bursty traffic employs a bandwidth allocation scheme to avoid congestion. When a source node has a burst of traffic to send, it first sends a bandwidth request message through the network from source to destination. At each intermediate node, this bandwidth request is examined and the node determines how much of the requested traffic level it will be able to support at a time in the future of one round-trip interval hence, and this node either grants the request or marks down the request to a level that it can support, then passes it on. When the request reaches the destination, it is returned along the same path to the source, and the source then employs the marked-down allocation to select the rate used to send the burst of data. The allocation for this source node remains in effect for a limited time, depending upon the amount of data to be sent in the burst, then returns to a "residual" level.

Claims

1. A method of congestion avoidance in a communications network having multiple nodes, comprising the steps of:

(a) sending from a first of said nodes to a first intermediate one of said nodes a request for an allocation of bandwidth for a transmission of a quantity of data from said first node to a second one of said nodes via said first intermediate node and a second intermediate node;

(b) comparing said request in said first intermediate node with capacity at said first intermediate node to meet said request, and generating a modified request to reduce said allocation if necessary;

(c) sending said modified request from said first intermediate node to said second intermediate node;

(d) comparing said modified request in said second intermediate node with capacity at said second intermediate node to meet said modified request, and generating a second modified request to reduce said allocation if necessary;

(e) sending said second modified request back to said first node;

(f) transmitting said quantity of data from said first node to said second node using the bandwidth specified in said second modified request.

2. A method according to claim 1 wherein said step of comparing said request in said first intermediate node includes, comparing with capacity projected at a time about that required for one round trip between said first node and said second node.

3. A method according to claim 1 wherein said first node is allocated a standard bandwidth value and only sends said request if the bandwidth needed to transmit said quantity of data exceeds said standard bandwidth value.

4. A method according to claim 1 wherein data is transmitted from said first intermediate node to said second intermediate node by an asynchronous transfer mode.

5. A method according to claim 1 wherein said steps of sending are by a serial data link.

6. A communications network having multiple nodes, comprising:

(a) a transmitter sending from a first of said nodes to a first intermediate one of said nodes a request for an allocation of bandwidth for a data transmission from said first node to a second one of said nodes via said first intermediate node and a second intermediate node;

(b) means for comparing said request in said first intermediate node with capacity at said first intermediate node to meet said request, and for generating a modified request to reduce said allocation if necessary, said modified request being sent from said first intermediate node to said second intermediate node;

(c) means for comparing said modified request in said second intermediate node with capacity at said second intermediate node to meed said modified request, and for generating a second modified request to reduce said allocation if necessary, said second modified request being sent back to said first node;

(d) said transmitter sending data from said first node to said second node using the bandwidth specified in said second modified request.

7. A network according to claim 6 wherein said means for comparing said request in said first intermediate node includes means for comparing with capacity projected at a time about that required for one round trip between said first node and said second node.

8. A network according to claim 6 wherein said first node is allocated a standard bandwidth value and only sends said request if the bandwidth needed for said data transmission exceeds said standard bandwidth value.

9. A network according to claim 6 including a transceiver in said first intermediate node which transmits data from said first intermediate node to said second intermediate node by an asynchronous transfer mode.

10. A network according to claim 6 wherein said transmitter sends data by a serial data link.

11. A method of transmitting a quantity of digital information from a first node in a network to a destination, comprising the steps of:

(a) transmitting from said first node a control cell containing a request for a bandwidth allocation needed for said quantity of information, a bandwidth quote equal to said bandwidth allocation, and a duration for the requested bandwidth;

(b) receiving said control cell at an intermediate node in said network and marking down said bandwidth quote in said control cell at said intermediate node in response to the capacity of said intermediate node at a time when said quantity of information is to be transmitted, then transmitting said control cell toward said destination;

(c) subsequently receiving at said first node a return of said control cell in which said bandwidth quote is modified downward in accordance with capacity of other nodes in said network;

(d) transmitting from said first node to said destination said quantity of information at a bandwidth corresponding to said modified bandwidth quote.

12. A method according to claim 11 wherein said duration is expressed in quantity of digital information.

13. A method according to claim 11 wherein said node is granted a selected allocation of bandwidth, and said control cell is transmitted only if said request exceeds said selected allocation of bandwidth.

14. A method according to claim 11 wherein said information is transmitted from said intermediate node in said network to another node by an asynchronous transfer mode.

15. A method according to claim 11 wherein said step of transmitting is by a serial data link.

16. Apparatus for transmitting a quantity of digital information from a first node in a network to a destination, comprising:

(a) means for transmitting from said first node a control cell containing (1) a request for a bandwidth allocation needed for said quantity of information, (2) a bandwidth quote equal to said bandwidth allocation, and (3) a duration for the requested bandwidth;

(b) means for receiving said control cell at an intermediate node in said network and modifying downward said bandwidth quote in said control cell in response to the capacity of said intermediate node at a time when said quantity of information is to be transmitted;

(c) means for transmitting said control cell including said modified downward bandwidth quote from said intermediate node toward said destination;

(d) means in said first node for subsequently receiving at said node a return of said control cell in which said bandwidth quote is modified downward in accordance with capacity of other nodes in said network;

(c) and means in said first node for transmitting from said first node to said destination said quantity of information at a bandwidth corresponding to said modified downward bandwidth quote.

17. Apparatus according to claim 16 wherein duration is expressed in quantity of digital information.

18. Apparatus according to claim 16 wherein said first node is granted a selected allocation of bandwidth, and said control cell is transmitted from said first node only if said request exceeds said selected allocation of bandwidth.

19. Apparatus according to claim 16 wherein said means in said node for transmitting uses an asynchronous transfer mode.