Bozidar Radunovic

Publications

## 2014

- Charalampos E. Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic, Fennel: Streaming Graph Partitioning for Massive Scale Graphs, in
*WSDM 2014*, February 2014Balanced graph partitioning in the streaming setting is a key problem to enable scalable and efficient computations on massive graph data such as web graphs, knowledge graphs, and graphs arising in the context of online social networks. Two families of heuristics for graph partitioning in the streaming setting are in wide use: place the newly arrived vertex in the cluster with the largest number of neighbors or in the cluster with the least number of non-neighbors. In this work, we introduce a framework which unifies the two seemingly orthogonal heuristics and allows us to quantify the interpolation between them. More generally, the framework enables a well principled design of scalable, streaming graph partitioning algorithms that are amenable to distributed implementations. We derive a novel one-pass, streaming graph partitioning algorithm and show that it yields significant performance improvements over previous approaches using an extensive set of real-world and synthetic graphs. Surprisingly, despite the fact that our algorithm is a one-pass streaming algorithm, we found its performance to be in many cases comparable to the {\it de-facto} standard offline software METIS and in some cases even superiror. For instance, for the Twitter graph with more than 1.4 billion of edges, our method partitions the graph in about 40 minutes achieving a balanced partition that cuts as few as 6.8\% of edges, whereas it took more than 8$\tfrac{1}{2}$ hours by METIS to produce a balanced partition that cuts 11.98\% of edges. We also demonstrate the performance gains by using our graph partitioner while solving standard PageRank computation in a graph processing platform with respect to the communication cost and runtime.

## 2013

- Souvik Sen, Bozidar Radunovic, Jeongkeun Lee, and Kyu-Han Kim, CSpy: Finding the Best Quality Channel without Probing, in
*Mobicom*, ACM MOBICOM, September 2013Wireless performance depends directly on the quality of the channel. A wireless transmitter can improve its performance by estimating and transmitting on only the strongest channel, which can be of significantly higher quality than a weak channel (yielding up to 100% rate improvement). It is considered impossible to predict the quality of the unseen channels. Thus, the only way to identify the strongest channel is by probing each channel individually, incurring large overheads. The key contribution of this paper is a discovery of previously unobserved properties of the wireless channel that makes it possible to predict the strongest of a set of channels from the measurements collected only on a single channel. We confirm the properties through measurements and present a theoretical analysis that explains their nature. Our proposed system, CSpy, utilizes these observations to predict the strongest channel. CSpy is the first to reliably estimate the strongest channel by utilizing channel responses extracted from off-the-shelf wireless chipsets, without probing any additional channels. By tracking the strongest channel, CSpy improves performance by up to 100% in comparison to channel agnostic schemes. - Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang, Communication Complexity of Approximate Maximum Matching in Distributed Graph Data, no. MSR-TR-2013-35, April 2013We consider the problem of computing an approximate maximum matching in a graph that consists of $n$ vertices whose edges are stored partitioned across $k$ distributed sites in a data center. We are interested in characterizing the communication complexity of this problem which is of primary concern in data centers where communication bandwidth is a scarce resource. Our main result is that any algorithm that finds an $\alpha$-approximate maximum matching has a communication complexity of $\Omega(\alpha^2 k n)$. Perhaps surprisingly, we show that this lower bound matches an upper bound of a simple sequential algorithm, showing that no benefits can be obtained with respect to the communication cost despite the full flexibility allowed by the underlying computation model. Our lower bound for matching also implies lower bounds for other important graph problems in the distributed computation setting, including max-flow and graph sparsification. Other main contribution of this paper is a new technique for multi-party randomized communication complexity that is of wide applicability.

## 2012

