Method and apparatus for interconnection of packet switches with guaranteed bandwidth

• US 6,714,517 B1
• Filed: 11/10/1998
• Issued: 03/30/2004
• Est. Priority Date: 11/10/1998
• Status: Expired due to Term

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Walrand, Jean, Fawaz, Ayman
• Primary Examiner(s): Jung, Min
• Application Number:
  US09/189,206
• Time in Patent Office: 1,967 Days
• Field of Search: 370/230, 370/232, 370/235, 370/236, 370/400, 370/410, 370/412, 370/417, 370/428, 370/537, 370/538, 370/540, 370/468
• US Class Current: 370/236
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A packet-switched communication network in accordance with the invention provides a guaranteed minimum bandwidth between pairs of Packet Switches by defining Service Level Agreements (SLAs). An SLA is defined by at least a source identifier, a destination identifier, and a minimum data rate although other information can also be used. Upon arrival at certain networked nodes, packets are classified according to an SLA by reading the source and destination addresses in the packet. Once classified, the packets are placed in a queue and scheduled for transmission. A scheduler ensures that packets are transmitted at the minimum defined data rate for the SLA. The scheduler may use a statistical multiplexing method, such as deficit round robin, or deficit golden ratio, which is part of the present invention. The deficit golden ratio method assures a minimum rate to packets for a particular SLA, but minimizes jitter and delay. Further, the present invention implements congestion control that does not require nodes to be entirely turned off in congested conditions.

Claims

1. In a packet forwarding quality of service (QoS) node, a method of data communications comprising:

receiving a plurality of data packets, each including classification information;

classifying each of said data packets with one of a plurality of service level agreements (SLAs) corresponding to said classification information for each packet;

scheduling said data packets for transmitting at or above a minimum data rate that corresponds to a respective SLA; and

reducing a data rate for transmitting packets corresponding to an SLA if downstream congestion is detected for packets associated with said SLA, while maintaining a data rate for transmitting packets corresponding to a different SLA for which downstream congestion is not detected.

2. The method of claim 1, wherein classifying each of said data packets further includes placing said packets into separate queues corresponding to their respective SLAs, and wherein scheduling said data packets includes multiplexing data packets from each SLA queue in accordance with a deficit golden ratio method.

3. The method of claim 1, further including:

assigning a queue threshold number to each SLA;

wherein scheduling said data packets includes, for each data packet, adding said data packet to a corresponding SLA queue if a number of data units in said SLA queue combined with a number of data units in said data packet is less than or equal to said queue threshold number, and otherwise discarding said data packet.

4. The method of claim 3, wherein adding said data packet if said number of data units is less than or equal to said queue threshold comprises adding said data packet if a number of data bits in said SLA queue combined with a number of data bits in said data packet is less than or equal to said queue threshold number.

5. The method of claim 1, wherein reducing said data rate comprises reducing said data rate to said minimum data rate.

6. The method of claim 1, wherein reducing said data rate comprises reducing said data rate below said minimum data rate.

7. The method of claim 1, wherein classifying said data packets further comprises placing data packets corresponding to different SLAs into an aggregate queue, and further comprising performing a Distributed Back Pressure (DBP) routine to adjust a rate of transmission of data packets corresponding to an SLA in response to congestion.

8. A network, comprising:

a first set of QoS nodes communicatively coupled in a ring; and

a second set of QoS nodes communicatively coupled with said first set to form a ring-star topology;

wherein each QoS node includes a packet classifier to classify data packets based, at least in part, on a service level agreement (SLA) associated with each packet, a scheduler to order said packets for transmitting at or above a minimum data rate specified by an SLA associated with each packet, and a plurality of SLA queues, each corresponding to an SLA, wherein said scheduler orders said packets according to a deficit golden ratio algorithm.

9. A packet forwarding network device, comprising:

an input to receive a plurality of data packets from one or more upstream nodes, each data packet including classification information;

a classifier coupled with said input to associate each of said data packets with one of a plurality of service level agreements (SLAs) corresponding to said classification information;

a scheduler responsive to said classifier to order said data packets for transmission such that said data packets are transmitted at or above a minimum data rate specified by their corresponding SLAs;

a transmitter to transmit said data packets as ordered by said scheduler; and

a congestion monitoring circuit coupled with said transmitter to monitor data packet transmission for data packets corresponding to each SLA, direct said transmitter to reduce a data rate of transmission of data packets for an SLA if downstream congestion is detected for data packets associated with said SLA, and direct said transmitter to maintain a data rate of transmission of data packets corresponding a different SLA for which downstream congestion is not detected.

