Traffic scheduling system and method for packet-switched networks with fairness and low latency

A method for scheduling the transmission of data packets in a packet switch having an input port and an output port wherein individual application sessions share an outgoing communications link, comprising the steps of:

• (a) receiving a plurality of data packets;
• (b) determining a system potential as a function of network activity, the system potential being zero when there are no packets to send on the outgoing communications link and increasing in real time as packets are transmitted;
• (c) recalibrating the system potential at the end of transmission of each packet;
• (d) timestamping each packet on arrival at the output port based on the system potential and the timestamp of the previous packet of the same session;
• (e) storing packets in a packet queue, wherein the packets are ordered according to their timestamps, and wherein the packet with the smallest timestamp value is placed at the head of the packet queue;
• (f) adding an entry for the packet in a starting-potential queue, wherein the packet with the smallest starting-potential value is placed at the head of the starting-potential queue;
• and
• (g) transmitting the packet having the smallest timestamp.

A priority queue method for selecting for transmission ATM cells arriving at an ATM network switch from a plurality of different connections wherein a timestamp value is assigned to each of plurality of ATM cells based on a system potential, wherein ATM cells are stored in a queue in a sequential order according to their timestamps, wherein the time period during which ATM cells are received is divided into W individual slots, each slot having a corresponding timestamp, comprising the steps of:

• (a) providing a state array means for indicating the presence of queued cells with an associated timestamp value, the state array means including a plurality of storage elements corresponding to slots, at least one storage element corresponding to each timestamp value,
• (b) an array of head pointers, one head pointer per slot, each head pointer pointing to at least one ATM cell with a time stamp value corresponding to a slot number;
• and
• (c) scanning storage elements and selecting an ATM cell having the smallest timestamp value for transmission.

A starting-potential queue method for determining the minimum starting potential of ATM cells queued in an ATM network switch from a plurality of different connections, wherein the starting potentials of ATM cells are stored in a queue in a sequential order according to their starting potential values, wherein the time period during which ATM cells are received is divided into W individual slots, each slot having a corresponding starting potential comprising the steps of:

• (a) providing a state array means for indicating the presence of queued cells with an associated starting-potential value, the state array means including a plurality of storage elements corresponding to the slots, at least one storage element corresponding to each starting-point value;
• (b) providing a set of counters for indicating the number of queued cells with an associated starting-potential value, with at least one counter corresponding to each starting-potential value;
• and
• (c) scanning storage elements and selecting the smallest starting-potential value.

A method of determining the lowest starting potential of a queued ATM cell, wherein the time period during which a plurality of data packets are received is divided into slots, each of the slots having a corresponding starting-potential, each of the slots having a number, each of the slots having a state, the state including full and empty, wherein data packets comprise a plurality of ATM cells, the method comprising the steps of:

• (a) providing an array of slots which indicate which of the plurality of different connections contain ATM cells for transmission;
• (b) scanning for a first full slot starting from one of the slots corresponding to a first-slot pointer, the first full slot indicating that one of the connections has an ATM cell for transmission;
• and
• (c) retrieving the starting potential of the ATM cell corresponding to the first full slot.

A method for updating the starting-potential queue on transmission of a cell, wherein the time period during which data packets are received is divided into slots, each slot having a corresponding starting-potential value, each slot having a number, each slot having a state, the state including full and empty, wherein data packets comprise ATM cells, the method comprising the steps of:

• (a) locating the slot corresponding to the ATM cell just transmitted;
• (b) decrementing the counter associated with the slot;
• (c) setting the state of the slot to empty if the counter is zero;
• and
• (d) if more ATM cells exist from the connection corresponding to the cell that was just transmitted;
• (i) locating the next ATM cell from the same connection,
• (ii) calculating the starting-potential of the next ATM cell,
• (iii) determining the slot number corresponding to obtained starting potential;
• and
• (iv) incrementing the counter corresponding to the slot number.

A scheduling system for receiving a plurality of data packets arriving at a network switch from a plurality of connections and transmitting data packets over a communications link, each of the plurality of connections having a service rate, comprising:

• (a) means for receiving a plurality of data packets during a period of time, each of the plurality of packets having a length;
• (b) means for calculating an elapsed real-time since a current data packet being transmitted has started transmitting, the elapsed real-time representing a time offset between the arrival time of newly arriving data packet at said network switch and the time at which the current data packet started transmitting, and means for adding the elapsed real time to the previous system potential in order to obtain a system potential as each of a plurality of data packets arrives at said network switch;
• (c) means for retrieving a timestamp of a prior data packet that arrived from a same connection as an incoming data packet, the timestamp of the prior data packet being reset to zero when there are no data packets to transmit from any of the plurality of connections, means for defining a starting potential for the incoming data packet as a maximum value of the timestamp of the prior data packet and the system potential, and means for dividing the length of incoming data packet by the service rate of the connection associated with incoming data packet and adding the result of the division to a starting potential in order to obtain timestamp;
• and
• (d) means for storing data packets in a packet queue and transmitting the data packets from packet queue according to their timestamps.

