Peer-to-peer and overlay networks allow routing to be controlled at the application layer. Consider several independent overlay flows, each with a set of available overlay routes to send their data on. If they each select the route with the most available bandwidth, i.e., they are "greedy", a significant degree of instability could result, leading to degraded performance. We investigate this possibility, and a wide variety of factors that affect routing performance, by simulations. We find that some measure of "restraint" is crucial for obtaining acceptable performance of route selection in such scenarios. Specifically, we investigate three forms of restraint -- randomization of route selection, utilizing an appropriate hysteresis threshold when switching routes, and increasing the time intervals between route-change considerations.
Our results indicate that randomization can significantly reduce loss-rates (typically by half) -- more importantly, it is sufficient to utilize load information from a small subset of overlay paths to obtain such results. This approach would significantly reduce the path measurement overhead imposed by applications. Secondly, we find that appropriate values of the hysteresis threshold (H) can be heavily dependent on the parameters of the system. Therefore we propose that flows determine H dynamically; we suggest and evaluate an algorithm based on multiplicative increase and decrease of H for this purpose. This algorithm is found to reduce loss rates of the basic greedy method by at least half. Finally, we investigate the scenario when a subset of unrestrained overlay flows (the "cheaters") select the best of all available routes, while the remainder use suitable hysteresis thresholds or randomization.
Dynamics of Simultaneous Overlay Network Routing
Computer Science Division, University of California at Berkeley, Berkeley, California, November 2003
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
The Engineering Library
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).