Aouad, Hazar (2005) Transport of real time flows in a wireless IP network. PhD thesis Informatique et Réseaux, ENST - INFRES Informatique et Réseaux, ENST.

Full text available as: - thèse_soutenance.pdf ( 3864 Kb )

Licence: Copyright

Abstract

In this thesis, we study several implementation methods of the QoS (Quality of Service) in an IP network. Before starting our research, we will first reveal the various mechanisms of QoS which we will study in the thesis. MPLS (Multi Protocol Switching Label), DiffServ (Differentiated Services) and scheduling algorithms will form the basic mechanisms of our backbone network which we will study. In accordance with several other works, we define three classes of services to differentiate in the network. The first class includes voice flows. It requires a small delay and a reduced jitter. Flows of "critical data", requiring a low loss probability and a limited delay, form the second class. The third class, gathering the applications such as file transfer or email exchange, do not need any condition from the network.
As a first step, we model outgoing/entering flows of a mobile wireless network. We model the inter arrival law of the aggregation of the flows at the MAC (Medium Access Control) layer, entering the UTRAN (UMTS Terrestrial Radio Access Network) network, the UMTS (Mobile Universal Telecommunication Service) access network. The CDMA (Code Division Multiple Access) protocol used in this network, proposes different access probability according to the QoS required. We determine also the characterizing law of the inter arrival aggregated traffic leaving a WiFi (Wireless Fidelity) network, using the basic MAC 802.11 layer. For these two networks, we propose various models of aggregation of voice, Web, file transfer flow and a multiplexing of these various classes. We measure the precision of two distribution models to those created by the traces. The first distribution used is the MMPP (Markov Modulated Poisson Process) process which represents a Markovian model. We experimented two values of the states number: 2 and 4. The second law that we consider is the Gaussian law. Our results show that both the type of aggregate flows and the network used influence the resulting model.
In a second step, we develop the equations determining the stationary probabilities of a queue implementing a GPS (Generalised Processor Sharing) scheduler with three classes of services. By using the DiffServ mechanism to differentiate flows, we measure the QoS at the output of a single queue using WRR (Weighted Round Robin), one of the algorithms approximating GPS. We then plot the various curves of delays and loss probabilities observed at the output of this queue according to weight and the load created by each class. We apply the various conclusions of the choice of the parameters which we draw from one server to a whole network. Moreover, we add the traffic engineering capability of MPLS to quantify the gain added by each policy. From this work, we can generalize our observations which become valid as well on a queue as in a network.
In a third step, we develop a method of dynamic adaptation of the routing. We propose it in order to solve the problem with the variations of the delay distribution on the links forming the end to end path. This mechanism is based on network tomography techniques in order to estimate the delay distribution on the various sections of the paths observed. If the average delay on the used path remains greater of the  threshold for a time  than the average delay of another path, then, the mechanism initiates the procedure of path modification. The use of the MPLS protocol allows this mechanism to be flexible and fast.

References

