# US 2004/0001491 A1 · Programmable scheduling for IP routers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0001491 A1
- Document ID: US20040001491A1
- Status: Published application
- Kind: A1
- Application number: 10/183,057
- Filed: 2002-06-26
- Published: 2004-01-01
- Earliest claimed: 2002-06-26
- Assignees: Nokia Corporation
- Inventors: Jussi Ruutu; Jani Lakkakorpi; Vilho I. Raisanen
- Web page: https://patentgrep.com/patent/US20040001491A1

## CPC

- H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ]
- H04L 45/60: Router architectures
- H04L 47/2408: for supporting different services, e.g. a differentiated services [DiffServ] type of service
- H04L 47/2491: Mapping quality of service [QoS] requirements between different networks
- H04L 47/50: Queue scheduling
- H04L 47/522: {Dynamic queue service slot or variable bandwidth allocation}
- H04L 47/60: implementing hierarchical scheduling
- H04W 8/04: Registration at HLR or HSS [Home Subscriber Server]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

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

### Claim 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;
a scheduling configuration interface coupled to the routing core and the interface arrangement that is arranged to provide a scheduling configuration, wherein the scheduling configuration interface may be programmed to implement an undetermined number of scheduling algorithms; and
wherein the interface arrangement is configured to output packets according to the selected scheduling configuration.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the scheduling configuration interface is further configured to receive at least one parameter relating to the scheduling configuration.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the scheduling configuration supports single stage and multiple-stage scheduling.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the scheduling configuration may be selected from a Priority Queuing method and a Deficit Round Robin method.

### Claim 5 (depends on 3)

The apparatus of claim 3, wherein the scheduling configuration interface that may be programmed to implement the undetermined number of scheduling algorithms, further comprises programming the scheduling algorithms dynamically.

### Claim 6 (depends on 5)

The apparatus of claim 5, wherein scheduling parameters are provided to the scheduling configuration interface that are used to determine the scheduling configuration.

### Claim 7 (depends on 6)

The apparatus of claim 6, 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.

### Claim 8 (depends on 6)

The apparatus of claim 6, wherein the interface is further configured to classify the packet into separate classes.

### Claim 9 (depends on 8)

The apparatus of claim 8, further comprising a Quality of Service block coupled to the interface, the scheduling configuration interface that is configured to enforce Quality of Service requirements.

### Claim 10

A system for a programmable scheduler relating to IP routers, comprising:
nodes, wherein the nodes include a network interface unit arranged to communicate packets across the network; and
a router; wherein the router includes:
a network interface unit arranged to receive the packets and transmit packets to the nodes;
a scheduling configuration interface configured to receive parameters relating to a scheduling method;
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; and
an output arranged to output packets such that the scheduling method is followed.

### Claim 11 (depends on 10)

The system of claim 10, wherein the programmable scheduling component may be re-configured dynamically.

### Claim 12 (depends on 11)

The system of claim 11, wherein the programmable scheduling component receives input from a plurality of scheduling methods.

### Claim 13 (depends on 12)

The system of claim 12, wherein the plurality of scheduling methods may use at least two queues.

### Claim 14 (depends on 13)

The system of claim 13, wherein the queues may be implemented in hardware.

### Claim 15 (depends on 13)

The system of claim 13, wherein the queues may be implemented in software.

### Claim 16 (depends on 13)

The system of claim 13, wherein the queues may be implemented in hardware and software.

### Claim 17 (depends on 13)

The system of claim 13, wherein the plurality of scheduling methods may be a Priority Queuing method and a Deficit Round Robin method.

### Claim 18 (depends on 11)

The system of claim 11, wherein the parameters received by the scheduling configuration interface further comprise the number and relative positions of scheduling stages.

### Claim 19 (depends on 11)

The system of claim 11, wherein the parameters received by the scheduling configuration interface further comprise scheduling methods applied by scheduling stages.

### Claim 20 (depends on 11)

The system of claim 11, wherein the parameters received by the scheduling configuration interface further comprise parameters relating to a selected method.

### Claim 21 (depends on 11)

The system of claim 11, wherein the parameters received by the scheduling configuration interface further comprise a position of queues in a scheduling hierarchy.

### Claim 22

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;
determining when the input is connected to a virtual queue, and when proceeding until the input is connected to a physical queue, otherwise, taking the packet from a physical queue and transmitting the packet to an output link.

### Claim 23 (depends on 22)

The method of claim 22, wherein determining when to reconstruct the scheduling hierarchy, further comprises determining when parameters have been received that relate to the scheduling hierarchy, and when reconstructing the scheduling hierarchy.

### Claim 24 (depends on 23)

The method of claim 23, further comprising dynamically receiving the parameters.

### Claim 25 (depends on 24)

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

### Claim 26 (depends on 22)

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