«BY VIJAY RAMAN DISSERTATION Submitted in partial fulﬁllment of the requirements for the degree of Doctor of Philosophy in Electrical and Computer ...»
c 2012 Vijay Raman
TRAFFIC-AWARE CHANNEL ALLOCATION AND ROUTING IN
MULTICHANNEL, MULTI-RADIO WIRELESS NETWORKS
Submitted in partial fulﬁllment of the requirements
for the degree of Doctor of Philosophy in Electrical and Computer Engineering
in the Graduate College of the University of Illinois at Urbana-Champaign, 2012 Urbana, Illinois
Professor Nitin Vaidya, Chair Assistant Professor Matthew Caesar Assistant Professor Sayan Mitra Professor Klara Nahrstedt Professor David Nicol
ABSTRACTModern day wireless network applications exhibit varying service demands to satisfy user requirements, while diﬀering in the nature of traﬃc they gen- erate. Future wireless networks should, therefore, be capable of adapting to the heterogeneous traﬃc characteristics, by eﬃciently utilizing the expen- sive radio resources. In this dissertation, we concentrate on three important problems in existing wireless networks and propose algorithms for addressing them.
As the ﬁrst problem, we focus on the eﬀect of rate-independent MAC overheads in random access protocols such as carrier sensing, backoﬀ, and ﬁxed rate header transmissions. These overheads become prominent in short packets that are transmitted at high data rates. We address this problem by partitioning the transmission spectrum into a narrow channel and a wide channel. The narrow channel is used for transmitting the short packets and the wide channel is used for transmitting the longer packets. We propose a protocol called WiSP (channel Width Selection based on Packet size) to estimate the appropriate channel widths depending on the relative traﬃc load involving short and long packets in the network.
Next, we address the problem of channel switching delay in multichan- nel, multihop wireless networks. Future networks can beneﬁt from using multiple channels simultaneously within a network. However, to maintain connectivity between various wireless nodes, the wireless radios may have to switch between channels. Due to both software and hardware restrictions, switching channels incur signiﬁcant delay, which can be detrimental to many delay-sensitive, real-time applications, such as VoIP and interactive gaming.
To address this, we propose SHORT (Static-Hybrid approach for rOuting Real Time applications), a joint channel allocation and routing algorithm for ﬁnding delay eﬃcient routes for real-time applications without signiﬁcantly aﬀecting the performance of non-real time applications.
ii Finally, we explore the possibility of using variable width channels in a multihop wireless network for eﬃcient spectrum utilization. We propose a variable width channel allocation scheme that adjusts the channel widths for the nodes during routing proportional to the rate requirement of the ﬂows.
The nodes also perform an admission control mechanism to determine if there is enough spectrum to satisfy the rate requirement.
The last ﬁve years at Illinois has been a great experience, where I got to meet several inﬂuential people. Many of them played a signiﬁcant role in encouraging my work and assisting me whenever I felt low. I would like to use this space to thank all of them to my heart’s content.
First and foremost, I would like to thank my adviser Prof. Nitin Vaidya.
His guidance and assistance, all through my research, provided me with all the positive energy whenever I needed. His straightforward remarks and timely suggestions proved critical throughout my research.
I would next like to thank Prof. Matthew Caesar for all the time he spent with me for my class research project. His encouraging words and able guidance helped me to come up with interesting ideas that eventually led me to my Ph.D. research topic that is presented in the Chapter 5 of this dissertation.
Next, I would like to thank my dissertation committee members, Prof. David Nicol, Prof. Klara Nahrstedt, and Prof. Sayan Mitra for agreeing to be part of my ﬁnal exam process. Their comments and suggestions helped me improve my research topic and project it in a perspective suitable for a wider audience.
I thank Prof. Romit Roy Choudhury for giving me a chance to explore a wider research domain. I appreciate his SyNRG group for helping me to think diﬀerently and gain a diﬀerent attitude on research. Visiting Duke University truly played an important role in developing the breadth of my research.
I wish to thank my collaborators Prof. Fan Wu, Dr. Nikhil Singh, Brian Proulx, and Rakesh Kumar for sharing their thoughts and ideas that proved vital to our research goals. I would like to thank my previous lab-mates and visitors, Dr. Vartika Bhandari, Dr. Cheolgi Kim, Dr. Helen Xi, Dr. Simone Merlin, Dr. Chun-cheng Chen, Lu-Chuan Kung, Anthony Halley, Thomas v Shen, Nistha Tripathi, and Rishi Bhardwaj, for helping me without reservations whenever I needed their assistance. I would like to specially thank Dr. Vartika Bhandari and Dr. Cheolgi Kim for being my mentors whenever I needed their suggestions. I also thank Dr. Pradeep Kyasanur and Chandrakanth Chereddi for taking time in answering my questions on the Net-X testbed. Special thanks to my lab mates Ghazale Hosseinabadi, Guanfeng Liang, Tae Hyun Kim, and Shehla Saleem for all the fun times and for providing a pleasant work environment.
I thank the ECE Publications Oﬃce for going through my thesis and for suggesting changes to improve its readability. I thank the National Science Foundation (NSF) and the US Army Research Oﬃce for funding my research.
Friends make an important part of a Ph.D. as without them it can be insanely diﬃcult to go through the gloomy days. I made quite a few friends here who were really successful at making my every single day. This space may not be suﬃcient to express all my gratitude to them. However, I would like to extend my humble thanks to my following friends, who I would like to rather call my family: G3, Kutti, Dunjan, Phi-man, RG, Dorky, Topa, Bumpkin Latte, JK, PG, Mugsu, JD, DPK, Mush-man, Photon, (Bed) Bug Fixer, and Meta.
Last but not the least, I thank my mom, dad, sister, and brother-in-law for their encouraging words and support throughout my academic life away from home.
Today’s internet is dominated by heterogeneous traﬃc characterized by a variety of applications that include both real-time and non-real-time applications. Real-time applications include voice over IP (VoIP), video, and online gaming that are delay sensitive. Non-real time applications, on the other hand, are delay tolerant, such as those transmitted over transmission control protocol (TCP) that require reliable data delivery. Each of these kinds of traﬃc behaves diﬀerently with respect to the packet characteristics and wireless bandwidth requirements. For instance, VoIP traﬃc is characterized by short packets, of the order of few 100 bytes, that may be generated at a constant rate. Such low rate traﬃc requires only very little wireless bandwidth, but the packets need to be delivered to the destination within a time deadline as otherwise the receiver may not be able to reproduce the voice without much distortion. Video traﬃc consists of variably sized packets and demands a higher transmission bandwidth. Finally, the traﬃc due to online gaming may involve a lot of packets and have to be delivered quickly to the gaming server to minimize user frustration. Moreover, these packets, similar to those of video, can be of varying sizes.
The real-time applications discussed above have to co-exist in the same network with the non-real-time traﬃc, which exhibits diﬀerent characteristics. For instance, TCP packets are typically ﬁxed size packets generated at a varying rate depending on the bandwidth availability. These are typically best-eﬀort traﬃc requiring reliable packet delivery, but are not timeconstrained, unlike the real-time applications. Examples of non-real-time applications include e-mail, ﬁle transfer, and normal web browsing.
The relative heterogeneity in the traﬃc characteristics and the service requirement of the applications has motivated extensive research on algorithms for adapting the radio resources to suit the application needs. Because wireless is a shared medium, a signiﬁcant portion of this research has been dedicated to exploring the means for eﬀectively sharing the spectrum among the contending users or applications. Many of the existing wireless standards, such as IEEE 802.11, IEEE 802.15.4, etc., provision multiple frequency channels, where a channel is a band of frequency spectrum. Realizing wireless networks using these standards allows for a natural way of sharing the spectrum amongst the users. By equipping the wireless nodes with multiple radio interfaces [1, 2, 3] and by utilizing appropriate routing, channel allocation, and scheduling strategies [3, 4, 5, 6], substantial performance beneﬁts can be harnessed using these multichannel standards.
In this thesis, we explore variable-width channelization in multichannel wireless networks and focus on three important problems that are signiﬁcant
in this perspective. We brieﬂy summarize each of these three works below:
Channelization to Reduce Protocol Overheads: In random access protocols every packet transmission is preceded by a considerable amount of time spent in assessing the channel to be free. The time spent in these overheads is independent of the actual length of the packet transmitted or the data rate used for transmitting the packet. These are, therefore, termed as bandwidth independent or rate independent overheads . The ratio of the time spent on these overheads to the time spent on an actual packet transmission, suggests an ineﬃciency in the underlying protocols. This is because, while the time spent on the overhead can be justiﬁed when considerable time is spent on the packet transmission, it may seem unfair when the actual packet transmission itself lasts for just a fraction of the time spent on the overheads . The ineﬃciency can be substantial when the packet payloads are small or the transmission data rates are large. The situation can be worse when a wider spectrum is allocated for packet transmissions, as wider channels can achieve larger data rates.
Present day communication networks predominantly involve packets of smaller sizes. For instance, a 2008 study  showed that more than 55% of the packets in the internet are of sizes smaller than 100 bytes. This is not surprising given that many of the packets, such as those generated by VoIP or the ACKs generated by TCP (used commonly by the HTML traﬃc), are small packets of the order of 100 bytes. To minimize the ineﬃciency, it makes sense to use a lower rate of transmission for shorter packets. However, simply reducing the rate of transmission may result in the short packets 2 occupying the channel for a longer time, which may be unfair for any long packets that are to be transmitted. Furthermore, the channel will not be used eﬃciently. In this work, we propose to instead partition a channel into a narrow channel, for sending short packets, and a wide channel, for sending long packets. We intend to use two wireless radios,1 one each for the two channel partitions. Narrow channels have a reduced capacity, which lowers the maximum transmission rate. We provide protocols for dynamically deciding the appropriate percentage of bandwidth for the short packets.
Managing System Latencies Due to Channel Switching Delays: To ensure connectivity between multiple wireless nodes that are allocated diﬀerent channels, the wireless interfaces must be allowed to switch across channels. However, due to software and hardware constraints, the delay involved in switching the channels can be signiﬁcant. This may result in latencies in packet transmissions that can be prohibitive for delay sensitive applications, such as VoIP. We propose an algorithm that can adapt the underlying channel allocation mechanism dynamically based on the type of traﬃc routed through the network. We consider two popular channel allocation strategies followed in multichannel wireless networks, namely static channel approach (in which the channels for all the radios of a node are ﬁxed), and hybrid channel approach (in which the channels for only a subset of radios are ﬁxed a priori and those for the remaining radios are varied dynamically during communication). The hybrid channel approach is optimized for achieving higher throughputs, but has poor delay performance due to the associated dynamic channel switching. While there are no such latencies in a static channel allocation scheme, which results in a better delay performance, they do not have a good throughput performance. In this work, we propose a mechanism that exploits the beneﬁts of a static channel approach for providing lower delay paths for real-time applications, while at the same time utilizing the ﬂexibilities of a hybrid channel approach for providing higher throughputs for non-delay sensitive applications. Using actual implementations on a multichannel mesh testbed, we show that the end-to-end delays of real-time applications are signiﬁcantly lower in our proposed approach when compared to a purely hybrid approach. Furthermore, we show that the 1 The terms ‘wireless radio’ and ‘wireless interface’ are used interchangeably in this thesis and both mean a wireless network interface card.
3 throughput of non-delay sensitive applications is not degraded signiﬁcantly as a result of our approach.
Variable Width Channelization Based on Traﬃc Demand: Most of the existing multichannel protocols propose to use ﬁxed width channels. For instance, the channel width in the case of IEEE 802.11a is ﬁxed at 20 MHz.
These ﬁxed width channels may either result in the spectrum being used ineﬃciently when there is not enough traﬃc to utilize the spectrum or in an insuﬃcient spectrum when the traﬃc requires more than the available bandwidth. If the spectrum widths, instead are allowed to be variable, then the ﬂows that require less spectrum can use a narrow spectrum, thereby allowing the remaining spectrum to be used by ﬂows requiring more spectrum. While certain standards allow for variable channels widths, as in the case of IEEE