Patent ID: 6618391
Filing Date: 2003-09-09
Classification: H04L

Abstract:
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.