- Varun Kanade, Zhenming Liu, and Bozidar Radunovic, Distributed Non-Stochastic Experts, in
*NIPS*, Neural Information Processing Systems Foundation, December 2012We consider the online distributed non-stochastic experts problem, where the distributed system consists of one \emph{coordinator} node that is connected to $k$ \emph{sites}, and the sites are required to communicate with each other via the coordinator. At each time-step $t$, one of the $k$ site nodes has to pick an expert from the set $\{1, \ldots, n\}$, and the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret at time horizon $T$, while simultaneously keeping communication to a minimum. The two extreme solutions to this problem are: (i) \emph{Full communication}: This essentially simulates the non-distributed setting to obtain the optimal $O(\sqrt{\log(n)T})$ regret bound at the cost of $T$ communication. (ii) \emph{No communication}: Each site runs an independent copy -- the regret is $O(\sqrt{\log(n)kT})$ and the communication is $0$. This paper shows the difficulty of simultaneously achieving regret asymptotically better than $\sqrt{kT}$ and communication better than $T$. We give a novel algorithm that for an oblivious adversary achieves a non-trivial trade-off: regret $O(\sqrt{k^{5(1 + \epsilon)/6}T})$ and communication $O(T/k^{\epsilon})$, for any value of $\epsilon \in (0, 1/5)$. We also consider a variant of the model, where the coordinator picks the expert. In this model, we show that the \emph{label-efficient} forecaster of Cesa-Bianchi et al. (2005) already gives us strategy that is near optimal in regret vs communication trade-off. - Bozidar Radunovic, Ranveer Chandra, and Dinan Gunawardena, Weeble: Enabling Low-Power Nodes to Coexist with High-Power Nodes in White Space Networks, in
*ACM CoNEXT*, ACM, December 2012One of the key distinctive requirements of white-space networks is the power asymmetry. Static nodes are allowed to transmit with 15dB-20dB higher power than mobile nodes. This poses significant coexistence problems, as high-power nodes can easily starve low-power nodes. In this paper, we propose Weeble, a novel distributed and state-less MAC protocol that solves the coexistence problem. One of the key building block is an adaptive preamble support, an add-on to the PHY layer that allows high-power nodes to detect a low-power transmission even when the difference in transmit power is as high as 20dB. The other key building block is a MAC protocol that exploits the adaptive preambles functionality. It implements a virtual carrier-sensing and automatically adapts the preamble size to optimize network performance. We extensively evaluate our system in a test-bed and in simulations. We show that we can prevent starvation of low-power nodes in almost all existing scenarios and improve the data rates of low-power links several-fold over existing MACs, and as a trade-off we decrease the throughput of the rest of the system by 20%-40%. - Charalampos E. Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic, Fennel: Streaming Graph Partitioning for Massive Scale Graphs, no. MSR-TR-2012-113, November 2012Graph partitioning is a key problem to enable efficient solving of a wide range of computational tasks and querying over large-scale graph data, such as computing node centralities using iterative computations, and personalized recommendations. In this work, we introduce a unifying framework for graph partitioning which enables a well principled design of scalable, streaming graph partitioning algorithms that are amenable to distributed implementation. We show that many previously proposed methods are special instances of this framework, we derive a novel one-pass, streaming graph partitioning algorithm and show that it yields significant benefits over previous approaches, using a large set of real-world and synthetic graphs. Surprisingly, despite the fact that our algorithm is a one-pass streaming algorithm, we found its performance to be overall comparable to the de-facto standard offline software METIS, and it even outperforms it on numerous real-world graphs. For instance, for the Twitter graph with more than 1.4 billion of edges, our method partitions the graph in about 40 minutes achieving a balanced partition that cuts as few as 6.8% of edges, whereas it took more than 8.5 hours by METIS to produce a balanced partition that cuts 11.98% of edges. Furthermore, modularity--a popular measure for community detection [Girvan and Newman, 2002; Newman and Girvan, 2004; Newman, 2006]--is also a special instance of our framework. We establish the first rigorous approximation algorithm, achieving a guarantee of O(log(k)/k) for partitioning into k clusters. Finally, we evaluate the performance gains by using our graph partitioner while solving standard PageRank computation in a graph processing platform, and observe significant gains in terms of the communication cost and runtime.
- Souvik Sen, Bozidar Radunovic, Romit Roy Choudhury, and Tom Minka, Spot Localization Using PHY Layer Information, in
*In proceedings of ACM Mobisys*, ACM, 25 June 2012This paper explores the viability of precise indoor localization using physical layer information in WiFi systems. We find evidence that channel responses from multiple OFDM subcarriers can be a promising location signature. While these signatures certainly vary over time and environmental mobility, we notice that their core structure preserves certain properties that are amenable to localization. We demonstrate these ideas through a functional system called PinLoc, implemented on off-the-shelf Intel 5300 cards. We evaluate the system in an active engineering building, a busy student center, a cafeteria, and at the Duke University museum, and demonstrate localization accuracies in the granularity of 1m x 1m boxes, called spots. Results show that PinLoc is able to localize users to a spot with 90% mean accuracy, while incurring less than 6% false positives. We believe this is an important step forward, compared to the best indoor localization schemes of today, such as Horus. - Zhenming Liu, Bozidar Radunovic, and Milan Vojnovic, Continuous Distributed Counting for Non-monotonic Streams, in
*Proceedings of ACM PODS*, ACM SIGMOD, 20 May 2012We consider the continual count tracking problem in a distributed environment where the input is an aggregate stream originating from $k$ distinct sites and the updates are allowed to be non-monotonic, i.e. both increments and decrements are allowed. The goal is to continually track the count within a prescribed relative accuracy $\epsilon$ at the lowest possible communication cost. Specifically, we consider an adversarial setting where the input values are selected and assigned to sites by an adversary but the order is according to a random permutation or is a random i.i.d process. The input stream of values is allowed to be non-monotonous with an unknown drift $-1\leq \mu \leq 1$ where the case $\mu = 1$ corresponds to the special case of a monotonic stream of only non-negative updates. We show that a randomized algorithm guarantees to track the count accurately with high probability and has the expected communication cost $\tilde O(\min\{\sqrt{k}/(|\mu| \epsilon), \sqrt{k n}/\epsilon, n\})$, for an input stream of length $n$, and establish matching lower bounds. This improves upon previously best known algorithm whose expected communication cost is $\tilde \Theta(\min\{\sqrt{k}/\epsilon,n\})$ that applies only to an important but more restrictive class of monotonic input streams, and our results are substantially more positive than the communication complexity of $\Omega(n)$ under fully adversarial input. We also show how our framework can also accommodate other types of random input streams, including fractional Brownian motion that has been widely used to model temporal long-range dependencies observed in many natural phenomena. Last but not least, we show how our non-monotonic counter can be applied to track the second frequency moment and to a Bayesian linear regression problem. - Krishna Chintalapudi, Bozidar Radunovic, Vlad Balan, Michael Buettener, Srinivas Yerramalli, Vishnu Navda, and Ramachandran Ramjee, WiFi-NC : WiFi Over Narrow Channels, no. MSR-TR-2012-17, 27 April 2012The quest for higher data rates in WiFi is leading to the development of standards that make use of wide channels (e.g., 40MHz in 802.11n and 80MHz in 802.11ac). In this paper, we argue against this trend of using wider channels, and instead advocate that radios should communicate over multiple narrow channels for efficient and fair spectrum utilization. We propose WiFi-NC, a novel PHY-MAC design that allows radios to use WiFi over multiple narrow channels simultaneously. To enable WiFi-NC, we have developed the compound radio, a single wideband radio that exposes the abstraction of multiple narrow channel radios, each with independent transmission, reception and carrier sensing capabilities. The architecture of WiFi-NC makes it especially suitable for use in whitespaces where free spectrum may be fragmented. Thus, we also develop a frequency band selection algorithm for WiFi-NC making it suitable for use in whitespaces. WiFi-NC has been implemented on an FPGA-based software defined radio platform. Through real experiments and simulations, we demonstrate that WiFi-NC provides better efficiency and fairness in both common WiFi as well as future whitespace scenarios.
- Krishna Chintalapudi, Bozidar Radunovic, Vlad Balan, Michael Buettener, Srinivas Yerramalli, Vishnu Navda, and Ramachandran Ramjee, WiFi-NC : WiFi Over Narrow Channels, in
*NSDI*, NSDI, 27 April 2012The quest for higher data rates in WiFi is leading to the development of standards that make use of wide channels (e.g., 40MHz in 802.11n and 80MHz in 802.11ac). In this paper, we argue against this trend of using wider channels, and instead advocate that radios should communicate over multiple narrow channels for efficient and fair spectrum utilization. We propose WiFi-NC, a novel PHY-MAC design that allows radios to use WiFi over multiple narrow channels simultaneously. To enable WiFi-NC, we have developed the compound radio, a single wideband radio that exposes the abstraction of multiple narrow channel radios, each with independent transmission, reception and carrier sensing capabilities. The architecture of WiFi-NC makes it especially suitable for use in whitespaces where free spectrum may be fragmented. Thus, we also develop a frequency band selection algorithm for WiFi-NC making it suitable for use in whitespaces. WiFi-NC has been implemented on an FPGA-based software defined radio platform. Through real experiments and simulations, we demonstrate that WiFi-NC provides better efficiency and fairness in both common WiFi as well as future whitespace scenarios. - Bozidar Radunovic and Alexandre Proutiere, On Downlink Capacity of Cellular Data Networks with WLAN/WPAN Relays, in
*IEEE/ACM Transactions on Networking*, IEEE/ACM Transactions on Networking, 2012We consider the downlink of a cellular network supporting data traffic in which each user is equipped with the same type of 802.11-like WLAN or WPAN interface, used to relay packets to further users. We are interested in the design guidelines for such networks and how much capacity improvements can the additional relay layer bring. A first objective is to provide a scheduling/relay strategy that maximizes the network capacity. Using theoretical analysis, numerical evaluation and simulations, we find that, when the number of active users is large, the capacity-achieving strategy divides the cell into two areas: one closer to the base-station where the relay layer is always saturated and some nodes receive traffic through both direct and relay links, and the further one where the relay is never saturated and the direct traffic is almost nonexistent. We also show that it is approximately optimal to use fixed relay link lengths, and we derive this length. We show that the obtained capacity is independent of the cell size (unlike in traditional cellular networks). Based on our findings we propose simple, decentralized routing and scheduling protocols. We show that in a fully saturated network our optimized protocol substantially improves performance over the protocols that use naive relay-only or direct-only policies.

