Store-and-forward devices (e.g., switches and routers) are used in packet networks, such as the Internet, for directing traffic at interconnection points. These switches and routers include switching fabrics which range from a simple bus-based fabric to a fabric based on crossbar (or crosspoint) switching devices. The choice of fabric depends on the design parameters and requirements of the switch or router, such as the port rate, maximum number of ports in the system, performance requirements, reliability/availability requirements, packaging constraints, etc. Crossbar-based fabrics are the preferred choice for high-performance routers and switches because of their ability to provide high switching throughputs.
A typical switch or router contains a set of interfaces or ports, each of which connects to an external link. The interfaces generally reside on a set of circuit boards, called “line cards” or “port interface cards”. A packet arriving from an external link first passes through a port interface in the line card. The port interface may be a framer, a medium access control device, etc. The packet is then processed in a packet processor and traffic manager device, which provides the functions of forwarding, classification and queuing based on its class of service, etc. The switching fabric receives the packet and forwards it to the line card corresponding to its destination port (which may be more than one for a multicast packet being sent to multiple destinations). The switching fabric thus provides the re-configurable data paths over which packets can be transported from one port to another within the router or switch.
A general crossbar-based packet switching fabric consists of a crossbar switching matrix, a fabric scheduler, and input buffers to hold arriving packets. The crossbar matrix is logically organized as an array of N×N switching points, thus enabling any of the packets arriving at any of the N input ports to be switched to any of the N output ports. These switching points are configured in the fabric scheduler at packet boundaries. Typically, the packets are switched through the crossbar switching matrix in batches, where a batch consists of at most one packet selected from each input port in such a way that no more than one of the packets is destined for each output port.
In a general crossbar-based switching fabric, each of the packets arriving into one of the input buffers has a header containing the destination port number where it needs to be switched. The fabric scheduler periodically reads this information from the headers of the packets stored in the input buffers and schedules a new batch of packets to be transferred through the crossbar matrix. Because each of the output ports is distinct, the fabric scheduler can schedule all the packets in a batch (a maximum of N packets) for transfer in parallel across the crossbar switching matrix. While the packets from a batch are being transferred through the crossbar, the scheduler can select the packets to form the next batch, so that the transmission can be nearly continuous. At the end of each batch of packets, the fabric scheduler re-configures the crossbar switching matrix so as to connect each input port to the correct output port for the next packet.
Single crossbar switch fabrics are difficult to scale to a large number of ports because of the complexity of implementing a large crossbar matrix (the complexity is of the order of N2, where N is the number of ports); heat dissipation; and simultaneous-switching noise. Thus, large switching fabrics are achieved by cascading multiple crossbar modules in a multistage configuration.
When multicast packets are received by a store-and-forward device (e.g., switch, router), the store-and-forward device must copy the packets and transmit the packets to the specified destination ports. This replication function naturally belongs to the switch fabric of the router. The copying operation can be expensive in terms of internal resources of the router such as bandwidth and memory needed to store lookup tables. Look-up tables are utilized to determine how many copies of the packet need to be made and where the copies need to be transmitted to. A difficulty with handling multicast packets in a multistage switch fabric is the size of the lookup tables needed. The size of these tables increases both with the number of ports in the system and the number of distinct multicast groups that needs to be supported.