Regulating packet traffic in an integrated services network

• US 6,680,906 B1
• Filed: 03/31/1999
• Issued: 01/20/2004
• Est. Priority Date: 03/31/1999
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nguyen, Khanh Vinh
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/283,117
• Time in Patent Office: 1,756 Days
• Field of Search: 570/229, 570/230, 570/230.1, 570/232, 570/235, 570/236, 570/235.1, 570/244, 570/394, 570/392, 570/351, 570/395.4, 570/395.42, 570/401, 570/410, 570/415, 570/412, 570/416, 570/408, 570/400, 570/477, 710/56, 710/60, 709/238, 709/242
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6285 Provisions for avoiding starvation of low priority queues
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

Methods and mechanisms for regulating network packet traffic in an integrated services network, by selectively dropping packets of particular traffic, are described. Packets of network traffic arriving at an input port of a router or switch are selectively copied to one of two queues according to the type of transmission (voice, video, data) represented by the packets. A first queue receives traffic requiring guaranteed bandwidth and the second queue receives traffic requiring guaranteed minimum delay. Data in the packets indicates when the packet should be dropped relative to other packets in a packet stream. The process of marking packets with data used to indicate a drop order is referred to herein as marking packets. A network device that receives marked packets, for example, a router, may drop some of packets according to a drop policy based on the values used to mark the packets.

Claims

1. A method of managing traffic directed from a first network element to a second network element in a packet-switched network, comprising the steps of:

receiving, from the first network element, a plurality of packets each including a drop priority value in a drop priority field that indicates an order to drop the packet relative to other packets among the plurality of packets;

storing the plurality of packets in a queue;

detecting a drop condition, and in response thereto;

from among packets in the queue, selecting one or more packets based on the drop priority value in the drop priority field of each of said packets in the queue, and

dropping the selected packets from the queue while transmitting to the second network element other packets of said plurality of packets;

wherein the step of receiving includes receiving a plurality of packets that includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values and a second subset of packets that each include a drop priority field set to a second drop priority value of said set of drop priority values; and

wherein the step of selecting includes selecting all packets from said first subset before selecting packets from said second subset.

2. A method as recited in claim 1, wherein the step of selecting includes selecting a first packet that is received after at least one other packet from said plurality of packets.

3. A method as recited in claim 1, wherein the step of receiving a plurality of packets includes assigning the first drop priority values and the second drop priority values according to a pre-determined ratio.

4. A method as recited in claim 1, wherein the step of receiving includes receiving a plurality of packets each having drop priority field values that form a sequence of consecutively greater integers.

5. A method as recited in claim 1, wherein the step of selecting one or more packets comprises selecting only an earlier received packet that has a particular drop priority field value.

6. A method as recited in claim 1, wherein the step of storing includes storing said plurality of packets in a first set of one or more first queues, and further comprising the step of storing a second plurality of packets in a second set of one or more second queues.

7. A method as recited in claim 1, wherein the step of storing includes storing said plurality of packets either in a first set of one or more first queues, or in a second plurality of packets in a second set of one or more second queues, according to a type of traffic represented by the plurality of packets.

8. A method as recited in claim 7, wherein the step of storing includes the steps of:

storing said plurality of packets in a queue selected from among a plurality of queues according to a type of data contained in each packet of said plurality of packets; and

storing packets containing voice traffic in a first queue of the plurality of queues and storing data traffic in a second queue of the plurality of queues.

9. A method as recited in claim 1, wherein the step of storing includes storing said plurality of packets in a queue selected from among a plurality of queues according to a type of data contained in each packet of said plurality of packets.

10. A network traffic apparatus, the network traffic apparatus configured to perform the steps of:

receiving a plurality of packets each containing a drop priority field that contains a drop value indicating an order in which to drop that packet relative to other packets;

wherein the drop priority field of a first subset of packets of the plurality of packets stores a first drop value from a set of values that includes a second drop value;

wherein the drop priority field of a second subset of packets stores said second value, wherein the ratio of the number packets in the first subset to the number of packets in the second subset is substantially equal to a predetermined ratio; and

in response to detection of network congestion, selectively dropping one or more packets according to the drop value of each of the packets.

11. A method of managing transmission of packets of network traffic from a first network element to a second network element, the method comprising the steps of:

generating a plurality of packets each containing a drop priority field;

storing, in the drop priority field of each of the packets, a drop priority value that indicates an order in which to drop that packet relative to other packets;