## 2011

- Bozidar Radunovic, Alexandre Proutiere, Dinan Gunawardena, and Peter Key, Dynamic Channel, Rate Selection and Scheduling for White Spaces, in
*ACM CoNEXT*, ACM, December 2011We investigate dynamic channel, rate selection and scheduling for wireless systems which exploit the large number of channels available in the White-space spectrum. We first present measurements of radio channel characteristics from an indoor testbed operating in the 500 to 600MHz band and comprising 11 channels. We observe significant and unpredictable (non-stationary) variations in the quality of these channels, and demonstrate the potential benefit in throughput from tracking the best channel and also from optimally adapting the transmission rate. We propose adaptive learning schemes able to efficiently track the best channel and rate for transmission, even in scenarios with non-stationary channel condition variations. We also describe a joint scheduling scheme for providing fairness in an Access Point scenario. Finally, we implement the proposed adaptive scheme in our testbed, and demonstrate that it achieves significant throughput improvement (typically from 40% to 100%) compared to traditional fixed channel selection schemes. - Zhenming Liu, Bozidar Radunovic, and Milan Vojnovic, Continuous Distributed Counting for Non-monotonic Streams, no. MSR-TR-2011-128, 30 November 2011We consider the continual count tracking problem in a distributed environment where the input is an aggregate stream originating from $k$ distinct sites and the updates are allowed to be non-monotonic, i.e. both increments and decrements are allowed. The goal is to continually track the count within a prescribed relative accuracy $\epsilon$ at the lowest possible communication cost. Specifically, we consider an adversarial setting where the input values are selected and assigned to sites by an adversary but the order is according to a random permutation or is a random i.i.d process. The input stream of values is allowed to be non-monotonous with an unknown drift $-1\leq \mu \leq 1$ where the case $\mu = 1$ corresponds to the special case of a monotonic stream of only non-negative updates. We show that a randomized algorithm guarantees to track the count accurately with high probability and has the expected communication cost $\tilde O(\min\{\sqrt{k}/(|\mu| \epsilon), \sqrt{k n}/\epsilon, n\})$, for an input stream of length $n$, and establish matching lower bounds. This improves upon previously best known algorithm whose expected communication cost is $\tilde \Theta(\min\{\sqrt{k}/\epsilon,n\})$ that applies only to an important but more restrictive class of monotonic input streams, and our results are substantially more positive than the communication complexity of $\Omega(n)$ under fully adversarial input. We also show how our framework can also accommodate other types of random input streams, including fractional Brownian motion that has been widely used to model temporal long-range dependencies observed in many natural phenomena. Last but not least, we show how our non-monotonic counter can be applied to track the second frequency moment and to a Bayesian linear regression problem.
- Souvik Sen, Bozidar Radunovic, Romit Roy Choudhury, and Tom Minka, Precise Indoor Localization using PHY Layer Information, in
*ACM Hotnets*, ACM HotNets, November 2011 - Eugenio Magsiretti, krishna kant chintalapudi, Bozidar Radunovic, and Ramachandran Ramjee, WiFi-Nano : Reclaiming WiFi Efficiency through 800 ns slots, in
*Mobicom*, September 2011The increase in WiFi physical layer transmission speeds from 1 Mbps to 1 Gbps has reduced transmission times for a 1500 byte packet from 12 ms to 12 us. However, WiFi MAC overheads such as channel access and acks have not seen similar reductions and cumulatively contribute about 150 us on average per packet. Thus, the efficiency of WiFi has deteriorated from over 80% at 1 Mbps to under 10% at 1 Gbps. In this paper, we propose WiFi-Nano, a system that uses 800 ns slots to significantly improve WiFi efficiency. Reducing slot time from 9 us to 800 ns makes backoffs efficient but clear channel assessment can no longer be completed in one slot since preamble detection can now take multiple slots. Instead of waiting multiple slots for detecting preambles, nodes speculatively transmit preambles as their backoff counters expire while continuing to detect premables using self-interference cancellation. Upon detection of preambles from other transmitters, nodes simply abort their own preamble transmissions, thereby allowing the earliest transmitter to succeed. Further, receivers speculatively transmit their ack preambles at the end of packet reception, thereby reducing ack overhead. We validate the effectiveness of WiFi-Nano using an implementation on an FPGA based software defined radio platform and through extensive simulations, demonstrating efficiency gains of up to 100%. - Nikhil Singh, Dinan Gunawardena, Alexandre Proutiere, Bozidar Radunovic, Horia Vlad Balan, and Peter Key, Efficient and Fair MAC for Wireless Networks with Self-interference Cancellation, in
*WiOpt 2011*, May 2011Recent advances in PHY layer design demonstrated efficient self-interference cancellation and full-duplex in a single band. Building a MAC that exploits self-interference cancellation is a challenging task. Links can be scheduled concurrently, but only if they either (i) don't interfere or (ii) allow for self-interference cancellation. Two issues arise: Firstly, it is difficult to construct a schedule that fully exploits the potentials for self-interference cancellation for arbitrary traffic patterns. Secondly, designing an efficient and fair distributed MAC is a daunting task; the issues become even more pronounced when scheduling under the constraints. We propose ContraFlow, a novel MAC that exploits the benefits of self-interference cancellation and increases spatial reuse. We use full-duplex to eliminate hidden terminals, and we rectify decentralized coordination inefficiencies among nodes, thereby improving fairness. Using measurements and simulations we illustrate the performance gains achieved when ContraFlow is used and we obtain both a throughput increase over current systems, as well as a significant improvement in fairness. - Bozidar Radunovic, Alexandre Proutiere, Dinan Gunawardena, and Peter Key, Exploiting Channel Diversity in White Spaces, no. MSR-TR-2011-53, 1 April 2011In a recent ruling, FCC has enabled an unlicensed use of the vacated analogue broadcast TV spectrum, called "White Spaces", provided that the unlicensed devices detect and avoid primary users (remaining TV channels and wireless MICs). The offered frequency space is very wide and has excellent propagation characteristics, hence the ruling offers a huge potential to develop high-quality, cheap and ubiquitous wireless access, and it also poses several novel design challenges (detecting primaries, network asymmetries, channel selections, etc). In this work we focus on the problem of channel and rate selections for white-spaces. We start by presenting measurements using an indoor testbed operating in the 500 to 600MHz band, and demonstrate that the key challenge is handling variable channel quality. The measurements show that there is significant potential benefit from selecting the best channel and adapting the transmission rate while also revealing non-stationary channel characteristics. The proposed learning algorithms are well suited to non-stationary environments and attempt to minimize "regret" with respect to a best or oracle-like algorithm. The novel aspects of the algorithms includes (i) accounting for the cost incurred when switching channels and synchronization costs, (ii) exploiting inherent correlations between the effective throughputs achieved when selecting the same channel but different transmission rates. We further extend the algorithms to account for fairness issues in network scenarios where several users are served by an access point.
- Bozidar Radunovic, Ranveer Chandra, and Dinan Gunawardena, Adaptive Preambles for Coexistence, no. MSR-TR-2011-15, 31 January 2011Wireless protocols in the unlicensed spectrum are developed for different requirements in terms of range and power, which makes them difficult to coexist in the same unlicensed spectrum. One such example is Zigbee and WiFi coexistence where low-power Zigbee nodes are frequently starved by WiFi nodes. Recent standardization efforts of short range IEEE 802.11af and long range IEEE 802.22 in the TV white spaces will make this problem more severe in the future. In this paper, we propose a novel PHY and MAC protocol for coexistence. Our protocol is decentralized and simple. The key building block is an adaptive preamble support at the PHY layer that allows high-power nodes to detect a low-power transmission even when the difference in transmit power constraints between the two groups of nodes is as high as 20dB. We show that this technique can prevent starvation of low-power nodes in almost all existing scenarios. We further propose a MAC protocol that builds on CSMA MAC and exploits the adaptive preambles functionality. We extensively evaluate our system in a test-bed and in simulations. We show that we can improve the data rates of low-power links by as much as 10x over existing MACs, without sacrificing more than 20%-40% of throughput of the rest of the system.

