Patent ID: 6075791
Filing Date: 2000-06-13
Classification: H04L,H04Q

Abstract:
A method of servicing, at a predetermined service rate, a plurality of queues containing data packets, each of said queues being associated with respective connections, said connections traversing an associated communications switch, each of said connections being allocated a respective data transfer rate, said method comprising:responsive to receiving a plurality of data packets via a plurality of data links, identifying for each received data packet the respective one of said connections and identifying the associated one of said queues,storing each of the received data packets in their respective identified queue,associating a timestamp with each connection whose associated queue has at least one data packet waiting therein, in which said connection is identified as a backlogged connection, and generating a timestamp associated with each connection each time a new data packet reaches the head of the associated queue,storing in memory the timestamps associated with respective ones of the backlogged connections,determining which of the timestamps associated with respective ones of the backlogged connections has the smallest value among all of the timestamps, identifying the associated connection, removing a data packet from the head of that one of the queues associated with the identified connection and transmitting the removed data packet to an output,in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as a maximum value between a previous value of the timestamp assigned to the connection and a current value of at least one function or system potential, said maximum value incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet was not backlogged before the packet reaches the head of the associated queue,in which the timestamp associated with a backlogged connection, generated each time a new data packet reaches the head of the associated queue, is generated as the previous value of the timestamp of the connection incremented by the inverse of the data transfer rate allocated to the connection normalized to the rate of the server, if the connection associated with the data packet was backlogged before the packet arrived at the head of the associated queue,wherein a value for the system potential is generated following the transmission of a packet in the system as the maximum value between the latest value of the system potential incremented by a first predetermined value and the weighted sum of the timestamp values associated with all the currently backlogged connections, in which the weight of each timestamp value in the weighted sum is the data transfer rate allocated to the associated connection, and in which said weighted sum is decremented by the number of connections that are currently backlogged, in which that result is then divided by the sum of the values of the data transfer rates allocated to all connections that are currently backlogged.