Method and apparatus for scheduling cells for use in a static priority scheduler

• US 5,999,534 A
• Filed: 11/24/1997
• Issued: 12/07/1999
• Est. Priority Date: 12/26/1996
• Status: Expired due to Term

• Current Assignee: Wi-LAN Inc.
• Original Assignee: Daewoo Electronics Company Limited (Dayou Holdings Co.,Ltd.)
• Inventors: Kim, Deog-Nyoun
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Sam, Phirin
• Application Number:
  US08/976,728
• Time in Patent Office: 743 Days
• Field of Search: 370/395, 370/399, 370/409, 370/389, 0/415, 0/420, 0/422, 0/428, 0/429, 0/444, 0/455, 0/516, 0/517, 0/519, 0/230, 0/235, 0/360, 0/412, 0/413, 0/417, 0/229, 0/231, 0/232 , 0/233, 0/234, 0/253, 0/378, 0/383
• US Class Current: 370/395.42
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 49/206 Real Time traffic
• CPC Class Codes: H04L 49/503 Policing
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method for scheduling a plurality of cells of N number of prioritized queues in a node of an ATM network is provided, wherein each prioritized queue has a static priority different from priorities of other queues. In response to receipt of a cell having a jth static priority, the cell is held for a holding time so that the cell turns to be an eligible cell for transmission. Meanwhile, an empty flag EF_j `0` or `1` is generated on a time slot basis, wherein the empty flag EF_j `0` or `1` represents whether or not there exists the eligible cell for transmission in the corresponding jth prioritized queue; and the jth prioritized queue is switched to a higher prioritized switch in a jth prioritized switch based on the empty flag EF_j, wherein the jth prioritized switch has a jth and a lower input terminals, which are connected to the jth prioritized queue and the lower prioritized switch, respectively, and an output terminal, which is connected to the higher prioritized switch.

Claims

1. A method for scheduling a plurality of cells of N number of prioritized queues in a node of an ATM network, N being a positive integer, wherein each prioritized queue has a static priority different from priorities of other queues, the method comprising the steps of:

(a) in response to a cell having a jth static priority, calculating a holding time after which the cell will be eligible for transmission, wherein the static prioritized number j is a positive integer less than or equal to N and a smaller static prioritized number has a higher priority;

(b) holding the cell for the holding time so that the cell becomes eligible for transmission;

(c) generating an empty flag EF_j of a value either `0` or `1` on a time slot basis, wherein the empty flag EF_j of a value `0` represents that there exists an eligible cell for transmission in a corresponding jth prioritized queue while that of a value `1` indicates that there is none eligible;

(d) switching a jth prioritized queue to a higher prioritized switch in a jth prioritized switch based on the empty flag EF_j, wherein the jth prioritized switch has two input terminals, a jth one and a lower one, which are connected to the jth prioritized queue and a lower prioritized switch, respectively, and an output terminal, which is connected to the higher prioritized switch; and

the output terminal of a first prioritized switch is attached to a transmitter for transmission and the lower input terminal of an Nth prioritized switch is attached to a non real-time queue which has non-prioritized cells; and

(e) transmitting the eligible cell attached to the transmitter to a destined next node on a time slot basis.

2. The method as recited in claim 1, wherein, if the empty flag EF_j is of a value `0`, the jth prioritized queue is coupled with a higher prioritized switch and, if the empty flag EF_j is of a value `1`, the lower prioritized switch is coupled with the higher prioritized switch.

3. The method as recited in claim 2, wherein the higher static priority has a smaller delay bound.

4. An apparatus for scheduling a plurality of cells of N number of prioritized queues in ATM network, N being a positive integer, wherein each prioritized queue has a static priority different from priorities of other queues, the apparatus comprises:

means, in response to a cell having a jth static priority, for calculating a holding time after which the cell will be eligible for transmission, wherein the static prioritized number j is a positive integer less than or equal to N and a smaller static prioritized number has a higher priority;

means for holding the cell for the holding time so that the cell becomes eligible for transmission;

means for signaling time slots, wherein at most one eligible cell per time slot is transmitted;

means for generating an empty flag EF_j of a value either `0` or `1` on a time slot basis, wherein the empty flag EF_j of a value `0` represents that there exists an eligible cell for transmission in a corresponding jth prioritized queue while that of a value `1` indicates that there is none eligible;

N prioritized switches, jth prioritized switch for switching a jth prioritized queue to an adjacent higher prioritized switch based on the empty flag EF_j, j having values from 1 to N, wherein the jth prioritized switch has two input terminals, a jth one and a lower one, which are connected to the jth prioritized queue and a lower prioritized switch, respectively, and an output terminal, which is connected to the higher prioritized switch; and

the output terminal of a first prioritized switch is attached to a transmitter for transmission and the lower input terminal of an Nth prioritized switch is attached to a non real-time queue which has non-prioritized cells; and

means for transmitting the eligible cell attached to the transmitter to a destined next node on a time slot basis.

5. The apparatus as recited in claim 4, wherein the holding means includes two FIFO(first-in first-out) queues logically separated from each other so that one FIFO queue stores an eligible cell ready to be scheduled for transmission while the other FIFO queue stores a non-eligible cell for the holding time.

6. The apparatus as recited in claim 5, wherein, if the empty flag EF_j is of a value `0`, the jth prioritized queue is coupled with the higher prioritized switch and, if the empty flag EF_j is of a value `1`, a lower prioritized switch is coupled with the higher prioritized switch.

7. The apparatus as recited in claim 6, wherein the higher static priority has a smaller delay bound.