## 2010

- Bozidar Radunovic, Dinan Gunawardena, Peter Key, Alexandre Proutiere, Nikhil Singh, Vlad Balan, and Gerald Dejean, Rethinking Indoor Wireless Mesh Design: Low Power, Low Frequency, Full-duplex, in
*WiMesh (SECON Workshop)*, IEEE Communications Society, June 2010Existing indoor WiFi networks in the 2.5GHz and 5 GHz use too much transmit power, needed because the high carrier frequency limits signal penetration and connectivity. Instead, we propose a novel indoor wireless mesh design paradigm, based on Low Frequency, using the newly freed white spaces previously used as analogue TV bands, and Low Power – 100 times less power than currently used. Preliminary experiments show that this maintains a similar level of connectivity and performance to existing networks. It also yields more uniform connectivity, thus simplifies MAC and routing protocol design. We also advocate full-duplex networking in a single band, which becomes possible in this setting (because we operate at low frequencies). It potentially doubles the throughput of each link and eliminates hidden terminals. - Prasanna Chaporkar, Alexandre Proutiere, and Bozidar Radunovic, Rate Adaptation Games in Wireless LANs: Nash Equilibrium and Price of Anarchy, in
*INFOCOM 2010*, IEEE Communications Society, March 2010In Wireless LANs, users may adapt their transmission rates depending on the radio conditions of their links so as to maximize their throughput. Recently, there has been a significant research effort in developing distributed rate adaptation schemes. Unlike previous works that mainly focus on channel tracking, this paper characterizes the optimal reaction of a rate adaptation protocol to the contention information received from the MAC. We formulate this problem analytically. We study both competitive and cooperative user behaviors. In the case of competition, users selfishly adapt their rates so as to maximize their own throughput, whereas in the case of cooperation they adapt their rates so as to maximize the overall system throughput. We show that the Nash Equilibrium reached in the case of competition is inefficient (i.e. the price of anarchy goes to infinity as the number of users increases), and provide insightful properties of the socially optimal rate adaptation schemes. We find that recently proposed collision-aware rate adaptation algorithms decrease the price of anarchy. We also propose a novel collision-aware rate adaptation algorithm that further reduces the price of anarchy.

