A Routing Underlay for Overlay Networks

This paper proposed a new architecture element, a routing underlay, to facilitate overlay network gathering information. The philosophy is that underlay provides coarse-grain rather static information in large scale, while overlay performs frequent probes over a narrow set of nodes. The ultimate goal is to save the total cost of network probes, which are usually carried out by overlay applications separately. The paper also emphasizes the importance of layered service, which enables sharing topology information gathered in kernel layer among services provided by library layer.

The most important contribution of this paper seems to be the underlay idea itself. By abstracting common requirements from various overlay services, it is conceivable that building a shared architecture element can aggregate probes and thus reduce corresponding costs. However, the actual effectiveness is largely determined by how well different requirements coincide. For example, RON seems to need to gather detailed path information between every pair of nodes (from its N^2 complexity), while some other overlay services might just work well with coarse grain information. It would be helpful if the performance impact of using this underlay was evaluated for some representative overlay services.

Also, there are several other issues to be clarified:

1. The paper primarily uses AS as the granular, but how coarse (or fine) is AS? Disjoint paths found by checking the PG consisting of AS are truly separated, but does this approach miss a significant portion of disjoin paths, which might go through some same ASs?

2. The paper sort of use AS hop as a good measurement of distance. It mentions the shortest path being the path with smallest AS hops. However, it also mentions that AS hop is not a good indication of actual latency, while really causes ambiguity.

3. The effectiveness of the underlay also depends on the amount of network information it could gather. The approach suggested by author is to export BGP tables to the overlay nodes. Is this an issue from practice perspective?

4. Finally, not as important, this paper lacks details of its algorithms, which certainly causes difficulties in understanding.

Reviewed by Cheng Huang