Wormhole IP over ATM

Manolis Katevenis, Iakovos Mavroidis, Georgios Sapountzis, Eva Kalyvianaki, Ioannis Mavroidis, Georgios Glykopoulos, Georgios Kalokerinos, Spyros Lyberis, Michalis Ligerakis, Thanos Papathanasiou, Antonis Danalis, Fotis Kitsos, Vassilios Siris, Evangelos Markatos, and Stelios Sartzetakis

CARV-FORTH-ICS and CSD department of the UOC, Heraklion, Crete, Greece

Abstract: High speed switches and routers internally operate using fixed-size cells or segments; variable-size packets are segmented and later reassembled. Connectionless ATM was proposed [Barn97] to quickly carry IP packets segmented into cells (AAL5) using a number of hardware-managed ATM VC's. We show that this is analogous to wormhole routing. We modified (1998) this architecture to make it applicable to existing ATM equipment: we proposed a low-cost, single-input, single-output Wormhole IP Router that functions as a VP/VC translation filter between ATM subnetworks. When compared to IP routers, the proposed architecture features simpler hardware and lower latency. When compared to software-based IP-over-ATM techniques, the new architecture avoids the overheads of a large number of labels, or the delays of establishing new flows in software after the first few packets have suffered considerable latencies. We simulated (1998) a wormhole IP routing filter, showing that a few tens of hardware-managed VC's per outgoing VP usually suffice. We built (1999) and successfully tested a prototype, operating at 2x155 Mbps, using one FPGA and DRAM. Simple analysis shows that operation at 10 Gbps and beyond is feasible today (2001).

Keywords: IP over ATM, connectionless ATM, wormhole routing, gigabit router, wormhole IP, routing filter.

Introduction:

Speeding up the Internet is of capital importance; this will need some hardware assistance. Hardware switches operate best on fixed-size quanta, while IP packets, on the other hand, have a variable size. It is not the first time, though, that hardware is called upon to route variable-size packets at high speed: Wormhole Routers did precisely that, in the eighties, for multiprocessor interconnection networks. The same techniques are applicable today to the Internet.

IP is the uncontested protocol for data communications. At the same time, ATM technology finds widespread use, owing to its fixed-size "cells" that allow high-speed hardware switching, owing to the small size of these cells that allows fast preemption and hence low latency, and owing to its quality-of-service (QoS) architecture. IP can fruitfully run on top of ATM, thus getting the best of both worlds. This has been done in software, on general-purpose computers; we do it in hardware, at a lower cost and with a lower latency.

ATM has some similarity with wormhole routing, the most popular multiprocessor interconnection network technique of the eighties. Just like virtual channels in wormhole routing carry packets segmented into flits, a number of hardware-managed VC's in ATM can carry IP packets segmented into cells according to AAL-5; each VC is dedicated to one packet for the duration of that packet, and is afterwards reassigned to another packet, in hardware. This was proposed by Barnett [Barn97] and was named connectionless ATM.

This Project:

We modified the Barnett proposal to make it applicable to existing ATM equipment: we proposed a novel single-input, single-output Wormhole IP Router, that functions as a VP/VC translation filter between ATM subnetworks; fast IP routing lookups can be as in [GuLK98] or [MoSj98]. Such Wormhole IP over ATM Routing Filters, turn ATM networks into Gigabit IP Routers, appropriate for forwarding IP traffic at hardware-speed all the way from the local area through the backbone of the internet, while at the same time sharing the network with native-ATM traffic. The proposed wormhole IP routing filter has a number of advantages:

  • it works together with standard, existing ATM equipment;
  • it allows the co-existence and integration of both IP and native ATM traffic in the same networks;
  • the quality of service of native ATM traffic can stay unaffected by the added IP traffic, while IP can benefit from ATM's QoS capabilities;
  • for IP traffic, the system operates equivalently to a network of low-latency gigabit IP routers, while being a lot less expensive;
  • packet routing delay is minimized owing to virtual-cut-through routing --segmentation and reassembly delays at intermediate routers are eliminated;
  • packet routing delay is minimized for all packets --not just for the packets after a flow has been recognized, as in IP switching;
  • the number of pre-established connections (labels) is small and fixed, and does not grow with the size of the total network (as in tag switching), yet all packets are routed through pre-established connections.

Based on actual internet traces, we have shown by simulation that a few tens of hardware-managed VC's per outgoing VP suffice for all but 0.01% or less of the packets. We analyzed the hardware cost of a wormhole IP routing filter, and showed that it can be built at low cost: 10 off-the-shelf chips will do for 622 Mb/s operation; using pipelining, operation is feasible even at 10 Gb/s, today.

