11.11.06
Review of ROFL: Routing on Flat Labels
Current Internet architecture has several limitations and to a large extent, these limitations stem from the structured addressing scheme used in the Internet. The Internet uses IP addresses to represent both the location as well as the identity of the nodes, and this design choice has been motivated partly by two reasons: i) when the Internet was developed, most of the participating nodes were static in location, therefore their location and identity were more or less the same, and ii) The hierarchical structured form of the IP addresses and the location information embedded within them, enables much scalable routing, and millions of addresses can be handled efficiently (the routing tables at each router remains small and easy to maintain).
With the rapid proliferation of mobile devices which are connected to the Internet, and with the introduction of multihoming in which a node may have multiple identities, the structured addressing of the current Internet appears to be problematic. As early as 1993, many have suggested that in any network architecture, host identity should be cleanly separated from the host’s location. Consequently, a large variety of such addressing schemes have been proposed, and most of these involve some form of resolution, where the host name is translated into the location at some point, which is used to deliver the data. In this paper, authors introduce a new network addressing architecture called ROFL, which takes a radically different approach in decoupling the identity from the location: ROFL gets rid of location altogether. Thus, a ROFL based network needs to route packets directly looking at the destination names, without any associated location information. Clearly, it appears to be a daunting challenge, and how such a design will scale to potentially billions of hosts. The authors recognize this challenge, and admit that they do not attempt to match the performance of the current Internet addressing and routing; rather they attempt to evaluate how far such a flat naming scheme will go, and is this feasible at all?
From a high level, the proposal borrows many ideas from DHT, where every participating node is assigned a unique ID along a circular namespace and thus is connected to a virtual overlay ring. Messages from one node to the other are routed using the notion of successor and predecessor, as they are used in Chord. However, the way ROFL is different from such overlay rings as Chord, is that in ROFL, there is no notion of virtual overlay built over an IP layer; rather ROFL builds a DHT like structure directly over the link layer. Thus, the routing protocol can not assume connectivity between every two nodes, rather the connectivity of a node to its successors and predecessors is ensured by employing the source routing between them. Thus, the DHT based node by node routing is carried out from the source node to the destination node, and between any two nodes along the route, source routing is carried out.
With such routing, a node needs to remember the list of all nodes along the source route originating from a host connected to it to its successor. Moreover, a node also needs to remember the route information of source routes of all hosts which traverses through it. Clearly, a node may have to store the source route information of potentially millions of hosts, which may severely affect the scalability. However, since the routes are chosen randomly, the expectation is that the route information will be uniformly distributed across nodes, and there is likely to be few hot spots.
Source route information are stored at the nodes (routers) and not on the host. Thus, in order for a host to setup a source route, it needs to register with the gateway router, with which it is directly connected. Authors argue that with a public-private key encryption, such a scheme will also avoid any address spoofing by the hosts. After a host registers itself with its hosting router, the ID of the host remains resident at the router, which also maintains the source route information to the host’s successor and predecessor nodes. Additionally, these routers also maintain routes to both the internal (within an AS) and the external successor. In order to efficiently handle mobile and static hosts, authors introduce two different classes of hosts, stable hosts, which are less likely to change their locations and ephemeral hosts, which are likely to frequently change their location. Hosts are classified to belong to one of these classes by a central authority. The way ephemeral hosts are handled is slightly different from the stable hosts in that, the ephemeral hosts can not act as the successor and predecessor of another IDs; there merely establish a path between themselves and their predecessor, which keeps a source route to the ephemeral host.
Once a global virtual ring is constructed within an AS, and the intra-domain routing is straightforward, and involves joining of hosts, caching of the source routes at the routers along various routes, and forwarding, which is greedy. Authors also argue that tear-down messages are used to easily recover from physical link failures, or host failures. Inter-domain routing is similar to the Intra-domain routing however, it additionally needs to the support hierarchical AS-level policies. Thus, routing rings are constructed for each AS, and they are merged in a hierarchical fashion. This leads to the existence of additional successors to the routing rings of the other ASes.
While, it appears to be feasible to build a ROFL based network, the primary concern is performance and scalability. Authors argue that the current technology is capable of implementing ROFL based networks which are as large in scale as the current Internet. In their evaluation, they have shown that, even with 600 million hosts, ROFL based network will only require 9 Mbits of fast memory per router to perform the routing. Moreover, they also show that the join overheads in terms of the number of messages needed per join is modest; also the joining times are only a few tens of millisecond. While these results seem convincing, there are some important concerns. For example, these overheads appear to be recurring; whenever a new host arrives, it needs to register with its resident router, ad the messages needs to be propagated. Moreover, such a joining mechanism may also be problematic for multicast, and broadcast. The authors also do not mention the size of the messages involved in the joining process. Another issue concerns with the complexity involved in quickly updating the route caches of all routers along the route.
While the problems with join may be tolerable, there appears to be more serious issues with the efficiency of the routing. Since routing in ROFL is essentially similar to those which are used in the overlay rings, it is likely to be equally inefficient. For instance, since the host names have no relevance with the host location, it is possible that the physical route taken indeed contains many more hops than the shortest route. Moreover, due to the use of source routing, there may be additional routing inefficiency, e.g. every message in the data path will have to carry information about all nodes along the route. While authors argue that the stretch in ROFL is less than 2, i.e. the average route undergoes fewer than two times the optimal number of hops, this metric may be slightly misleading, because the number of hops does not have much direct correlation to the end to end latency. In my opinion, actual stretch in terms of delay may increases dramatically. Also, authors do not talk about the worst-case numbers in terms of latency.
While this paper is a first stab at a radically different clean slate design approach, which attempts to address many recent problems in the current internet, at this point, it appears difficult to make a case in favor of the implementation of ROFL. It is not clear, how the benefits of ROFL will overpower its obvious limitations in terms of scalability. The number of hosts connected to the Internet is likely to grow continuously in which case ROFL based network may further suffer from the performance and scalability issues.
jon.turner said,
November 12, 2006 at 10:25 am
It seems to me that the authors made a poor design choice by using virtual virtual nodes for each host. This makes the impact of joins and leaves much greater than it needs to be. An alternative would be to view the host-ids as data to be stored in the DHT, with the routers acting as the “servers” that store the keys, along with a source route to the hosting router for the given host. With this approach, when a host adds, we just need to inform the successor router (relative to its id), by sending a message to it using the DHT routing. As the packet passes through the network, the reverse source route is stored in the packet, allowing the successor-router to store a copy of the route back to the host.
Then, whenever the successor-router receives a packet for that host-id, it just retrieves the source route from the table. This makes things much more stable, since routers come and go a lot less frequently than hosts. The only drawback I can see is that it implies that in a network with n routers and N hosts, the average router must store source routes N/n hosts. On the other hand, their scheme requires routers to maintain an average of N/n virtual nodes in the ring, which is going to require more space and be much less stable.
It seems to me that this should also produce shorter routes. Instead of log(N) DHT hops, you get 1+log(n), which is smaller so long as n