LTE evolved Multimedia Broadcast/Multicast Service (eMBMS) is an attractive solution for video delivery to very large groups in crowded venues. However, the deployment and management of eMBMS systems are challenging, due to the lack of real-time feedback from the user equipments (TIEs). Therefore, we present the Dynamic Monitoring (DyMo) system for low-overhead feedback collection. DyMo leverages eMBMS for broadcasting stochastic group instructions to all UEs. These instructions indicate the reporting rates as a function of the observed quality of service (QoS). This simple feedback mechanism collects very limited QoS reports from the TIEs. The reports are used for network optimization, thereby ensuring high QoS to the TIEs. We present the design aspects of DyMo and evaluate its performance analytically and via extensive simulations. Specifically, we show that DyMo infers the optimal eMBMS settings with extremely low overhead while meeting strict QoS requirements under different TIE mobility patterns and presence of network component failures. For instance, DyMo can detect the eMBMS signal-to-noise ratio experienced by the 0.1th percentile of the TIEs with a root mean square error of 0.05% with only 5 to 10 reports per second regardless of the number of TIEs.

WiFi multicast to very large groups has gained attention as a solution for multimedia delivery in crowded areas. Yet, the most recently proposed schemes do not provide performance guarantees and none have been tested at scale. To address the issue of providing high multicast throughput with performance guarantees, we present the design and experimental evaluation of the multicast dynamic rate adaptation (MuDRA) algorithm. MuDRA balances fast adaptation to channel conditions and stability, which is essential for multimedia applications. MuDRA relies on feedback from some nodes collected via a light-weight protocol and dynamically adjusts the RA response time. Our experimental evaluation of MuDRA on the ORBIT testbed with over 150 nodes shows that MuDRA outperforms other schemes and supports high throughput multicast flows to hundreds of receivers while meeting quality requirements. MuDRA can support multiple high-quality video streams, where 90% of the nodes report excellent or very good video quality.

LTE evolved Multimedia Broadcast/Multicast Service (eMBMS) is an attractive solution for video delivery to very large groups in crowded venues. However, deployment and management of eMBMS systems is challenging, due to the lack of realtime feedback from the User Equipment (UEs). Therefore, we present the Dynamic Monitoring (DyMo) system for low-overhead feedback collection. DyMo leverages eMBMS for broadcasting Stochastic Group Instructions to all UEs. These instructions indicate the reporting rates as a function of the observed Quality of Service (QoS). This simple feedback mechanism collects very limited QoS reports from the UEs. The reports are used for network optimization, thereby ensuring high QoS to the UEs. We present the design aspects of DyMo and evaluate its performance analytically and via extensive simulations. Specifically, we show that DyMo infers the optimal eMBMS settings with extremely low overhead, while meeting strict QoS requirements under different UE mobility patterns and presence of network component failures. For instance, DyMo can detect the eMBMS Signal-to-Noise Ratio (SNR) experienced by the 0.1% percentile of the UEs with Root Mean Square Error (RMSE) of 0.05% with only 5 to 10 reports per second regardless of the number of UEs.

WiFi multicast to very large groups has gained attention as a solution for multimedia delivery in crowded areas. Yet, most recently proposed approaches do not provide performance guarantees. In this paper, we describe the AMuSe system, whose objective is to enable scalable and adaptive WiFi multicast services. AMuSe includes a lightweight feedback mechanism that allows monitoring channel quality of a large number of users. This feedback allows the system to dynamically optimize the multicast transmission rate at the AP. We implemented AMuSe on the ORBIT testbed and evaluated its performance in large groups with approximately 200 WiFi devices in different scenarios. We show that AMuSe supports high throughput multicast flows to hundreds of receivers while meeting quality requirements and that it outperforms other systems.

WiFi multicast to very large groups has gained attention as a solution for multimedia delivery in crowded areas. Yet, most recently proposed schemes do not provide performance guarantees and none have been tested at scale. To address the issue of providing high multicast throughput with performance guarantees, we present the design and experimental evaluation of the Multicast Dynamic Rate Adaptation (MuDRA) algorithm. MuDRA balances fast adaptation to channel conditions and stability, which is essential for multimedia applications. MuDRA relies on feedback from some nodes collected via a light-weight protocol and dynamically adjusts the rate adaptation response time. Our experimental evaluation of MuDRA on the ORBIT testbed with over 150 nodes shows that MuDRA outperforms other schemes and supports high throughput multicast flows to hundreds of receivers while meeting quality requirements. MuDRA can support multiple high quality video streams, where 90% of the nodes report excellent or very good video quality.

We consider the problem of managing the sharing of data among multiple users in a mobile shared data plan. Such plans allow for quota to be shifted from a user with only small requests in a given month to a user with larger requests. However, in the long run we wish for this sharing to be done in a fair manner. We begin with an intra-month problem in which requests arrive online during a single month and we wish to maximize fairness by the end of the month. For this case we describe an algorithm for which each user receives at least an I/O (log n) fraction of its optimal allocation and we also present a matching lower bound. We next consider a month-by-month version of the problem in which each user has a single usage request for each month and we wish to allocate the group quota in a way that satisfies each request as much as possible while also achieving long-term fairness (as defined by a utility function). For stochastic requests we present an optimal algorithm derived from the theory of wireless scheduling. In contrast, for adversarial requests we show that for any algorithm there may be a user that only receives a 1/n fraction of its optimal allocation. We conclude with the combined problem in which the requests arrive online during the month but we wish to achieve fairness over a longer timescale. For this case we derive the subproblem that must be solved in each individual month and derive a dynamic programming based solution. Our simulations show that our approaches perform well compared to the optimal offline approach that knows the request sequences in advance.

