Method and apparatus of processing packets having varying priorities by adjusting their drop functions according to a predefined fairness relationship

• US 6,820,128 B1
• Filed: 10/03/2000
• Issued: 11/16/2004
• Est. Priority Date: 11/04/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Zhang, Xiaohui, Guo, Yang, Firoiu, Victor
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US09/678,762
• Time in Patent Office: 1,505 Days
• Field of Search: 709/200, 709/223, 709/225, 709/230, 709/232, 709/233, 370/230.1, 370/229, 370/230-233
• US Class Current: 709/233
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

An apparatus and method of managing received packets to be transmitted from a network device stores the received packets on one of two different buffers. In particular, the received packets are one of a first type of data packet and a second type of packet. Each one of the first type is stored in a first buffer having a first drop function, while each one of the second type is stored in a second buffer having a second drop function. Each respective drop function specifies a packet drop rate as a function of the average number of packets in its respective buffer. The first drop function has a first average drop rate over a specified time interval, while the second drop function has a second average drop rate over the specified time interval. The first average drop rate and the second average drop rate have a predefined relationship. Accordingly, if the two drop rates do not comply with the predefined relationship, then at least one of the two average drop rates are modified.

Claims

1. A method of managing received packets to be tramsmitted from a network device, each packet being at least one of a first type and a second type, the method comprising:

storing the first type of packets in a first buffer, the first buffer having a first drop function that specifies a first packet drop rate as a function of the average number of first type of packets in the first buffer, the first drop function having a first average drop rate over a time interval;

storing the second type of packets in a second buffer, the second buffer having a second drop function that specifies a second packet drop rate as a function of the average number of second type of packets in the second buffer, the second drop function having a second average drop rate over the time interval; and

modifying at least one of the first average drop rate and the second average drop rate if such two drop average rates do not comply with a predefined fairness relationship.

2. The method as defined by claim 1 wherein the first buffer has a first packet withdrawal rate that specifies the rate that packets are withdrawn from the first buffer,

the second buffer having a second packet withdrawal rate that specifies the rate that packets are withdraw from the second buffer;

the act of modifying including;

changing at least one of the first packet withdrawal rate and the second packet withdrawal rate.

3. The method as defined by claim 1 wherein the act of modifying includes:

modifying the second average drop rate as a function of the average number of packets in the first buffer.

4. The method as defined by claim 1 wherein the first drop function has a first start point and a first end point,

the second drop function also having a second start point and a second end point.

5. The method as defined by claim 4 wherein the predefined relationship specifies that the first average drop rate is at the first start point whenever the second average drop rate is at the second start point.

6. The method as defined by claim 4 wherein the predefined relationship specifies that the first average drop rate is at the first end point whenever the second average drop rate is at the second end point.

7. The method as defined by claim 4 wherein the first drop function defines a first curve connecting the first start point and the first end point, the second drop function defining a second curve connecting the second start point and the second end point,

the predefined relationship specifying that the first average drop rate moves along the first curve at a first rate, the predefined relationship specifying that the second average drop rate moves along the second curve at a second rate, the first and second rates being rates.

8. The method as defined by claim 7 wherein the first rate and second rate are different.

9. The method as defined by claim 1 wherein the first type of packets are loss sensitive packets.

10. The method as defined by claim 9 wherein the second type of packets are delay sensitive packets.

11. The method as defined by claim 1 wherein the act of modifying includes:

altering at least one of the first drop function and the second drop function.

12. The method as defined by claim 1 wherein the first and second drop functions represent a drop probability.

13. A packet manager for managing received packets to be transmitted from a network device, the packets being at least one of a first type and a second type, the packet manager comprising:

a first buffer for storing the first type of packet, the first buffer having a first drop function that specifies a first packet drop rate as a function of the average number of first type of packets in the first buffer, the first drop function having a first average drop rate over a time interval;

a second buffer for storing the second type of packets, the second buffer having a second drop function that specifies a second packet drop rate as a function of the average number of second type of packets in the second buffer, the second drop function having a second average drop rate over the time interval; and

a modifier module operatively coupled with the first buffer and the second buffer, the modifier module modifying at least one of the first average drop rate and the second average drop rate if such two average drop rates do not comply with a predefined fairness relationship.

14. The packet manager as defined by claim 13 wherein the first buffer has a first packet withdrawal rate that specifies the rate that packets are withdrawn from the first buffer,

the second buffer having a second packet withdrawal rate that specifies the rate that packets are withdrawn from the second buffer;

the modifier module including;

a withdrawal module that changes at least one of the first packet withdrawal rate and the second packet withdrawal rate.

15. The packet manager as defined by claim 13 wherein the modifier module includes:

a rate modifier that modifies the second average drop rate as a function of the average number of packets in the first buffer.