in response to detection of network congestion, selectively dropping one or more packets according to the drop priority value of each of the packets, while transmitting the other packets of said plurality of packets from the first network element to the second network element;

storing in the drop priority field of each packet of a first subset of packets a first drop priority value from a set of values that includes a second drop priority value; and

storing the second value in the drop priority field of each packet of a second subset of packets, wherein the ratio of the number packets in the first subset to the number of packets in the second subset is substantially equal to a predetermined ratio.

12. A method of managing packet based network traffic, the method comprising the steps of:

a first network device generating a plurality of packets that includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values that indicate an order in which to drop said packet relative to other packets of said plurality of packets and

a second subset of packets from said plurality of packets that each include a drop priority field set to a second value of the set of drop priority values;

the first network device transmitting said plurality of packets to a second network device;

the second network device receiving said plurality of packets;

the second network device storing said plurality of packets;

detecting a drop condition;

in response to detecting said drop condition;

selecting one or more of said plurality of packets based on the order indicated by the drop priority values in the drop priority field of each of said plurality of packets, and

dropping said one or more plurality of packets while transmitting the other packets of said plurality of packets from the second network element to another network element;

wherein the step of receiving includes receiving a plurality of packets that includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values and a second subset of packets that each include a drop priority field set to a second drop priority value of said set of drop priority values; and

wherein the step of selecting includes selecting all packets from said first subset before selecting packets from said second subset.

13. A network traffic regulation apparatus, comprising:

an input port coupled to a packet-switched network and receiving network traffic therefrom;

a first queue and a second queue coupled to the input port, each queue comprising a plurality of queue buckets that may receive a packet of the network traffic, each packet including a type value that identifies a type of transmission represented by the packet, each packet including a drop priority value in a drop priority field that indicates an order to drop the packet relative to other packets;

a copier that selectively copies the network traffic to the first queue or to the second queue based on the type value of the packet;

wherein a particular queue of said first queue and said second queue includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values and a second subset of packets that each include a drop priority field set to a second drop priority value of said set of drop priority values; and

a queue monitor that;

monitors available storage in the first queue and the second queue, and

from among the packets in the particular queue, selectively drops packets from the particular queue according to their drop priority values when a network congestion condition is identified by selectively dropping all packets from said first subset before selectively dropping packets from said second subset.

14. A network traffic regulation apparatus as recited in claim 13, wherein the first queue is reserved for non-priority network traffic and the second queue is reserved for priority network traffic, and

wherein the copier copies data type packets only to the first queue and copies voice type packets only to the second queue.

15. A network traffic regulation apparatus as recited in claim 13, wherein the first queue is reserved for network traffic requiring guaranteed bandwidth availability and the second queue is reserved for network traffic requiring guaranteed minimum transmission delay.

16. A network traffic regulation apparatus as recited in claim 13, wherein the first queue is reserved for network traffic requiring guaranteed bandwidth availability and the second queue is reserved for network traffic requiring guaranteed minimum transmission delay, and wherein the copier copies data type packets only to the first queue and copies voice type packets only to the second queue.

17. A network traffic regulation apparatus as recited in claim 13,

wherein the first queue is reserved for network traffic requiring guaranteed bandwidth availability and the second queue is reserved for network traffic requiring guaranteed minimum transmission delay;

wherein the copier copies data type packets only to the first queue and copies voice type packets only to the second queue;

wherein the queue monitor monitors available storage in the first queue and the second queue;

wherein the queue monitor selectively drops packets from the first queue only according to their drop priority values when a network congestion condition is identified; and

wherein the queue monitor selectively drops packets from the second queue only based on a Rapid Early Detection (“

RED”

) mechanism.

18. A network traffic regulation apparatus as recited in claim 13,

wherein the queue monitor selectively drops packets from the first queue only according to their drop priority values when a network congestion condition is identified;

and

wherein the queue monitor selectively drops packets from the second queue only based on a Rapid Early Detection (“

RED”

) mechanism.

19. A network traffic regulation apparatus as recited in claim 13, wherein the queue monitor selectively drops packets from the queues according to their drop priority values when a network congestion condition is identified by carrying out the steps of:

detecting the network congestion condition;

determining a current drop priority value; and

determining whether the first queue contains more than one packet having the current drop priority value, and if so, dropping the oldest packet in the first queue having the current drop priority value.

20. A network traffic regulation apparatus as recited in claim 13, wherein the queue monitor selectively drops packets from the queues according to their drop priority values when a network congestion condition is identified by carrying out the steps of:

