27-07-2012, 04:10 PM
Selfish Overlay Network Creation and Maintenance
Selfish Overlay Network Creation and Maintenance.docx (Size: 21.67 KB / Downloads: 60)
Abstract:
A foundational issue underlying many overlay network applications ranging from routing to peer-to-peer file sharing is that of the network formation, i.e., folding new arrivals into an existing overlay, and rewiring to cope with changing network conditions. Previous work has considered the problem from two perspectives: devising practical heuristics for the case of cooperative peers and performing game-theoretic analysis for the case of selfish peers. In this paper, we unify the aforementioned thrusts by defining and studying the selfish neighbor selection (SNS) game and its application to overlay routing. At the heart of SNS stands the restriction that peers are allowed up to a certain number of neighbors. This makes SNS substantially different from existing network formation games that impose no bounds on peer degrees. Having bounded degrees has important practical consequences as it permits the creation of overlay structures that require $O(n)$ instead of $O(n^2)$link monitoring overhead. We show that a node's “best response” wiring strategy amounts to solving a $k$ -median problem on asymmetric distance. Best-response wirings have substantial practical utility as they permit selfish nodes to reap substantial performance benefits when connecting to overlays of nonselfish nodes. A more intricate consequence is that even nonselfish nodes can benefit from the existence of some selfish nodes since the latter, via their local optimizations, create a highly optimized backbone, upon which even simple heuristic wirings yield good performance. To capitalize on the above properties, we design, build, and deploy EGOIST, an SNS-inspired prototype overlay routing system for PlanetLab. We demonstrate that EGOIST outperforms existing heuristic overlays on a variet- - y of performance metrics, including delay, available bandwidth, and node utilization, while it remains competitive with an optimal but unscalable full-mesh overlay.
Algorithm Used:
Dijkstra’s algorithm
Dijkstra's algorithm solves the single-source shortest-path problem when all edges have non-negative weights. It is a greedy algorithm and similar to Prim's algorithm. Algorithm starts at the source vertex, s, it grows a tree, T, that ultimately spans all vertices reachable from S. Vertices are added to T in order of distance i.e., first S, then the vertex closest to S, then the next closest, and so on. Following implementation assumes that graph G is represented by adjacency lists.
Existing System:
In a typical overlay network, a node must select a fixed number (k) of immediate overlay neighbors for routing traffic. Previous work has considered this problem from two perspectives:
(1) Devising practical heuristics for specific applications in real deployments, such as bootstrapping by choosing the k closest links (e.g., in terms of TTL or IP prefix distance), or by choosing k random links in a P2P file-sharing system. Notice here that DHTs like Chord solve a different problem. They route queries, not data traffic. The latter is left to a separate subsystem that typically opens a direct connection to the target host.
(2) Providing abstractions of the underlying fundamental neighbor selection problem that are analytically tractable, especially via game theoretic analysis. To date, however, the bulk of the work and main results in this area have centered on strategic games where edges are undirected, access costs are based on hop-counts, and nodes have potentially unbounded degrees. While this existing body of work is extremely helpful for laying a theoretical foundation and for building intuition, it is not clear how or whether the guidance provided by this prior work generalizes to situations of practical interest, in which underlying assumptions in these prior studies are not satisfied. Another aspect not considered in previous work is the consideration of settings in which some or even most players do not play optimally – a setting which we believe to be typical. Interesting questions along these lines include an assessment of the advantage to a player from employing an optimizing strategy, when most other players .Do not, or more broadly, whether employing an optimizing strategy by a relatively small number of players could be enough to achieve global efficiency.
Proposed System:
In this Paper, Overlay networks are used for a variety of popular applications including routing , content distribution , peer-to-peer (P2P) file sharing and streaming , data-center applications , and online multi-player games . A foundational issue underlying many such overlay network applications is that of connectivity management. Connectivity management is called upon when having to wire a newcomer into the existing mesh of nodes (bootstrapping), or when having to rewire the links between overlay nodes to deal with churn and changing network conditions. Connectivity management is particularly challenging for overlay networks because overlays often consist of nodes that are distributed across multiple administrative domains, in which auditing or enforcing global behavior can be difficult or impossible. As such, these nodes may act selfishly and deviate from the default protocol, by utilizing knowledge they have about the network, to maximize the benefit they receive from it. Selfish behavior has been reported in studies relating to selfish (source) routing and free riding in P2P file sharing networks. Selfish behavior also has many implications for connectivity management. In particular, it creates additional incentives for nodes to rewire, not only for operational purposes (bootstrapping and substituting nodes that went offline), but also for seizing opportunities to incrementally maximize the local connection quality to the overlay. While much attention has been paid to the harmful downsides of selfish behavior in different settings , the impact of adopting selfish connectivity management techniques in real
overlay networks has been an open problem.
Module Description:
We start by relaxing and modifying some of the central modeling assumptions of previous work. In that regard, the central aspects of our model are:
1. Bounded Degree
2. Directed Edges
3. Non-uniform preference vectors
4. Selfish Neighbor Selection
Bounded Degree:
Most protocols used for implementing overlay routing or content sharing impose hard constraints on the maximum number of overlay neighbors. For example, in popular versions of BitTorrent a client may select up to 50 nodes from a neighbors’ list provided by the Tracker of a particular torrent file. In overlay routing systems, the number of immediate nodes has to be kept small so as to reduce the monitoring and reporting overhead imposed by the link-state routing protocol implemented at the overlay layer. Hard constraints on the number of first hop neighbors are also imposed in most P2P systems to address scalability issues, up-link fragmentation, and CPU consumption due to contention . Motivated by these systems, we explicitly model such hard constraints on node degrees. Notice that in the prior studies cited above, node degrees were implicitly bounded (as opposed to explicitly constrained) by virtue of the trade-off between the additional cost of setting up more links and the decreased communication distance achieved through the addition of new links. We also note that some of these earlier network creation games were proposed in the context of physical communication networks. In such networks, the cost of acquiring a link is instrumental to the design and operation of a critical infrastructure. Such concerns do not apply in the case of overlay networks such as those we consider in this paper.
Directed Edges:
Another important consideration in the settings we envision for our work relates to link directionality. Prior models have generally assumed bi-directional (undirected) links. This is an acceptable assumption that fits naturally with the unbounded node degree assumption for models that target physical telecommunication networks because actual wire-line communication links are almost exclusively bidirectional. In overlay settings we consider, this assumption needs to be relaxed since the fact that node v forwards traffic or requests to node u does not mean that node u may also forward traffic or requests to v. Undirected links are created by the establishment of two directed links.
Non-uniform preference vectors:
In our model, we supply each node with a vector that captures its local preference for all other destinations. In overlay routing such preference may capture the percentage of locally generated traffic that a node routes to each destination, and then the aggregation of all preference vectors would amount to a origin/destination traffic matrix. In P2P overlays such preference may amount to speculations from the local node about the quality of, or interest in, the content held by other nodes. Other considerations may also include subjective criteria such as the perceived capacity of the node, its geographic location, or its availability profile.
Selfish Neighbor Selection:
In a typical overlay network, a node must select a fixed number (k) of immediate overlay neighbors for routing traffic. Previous work has considered this problem from two perspectives:
(1) Devising practical heuristics for specific applications in real deployments, such as bootstrapping by choosing the k closest links (e.g., in terms of TTL or IP prefix distance), or by choosing k random links in a P2P file-sharing system. Notice here that DHTs like Chord solve a different problem. They route queries, not data traffic. The latter is left to a separate subsystem that typically opens a direct connection to the target host.
(2) Providing abstractions of the underlying fundamental neighbor selection problem that are analytically tractable, especially via game theoretic analysis. To date, however, the bulk of the work and main results in this area have centered on strategic games where edges are undirected, access costs are based on hop-counts, and nodes have potentially unbounded degrees. While this existing body of work is extremely helpful for laying a theoretical foundation and for building intuition, it is not clear how or whether the guidance provided by this prior work generalizes to situations of practical interest, in which underlying assumptions in these prior studies are not satisfied. Another aspect not considered in previous work is the consideration of settings in which some or even most players do not play optimally – a setting which we believe to be typical. Interesting questions along these lines include an assessment of the advantage to a player from employing an optimizing strategy, when most other players .Do not, or more broadly, whether employing an optimizing strategy by a relatively small number of players could be enough to achieve global efficiency.