Multi-Stage Buffered Packet Switches

The Internet has become a fundamental driving force for a variety of information technologies due to its ever-growing ability to handle traffic, its ubiquitousness, and the services. New applications, such as sensor fusion, bio-informatics, grid computation, global data storage, and on-line video applications, are emerging. Common among these applications is their demand for a huge amount of bandwidth and a global packet switching infrastructure. In contrast to the success in increasing the raw bandwidth for terabit transmission capability using dense wavelength division multiplexing (DWDM) technology toward the end of last century, today’s electronic router technology may soon exhaust its capacity of a few terabit/s. To find a cost-effective way to build a router with a few tens of terabit or even petabit capacity will be the key to the continuing success of the next-generation Internet.

Many researchers have attempted to build high-speed large-capacity packet switches, which are often categorized into different architectures based on the placement of buffers, e.g., input-buffered, output-buffered, crosspoint-buffered, internal buffered, and combined input-output buffered.  Reference [1] addresses the basics, theories, architectures, and technologies to implement ATM switches, IP routers, and optical packet switches. One of promising architectures is a multi-stage buffered switch as shown in the figure below. It is very scalable and doesn’t require any arbitration if a flow control scheme is implemented between the stages.

 

One of the challenges for the multi-stage buffered switches is to resolve packet out-of-sequence problem because packets sent to different paths may experience different queuing delays. One way to avoid the packet out-of-sequence problem in the buffered multi-path switch fabric is to re-sequence packets at the output port. This re-sequencing scheme has been studied in many literatures. Another way to avoid the out-of-sequence problem is to send all packets belong to the same flow to the same path. This idea is attractive in the sense that the out-of-sequence problem is only counted for the packets belong to the same flow.
One problem of the static hashing scheme is the load imbalance. Since each flow may have different bandwidth, it is possible that one path is more congested than the other path. This creates the complexity of choosing proper paths to route packets from an input port to an output port. If paths are not properly chosen, the probability of internal block in the middle stage increases, adversely impacting switch performance. In order to make the loads of all paths comparable, we propose to use a dynamic hashing. In dynamic hashing, the input port maintains outstanding number of packets in the switch fabric for each flow. If there is an outstanding packet in the switch fabric, all the following packets belonging to the flow must be sent to the same path with the previous packet. Otherwise, they can be sent to any other path. Therefore, there is no need for packet re-sequencing circuitry at the output port. This scheme is more attractive than the re-sequencing scheme because the high-speed input port may have hundreds of thousands flows and the number of paths is only a few hundreds.
We have prototyped a 16x16 multi-stage buffered switch with line rate of 10 Gbit/s, as shown below. We are experimenting different load-balancing schemes by using the FGPA-based reconfigurable switch fabric.

 

Participating members: H. Jonathan Chao (chao@poly.edu), Sertac Artan (sartan@poly.edu)

[1] Broadband Packet Switching Technologies – A Practical Guide to ATM Switches and IP Routers, H. J. Chao, C. Lam, and E. Oki, John Wiley & Sons, Inc, Sep. 2001.
[2] H. J. Chao, Z. Jing, and K. Deng, PetaStar: A petabit photonic packet switch, in IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on High-Performance Optical/Electronic Switches/Routers for High-Speed Internet, vol. 21, no. 7, pp. 1096-1112, Sep. 2003.
[3] R. Rojas-Cessa, E. Oki, and H. J. Chao, Concurrent fault detection for a multiple-plane packet switch, in IEEE/ACM Trans. on Networking, vol. 11, no. 4, pp. 616-627, Aug. 2003.
[4] E. Oki, Z. Jing, R. Rojas-Cessa, and H J. Chao, Concurrent round-robin-based dispatching schemes for Clos-network switches, in IEEE/ACM Trans. on Networking, vol. 10, no. 6, pp. 830-844, Dec. 2002.
[5] H. J. Chao, Next generation routers, invited paper, IEEE Proceeding, vol. 90, no. 9, pp. 1518-1558, Sep. 2002.
[6] E. Oki, R. Rojas-Cessa, and H J. Chao, A pipeline-based maximal-sized matching scheme for high-speed input-buffered switches, in IEICE Trans. Commun, vol. E85-B, no. 7, pp. 1302-1311, July 2002.
[7] J. S. Park and H. J. Chao, Design and analysis of enhanced Abacus switch, Computer Communications, vol. 25, no. 6, pp. 577 – 589, April 2002.
[8] H. J. Chao and T. S. Wang, An optical interconnection network for terabit IP routers, IEEE Journal of Lightwave Technology, vol. 18, no. 12, pp. 2095-2112, Dec. 2000.