Paper Info
Title
Can an Overlay Compensate for a Careless Underlay?
Abstract
We investigate the ability of an overlay network to compensate for "careless" routing in the native network layer, i.e., for network-layer routes not optimized for a given cost function or traffic matrix. We consider cost/traffic-dependent, overlay rout- ing on top of an underlay routing based on randomly-generated, cost/traffic-independent link weights, and determine the extent to which overlay-over-careless-underlay can achieve performance close to that attainable when underlay routing is performed in an optimal cost/traffic-dependent ("careful") manner. We iden- tify three graph-theoretic metrics that collectively characterize the richness of the underlay network: the tightness (characteristic path length, or CPL), the thickness (cut average) and the weighted sum of node degrees. We find that only when the underlay graph is rich, the overlay can compensate for careless underlay. If net- work links have linear costs, we prove that overlay cost is a linear increasing function of CPL under some assumptions. Finally, we investigate heuristics (based on the notion of richness) for choos- ing a set of overlay nodes of fixed size that is likely to result in good overlay performance.
Year
DOI
Venue
2006
10.1109/INFOCOM.2006.323
INFOCOM
Keywords
Field
DocType
computer science,stability,cost function,network topology,overlay network,routing protocols
Link-state routing protocol,Static routing,Computer science,Computer network,Routing domain,Network topology,Underlay,Routing table,Overlay network,Routing protocol,Distributed computing
Conference
ISSN
ISBN
Citations 
0743-166X
1-4244-0221-2
12
PageRank 
References 
Authors
0.75
14
3
Name
Order
Citations
PageRank
Honggang Zhang11223108.55
Jim Kurose25307610.06
Don Towsley3186931951.05