Routing Methods, Systems, And Computer Program Products

What is this patent about?

’344 is related to the field of network routing, specifically addressing the challenges of scalability and efficiency in large networks. Traditional routing protocols often rely on destination-based forwarding, which can lead to increased latency and complex routing tables, especially as network size grows. The patent aims to improve routing performance by incorporating path segment information directly into packet headers.

The underlying idea behind ’344 is to enable source routing by encoding a sequence of segment identifiers within a packet's header. These identifiers represent nodes, network interfaces, or network regions along the path to the destination. The key insight is to allow intermediate nodes to forward packets based on these segment identifiers, effectively guiding the packet along a pre-determined path, while still allowing for some flexibility in routing.

The claims of ’344 focus on a method performed by a transmitting node. This involves receiving segment identifiers from other nodes, storing them in a data structure representing the network topology, selecting a sequence of these identifiers based on a policy to define a path segment to a receiving node, identifying the appropriate outgoing network interface based on the first segment identifier in the sequence, storing the remaining segment identifiers in the packet header, and transmitting the packet.

In practice, the transmitting node first learns about the network topology and available segment identifiers through standard routing protocols like link-state or distance-vector protocols. Based on a defined policy (e.g., shortest path, least congested path), it then selects a sequence of segment identifiers that define the desired path. The transmitting node then examines the first segment identifier in the sequence to determine the correct outgoing interface. The remaining segment identifiers are placed in the packet header, allowing downstream nodes to continue forwarding the packet along the intended path.

This approach differs from traditional destination-based routing where each router independently determines the next hop. By embedding path information in the packet header, ’344 enables a form of explicit routing , potentially reducing latency and improving network utilization. Furthermore, the inclusion of a non-predetermined node allows for some dynamic adaptation to network conditions, offering a balance between strict source routing and traditional hop-by-hop forwarding. The use of segment identifiers rather than full IP addresses also contributes to header efficiency.