Design and optimization of next-generation internet

Abstract

As applications have become extensions of ourselves, helping us navigate all aspects of life, Internet Service Providers (ISPs) have designed, built, and optimized their networks to enhance the quality of experience in using the applications. Ensuring ubiquitous access, providing more bandwidth, and keeping user data safe are three ever-present challenges facing the next-generation Internet. Consequently, the research in this thesis consists of three parts, Low Earth Orbit Satellite Constellations (LEO-SCs) for global coverage, Space Division Multiplexing Elastic Optical Networks (SDM-EONs) for more bandwidth, and quantum networks for secure communications.

As evident from the ongoing Russia-Ukraine war, high-speed and low-latency Internet access from anywhere has never been so important. LEO-SCs such as Starlink are the solution. But the time-varying topology due to fast-moving satellites makes both routing and traffic engineering difficult. In this thesis, a scalable two-layer routing architecture is first proposed. Based on it, two new routing algorithms, Delay-Bounded Routing (DBR) and Delay-Aware Routing (DAR) are designed to minimize route changes. Segment routing is then introduced to realize arbitrary path routing. Relying on the segment routing, two load balancing algorithms, Delay-Bounded Traffic Splitting (DBTS) and DBTS+ are proposed. Aiming at minimizing failure reaction time, two fast reroute mechanisms, Loop-Free Alternate (LFA) and LFA+, are also studied.

Space Division Multiplexing (SDM) is an advanced optical network technology that explores the spatial domain for a larger bandwidth. In this thesis, we focus on SDM-EONs using multi-core fibers. We find that, to achieve the higher spectrum efficiency, the modulation format that gives the highest data rate within the quality of transmission constraints is always chosen, which leads to lower crosstalk tolerance, and thus more spectrum fragments. To address this problem, MFS, a new modulation format selection algorithm, is designed. Furthermore, under the concept of infrastructure-as-a-service, the network virtualization is also considered in SDM-EONs, where a network service can be implemented by an ordered list of Virtual Network Functions (VNFs) instantiated in different data centers, forming a Service Function Chain (SFC). Aiming at load balancing, the problem of SFC deployment is to admit a given set of service requests such that the maximum index of utilized frequency slot is minimized. An Integer Linear Programming (ILP) is first formulated for finding the optimal solution. A more efficient enumeration approach is then adopted to find the least-cost solution for each SFC with three different cost metrics. To further reduce the computing complexity, a novel heuristic, called stretch algorithm, is designed.

Quantum computing is arguably the biggest security threat due to its potential ability to crack major encryption methods. But a quantum network, which sends information encoded in quantum states (qubits), can be built to secure our data. Existing quantum routing algorithms pre-assign each entangled qubit pair to a specific path. But if the path fails, the pre-assigned qubit pairs may be wasted. By allowing entangled pairs to be shared among different paths with different priorities, a new entanglement routing algorithm is proposed to maximize the network throughput.