31-05-2012, 03:41 PM
SELFISH OVERLAY NETWORK CREATION ANDMAINTENANCE
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.
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
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.
IMPLEMENTATION
Implementation is the stage of the project when the theoretical design is turned out into a working system. Thus it can be considered to be the most critical stage in achieving a successful new system and in giving the user, confidence that the new system will work and be effective.
The implementation stage involves careful planning, investigation of the existing system and it’s constraints on implementation, designing of methods to achieve changeover and evaluation of changeover methods.
Modules:
1. 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 here.
2. 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.
4. 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.
3. 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.
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.
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
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.
IMPLEMENTATION
Implementation is the stage of the project when the theoretical design is turned out into a working system. Thus it can be considered to be the most critical stage in achieving a successful new system and in giving the user, confidence that the new system will work and be effective.
The implementation stage involves careful planning, investigation of the existing system and it’s constraints on implementation, designing of methods to achieve changeover and evaluation of changeover methods.
Modules:
1. 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 here.
2. 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.
4. 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.
3. 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.