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

Claim 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.

Claim 2

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.

Claim 5

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.

Claim 6

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.