Patent US6546017B1 successfully refreshed from Google Patents.
US6546017B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technique for supporting tiers of traffic priority levels in a packet-switched network
Assignee: Cisco Technology Inc
•
Filing: 1999-03-05
•
Granted: 2003-04-08
•
Expires: 2019-03-05
Abstract
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.
Inventors
- 👤 Sunil Khaunte
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 11:08
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/70; H04L47/80; H04L47/805; H04L47/10; H04L47/15; H04L47/24; H04L47/2425; H04L47/2433; H04L47/82; H04L47/821
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
144 words
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 (T 1 ), a first bandwidth request, said first bandwidth request being associated with a first priority class of service (PCM 1 ); (b) receiving at a second arrival time (T 2 ), a second bandwidth request, said second bandwidth request being associated with a second priority class of service (PCM 2 ); (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.
Claim 2
Independent Claim
144 words
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 (T 1 ), a first bandwidth request, said first bandwidth request being associated with a first priority class of service (PCM 1 ); (b) receiving at a second arrival time (T 2 ), a second bandwidth request, said second bandwidth request being associated with a second priority class of service (PCM 2 ); (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.
Claim 3
Dependent Claim
24 words
The method of claim 1 further including servicing queued bandwidth requests within said data structure in an order based upon said priority index values.
Claim 4
Dependent Claim
28 words
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.
Claim 5
Dependent Claim
56 words
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.
Claim 6
Dependent Claim
80 words
The method of claim 1 further including: assigning to said first bandwidth request a first priority index (P 1 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 (P 2 index ) within said data structure, said second priority index value being a function of said second arrival time and said second priority class.
Claim 7
Dependent Claim
36 words
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.
Claim 8
Dependent Claim
46 words
The method of claim 5 further including: calculating said first priority index according to: P 1 index =T 1 −(P CM1 *PRIORITY_WEIGHT); and calculating said second priority index according to: P 2 index =T 2 −(P CM2 *PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.
Claim 9
Dependent Claim
44 words
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 1 value.
Claim 10
Dependent Claim
44 words
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 2 value.
Claim 11
Independent Claim
153 words
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 (T 1 ), a first packet, said first packet being associated with a first priority class of service (PP 1 ); (b) receiving at a second arrival time (T 2 ), a second packet, said second packet being associated with a second priority class of service (PP 2 ); (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.
Claim 12
Independent Claim
153 words
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 (T 1 ), a first packet, said first packet being associated with a first priority class of service (PP 1 ); (b) receiving at a second arrival time (T 2 ), a second packet, said second packet being associated with a second priority class of service (PP 2 ); (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.
Claim 13
Dependent Claim
28 words
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.
Claim 14
Dependent Claim
55 words
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.
Claim 15
Dependent Claim
78 words
The method of claim 10 further including: assigning to said first packet a first priority index (P 1 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 (P 2 index ) within said data structure, said second priority index value being a function of said second arrival time and said second priority class.
Claim 16
Dependent Claim
33 words
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.
Claim 17
Dependent Claim
46 words
The method of claim 13 further including: calculating said first priority index according to: P 1 index =T 1 −(P P1 *PRIORITY_WEIGHT); and calculating said second priority index according to: P 2 index =T 2 −(P P2 *PRIORITY_WEIGHT), wherein said PRIORITY_WEIGHT value is a predetermined constant.
Claim 18
Dependent Claim
44 words
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 1 value.
Claim 19
Dependent Claim
44 words
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 2 value.
Claim 20
Independent Claim
113 words
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.
Claim 21
Independent Claim
113 words
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.
Claim 22
Dependent Claim
28 words
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.
Claim 23
Dependent Claim
30 words
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.
Claim 24
Dependent Claim
23 words
The method of claim 18 further including determining said P P value by referencing a Type of Service (ToS) field in said packet.
Claim 25
Dependent Claim
123 words
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.
Claim 26
Dependent Claim
123 words
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.
Claim 27
Dependent Claim
33 words
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.
Claim 28
Dependent Claim
35 words
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.
Claim 29
Dependent Claim
28 words
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.
Claim 30
Dependent Claim
113 words
The computer program product of claim 22 further including: computer code for determining an arrival time (T 2 ) and a service class priority value (P 2 P ) associated with a second received packet, wherein said P 2 P value is different than said P P value; computer code for assigning a second priority index value (P 2 index ) to said second received packet, wherein said second priority index value is calculated by subtracting a product of said P 2 P value from said T 2 value; and computer code for enqueuing said second received packet within said sorted data structure in an order based upon said P 2 index value.
Claim 31
Dependent Claim
102 words
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.
Claim 32
Dependent Claim
102 words
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.
Claim 33
Dependent Claim
30 words
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.
Claim 34
Dependent Claim
32 words
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.
Claim 35
Dependent Claim
25 words
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.
Claim 36
Dependent Claim
108 words
The router of claim 27 further including: means for determining an arrival time (T 2 ) and a service class priority value (P 2 P ) associated with a second received packet, wherein said P 2 P value is different than said P P value; means for assigning a second priority index value (P 2 index ) to said second received packet, wherein said second priority index value is calculated by subtracting a product of said P 2 P value from said T 2 value; and means for enqueuing said second received packet within said sorted data structure in an order based upon said P 2 index value.
Claim 37
Dependent Claim
30 words
The router of claim 31 wherein said P P priority class and said P 2 P priority class correspond to different levels of priority within a tiered best-effort service class.
Claim 38
Dependent Claim
114 words
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.
Claim 39
Dependent Claim
114 words
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.
Claim 40
Dependent Claim
32 words
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.
Claim 41
Dependent Claim
32 words
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.
Claim 42
Dependent Claim
28 words
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.
Claim 43
Dependent Claim
111 words
The system of claim 33 further including: means for determining an arrival time (T 2 ) and a service class priority value (P 2 CM ) associated with a second received bandwidth request, wherein said P 2 CM value is different than said P CM value; means for assigning a second priority index value (P 2 index ) to said second received bandwidth request, wherein said second priority index value is calculated by subtracting a product of said P 2 CM value from said T 2 value; and means for enqueuing said second received bandwidth request within said sorted data structure in an order based upon said P 2 index value.
Claim 44
Dependent Claim
30 words
The system of claim 37 wherein said P CM priority class and said P 2 CM priority class correspond to different levels of priority within a tiered best-effort service class.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-04-07 | 2006-10-07 | 2007-04-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-04-07 | 2010-10-07 | 2011-04-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-04-07 | 2014-10-07 | 2015-04-08 | $7700.00 | Window Closed / Lapsed |