Method and Device for Scheduling Packets for Routing in a Network with Implicit Determination of Packets to be Treated as Priority

• US 20070291644A1
• Filed: 11/15/2005
• Published: 12/20/2007
• Est. Priority Date: 11/15/2004
• Status: Active Grant

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Oueslati, Sara, Kortebi, Abdesselem, Roberts, James
• Granted Patent: US 8,311,049 B2
• Time in Patent Office: Days
• US Class Current: 370/230.1
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

A method of ordonnancing packets belonging to different flows comprises: a step (E58) of queuing each packet in a queue associated with the flow of said packet; and for each of said queues processed cyclically, a step of sending packets contained in said queue up to a quota for said cycle; said method being characterized in that it further includes: a step (E40, E54) of determining the priority of said packet before said step (E58, E56, E48) of queuing, the priority packets being, firstly, the first packets of the inactive flows, namely the flows for which no packet has been received in said cycle, and, secondly, the packets of the active flows for which the volume of packets received in the cycle is less than the quota; and a step of sending with priority in said cycle packets determined to have priority during said determination step (E40, E54).

Claims

1. A method of ordonnancing packets (p) belonging to different flows (i), the method comprising:

a step (E58) of queuing each packet in a queue (Queue_i) associated with the flow of said packet (p); and

for each of said queues (Queue_i) processed cyclically, a step (F64) of sending packets contained in said queue (Queue_i) up to a quota (Q_i) for said cycle;

a step (E40, E54) of determining the priority of said packet (p) before said step (E58) of queuing, the priority packets being;

firstly, the first packets of the inactive flows, namely the flows for which no packet has been received in said cycle; and

secondly, the packets of the active flows for which the volume (BytesCount_i) of packets received in said cycle is less than said quota (Q_i); and

a step (F24) of sending with priority in said cycle packets determined to have priority during said determination step (E40, E54).

2. The ordonnancing method according to claim 1, further including a step (F28, F42) of measuring congestion counters (FB, PB) adapted to be processed to calculate congestion estimators (CP, DE) used for admission control.

3. The ordonnancing method according to claim 2, wherein said congestion parameters comprise:

a fair bit rate value (DE) which is a measure of the bit rate that a data flow would produce that always had packets to send; and

a priority load value (CP) corresponding to the volume of said priority packets transmitted during a period divided by the duration of that period.

9. A computer program stored on an information medium, said program including instructions enabling the execution of an ordonnancing method according to claim 1 when that program is loaded into and executed by an electronic data processing system.

10. An information medium readable by an electronic data processing system and optionally totally or partially removable, in particular a CD-ROM or a magnetic medium, such as a hard disk or a diskette, or a transmissible medium, such as an electrical or optical signal, wherein the medium includes instructions of a computer program for executing an ordonnancing method according to claim 1 when that program is loaded into and executed by an electronic data processing system.

4. A device for ordonnancing packets (p) belonging to different flows (i), the device comprising:

means for queuing each packet in a queue (Queue_i) associated with the flow of said packet (p); and

means for processing each of said queues (Queue_i) cyclically, said processing means including means for sending packets contained in said queue (Queue_i) up to a quota (Q_i) for said cycle;

means for determining the priority of said packet (p) before queuing said packet, the priority packets being;

firstly, the first packets of the inactive flows, namely the flows for which no packet has been received in said cycle; and

secondly, the packets of the active flows for which the volume (BytesCount_i) of packets received in said cycle is less than said quota (Q_i); and

means for sending with priority in said cycle packets determined to have priority by said determination means.

5. The ordonnancing device according to claim 4, further including means for measuring congestion counters (FB, PB) adapted to be processed to calculate congestion estimators (CP, DE) used for admission control.

6. The ordonnancing device according to claim 5, wherein congestion parameters comprise:

a fair bit rate value (DE) which is a measure of the bit rate that a data flow would produce that always had packets to send; and

a priority load value (CP) corresponding to the volume of said priority packets transmitted during a period divided by the duration of that period.

7. A packet router including an ordonnancing device (100) according to claim 5 and a module (24) for controlling admission of said packets as a function of congestion parameters measured by said ordonnancing device.

8. The packet router according to claim 7, wherein said admission module is further adapted to route directly the packets belonging to protected flows, namely flows for which at least one packet has been received by said admission module in a predetermined term interval.