Vol. 66, n° 1-2, January-February 2011
Content available on SpringerLink
Prosper Chemouil, Orange Labs, France
Michael Menth, University of Wuerzburg, Germany
Deep Medhi, University of Missouri, Kansas City, USA
Fabrice Guillemin, Orange Labs, France
Prosper Chemouil1 · Michael Menth2 · Deep Medhi3 · Fabrice Guillemin1
1.Orange Labs, France
2.University of Wuerzburg, Germany
3.University of Missouri – Kansas City, USA
A new statistical approach to estimate global file populations from local observations in the eDonkey P2P file sharing system
Patrick Brown1 · Sanja Petrovic1
1. Orange Labs, Sophia-Antipolis, France
Abstract In this paper, we propose a new statistical approach, also known in biology under the name capture–recapture methods in order to estimate global population statistics from local observations. Evaluating population sizes in P2P systems has received much attention lately as these may be useful to set system parameters, to derive other system statistics, or to predict system performance. As these systems are very large, encompassing several millions of users and since they are highly distributed estimating population sizes is a challenging task. More precisely, we are interested in estimating the number of file replicas in the system, i.e., the size of the population of users possessing given files. To this end, we propose a capture–recapture method which is both computationally efficient and accurate. The method proposed allows deriving global population statistics from local and time-limited observations. We apply the method on a measurement data set of several days on a residential network. We compare the results obtained from direct counting procedures with those derived with the proposed methodology.
Keywords Population size estimation · Capture–recapture · Bayes theorem · Peer-to-peer systems
On the Interplay of Network Structure and Routing Strategies in Scale-Free Networks
Walid K. Ghamry1 · Khaled M. F. Elsayed2
1. Department of Informatics, National Research Center, Egypt
2. Department of Electronics and Communications Engineering, Cairo University, Egypt
Abstract In this paper, we examine how the structural characteristics of network topologies affect the network performance, and we examine the interplay between structural characteristics of network topologies and routing strategies. We consider routing strategies subject to practical constraints (router technology) and economic considerations (link costs) at layer 3. We propose two new routing methods suitable for implementation in large networks and examine various routing strategies (local, global, and hybrid) with tunable parameters and explore how they can enhance the network performance. We find that there exists an optimal range of values for the tunable parameters to achieve high network performance which depends on the structural properties of the network topology. We also show that our proposed routing scheme, which requires minimum local information, achieves high network performance.
Keywords Routing strategies · Network throughput · Network structure
On the Performance and Improvement of Alias Resolution Methods for Internet Core Networks
Santiago Garcia-Jimenez1 · Eduardo Magaña1 · Daniel Morató1 · Mikel Izal1
1. Universidad Publica de Navarra Depto. de Automatica, y Computacion Campus Arrosadia, Pamplona, Navarra Spain
Abstract The Internet is a huge interconnection of thousands of networks with different technologies, equipment, configurations, and administrative owners. This, added to the lack of public information about those individual infrastructures, makes it a difficult task to provide a so-called Internet map: a topological map with information of routers, interconnections between routers, and IP addressing configuration. Traditional topology discovery methods based on traceroutes only provide IP addresses in the path between end-nodes. Some of those IP addresses can belong to the same router, and this identification is made by alias resolution methods. Therefore, alias resolution allows to provide router-level map of the Internet with important applications in network simulation, protocol design, network management, network security, network service design, and geolocation. In this paper, alias resolution methods are analyzed in Internet core networks (GlobalNOC, Canet4, and Geant). This allows to identify peculiar behaviors in these core networks, improving alias resolution methods. Simultaneously, reduction methods are used to decrease the number of probing packets in alias resolution methods.
Keywords Internet topology – IP alias resolution – Reduction methods – Router identification
Compact Inter-Domain Routing under Real-World Constraints
NEC Laboratories Europe, Heidelberg, Germany
Abstract Due to the “natural” growth of the Internet, the scaling properties of today’s inter-domain routing system worsen at a steep rate. Certain operational practices and a number of limitations of the routing protocol itself further exacerbate the scalability problem. In order to address this threat, this paper introduces 2SIDR, a two-step inter-domain routing approach. 2SIDR aims at significantly reducing the state requirements of routers while minimizing the incurred path inflation due to the lack of full routing state. 2SIDR leverages insights from theoretical approaches termed compact routing. But instead of adhering to mathematical constraints 2SIDR takes practical constraints from Internet operations into consideration, i.e., data that is available in practice and business relationships. We call this practical compactness as it deliberately gives up mathematical bounds in order to satisfy real-world requirements. Two variants of 2SIDR were analyzed extensively based on multiple sources of data gathered from the Internet to construct an Internet-scale AS-level topology. Various aspects were analyzed such as the state/stretch trade-off and the effect of observed routing policies.
Keywords Inter-domain routing · Compact routing · Scalability · Stretch/state trade-off
Towards End-Host Based Identification of Competing Protocols against TCP in a Bottleneck Link
Abdul Serwadda1 · Idris A. Rai2
1. Faculty of Computing and Information Technology, Makerere University, Kampala, Uganda
2. College of Engineering and Sciences, Louisiana Tech University, Ruston, USA
Abstract Classical Transmission Control Protocol (TCP) designs have never considered the identity of the competing transport protocol as useful information to TCP sources in congestion control mechanisms. When competing against a TCP flow on a bottleneck link, a User Datagram Protocol (UDP) flow can unfairly occupy the entire link bandwidth and suffocate all TCP flows on the link. If it were possible for a TCP source to know the type of transport protocol that deprives it of link access, perhaps it would be better for the TCP source to react in a way which prevents total starvation. In this paper, we use coefficient of variation and power spectral density of throughput traces to identify the presence of UDP transport protocols that compete against TCP flows on bottleneck links. Our results show clear traits that differentiate the presence of competing UDP flows from TCP flows independent of round-trip times variations. Signatures that we identified include an increase in coefficient of variation whenever a competing UDP flow joins the bottleneck link for the first time, noisy spectral density representation of a TCP flow when competing against a UDP flow in the bottleneck link, and a dominant frequency with outstanding power in the presence of TCP competition only. In addition, the results show that signatures for congestion caused by competing UDP flows are different from signatures due to congestion caused by competing TCP flows regardless of their round-trip times. The results in this paper present the first steps towards development of more ’intelligent’ congestion control algorithms with added capability of knowing the identity of aggressor protocols against TCP, and subsequently using this additional information for rate control.
Keywords Bandwidth hogging · User Datagram Protocol · Transmission Control Protocol · Coefficient of variation · Power spectral density
Quality Assurance of Voice over WLANs (VoWLANs) with Differentiated Services
Badis Tebbani1 · Kamel Haddadou1 · Guy Pujolle1
1. Laboratory of Computer Science, University of Paris 6, Paris, France
Abstract Several technical issues make commercial and large voice over wireless local area network (VoWLAN) services difficult to provide. The most challenging issue when voice over Internet Protocol (VoIP) services are ran over IEEE 802.11-based WLANs is the bandwidth inefficiency due to the considerable overhead associated with WLAN packet transmission. In this work, we propose a session-based quality-of-service management architecture (SQoSMA) to overcome the low number of VoIP calls in IEEE 802.11 Wireless LANs and the negative effect of new call addition when the WLAN reaches its capacity. The SQoSMA combines data and control planes to detect VoWLAN QoS degradations and performs either an adaptive audio codec switching or a call stopping to fix VoWLAN issues in a differentiated services manner. In addition, our solution deals with user sessions information, by considering user priority (from its agreement) to guarantee a certain level of its multimedia applications. Performance evaluation using a real test-bed shows that call codec change and call stopping techniques can easily assure high-priority calls with acceptable call blocking probability.
Keywords QoS · VoIP · WLAN · IEEE 802.11 · Audio codec adaptation
All-Optical Multipoint-to-Point Routing in WDM Mesh Networks
Fen Zhou1&2 · Miklos Molnar3 · Bernard Cousin1&4
1. IRISA, Campus de Beaulieu, Rennes, France
2. INSA de Rennes, France
3. LIRMM, University Montpellier II, France
4. University of Rennes 1, Campus de Beaulieu, France
Abstract In this article, the routing and wavelength assignment (RWA) problem for supporting multipoint-to-point communications in all-optical WDM mesh networks is investigated. Two efficient algorithms, namely reverse shortest path tree routing (RSPT) and k-bounded edge disjoint path routing (EDPR), are proposed. We proved that the problem of minimizing the total cost while establishing a multipoint-to-point session can be solved in polynomial time of O(|V|log|V| + |V| + |E|) by the RSPT algorithm, where |V| and |E| denote the number of nodes and the number of edges in the network, respectively. Nevertheless, the solution provided by the EDPR algorithm produces a significant reduction in the maximum number of wavelengths required per link (i.e., the link stress) for a multipoint-to-point session compared to RSPT algorithm. EDPR algorithm can also approximate to the optimal total cost with a ratio of k. Simulations are done to assess these two algorithms. Numerical results demonstrate their efficiencies in supporting multipoint-to-point communications in all-optical WDM networks.
Keywords WDM networks · Multipoint-to-point communication · Routing and wavelength assignment (RWA) · Light-startree · Reverse shortest path tree (RSPT) · Edge disjoint path routing (EDPR)
Parametric Distributions of Connection Lengths for the Efficient Analysis of Fixed Access Network
Catherine Gloaguen1 · Florian Voss2 · Volker Schmidt2
1. Orange Labs, Issy les Moulineaux, France
2. Institute of Stochastics, Ulm University, Germany
Abstract The access network displays an important particularity that the locations of the network components strongly depend on geometrical features such as road systems and a city’s architecture. This paper deals with the distributions of point-to-point connection lengths that play a major role in current problems in the analysis and planning of networks. Using the mathematical framework of stochastic geometry to model both the road system and the locations of network nodes, we derive analytical formulas for distributions of connection lengths. These formulas depend explicitly on a few parameters that can be computed easily and fast avoiding time-consuming reconstructions. We validate the approach by a comparison with actual network data and show its adaptability by considering several policies for nodes location and examples of use.
Keywords Stochastic geometry · Palm calculus · Telecommunication networks · Communication systems · Communication system planning · Network planning
Maximum Weight Independent Sets in an Infinite Plane with Uni- and Bidirectional Interference Models
Jarno Nousiainen1 · Jorma Virtamo1 · Pasi Lassila1
1. Department of Communications and Networking, Aalto University, Finland
Abstract We study the maximum weight independent sets of links between nodes distributed randomly in an infinite plane. Different definitions of the weight of a link are considered, leading to slight variations of what is essentially a spatial reuse problem in wireless multihop networks. A simple interference model is assumed with the interference radius equaling the transmission radius. In addition to unidirectional interference from a transmitter to the receivers of other links, also an RTS/CTS-type bidirectional handshake is considered. We study both the case where the transmission radius is fixed and tunable through power control. With a fixed transmission radius, we derive asymptotic results for the low- and high-density regimes. The main contribution is in the numerical results for the maximum weight, establishing some previously unknown parameters of stochastic geometry. The results are obtained by the Moving Window Algorithm that is able to find the maximum weight independent set in a strip of limited height but unlimited length. By studying the results as a function of the height of the strip, we are able to extrapolate to the infinite plane.
Keywords Maximum weight independent set · Spatial reuse · Random geometric graph · Asymptotics · Wireless multihop network · Capacity