Method and apparatus to reduce Jitter in packet switched networks

• US 6,654,374 B1
• Filed: 11/10/1998
• Issued: 11/25/2003
• Est. Priority Date: 11/10/1998
• Status: Expired due to Term

• Current Assignee: Extreme Networks, Inc.
• Original Assignee: Extreme Networks, Inc.
• Inventors: Walrand, Jean, Fawaz, Ayman
• Primary Examiner(s): Nguyen, Steven
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US09/189,347
• Time in Patent Office: 1,841 Days
• Field of Search: 370/230, 370/231, 370/232-235, 370/253, 370/389, 370/395.21, 370/395.4, 370/395.41, 370/412-413
• US Class Current: 370/394
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/52 by attributing bandwidth to queues
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 47/623 Weighted service order
• CPC Class Codes: H04L 47/6285 Provisions for avoiding starvation of low priority queues
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

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. A method of data packet transmission comprising:

receiving a data packet;

classifying the data packet based on classification information associated with the data packet;

storing the data packet in one of a plurality of queues, the one queue corresponding to the classification of the packet; and

scheduling transmission of the data packet from the one queue with transmission of other data packets stored in the other queues in accordance with a deficit golden ratio algorithm, including;

scheduling transmission of the data packet from the one queue with transmission of other data packets stored in the other queues according to a golden ratio; and

assigning to a data stream associated with the data packet a deficit if transmission of the data packet will equal or exceed a threshold bandwidth value corresponding to the associated data streams, and a credit if transmission of the data packet will not equal or exceed the threshold bandwidth value corresponding to the associated data stream.

2. The method of claim 1 wherein classifying the data packet based on classification information associated with the data packet comprises classifying the data packet based on information obtained from the data packet.

3. The method of claim 2 wherein classifying the data packet based on information obtained from the data packet comprises classifying the data packet based on information obtained from a header of the packet.

4. The method of claim 2 wherein classifying the data packet based on information obtained from the data packet comprises classifying the data packet based, at least in part, on source and destination address information.

5. The method of claim 4 wherein classifying the data packet based, at least in part, on source and destination address information comprises classifying the data packet based on physical layer address information.

6. The method of claim 1 wherein classifying the data packet based on classification information associated with the data packet comprises classifying the data packet based, at least in part, on information indicating packet type.

7. An article of manufacture comprising a machine accessible medium having content that when accessed provides instructions to cause an electronic device to:

receive a data packet;

classify the data packet based on classification information associated with the data packet;

store the data packet in one of a plurality of queues, the one queue corresponding to the classification of the packet; and

schedule transmission of the data packet from the one queue with transmission of other data packets stored in the other queues in accordance with a deficit golden ratio algorithm, including the content providing instructions to cause the electronic device to;

schedule transmission of the data packet from the one queue with transmission of other data packets stored in the other queues according to a golden ratio; and

assign to a data stream associated with the data packet a deficit if transmission of the data packet will equal or exceed a threshold bandwidth value corresponding to the associated data stream, and a credit if transmission of the data packet will not equal or exceed the threshold bandwidth value corresponding to the associated data stream.

8. The article of manufacture of claim 7 wherein the content providing instructions to cause the electronic device to classify the data packet based on classification information associated with the data packet comprises the content providing instruction to cause the electronic device to classify the data packet based on information obtained from the data packet.

9. The article of manufacture of claim 8 wherein the content providing instructions to cause the electronic device to classify the data packet based on information obtained from the data packet comprises the content providing instructions to cause the electronic device to classify the data packet based on information obtained from a header of the packet.

10. The article of manufacture of claim 8 wherein the content providing instructions to cause the electronic device to classify the data packet based on information obtained from the data packet comprises the content providing instructions to cause the electronic device to classify the data packet based, at least in part, on source and destination address information.

11. The article of manufacture of claim 10 wherein the content providing instructions to cause the electronic device to classify the data packet based, at least in part, on source and destination address information comprises the content providing instructions to cause the electronic device to classify the data packet based on physical layer address information.

12. The article of manufacture of claim 7 wherein the content providing instructions to cause the electronic device to classify the data packet based on classification information associated with the data packet comprises the content providing instruction to cause the electronic device to classify the data packet based, at least in part, on information indicating packet type.

13. A method for transmitting data packets received from multiple data streams, comprising:

assigning a bit weight to each data stream;

generating a set of numbers;

associating a number of the set to each data packet based, at least in part, on a minimum bandwidth specification associated with a data stream to which the data packet corresponds;

ordering the data packets based on the number associated with each data packet;

transmitting the data packets as ordered;

monitoring a number of bits transmitted associated with one or more of the data streams; and

assigning a value to the data stream(s) monitored, the value being;

a credit of a quantity;

the bit weight minus the number of bits transmitted, if the number of bits transmitted is less than the bit weight; and

a deficit of a quantity;

the number of bits transmitted minus the bit weight, if the number of bits transmitted is greater than or equal to the bit weight.

14. The method of claim 13 wherein generating a set of numbers comprises multiplying a golden ratio value by a set of integers to obtain a set of decimal fractions, and wherein associating a number of the set to each data packet comprises assigning each data packet a different decimal fraction.

15. The method of claim 14 wherein ordering the data packets comprises ordering the data packets in order of ascending value of the respective associated decimal fractions.

16. The method of claim 14 wherein ordering the data packets comprises ordering the data packets in order of descending value of the respective associated decimal fractions.

17. The method of claim 14 further comprising repeating transmitting the data packets, monitoring the number of bits transmitted, and assigning credits and deficits until the credit for each data stream is less than or equal to zero.

18. The method of claim 17 further comprising reducing the quantity of the credit by the quantity of the deficit.

19. An article of manufacture comprising a machine accessible medium having content that when accessed provides instructions to cause an electronic system to:

assign a bit weight to each data stream;

generate a set of numbers;

associate a number of the set to each data packet based, at least in part, on a minimum bandwidth specification associated with a data stream to which the data packet corresponds;

order the data packets based on the number associated with each data packet;

transmit the data packets as ordered;

monitor a number of bits transmitted associated with one or more of the data streams; and

assign a value to the data stream(s) monitored, the value to be;

a credit of a quantity;

the bit weight minus the number of bits transmitted, if the number of bits transmitted is less than the bit weight; and

a deficit of a quantity;

the number of bits transmitted minus the bit weighs, if the number of bits transmitted is greater than or equal to the bit weight.

20. The article of manufacture of claim 19 wherein the content to provide instructions to generate a set of numbers comprises the content to provide instructions to cause the electronic system to multiply a golden ratio value by a set of integers to obtain a set of decimal fractions, and wherein the content to provide instructions to associating a number of the set to each data packet comprises the content to provide instructions to cause the electronic system to assign each data packet a different decimal fraction.

21. The article of manufacture of claim 20 wherein the content to provide instructions to order the data packets comprises the content to provide instructions to cause the electronic system to order the data packets in order of ascending value of the respective associated decimal fractions.

22. The article of manufacture of claim 20 wherein the content to provide instructions to order the data packets comprises the content to provide instructions to cause the electronic system to order the data packets in order of descending value of the respective associated decimal fractions.

23. The article of manufacture of claim 20 further comprising the content to provide instructions to cause the electronic system to transmit the data packets, monitor the number of bits transmitted, and assign credits and deficits until the credit for each data stream is less than or equal to zero.

24. The article of manufacture of claim 23 further comprising the content to provide instructions to cause the electronic system to reduce the quantity of the credit by the quantity of the deficit.