Adaptive processor schedulor and method for reservation protocol message processing

• US 6,353,616 B1
• Filed: 12/28/1998
• Issued: 03/05/2002
• Est. Priority Date: 05/21/1998
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Elwalid, Anwar I., May, Martin, Lakshman, T. V.
• Primary Examiner(s): Zimmerman, Brian A.
• Application Number:
  US09/221,552
• Time in Patent Office: 1,163 Days
• Field of Search: 370/443, 370/522, 370/412, 370/468, 370/428, 370/429, 370/389, 370/395.2, 709/103, 709/104, 709/105, 709/226, 709/241
• US Class Current: 370/443
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.