10. The network device of claim 9, wherein said scheduler places each packet into a separate queue corresponding to said associated SLA, according to a golden ratio method.

11. The network device of claim 9, wherein

said classifier assigns a queue threshold number to each SLA; and

said scheduler adds a data packet to a queue corresponding to said associated SLA if a number of data units in said queue combined with a number of data units in said data packet is less than or equal to said queue threshold number, and otherwise discards said data packet.

12. The network device of claim 11, wherein said scheduler adds said data packet if a number of data bits in said queue combined with a number of d data bits in said data packet is less than or equal to said queue threshold number.

13. The network device of claim 9, wherein said congestion monitoring circuit directs said transmitter to reduce said data rate to said minimum data rate.

14. The network device of claim 9, wherein said congestion monitoring circuit directs said transmitter to reduce said data rate below said minimum data rate.

15. An article of manufacture comprising a machine-accessible medium that includes content that when accessed provides instructions to cause a packet forwarding network device to:

receive a plurality of data packets from one or more upstream nodes, each including classification information;

classify each of said data packets with one of a plurality of service level agreements (SLAs) corresponding to said classification information for each packet;

schedule said data packets for transmitting at or above a minimum data rate that corresponds to a respective SLA; and

reduce a data rate for transmitting packets corresponding to an SLA if downstream congestion is detected for packets associated with said SLA and maintain a data rate for transmitting packets corresponding to a different SLA for which downstream congestion is not detected.

16. The article of manufacture of claim 15, wherein said content to provide instructions to cause said network device to classify each of said data packets further includes said content to provide instructions to cause said network device to place the packets into separate queues corresponding to their respective SLAs, and wherein said content to provide instructions to cause said network device to schedule said data packets includes said content to provide instructions to cause said network device to multiplex data packets from each SLA queue in accordance with a deficit golden ratio method.

17. The article of manufacture of claim 15, further including said content to provide instructions to cause said network device to:

assign a queue threshold number to each SLA;

wherein scheduling said data packets includes, for each data packet, adding said data packet to a corresponding SLA queue if a number of data units in said SLA queue combined with a number of data units in said data packet is less than or equal to said queue threshold number, and otherwise discarding said data packet.

18. The article of manufacture of claim 17, wherein said content to provide instructions to cause said network device to add said data packet if said number of data units is less than or equal to said queue threshold comprises said content to provide instructions to cause said network device to add said data packet if a number of data bits in said SLA queue combined with a number of data bits in said data packet is less than or equal to said queue threshold number.

19. The article of manufacture of claim 15, wherein said content to provide instructions to cause said network device to reduce said data rate comprises said content to provide instructions to cause said network device to reduce said data rate to said minimum data rate.

20. The article of manufacture of claim 15, wherein said content to provide instructions to cause said network device to reduce said data rate comprises said content to provide instructions to cause said network device to reduce said data rate below said minimum data rate.

21. In a network switching node, a method comprising:

receiving data packets, each data packet having a corresponding service level agreement (SLA);

scheduling the data packets for transmitting at a data rate that is equal to or greater than a minimum data rate associated with the respective SLAs; and

reducing the data rate for transmitting data packets corresponding to a particular SLA for which downstream congestion is detected wherein scheduling the data packets includes maintaining queues associated with one or more SLAs, placing the data packets into corresponding SLA queues, and multiplexing data packets from each SLA queue in accordance with a golden ration algorithm.

22. The method of claim 21, wherein reducing the data rate comprises reducing the data rate to the minimum data rate.

23. The method of claim 21, wherein reducing the data rate comprises reducing the data rate to a level below the minimum data rate.

24. A network switching device, comprising:

an input to receive a plurality of data packets from an upstream node, each data packet to correspond to a service level agreement (SLA);

a scheduler to order the received data packets for transmission at a data rate equal to or greater than a minimum data rate associated with the corresponding SLAs;

a transmitter to transmit the data packets downstream as ordered by the scheduler; and

a congestion control circuit communicatively coupled with the transmitter and the downstream, to direct the transmitter to reduce the data rate of transmission of data packets corresponding to a particular SLA for which downstream congestion is detected.

25. The network switching device of claim 24, wherein the scheduler places the data packets into separate queues corresponding to one or more SLAs, and multiplexes the data packets from each SLA queue according to a golden ratio algorithm.

26. The network switching device of claim 24, wherein the congestion control circuit directs the transmitter to reduce the data rate to the minimum data rate.

27. The network switching device of claim 24, wherein the congestion control circuit directs the transmitter to reduce the data rate to a level below the minimum data rate.