detecting the network congestion condition;

determining a current drop priority value; and

determining whether the first queue contains more than one packet having the current drop priority value, and if not, dropping the last remaining packet in the first queue having the current drop priority value.

21. A switching apparatus for packet-switched networks, comprising:

a plurality of input ports each coupled to a packet-switched network to receive network traffic therefrom and coupled to associated input lines;

a plurality of output ports each directed to other network elements and which may be selectively logically coupled to one of the input ports at a crosspoint therewith;

a traffic regulator module logically coupled between each input port and each input line, the traffic regulator module comprising;

a first queue and a second queue, each queue comprising a plurality of queue buckets that may receive a packet of the network traffic, each packet including a type value that identifies a type of transmission represented by the packet, each packet including a drop priority value in a drop priority field that indicates an order to drop the packet relative to other packets among the plurality of packets;

a copier that selectively copies the network traffic to the first queue or to the second queue based on the type value of the packet;

wherein a particular queue of said first queue and said second queue includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values and a second subset of packets that each include a drop priority field set to a second drop priority value of said set of drop priority values; and

a queue monitor that;

monitors available storage in the first queue and the second queue, and

from among the packets in the particular queue, selectively drops packets from the particular queue according to their drop priority values when a network congestion condition is identified by selectively dropping all packets from said first subset before selectively dropping packets from said second subset.

22. A computer-readable medium carrying one or more sequences of instructions for managing traffic directed from a first network element to a second network element in a packet-switched network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving, from the first network element, a plurality of packets each including a drop priority value in a drop priority field that indicates an order to drop the packet relative to other packets among the plurality of packets;

storing the plurality of packets in a queue;

detecting a drop condition, and in response thereto;

from among packets in the queue, selecting one or more packets based on the drop priority value in the drop priority field of each of said packets in the queue, and

dropping the selected packets from the queue while transmitting to the second network element other packets of said plurality of packets;

wherein the step of receiving includes receiving a plurality of packets that includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values and a second subset of packets that each include a drop priority field set to a second drop priority value of said set of drop priority values; and

wherein the step of selecting includes selecting all packets from said first subset before selecting packets from said second subset.

23. A computer-readable medium as recited in claim 22, wherein the step of selecting includes selecting a first packet that is received after at least one other packet from said plurality of packets.

24. A computer-readable medium as recited in claim 22, wherein the step of receiving a plurality of packets includes assigning the first drop priority values and the second drop priority values according to a pre-determined ratio.

25. A computer-readable medium as recited in claim 22, wherein the step of receiving includes receiving a plurality of packets each having drop priority field values that form a sequence of consecutively greater integers.

26. A computer-readable medium as recited in claim 22, wherein the step of selecting one or more packets comprises selecting only an earlier received packet that has a particular drop priority field value.

27. A computer-readable medium as recited in claim 22, wherein the step of storing includes storing said plurality of packets in a first set of one or more first queues, and further comprising the step of storing a second plurality of packets in a second set of one or more second queues.

28. A computer-readable medium as recited in claim 22, wherein the step of storing includes storing said plurality of packets either in a first set of one or more first queues, or in a second plurality of packets in a second set of one or more second queues, according to a type of traffic represented by the plurality of packets.

29. A computer-readable medium as recited in claim 28, wherein the step of storing includes the steps of:

storing said plurality of packets in a queue selected from among a plurality of queues according to a type of data contained in each packet of said plurality of packets; and

storing packets containing voice traffic in a first queue of the plurality of queues and storing data traffic in a second queue of the plurality of queues.

30. A computer-readable medium as recited in claim 22, wherein the step of storing includes storing said plurality of packets in a queue selected from among a plurality of queues according to a type of data contained in each packet of said plurality of packets.

31. A computer-readable medium carrying one or more sequences of instructions for managing traffic directed from a first network element to a second network element in a packet-switched network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving network traffic from a packet-switched network;

creating and storing a first queue and a second queue, each queue comprising a plurality of queue buckets that may receive a packet of the network traffic, each packet including a type value that identifies a type of transmission represented by the packet, each packet including a drop priority value in a drop priority field that indicates an order to drop the packet relative to other packets;

selectively copying the network traffic to the first queue or to the second queue based on the type value of the packet;

monitoring available storage in the first queue and the second queue;

from among the packets in a particular queue of said first queue and said second queue, selectively dropping packets from the particular queue according to their drop priority values when a network congestion condition is identified;