WiFi networks have been globally deployed and most mobile devices are currently WiFi-enabled. While WiFi has been proposed for multimedia content distribution, its lack of adequate support for multicast services hinders its ability to provide multimedia content distribution to a large number of devices. In this paper, we present the AMuSe system, whose objective is to enable scalable and adaptive WiFi multicast services. AMuSe is based on accurate receiver feedback and incurs a small control overhead. In particular, we develop an algorithm for dynamic selection of a subset of the multicast receivers as feedback nodes, which periodically send information about the channel quality to the multicast sender. This feedback information can be used by the multicast sender to optimize multicast service quality, e.g., by dynamically adjusting transmission bitrate. AMuSe does not require any changes to the standards or any modifications to the WiFi devices. We implemented AMuSe on the ORBIT testbed and evaluated its performance in large groups with approximately 200 WiFi devices, both with and without interference sources. Our extensive experiments demonstrate that AMuSe can provide accurate feedback in a dense multicast environment. It outperforms several alternatives even in the case of external interference and changing network conditions.

We consider the problem of minimizing the power consumption of IP core networks by means of power aware configuration of the Points of Presence (PoPs), given general traffic demands on the links. Although the problem is in general NP-complete, we give an optimal algorithm for an important variant where the number of ports on each line-card chassis is 2. For the general problem, we design two approximation algorithms with respective P/2 and 2lnN approximation ratios, where P is the number of ports on each line-card chassis, and N is the number of chassis within the PoP. When the traffic demands are correlated, we prove that our algorithms are optimal. Extensive simulations demonstrate that our PoP configuration algorithms significantly outperform existing design solutions over a wide range of traffic instances.

