Vol. 59 n°11-12, nov.-dec. 2004
Traffic engineering and routing
Guest editors Prosper CHEMOUIL* and Erol GELENBE**
*France Télécom R&D
**Imperial College
A flow-based approach to modeling ADSL traffic on an IP backbone link
Nadia BEN AZZOUNA*, Fabrice CLÉROT*, Christine FRICKER**, Fabrice GUILLEMIN*
* France Telecom R&D, 2 Ave. P. Marzin, F-22300 Lannion France
** INRIA, Domaine de Voluceau, F-78150 Rocquencourt France
Abstract: Measurements from an Internet backbone link carrying TCP traffic towards different ADSL areas are analyzed in this paper. For traffic analysis, we adopt a flow-based approach and the popular mice/elephants dichotomy. The originality of the experimental data reported in this paper, when compared with previous measurements from very high speed backbone links, is that commercial traffic comprises a significant part due to peer-to-peer applications. This kind of traffic exhibits some remarkable properties in terms of mice, elephants and bit rates, which are thoroughly described in this paper. Global traffic is actually decomposed into several flow components on the basis of the mice/elephants dichotomy. Mice due p2p protocols and mice due to classical Internet applications such as HTTP, ftp, etc. are analyzed separately. It turns out that by adopting a suitable level of aggregation, global traffic can be described by means of usual tele-traffic models based on M/G/¥ queues with Weibullian service times. The global bit rate can then be approximated by the superposition of Gaussian processes perturbed by a white noise.
Key words: Teletraffic, Statistical analysis, Statistical model, TCP/IP, ADSL, Queue, Peer to peer networking, Spectral analysis, Power spectrum, Weibull distribution, Heterogeneous traffic.
Bandwidth sharing with heterogeneous flow sizes
Sem BORST*, **, ***, Rudesindo NÚÑEZ-QUEIJA*, **, Bert ZWART*,**
* CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands.
** Department of Mathematics & Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.
*** Bell Laboratories, Lucent Technologies, P.O. Box 636, Murray Hill, NJ 07974, USA.
Abstract: We consider a system with two heterogeneous traffic classes. The users from both classes randomly generate service requests, one class having light-tailed properties, the other one exhibiting heavy-tailed characteristics. The heterogeneity in service requirements reflects the extreme variability in flow sizes observed in the Internet, with a vast majority of small transfers ("mice") and a limited number of exceptionally large flows ("elephants"). The active traffic flows share the available bandwidth in a Processor-Sharing (PS) fashion. The PS discipline has emerged as a natural paradigm for modeling the flow-level performance of bandwidth- sharing protocols like TCP. The number of simultaneously active traffic flows is limited by a threshold on the maximum system occupancy. We obtain the exact asymptotics of the transfer delays incurred by the users from the light-tailed class. The results show that the threshold mechanism significantly reduces the detrimental performance impact of the heavy-tailed class.
Key words: Teletraffic, Heterogeneous traffic, Resource sharing, Statistical distribution, Decrease rate, Statistical model, Traffic control, Delay.
Dimensioning IP access links carrying data traffic
Thomas BONALD*, Philippe OLIVIER*, James ROBERTS*
* France Telecom R&D, 38-40, rue du Général Leclerc, 92794 Issy-les-Moulineaux Cedex 9, France
Abstract: This paper proposes simple dimensioning rules for high speed IP access links carrying data traffic. Assuming a finite source population and fair bandwidth sharing among user flows, we derive formulas relating capacity, demand and performance. These formulas allow link dimensioning for a target quality of service expressed in terms of useful per-flow throughput. They constitute a data traffic model equivalent of the Engset model for telephone access networks. Performance is shown to be largely independent of detailed traffic characteristics such as the statistical distributions of flow size and think time. Simple approximations are derived for two distinct performance regimes corresponding to transparency and saturation, respectively. Extensions to the basic model account for a heterogeneous user demand, unfair bandwidth sharing or different access rate classes. In any case, the key parameter for dimensioning is the offered traffic, defined as the average data rate a user would generate in the absence of congestion.
Key words: Teletraffic, Data communication, Access network, TCP/IP, Dimensioning, Quality of Service, Frequency band sharing, Elastic traffic, modeling.
Fair Internet traffic integration: network flow models and analysis
Peter KEY*, Laurent MASSOULIÉ*, Alan BAIN**, Frank KELLY**
* Microsoft Research, 7 J J Thomson Avenue, Cambridge CB3 0FB, UK.
** Statistical Laboratory, Centre for Mathematical Sciences, Wilberforce road, University of Cambridge, Cambridge CB3 0WB, UK.
Abstract: We use flow-level models to study the integration of two types of Internet traffic, elastic file transfers and streaming traffic. Previous studies have concentrated on just one type of traffic, such as the flow level models of Internet congestion control, where network capacity is dynamically shared between elastic file transfers, with a randomly varying number of such flows. We consider the addition of streaming traffic in two cases, under a fairness assumption that includes TCP-friendliness as a special case, and under certain admission control schemes. We establish sufficient conditions for stability, using a fluid model of the system. We also assess the impact of each traffic type on the other: file transfers are seen by streaming traffic as reducing the available capacity, whereas for file transfers the presence of streaming traffic amounts to replacing sharp capacity constraints by relaxed constraints. Simulation results suggest that the integration of streaming traffic and file transfers has a stabilizing effect on the variability of the number of flows present in the system.
Key words: Teletraffic, Heterogeneous traffic, Internet, Quality of Serice, Elastic traffic, Real time, Modeling, File transfer, Fairness.
I
AIMD-based online MPLS traffic engineering for TCP flows via distributed multi-path routing
Onur ALPARSLAN*, Nail AKAR*, Ezhan KARASAN*
* Electrical and Electronics Engineering Department, Bilkent University, Bilkent, Ankara 06800, Turkey
Abstract: With this paper, we propose a distributed online traffic engineering architecture for MPLS networks. In this architecture, a primary and secondary MPLS LSP are established from an ingress LSR to every other egress LSR. We propose to split the TCP traffic between the primary and secondary paths using a distributed mechanism based on ECN marking and AIMD-based rate control. Inspired by the random early detection mechanism for active queue management, we propose a random early reroute scheme to adaptively control the delay difference between the primary and secondary LSPs. Considering the adverse effect of packet reordering on TCP performance for packet-based load balancing schemes, we propose that the TCP splitting mechanism operates on a per-flow basis. Using flow-based models developed for Internet traffic and simulations, we show that flow-based distributed multi-path traffic engineering outperforms on a consistent basis the case of a single path in terms of per-flow goodputs. Due to the elimination of out-of-order packet arrivals, flow-based splitting also enhances TCP performance with respect to packet-based splitting especially for long TCP flows that are hit hard by packet reordering. We also compare and contrast two queuing architectures for differential treatment of data packets routed over primary and secondary LSPs in the MPLS data plane, namely first-in-first-out and strict priority queuing. We show through simulations that strict priority queuing is more effective and relatively more robust with respect to the changes in the traffic demand matrix than first-in-first-out queuing in the context of distributed multi-path routing.
Key words: Teletraffic, Internet, TCP/IP, Network routing, Resource sharing, Queue, Distributed system.
Optimizing IP networks in a hybrid IGP/MPLS environment
Eueung MULYANA*, Ulrich KILLAT*
* Department of Communication Networks, Hamburg University of Technology (TUHH), BA IIA, Denickestrasse 17, 21071 Hamburg, Germany
Abstract: In this paper, we consider a traffic engineering (TE) approach to IP networks in a hybrid IGP/MPLS environment. Though IGP (Interior Gateway Protocol) routing has proven its scalability and reliability, effective traffic engineering has been difficult to achieve in public IP networks because of the limited functional capabilities of conventional IP technologies. MPLS (Multi-Protocol Label Switching) on the one hand enhances the possibility to engineer traffic on IP networks by allowing explicit routes. But on the other hand it suffers from the scalability (N-square) problem. Hybrid IGP/MPLS approaches rely on IP native routing as much as possible and use MPLS only if necessary. In this work we propose a novel hybrid traffic engineering method based on genetic algorithms, which can be considered as an offline TE approach to handle long or medium-term traffic variations in the range days, weeks or months. In our approach the maximum number of hops an LSP (Label Switched Path) may take and the number of LSPs which are applied solely to improve the routing performance, are treated as constraints due to delay considerations and the complexity of management. We apply our method to the German scientific network (B-WiN) for which a traffic matrix is available and also to some other networks with a simple demand model. We will show results comparing this hybrid IGP/MPLS routing scenario with the result of pure IGP routing and that of a full mesh MPLS with and without traffic splitting.
Key words: Teletraffic, Network routing, IP, Telecommunication network, Traffic control, Genetic algorithm, Optimization.
QoS multicast routing with delay constraints
Hieu T. TRAN*, Richard J. HARRIS*
* RMIT University, Melbourne, Australia, Address : 459 Swanston Street, Melbourne, Victoria, Australia, 3001
Abstract: Proliferation of group-based real-time applications, such as online games and video conferencing has motivated research into QoS multicast routing. These types of applications require consideration of both source-to-destination delay (i.e., packet delay from the source to all destinations) and inter-destination delay variation (i.e., the difference in packet delay from the source to different destinations) constraints. In this paper, we formulate a new combined problem for delay partitioning and multicast routing with source-to-destination delay and inter-destination delay variation constraints in a QoS framework, where a delay dependent cost function is associated with each network link. After identifying the problem as NP-complete, we introduce a Genetic Algorithm (GA) based algorithm that computes a source-based multicast tree which satisfies both constraints with near-optimal cost. We compare different GA schemes using different selection operators and find that the combination of Steady State GA and Remainder Stochastic Sampling selection operator works best for our problem. Simulation results also show that our GA heuristic consistently perfornis better than several other simple heuristics.
Key words: Teletraffic, Network routing, Point multipoint communication, Quality of Service, Transit time, Real time, Genetic algorithm, Resource allocation, Heuristic method.
Analysis of flow transfer times in IEEE 802.11 wireless LANs
Remco LITJENS1, Frank ROIJERS1, Hans VAN DEN BERG1, 2, Richard J. BOUCHERIE3, Maria FLEUREN4
1. Knowledge Innovation Center, TNO Telecom, PO Box 5050, 2600 GB Delft, The Netherlands.
2. Department of Design and Analysis of Communication Systems, University of Twente, PO Box 217, 7500 AE Enschede, The Netherlands.
3. Department of Applied Mathematics, University of Twente, PO Box 217, 7500 AE Enschede, The Netherlands.
4. Business Innovation Center, TNO Telecom, PO Box 5050, 2600 GB Delft, The Netherlands.
Abstract: In this paper we present an integrated packet/flow level modelling approach for analysing flow throughputs and transfer times in IEEE 802.11 WLANs. It captures the statistical characteristics of the transmission of individual packets at the MAC layer and takes into account the system dynamics due to the initiation and completion of data flow transfers. In particular, at the flow level the system is modelled by a processor sharing type of queue, reflecting the IEEE 802.11 MAC design principle of distributing the transmission capacity fairly among the active flows. The integrated packet/flow level model is analytically tractable and yields a simple approximation for the throughput and flow transfer time. Extensive simulations show that the approximation is very accurate for a wide range of parameter settings. In addition, the simulation study confirms the attractive property following from our approximation that the expected flow transfer delay is insensitive to the flow size distribution (apart from its mean).
Key words:Wireless LAN, Transit time, Resource sharing, Packet transmission, Random multiprocess, Carrier detection, Collision detection.
Measurement-based admission control in UMTS
Salah-Eddine ELAYOUBI*, Tijani CHAHED*, Mazen TLAIS*, Abed-Ellatif SAMHAT*
* GET/Institut National des Telecommunications, 9 rue Charles Fourier - 91011 Evry Cedex - France.
Abstract: In this paper, we develop an efficient Call Admission Control (CAC) algorithm for UMTS systems. We first introduce the expressions that we developed for Signal-to-Interference (SIR) for both uplink and downlink, to obtain a novel CAC algorithm that takes into account, in addition to SIR constraints, the effects of mobility, coverage as well as the wired capacity behind the base station, for the uplink, and the maximal transmission power of the base station, for the downlink. As of its implementation, we investigate the measurement-based approach as a means to predict future, both handoff and new, call arrivals and thus manage different priority levels depending on a tunable coefficient. Compared to classical CAC algorithms, our CAC mechanism achieves better performance in terms of outage probability and QoS management.
Key words: UMTS, Traffic control, Cellular network, Signal interference, Call processing, Heterogeneous traffic, CDMA, Priority, Radio communication handover.
Network services and traffic engineering methods for supporting applications on the VTHD experimental gigabit network
Philippe CINQUIN1,Yves DEVILLERS2, Annie GRAVEY3, Elodie LARREUR4
1. TIMC-IMAG, UMR 5525 UJF-CNRS, Faculté de Médecine ; 38706 La Tronche cedex, France.
2. INRIA, Domaine de Voluceau-Rocquencourt, BP 105 ; 78153 Le Chesnay cedex, France.
3. GET/ENST Bretagne, Technopôle Brest Iroise, CS 83818 ; 29238 Brest cedex, France.
4. France Telecom, R&D Division, 38, rue du Général-Leclerc ; 92794 Issy les Moulineaux cedex 9, France.
Abstract: VTHD is a high-performance IP experimental network. This network and associated research projects have been partially funded by the French government through the French Research Network for Telecommunications (RNRT) in order to support the development of leading- edge network services on the one hand, and test a wide-scale deployment of advanced Internet applications on the other hand. This paper describes the network services that were deemed necessary to support the deployment of innovative applications, as well as several of the applications that have been experimented on the network. It also presents a selection of the traffic engineering methods and experiments that have been developed in the course of the VTHD related research projects. This article describes the collective works of members of the project partners, which are represented by the set of authors for the present paper.
Key words: Teletraffic, Telecommunication network, High rate, IP, Experimentation, Research program, Telecommunication service, Telecommunication application, Peer to peer networking, Active telecommunication network, Distributed processing, Telemedecine, Teleconference, Multiple service network, Telecommunication traf- fic control, Network routing.
