Router with class of service mapping

• US 7,106,731 B1
• Filed: 07/14/2000
• Issued: 09/12/2006
• Est. Priority Date: 12/31/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hashmi, Tauseef, Edsall, Thomas J., Lin, Arthur
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): NGUYEN, TOAN D
• Application Number:
  US09/616,842
• Time in Patent Office: 2,251 Days
• Field of Search: None
• US Class Current: 370/389
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• 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/32 by discarding or delaying data units, e.g. packets or frames

Abstract

A router classifies packets assigned to X*Y classes of service into X classes of service supported by the router, each of the X classes of service having Y loss-priority levels. The router maintains a free queue that links available entries of a buffer in which packets are stored. A weighted average depth of the free queue is used to determine whether to retain a given packet. If the weighted average is above a maximum threshold, the packet is retained. If the weighted average is below a minimum threshold, the packet is discarded. If the weighted average is between the two thresholds, a probability of discard that is based on the X*Y classes of service is calculated and compared to a random value to determine whether the packet should be retained.

Claims

1. A router for use in routing packets over a network, the router supporting a plurality, X, of classes of service and including:

A. a plurality of input ports configured to receive packets over the network;

B. a plurality of output ports configured to transfer packets over the network;

C. a classifier configured to assign packets received by the input ports to X*Y classes of service, where * represents multiplication, and mapping the X*Y classes of service to the X classes of service that are supported by the router, the classifier assigning to the packet one of Y associated levels of priority, wherein each level of priority is associated with a different probability of packet loss;

D. a buffer subsystem configured to retain the packets in class of service per output port queues based on probabilities of discard associated with the X*Y classes of service; and

E. a scheduler for transferring the packets from the buffer subsystem through each of the output ports based on the X classes of service.

2. The router of claim 1 wherein the buffer subsystem includes multiple storage locations and links available storage locations in a free queue.

3. The router of claim 2 wherein the buffer subsystem includes a processor that determines:

i. a new weighted average depth for the free queue, and

ii. a probability of discard for a given packet if the new weighted average queue depth falls below a predetermined maximum threshold associated with the class of service to which the packet is assigned by the classifier.

4. The router of claim 3 wherein the buffer subsystem discards a given packet if the associated new weighted average depth for the free queue falls below a minimum threshold associated with the class of service to which the packet is assigned.

5. The router of claim 4 wherein the buffer subsystem processor calculates the probability of discard as P_d=c−

(m*A_NEW) where c is an intercept and m is a slope that is associated with a line that plots average free queue depth versus probability of discard for the class of service to which the packet is assigned, and A_NEW is the new weighted average depth of the free queue.

6. The router of claim 5 wherein the buffer subsystem processor calculates the new weighted average depth of the free queue as A_NEW=A_CURRENT+w(I−

A_CURRENT) where w is a weighting factor, I represents the instantaneous depth of the free queue and A_CURRENT is the current weighted average depth of the free queue.

7. The router of claim 1 wherein the scheduler selects from the buffer subsystem packets for transfer based on weighting factors associated with the respective X classes of service.

8. A router for use in routing packets over a network, the router supporting a plurality, X, of classes of service and including:

A. a plurality of input ports configured to receive packets over the network;

B. a plurality of output ports configured to transfer packets over the network;

C. a multiple storage location buffer configured to retain packets to be transferred through the output ports;

D. a buffer subsystem configured to retain the packets in class of service per output port queues based on probabilities of discard associated with X*Y classes of service, where Y represents a number and * represents multiplication; and

E. a scheduler configured to transfer the packets from the buffer subsystem through each of the output ports based on the X classes of service that the router supports.

9. The router of claim 8 further including a classifiers configured to:

i. assign packets received by the input ports to X*Y classes of service,

ii. associate the packets with the X classes of service that are supported by the router, and

iii. assign to the packet one of Y associated levels of priority, wherein each level of priority is associated with a different probability of packet loss.

10. The router of claim 8 wherein the buffer subsystem includes a processor that determines

i. a new weighted average queue depth for a free queue that links available buffer storage locations, and

ii. a probability of discard for a given packet if the new weighted average free queue depth falls below a predetermined maximum threshold associated with the class of service to which the packet is assigned.

11. The router of claim 10 wherein the buffer subsystem processor calculates the probability of discard as P_d=c−

(m*A_NEW) where c is an intercept and m is a slope that are associated with a line that plots average free queue depth versus probability of discard for the class of service to which the packet is assigned, and A_NEW is the new weighted average depth of the free queue.

12. The router of claim 11 wherein the buffer subsystem processor calculates the new depth of the weighted average free queue as A_NEW=A_CURRENT+w(I−

A_CURRENT) where w is a weighting factor, I represents the instantaneous depth of the free queue and A_CURRENT is the current weighted average depth of the free queue.

13. The router of claim 11 wherein the buffer subsystem discards a given packet if the new weighted average free queue depth falls below a minimum threshold associated with the class of service to which the packet is assigned.

14. The router of claim 11 wherein the buffer subsystem retains a given packet if the new weighted average free queue depth is above a maximum threshold associated with the class of service to which the packet is assigned.

15. The router of claim 8 wherein the scheduler selects packets for transfer through each of the output ports on weighting factors associated with the respective X classes of service.

16. An apparatus for routing packets through a router that supports a plurality, X, of classes of service, the apparatus comprising:

means for receiving packets;

means for assigning the packets to X*Y classes of service, where Y represents a number and * represents multiplication;

means for retaining packets based on probabilities of discard associated with the X*Y classes of service; and

