This paper presents Facebook's design and operational experience of a Hose-based backbone network planning system. This initial adoption of the Hose model in network planning is driven by the capacity and demand uncertainty pressure of backbone expansion. Since the Hose model abstracts the aggregated traffic demand per site, peak traffic flows at different times can be multiplexed to save capacity and buffer traffic spikes. Our core design involves heuristic algorithms to select Hose-compliant traffic matrices and cross-layer optimization between the optical and IP networks. We evaluate the system performance in production and share insights from years of production experience. Hose-based network planning can save 17.4% capacity and drops 75% less traffic under fiber cuts. As the first study of Hose in network planning, our work has the potential to inspire follow-up research.

IP fast reroute methods are used to recover packets in the data plane upon link failures. Previous work provided methods that guarantee failure recovery from at most two-link failures. We develop an IP fast reroute method that employs rooted arc-disjoint spanning trees to guarantee recovery from up to k-1 link failures in a k-edge-connected network. As arc-disjoint spanning trees may be constructed in sub-quadratic time in the size of the network, our approach offers excellent scalability. Through experimental results, we show that employing arc-disjoint spanning trees to recover from multiple failures reduces path stretch in comparison with previously known techniques.

We develop approaches for disjoint multipath routing and fast recovery in IP networks that guarantee recovery from arbitrary two link failures. We achieve this by developing the first known algorithm to construct three edge-independent spanning trees, which has a running time complexity of O(V2). The property of these trees is that the paths from a source to the destination on the trees are mutually link-disjoint. We illustrate how the three edge-independent trees rooted at a destination may be employed to achieve multipath routing and IP fast recovery. We discuss different ways of employing the trees. The routing of packets is based on the destination address and the input interface over which the packet was received. If the trees are employed exclusively for multipath routing, then no packet overhead is required. If the trees are employed for failure recovery, then the overhead bits will range from 0 to 2 bits depending on the flexibility sought in routing. We evaluate the performance of the trees in fast recovery by comparing the path lengths provided under single- and dual-link failures with an earlier approach based on tunneling. We also evaluate the performance of the trees when used for multipath routing and compare it to equal-cost multipaths (ECMP).

The introduction of coherent optics and wavelength division multiplexing (WDM) in telecommunication networks has led to unprecedented gains in backbone capacity. The increase in optical layer capacity inadvertently exacerbates the problem of traffic loss due to optical component failures. IP networks are designed over optical backbone networks, where each IP link traverses a multihop optical lightpath. Therefore, the failure of optical components often lead to multiple link failures in the IP network. In this paper, we develop an IP fast reroute mechanism using rooted arc-disjoint spanning trees that guarantees recovery from (k-1) link failures in a k-edge-connected network. As arc-disjoint spanning trees may be constructed in sub-quadratic time in the size of the network, our approach offers excellent scalability. Through experimental results, we show that employing arc-disjoint spanning trees to recover from multiple failures reduces path stretch in comparison with previously known techniques.

Central to network tomography is the problem of identifiability, the ability to identify internal network characteristics uniquely from end-to-end measurements. This problem is often underconstrained even when internal network characteristics such as link delays are modeled as additive constants. While it is known that the network topology can play a role in determining the extent of identifiability, there is a lack in the fundamental understanding of being able to quantify it for a given network. In this paper, we consider the problem of identifying additive link metrics in an arbitrary undirected network using measurement nodes and establishing paths/cycles between them. For a given placement of measurement nodes, we define and derive the “link rank” of the network-the maximum number of linearly independent cycles/paths that may be established between the measurement nodes. We achieve this in linear time. The link rank helps quantify the exact extent of identifiability in a network. We also develop a quadratic time algorithm to compute a set of cycles/paths that achieves the maximum rank.

Fast-recovery from link failures is a well-studied topic in IP networks. Employing fast-recovery in Ethernet networks is complicated as the forwarding is based on destination MAC addresses, which do not have the hierarchical nature similar to those exhibited in Layer 3 in the form of IP-prefixes. Moreover, switches employ backward learning to populate the forwarding table entries. Thus, any fast recovery mechanism in Ethernet networks must be based on undirected spanning trees if backward learning is to be retained. In this paper, we develop three alternatives for achieving fast recovery from single link failures in Ethernet networks. All three approaches provide guaranteed recovery from single link failures. The approaches differ in the technologies required for achieving fast recovery, namely VLAN rewrite or mac-in-mac encapsulation or both. We study the performance of the approaches developed on five different networks.

In this paper, we study the problem of identifying constant additive link metrics using linearly independent monitoring cycles and paths. A monitoring cycle starts and ends at the same monitoring station, while a monitoring path starts and ends at distinct monitoring stations. We show that three-edge connectivity is a necessary and sufficient condition to identify link metrics using one monitoring station and employing monitoring cycles. We develop a polynomial-time algorithm to compute the set of linearly independent cycles. For networks that are less than three-edge-connected, we show how the minimum number of monitors required and their placement may be computed. For networks with symmetric directed links, we show the relationship between the number of monitors employed, the number of directed links for which metric is known a priori, and the identifiability for the remaining links. To the best of our knowledge, this is the first work that derives the necessary and sufficient conditions on the network topology for identifying additive link metrics and develops a polynomial-time algorithm to compute linearly independent cycles and paths.

Multi-channel wireless networks are increasingly being employed as infrastructure networks in metro areas. In addition, nodes in these networks employ directional antennas to improve spatial throughput. In such networks, given a source and destination, it is of interest to compute a path and channel assignment on every link in the path such that the path bandwidth is the same as that of the link bandwidth. Such a path must satisfy the constraint that no two consecutive links on the path are assigned the same channel, referred to as "channel discontinuity constraint." In this paper, we develop two graph expansion techniques to compute the minimum cost path between a given node pair that satisfy the channel discontinuity constraint. The first expansion provides the exact solution in polynomial time using minimum cost perfect matching algorithm. The second expansion results in a lesser complexity algorithm compared to the former and is amenable to distributed implementation, while it may result in infeasible paths at times. Through extensive simulations, we study the effectiveness of the routing algorithms developed based on the two expansion techniques and the benefits of employing the minimum cost perfect matching based solution. We show that the lesser complexity algorithm may not be able to compute a path for less than 2% of the calls in the networks considered.