IP Routing Table Lookup at high speed and low cost, in hardware, is feasible, as has been proposed by other researchers. See: P. Gupta, S. Lin, N. McKeown: ``Routing Lookups in Hardware at Memory Access Speeds'', Proceedings of IEEE Infocom, San Francisco, CA USA, April 1998 (paper available in Postscript or in PDF format); or: 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. Both proposals follow a "brute-force" approach, exploiting the fact that RAM is inexpensive, today. Rather than just caching the most-recently-used table entries, they store the entire IP Routing Table in DRAM or SRAM. Instead of organizing the table as a tree with many levels, they make it have only two (Gupta/Lin/McKeown) or three to five (Moestedt/Sjodin) levels; thus, the IP Routing Table looks like a virtual-to-physical address translation table. Each IP Routing Lookup takes 2 to 5 RAM accesses. In our prototype, we use the Gupta/Lin/McKeown organization, with DRAM. In a higher-throughput system, we would use the Moestedt/Sjodin organization (possibly pipelined), with SRAM.
In Wormhole Routing, packets were segmented into fixed-size "flits". In ATM (AAL5) packets are segmented into fixed-size "cells". In our proposed system, as in virtual-channel wormhole routing, each network link carries multiple IP packets with their cells inteleaved in time. The cells of different packets are distiguished from each other based on their different VC number (blue, red, green cells and packets, in the figure). VC numbers can be reused, as illustrated with VC#1 in the figure: after packet1 has been fully transmitted, the same VC label can be used for the cells of another packet, packet4. In our system, VC labels are assigned by the upstream node, in hardware, without any time-consuming handshake with the downstream node. Thus, VC label assignment is fast and inexpensive, and we do it on an individual packet basis, without the need for any flow recognition: the two "blue" packets in the above figure are unrelated to each other --they do not need to belong to the same "flow". Under AAL5, the cells of two different packets on a specific VC are distinguished from each other via a specific combination of bits in the payload type indicator (PTI) field of the ATM cell header, which identifies the last cell of each packet.
Rather than making IP routers that function like wormhole routers, i.e. look like modified ATM switches, as was the Barnett proposal, we take advantage of existing ATM switches and networks, that provide the forwarding (switching) function. The only thing we need to add are "routing filters", i.e. devices with a single input and output port, that translate the VP/VC numbers of the ATM cells passing through them, based on the destination address of the IP packets that they see. These routing filters are simple and inexpensive, and they introduce very short delay because routing table lookups are fast (in hardware), and because cells are not reassembled into whole IP packets before being processed --instead, the equivalent of virtual cut-through routing is performed.
The basic purpose of the proposed system is to handle, at high speed and low cost, IP traffic over a wide area network (WAN) that is composed mostly or entirely of ATM switches and subnetworks. Using this transparency we will compare the proposed system to other methods for achieving the same goal, i.e. fast IP routing over ATM WAN's. First consider ATM LAN's, e.g. host1 talking (in IP) to host2 in the above figure. In this case, the problem of fast IP over ATM can be solved by maintaining pre-established, semi-permanent ATM connections from every port to every other port of the ATM subnetwork. Our proposed system has nothing to add to such an environment --it merely uses it. Next, consider the case of IP traffic over a (mostly) ATM WAN, like host1 talking to host3 or host4 in the above figure. Because this is a WAN (comparable to the entire Internet), the number of source-destination port pairs is huge. Thus, it is no longer feasible to maintain pre-established, semi-permanent ATM connections from every port to every other port of this ATM WAN.
To solve this problem, other IP-over-ATM systems follow various approaches. One approach introduces IP "routers" between ATM subnetworks (red boxes in the figure). If these are traditional IP routers, then they reassemble every single IP packet from ATM cells, process it, re-segment it, and forward it; by doing so, they either consitute bottlenecks of the system, or they are very expensive. If these are "IP switches", then they only perform the above expensive task for the first few packets of each "flow"; when a (long-lived) flow is recognized, a new ATM connection is set-up specifically for that flow. Under such "IP switching", the first few packets of each flow still suffer considerable delay; also, the set-up of new ATM connections for each flow, which is done in software, places considerable overhead on the system and risks to become a bottleneck. Another approach (topology-driven / tag-switching / MPLS) uses ATM connections that have been established for any packet that happens to be travelling in the same direction. However, the number of source-destination port pairs in a WAN is huge and ATM connections can only be established between a subset of these at any given time; when a packet arrives for a destination for which no ATM connection has been established, that packet suffers a long routing delay, and the same happens with other such packets until a new ATM connection is established (a lengthy process).
Our proposed system performs better than the above solutions, while being inexpensive. In our system, wormhole IP "routing filters" are introduced between ATM subnetworks, at the places of the red boxes in the above figure. All IP packets are routed with minimum delay --not just packets after a flow has been recognized-- owing to cut-through processing and hardware lookups. In addition, no new ATM connections are set-up at "run-time", besides the (semi) permanent connections that are pre-establisehd at system "boot-time".
Looking more closely, the proposed "wormhole IP over ATM routing filter" has one incoming and one outgoing link. It receives traffic (ATM cells) from a conventional ATM subnetwork, and feeds similar traffic into another such subnetwork. The size of each ATM subnetwork is arbitrary: it may be a single switch, or as large as one can afford for the desired permanent virtual paths to be pre-established. The traffic in the system consists of "native ATM" traffic and of IP packets that have been segmented into ATM cells according to AAL5. The fact that the network capacity is dynamically shared among the IP and the non-IP (native ATM) traffic is a distinct advantage of the system.
IP packet segmentation occurs at the original source host, or at the point of first entry into an ATM subnetwork; this segmentation is performed by conventional ATM network adapters. ATM cells are re-assembled into IP packets at their final destination host, or at the point of exit into a non-ATM subnetwork; such re-assembly is performed at conventional ATM network adapters. IP traffic arrives at the wormhole routing filter through a number of virtual paths (VP); there is one such pre-established VP arriving from each (IP capable) input port of the ATM subnetwork [for purposes of QoS differentiation, more than one VPs may be used]. Inside each of these VPs, throughout the ATM subnetwork, a relatively small number of VCs has been opened and pre-allocated for use by the wormhole IP over ATM system; the ATM subnetwork performs no further signaling operations on these permanent VP/VC connections, at system "run-time". The wormhole routing filter delivers ATM cells into a conventional ATM subnetwork. Cells belonging to IP packets are delivered into a number of pre-established, permanent VPs --one leading to each (IP capable) output port of the ATM subnetwork. Again, inside each such VP, a relatively small number of VCs has been opened and pre-allocated for use by the wormhole system; the routing filter's hardware assigns these VCs to individual packets, without any involvement of the ATM subnetwork signaling.
("Multiprotocol Encapsulation over AAL5", RFC 1483)
