Programmable scheduling for IP routers

• US 7,023,843 B2
• Filed: 06/26/2002
• Issued: 04/04/2006
• Est. Priority Date: 06/26/2002
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: Lakkakorpi, Jani, Ruutu, Jussi, Raisanen, Vilho I.
• Primary Examiner(s): Nguyen, Hanh
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US10/183,057
• Publication Number:
  US 20040001491A1
• Time in Patent Office: 1,378 Days
• Field of Search: 370/229, 370/230.1, 370231-235, 370/254, 370/351, 370/352, 370/389, 370/395.41, 370/400, 370/401, 370/412, 370/413, 370/414, 370/428, 370/429, 370/388
• US Class Current: 370/388
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/2491 Mapping quality of service [QoS] requirements between different networks
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/60 implementing hierarchical scheduling
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

A scheduling system for IP routers is provided. A programmable scheduler for IP routers can support single stage and multistage scheduling. This allows flexible combinations of scheduling and widens dramatically the available QoS solutions to operators. With this kind of scheduling the router can be configured to support almost any known scheduling method or combination. Priority Queuing (PQ) and Deficit Round Robin (DRR) scheduling is scheduling is used according to one embodiment of the invention.

Claims

1. An apparatus for a programmable scheduler that can support single stage and multi-stage scheduling, comprising:

an interface arrangement configured to receive and output packets;

a routing core coupled to the interface arrangement that is configured to provide routing and switching functionality relating to the packets; and

a scheduling configuration interface coupled to the routing core and the interface arrangement, and arranged to provide a scheduling configuration, wherein the scheduling configuration interface may be programmed to implement an scheduling algorithms;

the interface arrangement is configured to output packets according to the scheduling configuration;

the scheduling configuration interface that may be programmed to implement the scheduling algorithms, further comprises programming the scheduling algorithms dynamically;

scheduling parameters are provided to the scheduling configuration interface that are used to determine the scheduling configuration; and

wherein the scheduling parameters define a number and relative positions of scheduling stages, a scheduling method applied by the scheduling stages, parameters for the scheduling method and a position of queues in a scheduling hierarchy.

2. A system for a programmable scheduler relating to IP routers, comprising:

nodes, wherein a node in the nodes include a network interface unit arranged to communicate packets across a network; and

a router;

wherein the router includes;

a network interface unit ananged to receive the packets and transmit packets to the nodes;

a scheduling configuration interface configured to receive parameters relating to a scheduling method wherein the parameters received by the scheduling configuration interface further comprise the number and relative positions of scheduling stages;

a programmable scheduling component configured to implement a one stage scheduling method and a multi-stage scheduling method in response to the parameters received by the scheduling configuration interface, wherein the programmable scheduling component may be re-configured dynamically; and

an output ranged to output packets such that the scheduling method is followed.

3. A method for programmable scheduling of routers, comprising:

receiving a packet;

storing the packet in a physical queue;

determining when to reconstruct a scheduling hierarchy, and when, reconstructing the scheduling hierarchy;

selecting a scheduling method;

selecting an input based on the scheduling method;

determining when to update scheduler parameters;

if the input is connected to a virtual queue, proceeding until the input is connected to a corresponding physical queue, else if the input is connected to said physical queue, taking the packet from the physical queue and transmitting the packet to an output link.

4. The method of claim 3, wherein the scheduling method may be a combination of Priority Queuing method and a Deficit Round Robin method.

5. The method of claim 3, wherein the parameters received by the scheduling configuration interface are related to at least one of a scheduling hierarchy, the number of scheduling stages, and relative positions of the scheduling stages.

6. A method for programmable scheduling of routers, comprising:

receiving a packet;

storing the packet in a physical queue;

determining when to reconstruct a scheduling hierarchy, wherein determining when to reconstruct the scheduling hierarchy, further comprises determining when parameters have been received that relate to the scheduling hierarchy, and when the parameters have been received, reconstructing the scheduling hierarchy;

selecting a scheduling method;

selecting an input based on the scheduling method;

detennining when to update scheduler parameters;

if the input is connected to a virtual queue, proceeding until the input is connected to a corresponding physical queue, else if the input is connected to said physical queue, taking the packet from the physical queue and transmitting the packet to an output link.

7. The method of claim 6, further comprising dynaxmically receiving the parameters.

8. The method of claim 7, wherein selecting the scheduling method further comprises programming the scheduling method in relation to the dynamically received parameters.

9. An apparatus for a programmable scheduler that can support single stage and multi-stage scheduling, comprising:

a scheduling configuration interface that is arranged to receive parameters related to at least one of a cardinality of scheduling stages, a relative order of the scheduling stages in a scheduling hierarchy, and a position of queues in the scheduling hierarchy; and

further arranged to provide a scheduling configuration based, at least in part, on the parameters and

an interface arrangement that is configured to receive and output packets, wherein the interface arrangement is configured to output the packets according to the scheduling configuration.

10. The apparatus of claim 9, wherein the scheduling configuration interface is further arranged such that a scheduling method employed by each of the scheduling stages is capable of being modified through dynamic progamming.

11. The apparatus of claim 9, wherein the scheduling configuration interface is further arranged such that the relative order of the scheduling stages is capable of being modified through dynamic programming.

12. The apparatus of claim 9, wherein the position of the queues in the scheduling hierarchy is capable of being modified through dynamic programming.