This paper considers a hybrid cellular architecture in which mobiles can communicate with others in their vicinity, e.g. using 802.11 interface, in addition to the base stations of the cellular network. Such an architecture can aid device-to-device communication as well as assist critical tasks of cellular networks such as mobility management, content caching and relaying. In order to enable these capabilities, base stations need to have sufficient knowledge of the underlying network topology induced by the 802.11 links of the mobiles. Due to the dynamic nature of this network, a compressed snapshot of its topology should be collected within a very short time duration and with minimal communication among mobiles. Addressing this need, we propose a compact topology representation that is suitable for a number of applications. We utilize the broadcast nature of wireless channels to design an efficient topology detection algorithm that acquires a compact representation of the underlying network (at most 3N links and a low `stretch' factor for the N mobiles) within a short duration (10s of ms). Our scheme does not have collision resolution, backoffs or any of the other MAC layer inefficiencies.

Physical layer capture is one of the main causes of unfairness in IEEE 802.11 Wireless LANs. While existing work have analyzed the impact of physical layer capture on the total system throughput of a cell, we analyze the unfairness among users as result of capture. Since this unfairness is related to the relative location of users, we call it as spatial unfairness. Our analysis characterizes the relative throughput share of a user as a function of the users' distance from the Access Point (i.e., as a function of received signal strength). We validate the accuracy of our analysis via extensive simulations and experimental measurements.

A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue by promptly forwarding an IP packet to a predetermined alternate next-hop as soon as the primary next-hop to the destination becomes unavailable. Among the numerous IP FRR schemes proposed to date, the simplest ones do not guarantee protection against every component failure, while more sophisticated ones tend to be difficult to implement due to various inherent complexities, such as nontrivial modifications of IP packets or high resource requirements. This paper presents a simple and efficient IP FRR scheme called DisPath, which leverages several fundamental properties of minimum-cost node-disjoint paths for determining the alternate next-hop toward a given destination. We show that DisPath ensures full coverage, meaning protection against all single link or node failures, with low computational overhead and without the practical complications encountered by other schemes that offer the same level of protection. Our simulations on several realistic instances reveal that DisPath usually creates shorter (and, at worst, not much longer) alternative paths than existing solutions adopted by the industry. Combined with the aforementioned protection guarantee and simplicity of implementation, these results provide strong evidence that DisPath is a most compelling choice of IP FRR scheme.

Physical layer capture is one of the main causes of throughput unfairness in IEEE 802.11 Wireless LANs. While existing work have analyzed the impact of physical layer capture on the total system throughput of a cell, we study the relative unfairness among users as result of capture. Since this unfairness is related to the relative location of users, we call it as spatial unfairness. Our evaluation characterizes the relative throughput of users as a function of the users' distance from the Access Point.

Reliable delivery of network services is critically for numerous real-time applications, such as video conferencing, broadcast TV and content distribution, in which time sensitive content is delivered to a single or multiple destinations. Failure protection in connection-oriented networks can be realized using local protection schemes, such as fast reroute (FRR), or using end-to-end protection schemes, like redundant trees. In this paper we study the trade-offs between local and end-to-end protection schemes from several key aspects such as protection availability, management complexity and in particular the resource reservation efficiency of the two approaches.

We propose a computationally efficient link-coloring based scheme that facilitates end-to-end protection for dynamic multicast and unicast connections. For a given source node, links are colored as red or blue such that, for any destination node, the red and blue paths are guaranteed to be node disjoint. Red and blue trees, constructed using only the red and blue links, respectively, always form redundant trees (RTs) independent of the used tree selection method. RTs connect the source of a multicast connection to all its destinations in such a way that in the event of a single link or node failure in the network, every destination is still connected to the source in at least one of the two trees. In network topologies where such RTs cannot be constructed due to lack of required path diversity, our scheme constructs two multicast trees such that the red and blue paths to any destination node only share cut links or nodes. To our knowledge, our scheme is the first that can construct such RTs. Although finding the optimal RTs is known to be NP-complete, extensive simulations show that our scheme calculates near optimal RTs and substantially outperforms other solutions.

IEEE 802.11-based wireless local area networks, referred to as WiFi, have been globally deployed and the vast majority of mobile devices are currently WiFi-enabled. While WiFi has been proposed for multimedia content distribution, its lack of adequate support for multicast services hinders its ability to provide multimedia content distribution to a large number of devices. We propose AMuSe, a scalable and adaptive interference mitigation solution for WiFi multicast services which is based on accurate receiver feedback and that incurs a small control overhead. Specifically, we develop a scheme for dynamic selection of a subset of the multicast receivers as feedback nodes, which periodically send information, such as channel quality or received packet statistics, to the multicast sender. This feedback information is used by the multicast sender to optimize the multicast service quality, e.g., by dynamically adjusting the transmission bit-rate. Our proposed solution does not require any changes to the standards or any modifications to the WiFi devices. We have implemented the proposed solution in the ORBIT testbed and evaluated its performance in large groups with approximately 250 receivers, both with and without interference sources. Our online experiments demonstrate that our system provides practical multicast services that can accommodate hundreds of receivers.

We consider the problem of minimizing the power consumption of IP core networks by means of power-aware design and auto-configuration of the Points of Presence (PoPs), given general traffic demands on the links. Although the problem is in general NP-complete, we give an optimal algorithm for an important variant in which the number of ports on each line-card chassis is 2. For the general problem, we design two approximation algorithms with respective P=2 and 2 lnN approximation ratios, where P is the number of ports on each line-card chassis, and N is the number of chassis within the PoP. When the traffic demands are correlated, we prove that our algorithms are optimal. Extensive simulations demonstrate that our PoP design and auto-configuration algorithms significantly outperform existing design solutions over a wide range of traffic instances.

A major concern in IP networks is to ensure that any topology changes, whether planned or unplanned, do not disrupt network performance. IP Fast Reroute (IP FRR) is a general approach to address this issue, by promptly forwarding an IP packet to a predetermined alternate next hop as soon as the primary next hop to the destination becomes unavailable. Among the numerous IP FRR schemes proposed to date, the simplest ones do not guarantee protection against every component failure, while more sophisticated ones tend to be difficult to implement due to various inherent complexities, such as nontrivial modifications of IP packets or high resource requirements.

Multicast is getting increasingly popular to support critical business services such as IPTV, video conferencing and content distribution. To meet the stringent availability requirements, a highly fault resilient multicast infrastructure is critically important. Redundant Steiner trees (RST) are one mechanism for realizing such infrastructure. RSTs are a pair of Steiner trees that ensure that for any single link or node failure in the network, every destination node of a multicast connection is reachable from the source on at least one of these two trees. In this paper, we consider the problem of constructing optimal RSTs in a directed graph, which is NP-complete. In light of this, we propose a simple and efficient scheme to construct near-optimal RSTs. The scheme ensures an approximation ratio of 2k for general directed graphs, where k denotes the number of destination nodes. We compare the performance of our scheme with an linear program (LP) formulation of the problem that provides a lower bound on the optimal solution. Our simulations illustrate that our scheme constructs near optimal RSTs independent of the number of destination nodes and significantly outperforms other approaches proposed in prior literature.

Wireless sensor networks (WSNs) have recently emerged as a prominent technology for environmental monitoring and hazardous event detection. Yet, their success depends considerably on their ability to ensure reliable event detection. Such guarantees can be provided only if the target field monitored by a WSN does not contain coverage holes that are not monitored by any sensor. Currently, the coverage hole detection solutions require accurate knowledge of the sensors locations, which cannot be easily obtained, or they cannot provide guarantees on the coverage quality. In this study, we address the challenge of designing an accurate k-coverage verification scheme, without using location information, for a predefined k\ge 1. To this end, we present two efficient, distributed, and localized k-coverage verification schemes with proven guarantees on their coverage detection quality. Our simulations show that the schemes accurately detect coverage holes of various sizes.

Wireless sensor networks (WSNs) have recently emerged as a key sensing technology with diverse civilian and military applications. In these networks, a large number of small sensors or nodes perform distributed sensing of a target field. Each node is capable of sensing events of interest within its sensing range and communicating with neighboring nodes. The target field is said to be$k$-covered if every point in it is within the sensing range of at least$k$sensors, where$k$is any positive integer. We present a comprehensive framework for verifying$k$-coverage of a$d$-dimensional target field for an arbitrary positive integer$k$and$d \in \{1, 2, 3\}$. Our framework uses a divide-and-conquer approach based on the technique of dimension reduction, in which the$k$-coverage verification problem in$d$dimensions is reduced to a number of coverage verification problems in$(d-1)$dimensions, which are then recursively solved. Our framework leads to a distributed polynomial-time coverage verification algorithm that does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in WSNs. Each node can execute the algorithm using only the distances between adjacent nodes within its transmission range and their sensing radii. We analytically prove that the scheme detects a coverage hole if and only if the target field has a coverage hole.

In wireless sensor networks (WSNs), a large number of sensors perform distributed sensing of a target field. A sensor cover is a subset of the set of all sensors that covers the target field. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with nonzero remaining energy does not constitute a sensor cover any more. An important goal in sensor networks is to design a schedule-that is, a sequence of sensor covers to activate in every time slot-so as to maximize the lifetime of the network. In this paper, we design a polynomial-time distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factorO(logn* lognB) lower than the maximum possible lifetime, wherenis the number of sensors andBis an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each sensor only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. Then, in a distributed manner, it finds anO(logn) approximate minimum weight sensor cover, which it activates in the slot.

Multi-hop wireless networks using directional antennas are increasingly deployed for various applications such as wireless backhaul. In such systems, each node is equipped with a few directional antennas. Each antenna is exclusively used for establishing a point-to-point link with another antenna on some neighboring node. Thus in the constructed network, each node cannot have more links than its number of installed antennas, which defines a degree bound on all nodes. Hence, a practically important problem is to construct fault resilient and high capacity networks with bounded node degree. The main contribution of this paper is two-fold. First, we propose a localized algorithm for building fault resilient wireless networks that contain the path with highest possible capacity for every pair of nodes, not only in normal cases but also in the presence of any node/link failure. Second, we give an algorithm for building fault resilient wireless networks with the lowest possible degree bound.

Channel zapping is the act of changing from one television channel to another. Zap response time is the time it takes for the new TV channel to start playing from the time a request to zap to that channel occurs. In digital TV systems such as IPTV where TV channel content is transported as an MPEG-2 or MPEG-4 data stream encapsulated in IP packets, zap response time is a significant concern. This is due to the requirement that for an MPEG stream, which is a series of groups of pictures (GOPs), playout can only start at the beginning of a GOP. The time between the occurrence of a zap event to the time to the beginning of the next GOP, which can be anywhere from less than a second to a few seconds, is a significant contributor to zap response time. It is widely accepted that such large zap response times can significantly hamper IPTV quality of experience (QoE) and an efficient solution to this problem is therefore a business imperative. Existing solutions to this problem are bandwidth inefficient either on the last mile, or within the video distribution network, or both. We present a novel solution that is significantly efficient in terms of bandwidth utilization and zap response time. We derive and present the theoretical bounds for our solution and quantitatively demonstrate the properties of our solution through results from extensive simulations.

In this paper, we consider the problem of protection of multicast connections against single link or node failures using redundant multicast trees (RMTs). RMTs connect the source node of a multicast connection to all its destinations in such a way that in the event of a single link or node failure in the network, every destination node is still connected to the source node in at least one of the two trees. Construction of RMTs has been studied extensively for undirected graphs, but not for directed graphs. Computing RMTs in directed graphs can be important in networks, for instance, where link capacity is available in one direction but not the other. Also, none of the schemes proposed in previous work provide a solution for finding optimal (minimal-cost) RMTs even for weighted undirected graphs. We show that a whole class of earlier schemes that are based on the concept of ear-decomposition cannot find optimal redundant trees in certain network topologies. To our knowledge, we are the first to consider the problem of finding optimal RMTs in directed graphs. We present a novel efficient scheme for construction of optimal RMTs in networks modeled as weighted undirected as well as directed graphs.

Physical layer capture is one of the basic causes of throughput unfairness in IEEE 802.11 Wireless LANs. While papers have analyzed the impact of capture on the overall throughput of a single 802.11 cell, we are unaware of any analysis of the relative unfairness among users as result of capture. Since this unfairness is related to the relative location of users, we call this as spatial unfairness. We provide, to the best of our knowledge, the first such analysis that characterizes the relative throughput of users as a function of the users' distance from the access point (AP). We experimentally validate our analysis using a single 802.11b cell testbed.

Wireless Sensor Networks are emerging as a key sensing technology, with diverse military and civilian applications. In these networks, a large number of sensors perform distributed sensing of a target field. Each sensor is a small battery-operated device that can sense events of interest in its sensing range and can communicate with neighboring sensors. A sensor cover is a subset of the set of all sensors such that every point in the target field is in the interior of the sensing ranges of at least $k$ different sensors in the subset, where k is a given positive integer. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with non-zero remaining energy does not constitute a sensor cover. An important goal in sensor networks is to design a schedule, that is, a sequence of sensor covers to activate in every time slot, so as to maximize the lifetime of the network. In this paper, we design a polynomial-time, distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factor O(log n * log nB) lower than the maximum possible lifetime, where n is the number of sensors and B is an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each sensor only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. Then, in a distributed manner, it finds a O(log n) approximate minimum weight sensor cover which it activates in the slot. Our simulations reveal that our algorithm substantially outperforms several existing lifetime maximization algorithms.

Wireless sensor networks (WSNs) have recently emerged as a key sensing technology with diverse civilian and military applications. In these networks, a large number of small sensors or nodes perform distributed sensing of a target field. Each node is capable of sensing events of interest within its sensing range and communicating with neighboring nodes. The target field is said to be k-covered if every point in it is within the sensing range of at least k sensors, where k is any positive integer. We present a comprehensive framework for verifying k-coverage of a d-dimensional target field for arbitrary positive integers k, d. Our framework uses a divide and conquer approach based on the technique of dimension reduction, in which the k-coverage verification problem in d-dimensions is reduced to a number of coverage verification problems in (d-1) dimensions, which are then recursively solved. Our framework leads to a distributed polynomial-time coverage verification algorithm that does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in WSNs. Each node can execute the algorithm using only the distances between adjacent nodes within its transmission range and their sensing radii. We analytically prove that the scheme detects a coverage hole if and only if the target field has a coverage hole.

Maximizing network throughput while providing fairness is one of the key challenges in wireless LANs (WLANs). This goal is typically achieved when the load of access points (APs) is balanced. Recent studies on operational WLANs, however, have shown that AP load is often substantially uneven. To alleviate such imbalance of load, several load balancing schemes have been proposed. These schemes commonly require proprietary software or hardware at the user side for controlling the user-AP association. In this paper we present a new load balancing technique by controlling the size of WLAN cells (i.e., AP's coverage range), which is conceptually similar to cell breathing in cellular networks. The proposed scheme does not require any modification to the users neither the IEEE 802.11 standard. It only requires the ability of dynamically changing the transmission power of the AP beacon messages. We develop a set of polynomial time algorithms that find the optimal beacon power settings which minimize the load of the most congested AP. We also consider the problem of network-wide min-max load balancing. Simulation results show that the performance of the proposed method is comparable with or superior to the best existing association-based methods.

Wireless sensor networks (WSNs) have recently emerged as a prominent technology for environmental monitoring and hazardous event detection. Yet, their success depends considerably on their ability to ensure reliable event detection. Such guarantees can be provided only if the target field monitored by a WSN does not contain coverage holes that are not monitored by any sensor. Currently, the coverage-holes detection solutions require accurate knowledge of the sensors locations, which cannot be easily obtained, or they cannot provide guarantees on the coverage quality. In this study we address the challenge of designing an accurate k-coverage verification scheme, without using location information, for a predefined kges1. To this end, we present an efficient, distributed and localized k-coverage verification scheme with proven guarantees on its coverage detection quality. Our simulations show that the scheme accurately detects coverage holes of various sizes.

In recent years, numerous large-scale Wireless LANs (WLAN) have been deployed all over the world. However, the shortage of non-interfering channels makes it a challenge for WLANs to efficiently support real-time multicast services. We study the problem of efficient scheduling ofreal-timemulticastflows. For mitigating interferences, we allow access-points (APs) to transmit simultaneously only if they are mutually non-interfering and our objective is minimizing the fraction of time used by the APs for servicing the multicast flows. We introduce two multicast strategies, theassociationstrategyfor which each user is restricted to receive flows only from its associated AP and thenon-associationstrategy for which a user may also decode transmissions from other APs in its vicinity. Under both strategies, the scheduling problem of minimizing the multicast service time is NP-hard and we propose simple approximation algorithms with provable performance bounds. Our simulations clearly demonstrate that the proposed algorithms yield efficient multicast scheduling.

Recently, wireless mesh technology has been used for military applications and fast recovery networks, referred to as nomadic wireless mesh networks (NWMNs). In such systems, wireless routers, termed nodes, are mounted on top of vehicles or vessels, which may change their location according to application needs; and the nodes are required to establish a reliable wireless mesh network. For improving network performance, some vendors use directional antennas, and the mesh topology comprises of point-to-point connections between adjacent nodes. The number of point-to-point connections of a node is upper-bounded by the number of directional radios it has, which is typically a small constant. This raises the need to build robust (i.e., two-node/edge- connected) mesh networks with bounded node degree, regardless of node locations. In this paper, we present simple elegant schemes for constructing such efficient and robust wireless mesh networks with provably small constant degree bounds. Our extensive simulations show our schemes build robust and efficient topologies for various settings with node degree bounded by 4 and small hop-count distance between nodes and gateways.

Energy-aware routing is important in multi-hop wireless networks that are operated by battery power, e.g., wireless sensor networks. To maximize the network survivability, the energy efficiency of paths must be taken into account for route selection. Simple heuristics such as choosing paths with minimal energy consumption do not perform well, because the energy of the nodes on such paths may deplete quickly. The issue is particularly serious for the networks with regular traffic pattern as in monitoring sensor applications. Existing solutions to this issue typically adopt the multi-path routing approach, in which multiple paths are set up between source and destination and one (or all) of the paths is (are) used at a certain moment. However, this approach involves high overhead for establishment and management of multiple paths. In this paper, we present a static single-path routing algorithm which uses one energy-efficient path for each communicating peer throughout the network lifetime, eliminating the overhead of multi-path routing. It is proved that our algorithm achieves a constant factor approximate of the optimal solution. We compare the performance of the proposed scheme with that of multi-path routing via simulations. Despite the use of single static path, the proposed scheme outperforms the dynamic multi-path approach, particularly under heavy network loads.

Abstract: Today, Ethernet is the dominant local area network (LAN) technology. These networks, typically, comprise large number of elements from different vendors. This raises considerable difficulties in performing network management tasks, such as resource management and root cause analysis, which are practically impossible without an up-to-date knowledge of the physical network topology. Given the dynamic nature of today’s LANs, keeping track of topology information manually is a daunting (if not impossible) task. Therefore, it is essential to develop practical schemes for automatic inference of the physical topology of Ethernet networks. In this paper, we propose a simple and efficient algorithmic solution for discovering the physical topology of large, heterogeneous Ethernet LANs that may include multiple subnets as well as uncooperative network elements, like hubs. Our scheme utilizes only generic MIB information and does not required any hardware or software modification of the underlying network elements. By rigorous analysis, we prove that our method correctly infers the network topology and has low communication and computational overheads. Our simulation results show that the scheme successfully infers the complete topology in the vast majority of the cases, including many instances in which other methods fail. Finally, we implemented the proposed scheme to verify its inference capabilities. These properties confirm the practicality of our scheme for network management.

Maximizing network throughput while providing fairness is one of the key challenges in wireless LANs (WLANs). This goal is typically achieved when the load of access points (APs) is balanced. Recent studies on operational WLANs, however, have shown that AP load is often substantially uneven. To alleviate such imbalance of load, several load balancing schemes have been proposed. These schemes commonly require proprietary software or hardware at the user side for controlling the user-AP association. In this paper we present a new load balancing technique by controlling the size of WLAN cells (i.e., AP’s coverage range), which is conceptually similar to cell breathing in cellular networks. The proposed scheme does not require any modification to the users neither the IEEE 802.11 standard. It only requires the ability of dynamically changing the transmission power of the AP beacon messages. We develop a set of polynomial time algorithms that find the optimal beacon power settings which minimize the load of the most congested AP. We also consider the problem of network-wide min-max load balancing. Simulation results show that the performance of the proposed method is comparable with or superior to the best existing association-based methods.

There is a growing interest among service providers to offer new services with Quality of Service (QoS) guarantees that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both bottleneck QoS constraints, such as bandwidth, and additive QoS constraints, such as delay and jitter. This is the first study to provide a rigorous solution, with proven guarantees, to the combined problem of computing QoS paths with restoration. It turns out that the widely used approach of disjoint primary and restoration paths is not an optimal strategy. Hence, the proposed algorithms construct a restoration topology , i.e., a set of bridges, each bridge protecting a portion of the primary QoS path. This approach guarantees to find a restoration topology with low cost when one exists.

We present a framework for providing fair service and supporting QoS requirements in IEEE 802.11 networks with multiple access-points (APs). These issues becomes critical as IEEE 802.11 wireless LAN are widely deployed in nationwide networks, linking tens of thousands of "hot-spots" for providing both real-time (voice) and non real-time (data) services to a large population of mobile users. However, both fairness and QoS guarantees cannot he supported in the current 802.11 standard. Our system, termed MiFi, relies on centralized coordination of the APs. During any given time of the "contention-free" period only a set of non-interfering APs is activated while the others are silenced. Moreover the amount of service granted to an AP is proportional to its load and the system's performance is optimized by employing efficient scheduling algorithms. We show that such a system can be implemented without requiring any modification of the underlying MAC protocol standard or the behavior of the mobile stations and it guarantees to overcome the hidden node and the overlapping cell problems. Our simulations establish that the system supports fairness and hence can provide QoS guarantees for real-time traffic, while maintaining a relative high till throughput.

Recent studies on operational wireless LANs (WLANs) have shown that user load is often unevenly distributed among wireless access points (APs). This unbalanced load results in unfair bandwidth allocation among users. We observe that the unbalanced load and unfair bandwidth allocation can be greatly alleviated by intelligently associating users to APs, termed association control, rather than having users greedily associate APs of best received signal strength.In this study, we present an efficient algorithmic solution to determine the user-AP associations that ensure max-min fair bandwidth allocation. We provide a rigorous formulation of the association control problem that considers bandwidth constraints of both the wireless and backhaul links. Our formulation indicates the strong correlation between fairness and load balancing, which enables us to use load balancing techniques for obtaining near optimal max-min fair bandwidth allocation. Since this problem is NP-hard, we present algorithms that achieve a constant-factor approximate max-min fair bandwidth allocation. First, we calculate a fractional load balancing solution, where users can be associated with multiple APs simultaneously. This solution guarantees the fairest bandwidth allocation in terms of max-min fairness. Then, by utilizing a rounding method we obtain an efficient integral association. In particular, we provide a 2-approximation algorithm for unweighted greedy users and a 3-approximation algorithm for weighted and bounded-demand users. In addition to bandwidth fairness, we also consider time fairness and we show it can be solved optimally. We further extend our schemes for the on-line case where users may join and leave. Our simulations demonstrate that the proposed algorithms achieve close to optimal load balancing and max-min fairness and they outperform commonly used heuristic approaches.

This study considers the problem of designing an efficient and low-cost infrastructure for connecting static multihop wireless networks with wired backbone, while ensuring QoS requirements such as bandwidth and delay. This infrastructure is useful for designing low-cost and fast deployed access networks in rural and suburban areas. It may also be used for providing access to sensor networks or for efficient facility placement in wireless networks. In these networks, some nodes are chosen as access points and function as gateways to access a wired backbone. Each access point serves a cluster of its nearby user, and a spanning tree rooted at the access point is used for message delivery. The study addresses both the design optimization and the operation aspects of the system. From the design perspective, we seek for a partition of the network nodes into a minimal number of disjoint clusters that satisfy multiple constraints; each cluster is required to be a connected graph with an upper bound on its radius. We assume that each node has a weight (representing its bandwidth requirement), and the total weight of all cluster nodes is also bounded. We show that these clustering requirements can be formulated as an instance of the capacitated facility location problem (CFLP) with additional constraints. By breaking the problem into two subproblems and solving each one separately, we propose polynomial time approximation algorithms that calculate solutions within a constant factor of the optimal ones. From the operation viewpoint, we introduce an adaptive delivery mechanism that maximizes the throughput of each cluster without violating the QoS constraints.

Knowledge of the up-to-date physical (i.e., layer-2) topology of an Ethernet network is crucial to a number of critical network management tasks, including reactive and proactive resource management, event correlation, and root-cause analysis. Given the dynamic nature of today's IP networks, keeping track of topology information manually is a daunting (if not impossible) task. Thus, effective algorithms for automatically discovering physical network topology are necessary. In this paper, we propose the first complete algorithmic solution for discovering the physical topology of a large, heterogeneous Ethernet network comprising multiple subnets as well as (possibly) dumb or uncooperative network elements. Our algorithms rely on standard SNMP MIB information that is widely supported in modern IP networks and require no modifications to the operating system software running on elements or hosts. Furthermore, we formally demonstrate that our solution is complete for the given MIB data; that is, if the MIB information is sufficient to uniquely identify the network topology then our algorithm is guaranteed to recover it. To the best of our knowledge, ours is the first solution to provide such a strong completeness guarantee.

There is a growing interest among service providers to offer new services with quality of service (QoS) guaranties that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both bottleneck QoS constraints, such as bandwidth, and additive QoS constraints, such as delay and jitter. This is the first study to provide a rigorous solution, with proven guarantees, to the combined problem of computing QoS paths with restoration. It turns out that the widely used approach of disjoint primary and restoration paths is not an optimal strategy. Hence, the proposed algorithms construct a restoration topology, i.e., a set of bridges, each bridge protecting a portion of the primary QoS path. This approach guaranties to find a restoration topology with low cost when one exists. In addition to analysis, we test our approach also by way of simulations. The simulation results demonstrate that our proposed approximation algorithms identify QoS restoration paths whose cost is significantly smaller than those provided by alternative approaches.

In this paper, we develop failure-resilient techniques for monitoring link delays and faults in a service provider or enterprise IP network. Our two-phased approach attempts to minimize both the monitoring infrastructure costs as well as the additional traffic due to probe messages. In the first phase of our approach, we compute the locations of a minimal set of monitoring stations such that all network links are covered, even in the presence of several link failures. Subsequently, in the second phase, we compute a minimal set of probe messages that are transmitted by the stations to measure link delays and isolate network faults. We show that both the station selection problem as well as the probe assignment problem are NP-hard. We then propose greedy approximation algorithms that achieve a logarithmic approximation factor for the station selection problem and a constant factor for the probe assignment problem. These approximation ratios are provably very close to the best possible bounds for any algorithm.

A central problem in personal communication systems is to optimize bandwidth usage, while providing Quality of Service (QoS) guarantees to mobile users. Network mobility management, and in particular, location management, consumes a significant portion of bandwidth, which is a necessary overhead for supporting mobile users. We focus our efforts on minimizing this overhead. Unlike previous works, we concentrate on optimizing existing schemes, and so the algorithms we present are easily incorporated into current networks. We present the first polynomial time approximation algorithms for minimum bandwidth location management. In planar graphs, our algorithm provably generates a solution that uses no more than a constant factor more bandwidth than the optimal solution. In general graphs, our algorithm provably generates a solution that uses just a factor O(logn) more bandwidth than optimal where n is the number of base stations in the network. We show that, in practice, our algorithm produces near-optimal results and outperforms other schemes that are described in the literature. For the important case of the line graph, we present a polynomial-time optimal algorithm. Finally, we illustrate that our algorithm can also be used for optimizing the handoff mechanism.

This work considers the problem of designing an efficient and low-cost infrastructure for connecting static multi-hop wireless networks with wired backbone, while ensuring QoS requirements such as bandwidth and delay. This infrastructure is useful for designing low cost and fast deployed access networks in rural and suburban areas. It may also be used for providing access to sensor networks or for efficient facility placement in wireless networks. In these networks some nodes are chosen as access points and function as gateways to access a wired backbone. Each access point serves a cluster of its nearby user and a spanning tree rooted at the access point is used for message delivery. The work addresses both the design optimization and the operation aspects of the system. From the design perspective, we seek for a partition of the network nodes into minimal number of disjoint clusters that satisfy multiple constraints; Each cluster is required to be a connected graph with an upper bound on its radius. We assume that each node has a weight (representing its bandwidth requirement) and the total weight of all cluster nodes is also bounded. We show that these clustering requirements can be formulated as an instance of the Capacitated Facility Location problem (CFLP) with additional constraints. By breaking the problem into two sub-problems and solving each one separately, we propose polynomial time approximation algorithms that calculate solutions within a constant factor of the optimal ones. From the operation viewpoint, we introduce an adaptive delivery mechanism that maximizes the throughput of each cluster without violating the QoS constraints.

This paper considers the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (PCS). Most modern communication systems that are used as an infrastructure for PCS networks are based on connection-based technologies. In these systems, the session cost is composed of two components. The setup cost represents the cost associated with the handoff operations, and the hold cost determines the expense related to the use of network resources held by the connection. This work introduces for the first time, rerouting algorithms for general graphs which are cost effective in terms of their worst-case analysis. The algorithms are analyzed using a competitive analysis approach, and it is proved that the competitive ratio of the proposed algorithms is a small constant of which the precise value depends on the ratio between the setup costs and the hold costs of the links. We also prove a lower bound of 2 on the competitive ratio of any online algorithm, which means that the proposed algorithms are close in terms of worst case behavior to the best possible rerouting algorithm. In addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.

Personal communication systems (PCS) maintain a location management mechanism for tracking the location of their mobile users. The increasing population of mobile users leads to congestion problems in these systems, and motivates the development of more efficient management schemes. This work presents a new mobility management scheme that integrates the location area approach with the location prediction idea. It is based on results from traffic flow theory and it is first that uses the concept of moving location areas. Traffic flow theory suggests that people tend to reside in specific places for long periods of time. Occasionally, they move to new locations and try to minimize the travel time using highways as much as possible. The scheme uses two complementary sets of location areas that overlap each other. The first set contains small location areas and is designated for locating mobile users in a quasi-static state. The second set covers the highways and it is designated to track mobile users while they are traveling from place to place, where each highway is covered by a single location area. The dual set design enables tracking mobile users at a high degree of accuracy with low update cost while they are quasi-static state, and reduces the amount of update operations when they travel. For tracing mobile users on a highway, the scheme uses a system of moving location areas. A moving location area (MLA) is a small location area that defines the location of a group of mobile users, which are geographically concentrated and move in the same direction. The scheme guarantees low rate of update and search operations at each cell of the system and efficiently utilizes the radio spectrum and the network resources with low computational overhead. These advantages are also backed by simulation results.

This work presents a simple mobility scheme for IP-based networks, termed the "anchor chain" scheme. The scheme combines pointer forwarding and caching methods. Every mobile host (MH) is associated with a chain of anchors that connects it to its home agent. Each anchor defines the location of the MH at a certain degree of accuracy. The accuracy is increased along the chain until the attachment point of the MH is reached. We develop distributed procedures for updating the anchor chain (binding operation) with MH movements and for delivering messages to a MH (delivery operation). In terms of worst-case performance, the total cost of the binding operations is O(MovelogMove), where Move is the total geographic distance that the MH has traveled since its activation. The total length of the MH's pointer path is linear with the distance between the MH and its home network, and the delivery cost is near-optimal. In addition, the anchor chain of a MH is determined dynamically with no need for preliminary definitions of static anchors or regions. Our simulation results show that the anchor chain scheme also yields lower average overheads for both the binding and the delivery operations than other methods that are described in the literature, including the current home approach. We believe that the proposed scheme is scalable, fairly easy to implement and therefore attractive for supporting MH.

This paper considers the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (PCS). Most modern communication systems that are used as an infrastructure for PCS networks are based on connection-based technologies. In these systems the session cost is composed of two components. The setup cost represents the cost associated with the handoff operations and the hold cost determines the expense related to the use of network resources held by the connection. Using an efficient handoff rerouting algorithm is important for the efficient management of PCS networks. This work introduces for the first time rerouting algorithms for general graphs which are cost-effective in terms of their worst-case analysis. The algorithms are analyzed using a competitive analysis approach and it is proved that the competitive ratio of the proposed algorithms is a small constant whose precise value depends on the ratio between the setup costs and the hold costs of the links. We also prove that the competitive ratio of the best online algorithm is at least 2, which means that the proposed algorithms are close in terms of worst-case behavior to the best possible rerouting algorithm. In addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.

Personal Communication Systems (PCS) enable people to communicate independent of their location.For tracking the location of mobtie users the system must maintain a Location Management mechanism, which maps user ad-&ases to their current location.The increasing population of mobfle users leads to congestion problems in these systems, and motivatw the development of more ficient management sdemw.This work pr=ents a novel hierarchical Location Management scheme, in which every level of the hierarchy reprwents a partition to geographic regions.Within each level of the hierarchy the system records the location of every mobile user to a c@ain degree of accuracy.The degree of accuracy is incre=ed as we go down the levek until we reach the node to which the mobile user is attached.We develop distributed procedures for locating the mobile users (termed the Sear& operation) and updating the system location records (termed the Update operation) with user movements.The proposed scheme guarantew upper bound on the procedures costs: The amortized compltity of the mobile user update operations is O(Move.log Move), where Move is the total geographic distance that the mobile user has traveled.The upper bound of a search operation is ~mear with the distance between the search originator and the target node.These upper bounds do not depend on the network size.Therefore, the proposed scheme is attractive for the next generation of PCS.The management system is &o suitable for supporting anycaat and territory rwtricted users.