Method and apparatus for simple IP-layer bandwidth allocation using ingress control of egress bandwidth

• US 6,628,609 B2
• Filed: 04/30/1998
• Issued: 09/30/2003
• Est. Priority Date: 04/30/1998
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Kung, Hsiang-Tsung, Chapman, Alan Stanley John
• Primary Examiner(s): TON, DANG T
• Assistant Examiner(s): Tran, Maikhanh
• Application Number:
  US09/069,845
• Publication Number:
  US 20030103450A1
• Time in Patent Office: 1,979 Days
• Field of Search: 370/229, 370/230, 370/231-232, 370/234, 370/235, 370/236.1, 370/236.2, 370/412, 370/413-416, 370/420
• US Class Current: 370/229
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/50 Queue scheduling

Abstract

The present invention relates to a switch for processing data units, such as IP data packets. The switch can be implemented as a router that includes a plurality of input ports, a plurality of output ports and a switch fabric capable of establishing logical pathways to interconnect a certain input port with a certain output port. A characterizing element of the router is its ability to control bandwidth usage on a basis of a logical pathway. This prevents congestion to occur in the switch fabric and also at the level of the output ports. For every active logical pathway the router sets-up a bandwidth control mechanism including at least one queue to hold data units received at an input port. The bandwidth control mechanism performs an accounting operation to determine the average bandwidth usage and if less than a threshold requests for releasing data units in the switch fabric are sent to the switch fabric controller. When the threshold is exceeded the bandwidth control mechanism stops sending requests for service to the switch fabric controller. The system also supports priorities. Instead of stopping the issuance of signals requesting release of data packets the priority level of the queue (reflected in a priority field in the signal requesting release of a data packet) changes from HI to LO. The switch fabric controller is designed to recognize priority requests and will accept LO priority requests only when there are no other HI priority requests pending. The present invention also provides a data transport device which includes a plurality of nodes interconnected by a physical link that establishes two ring-shaped paths on which data is transported on opposite directions. Each node is capable of sending a control message to the upstream node to advise the upstream node of the data carrying requirements of the node at which the message has originated. The upstream node can then throttle the introduction of data in the paths to preserve capacity that can be used by the downstream nodes.

Claims

1. A switch for processing data units, said switch including:

a plurality of input ports, each input port capable of receiving data units;

a plurality of output ports, each output port capable of releasing data units;

a switch fabric capable of selectively establishing a plurality of logical pathways between said input ports and said output ports, each logical pathway connecting a certain input port to a certain output port, whereby a data unit received at the certain input port can be transported to the certain output port on the logical pathway between said certain output port and said certain input port;

a plurality of bandwidth control mechanisms, each bandwidth control mechanism being associated with a different logical pathway established through said switch fabric, each bandwidth control mechanism operative to;

a) compute a bandwidth usage of the respective logical pathway; and

b) regulate the transport of data units over the respective logical pathway on a basis of the computed bandwidth usage.

2. A switch as defined in claim 1, wherein said switch is a router.

3. A switch as defined in claim 2, wherein said switch includes an independent bandwidth control mechanism for each logical pathway established through said switch fabric.

4. A switch as defined in claim 3, wherein each bandwidth control mechanism regulates bandwidth usage over a respective logical pathway independently from the regulation of bandwidth usage over a different logical pathway.

5. A switch as defined in claim 4, wherein each bandwidth control mechanism comprises a queue for storage of data units to be transported over the logical pathway associated with the bandwidth control mechanism.

6. A switch as defined in claim 5, wherein each bandwidth control mechanism includes a queue control unit for regulating a rate of data packets released from said queue over the logical pathway associated with the bandwidth control mechanism.

7. A switch as defined in claim 6, wherein said queue control unit is capable of performing an accounting operation to determine bandwidth usage as a result of releasing data packets from said queue.

8. A switch as defined in claim 7, wherein said queue control unit is capable of computing an average bandwidth usage value when performing an accounting operation.

9. A switch as defined in claim 8, wherein said queue control unit prevents release of data units from said queue when said average bandwidth usage value exceeds a certain threshold.

10. A switch as defined in claim 9, wherein said queue control unit alters a priority setting of said queue when said average bandwidth usage value exceeds a certain threshold.

11. A switch as defined in claim 1, wherein said data units are IP data packets.

