Unified method and system for scheduling and discarding packets in computer networks

A computer-readable medium including a program for controlling a plurality of pipes in a computer network including at least one processor for a switch, the at least one processor having a queue, the plurality of pipes utilizing the queue for transmitting traffic through the switch, the program including instructions for:

• (a) allowing a minimum flow and a maximum flow to be set for each of the plurality of pipes;
• (b) determining if excess bandwidth exists for the queue;
• (c) determining a queue level for the queue;
• (d) determining an offered rate of the plurality of packets to the queue;
• (e) controlling a global transmit fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the global transmit fraction and the queue level are critically damped if the queue level is between at least a first queue level and a second queue level;
• (f) setting a transmit fraction for a flow for a pipe of the plurality of pipes to be a minimum of the global transmit fraction and a differential transmit fraction, the differential transmit fraction capable of linearly increasing the flow based on the minimum flow or the maximum flow if excess bandwidth exists and if the flow for the pipe of the plurality of pipes is less than the maximum flow for the pipe and capable of exponentially decreasing the flow for the pipe of the plurality of pipes based on the minimum flow or the maximum flow if excess bandwidth does not exist and the flow is greater than the minimum flow for the pipe, such that the traffic through the queue is stable;
• (g) controlling transmission of traffic to the queue based on the transmit fraction;
• and
• (h) utilizing a scheduler to control traffic from the queue.

A system for controlling a plurality of pipes in a computer network including at least one processor for a switch, the at least one processor having a queue, the plurality of pipes utilizing the queue for transmitting traffic through the switch, the system comprising:

• a queue for use by the plurality of pipes in transmitting traffic through the switch;
• an enqueuing mechanism, coupled with the queue, for controlling traffic through the switch using a minimum flow and a maximum flow set for each of the plurality of pipes by a user, the enqueuing mechanism for determining if excess bandwidth exists for the queue, for determining a queue level for the queue, and for determining an offered rate of the plurality of packets to the queue, the enqueuing mechanism also controlling a global transmit fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the global transmit fraction and the queue level are critically damped if the queue level is between at least a first queue level and a second queue level, the enqueuing mechanism also for setting a transmit fraction for a flow for a pipe of the plurality of pipes to be a minimum of the global transmit fraction and a differential transmit fraction, the differential transmit fraction capable of linearly increasing the flow based on the minimum flow or the maximum flow if excess bandwidth exists and if the flow for the pipe of the plurality of pipes is less than the maximum flow for the pipe and capable of exponentially decreasing the flow for the pipe of the plurality of pipes based on the minimum flow or the maximum flow if excess bandwidth does not exist and the flow is greater than the minimum flow for the pipe, such that the traffic through the queue is stable, the enqueuing mechanism also for controlling transmission of traffic to the queue based on the transmit fraction;
• and
• a scheduler to control traffic from the queue.

A processor for use with a switch in a computer network, the processor being coupled to a plurality of ports and a switch fabric, the processor for controlling a plurality of pipes for the switch fabric, the processor comprising:

• a queue for use by the plurality of pipes in transmitting traffic through the switch;
• an enqueuing mechanism, coupled with the queue, for controlling traffic through the switch using a minimum flow and a maximum flow set for each of the plurality of pipes by a user, the enqueuing mechanism for determining if excess bandwidth exists for the queue, for determining a queue level for the queue, and for determining an offered rate of the plurality of packets to the queue, the enqueuing mechanism also controlling a global transmit fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the global transmit fraction and the queue level are critically damped if the queue level is between at least a first queue level and a second queue level, the enqueuing mechanism also for setting a transmit fraction for a flow for a pipe of the plurality of pipes to be a minimum of the global transmit fraction and a differential transmit fraction, the differential transmit fraction capable of linearly increasing the flow based on the minimum flow or the maximum flow if excess bandwidth exists and if the flow for the pipe of the plurality of pipes is less than the maximum flow for the pipe and capable of exponentially decreasing the flow for the pipe of the plurality of pipes based on the minimum flow or the maximum flow if excess bandwidth does not exist and the flow is greater than the minimum flow for the pipe, such that the traffic through the queue is stable, the enqueuing mechanism also for controlling transmission of traffic to the queue based on the transmit fraction;
• and
• a scheduler to control traffic from the queue.

A switch for use in a computer network including a plurality of hosts, the switch comprising:

• a plurality of processors, each of the plurality of processors coupled with a plurality of ports, the plurality of ports coupled with a portion of the plurality of hosts, each of the plurality of processors including a queue, an enqueuing mechanism and a scheduler, the queue accepting traffic from a plurality of pipes in a computer network, the plurality of pipes coupling a portion of the plurality of ports coupled with a first processor and a portion of the plurality of ports coupled with a second processor, the enqueuing mechanism being coupled with the queue, for controlling traffic through the switch using a minimum flow and a maximum flow set for each of the plurality of pipes by a user, the enqueuing mechanism for determining if excess bandwidth exists for the queue, for determining a queue level for the queue, and for determining an offered rate of the plurality of packets to the queue, the enqueuing mechanism also controlling a global transmit fraction of the plurality of packets to the queue, based on the queue level and the offered rate, so that the global transmit fraction and the queue level are critically damped if the queue level is between at least a first queue level and a second queue level, the enqueuing mechanism also for setting a transmit fraction for a flow for a pipe of the plurality of pipes to be a minimum of the global transmit fraction and a differential transmit fraction, the differential transmit fraction capable of linearly increasing the flow based on the minimum flow or the maximum flow if excess bandwidth exists and if the flow for the pipe of the plurality of pipes is less than the maximum flow for the pipe and capable of exponentially decreasing the flow for the pipe of the plurality of pipes based on the minimum flow or the maximum flow if excess bandwidth does not exist and the flow is greater than the minimum flow for the pipe, such that the traffic through the queue is stable, the enqueuing mechanism also for controlling transmission of traffic to the queue based on the transmit fraction, the scheduler for controlling traffic from the queue;
• and
• a switch fabric coupling the plurality of processors.