Technique for supporting tiers of traffic priority levels in a packet-switched network

• US 6,546,017 B1
• Filed: 03/05/1999
• Issued: 04/08/2003
• Est. Priority Date: 03/05/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Khaunte, Sunil
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/263,147
• Time in Patent Office: 1,495 Days
• Field of Search: 375/222, 370/282, 370/351, 370/389, 370/395.1, 370/395.2, 370/395.21, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/395.52, 370/442, 370/458, 370/463, 370/468, 370/469, 370/480, 370/412-418
• US Class Current: 370/412
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/821 Prioritising resource allocation or reservation requests

Abstract

The technique of the present invention provides a simple and efficient solution to the problem of supporting differentiated priority levels within a QoS service class within a packet-switched network. When a bandwidth request is received at the cable modem head end, the service ID of that particular cable modem is identified. From this service ID, the associated static priority value of the requesting modem'"'"'s service class is determined. The grant scheduler at the CMTS maintains a single queuing structure to temporarily store all differentiated priority bandwidth requests associated with a particular class of service that are received from cable modems on a selected channel. The technique of the present invention implements a procedure to calculate a metric used in determining a queuing priority for each received bandwidth request so that a single priority queuing structure may be used for this purpose. The metric is calculated by subtracting a product of the static priority value from the arrival time value of an associated bandwidth request. Use of the static service class priority in the queuing priority metric helps the grant scheduler to prioritize bandwidth requests from high priority modems over requests from low priority modems in the same queuing structure. Use of the arrival time in the metric enables an implicit fairness feature in the traffic prioritization to prevent starvation of low priority traffic.

Claims

1. A method for handling traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the method comprising:

(a) receiving at a first arrival time (T1), a first bandwidth request, said first bandwidth request being associated with a first priority class of service (PCM1);

(b) receiving at a second arrival time (T2), a second bandwidth request, said second bandwidth request being associated with a second priority class of service (PCM2);

(c) calculating a respective priority index value for each received bandwidth request, said priority index value being a function of a difference between the arrival time and priority class of each respective bandwidth request; and

(d) enqueuing said first and second bandwidth requests within a common data structure in an order based upon the priority index value of each respective bandwidth request.

2. The method of claim 1 further including servicing queued bandwidth requests within said data structure in an order based upon said priority index values.

3. The method of claim 1 wherein said first priority class and said second priority class each correspond to different levels of priority within a tiered best-effort service class.

4. The method of claim 1 further including:

identifying a respective priority class of service value (P_CM) and respective arrival time (T) for each received bandwidth request; and

determining said respective priority index value for each received bandwidth request by calculating a difference between a product of said P_CM value and said T value.

5. The method of claim 1 further including:

assigning to said first bandwidth request a first priority index (P1_index) within said data structure, said first priority index value being a function of said first arrival time and said first priority class; and

assigning to said second bandwidth request a second priority index (P2_index) within said data structure, said second priority index value being a function of said second arrival time and said second priority class.

6. The method of claim 5 further including servicing queued bandwidth requests within said data structure such that bandwidth requests having relatively lower priority index values are serviced before bandwidth requests having relatively higher priority index values.

7. The method of claim 5 further including:

calculating said first priority index according to;

P1_index=T₁−

(P_CM1*PRIORITY_WEIGHT); and

calculating said second priority index according to;

P2_index=T₂−