12. A switch as defined in claim 6, wherein said switch fabric includes a switch fabric controller to regulate the transport of data units through respective logical pathways of said switch fabric.

13. A switch as defined in claim 12, wherein said queue control unit is capable of issuing a request for data release signal to said switch fabric controller to request authorization from said switch fabric controller to release a data packet from said queue to said switch fabric.

14. A switch as defined in claim 13, wherein said queue control unit is responsive to an authorization for data release signal from said switch fabric controller to release a data packet from said queue to said switch fabric.

15. A switch as defined in claim 14, wherein said request for data release signal includes priority information.

16. A switch as defined in claim 15, wherein said priority information establishes a right of preeminence to gain access to said switch fabric relative to other request for data release signals from queues associated to different logical pathways.

17. A switch as defined in claim 16, wherein said priority information is indicative of at least two priority levels.

18. A switch as defined in claim 17, wherein said queue control unit sets the priority level of said request for data release signal in dependence of bandwidth usage of said queue.

19. A switch as defined in claim 18, wherein said queue control unit is capable of performing an accounting operation to determine bandwidth usage as a result of releasing data packets from said queue.

20. A switch as defined in claim 19, wherein said queue control unit is capable of computing an average bandwidth usage value when performing an accounting operation.

21. A switch as defined in claim 20, wherein said queue control unit is capable of setting the priority level of said request for data release signal at either one of first and second levels, said first level being indicative of a higher priority than said second level, said queue control unit setting the priority level of said request for data release signal at said first level when said average bandwidth usage is less than a certain threshold.

22. A switch as defined in claim 21, wherein said queue control unit sets the priority level of said request for data release signal at said second level when said average bandwidth usage exceeds said certain threshold.

23. A method for managing the transport of data units in a switch, said switch comprising:

a plurality of input ports, each input port capable of receiving data units;

a plurality of output ports, each output port capable of releasing data units;

a switch fabric capable of selectively establishing a plurality of logical pathways between said input ports and said output ports, each logical pathway connecting a certain input port to a certain output port, whereby a data unit received at the certain input port can be transported to the certain output port on the logical pathway;

for a particular logical pathway, said method comprising the steps of;

a) computing a bandwidth usage of the particular logical pathway; and

b) regulating the transport of data units over the particular logical pathway on a basis of the bandwidth usage computed in step a.

24. A method as defined in claim 23, wherein said switch is a router.

25. A method as defined in claim 24, comprising the step of providing said switch with an independent bandwidth control mechanism for each logical pathway established through said switch fabric.

26. A method as defined in claim 25, wherein each bandwidth control mechanism comprises a queue for storage of data units to be transported over the logical pathway associated with the bandwidth control mechanism.

27. A method as defined in claim 26, wherein each bandwidth control mechanism includes a queue control unit for regulating a rate of data packets released from said queue over the logical pathway associated with the bandwidth control mechanism.

28. A method as defined in claim 27, wherein said queue control unit is capable of performing an accounting operation to determine bandwidth usage as a result of releasing data packets from said queue.

29. A method as defined in claim 28, wherein said queue control unit is capable of computing an average bandwidth usage value when performing an accounting operation.

30. A method as defined in claim 29, wherein said queue control unit stops releasing data units from said queue when said average bandwidth usage value exceeds a certain threshold.

31. A method as defined in claim 30, wherein said queue control unit reduces a rate of data units released from said queue when said average bandwidth usage value exceeds a certain threshold.

32. A method as defined in claim 23, wherein said data units are IP data packets.

33. A switch for processing data units, said switch including:

a plurality of input ports, each input port capable of receiving data units;

a plurality of output ports, each output port capable of releasing data units;

a switch fabric capable of selectively establishing a plurality of logical pathways between said input ports and said output ports, each logical pathway connecting a certain input port to a certain output port, whereby a data unit received at the certain input port can be transported to the certain output port on the logical pathway associated to said certain output port and to said certain input port;

means responsive to establishment of a logical pathway through said switch fabric to enable a bandwidth control mechanism to;

a) compute a bandwidth usage of the logical pathway; and

b) regulate the transport of data units over the logical pathway on a basis of the computed bandwidth usage.

34. A switch as defined in claim 33, wherein said switch is a router.