means for transferring the packets based on the X classes of service.

17. The apparatus of claim 16, further including:

means for associating packets assigned to the X*Y classes of service with the X classes of service supported by the apparatus; and

means for assigning to the respective packets one of Y associated levels of priority, each level of priority being associated with a different probability of packet loss.

18. The apparatus of claim 17, further comprising:

means for determining a new weighted average depth for the free queue; and

means for determining a probability of discard for a given packet if the new weighted average free queue depth falls below a predetermined maximum threshold associated with the class of service to which the packet is assigned.

19. The apparatus of claim 18, wherein the means for retaining packets further comprises:

means for discarding a given packet if the new weighted average free queue depth is less than a minimum threshold associated with the class of service to which the packet is assigned.

20. The apparatus of claim 18, wherein the means for retaining packets further comprises:

means for retaining a given packet if the new weighted average free queue depth is greater than a maximum threshold associated with the class of service to which the packet is assigned.

21. A computer-readable media, comprising:

instructions for execution in a processor for the practice of a method, said method having the steps,

receiving packets through one or more input ports and assigning the packets to X*Y classes of service, where * represents multiplication, X represents a number of classes of service and Y represents a number,

retaining packets based on probabilities of discard associated with the X*Y classes of service in a multiple storage location buffer that links available storage locations to a free queue; and

transferring the packets through one or more output ports based on the X classes of service.

22. The computer-readable media of claim 21, wherein the method further comprises the steps of:

associating packets assigned to the X*Y classes of service with the X classes of service; and

assigning to the respective packets one of Y associated levels of priority, each level of priority being associated with a different probability of packet loss.

23. The computer-readable media of claim 22, wherein the method further comprises the steps of:

determining a new weighted average depth for the free queue; and

determining a probability of discard for a given packet if the new weighted average free queue depth falls below a predetermined maximum threshold associated with the class of service to which the packet is assigned.

24. The computer-readable media of claim 23, wherein the method further comprises the step of:

discarding a given packet if the new weighted average free queue depth is less than a minimum threshold associated with the class of service to which the packet is assigned.

25. The computer-readable media of claim 23, wherein the method further comprises the step of:

retaining a given packet if the new weighted average free queue depth is greater than a maximum threshold associated with the class of service to which the packet is assigned.

26. A router for use in routing packets over a network, the router supporting a first number of classes of service, the router comprising:

a port to receive packets, each packet having a field that indicates one of a second number of classes of service, the second number of classes of service greater than the first number of classes of service;

a classifier configured map the one of the second number of classes of service indicated by the field of each packet to one of the first number of classes of service and to a particular loss priority value for the packet; and

a processor configured to discard selected packets in response to the one of the first number of classes of service and the loss priority value for each packet, to thereby approximate the second number of classes of service.

27. The router of claim 26 wherein the router discards selected packets based upon a probability of discard for each packet, and wherein the probability of discard of each packet substantially corresponds to the probability of discard specified by the one of the second number of classes of service indicated by the field of the packet.

28. The router of claim 26 wherein the processor is configured to organize all the packets into a single queue containing packets for all classes of service.

29. The router of claim 28 wherein the processor is configured to determine a weighted average depth of the queue, and is configured to determine a probability of discard of each packet if the weighted average depth of the queue passes a predetermined threshold.

30. The router of claim 29 wherein the probability of discard of each packet is a linear function of queue depth, the linear function having a slope value and an intercept value selected based upon the one of the first number of classes of service and the particular loss priority value of the packet.

31. The router of claim 26 wherein the first number of classes of service equals 2ⁿ and the second number of classes of service equals 2^n+m, where n and m are positive integers.

32. A method for routing packets over a network with a router supporting a first number of classes of service, the method comprising the steps of:

receiving packets, each packet having a field that indicates one of a second number of classes of service, the second number of classes of service greater than the first number of classes of service;

mapping the one of the second number of classes of service indicated by the field of each packet to one of the first number of classes of service and to a particular loss priority value for the packet; and

discarding selected packets in response to the one of the first number of classes of service and the loss priority value of each packet, to thereby approximate the second number of classes of service.

33. The method of claim 32 wherein the step of discarding further comprises the step of:

choosing selected packets based upon a probability of discard for each packet, the probability of discard of each packet substantially corresponding to a probability of discard specified by the one of the second number of classes of service indicated by the field of packet.

34. The method of claim 32 further comprising the step of:

organizing the packets into a single queue containing packets for all classes of service.

35. The method of claim 34 wherein the step of discarding further comprising the step of:

determining a weighted average depth of the queue to determine, and if the weighted average depth of the queue passes a predetermined threshold, determining a probably of discard for each packet.

36. The method of claim 35 wherein the probability of discard of each packet is a linear function of queue depth, the linear function having a slope value and an intercept value selected based upon the one of the first number of classes of service and the particular loss priority value of the packet.

37. The method of claim 32 wherein the first number of classes of service equals 2ⁿ and the second number of classes of service equals 2^n+m, where n and m are positive integers.

38. A computer readable medium containing executable program instructions for routing packets over a network with a router supporting a first number of classes of service, the executable program instructions comprising program instructions adapted to:

receive packets, each packet having a field that indicates one of a second number of classes of service, the second number of classes of service greater than the first number of classes of service;

map the one of the second number of classes of service indicated by the field of each packet to one of the first number of classes of service and to a particular loss priority value for the packet; and

discard selected packets in response to the one of the first number of classes of service and the particular loss priority value for each packet, to thereby approximate the second number of classes of service.