Network design is the process of dimensioning IP capacity over an optical network infrastructure to satisfy a given set of demands and reliability constraints. Specifically, we consider the problem of hose-based cross-layer network design, which seeks to find a minimum cost design that is able to route demand for all hose traffic matrices under all specified failure states. While most network design problems are solved as Mixed Integer Programs, a commercial solver can become intractable due to the scale of today's networks. We demonstrate how the classic Benders decomposition algorithm can be applied and improved for this problem and discuss practical implementation aspects. We showcase a horizontally scalable distributed framework to leverage the decomposable problem structure and solve millions of linear programs in a distributed manner, thereby making the network design problem tractable. In contrast to the conventional approach where failure states and traffic matrices are planned sequentially, the Benders algorithm finds global optimal designs across all traffic matrices and failure states. This leads to network designs with improved solution quality and reliability, with 20--30% less IP capacity and spectrum consumption, 50% less link augments and up to 20x faster runtime that enables design for hyper scale networks in a matter of hours.

This paper presents Meta's Production Wide Area Network (WAN) Entitlement solution used by thousands of Meta's services to share the network safely and efficiently. We first introduce the Network Entitlement problem, i.e., how to share WAN bandwidth across services with flexibility and SLO guarantees. We present a new abstraction entitlement contract, which is stable, simple, and operationally friendly. The contract defines services' network quota and is set up between the network team and services teams to govern their obligations. Our framework includes two key parts: (1) an entitlement granting system that establishes an agile contract while achieving network efficiency and meeting long-term SLO guarantees, and (2) a large-scale distributed run-time enforcement system that enforces the contract on the production traffic. We demonstrate its effectiveness through extensive simulations and real-world end-to-end tests. The system has been deployed and operated for over two years in production. We hope that our years of experience provide a new angle to viewing WAN network sharing in production and will inspire follow-up research.

An increasing number of cloud services are operated globally, where the service data are frequently replicated across geographically distributed datacenters to improve service quality and reliability. Such replication generates many one-to-many bulk data transfers over inter-datacenter networks from one datacenter to many receiver datacenters. To provide end-users with guaranteed services, these data transfers are usually required to be completed within designated deadlines. Despite the exponential growth in data demand, there has been little work on guaranteeing deadlines for one-to-many transfers, which is the subject of this paper. This paper proposes a centralized admission control coupled with a scheduling algorithm, named deAdline-Guaranteed transfEr (AGE), to guarantee the deadline of admitted data transfers and utilize the network capacity efficiently. The key idea is to flexibly select the source datacenter for receiver datacenters and allow the remaining receivers to obtain a replica from either the original source or the other receivers that have already received a copy. By jointly allocating the source for receivers and the bandwidth and routing paths for every data transfer, AGE maximizes the number of deadline-satisfied transfers. Our simulations show that compared to the state-of-the-art, AGE guarantees the deadline for up to 70 percent more transfers, achieves at least 2× higher network throughput, and reduces the completion time up to 80 percent.

Several organizations have built multiple datacenters connected via dedicated wide area networks over which large inter-datacenter transfers take place. Since many such transfers move the same data from one source to multiple destinations, using multicast forwarding trees can reduce bandwidth needs and improve completion times. However, using a single forwarding tree per transfer can lead to poor performance as the slowest receiver dictates the completion time for all receivers. Using multiple forwarding trees per transfer alleviates this concern-the average receiver could finish early; however, if done naively, bandwidth usage would also increase and it is apriori unclear how best to partition receivers, how to construct the multiple trees and how to determine the rate and schedule of flows on these trees. This paper presents QuickCast, a first solution to these problems. Using simulations on real-world network topologies, we see that QuickCast can speed up the average receiver's completion time by as much as 10× while only using 1.04× more bandwidth; further, the completion time for all receivers also improves by as much as faster at high loads. Thereby, while some implementation challenges remain, we advocate using a cohort of forwarding trees.

Datacenters provide the infrastructure for cloud computing services used by millions of users everyday. Many such services are distributed over multiple datacenters at geographically distant locations possibly in different continents. These datacenters are then connected through high speed WAN links over private or public networks. To perform data backups or data synchronization operations, many transfers take place over these networks that have to be completed before a deadline in order to provide necessary service guarantees to end users. Upon arrival of a transfer request, we would like the system to be able to decide whether such a request can be guaranteed successful delivery. If yes, it should provide us with transmission schedule in the shortest time possible. In addition, we would like to avoid packet reordering at the destination as it affects TCP performance. Previous work in this area either cannot guarantee that admitted transfers actually finish before the specified deadlines or use techniques that can result in packet reordering. In this paper, we propose DCRoute, a fast and efficient routing and traffic allocation technique that guarantees transfer completion before deadlines for admitted requests. It assigns each transfer a single path to avoid packet reordering. Through simulations, we show that DCRoute is at least 200 times faster than other traffic allocation techniques based on linear programming (LP) while admitting almost the same amount of traffic to the system.