Jasleen Kaur

Efficacy of Overlay Routing

Research | Past Research Projects | Prototypes



            Recent studies have demonstrated the utility of alternate paths in improving connectivity of two end hosts. However studies that comprehensively evaluate the tradeoff between its effectiveness and overhead are lacking. In this study we carefully characterize and evaluate the trade-off between (1) the efficacies of alternate path routing in improving end-to-end delay and loss, and (2) the overheads introduced by alternate routing methodology. This helps us test the scalability of an overlay network. We studied the above trade-off under different parameter settings such as path sampling frequency, overlay-connectivity, and number of overlay hops etc. We find that changing epoch duration and connectivity helps reduce the overheads by a factor of 4 and 2 respectively with slight performance degradation.


           We emulate an overlay network by gathering ping data from a collection of nodes in a real wide-area network and then sub-sampling the data as appropriate to emulate an overlay network with the desired degree of logical connectivity between nodes. Each node in the network runs two programs: a ``ping'' module that emulates the probing mechanism in an overlay and a ``state exchange'' module that emulates mechanism used to propagate measurement data to other nodes.

             At the beginning of each epoch, the ping module collects ping measurements to all other nodes. It then summarizes this ping information and records it in a local file for off-line analysis. Following each 24 or 48 hour measurement period, data from the nodes is collected and analyzed. To emulate different average connectivity of nodes, the analysis considers only information that would be acquired about neighboring nodes. The analysis tool uses the ping summaries to compute, for each service metric such as delay and loss, all  "better" overlay routes to all other overlay nodes. Only those alternate paths are considered that use one of the neighbors as the next-hop. We also ran the ping module on each node and used a link state routing protocol to flood the summary of the measurements to all nodes. The bytes exchanged by this module was used to determine the state-exchange overhead.


We have plotted the normalized effect on the gain and overhead with varying connectivity and epoch size. The x axis is the connectivity. Y axis is epoch size and Z axis is gain and overhead. To compare the two we have normalized the two to begin from 1 at 100% connectivity and base epoch size.

             We observe that increasing the epoch size by 2 keeping the connectivity the same reduces the gain by 11% and the overheads by 50% . Also keeping the epoch the same and reducing the connectivity by 2 reduces the gains by 38% and the overheads by 78%. For this we can conclude that by increasing the epoch size by 2 and reducing the connectivity by half we can increase the overlay size by 4 times without much loss in gain. This figure can be used to study the tradeoffs between increasing or decreasing the various parameters to achieve required level of performance and overheads.



"Testing the Scalability of Overlay Routing Infrastructures", S. Rewaskar and J. Kaur, in Proceedings of the Fifth Passive and Active Measurements Workshop (PAM'04), Juan-les-Pins, France, April 2004. ( Presentation )


Other links