ROFL: Routing on Flat Labels

M. Caesar, T. Condie, J. Kannan, K. Lakshminarayanan, I. Stoica, S. Shenker
Proceedings of the ACM SIGCOMM 2006 Conference, September 2006.

Presented by Kevin Mark Loken
Discussion by Wilson Fung

Brief Summary for the Paper

This paper presents a way how flat labels can replace IP as a network-layer protocol to separate network location and host identities in the . A routing mechanism based on Chord is used for both inter-domain and intra-domain routing. For intra-domain routing, a Chord overlay is formed within a autonomous system (AS). For inter-domain routing, multiple ASs forms a hierarchical tree and hosts in different ASs communicate via the use of external finger. ROFL touts itself as a flat label routing technique which is readily runnable on existing Internet hardware and preserves the ability to implement policies, such as peering and multihoming, for ISPs. Simulation of ROFL over collected data from real world ISPs shows that given sufficiently large cache in each router, ROFL can scale to a large number of hosts, indicating that the use of flat labels is not completely impractical for future Internet development.

Discussion Recap

The discussion for this paper is done together with the other three papers presented in the same section due to a lack of time and the intimate relationship between the four papers in presenting a redesign of the Internet using distributed hash table (DHT). DHT is currently a popular technique for peer-to-peer file sharing system and is mostly implemented on the application level. To use it to replace BGP, it needs to be able to implement routing policies, which is important for commercial ISPs. ROLF manages to achieve this based on the Chord routing algorithm. Another vulnerable part of the Internet is the DNS, which can be replaced by the distributed approach of UIA. And even if the DNS is not available, as long as one has the public key (UIA equivalent of IP) to a host, one can access the host. But then, how to obtain the key without the Internet is another problem. This brings up the question on why not using human-readable names as host identifiers...

Another question that came up is if all the root servers of the Internet are taken down by the terrorist, would the Internet be brought down? According Dr. Krasic, this is indeed a true threat to the current Internet. He also comment that stopping Internet no longer only bring inconvenience, but a life-threatening issue. Restoring the root servers after the attack is also difficult, as some of them are using proprietary inside with limited documentation. However, bringing down the root servers may not be so simple, as some of them are actually physically distributed cluster doing anycast.

Final part of the discussion centers around the practicality of using flat labels. While DHT is scalable by itself, the routing based on it (ROFL) is not completely scalable, especially in terms of latency. One of the student suggested the idea of adding proximity concept (rather than location information) to the host identifiers. Another comment from a student is that judging from the adoption rate of IPv6, the Internet community is just unwilling to change. Redesigning the Internet can very well be a political problem more than a technical problem.

Presentation Slides

Link for the PowerPoint file < pdf >

Submitted Questions

The overhead involved in host join and in failure appear to affect the overall performance. Is that true? If so, to what extent?

The paper states that a source route is cached by all routers on the path. Doesn't this affect scalability? Or is it only in the case of intradomain routing and so the number of source routes is maybe bounded?

Is this design really that different from what we have? All I see is a layered implementation of Chord which I guess will reduce packet overhead but we will increase the number of packets? Is increasing cache size a feasible option?

Why doesnt this paper prove that ROFL can match the performance of the current Internet?

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. What is your idea on this point ?

It seems to me like their approach mimics running an overlay network (e.g. Chord), designed to run atop IP, directly as the network layer. Wouldn't it perform better if we made all the network applications address their packets to node IDs (instead of IP addresses) of an overlay network overlayed over IP ? You could then maintain communication between nodes without bothering about the underlying IP addresses (because applications only use the node IDs). It seems to me this could allow both mobility, and efficient routing (because it's using structured IP routing underneath).

Even though authors also accept that the results for the experiments are not satisfying enough, I'm still wondering how close these results are to today's internet. For example joining a host would require about 100 million packets in a system with 10000 hosts and the graph shows a linear increase with number of hosts. I wonder how this scales up to 600 million hosts, if the increase is still linear (around 6 trillion packets) how close is it to numbers today?

Their experiments show that when there is enough router memory the stretch can be made near to one. It seems that they are talking about average stretch. What happens in case of worst case stretch?

Rather than using an overlay as is constructed in Chord, could we generate and use an overlay that's more aware of actual network topology, in order to help aleviate some of their performance issues?

What is the main reason that ROFL does not show high performance? What would be issues if ROFL is applied to real internet addressing?

The results they offered are very useful and clear to me. For example, Figure 5a shows us the total number of message sent during start-up as a function of the number of IDs in the AS. But the weird thing of this result is that it only shows up to 10,000 contrasting to millions of hosts of topologies mentioned before. Extrapolating to ten million would mean one hundred billion messages. How come this could happen over a short time period?