16. The packet manager as defined by claim 13 wherein the first drop function has a first start point and a first end point,

the second drop function also having a second start point and a second end point.

17. The packet manager as defined by claim 16 wherein the predefined relationship specifies that the first average drop rate is at the first start point whenever the second average drop rate is at the second start point.

18. The packet manager as defined by claim 16 wherein the predefined relationship specifies that the first average drop rate is at the first end point whenever the second average drop rate is at the second end point.

19. The packet manager as defined by claim 16 wherein the first drop function defines a first curve connecting the first start point and the first end point, the second drop function defining a second curve connecting the second start point and the second end point,

the predefined relationship specifying that the first average drop rate moves along the first curve at a first rate, the predefined relationship specifying that the second average drop rate moves along the second curve at a second rate, the first and second rates being constant rates.

20. The packet manager as defined by claim 19 wherein the first rate and second rate are different.

21. The packet manager as defined by claim 13 wherein the first type of packets are loss sensitive packets.

22. The packet manager as defined by claim 13 wherein the second type of packets are delay sensitive packets.

23. The packet manager as defined by claim 13 wherein the modifier module alters at least one of the first drop function and the second drop function.

24. The method as defined by claim 13 wherein the first and second drop functions represent a drop probability.

25. A computer program product for use on a computer system for managing received packets to be transmitted from a network device, the packets being at least one of a first type and a second type, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code comprising:

program code for storing the first type of packets in a first buffer, the first buffer having a first drop function that specifies a first packet drop rate as a function of the average number of first type of packets in the first buffer, the first drop function having a first average drop rate over a time interval;

program code for storing the second type of packets in a second buffer, the second buffer having a second drop function that specifies a second packet drop rate as a function of the average number of second type of packets in the second buffer, the second drop function having a second average drop rate over the specified time interval; and

program code for modifying at least one of the first average drop rate and the second average drop rate if such two average drop rates do not comply with a predefined fairness relationship.

26. The computer program product as defined by claim 25 wherein the first buffer has a first packet withdrawal rate that specifies the rate that packets are withdrawn from the first buffer,

the second buffer having a second packet withdrawal rate that specifies the rate that packets are withdrawn from the second buffer;

the program code for modifying including;

program code for changing at least one of the first packet withdrawal rate and the second packet withdrawal rate.

27. The computer program product as defined by claim 25 wherein the program code for modifying includes:

program code for modifying the second average drop rate as a function of the average number of packets in the first buffer.

28. The computer program product as defined by claim 25 wherein the first drop function has a first start point and a first end point,

the second drop function also having a second start point and a second end point.

29. The computer program product as defined by claim 28 wherein the predefined relationship specifies that the first average drop rate is at the first start point whenever the second average drop rate is at the second start point.

30. The computer program product as defined by claim 28 wherein the predefined relationship specifies that the first average drop rate is at the first end point whenever the second average drop rate is at the second end point.

31. The computer program product as defined by claim 28 wherein the first drop function defines a first curve connecting the first start point and the first end point, the second drop function defining a second curve connecting the second start point and the second end point,

the predefined relationship specifying that the first average drop rate moves along the first curve at a first rate, the predefined relationship specifying that the second average drop rate moves along the second curve at a second rate, the first and second rates being constant rates.

32. The computer program product as defined by claim 31 wherein the first rate and second rate are different.

33. The computer program product as defined by claim 25 wherein the first type of packets are loss sensitive packets.

34. The computer program product as defined by claim 33 wherein the second type of packets are delay sensitive packets.

35. The computer program product as defined by claim 25 wherein the program code for modifying includes:

program code for altering at least one of the first drop function and the second drop function.

36. The computer program product as defined by claim 25 wherein the first and second drop functions represent a drop probability.

37. A method of processing a received packet for transmission across a network, the packet being one of at least two types of packets, the at least two types of packets including delay sensitive packets and loss sensitive packets, the method comprising:

determining the type of the packet;

adding the packet to a loss sensitive buffer if the packet is determined to be a loss sensitive packet, the loss sensitive buffer having a loss sensitive packet drop function relating to dropping packets in the loss sensitive buffer;

adding the packet to a delay sensitive buffer if the packet is determined to be a delay sensitive packet, the delay sensitive buffer having a delay sensitive packet drop function relating to dropping packets in the delay sensitive buffer;

the two buffers being operatively coupled with an output for forwarding packets to the network,

the loss sensitive packet drop function and the delay sensitive packet drop function being different and related to achieve a predetermined fairness.

38. The method as defined by claim 37 wherein each packet drop functions produces a packet drop rate as a function of the average number of packets in its buffer.

39. The method as defined by claim 37 further comprising:

forwarding the packet from one of the two buffers to the output for transmission to the network.

