US6353616B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive processor schedulor and method for reservation protocol message processing
Assignee: Nokia of America Corp
•
Filing: 1998-12-28
•
Granted: 2002-03-05
•
Expires: 2018-12-28
Abstract
Abstract A packet network employing a reservation-based protocol system includes routers having processing sections that schedule message processing of the protocol's control messages adaptively based on link utilization. A scheduler of the processing section employs a round-robin scheduling with adaptive weight assignment to allocate processing capacity for control messages. For the RSVP protocol, for example, messages are grouped in classes, and link utilization of the packet flows for each message class is monitored. Weights corresponding to a portion of the processing section's processing capacity are allocated to each message class. The weights are defined based on link utilization for the message class and average message queue length. For processing sections monitoring multiple links, weights are further defined for super-classes based on overall link utilization. Weights may change as link utilization and average message size changes. With defined weights adaptively defined, the processing section then processes each message class in a cyclic, “round-robin” fashion.
Inventors
- 👤 Anwar I. Elwalid
- 👤 T. V. Lakshman
- 👤 Martin May
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 15:53
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/24; H04L47/2408; H04L47/70
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
100 words
A processing section of a router for processing control messages in a packet network, the processing section comprising: a monitoring module adapted to monitor a link utilization value of a link coupled to the router; a processor to calculate a message request size and a corresponding weight for at least one class of control messages, each weight calculated based on the link utilization value and each message request size; and a scheduling module adapted to allocate, for each class of control messages, a portion of the processing capacity of the processing section based on the corresponding weight of the class.
Claim 2
Dependent Claim
100 words
A processing section of a router for processing control messages in a packet network, the processing section comprising: a monitoring module adapted to monitor a link utilization value of a link coupled to the router; a processor to calculate a message request size and a corresponding weight for at least one class of control messages, each weight calculated based on the link utilization value and each message request size; and a scheduling module adapted to allocate, for each class of control messages, a portion of the processing capacity of the processing section based on the corresponding weight of the class.
Claim 3
Dependent Claim
55 words
The invention as recited in claim 1 , wherein the control messages further include an update message class of control messages for maintaining at least one established packet flow of the link, and the processor further calculates the weight for the update message class based on the number of established packet flows of the link.
Claim 4
Dependent Claim
57 words
The invention as recited in claim 2 , wherein the control messages are in accordance with a reservation-based protocol, and the control messages include a first class of control messages for establishing at least one packet flow of the link and a second class of control messages for terminating at least one packet flow of the link.
Claim 5
Dependent Claim
27 words
The invention as recited in claim 2 , wherein the message request size is based on an average of a requested link characteristic of the control messages.
Claim 6
Dependent Claim
27 words
The invention as recited in claim 4 , wherein the requested link characteristic of the control messages is either bandwidth, transmission delay, or probability of lost packet.
Claim 7
Dependent Claim
113 words
The invention as recited in claim 1 , wherein: the monitoring module further monitors link utilization values for two or more links coupled to the router; the processor further calculates, for each link, a message request size and corresponding weight for each class of control messages based on the link utilization of the link, the processor further adapted to calculate a super-class weight for each link; and the scheduling module allocates the processing capacity of the processing section to each link based on the corresponding super-class weight, and allocates a portion of the processing capacity allocated to the link to each class of the link based on the corresponding weight of the class.
Claim 8
Independent Claim
94 words
A method for allocating processing capacity to control messages received by a router in a packet network, the method comprising the steps of: a) monitoring a link utilization value of a link coupled to the router; b) calculating a message request size and a corresponding weight for at least one class of control messages, each weight calculated based on the link utilization value and each message request size; and c) allocating, for each class of control messages, a portion of the processing capacity of the router based on the corresponding weight of the class.
Claim 9
Independent Claim
94 words
A method for allocating processing capacity to control messages received by a router in a packet network, the method comprising the steps of: a) monitoring a link utilization value of a link coupled to the router; b) calculating a message request size and a corresponding weight for at least one class of control messages, each weight calculated based on the link utilization value and each message request size; and c) allocating, for each class of control messages, a portion of the processing capacity of the router based on the corresponding weight of the class.
Claim 10
Dependent Claim
62 words
The method as recited in claim 7 , wherein the control messages further include an update message class of control messages for maintaining at least one established packet flow of the link, and the calculating step b) further includes the step of b1) calculating the weight for the update message class based on the number of established packet flows of the link.
Claim 11
Dependent Claim
62 words
The method as recited in claim 8 , wherein, for the calculating step b), the control messages are in accordance with a reservation-based protocol, and the control messages include a first class of control messages for establishing at least one packet flow of the link and a second class of control messages for terminating at least one packet flow of the link.
Claim 12
Dependent Claim
36 words
The method as recited in claim 8 , wherein, for the calculating step b), the message request size of a class is calculated based on an average of a requested link characteristic of the control messages.
Claim 13
Dependent Claim
28 words
The method as recited in claim 10 , wherein, for the calculating step b), the requested link characteristic is either bandwidth, transmission delay, or probability of lost packet.
Claim 14
Dependent Claim
127 words
The method as recited in claim 7 , wherein: the monitoring step a) further includes the step of a1) monitoring link utilization values for two or more links coupled to the router; the calculating step b) further includes the steps of b2) calculating, for each link, a message request size and corresponding weight for each class of control messages based on the link utilization of the link, and b3) calculating a super-class weight for each link; and the allocating step c) further includes the step of c1) allocating the processing capacity to each link based on the corresponding super-class weight, and c2) allocating a portion of the processing capacity allocated to the link to each class of the link based on the corresponding weight of the class.
Claim 15
Dependent Claim
108 words
A router of an IP packet network having a processing section for processing control messages in accordance with a reservation-based protocol, the processing section comprising: a monitoring module adapted to monitor a link utilization value of a link coupled to the router; a processor adapted to calculate a message request size and a corresponding weight for at least one class of control messages, each weight calculated based on the link utilization value and each message request size; and a scheduling module adapted to allocate, for each class of control messages, a portion of the processing capacity of the processing section based on the corresponding weight of the class.
Claim 16
Dependent Claim
108 words
A router of an IP packet network having a processing section for processing control messages in accordance with a reservation-based protocol, the processing section comprising: a monitoring module adapted to monitor a link utilization value of a link coupled to the router; a processor adapted to calculate a message request size and a corresponding weight for at least one class of control messages, each weight calculated based on the link utilization value and each message request size; and a scheduling module adapted to allocate, for each class of control messages, a portion of the processing capacity of the processing section based on the corresponding weight of the class.
Claim 17
Dependent Claim
55 words
The invention as recited in claim 13 , wherein the control messages further include an update message class of control messages for maintaining at least one established packet flow of the link, and the processor further calculates the weight for the update message class based on the number of established packet flows of the link.
Claim 18
Dependent Claim
113 words
The invention as recited in claim 14 , wherein: the monitoring module further monitors link utilization values for two or more links coupled to the router; the processor further calculates, for each link, a message request size and corresponding weight for each class of control messages based on the link utilization of the link, the processor further adapted to calculate a super-class weight for each link; and the scheduling module allocates the processing capacity of the processing section to each link based on the corresponding super-class weight, and allocates a portion of the processing capacity allocated to the link to each class of the link based on the corresponding weight of the 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) | 2005-03-04 | 2005-09-03 | 2006-03-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-03-04 | 2009-09-03 | 2010-03-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-03-04 | 2013-09-03 | 2014-03-05 | $7700.00 | Window Closed / Lapsed |