(P_CM2*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.

8. The method of claim 5, wherein said first priority class (P_CM1) has a first numeric value associated therewith, said method including calculating the first priority index value by subtracting a product of said P_CM1 value from said T₁ value.

9. The method of claim 8, wherein said second priority class (P_CM2) has a second numeric value associated therewith, said method including calculating the second priority index value by subtracting a product of said P_CM2 value from the T₂ value.

10. A method for handling traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the method comprising:

(a) receiving at a first arrival time (T1), a first packet, said first packet being associated with a first priority class of service (PP1);

(b) receiving at a second arrival time (T2), a second packet, said second packet being associated with a second priority class of service (PP2);

(c) calculating a respective priority index value for each received packet, said priority index value being a function of a difference between the arrival time and priority class of each respective packet;

(d) enqueuing said first and second packets within a common data structure in an order based upon the priority index value of each respective packet; and

(e) servicing queued packets within said data structure in an order based upon said priority index values.

11. The method of claim 10 wherein said first priority class and said second priority class each correspond to different levels of priority within a tiered best-effort service class.

12. The method of claim 10 further including:

identifying a respective priority class of service value (P_P) and respective arrival time (T) for each received packet; and

determining said respective priority index value for each received packet by by calculating a difference between a product of said P_P value and said T value.

13. The method of claim 10 further including:

assigning to said first packet a first priority index (P1_index) within said data structure, said first priority index value being a function of said first arrival time and said first priority class; and

assigning to said second packet a second priority index (P2_index) within said data structure, said second priority index value being a function of said second arrival time and said second priority class.

14. The method of claim 13 further including servicing queued packets within said data structure such that packets having relatively lower priority index values are serviced before packets having relatively higher priority index values.

15. The method of claim 13 further including:

calculating said first priority index according to;

P1_index=T₁−

(P_P1*PRIORITY_WEIGHT); and

calculating said second priority index according to;

P2_index=T₂−

(P_P2*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.

16. The method of claim 13, wherein said first priority class (P_P1) has a first numeric value associated therewith, said method including calculating the first priority index value by subtracting a product of said P_P1 value from the T₁ value.

17. The method of claim 16, wherein said second priority class (P_P2) has a second numeric value associated therewith, said method including calculating the second priority index value by subtracting a product of said P_P2 value from the T₂ value.

18. A method for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes, the method comprising:

(a) receiving a packet at an arrival time (T), said packet being associated with one of a plurality of different priority classes of service, said one priority class (P_P) having a numeric value associated therewith;

(b) assigning a respective priority index value to said received packet, wherein said priority index value is determined by calculating a difference between a product of said P_P value and said T value; and

(c) enqueuing said received packet within a sorted data structure in an order based upon its priority index value.

19. The method of claim 18 further including servicing queued packets within said data structure in an order based upon the respective priority index value of each queued packet.

20. The method of claim 18 wherein said priority index value (P_index) is calculated according to:

P_index=T−

(P_P*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.

21. The method of claim 18 further including determining said P_P value by referencing a Type of Service (ToS) field in said packet.

22. A computer program product for handling traffic in a packet-switched integrated services network which supports a plurality of different service classes, the computer program product comprising:

at least one computer usable medium having computer readable code embodied therein, the computer readable code comprising;

computer code for determining an arrival time (T) and a service class priority value (P_P) associated with a received packet;

computer code for assigning a respective priority index value (P_index) to said received packet, wherein said priority index value is calculated by subtracting a product of said P_P value from said T value; and

computer code for enqueuing said received packet within a sorted data structure in an order based upon said P_index value.

23. The computer program product of claim 22 further including computer code for servicing queued packets within said data structure in an order based upon the respective priority index value of each queued packet.

24. The computer program product of claim 22 further including computer code for calculating said priority index value (P_index) according to:

P_index=T−

(P_P*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.

25. The computer program product of claim 22 further including computer code for determining said P_P value by referencing a Type of Service (ToS) field in said packet.

26. The computer program product of claim 22 further including:

computer code for determining an arrival time (T2) and a service class priority value (P2_P) associated with a second received packet, wherein said P2_P value is different than said P_P value;

computer code for assigning a second priority index value (P2_index) to said second received packet, wherein said second priority index value is calculated by subtracting a product of said P2_P value from said T2 value; and

computer code for enqueuing said second received packet within said sorted data structure in an order based upon said P2_index value.

27. A router for handling traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the router comprising:

means for determining an arrival time (T) and a service class priority value (P_P) associated with a received packet;

means for assigning a respective priority index value (P_index) to said received packet, wherein said priority index value is determined by calculating a difference between a product of said P_P value and said T value; and

means for enqueuing said received packet within a sorted data structure in an order based upon said P_index value.

28. The router of claim 27 further including means for servicing queued packets within said data structure in an order based upon the respective priority index value of each queued packet.

29. The router of claim 27 further including means for calculating said priority index value (P_index) according to:

P_index=T−

(P_P*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.

30. The router of claim 27 further including means for determining said P_P value by referencing a Type of Service (ToS) field in said packet.

31. The router of claim 27 further including:

means for determining an arrival time (T2) and a service class priority value (P2_P) associated with a second received packet, wherein said P2_P value is different than said P_P value;

means for assigning a second priority index value (P2_index) to said second received packet, wherein said second priority index value is calculated by subtracting a product of said P2_P value from said T2 value; and

means for enqueuing said second received packet within said sorted data structure in an order based upon said P2_index value.

32. The router of claim 31 wherein said P_P priority class and said P2_P priority class correspond to different levels of priority within a tiered best-effort service class.

33. A Cable Modem Termination System (CTMS) in a cable modem network for handling traffic in a packet-switched, integrated services network which supports a plurality of different service classes, the system comprising:

means for determining an arrival time (T) and a service class priority value (P_CM) associated with a received bandwidth request;

means for assigning a respective priority index value (P_index) to said received bandwidth request, wherein said priority index value is determined by calculating a difference between a product of said P_CM value and said T value; and

means for enqueuing said received bandwidth request within a sorted data structure in an order based upon said P_index value.

34. The system of claim 33 further including means for servicing queued bandwidth requests within said data structure in an order based upon the respective priority index value of each queued bandwidth request.

35. The system of claim 33 further including means for calculating said priority index value (P_index) according to:

P_index=T−

(P_CM*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.

36. The system of claim 33 further including means for determining said P_CM value by identifying a service ID of a cable modem which issued said bandwidth request.

37. The system of claim 33 further including:

means for determining an arrival time (T2) and a service class priority value (P2_CM) associated with a second received bandwidth request, wherein said P2_CM value is different than said P_CM value;

means for assigning a second priority index value (P2_index) to said second received bandwidth request, wherein said second priority index value is calculated by subtracting a product of said P2_CM value from said T2 value; and

means for enqueuing said second received bandwidth request within said sorted data structure in an order based upon said P2_index value.

38. The system of claim 37 wherein said P_CM priority class and said P2_CM priority class correspond to different levels of priority within a tiered best-effort service class.