Technique for supporting tiers of traffic priority levels in a packet-switched network
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
273 Citations
38 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
identifying a respective priority class of service value (PCM) 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 PCM value and said T value.
-
-
5. The method of claim 1 further including:
-
assigning to said first bandwidth request a first priority index (P1index) 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 (P2index) 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;
P1index=T1−
(PCM1*PRIORITY_WEIGHT); and
calculating said second priority index according to;
P2index=T2−
(PCM2*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.
-
-
8. The method of claim 5, wherein said first priority class (PCM1) has a first numeric value associated therewith, said method including calculating the first priority index value by subtracting a product of said PCM1 value from said T1 value.
-
9. The method of claim 8, wherein said second priority class (PCM2) has a second numeric value associated therewith, said method including calculating the second priority index value by subtracting a product of said PCM2 value from the T2 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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
identifying a respective priority class of service value (PP) 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 PP value and said T value.
-
-
13. The method of claim 10 further including:
-
assigning to said first packet a first priority index (P1index) 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 (P2index) 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;
P1index=T1−
(PP1*PRIORITY_WEIGHT); and
calculating said second priority index according to;
P2index=T2−
(PP2*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.
-
-
16. The method of claim 13, wherein said first priority class (PP1) has a first numeric value associated therewith, said method including calculating the first priority index value by subtracting a product of said PP1 value from the T1 value.
-
17. The method of claim 16, wherein said second priority class (PP2) has a second numeric value associated therewith, said method including calculating the second priority index value by subtracting a product of said PP2 value from the T2 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 (PP) 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 PP 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. - View Dependent Claims (19, 20, 21)
-
-
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 (PP) associated with a received packet;
computer code for assigning a respective priority index value (Pindex) to said received packet, wherein said priority index value is calculated by subtracting a product of said PP value from said T value; and
computer code for enqueuing said received packet within a sorted data structure in an order based upon said Pindex value. - View Dependent Claims (23, 24, 25, 26)
Pindex=T−
(PP*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 PP 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 (P2P) associated with a second received packet, wherein said P2P value is different than said PP value;
computer code for assigning a second priority index value (P2index) to said second received packet, wherein said second priority index value is calculated by subtracting a product of said P2P 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 P2index 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 (PP) associated with a received packet;
means for assigning a respective priority index value (Pindex) to said received packet, wherein said priority index value is determined by calculating a difference between a product of said PP value and said T value; and
means for enqueuing said received packet within a sorted data structure in an order based upon said Pindex value. - View Dependent Claims (28, 29, 30, 31, 32)
Pindex=T−
(PP*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.
-
-
30. The router of claim 27 further including means for determining said PP 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 (P2P) associated with a second received packet, wherein said P2P value is different than said PP value;
means for assigning a second priority index value (P2index) to said second received packet, wherein said second priority index value is calculated by subtracting a product of said P2P value from said T2 value; and
means for enqueuing said second received packet within said sorted data structure in an order based upon said P2index value.
-
-
32. The router of claim 31 wherein said PP priority class and said P2P 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 (PCM) associated with a received bandwidth request;
means for assigning a respective priority index value (Pindex) to said received bandwidth request, wherein said priority index value is determined by calculating a difference between a product of said PCM value and said T value; and
means for enqueuing said received bandwidth request within a sorted data structure in an order based upon said Pindex value. - View Dependent Claims (34, 35, 36, 37, 38)
Pindex=T−
(PCM*PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.
-
-
36. The system of claim 33 further including means for determining said PCM 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 (P2CM) associated with a second received bandwidth request, wherein said P2CM value is different than said PCM value;
means for assigning a second priority index value (P2index) to said second received bandwidth request, wherein said second priority index value is calculated by subtracting a product of said P2CM 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 P2index value.
-
-
38. The system of claim 37 wherein said PCM priority class and said P2CM priority class correspond to different levels of priority within a tiered best-effort service class.
Specification