23-02-2013, 04:41 PM
SELIFISH OVERLAY NETWORK CREATION AND MAINTANCE
SELIFISH OVERLAY NETWORK.pptx (Size: 185.96 KB / Downloads: 19)
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.
INTRODUCTION
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.
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.
disadvantages
Heuristic search algorithm isHard and expensive
It is Loosely structured
It does not allow a way to assess the quality of redesigns
PROPOSED SYSTEM
The previous results have shown that no simple heuristic strategy can keep up with the performance of best response across the entire range of considered scenarios. What is not clear, however, is whether it is practical to build overlays to support best response and how to incorporate additional metrics other than delay, e.g., bandwidth. It is also unclear what is the average performance gain when SNS wiring strategies are used in highly dynamic environments, whether such overlays are robust against churn, and whether they scale. We address the questions mentioned above by describing the design and implementation of EGOIST: an SNS-inspired prototype overlay routing network. EGOIST serves as a building block for the distributed construction of efficient and resilient overlays where both individual and social performance is close to optimal.