40. The method as defined by claim 37 wherein the packet has a header with data identifying the type, the type being determined by parsing the header.

41. The method as defined by claim 37 wherein the two buffers each have an associated weight variable for transmitting packets to the network.

42. The method as defined by claim 41 wherein the weight variable of each buffer has an associated fairness quality.

43. An apparatus for processing a received packet for transmission across a network, the packet being one of at least two types of packets, the at least two types of packets including delay sensitive packets and loss sensitive packets, the method comprising:

a packet module for determining the type of the packet;

a loss sensitive buffer operatively coupled with the packet module, the loss sensitive buffer storing the packet if the packet is determined to be a loss sensitive packet, the loss sensitive buffer having a loss sensitive packet drop function relating to dropping packets in the loss sensitive buffer;

a delay sensitive buffer operatively coupled with the packet module, the delay sensitive buffer storing the packet if the packet is determined to be a delay sensitive packet, the delay sensitive buffer having a delay sensitive packet drop function relating to dropping packets in the delay sensitive buffer, said delay sensitive packet drop function being related to said loss sensitive packet drop function to achieve a predetermined fairness,

the loss sensitive packet drop function and the delay sensitive packet drop function being different; and

an output module operatively coupled with the two buffers, the output module forwarding packets to the network.

44. The apparatus as defined by claim 43 wherein each packet drop functions produces a packet drop rate as a function of the average number of packets in its buffer.

45. The apparatus as defined by claim 43 further comprising:

forwarding the packet from one of the two buffers to the output for transmission to the network.

46. The apparatus as defined by claim 43 wherein the packet has a header with data identifying the type, the type being determined by parsing the header.

47. The apparatus as defined by claim 43 wherein the two buffers each have an associated weight variable for transmitting packets to the network.

48. The apparatus as defined by claim 47 wherein the weight variable of each buffers has an associated fairness quality.

49. A computer program product for use on a computer system for processing a received packet for transmission across a network, the packet being one of at least two types of packets, the at least two types of packets including delay sensitive packets and loss sensitive packets, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code comprising:

program code for determining the type of the packet;

program code for adding the packet to a loss sensitive buffer if the packet is determined to be a loss sensitive packet, the loss sensitive buffer having a loss sensitive packet drop function relating to dropping packets in the loss sensitive buffer; and

program code for adding the packet to a delay sensitive buffer if the packet is determined to be a delay sensitive packet, the delay sensitive buffer having a delay sensitive packet drop function relating to dropping packets in the delay sensitive buffer;

the two buffers being operatively coupled with an output for forwarding packets to the network,

the loss sensitive packet drop function and the delay sensitive packet drop function being different and related to achieve a predetermined fairness.

50. The computer program product as defined by claim 49 wherein each packet drop functions produces a packet drop rate as a function of the average number of packets in its buffer.

51. The computer program product as defined by claim 49 further comprising:

program code for forwarding the packet from one of the two buffers to the output for transmission to the network.

52. The computer program product as defined by claim 49 wherein the packet has a header with data identifying the type, the program code for determined including program code for parsing the header.

53. The computer program product as defined by claim 49 wherein the two buffers each have an associated weight variable for transmitting packets to the network.

54. The computer program product as defined by claim 53 wherein the weight variable of each buffer has an associated fairness quality.

55. The computer program product as defined by claim 49 wherein the loss sensitive packet drop function relates to drop probabilities.

56. A system for managing packets to be transmitted from a network device, the packets being one of a first type and a second type, the system comprising:

a packet marker for marking the type of each packet;

an input module for receiving packets;

a first buffer operatively coupled with the input module, the first buffer storing the first type of packets, the first buffer having a first drop function that specifies a packet drop rate as a function of the average number of packets in the first buffer, the first drop function having a first average drop rate over a specified time interval;

a second buffer operatively coupled with the input module, the second buffer storing the second type of packets, the second buffer having a second drop function that specifies a packet drop rate as a function of the average number of packets in the second buffer, the second drop function having a second average drop rate over the specified time interval,

the first average drop rate and the second average drop rat having a predefined relationship; and

a modifier module operatively coupled with the first buffer and the second buffer, the modifier module modifying at least one of the first average drop rate and the second average drop rate if such two drop rates do not comply with the predefined fairness relationship.

57. The system as defined by claim 56 wherein the first buffer has a first packet withdrawal rate that specifies the rate that packets are withdrawn from the first buffer,

the second buffer having a second packet withdrawal rate that specifies the rate that packets are withdrawn from the second buffer,

the modifier module including:

a withdrawal module that changes at least one of the first packet withdrawal rate and the second packet withdrawal rate.

58. The system as defined by claim 56 wherein the modifier module includes:

a rate modifier that modifies the second average drop rate as a function of the average of packets in the first buffer.