## 2009

- Christos Gkantsidis, Thomas Karagiannis, Peter Key, Bozidar Radunovic, Elias Raftopoulos, and D. Manjunath, Traffic management and resource allocation in small wired/wireless networks, in
*Fifth ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2009)*, Association for Computing Machinery, Inc., December 2009We consider the problem of traffic management in small networks with both wireless and wired devices, connected to the Internet through a single gateway. Examples of such networks are small office networks or residential networks, where typically traffic management is limited to flow prioritization through port-based filtering. We propose a practical resource allocation framework that provides simple mechanisms to applications and users to enable traffic management functionality currently not present due to the distributed nature of the system and various technology or protocol limitations. To allow for control irrespective of whether traffic flows cross wireless, wired or even broadband links, the proposed framework jointly optimizes rate allocations across wireless and wired devices in a weighted fair manner. Additionally, we propose a model for estimating the achievable capacity regions in wireless networks to overcome the absence of the queue information. This model is used by the controller to achieve a specific rate allocation. We evaluate a decentralized, host-based implementation of the proposed framework. The controller is incrementally deployable by not requiring modifications to existing network protocols and equipment or the wireless MAC. Using analytical methods and experimental results with realistic traffic, we show that our controller is stable with fast convergence for both UDP and TCP traffic, achieves weighted fairness, and mitigates scheduling inefficiencies of the existing hardware. - Bozidar Radunovic, Dinan Gunawardena, Peter Key, Alexandre Proutiere, Nikhil Singh, Horia Vlad Balan, and Gerald Dejean, Rethinking Indoor Wireless: Low Power, Low Frequency, Full-duplex, no. MSR-TR-2009-148, 24 July 2009Existing indoor WiFi networks in the 2.5GHz and 5 GHz use too much transmit power, needed because the high carrier frequency limits signal penetration and connectivity. Instead, we propose a novel indoor wireless design paradigm, based on Low Frequency, using the newly freed white spaces previously used as analogue TV bands, and Low Power -- 100 times less power than currently used. Preliminary experiments show that this maintains a similar level of connectivity and performance to existing networks. We also advocate full-duplex networking in a single band, which becomes possible in this setting (because we operate at low frequencies). It potentially doubles the throughput of each link and eliminates hidden terminals.
- Bozidar Radunovic, Dinan Gunawardena, Alexandre Proutiere, Nikhil Singh, Vlad Balan, and Peter Key, Efficiency and Fairness in Distributed Wireless Networks Through Self-interference Cancellation and Scheduling, no. MSR-TR-2009-27, 12 March 2009Handling interference is one of the major challenges in the design of multi-user distributed wireless systems. In current systems, interference is managed through carrier sensing mechanisms such as CSMA/CA and through MAC algorithms based on random back-off. However, the asymmetry in channel sensing inevitably causes degraded throughput and fairness issues, such as those caused by hidden terminal problems. We propose ContraFlow, a solution based on self-interference cancellation and innovative scheduling mechanisms that increases spatial reuse, eliminates hidden terminals, and rectifies decentralized coordination inefficiencies among nodes, thereby improving fairness. Self-interference cancellation is a technique allowing a node to cancel its own transmitted signal and hence to successfully receive data while transmitting on the same channel. We demonstrate the feasibility of such techniques in a low power WPAN setting, using Lyrtech software-defined radios. Self-interference cancellation repairs carrier sensing, making it possible to successfully eliminate hidden terminal problems, even when using current multi-user MAC protocols; but it also provides the opportunity to design new distributed MAC scheduling algorithms that increase the spatial reuse and solve most of the fairness problems associated with current algorithms. We use simulations to illustrate the performance gains achieved when ContraFlow is used and we obtain both a throughput increase over current systems, as well as a significant improvement in fairness.
- Bozidar Radunovic, Christos Gkantsidis, Peter Key, and Pablo Rodriguez, Toward Practical Opportunistic Routing with Intra-session Network Coding for Mesh Networks, in
*ACM/IEEE Transactions on Networking*, IEEE/ACM Transactions on Networking, 2009We consider opportunistic routing in wireless mesh networks. We exploit the inherent diversity of the broadcast nature of wireless by making use of multi-path routing. We present a novel optimization framework for opportunistic routing based on network utility maximization (NUM) that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. All previous work on NUM assumed unicast transmissions; however, the wireless medium is by its nature broadcast and a transmission will be received by multiple nodes. The structure of our design is fundamentally different; this is due to the fact that our link rate constraints are defined per broadcast region instead of links in isolation. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. Optimal MAC scheduling is difficult to implement, and we use 802.11-like random scheduling rather than optimal in our comparisons. Under random scheduling, our protocol becomes fully decentralized (we assume ideal signaling). The use of network coding introduces additional constraints on scheduling, and we propose a novel scheme to avoid starvation. We simulate realistic topologies and show that we can achieve 20-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).

