Stochastic modeling approach for performance and dependability analysis of communication networks
LO
Vandana Gupta
Department of Mathematics
Submitted
in fulfillment of the requirements of the degree of Doctor of Philosophy
to the
Indian Institute of Technology Delhi
January 2011
Certificate
This is to certify that the thesis entitled "Stochastic modeling approach for perfor- mance and dependability analysis of communication networks" submitted by Ms.
Vandana Gupta to the Indian Institute of Technology Delhi, for the award of the Degree of Doctor of Philosophy, is a record of the original bona fide research work carried out by her under my supervision and guidance. The thesis has reached the standards fulfilling the requirements of the regulations relating to the degree.
The results contained in this thesis have not been submitted in part or full to any other university or institute for the award of any degree or diploma.
New Delhi Dr. S. Dharmaraja
January 2011 Supervisor
1
Acknowledgements
I am taking this opportunity to thank,individua(ty, alithose who have been associated in one way or the other, throughout my Ph.D work. First of all, I thank, the 9lfmighty God for his blessings on me which made me to reach this place and always providing me the best of everything.
I express my sincere gratitude to my Ph.D supervisor Dr. S. Dkarmaraja for his invaluable guid- ance and continuous encouragement. He has always been ea.tremelygenerous with his time, knowledge and ideas and allowed megreat freedom in this research. I would not have been able to accomplish this workwithout his constant encouragement, inspiring criticism and motivation.
I am very much thankful to Prof. Carey Williamson, University of Cagary, Canada and Prof.
viswanatkan i runackalam, University of Los Andes, Bogota, Colombia whose comments and sug- gestions were useful in this research. I acknowledge C.SIX. India for providing financialsupport during the research period. I thankjPDefhi authorities for providing the essentialfacilitiesfor pursuing the research.
I express my regards to Prof.
R; K.
Sharma, Head of the Department, Prof. i nshul7Kumar and Prof. B. Chandra, former Heads of the Department for their support. Special thanks to my SRC mem- hers, Prof. 51M. Gupta and Prof. B.S. Panda for spending their invaluable time during the discussionsiii
iv ACKNOWLEDGEMENTS
over seminars. I amgrateful to my pre-P/.D course instructors: Dr. Wagisk Skuk a, Dr. 9Viiladri Ckat- terjee and Dr. s'lparna Mehra. I express mygratitude towards Dr. i £k agabhusknam and Prof. O. P.
Sharma, who helped me a lot when I did teaching assistantship under them.
I thank, my batch mates: Sumit and Dinabandku for their wonderful companionship, especially during pre-P/.D course work. Special thanks to my batch mate Sumit and my senior colleague and department room mate Pooja for their support, encouragement, motivation and patient listening wken- ever I felt low.
I expressed my thanks to my senior colleagues: Dr. vaneeta Tindal, Dr. K.V 7Krishna, Dr. Anita Das, Dr. Skaity, Dr. Santa, Dr. Uç. Pandey, Dr. Jvfukesk, Dr. Geeta, Dr. i nulekka, Dr. Deepali, Dr. Reskma, Dr. 7(anckan, Dr Jvfegka, Dr. Pratidka, Balckand, Puneet, Dkirendra, who have helped me a lot to learn many things and used to encourage at times. It is a pleasure to acknowledge my junior colleagues: Afok varska and Deepti for providing a joyful atmosphere with their company. I am very thankful to my junior colleague BQes/lam for her co-operation, companionship and technical interactions. 5[eartfelt thanks to my friend Gaurav for encouraging and supporting me in difficult times during the research period. I thank,al my hostel friends: 91rjrmala, 7ulsi andPooja Srivastava with whom I had spend wonderfid time and earned a lot of ckeriskable moments.
I am greatly indebted to my parents Sri. S.D.g Gupta and Smt. Shashi Gupta, my brother Ravi, my mother-in-law Smt. 7(usum 7(/aitan, my sisters-in-law Dr. Divya and 9 ayna and my extendedfamily for their understanding, support, encouragement and motivation during the entire research period: And last but not the least, heartfelt thanks to my husband Deepak,7cJIaitan for his cooperation and support.
9%[cw Delhi vandana Gupta
Abstract
Computer and communications networks are key infrastructures of the information society, and have become an ever-increasing part of our daily lives. Future generation network technologies, architectures and protocols are hence required to overcome the limitations of the legacy networks and add new capabilities and services. The future communication networks should be ubiquitous, resilient and secure for which it is crucial to analyze its performance and dependability attributes.
The efficiency of communication networks depend critically on its performance and dependability attributes (e.g. availability, reliability, safety, integrity and main- tainability). Performance analysis of communication networks involves the charac- terization of network traffic and derives the QoS measures such as delay, throughput, utilization, etc. Dependability analysis of communication network involves the study of at least two of its attributes. The research work in this thesis focuses on applying the stochastic modeling approaches such as Markov modeling, stochastic reward net (SRN) modeling, semi-Markov processes, and fluid queues for computing various performance metrics and dependability attributes in terms of availability, reliability and safety.
We begin with a brief description of communication networks and its vari- ous aspects. Thereafter, a short account of mathematical modeling paradigms
v
vi ABSTRACT
used/suitable for performance and dependability analysis of communication net- works, like Markov modeling, stochastic reward nets, semi-Markov processes (SMP) and fluid queues is presented. We, next deal with the performance analysis of the IEEE 802.11 MAC protocol. A fluid queue approach to model the flow of informa- tion from one node to another (via any intermediate node) in a network based on the IEEE 802.11 protocol is presented. Using the fluid queue model, the steady-state distribution of the buffer content at any intermediate node is obtained. Certain per- formance measures relevant to a communication network such as average through- put, server utilization, expected buffer content and mean delay are also obtained at the fluid queue level. Further, an SRN formalism for the IEEE 802.11 bidirectional multi channel MAC protocol is presented to study the performance advantages of its two features, namely bidirectional channel reservation for TCP traffic, and multi channel operation, over the classic IEEE 802.11 protocol.
Next, we deal with the performance analysis of the TCP. An SRN model for the TCP flow mechanism in WLANs is presented. The model captures various aspects of the protocol algorithm such as congestion window evolution, slow start and congestion avoidance phases, TCP packet transmissions, management of packet losses due to time-out and due to triple duplicate ACKs. The performance metrics such as throughput and delay of the TCP traffic are obtained. We are also able to show an interesting unfairness problem in WLAN existing between the upload users and the download users using SRN modeling.
We then move on to the performance and dependability analysis of a VoIP net- work. An analytical framework of dependability model for VoIP is proposed which models the dependability attributes of availability, reliability and confidentiality in the presence of resource degradation and security breaches. The dependability model is developed using a stochastic process based on SMP because of the non-Markovian nature of the various events involved in the model. Next, we present a hierarchical analytical model which combines the reliability and performance of a server based
vii
VoIP system operating on a wireless network. At the top level of the hierarchy, there is a pure reliability model with component redundancies and software rejuvenation, and it also incorporates failure of multiple components at the same time. And at the lower level, there is a pure performance model from which the performance metrics of the VoIP system at each state of the top level reliability model is obtained.
Finally, we discuss the end-to-end connection delay in a VoIP network in detail.
And based on the various delay components, we present two different queueing
models to analyze the end-to-end VoIP connection delay in two different queueing
scenarios.
Contents
Certificate i
Acknowledgements iii
Abstract v
List of Figures xiii
List of Tables xv
List of Abbreviations xvii
1 Introduction 1
1.1 A perspective . . . 1
1.2 Introduction to communication networks . . . 3
1.3 Mathematical modeling paradigms . . . 6
1.4 Scope and contribution of the thesis . . . 17
2 Performance modeling of IEEE 802.11 wireless networks using fluid
queue 21
ix
x CONTENTS
2.1 Introduction . . . 21
2.2 Fluid model description . . . 24
2.3 Buffer occupancy distribution . . . 27
2.4 Performance metrics . . . 35
2.5 Numerical illustrations and observations . . . . . . 38
2.6 Conclusion and future work . . . 43
3 Performance modeling of bidirectional multi channel IEEE 802.11 MAC protocol 45 3.1 Introduction . . . 45
3.2 IEEE 802.11 MAC protocols . . . 48
3.2.1 Classic IEEE 802.11 MAC protocol . . . . . . . . . . . . . . . 48
3.2.2 Bidirectional multi channel MAC protocols . . . . 49
3.3 SRN models . . . 51
3.3.1 Model 1: IEEE 802.11b MAC . . . 51
3.3.2 Model 2: Bidirectional multi channel MAC . . . . 56
3.3.3 Channel scheduling strategies . . . 59
3.3.4 Model 3: Bi-MCMAC with random channel selection . . . . . 60
3.3.5 Model 4: Bi-MCMAC with fastest-channel-first selection . . . 61
3.4 Performance metrics . . . 63
3.5 Numerical illustration and observations . . . 66
3.6 Conclusion and future work . . . 70
4 Performance modeling of TCP Flow in WLANs 75 4.1 Introduction . . . 75
4.2 Background and related work . . . 77
4.3 SRN model description . . . 79
4.4 Performance metrics . . . 86
4.5 Numerical illustration and observations . . . 88
CONTENTS xi
4.6 Conclusion and future work . . . 92
5 Dependability modeling of a VoIP network in the presence of re- source degradation and security attacks 93 5.1 Introduction . . . 93
5.2 Dependability model description . . . 97
5.3 Steady-state analysis . . . 102
5.3.1 Dependability attributes . . . . .. . . 109
5.3.2 Simulation verification of analytical model . . . 110
5.3.3 Numerical illustration of steady-state results . . . 112
5.4 'Transient analysis . . . 116
5.5 Conclusion . . . 117
6 Reliability and performance modeling of a VoIP system with mul- tiple component failure 119 6.1 Introduction . . . . . . . 119
6.2 System description . . . . . . . 122
6.3 Reliability model . . . .. . . . . 124
6.4 Performance model . . . . . . . 131
6.5 Numerical illustration and observations . . . 135
6.6 Conclusion and future work . . . 137
7 Analytical modeling of end-to-end delay in a VoIP network 139 7.1 Introduction . . . 139
7.2 VoIP delay . . . 141
7.3 Queueing model for delay . . . 144
7.3.1 Model 1: Infinite capacity M/G/1 retrial queueing model with two types of customers and non-preemptive priority . . . 145
xii CONTENTS
7.3.2 Model 2: Infinite capacity M/G/1 queueing model with two types of customers and pre-emptive priority . . . 148 7.4 Numerical illustration and observations . . . 151 7.5 Conclusion . . . 152
Bibliography 155
Appendix 169
Bio-Data 21