wherein the particular queue of said first queue and said second queue includes a first subset of packets that each include a drop priority field set to a first drop priority value of a set of drop priority values and a second subset of packets that each include a drop priority field set to a second drop priority value of said set of drop priority values; and

wherein the step of selectively dropping packets includes selecting all packets from said first subset before selecting packets from said second subset.

32. A computer-readable medium as recited in claim 31, further comprising the steps of:

reserving the first queue for non-priority network traffic;

reserving the second queue is for priority network traffic; and

copying data type packets only to the first queue and copies voice type packets only to the second queue.

33. A computer-readable medium as recited in claim 31, further comprising the steps of:

reserving the first queue for network traffic requiring guaranteed bandwidth availability and

reserving the second queue for network traffic requiring guaranteed minimum transmission delay.

34. A computer-readable medium as recited in claim 31, further comprising the steps of:

reserving the first queue for network traffic requiring guaranteed bandwidth availability;

reserving the second queue for network traffic requiring guaranteed minimum transmission delay; and

copying data type packets only to the first queue and copies voice type packets only to the second queue.

35. A computer-readable medium as recited in claim 31, further comprising the steps of:

reserving the first queue for network traffic requiring guaranteed bandwidth availability and reserving the second queue for network traffic requiring guaranteed minimum transmission delay;

copying data type packets only to the first queue and copies voice type packets only to the second queue;

monitoring available storage in the first queue and the second queue;

selectively dropping packets from the first queue only according to their drop priority values when a network congestion condition is identified; and

selectively dropping packets from the second queue only based on a Rapid Early Detection (“

RED”

) mechanism.

36. A computer-readable medium as recited in claim 31, further comprising the steps of:

selectively dropping packets from the first queue only according to their drop priority values when a network congestion condition is identified; and

selectively dropping packets from the second queue only based on a Rapid Early Detection (“

RED”

) mechanism.

37. A computer-readable medium as recited in claim 31, further comprising the steps of:

selectively dropping packets from the queues according to their drop priority values when a network congestion condition is identified by carrying out the steps of;

detecting the network congestion condition;

determining a current drop priority value; and

determining whether the first queue contains more than one packet having the current drop priority value, and if so, dropping the oldest packet in the first queue having the current drop priority value.

38. A computer-readable medium as recited in claim 31, further comprising the steps of:

selectively dropping packets from the queues according to their drop priority values when a network congestion condition is identified by carrying out the steps of;

detecting the network congestion condition;

determining a current drop priority value; and

determining whether the first queue contains more than one packet having the current drop priority value, and if not, dropping the last remaining packet in the first queue having the current drop priority value.

39. A method of managing transmission of packets over a network, the method comprising the steps of:

generating a plurality of packets each containing a drop priority field;

storing, in the drop priority field of each of the packets, a drop value that indicates an order in which to drop that packet relative to other packets;

storing in the drop priority field of each packet of a first subset of packets of the plurality of packets a first drop value from a set of values that includes a second drop value;

storing the second value in the drop priority field of each packet of a second subset of packets, wherein the ratio of the number packets in the first subset to the number of packets in the second subset is substantially equal to a predetermined ratio; and

transmitting over a network to a network element said plurality of packets, wherein the step of transmitting causes said network element to selectively drop one or more packets according to the drop value of each of the packets in response to detection of network congestion.

40. The method of claim 39, wherein the step of transmitting causes said network element to selectively drop one or more packets by performing one or more steps that include selecting all packets from said first subset before selecting packets from said second subset.

41. A computer-readable medium carrying one or more sequences of instructions for managing transmission of packets over a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

generating a plurality of packets each containing a drop priority field;

storing, in the drop priority field of each of the packets, a drop value that indicates an order in which to drop that packet relative to other packets;

storing in the drop priority field of each packet of a first subset of packets of the plurality of packets a first drop value from a set of values that includes a second drop value;

storing the second value in the drop priority field of each packet of a second subset of packets, wherein the ratio of the number packets in the first subset to the number of packets in the second subset is substantially equal to a predetermined ratio; and

transmitting over a network to a network element said plurality of packets, wherein the step of transmitting causes said network element to selectively drop one or more packets according to the drop value of each of the packets in response to detection of network congestion.

42. The computer-readable medium of claim 41, wherein the step of transmitting causes said network element to selectively drop one or more packets by performing steps that include selecting all packets from said first subset before selecting packets from said second subset.