Back to results
US 6,618,391 B1Granted
Method and apparatus for guaranteeing data transfer rates and delays in data packet networks using discrete data transfer rates
AssigneeAgere Systems Inc.
InventorsFabio Massimo Chiussi, Andrea Francini
Life of this patent
Estimating the term…
Abstract
A scheduler and method for use in ATM and packet communication systems applies a no-per-connection-timestamp discrete-rate scheduling technique which does not require the computation and storage of one timestamp per connection, and only maintains a single timestamp per supported service rate. The elimination of the per-connection timestamps has no negative effect on the delay bounds guaranteed by the scheduler. The total implementation cost of such schedulers which approximate the Generalized Processor Sharing (GPS) policy is reduced, since there is less complexity involved in maintaining and sorting the timestamps for all connections.
Claims32
A method for servicing, at a predetermined service rate, a plurality of queues containing data packets, each of the queues being associated with respective connections, the connections traversing an associated communication switch, each of the connections being allocated a respective data transfer rate, the method comprising the steps of:
- identifying for each received data packet, responsive to receiving a plurality of the data packets via a plurality of data links, the respective one of the connections and identifying the associated one of the queues;
- storing each of the received data packets in one of the plurality of queues;
- associating a queue of connections with each connection wherein an associated queue of each connection has at least one data packet waiting therein, in which the connection is identified as a backlogged connection, the queue of connections being associated with a respective data transfer rate equal to the data transfer rate associated with the backlogged connection;
- appending a connection to the tail of the associated queue of connections when the connection becomes backlogged after a period of time during which no data packets are stored in its associated queue;
- associating a timestamp with each of the queues of connections, including generating a new timestamp associated with a queue of connections each time a new backlogged connection reaches the head of the queue of connections, wherein a system potential is used in the generation of the new timestamp;
- associating a cumulative service rate with each of the queues of connections, the cumulative service rate being used to generate the respective timestamp associated with each of the queues of connections;
- generating a value for the system potential according to a predetermined function;
- and
- selecting one of the timestamps associated with any queues of connections which have at least one backlogged connection waiting for service therein, and identifying the backlogged connection at the head of the queue of connections associated with the selected timestamp as the recipient of the next service, the service including the steps of removing a data packet from the head of the queue associated with the identified backlogged connection, transmitting the removed data packet to an output, removing the identified backlogged connection from the head of the queue of connections associated with the selected timestamp, and appending again the identified connection to the tail of the same queue of connections only if the identified connection remains backlogged after the packet has been removed.
6 more elements
A packet communication system for servicing, at a predetermined service rate, a plurality of queues containing data packets, each of the queues being associated with respective connections, the connections traversing an associated communication switch, each of the connections being allocated a respective data transfer rate, the packet communication system comprising:
- a plurality of queues, with each queue for respectively storing received data packets;
- a session controller which identifies for each received data packet, responsive to receiving a plurality of the data packets via a plurality of data links, the respective one of the connections and identifying the associated one of the queues;
- wherein the session controller associates a queue of connections with each connection wherein an associated queue of each connection has at least one data packet waiting therein, in which the connection is identified as a backlogged connection, the queue of connections being associated with a respective data transfer rate equal to the data transfer rate associated with the backlogged connection;
- wherein the session controller appends a connection to the tail of the associated queue of connections when the connection becomes backlogged after a period of time during which no data packets are stored in its associated queue;
- wherein the session controller associates a timestamp with each of the queues of connections, including generating a new timestamp associated with a queue of connections each time a new backlogged connection reaches the head of the queue of connections, wherein a system potential is used in the generation of the new timestamp;
- wherein the session controller associates a cumulative service rate with each of the queues of connections, the cumulative service rate being used to generate the respective timestamp associated with each of the queues of connections;
- and
- wherein the session controller generates a value for the system potential according to a predetermined function;
- and
- a selector for selecting one of the timestamps associated with any queues of connections which have at least one backlogged connection waiting for service therein, and identifying the backlogged connection at the head of the queue of connections associated with the selected timestamp as the recipient of the next service, the service including the steps of removing a data packet from the head of the queue associated with the identified backlogged connection, transmitting the removed data packet to an output, removing the identified backlogged connection from the head of the queue of connections associated with the selected timestamp, and appending again the identified connection to the tail of the same queue of connections only if the identified connection remains backlogged after the packet has been removed.
7 more elements
A packet communication system for servicing, at a predetermined service rate, a plurality of queues containing data packets, each of the queues being associated with respective connections, the connections traversing an associated communication switch, each of the connections being allocated a respective data transfer rate, the packet communication system comprising:
- a memory having a plurality of queues, with each queue for respectively storing received data packets;
- a session controller including:
- means for identifying, for each received data packet, responsive to receiving a plurality of the data packets via a plurality of data links, the respective one of the connections and identifying the associated one of the queues;
- means for associating a queue of connections with each connection wherein an associated queue of each connection has at least one data packet waiting therein, in which the connection is identified as a backlogged connection, the queue of connections being associated with a respective data transfer rate equal to the data transfer rate associated with the backlogged connection;
- means for appending a connection to the tail of the associated queue of connections when the connection becomes backlogged after a period of time during which no data packets are stored in its associated queue;
- means for associating a timestamp with each of the queues of connections, including generating a new timestamp associated with a queue of connections each time a new backlogged connection reaches the head of the queue of connections, wherein a system potential is used in the generation of the new timestamp;
- means for associating a cumulative service rate with each of the queues of connections, the cumulative service rate being used to generate the respective timestamp associated with each of the queues of connections;
- and
- means for generating a value for the system potential according to a predetermined function;
- and
- selecting means for selecting one of the timestamps associated with any queues of connections which have at least one backlogged connection waiting for service therein, and identifying the backlogged connection at the head of the queue of connections associated with the selected timestamp as the recipient of the next service, the service including the steps of removing a data packet from the head of the queue associated with the identified backlogged connection, transmitting the removed data packet to an output, removing the identified backlogged connection from the head of the queue of connections associated with the selected timestamp, and appending again the identified connection to the tail of the same queue of connections only if the identified connection remains backlogged after the packet has been removed.
8 more elements
A method for processing connections in a packet-processing system, the method comprising the steps of:
- queuing the connections into a plurality of queues of connections, with each queue having a single service rate associated with every connection in the respective queue;
- allocating, for each queue, a single timestamp associated with every connection in the respective queue;
- and
- processing the connections using the timestamps of the queues by selecting a next connection for service from the plurality of queues of connections and from the single timestamps associated therewith using a smallest-eligible-virtual-finishing-time-first (SEFF) selector, where the SEFF selector is a packet-by-packet rate-proportional server (P-RPS).
1 more element
A method for processing connections in a packet-processing system, the method comprising the steps of:
- queuing the connections into a plurality of queues of connections, with each queue having a single service rate associated with each of the connections in the respective queue, with the connections having the same single service rate queues into a corresponding rate first-in-first-out (FIFO) queue to form the plurality queues, the single timestamp being associated with a head of the respective rate FIFO queue;
- allocating, for each queue, a single timestamp to every connection in the respective queue;
- and
- processing the connections using a no-per-connection-timestamp scheduling procedure by selecting a next connection for service from the plurality of rate FIFO queues of connections and from the single timestamps associated with the heads of the plurality of rate FIFO queues using a smallest-eligible-virtual-finishing-time-first (SEFF) selector, wherein the SEFF selector is a packet-by-packet rate-proportional server (P-RPS).
1 more element
A scheduler for controlling processing connections associated with packets in a communication system, the scheduler comprising:
- a plurality of queues of connections, with each queue having a single service rate associated with each of the connections in the respective queue;
- a plurality of timestamps, with each respective timestamp being a single timestamp associated with a respective queue and the connections therein, wherein the connections in a respective queue are commonly associated with the respective timestamp of the queue;
- and
- a smallest-eligible-virtual-finishing-time-first (SEFF) selector, responsive to the plurality of timestamps, said SEFF selector being a packet-by-packet rate-proportional server (P-RPS) and used for processing the connections using a no-per-connection-timestamp scheduling procedure.
1 more element
Dependencies are inferred from the claim text.