It is mentioned that routing directly on labels removes the need for a separate name resolution system. Therefore, if you have the identifier of the destination machine you want to contact, in their case the hash of a public key, you can just stamp that on a packet and send it. Now, wouldn't it require some name resolution service to map the human readable name of a web service to its network identifier ? Is it possible to have network identifiers that are human readable?

The authors suggest labels that are completely independent of locations and do not contain any semantics. This implies that there has to be a name resolving component of the system as the users would like to enter meaningful names to reach remote computers. How is it resolved? (without conciousness of location it looks like name resolving might be a burden)

Does applying this system, with all the benefits mentioned on page 1, necessitate abandoning human readable names?

At the beginning of section 4.1, how are the 2 conditions (a) and (b) different? If idb would be ida's successor in a merged ring, how could there be ids in between ida and idb?

In figure 3, why doesn't 16 have 20 as a successor?

For host joining mechaism, is it some problematic for multicast, and broadcast?

Is it just me or this paper is near impossible to understand the details (without having read the background papers which ROFL borrows the ideas from)?

What is AS? (It is first mentioned in the first paragraph of Section 2.1 without being defined.) I think it is a network? If so, how would you say the grouping of X's into ASes is done?

What do the authors mean by "up-hierarchy graph G_x, which consists of all ASes above X in the AS hierarchy"? They only define internal and external ASes, and if AS is a sub-network, how can there be hierarchy in a network design? I guess my problem is that I don't understand what AS is, so I can't tell what the authors are talking about.

The paper explains the mechanism of routing on the identification, not on the location information. However, the paper does not explain flat identifiers. What is the flat identifier? How are our internet addresses changed if the mechanism is adopted?

ROFL uses Chord-like routing scheme directly on the nodes and routers on Internet. I think this idea is really strange. When a packet is routed to the next router on the ring, it may pass over multiple other routers to arrive there. But it is also possible to go back to one of those routers again if the next hop is on the ring. What do you think of this part?

Does the system in its entirety provide complete support for mobility? Does host classification support or neglect this cause? Isn't clear to me!

How big a problem is mobility on the Internet? Aren't most nodes that need mobility ephemeral and hence not necessarily needing a persistent identity?

Is it really addressing the problem?

Do you think that bloom filters (and proximity fingers for that matter) resemble subnet masks? They both provide a way to quickly check a network for a certain address, aren't we trying to get away from these types of filters?

Section 6 points out that you can't really test a design in real internet conditions. How can we justify redesigning the internet without really being able to tell if a solution will work?

This paper takes a very different approach. Why doesnt it split identity from location rather than get rid of location altogether?

Precisely what advantages does ROFL provide, other than the elimination of the messy business of IP addresses? This reduction in the visibility of the network hierarchy - is it a good thing or a bad thing?

This paper is essentially a big thought experiment, with the added benefit of some concrete evaluation at the end. However, the authors are really trying to explore if their "big picture" idea of flat labels can be implemented within the current technological bounds of today's internet. Do you think that their approach could be made to scale well with further research, or do you think that there are systemic flaws in the approach that would prevent it from ever being used in practice (not considering political issues).

Is there a widely adopted new Internet?

Is the Abilene network a replacement to the not so great Internet we all use?

Do you think that ROFL can enable any worthwhile functionality which is not feasible in current internet?

What are the chances that such radical change will ever be adopted? With our reliance of the internet in it's current form, it find it hard to foresee such a drastic change in the low level routing protocol.

The idea of separating location and identity is nothing new and I believe that it will only become more important due to the popularity of subscription based online services. Does separating identity and location introduce any security issues?

The primary argument seems to be that we should consider the general idea of routing without location information. Is it possible to build a system that gets the benefits they list, but that doesn't look an awful lot like what they've built? It seems like the idea, while it's proposed as being general, actually lends itself only to a very specific implementation that doesn't offer much in terms of performance.

ROFL and CHORD both seem to rely on the complete randomness of the hash function for a lot of its nice properties. Is it possible to have a completely random hash function which shows no clustering effects?

In a flat address space based scheme how does one do grouping? (i.e. how would one form subnets?)

Is network topology reflected for intra-domain routing? For inter-domain routing?
- Residential ISPs are slow even intra-domain.
- (Seems to be true for inter-domain routing)

One of the claimed benefits of a flat namespace is the support for mobility. Inter-domain routing is done by first routing to the domain. Does this imply that mobility is restricted to within the same domain? If not, what prevents performance from dropping if most nodes are mobile? Do the routes taken then do random traversals of the underlying network?