35. A switch as defined in claim 34, wherein said means responsive to establishment of a logical pathway through said switch fabric enables an independent bandwidth control mechanism for each logical pathway established through said switch fabric.

36. A switch as defined in claim 35, wherein each bandwidth control mechanism regulates bandwidth usage over a respective logical pathway independently from the regulation of bandwidth usage over a different logical pathway.

37. A switch as defined in claim 36, wherein each bandwidth control mechanism comprises a queue for storage of data units to be transported over the logical pathway associated with the bandwidth control mechanism.

38. A switch as defined in claim 37, wherein each bandwidth control mechanism includes a queue control unit for regulating a rate of data packets released from said queue over the logical pathway associated with the bandwidth control mechanism.

39. A switch as defined in claim 38, wherein said queue control unit is capable of performing an accounting operation to determine bandwidth usage as a result of releasing data packets from said queue.

40. A switch as defined in claim 39, wherein said queue control unit is capable of computing an average bandwidth usage value when performing an accounting operation.

41. A switch as defined in claim 40, wherein said queue control unit stops releasing data units from said queue when said average bandwidth usage value exceeds a certain threshold.

42. A switch as defined in claim 41, wherein said queue control unit reduces a rate of data units released from said queue when said average bandwidth usage value exceeds a certain threshold.

43. A switch as defined in claim 33, wherein said data units are IP data packets.

44. A method for managing the transport of data units in a switch, said switch comprising:

a plurality of input ports, each input port capable of receiving data units;

a plurality of output ports, each output port capable of releasing data units;

a switch fabric capable of selectively establishing a plurality of logical pathways between said input ports and said output ports, each logical pathway connecting a certain input port to a certain output port, whereby a data unit received at the certain input port can be transported to the certain output port on the logical pathway;

in response to the establishment of a certain logical pathway through said switch fabric, said method comprising the steps of enabling a bandwidth control mechanism to;

a) compute a bandwidth usage of the certain logical pathway; and

b) regulate the transport of data units over the certain logical pathway on a basis of the computed bandwidth usage.

45. A method as defined in claim 44, wherein said switch is a router.

46. A method as defined in claim 45, comprising the step of establishing a given logical pathway between a given input port and a given output port when a data unit is received at said given input port and has a destination that can be reached through said given output port.

47. A method as defined in claim 46, comprising the step of enabling an independent bandwidth control mechanism for each logical pathway established through said switch fabric.

48. A method as defined in claim 47, wherein each bandwidth control mechanism comprises a queue for storage of data units to be transported over the logical pathway associated with the bandwidth control mechanism.

49. A method as defined in claim 48, wherein each bandwidth control mechanism includes a queue control unit for regulating a rate of data packets released from said queue over the logical pathway associated with the bandwidth control mechanism.

50. A method as defined in claim 49, wherein said queue control unit is capable of performing an accounting operation to determine bandwidth usage as a result of releasing data packets from said queue.

51. A method as defined in claim 50, wherein said queue control unit is capable of computing an average bandwidth usage value when performing an accounting operation.

52. A method as defined in claim 51, wherein said queue control unit stops releasing data units from said queue when said average bandwidth usage value exceeds a certain threshold.

53. A method as defined in claim 52, wherein said queue control unit reduces a rate of data units released from said queue when said average bandwidth usage value exceeds a certain threshold.

54. A method as defined in claim 53, wherein said data units are IP data packets.

55. A switch for processing data units, said switch including:

a plurality of input ports, each input port capable of receiving data units;

a plurality of output ports, each output port capable of releasing data units;

a switch fabric capable of selectively establishing a plurality of logical pathways between said input ports and said output ports, each logical pathway connecting a certain input port to a certain output port, whereby a data unit received at the certain input port can be transported to the certain output port on the logical pathway between said certain output port and said certain input port;

a plurality of bandwidth control mechanisms for regulating the transport of data units in said switch, each bandwidth control mechanism being associated with a different logical pathway established through said switch fabric, each bandwidth control mechanism including;

a) a queue for storage of data units to be transported over the logical pathway associated with the bandwidth control mechanism; and

b) a queue control unit for regulating a rate of data packets released from said queue over the respective logical pathway, said queue control unit being capable of performing an accounting operation to determine bandwidth usage of the respective logical pathway as a result of releasing data packets from said queue.