Benes/CLOS architectures are common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially MZI technology, have made Benes networks a very attractive scalable architecture for optical circuit switches. Numerous routing algorithms for Benes networks were developed starting with linear algorithms having time complexity of \(O(N\log_{2}N)\) steps. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of \(O((\log_{2}N)^{2})\). However, their implementation requires \(O(N^2\log_{2}N)\) wires (termed connectivity complexity), and thus are difficult to scale. We present a new routing algorithm for Benes networks combined with a scalable hardware architecture that supports full and partial input permutations. The processing time of the algorithm is limited to \(O((\log_{2}N)^{2})\) steps (iterations) by potentially forfeiting routing of a few input demands; however guarantees close to 100\% utilization for both full and partial input permutations. The algorithm and architecture allow a reduction of the connectivity complexity to \(O(N^{2})\), a \(\log N\) improvement over previous solutions. We prove the algorithm correctness, and analyze its performance analytically and with large scale simulations.

The emerging multi-fiber optical networks makes it urgent to design large-scale flexible mesh optical cross-connects (OXCs). Though Clos network is the theory for building scalable and cost-effective switching fabrics, the nonblocking conditions of flex-grid optical Clos networks without wavelength conversion remain unknown. This paper studies the nonblocking conditions for the flex-grid OXC-Clos network that is constructed from a number of small-size standard OXCs. We first show that a strictly nonblocking (SNB) OXC-Clos network will incur a high cost, as small-granularity lightpaths may abuse central modules (CMs), rendering them unavailable for large-granularity requests due to frequency conflicts. We thus propose a granularity differential routing (GDR) strategy, the idea of which is to restrict the set of CMs that can be used by the lightpaths of each granularity. Under the GDR strategy, we investigate two system models, granularity-port binding and unbinding models, and prove the wide-sense nonblocking (WSNB) conditions for OXC-Clos networks. We show that the cost of WSNB networks is remarkably smaller than that of SNB networks, and find that the second model can lead to more flexible network-bandwidth utilization than the first model only at a small cost of switching fabrics.

Time-sensitive applications have become increasingly prevalent in modern networks, necessitating the development of delay-guaranteed routing (DGR) solutions. Finding an optimal DGR solution remains a challenging task due to the NP-hard nature of the problem and the dynamic nature of network traffic. In this paper, we propose Deadline-Driven Routing (DDR), a distributed traffic-aware adaptive routing protocol that addresses the DGR problem. Inspired by online navigation techniques, DDR leverages real-time traffic conditions to optimize routing decisions and ensure on-time packet delivery. By combining network topology-based path generation with real-time traffic knowledge, each router can adjust the forwarding directions of packets to accommodate their heterogeneous latency requirements. Comprehensive simulations on real network topologies demonstrate that DDR can consistently provide delay-guaranteed service in different network topologies with different traffic conditions. Moreover, DDR ensures backward compatibility with legacy devices and existing routing protocols, making it a viable solution for supporting delay-guaranteed service.

Survivable routing is crucial in backbone networks to ensure connectivity, even during failures. At network design, groups of network elements prone to potential failure events are identified. These groups are referred to as Shared Risk Link Groups (SRLGs), and if they are a set of links intersected by a connected region of the plane, we call them regional-SRLGs. A recent study has presented a polynomial-time algorithm for finding a maximum number of regional-SRLG-disjoint paths between two given nodes in a planar topology, with the paths being node-disjoint. However, existing algorithms for this problem are not practical due to their runtime and implementation complexities.

This paper investigates a more general model, the maximum number of non-crossing, regional-SRLG-disjoint paths problem. It introduces an efficient and easily implementable algorithmic framework, leveraging an arbitrarily chosen shortest path finding subroutine for graphs with possibly negative weights. Depending on the subroutine chosen, the framework improves the previous worst-case runtime complexity, or can solve the problem w.h.p. in near-linear expected time.
The proposed framework enables the first additive approximation for a more general NP-hard version of the problem, where the objective is to find the maximum number of regional-SRLG-disjoint paths. We validate our findings through extensive simulations.

The nature of datacenter traffic is a high volume of bursty tiny flows and standing long flows, which forms the coexistence of transient and persistent congestion. Traditional congestion control (CC) algorithms have inherent limitations in reconciling fast response and high efficiency towards transients with stability and fairness during persistence. In this paper, we provide an insight that re-architects CC with two control laws, tailored to transient and persistent concerns, respectively. Armed with this key insight, we propose bimodal congestion control (BCC), which is founded on two core ideas: (i) Quaternary network state detection, which further distinguishes transient and persistent states in switches, and (ii) Bimodal control law, which is manifested as the transient controller and persistent controller at sources. The transient controller employs a precise control paradigm that halts flows to drain backlogged packets and ramps down/up flow rates to bottleneck bandwidth directly, striving for high efficiency. The persistent controller grounds itself in traditional CC algorithms, inheriting stability and fairness. We implement BCC in the Linux kernel and P4-programmable switch. Evaluations in testbed and simulations show that compared to DCQCN, HPCC, PowerTCP, and Swift, BCC shortens the convergence time by up to 96\% and reduces flow completion time by 14\%\(\sim\)99\%.

Reinforcement learning (RL)-based congestion control (CC) promises efficient CC in a fast-changing networking landscape, where evolving communication technologies, applications and traffic workloads pose severe challenges to human-derived CC algorithms. RL-based CC is in its early days and substantial research is required to understand existing limitations, identify research challenges and yield deployable solutions. In this paper we present the first reproducible and systematic study of RL-based CC with the aim to highlight strengths and uncover fundamental limitations of the state-of-the-art. We identify challenges in evaluating RL-based CC, establish a methodology for studying said approaches and perform experimentation with RL-based CC approaches that are publicly available. We show that existing approaches can acquire all available bandwidth swiftly and are resistant to non-congestive loss, at the cost of excessive packet loss in normal operation. We show that, as fairness is not embedded into reward functions, existing approaches exhibit unfairness in almost all tested network setups. Finally, we show that existing RL-based CC approaches under-perform when the available bandwidth and end-to-end latency dynamically change. Our codebase and datasets are publicly available with the aim to galvanise the community towards transparency and reproducibility, which have been recognised as crucial for researching and evaluating machine-generated policies.

Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is \(2\)-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of \(O\left(\log m/ \log\log m \right)\) and a lower bound of \(\Omega\left(\log m/ \log\log m \right)\) for polynomial-time approximation algorithms, where \(m\) is the number of static links. We further show that under splittable (resp., unsplittable) and non-segregated routing, even for demands of single source (resp., destination), the problem cannot be approximated within a ratio better than \(\Omega\left(\frac{c_{\max}}{c_{\min}} \right)\) unless P=NP, where \(c_{\max}\) (resp., \(c_{\min}\)) denotes the maximum (resp., minimum) capacity.

Caching can be leveraged to significantly improve network performance and mitigate congestion. However, characterizing the optimal tradeoff between routing cost and cache deployment cost remains an open problem. In this paper, for a network with arbitrary topology and congestion-dependent nonlinear cost functions, we aim to jointly determine the cache deployment, content placement, and hop-by-hop routing strategies, so that the sum of routing cost and cache deployment cost is minimized. We tackle this NP-hard problem starting with a fixed-routing setting, and then generalize to a dynamic-routing setting. For the fixed-routing setting, a Gradient-combining Frank-Wolfe algorithm with (1,1/2)-approximation is presented. For the general dynamic-routing setting, we obtain a set of KKT conditions, and devise a distributed and adaptive online algorithm based on these conditions. We demonstrate via extensive simulation that our algorithms significantly outperform a number of baseline techniques.