## 2008

- Bozidar Radunovic, Christos Gkantsidis, Dinan Gunawardena, and Peter Key, Horizon: Balancing TCP over Multiple Paths in Wireless Mesh Network, in
*MobiCom'08*, Association for Computing Machinery, Inc., 14 September 2008There has been extensive work on network architectures that support multi-path routing to improve performance in wireless mesh networks. However, previous work uses ad-hoc design principles that cannot guarantee any network-wide performance objectives such as conjointly maximizing resource utilization and improving fairness. In parallel, numerous theoretical results have addressed the issue of optimizing a combined metric of network utilization and fairness using techniques based on back-pressure scheduling, routing and flow control. However, the proposed theoretical algorithms are extremely difficult to implement in practice, especially in the presence of the 802.11 MAC and TCP. We propose Horizon, a novel system design for multi-path forwarding in wireless meshes, based on the theoretical results on back-pressure. Our design works with an unmodified TCP stack and on top of the existing 802.11 MAC. We modified the backpressure approach to obtain a simple 802.11-compatible packetforwarding heuristic and a - Prasanna Chaporkar, Alexandre Proutiere, and Bozidar Radunovic, Rate Adaptation Games in Wireless LANs: Nash Equilibrium and Price of Anarchy, no. MSR-TR-2008-137, September 2008In Wireless LANs, users may adapt their transmission rates depending on the observed radio conditions on their links to maximize their throughput. Recently, there has been a significant research effort in developing distributed rate adaptation schemes offering better performance than that of the current ARF (Automatic Rate Fallback). Unlike previous works, this paper characterizes the optimal reaction of a rate adaptation protocol to the contention information received from the MAC. We formulate this problem analytically. We study both competitive and cooperative user behaviors: In the case of competition, users selfishly adapt their rates so as to maximize their own throughput, whereas in the case of cooperation they aim at adapting their rates to maximize the overall system throughput. We show that the Nash Equilibrium realized in the case of competition can be inefficient (i.e., the price of anarchy is high, up to 50% of the social optimum), and provide insightful properties of the socially optimal rate adaptation schemes. We also show that RTS/CTS does not make the competitive scenario more efficient. We then apply the same analysis to recently proposed collision-aware rate adaptation algorithms and observe similar conclusions. Finally, we propose a novel collision-aware rate adaptation algorithm that significantly reduces the price of anarchy in many scenarios of interest. %Collision-aware algorithms have been recently proposed to handle the %interaction of the distributed scheduling (DCF) and rate adaptation %schemes, and require that users are able to differentiate packet %collisions from transmission failures caused by channel errors.
- Bozidar Radunovic, Christos Gkantsidis, Peter Key, and Pablo Rodriguez, An Optimization Framework for Opportunistic Multipath Routing in Wireless Mesh Networks, in
*INFOCOM Minisymposium*, 2008 - Bartek Blaszczyszyn and Bozidar Radunovic, Using transmit-only sensors to reduce deployment cost of wireless sensor networks, in
*INFOCOM*, IEEE Communications Society, 2008We consider a hybrid wireless sensor network with regular and transmit-only sensors. The transmit-only sensors do not have the receiver circuit (or have a very low data-rate one), hence are cheaper and less energy consuming, but their transmissions cannot be coordinated. Regular sensors, also called cluster-heads, are responsible for receiving information from the transmit-only sensors and forwarding it to sinks. The main goal of such a hybrid network is to reduce the cost of deployment while achieving some performance goals (minimum coverage, sensing rate, etc). In this paper we are interested in the communication between the transmit-only sensors and the cluster-heads. Since the sensors have no feedback, their transmission schedule is random. The cluster-heads, on the contrary, adapt their reception policy to achieve the performance goals. Using a mathematical model of random access networks developed in [BlaszczyszynRadunovic2007] we define and evaluate packet admission policies for different performance criteria. We show that the proposed hybrid network architecture, using the optimal policies, can achieve substantial dollar cost and power consumption savings as compared to conventional architectures while providing the same performance guarantees.