[1]. A. Baiocchi, N.B. Melazzi, M. Listanti, A. Roveri, R. Winkler, "Loss performance analysis of an ATM multiplexer loaded with high-speed on-off sources", IEEE Journal on Selected Areas in Communications, Volume 9, Issue 3, Avril 1991.
[2]. A. Ibrahim, S. Tohmé, "Service Multiplexing and Resource Allocation in S-CDMA LEO Systems", Proceedings PIMRC, Lisboa, Portugal, 2002.
[3]. A. Parekh and R. Gallager. "A generalized processor sharing approach to flow control in integrated services networks: The single node case", IEEE/ACM Transactions on Networking, Juin 1993.
[4]. A. Sayenko, T. Hamalainen, J. Joutsensalo et J. Siltanen, "An adaptive approach to WFQ with the revenue criterion", Proceedings ISCC, 2003.
[5]. Abbas Ibrahim, "Protocoles d'accès multiple orientés qualité de service en constellation de satellite à orbite basse", Thèse, Télécom Paris [ ENST ], 2002.
[6]. Abhay K. Parekh et Robret G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case", IEEE/ACM Transaction on Networking, Vol 1, Issue 3, Juin 1993.
[7]. Ahsan Habib, Bharat Bhargava, "Network Tomography-based Unresponsive Flow Detection and Control". Proceedings of the Ninth IEEE Workshop on Future Trends of Distributed Computing Systems (FTDCS'03)
[8]. B. Davie, A. Charny, J.C.R. Bennett, K. Benson, J.Y. Le Boudec, W. Courtney, S. Davari, V. Firoiu et D. Stiliadis, "An Expedited Forwarding PHB (Per-Hop Behavior)", IETF RFC 3246, mai 2002.
[9]. Brendan J. Frey, "Graphical Models for Machine Learning and Digital Communication", MIT Press, Cambridge, Massachusetts, 1998.
[10]. CAIDA: Cooperative Association for Internet Data Analysis. Disponible: http://www.caida.org/tools/.
[11]. Chin-Chang Li; Shiao-Li Tsao; Meng Cheng Chen; Yeali Sun; Yueh-Min Huang; "Proportional delay differentiation service based on weighted fair queuing"
Proceedings IEEE Computer Communications and Networks Conference, Oct - 2000
[12]. D. Ferrari and D. Verma, "A scheme for real-time channel establishment in wide area networks," IEEE J. Select. Areas Commun., vol. 8, Avril 1990.
[13]. D. Grossman, "New Terminology and Clarifications for Diffserv", IETF RFC 3260, avril 2002.
[14]. D.C. Verma, H. Zhang, et D. Ferrari, "Delay jitter control for real-time communication in a packet switching network", Proceedings de TRICOMM '91.
[15]. D.P. Heyman, A. Tabatabai, T.V. Lakshman, "Statistical analysis and simulation study of video teleconference traffic in ATM networks", IEEE Transactions on Circuits and Systems for Video Technology, Volume 2, Issue 1, Mars 1992.
[16]. Dempster, Laird et Rubin , "Maximum Likelihood from Incomplete Data via the EM Algorithm", Journal of the Royal Statistical Society, Series B, 39, 1977.
[17]. E. Rosen, A. Viswanathan et R. Callon, "Multiprotocol Label Switching Architecture", IETF RFC 3031, janvier 2001.
[18]. E. Rosen, D. Tappan, G. Fedorkow, Y. Rekhter, D. Farinacci, T. Li, A. et Conta, "MPLS Label Stack Encoding", IETF RFC 3032, janvier 2001.
[19]. ETSI TR 101 112 V3.2.0 (1998-04) "Selection procedures for the choice of radio transmission technologies of the UMTS", Technical Report Universal Mobile Telecommunications System (UMTS); ETSI (UMTS 30.03 version 3.2.0).
[20]. ETSI, "Radio Equipment and Systems (RES); Trans-European Trucked Radio (TETRA); Voice + Data", ETS 300 392, Part I. Edition 1. 1996.
[21]. ETSI, Technical Specification, "Network architecture", 3G TS 23.002 V3.3.0 (2000-03) (Release 1999).
[22]. ETSI, UMTS technical report, "Selection procedure for the choice of radio transmission technologies of the UMTS", TR 101 112 V3.2.0 (1998).
[23]. F. Le Faucheur, L. Wu, B. Davie, S. Davari, P. Vaananen, R. Krishnan, P. Cheval et J. Heinanen, "Multi-Protocol Label Switching (MPLS) Support of Differentiated Services", IETF RFC 3270, mai 2002.
[24]. F. Natterer, "The Mathematics of Computerized Tomography", New-york:Wiley, 1986.
[25]. Gilad Koren, Dennis Shasha, "An optimal Scheduling Algorithm with Cometitive Factor for Real Time Systems", rapport interne du département informatique de l'université de new-york, Juillet 1991.
[26]. H. Aouad, A. Ibrahim, S. Tohmé, "UTRAN traffic parameters estimation", IEEE CCNC 2004.
[27]. H. Heffes, D. Lucantoni, "A Markov Modulated Characterization of Packetized Voice and Data Traffic and Related Statistical Multiplexer Performance", IEEE Journal on Selected Areas in Communications, Volume 4, Issue 6, Septembre 1986.
[28]. H. W. Lee, J.W. Mark, "ATM network traffic characterization using two types of on-off sources", INFOCOM, Avril 1993.
[29]. IEEE 8802.11-1999, "Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications," 1999.
[30]. J. Cao, D. Davis, S. Vander Wiel et B. Yu, "Time-variying network tomography: Router link data", J. Amer, Statist. Assoc, vol 95, 2000.
[31]. J. Heinanen, F. Baker, W. Weiss et J. Wroclawski, "Assured Forwarding PHB Group", IETF RFC 2597, Juin 1999.
[32]. J.C.R. Bennett et Hui Zhang, "Hierarchical packet fair queueing algorithms", IEEE/ACM Transactions on Networking , Vo 5, Issue 5, Octobre 1997.
[33]. J.C.R. Bennett et H. Zhang, "WF²Q: Worst-case Fair Weighted Fair Queuing", Proceedings INFOCOM, 1996.
[34]. K. Nichols, S. Blake, F. Baker et D. Black, "Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers", IETF RFC 2474, December 1998.
[35]. L. Zhang, "Virtual clock: a new traffic control algorithm for packet switching networks ", ACM SIGCOMM Computer Communication Review, Volume 20 Issue 4, Août 1990.
[36]. M. F. Neuts, "Structured Stochastic matrices of M/G/1 type and their applications", Marcel Dekker, New York, 1989.
[37]. M. Shreedhar et G. Varghese, "Efficient fair queuing using deficit round-robin", IEEE/ACM Transactions on Networking, Vol 4, Issue 3, Juin 1996.
[38]. M.F. Neuts, "Matrix geometric solutions in stochastic models: an algorithmic approach", Baltimore, MD: john Hopkins Univ. press, 1981.
[39]. Mark Coates, Alfred O. Hero III, Robert Nowak, and Bin Yu, "Internet tomography", IEEE SIGNAL PROCESSING MAGAZINE, Mai 2002.
[40]. Mark Coates, Robert Nowak, "Network Loss Inference Using Unicast end-to-end Measurement", ITC Seminar on IP Traffic, Measurement and Modelling, Monterey, CA, Sep 2000.
[41]. Mark Coates, Robert Nowak, "Network Tomography for internal delay estimation", proc. IEEE Int. conf. Acoust., Speech, Signal Process., salt lake city, UT, Mai 2001.
[42]. Multicast-based inference of network-internal characteristics (MINC), Disponible: http://gaia.cs.umass.edu/minc.
[43]. N. D. Wilson , R. Ganesh, K. Joseph, D. Raychaudhuri, "Packet CDMA versus Dynamic TDMA for Multiple Access on an Integrated Voice/Data PCN", IEEE Journal on Selected Areas in Communications, Volume 11, August 1993.
[44]. N.G. Duffield, J. Horowitz, F. Lo Presti et D. Towsley, "Multicast topology inference from end-to-end measurements", ITC Seminar on IP Traffic, Measurement and Modelling, Monterey, CA, Sep 2000.
[45]. N.G. Duffield, J. Horowitz, F. Lo Presti et D. Towsley, "Multicast topology inference from measured end-to-end loss", IEEE Trans. Inform. Theory, vol 48, Janvier 2002.
[46]. P. O'Sullivan, "A Statistical Perspective on Ill-posed Inverse Problems", Statistical Science, vol.1, no. 4, 1986.
[47]. R. Caceres, N. Duffield, J. Horowitz et D. Towsley, "Multicast-based inference of network-internal loss characteristics", IEEE Trans. Inform. Theory, vol. 45, Nov 1999.
[48]. R.J. Mammone, "Inverse Problems and Signal Processing", The digital signal processing handbook. CRC press, 1998.
[49]. RTP: A Transport Protocol for Real-Time Applications, janvier 1996. IETF RFC 1889.
[50]. S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang et W. Weiss, "An Architecture for Differentiated Services", IETF RFC 2475, December 1998.
[51]. S. H. Kang, D. K. Sung, "Two-state MMPP modelling of ATM superposed traffic streams based on the characterization of correlated interarrival times", Global Telecommunications Conference, 1995.
[52]. S. Keshav, "An Engineering Approach to Computer Networking", Reading, MA: Addison-Wesley, 1997.
[53]. S. Ratnassamy et S. McCanne, "Inference of multicast routing trees ans bottleneck bandwidths using end-to-end measurements", Proc. IEEE INFOCOM 1999.
[54]. S.J. Golestani, "A self-clocked fair queueing scheme for broadband applications", Proceedings de Infocom 94.
[55]. Tobias Rydén, "An EM algorithm for estimation in Markov-modulated Poisson processes", Computational Statistics & Data Analysis Volume 21, Issue 4, 1996
[56]. Tobias RYDÉN, "Parameter Estimation For Markov Modulated Poisson Processes", Stocastic Models, 1994.
[57]. Wilson, Ganesh, Joseph, Raychaudhuri, "Performance of cellular Packet CDMA in an Integrated Voice/Data Network", International Journal Wireless Information Networks, Volume 1, 1994.
[58]. Wolfgan Fischer, Kathleen Meir-Hellstern, "The Markov-modulated Poisson Process (MMPP) Coolbook", Performance Evaluation 18, 1992.

Table of content

Introduction - 1
1. Cadre générale - 1
2. Objectifs de la thèse - 3
3. Contributions de la thèse - 3
4. Plan de la thèse - 4
CHAPITRE 1 La garantie de la qualité de service dans un réseau IP - 6
1.1. Introduction - 6
1.2. Le protocole MPLS - 6
1.2.1. Entête MPLS - 8
1.2.2. Label Switch Path (LSP) - 8
1.2.2.1. La création des LSP - 9
1.2.2.2. Les méthodes de distribution de label - 9
1.2.2.3. Utilisation des LSP - 10
1.2.3. Application des LSP: Ingénierie de trafic MPLS - 11
1.3. La différenciation de service par DiffServ - 12
1.3.1. L'entête DiffServ - 12
1.3.2. Le traitement à l'entrée du réseau DiffServ - 13
1.4. La combinaison DiffServ et MPLS - 14
1.5. Algorithmes d'ordonnancement - 15
1.5.1. First In First Out (FIFO) - 16
1.5.2. Head Of the Line (HOL) - 16
1.5.3. Generalised Processor Sharing (GPS) et algorithmes à poids dérivés - 17
1.5.3.1. GPS - 17
1.5.3.2. Weighted Fair Queuing (WFQ) - 18
1.5.3.3. Worst-case Fair Weighted Fair Queuing (WF2Q) - 18
1.5.4. Round Robin (RR) et ses dérivées - 21
1.5.4.1. Weighted Round Robin (WRR) - 21
1.5.4.2. Deficit Round Robin (DRR) - 21
1.5.5. Les ordonnanceurs à temps - 21
1.5.5.1. Earliest Deadline First (EDF) - 22
1.5.5.2. Earliest Due Date (EDD) - 22
1.5.6. Comparaisons d'ordonnanceurs à poids - 23
1.6. Conclusion - 32
CHAPITRE 2 Modélisation du trafic agrégé sortant d'un réseau sans fil UTRAN ou 802.11 - 34
2.1. Le réseau UMTS - 35
2.1.1. L'architecture du réseau UMTS - 35
2.1.2. La technique CDMA - 36
2.1.3. Les services - 39
2.1.4. La fonction CAC - 39
2.1.5. Le contrôle de trafic - 40
2.1.6. Les applications utilisées - 41
2.1.6.1. Sous système voix - 41
2.1.6.1.1. Application voix (RTC) - 41
2.1.6.2. Sous système data - 42
2.1.6.2.1. Application web (ITC) - 42
2.1.6.2.2. Application transfert de fichiers (STC) - 44
2.2. Le réseau WiFi 802.11 - 45
2.2.1. Introduction - 45
2.2.2. Le protocole MAC 802.11 - 46
2.3. Modèle de flux - 48
2.3.1. Sources voix - 49
2.3.2. Sources web - 49
2.3.3. Sources de transfert des fichiers - 49
2.3.4. Multiplexage de service - 49
2.4. Agrégation de flux On/Off - 49
2.5. Méthodologie d'estimation - 51
2.5.1. Estimation MMPP - 51
2.5.2. Estimation Gaussienne - 53
2.6. Résultats - 53
2.6.1. Réseau UMTS - 53
2.6.1.1. Utilisateurs voix - 53
2.6.1.2. Utilisateurs Web - 55
2.6.1.3. Utilisateurs FTP - 56
2.6.1.4. Multiplexage d'utilisateurs voix Web et FTP - 57
2.6.2. Réseau 802.11 - 58
2.6.2.1. Utilisateurs voix - 58
2.6.2.2. Utilisateurs FTP - 61
2.6.2.3. Multiplexage d'utilisateurs voix et FTP - 63
2.7. Conclusion - 71
CHAPITRE 3 Amélioration des performances par la différenciation des classes - 73
3.1. Modèle analytique pour GPS avec trois classes de service - 73
3.2. Résultats pour trois classes de service - 77
3.2.1. M/M/1 avec trois classes de service - 78
3.2.2. M/Pareto/1 avec trois classes de service - 83
3.3. Les règles à tirer - 88
3.4. Application sur un réseau - 88
3.4.1. Le modèle du réseau - 88
3.4.2. Les Modèles de trafics - 90
3.4.3. Les paramètres des scénarios de simulations - 92
3.4.4. Les résultats - 93
3.4.4.1. Sans QoS - 94
3.4.4.2. Priorité "Head Of the Line" non préemptive - 95
3.4.4.3. WRR - 95
3.4.4.3.1. WRR avec poids EF/AF/BE: 6/3/1 - 96
3.4.4.3.2. WRR avec poids EF/AF/BE: 4/4/2 - 97
3.4.4.3.3. WRR avec poids EF/AF/BE: 6/3/1 et ingénierie de trafic - 97
3.4.4.4. CB-WRR: Class Based WRR - 99
3.4.4.4.1. Choix des poids du CB-WRR - 100
3.4.4.4.2. CB-WRR: Class Based WRR pour le cas 2 - 103
3.4.4.4.3. CB-WRR: Class Based WRR pour le cas 3 - 104
3.4.4.4.4. Interprétation des résultats - 104
3.4.5. Interprétation des résultats - 105
3.5. Conclusion - 105
CHAPITRE 4 Adaptation dynamique du chemin par la tomographie des réseaux - 106
4.1. La tomographie dans les réseaux - 106
4.1.1. Introduction - 106
4.1.2. L'inférence au niveau lien et au niveau émetteur/récepteur - 108
4.1.3. L'avantage du multicast - 110
4.2. Méthodes d'estimation du délai - 111
4.2.1. L'estimation complète - 111
4.2.2. Les limitations de l'algorithme - 113
4.2.3. L'estimation simplifiée - 115
4.3. Implémentation - 116
4.4. Validation - 117
4.4.1. Le réseau expérimental - 117
4.4.2. Comparaison des mesures et des estimations - 119
4.4.3. Le gain acquis par la source - 125
4.5. Ouvertures - 127
4.6. Conclusion - 128
Conclusions - 129
1. Conclusions générales - 129
2. Ouvertures et perspectives - 130
ANNEXE 1 : Estimation MMPP - 132
1. MLE: Maximum Likelihood Estimation - 132
2. Chaînes de Markov Cachées - 134
a. Définition - 134
b. Premier exemple de HMM: Pile ou Face - 134
c. Deuxième exemple de HMM: le modèle des balles dans l'urne - 135
d. Les éléments d'une HMM - 135
3. MLE pour les HMM - 135
4. L'algorithme EM (Expectation Maximization) - 136
5. Solution adoptée: utiliser l'algorithme EM pour MLE - 137
a. L'algorithme proprement dit - 137
b. Les valeurs initiales - 138
6. Exemple d'estimation - 141
ANNEXE 2 : Complexité des algorithmes - 144
1. La méthode complète - 144
2. La méthode simple - 144
ANNEXE 3 : Exemple de calcul des probabilités stationnaires pour l'ordonnanceur WRR - 146
ANNEXE 4 : Résultats complémentaires pour l'ordonnanceur WRR - 148
1. Les chaînes incluses - 148
2. L'évolution du délai - 161
3. L'évolution du taux de perte - 172
ANNEXE 5 : Résultats complémentaires de l'ordonnancement - 189
1. Performance de CB-WRR dans le cas 1 - 189
2. Performance de CB-WRR dans le cas 2 - 191
3. Performance de CB-WRR dans le cas 3 - 193
4. Performance des flux en fonction des ordonnanceurs - 195
a. Le taux de perte - 195
b. Le délai moyen - 196
Glossaire - 198
Publications - 200
Bibliographie - 201

Statistiques de consultation

Repository Staff Only: edit this item