A system for scheduling the transmission of data packets in a packet switch having an input port and an output port wherein individual application sessions share an outgoing communications link, comprising:

• means for receiving a plurality of data packets;
• means for determining a system potential as a function of a network activity, the system potential being zero when there are no packets to send on the outgoing communications link and increasing in real time as packets are transmitted;
• means for recalibrating the system potential at the end of transmission of each packet;
• means for timestamping each packet on arrival at the output port based on the system potential and the timestamp of the previous packet of the same session;
• means for storing packets in a packet queue, wherein the packets are ordered according to their timestamps, and wherein the packet with the smallest timestamp value is placed at the head of the packet queue;
• means for adding an entry for the packet in a starting-potential queue, wherein the packet with the smallest starting-potential value is placed at the head of the starting-potential queue;
• and
• means for transmitting the packet having the smallest timestamp.

A priority queue for selecting for transmission ATM cells arriving at an ATM network switch from a plurality of different connections wherein a timestamp value is assigned to each of the ATM cells based on a system potential, wherein the ATM cells are stored in a queue in a sequential order according to their timestamps, wherein the time period during which the ATM cells are received is divided into W individual slots, each slot having a corresponding timestamp, comprising:

• means for providing a state array means for indicating the presence of queued cells with an associated timestamp value, the state array means including a plurality of storage elements corresponding to slots, at least one storage element corresponding to each timestamp value, wherein the ATM cells are stored in storage elements;
• means for providing an array of head pointers, one head pointer per slot, each head pointer pointing to at least one ATM cell with a time stamp value corresponding to a slot number;
• and
• means for scanning storage elements and selecting an ATM cell having the smallest timestamp value for transmission.

A starting-potential queue for determining the minimum starting potential of ATM cells queued in an ATM network switch from a plurality of different connections, wherein the starting potentials of ATM cells are stored in a queue in a sequential order according to their starting potential values, wherein the time period during which ATM cells are received is divided into W individual slots, each slot having a corresponding starting potential comprising:

• means for providing a state array means for indicating the presence of queued cells with an associated starting-potential value, the state array means including a plurality of storage elements corresponding to the slots, at least one storage element corresponding to each starting-point value;
• means for providing a set of counters for indicating the number of queued cells with an associated starting-potential value, with at least one counter corresponding to each starting-potential value;
• and
• means for scanning storage elements and selecting the smallest starting-potential value.

A system of determining the lowest starting potential of a queued ATM cell, wherein the time period during which a plurality of data packets are received is divided into slots, each of the slots having a corresponding starting-potential, each of the slots having a number, each of the slots having a state, state including full and empty, wherein data packets comprise a plurality of ATM cells, the system comprising:

• means for providing an array of slots which indicate which of the plurality of different connections contain ATM cells for transmission;
• means for scanning for a first full slot starting from one of the slots corresponding to a first-slot pointer, the first full slot indicating that one of connections has an ATM cell for transmission;
• and
• means for retrieving the starting potential of the ATM cell corresponding to the first full slot.

A system for updating the starting-potential queue on transmission of a cell, wherein the time period during which data packets are received is divided into slots, each slot having a corresponding starting-potential value, each slot having a number, each slot having a state, the state including full and empty, wherein data packets comprise ATM cells, the system comprising:

• means for locating the slot corresponding to the ATM cell just transmitted;
• means for decrementing the counter associated with the slot;
• means for setting the state of the slot to empty if the counter becomes zero;
• and
• means for locating the next ATM cell from the connection;
• means for calculating the starting-potential of the next ATM cell;
• means for determining the slot number corresponding to the obtained starting potential;
• and
• means for incrementing the counter corresponding to slot number if more ATM cells exist from the connection corresponding to the cell that was just transmitted.

A scheduling method for receiving a plurality of data packets arriving at a network switch from a plurality of connections and transmitting data packets over a communications link, each of the plurality of connections having a service rate, comprising the steps of:

• (a) receiving a plurality of data packets during a period of time, each of the plurality of packets having a length;
• (b) calculating a global variable as each of the plurality of data packets arrives at a switch;
• (c) calculating a timestamp for each of the plurality of data packets based on the global variable;
• and
• (d) storing data packets in a packet queue and transmitting the data packets from the packet queue according to their timestamps.

A scheduling system for receiving a plurality of data packets arriving at a network switch from a plurality of connections and transmitting data packets over a communications link, each of the plurality of connections having a service rate, comprising:

• means for receiving a plurality of data packets during a period of time, each of the plurality of packets having a length;
• means for calculating a global variable as each of the plurality of data packets arrives at a switch;
• means for calculating a timestamp for each of the plurality of data packets based on the global variable;
• and
• means for storing data packets in a packet queue and transmitting the data packets from the packet queue according to their timestamps.