## 2007

- Christos Gkantsidis, Wenjun Hu, Peter Key, Bozidar Radunovic, Pablo Rodriguez, and Steluta Gheorghiu, Multipath Code Casting for Wireless Mesh Networks, in
*CoNext 2007*, ACM, New York, December 2007Designing high throughput wireless mesh networks involves solving interrelated scheduling, routing, and interference problems. In this paper, we exploit the broadcast properties and the path diversity of wireless meshes to implement an efficient multipath routing protocol, Multipath Code Casting (MC2). In contrast to prior work in opportunistic routing, which required strong coordination across nodes to prevent information repetition, our design is based on network coding and does not require node coordination. Moreover, it provides a unified framework to deal with data transmissions across multiple and, often, unreliable transmission paths. Our design also includes a novel rate-scheduling algorithm that guarantees (proportionally) fair allocation of resources across multiple (multipath) flows, ensures that data use the paths with the best performance, and prevents information overflow by controlling the data rate across each path. Using simulations and a prototype implementation, we show that our algorithms provide over 30% performance improvement compared to traditional singlepath approaches when applied to realistic and other exemplar topologies; in some scenarios, our approach can even double the throughput. Our approach also performs better than 20% compared to other multipath routing schemes. - Bozidar Radunovic, Christos Gkantsidis, Peter Key, Pablo Rodriguez, and Wenjun Hu, An optimization framework for practical multipath routing in wireless mesh networks, no. MSR-TR-2007-81, June 2007We consider wireless mesh networks, and exploit the inherent broadcast nature of wireless by making use of multipath routing. We present an optimization framework that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. Optimal MAC scheduling is difficult to implement, and we use random scheduling rather than optimal for comparisons. Under random scheduling, our protocol becomes fully decentralised. We use simulation to show on realistic topologies that we can achieve 20-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).
- Christos Gkantsidis, Bozidar Radunovic, Peter Key, Steluta Gheorgiu, Wenjun Hu, and Pablo Rodriguez, Multipath Code Casting for Wireless Mesh Networks, no. MSR-TR-2007-67, June 2007Designing high throughput wireless mesh networks is a challenge, and involves solving interrelated scheduling, routing, and interference problems. In this paper, we exploit the fundamental properties of broadcast medium and path diversity in wireless meshes to implement multipath routing between a source and destination pair. We use network coding for a given unicast source-destination flow to ease the scheduling problem, exploit diversity, and deal with unreliable transmissions. We describe multipath-forwarding algorithms, and show their performance benefits over existing proposals, using simulation, analysis, and a prototype implementation on a small testbed. We propose a rate-scheduling protocol that relies on network coding, which gives over 30% performance improvement for a realistic topology and can double the throughput in certain cases.
- B. Radunovic and J.-Y. Le Boudec, A Unified Framework for Max-Min and Min-Max Fairness with Applications, in
*ACM/IEEE Transactions on Networking*, vol. 15, no. 5, 2007 - Bartlomiej Blaszczyszyn and Bozidar Radunovic, M/D/1/1 loss system with interference and applications to transmit-only sensor networks, in
*INFORMS*, 2007 - Bartlomiej Blaszczyszyn and Bozidar Radunovic, M/D/1/1 loss system with interference and applications to transmit-only sensor networks, in
*Spaswin*, 2007 - Bozidar Radunovic and Alexandre Proutiere, On Downlink Capacity of Cellular Data Networks with WLAN/WPAN Relays, in
*RAWNET*, 2007 - Bozidar Radunovic, Jean-Yves Le Boudec, and Raymond Knopp, Performance of Ultra-Wideband Impulse Radio in Presence of Impulsive Interference, no. arXiv:cs/0702084, 2007

