Method and apparatus for scheduling for packet-switched networks

• US 7,236,491 B2
• Filed: 09/19/2001
• Issued: 06/26/2007
• Est. Priority Date: 11/30/2000
• Status: Active Grant

• Current Assignee: A10 Networks Incorporated
• Original Assignee: Industrial Technology Research Institute
• Inventors: Tsao, Shih-Chiang, Lin, Ying-Dar, Tsai, Chun-Yi, Huang, Hai-Yang
• Primary Examiner(s): Phan; Man U.
• Application Number:
  US09/955,296
• Publication Number:
  US 20020131413A1
• Time in Patent Office: 2,106 Days
• Field of Search: 370229-252, 370322-392, 370393-492, 370412-428, 709230-249
• US Class Current: 370/392
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/17 Interaction among intermediate nodes, e.g. hop by hop
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]

Abstract

Apparatus and method use pre-order queuing and scheduling. Reordering of the transmission sequence of packets that could be sent out in one round is allowed according to the quantum consumption status of the flow within the round. Per-packet time complexity is maintained independent from an increase in flow number and packets of variable-length are processed.

Claims

1. A method for scheduling a packet, comprising the steps of:

receiving a packet having a size;

identifying a flow for said packet by at least a flow identifier;

classifying said packet based on said identified flow;

buffering said packet in one of a plurality of queues, arranged in a priority order, based on said classification of said packet and a priority of said packet assigned based on said priority order;

allocating a predetermined amount of bandwidth to said identified flow;

determining an accumulated bandwidth based on said predetermined amount of bandwidth; and

processing said packet in the one of the plurality of queues based on said accumulated bandwidth and said size of said packet.

2. The method of claim 1, wherein identifying said flow for said packet comprises identifying a source address of said packet.

3. The method of claim 1, wherein identifying said flow for said packet comprises identifying a destination address of said packet.

4. The method of claim 1, wherein classifying said packet comprises:

calculating said size of said packet; and

calculating said accumulated bandwidth assigned to said flow based upon said size of said packet.

5. The method of claim 4, wherein calculating said accumulated bandwidth is based upon predetermined amount of bandwidth assigned to said flow and said size of said packet.

6. The method of claim 1, wherein buffering said packet in one of said plurality of queues comprises:

arranging said plurality of queues in a priority order;

assigning a priority to said packet based on said priority order; and

buffering said packet in one of said queues based on said assigned priority.

7. The method of claim 6, wherein assigning a priority to said packet based on said priority order comprises;

determining said size of said packet; and

calculating a transmission delay based on said size of said packet and said priority order.

8. The method according to claim 1, further including:

calculating a residual bandwidth after said processing;

allocating a second predetermined amount of bandwidth to said identified flow; and

recalculating said accumulated bandwidth based on said residual bandwidth and said second predetermined amount of bandwidth.

9. The method according to claim 8, wherein:

said residual bandwidth is determined as a difference between said accumulated bandwidth and a total amount of data of packets processed; and

said accumulated bandwidth is recalculated as a summation of said residual bandwidth and said second predetermined amount of bandwidth.

10. A system for scheduling a packet, comprising;

an input to receive a plurality of packets;

an arrival module to identify a flow for each of said plurality of packets by at least a flow identifier;

a classifier to assign each of said plurality of packets to one of a plurality of queues, arranged in a priority order, based on said identified flow;

a server for allocating a predetermined amount of bandwidth to said identified flow, determining an accumulated bandwidth based on said predetermined amount of bandwidth, and selecting one of said plurality of queues based on said priority order; and

an output for outputting a packet from said selected queue based on said accumulated bandwidth of said identified flows, a priority of said packet assigned based on said priority order, and said size of said packet.

11. The system of claim 10, further comprising:

a memory to store a service list of flows identified for each of said plurality of packets.

12. An apparatus for scheduling a packet, comprising:

means for receiving a packet having a size;

means for identifying a flow for said packet by at least a flow identifier;

means for classifying said packet based on said identified flow;

means for buffering said packet in one of a plurality of queues, arranged in a priority order, based on said classification of said packet and a priority of said packet assigned based on said priority order;

means for allocating a predetermined amount of bandwidth to said identified flow;

means for determining an accumulated bandwidth based on said predetermined amount of bandwidth; and

means for processing said packet in the one of the plurality of queues based on the accumulated bandwidth and said size of said packet.

13. A program on a computer readable medium for configuring a processor to execute a method for scheduling a packet, said method comprising the steps of:

receiving a packet having a size;

identifying a flow for said packet by at least a flow identifier;

classifying said packet based on said identified flow;

buffering said packet in one of a plurality of queues, arranged in a priority order, based on said classification of said packet and a priority of said packet assigned based on said priority order;

allocating a predetermined amount of bandwidth to said identified flow;

determining an accumulated bandwidth based on said predetermined amount of bandwidth; and

processing said packet in the one of the plurality of queues based on said accumulated bandwidth and said size of said packet.