Method to schedule multiple traffic flows through packet-switched routers with near-minimal queue sizes

A method of transmitting a plurality of traffic flows to N output ports, comprising:

• receiving each one of said plurality of traffic flows, each one of said plurality of traffic flows associated with a respective guaranteed data rate;
• buffering packets in each of said plurality of traffic flows in one of N input queues, in dependence on the output port for that traffic flow;
• for each of said plurality of traffic flows determining an ideal packet departure time for each buffered packet in that flow that would provide for zero jitter for that flow, based on at least the guaranteed data rate for that flow;
• during a switching interval, transmitting a chosen packet from a selected one of said N input queues to the output port for that selected one of said N input queues;
• wherein said chosen packet is chosen among packets in said selected one of said N input queues, as the packet for which a normalized service lag is the largest positive value among packets buffered within said selected one of said N input queues, wherein the normalized service lag for each of said packets in said selected one of said N input queues reflects the current time minus that packet's ideal departure time in its flow, multiplied by the guaranteed data rate for that flow.

A method of computing a periodic flow schedule for F time slots, for transmitting a plurality of traffic flows buffered in N input queues to N output ports through a switch, said method comprising:

• associating each one of said plurality of traffic flows with the one of said N input queues corresponding to the one of the N output ports required by that flow;
• receiving for each of the plurality of flows, a guaranteed data rate corresponding to the number of packet transmissions required by that flow in said F time slots;
• calculating from said associating and said guaranteed data rate for each flow, a cumulative data rate for each of the N input queues in said F time slots, corresponding to the number of packet transmissions required by each of said N input queues in said F time slots in order to satisfy said guaranteed data rate for all of the plurality of flows associated with that one of said N input queues;
• receiving a connection schedule identifying a selected one of said N input queues in each of said F time slots, and satisfying the cumulative data rate requirement for each of the N input queues in said F time slots;
• computing a periodic flow schedule, said periodic flow schedule identifying a chosen flow if any for each of said F time slots, said chosen flow associated with the selected one of said N input queues in the connection schedule for that time slot, said periodic flow schedule further satisfying the guaranteed data rate requirements of said plurality of flows in said F time slots;
• storing said periodic flow schedule.

A method to compute a periodic flow schedule for F time slots for transmitting a plurality of traffic flows buffered in N input queues to N output ports through a switch, said method comprising:

• associating a subset of said plurality of traffic flows with each of the N input queues, each of said subset of said plurality of traffic flows destined for the same output port;
• receiving the guaranteed data rate of each flow of the plurality of traffic flows, where the guaranteed data rate of a flow corresponds to a number of packet transmissions required for the flow in a periodic schedule of F time slots;
• calculating from said guaranteed data rate for each flow, a cumulative data rate requirement for each of the N input queues in said F time slots, corresponding to the number of packet transmissions required by each of said N input queues in said F time slots in order to satisfy said guaranteed data rate for all of the plurality of flows associated with that one of said N input queues;
• receiving a periodic connection schedule of length F, identifying a selected one of the N input queues in each of F time slots, which satisfies the cumulative data rate requirement of each of the N input queues in said F time slots;
• computing a sequence of theoretical packet transmission times for each flow of the plurality of traffic flows, the sequence of theoretical packet transmission times for each flow satisfying the guaranteed data rate requirement for that flow, and having zero jitter, and wherein each theoretical packet transmission time will be assigned in a unique time- slot in the flow-schedule;
• for each time-slot in the connection schedule, choosing a flow associated with the selected input queue identified for that time-slot, for which a theoretical packet transmission time will be assigned onto that time slot;
• wherein the chosen flow in the selected one of said N input queues in each time-slot is chosen as the flow with the next earliest unassigned theoretical packet transmission time;
• storing the chosen flow for each of said F time slots.

A method of multiplexing N traffic flows onto one communication link, comprising:

• receiving each of said N traffic flows, each of said N traffic flows associated with a respective guaranteed data rate;
• buffering packets in each of said N traffic flows;
• in a switching time, transmitting a buffered packet from a chosen one of the N traffic flows onto the communication link;
• wherein said chosen one of said N traffic flows is chosen from said N traffic flows as the traffic flow with the largest positive normalized service lag among said N traffic flows;
• wherein the normalized service lag of each of said N traffic flows at any time reflects the difference between the cumulative transmission capacity that the flow would be allocated through said communication link at the guaranteed data rate over a measurement interval ending at that time, and the cumulative transmission capacity allocated to that flow through said communication link during that measurement interval.