The Peer-to-Peer network paradigm is drawing the attention of both final users
and researchers for its features. P2P networks shift from the classic client-server
approach to a high level of decentralization where there is no central control and
all the nodes should be able not only to require services, but to provide them to
other peers as well. While on one hand such high level of decentralization might
lead to interesting properties like scalability and fault tolerance, on the other hand
it implies many new problems to deal with.
A key feature of many P2P systems is openness, meaning that everybody is
potentially able to join a network with no need for subscription or payment systems.
The combination of openness and lack of central control makes it feasible for a user
to free-ride, that is to increase its own benefit by using services without allocating
resources to satisfy other peers’ requests. One of the main goals when designing
a P2P system is therefore to achieve cooperation between users. Given the nature
of P2P systems based on simple local interactions of many peers having partial
knowledge of the whole system, an interesting way to achieve desired properties on
a system scale might consist in obtaining them as emergent properties of the many
interactions occurring at local node level.
Two methods are typically used to face the problem of cooperation in P2P networks:
1) engineering emergent properties when designing the protocol; 2) study
the system as a game and apply Game Theory techniques, especially to find Nash
Equilibria in the game and to reach them making the system stable against possible
deviant behaviors. In this work we present an evolutionary framework to enforce
cooperative behaviour in P2P networks that is alternative to both the methods
mentioned above. Our approach is based on an evolutionary algorithm inspired by
computational sociology and evolutionary game theory, consisting in having each
peer periodically trying to copy another peer which is performing better.
The proposed algorithms, called SLAC and SLACER, draw inspiration from tag
systems originated in computational sociology, the main idea behind the algorithm
consists in having low performance nodes copying high performance ones. The
algorithm is run locally by every node and leads to an evolution of the network both
from the topology and from the nodes’ strategy point of view. Initial tests with a
simple Prisoners’ Dilemma application show how SLAC is able to bring the network
to a state of high cooperation independently from the initial network conditions.
Interesting results are obtained when studying the effect of cheating nodes on
SLAC algorithm. In fact in some cases selfish nodes rationally exploiting the system
for their own benefit can actually improve system performance from the cooperation
formation point of view.
The final step is to apply our results to more realistic scenarios. We put our
efforts in studying and improving the BitTorrent protocol. BitTorrent was chosen
not only for its popularity but because it has many points in common with SLAC and
SLACER algorithms, ranging from the game theoretical inspiration (tit-for-tat-like
mechanism) to the swarms topology.
We discovered fairness, meant as ratio between uploaded and downloaded data,
to be a weakness of the original BitTorrent protocol and we drew inspiration from the
knowledge of cooperation formation and maintenance mechanism derived from the
development and analysis of SLAC and SLACER, to improve fairness and tackle freeriding
and cheating in BitTorrent. We produced an extension of BitTorrent called
BitFair that has been evaluated through simulation and has shown the abilities of
enforcing fairness and tackling free-riding and cheating nodes.
| Identifer | oai:union.ndltd.org:unibo.it/oai:amsdottorato.cib.unibo.it:918 |
| Date | 28 April 2008 |
| Creators | Arteconi, Stefano <1979> |
| Contributors | Babaoglu, Ozalp |
| Publisher | Alma Mater Studiorum - Università di Bologna |
| Source Sets | Università di Bologna |
| Language | English |
| Detected Language | English |
| Type | Doctoral Thesis, PeerReviewed |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0023 seconds