We consider the problem of providing protection against failures in wireless networks subject to interference constraints. Typically, protection in wired networks is provided through the provisioning of dedicated backup paths. This approach has not been previously considered in the wireless setting due to the prohibitive cost of backup capacity. Assigning capacity for dedicated backup paths in a wireless setting can more than double the total resources required from what was needed without protection, which can make protection infeasible. However, we show that in the presence of interference, guaranteed protection can be provided for all demands with little, and oftentimes no , additional resources beyond what was required without any protection. This is due to the fact that after a failure, links that previously interfered with the failed link can be activated, thus leading to a “recapturing” of lost capacity. We provide an ILP formulation to find an optimal solution for both binary and SINR interference constraints, and develop corresponding time-efficient algorithms. Our approach utilizes up to 87 percent less protection resources than traditional disjoint path routing to provide guaranteed protection. For the case of 2-hop interference, our protection scheme requires only 8 percent more resources on average than providing no protection whatsoever.

In this paper, we consider medium access control (MAC) policies for emerging systems that are equipped with fully digital antenna arrays which are capable of adaptive multi-beam directional communications. With this technology, a user can form multiple simultaneous transmit or receive beams, allowing for greater spatial reuse and higher network throughput. The enabling technology that we consider is the ability to use digital post-processing to form multiple receive beams in real-time without a priori knowledge of the time and angle-of-arrival of the transmission. We present a novel unslotted, uncoordinated ALOHA-like random access MAC policy for multi-beam directional systems that asymptotically achieves the capacity of the network. Such an approach is particularly useful for systems where propagation delay makes the overhead associated with any sort of coordination prohibitive. We also consider the impact of numerous practical considerations including power constraints, latency, and beamwidth on the performance of our MAC policy.

This paper considers the problem of rapidly determining the maximum achievable capacity of a multi-hop wireless mesh network subject to interference constraints. Being able to quickly determine the maximum supported flow in a wireless network has numerous practical applications for network planners and researchers. Current approaches for determining network capacity either provide asymptotic results that are not necessarily achievable, are computationally intractable and cannot be computed quickly, or are not generalizable to different interference constraints for emerging technologies. In this paper, we present a new algorithm to rapidly determine the maximum concurrent flow for an arbitrary number of unicast and multicast connections subject to arbitrary binary interference constraints, and provide a feasible route and schedule to support those flows. The solution provided by our algorithm is within O(δ-1) of the maximum possible flow, where δ is the maximum number of links that cannot be activated due to interference from some particular transmission.

We consider the problem of providing protection against failures in wireless networks by using disjoint paths. Disjoint path routing is commonly used in wired networks for protection, but due to the interference between transmitting nodes in a wireless setting, this approach has not been previously examined for wireless networks. In this paper, we develop a non-disruptive and resource-efficient disjoint path scheme that guarantees protection in wireless networks by utilizing capacity "recapturing" after a failure. Using our scheme, protection can oftentimes be provided for all demands using no additional resources beyond what was required without any protection. We show that the problem of disjoint path protection in wireless networks is not only NP-hard, but in fact remains NP-hard to approximate. We provide an ILP formulation to find an optimal solution, and develop corresponding time-efficient algorithms. Our approach utilizes 87% less protection resources on average than the traditional disjoint path routing scheme. For the case of 2-hop interference, which corresponds to the IEEE 802.11 standard, our protection scheme requires only 8% more resources on average than providing no protection whatsoever.

We consider the problem of providing network protection that guarantees the maximum amount of time that flow can be interrupted after a failure. This is in contrast to schemes that offer no recovery time guarantees, such as IP rerouting, or the prevalent local recovery scheme of Fast ReRoute, which often over-provisions resources to meet recovery time constraints. To meet these recovery time guarantees, we provide a novel and flexible solution by partitioning the network into failure-independent “recovery domains”, where within each domain, the maximum amount of time to recover from a failure is guaranteed. We show the recovery domain problem to be NP-Hard, and develop an optimal solution in the form of an MILP for both the case when backup capacity can and cannot be shared. This provides protection with guaranteed recovery times using up to 45% less protection resources than local recovery. We demonstrate that the network-wide optimal recovery domain solution can be decomposed into a set of easier to solve subproblems. This allows for the development of flexible and efficient solutions, including an optimal algorithm using Lagrangian relaxation, which simulations show to converge rapidly to an optimal solution. Additionally, an algorithm is developed for when backup sharing is allowed. For dynamic arrivals, this algorithm performs better than the solution that tries to greedily optimize for each incoming demand.

We consider the problem of providing protection against failures in wireless networks subject to interference constraints. Typically, protection in wired networks is provided through the provisioning of backup paths. This approach has not been previously considered in the wireless setting due to the prohibitive cost of backup capacity. However, we show that in the presence of interference, protection can often be provided with no loss in throughput. This is due to the fact that after a failure, links that previously interfered with the failed link can be activated, thus leading to a “recapturing” of some of the lost capacity. We provide both an ILP formulation for the optimal solution, as well as algorithms that perform close to optimal. More importantly, we show that providing protection in a wireless network uses as much as 72% less protection resources as compared to similar protection schemes designed for wired networks, and that in many cases, no additional resources for protection are needed.

We develop a novel network protection scheme that provides guarantees on both the fraction of time a flow has full connectivity, as well as a quantifiable minimum grade of service during downtimes. In particular, a flow can be below the full demand for at most a maximum fraction of time; then, it must still support at least a fraction q of the full demand. This is in contrast to current protection schemes that offer either availability-guarantees with no bandwidth guarantees during the downtime, or full protection schemes that offer 100% availability after a single link failure. We develop algorithms that provide multiple availability guarantees and show that significant capacity savings can be achieved as compared to full protection. If a connection is allowed to drop to 50% of its bandwidth for 1 out of every 20 failures, then a 24% reduction in spare capacity can be achieved over traditional full protection schemes. In addition, for the case of q = 0, corresponding to the standard availability constraint, an optimal pseudo-polynomial time algorithm is presented.

This paper develops a mesh network protection scheme that guarantees a quantifiable minimum grade of service upon a failure within a network. The scheme guarantees that a fraction q of each demand remains after any single link failure. A linear program is developed to find the minimum-cost capacity allocation to meet both demand and protection requirements. For q ≤ 1/2, an exact algorithmic solution for the optimal routing and allocation is developed using multiple shortest paths. For q >; 1/2, a heuristic algorithm based on disjoint path routing is developed that performs, on average, within 1.4% of optimal, and runs four orders of magnitude faster than the minimum-cost solution achieved via the linear program. Moreover, the partial protection strategies developed achieve reductions of up to 82% over traditional full protection schemes.