Selective backpressure control for multistage switches

Abstract

A method and apparatus for applying selective backpressure to control a multi-stage interconnection network (MIN). At one or more stages in the MIN, local information is used to define a queue status parameter for each local queue in the fabric. At the egress linecard, the upstream queue status parameter is periodically combined with the egress linecard's output queue status to generate a queue-specific backpressure signal. The backpressure signal continuously indicates to the ingress linecard that a specific fabric queue or queues is experiencing congestion and that the ingress linecard should therefore slow down or stop sending additional packets to the affected queue. Status computation mechanisms, which are state machines in one embodiment of the present invention, are incorporated in each switch element in at least the last stage of the switch fabric. In an alternate embodiment, the ingress linecard further combines the backpressure signal with its own local queue status to influence the initial queuing decision. In another alternate embodiment, queue status calculating mechanisms are present within one or more stages further upstream from the last stage of the switch fabric. Queue status information from many stages can thus be scaleably combined with egress queue status to determine fabric congestion conditions efficiently and accurately in all queues.