## 2006

- A. El Fawal, J.-Y. Le Boudec, B. Radunovic R. Merz, and J. Widmer, The Optimal MAC Layer for Low-Power UWB is Non-Coordinated, in
*IEEE International Symposium on Circuits and Systems (ISCAS 2006)*, 2006

## 2005

- B. Radunovic and J.-Y. Le Boudec, Power Control is Not Required for Wireless Networks in the Linear Regime, in
*IEEE WoWMoM*, 2005 - J.-Y. Le Boudec, R. Merz, B. Radunovic, J. Widmer A. El Fawal, and G.M. Maggio, Tradeoff Analysis of PHY-aware MAC in Low-Rate, Low-Power UWB networks, in
*IEEE Communications Magazine*, vol. 43, no. 12, pp. 147, 2005 - Ruben Merz, Joerg Widmer, Jean-Yves Le Boudec, and Bozidar Radunovic, A Joint PHY/MAC Architecture for Low-Radiated Power TH-UWB Wireless Ad-Hoc Networks, in
*Wireless Communications and Mobile Computing Journal, Special Issue on Ultrawideband (UWB) Communications*, vol. 5, no. 5, pp. 567-580, 2005 - Bozidar Radunovic, A Cross-Layer Design of Wireless Ad-Hoc Networks, 2005
- B. Radunovic and J.-Y. Le Boudec, Rate Adaptation, Power Adaptation and Mutual Exclusion in Variable Rate Wireless Networks, in
*RAWNET Workshop*, 2005 - M. Weisenhorn B. Radunovic H. L. Truong, Bozidar Radunovic, Lin Truong, and Martin Weisenhorn, Receiver Architectures for Transmit-Only, UWB-Based Sensor Networks, in
*IEEE ICU*, 2005

## 2004

- Ruben Merz, Jean-Yves Le Boudec, Joerg Widmer, and Bozidar Radunovic, A Rate-Adaptive MAC Protocol for Low-Power Ultra-Wide Band Ad-hoc Networks, in
*Ad-Hoc Now 04, 3rd International Conference on AD-HOC Networks*, 2004 - Bozidar Radunovic and Jean-Yves Le Boudec, Rate Performance Objectives of Multi-hop Wireless Networks, in
*INFOCOM 04*, 2004 - B. Radunovic and J.-Y. Le Boudec, Rate Performance Objectives of Multihop Wireless Networks, in
*IEEE Transactions on Mobile Computing*, vol. 3, no. 4, pp. 334–349, 2004 - B. Radunovic and J.-Y. Le Boudec, Optimal Power Control, Scheduling and Routing in UWB Networks, in
*IEEE Journal on Selected Areas in Communications*, vol. 22, no. 7, pp. 1252, 2004 - Jean-Yves Le Boudec, Ruben Merz, Bozidar Radunovic, and J. Widmer, DCC-MAC: A Decentralized MAC Protocol for 802.15.4a-like UWB Mobile Ad-Hoc Networks Based on Dynamic Channel Coding, in
*Broadnets*, 2004

## 2003

- Bozidar Radunovic and Jean-Yves Le Boudec, Joint Scheduling, Power Control and Routing in Symmetric, One-dimensional, Multi-hop Wireless Networks, in
*WiOpt`03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks*, 2003

## 2002

- Bozidar Radunovic and Jean-Yves Le Boudec, A Unified Framework for Max-Min and Min-Max Fairness with Applications, in
*40th Annual Allerton Conference on Communication, Control, and Computing*, 2002