Method to achieve bounded buffer sizes and quality of service guarantees in the internet network

A switch for switching a plurality of guaranteed-rate (GR) traffic flows over a set of output ports, given a scheduling frame comprising a plurality of transmission intervals defined over a duration of time of F seconds for real number F, said switch comprising:

• N input ports for receiving data and M output ports for transmitting data, for integers N and M;
• a plurality of queues, wherein each queue buffers data which arrives at a common one of said N input ports and which departs on a common one of said M output ports;
• wherein each GR traffic flow is associated with a guaranteed data-rate requirement, wherein each GR traffic flow is associated with one queue, and wherein data associated with a GR traffic flow is buffered in its associated queue;
• memory for storing a flow-schedule,
• wherein the flow-schedule determines which of the GR traffic flows associated with said queues, if any, have a reservation to transmit in each transmission interval in said scheduling frame;
• wherein the flow-schedule provides each of said GR traffic flows with a guaranteed number of reservations per scheduling frame sufficient to meet its guaranteed data-rate requirement,
• and wherein for each GR traffic flow with R reservations per scheduling frame for integer R, said flow-schedule provides said GR traffic flow with a least R/2−K reservations and at most R/2+K reservations in each half of said scheduling frame with a duration of F/2 seconds, where integer K is the bound on the service lead and service lag measured in reservations per scheduling frame, and wherein R is substantially larger than K.

A switch for switching a plurality of class-based (CB) traffic flows over a set output ports, given a scheduling frame comprising a plurality of transmission intervals defined over a duration of time of F seconds for real number F, said switch comprising:

• N input ports for receiving data and M output ports for transmitting data, for integers N and M;
• a plurality of class-queues, wherein each class-queue buffers data associated with one class of traffic;
• wherein each class-queue buffers data which arrives at a common one of said N input ports and departs on a common one of said M output ports;
• wherein each class-queue is associated with a guaranteed data-rate requirement;
• wherein each CB traffic flow is associated with one class of traffic and with one class-queue;
• wherein data associated with a CB traffic flow is buffered in its associated class-queue;
• memory far storing a class-schedule;
• wherein the class-schedule determines which of said class-queues, if any, has a reservation to transmit in each transmission interval in said scheduling frame;
• and
• wherein said class-schedule provides each of said class-queues with a guaranteed number of reservations per scheduling frame sufficient to meet its guaranteed data-rate requirement;
• and
• wherein for each class-queue with R reservations per scheduling frame for integer R>=2, said class-schedule provides that class-queue at least R/2−K reservations and at most R/2+K reservations in each half of said scheduling frame with duration F/2 seconds, wherein integer K is the bound on the service lead and service lag measured in reservations per scheduling frame, and wherein R is substantially larger than K.