2x155 Mbps Wormhole IP Router Prototype We have built a first prototype of a bi-directional wormhole IP routing filter with two OC-3 ports (155 Mbps in each direction), which is shown on the right (for a larger photograph click here (JPEG, 150 KBytes)). Two 16-MByte DRAM SIMM's plug into the sockets on the right; they hold the two-level IP routing table and the ATM connection table. The datapath, the control FSM, and the VCout free list (bit map) are contained in the FPGA. The two optical fiber sockets and the two SONET/UTOPIA interfaces are on the left. The 6-layer PCB is 7 inches long by 5 inches wide. The routing delay is fixed, equal to about 2.5 microseconds plus SONET/UTOPIA conversion time, for all IP packets. We are currently testing this prototype by connecting it to our ATM and IP network.

Publications:

[Kate01] M. Katevenis, Iakovos Mavroidis, G. Sapountzis, E. Kalyvianaki, Ioannis Mavroidis, G. Glykopoulos: "Wormhole IP over (Connectionless) ATM", IEEE/ACM Transactions on Networking, to be published (expected: Oct. 2001). Preprint available in Postscript (800 KBytes) or gzip'ed Postscript (300 KBytes); © copyright 2001 IEEE.

Talk Transparencies: M. Katevenis: "Wormhole IP over ATM", GIGANET-1999 Workshop, Tel Aviv, Israel, March 1999. The transparencies are available with comments in HTML, or without the comments in Postscript (185 KBytes) or gzip'ed Postscript (24 KBytes); © copyright 1999 ICS-FORTH.

[Mavro99] Iakovos Mavroidis: "Hardware Implementation of a Routing Filter to support Wormhole IP over ATM", Technical Report FORTH-ICS/TR-258, ICS, FORTH, Heraklion, Crete, Greece, June 1999, 16 pages. Available in Postscript (780 KBytes) or gzip'ed Postscript (150 KBytes); © copyright 1999 ICS-FORTH.
This report describes, in detail, the routing filter prototype, including its overall organization, the datapath and the control sections of the FPGA, and the time schedule for accessing the external DRAM.

[Sapou99] G. Sapountzis: "IP Routing Table Organization and Management in the Wormhole IP Routing Filter", Technical Report FORTH-ICS/TR-257, ICS, FORTH, Heraklion, Crete, Greece, June 1999, 23 pages; Available in Postscript (520 KBytes) or gzip'ed Postscript (140 KBytes); © copyright 1999 ICS-FORTH.
This report, first, reviews the relevant bibliography and evaluates the proposed schemes for IP routing table (RT) organization; the metrics are set in compliance with the demands of the wormhole IP FPGA-based routing filter prototype. Next, we provide details on the route lookup operation and we analyze the complexity of the insert/delete prefix operations; a novel algorithm for extending the update engine to routing tables with more than 2 distinct prefix lengths is proposed. We also provide a thorough description of the datapath and control of the hardware blocks used in the system.

[Kate98] M. Katevenis, Iakovos Mavroidis, Ioannis Mavroidis, G. Glykopoulos: "Wormhole IP over (Connectionless) ATM", .I "ICS, FORTH, Heraklion, Crete, Greece, July 1998, 33 pages.  Postscript (440 KBytes), or gzip'ed Postscript (120 KBytes); © copyright 1998 ICS-FORTH.
This paper is similar to [Kate01]; [Kate98] contains the full, detailed simulation results and more details than [Kate01] on hardware analysis for 622 Mbps; on the other hand, [Kate98] was written before the implementaiton of the hardware prototype, and hence contains no information on that.

Main References:

[Barn97] R. Barnett (rbarn@westell.com): ``Connectionless ATM'', IEE Electronics & Communications Engineering Journal, Great Britain, October 1997, pp. 221-230.

[GuLK98] P. Gupta, S. Lin, N. McKeown: ``Routing Lookups in Hardware at Memory Access Speeds'', Proceedings of IEEE Infocom, San Francisco, CA USA, April 1998; Infocom98_lookup.ps or Infocom98_lookup.pdf

[MoSj98] Andreas Moestedt, Peter Sjodin: ``IP Address Lookup in Hardware for High-Speed Routing'', Proc. IEEE Hot Interconnects 6 Symposium, Stanford, California, USA, August 1998, pp. 31-39; http://www.sics.se/~am/HotI.ps

For a survey of (traditional) Wormhole Routing (much of which has to do with backpressure and is thus not relevant to this research), see: P. Mohapatra: ``Wormhole Routing Techniques for Directly Connected Multicomputer Systems'', ACM Computing Surveys, vol. 30, no. 3, Sep. 1998, pp. 374-410.