Digital networks have been developed to facilitate the transfer of information, including data and programs, among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modem networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnected pattern can allow for a number of paths to be available through the network from each computer system or other device which may transmit information as a source device, to another computer system or other device, which is to receive the information as a destination device, so that if congestion develops in particular regions of the network, or if components of the network become inoperative, information can be routed around the congested or inoperative portion of the network.
Information transferred from a source device to a destination device is generally transferred in the form of fixed-or variable-length packets, which are received by a switching node over one communication link connected thereto, and transmitted over another communication link to facilitate transfer of the packet to the destination device or another switching node along a path to the destination device. Each packet typically includes address information, including a source address that identifies the particular device that generated the packet, and a destination address that identifies the particular device or devices to receive the packet.
Typically, a switching node includes one or more input ports, each of which is connected to a communication link to receive packets, a plurality of output ports, each of which is connected to a communication link to transmit packets, and a “switching fabric” that couples packets from the input ports to the respective outport ports for transmission. After an input port receives a packet, it will typically buffer the packet, identify from the destination address the particular output port that is to transmit the packet and transfer the packet to the output port through the switching fabric. After the output port receives the packet, it (that is, the output port) will typically buffer the packet in a queue for transmission over the communication link connected thereto. While buffering and scheduling by the output port can provide for efficient packet transmission by the output port, since the output port can be kept continually busy, several problems can arise with output port buffering. Generally, each output port will effectively provide one queue for each input port, in which case the total number of queues provided by the switching node will be on the order of N2, where “N” is the number of input ports, which, in turn, corresponds to the, number of output ports, if, as is typical, each communication link provides for bi-directional transmission of packets. Thus, as “N,” the number of input/ouput ports, increases, the number of queues maintained by the output ports increases quadratically, at a much faster rate, and so output queuing does not scale well.
Instead of using output queuing of packets to be transmitted, switching nodes have been developed which can provide input queuing, in which packets are buffered and queued at the input ports. Only one queue is needed for each input port, and so, as the number of input (and output) ports increases, the number of queues increases at a linear rate, avoiding the quadratic increase with output queuing. However, input queuing results in much lower efficiency of usage of the switching fabric, since the input ports must, after buffering received packets, essentially contend and arbitrate for use of the switching fabric to facilitate transfer of the packets to the respective output ports for transmission.