Efficient simulation of bandwidth allocation dynamics in P2P Networks
Francesca Lo Piccolo, Giuseppe Bianchi, Stefano Cassella · 2006
Fluid-flow simulation models of Peer-to-Peer (P2P) networks are an effective way to properly account for low-level network bottleneck details, meanwhile circumventing the scala- bility limits imposed by packet-based simulators. A fundamental component in a fluid-flow simulator is the algorithm for the computation of the achievable per-flow rate for several competing flows offered to a given network topology. This paper presents a novel efficient approach to compute, in an exact manner (i.e. with no approximations), the max-min fair rate allocation. Numerical results demonstrate that our proposed algorithm outperforms traditional max-min computation approaches by as much as a factor 100 for a million nodes network. I. INTRODUCTION A large number of P2P simulators has recently emerged. Most of them mainly focus on simulating the resource search phase and the related query message handling. This is the case of Aurora (1) and Serapis (2), which model the key an- nouncement, insert or request process of Freenet-like systems. Similarly, P2Psim (3), FreePastry (4) and Chord simulator (5) simulate only the DHT-based (Distributed Hash Table) search phase. A similar approach is employed in other general- purpose P2P simulators, such as Neurogrid (6), (7), 3LS (8), and Peersim (9), (10). Although the P2P query/search phases are undoubtedly representative of a P2P system, there is plenty of interest in quantitatively characterizing performance figures related to the resource distribution process among involved peers. All the previously mentioned simulation platforms are not suitable to this purpose, as they neglect the process of distributing data across peers. A thorough understanding of the P2P network dynamics calls for a proper realistic modeling of the time required to distribute data across peers. This is especially true in P2P file sharing systems, where the data delivery may last several hours, as in the case of Gbyte-sized movies, and may dramatically influence (as well as being in turns influenced by) the peer behavior, e.g. in terms of up-time and churn rate. For some systems, such as BitTorrent, the multi-source data chunk distribution phase is indeed the most significative one, particularly since the search process is fastly/trivially accom- plished due to the usage of centralized servers. Its effectiveness depends on the bandwidth available at each network node, and This work has been partially supported by the Italian Ministry for University and Research (MIUR) under the PRIN project FAMOUS (http://www. tnt.dist.unige.it/famous). it is shown to be affected by the presence of peers connected to the network via heterogeneous bandwidth links (11). Finally, different P2P systems may support bandwidth and/or queueing management policies at each peer (think for example about the release option in eMule), which may significantly impact the resource distribution speed across the network. To properly model the data distribution phase, GnutellaSim (12), (13) interfaces with the ns-2 (14) discrete event packet- based network simulator, which provides a very detailed packet-level simulation model of the underlying transport network. However, such a simulation model compromises the scalability of the resulting simulation, as only a few hundreds of nodes may be properly simulated in reasonable time with such a level of details. This not only contrasts with the typical size of a P2P network, where the number of nodes may easily reach the order of several hundred thousands, if not millions, but it may lead to meaningless performance figures, since the P2P network dynamics simulated in small-scale networks are hardly representative of large-scale P2P system deployments. In the attempt to properly account for network low-level bottleneck details, meanwhile avoiding the need to properly model and simulate a complete network topology, a frequent assumption, which will also be used throughout this paper, consists in modeling the rate bottlenecks as occurring only in the access part of the network. This assumption is employed in both analytical models appeared in the literature (11), (15) as well as in simulation programs such as (16) and (17). It is justified by the current bandwidth gap between access links and core network trunk, and by the empirical observation