|
Efficacy of Overlay Routing
| Introduction
| Methodology
| Results
| 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.
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) Resilient Overlay Network (RON):
http://nms.csail.mit.edu/ron/
|
|