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-ICS-FORTH and
CSD-UofCrete,
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.
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.
Published on the web, in
HTML, or
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;
http://tiny-tera.stanford.edu/~nickm/papers/
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.
[Up to the
Computer Architecture and VLSI Systems Division of ICS-FORTH]
© copyright ICS-FORTH, Crete, Greece.
Last updated: July 2001, by
M. Katevenis.
