Loop-Free and Multi-Path Network Methods

Background

The recent state of the art in network routing has been dominated by the Border Gateway Protocol (BGP). While BGP is the standard for inter-domain routing, it primarily relies on single-path propagation based on shortest-path or policy-driven criteria and metrics. Traditional multi-path approaches to network routing are challenged by routing loops and slow convergence in changing network topology environments. More recently, Software Defined Networking (SDN) and Segment Routing have attempted to provide more granular control; however, ensuring loop-free paths across multiple autonomous systems without impractical overhead remains a stubborn issue. In considering larger-scale network communications involving internet protocols (IP), these modern networks require higher resilience and bandwidth, making the ability to utilize multiple paths simultaneously without the risk of circular routing is highly desirable.

Technology Description

To help address these challenges in network routing and communications protocols, researchers at UC Santa Cruz (UCSC) have developed methods for achieving loop-free multi-path routing across different network domains. The UCSC approach utilizes a specialized control logic that determines multiple valid next-hop options for a given destination. A core feature of the novel methods involves the use of ordering constraints or distance-based metrics to ensure that each selected path progressively moves "closer" to the destination, which effectively prevents the formation of routing loops. By dynamically updates these paths in response to real-time network topology changes, this allows traffic to be distributed across multiple independent systems and networks. Moreover, the decoupling of the path computation from a single-best-route constraint enables a node to maintain a set of viable backup and parallel routes, which significantly increases throughput and fault tolerance as compared to traditional single-path inter-domain protocols.

Applications

• internet access - internet service providers
• data centers - data center interconnects
• enterprise systems - software-defined wide area network
• servers and service - content delivery networks

Features/Benefits

• Eliminates routing loops through ordering constraints (e.g., sequence numbers or distance metrics) ensure packets never return to previously visited node.
• Increased network throughput by multi-path forwarding, allowing a single traffic stream or multiple streams to be spread across all available valid routes simultaneously.
• If one link fails, immediately switches to an alternate pre-calculated path without waiting for global BGP convergence.
• Supports decentralized computation models which enable individual routers to make local multi-path decisions without requiring a global view internet topology.

Intellectual Property Information

Patent Pending

Related Materials