# US 2005/0088965 A1 · Rapid alternate paths for network destinations

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2005/0088965 A1
- Document ID: US20050088965A1
- Status: Published application
- Kind: A1
- Application number: 10/993,025
- Filed: 2004-11-19
- Published: 2005-04-28
- Earliest claimed: 2003-10-03
- Assignees: Avici Systems, Inc.
- Inventors: Alia Atlas; Raveendra Torvi
- Web page: https://patentgrep.com/patent/US20050088965A1

## CPC

- H04L 45/28: using route fault recovery
- H04L 45/12: Shortest path evaluation
- H04L 45/22: {Alternate routing}
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Network traffic is sent via alternate paths in cases of network link or node failure. An alternate node responds to U-Turn traffic from a primary neighbor to select a further alternate. An algorithm for determining the alternate paths is provided to select loop-free neighbors.

## Claims

### Claim 1

A method of forwarding data packets comprising, at a network node:
storing links to primary neighbor nodes to which the data packet is primarily forwarded;
storing links to alternate neighbor nodes, and
upon receiving a U-turn data packet at the network node from a primary neighbor node, forwarding the data packet to an associated alternate neighbor node.

### Claim 2 (depends on 1)

The method of claim 1 wherein the alternate neighbor node is loop-free for the data packet with respect to the primary neighbor node from which the data packet arrived.

### Claim 3 (depends on 2)

The method of claim 2 wherein the alternate neighbor mode is loop-free with respect to a primary outgoing interface of the primary neighbor node.

### Claim 4 (depends on 2)

The method of claim 2 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary neighbor of the primary neighbor node.

### Claim 5 (depends on 4)

The method of claim 4 wherein the alternate neighbor mode is loop-free with respect to a primary outgoing interface of the primary neighbor node.

### Claim 6 (depends on 4)

The method of claim 4 wherein the alternate neighbor node is loop-free for the data packet with respect to all primary neighbors of the primary neighbor node.

### Claim 7 (depends on 4)

The method of claim 4 wherein the alternate neighbor node is loop-free for the data packet with respect to all nodes failing together with primary neighbors of the primary neighbor node.

### Claim 8 (depends on 2)

The method of claim 2 wherein the alternate neighbor node is the first node on a path to the data packet destination and that path does not utilize any resources that are known to potentially fail simultaneously with any of the primary neighbor's primary next hops.

### Claim 9 (depends on 2)

The method of claim 2 wherein the alternate neighbor node is the first node on a path to the data packet destination and that path does not utilize any resources that are known to potentially fail simultaneously with any of the primary neighbor's primary neighbors.

### Claim 10 (depends on 2)

The method of claim 2 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary remote node, the primary remote node being a node in a sequence of nodes starting at the network node, each node in the sequence being a primary neighbor of the prior node in the sequence with respect to the data packet and each node in the sequence being an alternate neighbor node of the next node in the sequence.

### Claim 11 (depends on 2)

The method of claim 2 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary remote node, the primary remote node being a node in a sequence of nodes starting at the network node, each node in the sequence being a primary neighbor of the prior node in the sequence.

### Claim 12 (depends on 11)

The method of claim 11 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary neighbor of the remote primary node.

### Claim 13 (depends on 11)

The method of claim 11 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary outgoing interface of the remote primary node.

### Claim 14 (depends on 11)

The method of claim 11 wherein the alternate neighbor node is loop-free for the data packet with respect to all primary neighbors of the remote primary node.

### Claim 15 (depends on 11)

The method of claim 11 wherein the alternate neighbor node is loop-free for the data packet with respect to all nodes failing together with primary neighbors of the remote primary node.

### Claim 16 (depends on 1)

The method of claim 1 wherein the network node is primary for the alternate neighbor node.

### Claim 17 (depends on 1)

The method of claim 1 wherein the alternate neighbor node depends on the data packet destination.

### Claim 18 (depends on 1)

The method of claim 1 wherein the alternate neighbor node is determined using a modified Dijkstra algorithm.

### Claim 19 (depends on 1)

The method of claim 1 wherein the U-turn data packet is identified by its being received from a primary neighbor node.

### Claim 20 (depends on 1)

The method of claim 1 wherein the U-turn data packet is identified by an explicit tag.

### Claim 21 (depends on 20)

The method of claim 20 wherein the tag is an MPLS label.

### Claim 22

A method of forwarding a unicast data packet to a globally defined destination comprising:
at a network node, for the destination, storing a function mapping inputs of the network node to outputs of the network node, some of which are used as alternates to reach the destination; and
forwarding the data packet arriving to the network node from the inputs to the outputs according to the mapping function.

### Claim 23

A router comprising:
stored primary neighbor node data indicating next-hops to which data packets are primarily forwarded toward destinations; and
stored alternate neighbor node data indicating next-hops to which the router forwards U-turn data packets.

### Claim 24 (depends on 23)

A router as claimed in claim 23 wherein the alternate neighbor node is loop-free for the data packet with respect to the primary neighbor node from which the U-turn data packet arrived.

### Claim 25 (depends on 24)

A router as claimed in claim 24 wherein the alternate neighbor mode is loop-free with respect to a primary outgoing interface of the primary neighbor node.

### Claim 26 (depends on 25)

A router as claimed in claim 25 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary neighbor of the primary neighbor node.

### Claim 27 (depends on 24)

A router as claimed in claim 24 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary neighbor of the primary neighbor node.

### Claim 28 (depends on 26)

A router as claimed in claim 26 wherein the alternate neighbor node is loop-free for the data packet with respect to all primary neighbors of the primary neighbor node.

### Claim 29 (depends on 26)

A router as claimed in claim 26 wherein the alternate neighbor node is loop-free for the data packet with respect to all nodes failing together with primary neighbors of the primary neighbor node.

### Claim 30 (depends on 24)

A router as claimed in claim 24 wherein the alternate neighbor node is the first node on a path to the traffic destination and that path does not utilize any resources that are known to potentially fail simultaneously with any of the primary neighbor's primary next hops.

### Claim 31 (depends on 24)

A router as claimed in claim 24 wherein the alternate neighbor node is the first node on a path to the traffic destination and that path does not utilize any resources that are known to potentially fail simultaneously with any of the primary neighbor's primary neighbors.

### Claim 32 (depends on 24)

A router as claimed in claim 24 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary remote node, the primary remote node being a node in a sequence of nodes starting at the network node, each node in the sequence being a primary neighbor of the prior node in the sequence with respect to the data packet and each node in the sequence being an alternate neighbor node of the next node in the sequence.

### Claim 33 (depends on 24)

A router as claimed in claim 24 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary remote node, the primary remote node being a node in a sequence of nodes starting at the network node, each node in the sequence being a primary neighbor of the prior node in the sequence.

### Claim 34 (depends on 33)

A router as claimed in claim 33 wherein the alternate neighbor node is loop-free for the data packet with respect to a primary neighbor of the remote primary node.

### Claim 35 (depends on 33)

A router as claimed in claim 33 wherein the alternate neighbor node is loop-free for the data packet with respect to all primary neighbors of the remote primary node.

### Claim 36 (depends on 33)

A router as claimed in claim 33 wherein the alternate neighbor node is loop-free for the data packet with respect to all nodes failing together with primary neighbors of the remote primary node.

### Claim 37 (depends on 23)

A router as claimed in claim 23 wherein the network node is primary for the alternate neighbor node.

### Claim 38 (depends on 23)

A router as claimed in claim 23 wherein the alternate neighbor node depends on the data packet destination.

### Claim 39 (depends on 23)

A router as claimed in claim 23 wherein the alternate neighbor node is determined using a modified Dijkstra algorithm.

### Claim 40 (depends on 23)

A router as claimed in claim 23 wherein the network packet comprises data packets.

### Claim 41 (depends on 23)

The method of claim 23 wherein the U-turn data packet is identified by its being received from the primary neighbor node.

### Claim 42 (depends on 23)

The method of claim 23 wherein the U-turn data packet is identified by an explicit tag.

### Claim 43 (depends on 42)

The method of claim 42 wherein the tag is an MPLS label.

### Claim 44

A router comprising:
means for storing next-hops to an alternate neighbor node at a network node; and
means for forwarding a U-turn data packet to one of the alternate neighbor nodes associated with the primary neighbor from which that U-turn data packet was received by the network node.

### Claim 45

A router comprising:
means for storing a function mapping unicast inputs of the network node to unicast outputs of the network node for a globally defined destination, some of which are used as alternates to reach the destination; and
means for forwarding the data packet arriving to the network node from the inputs from the outputs according to the mapping function

### Claim 46

A method of forwarding data packets comprising:
at a network node storing links to primary neighbor nodes and forwarding data packets to primary paths through primary neighbor nodes;
upon failure of a primary path, forwarding data packets destined from the network node to the primary path to an alternate link to an alternate neighbor node; and
upon receipt of a data packet through an alternate link at the alternate node, forwarding the data packet to an alternate link of the alternate neighbor node.

### Claim 47

A router comprising:
stored primary neighbor node data indicating next-hops to which data packets are primarily forwarded toward destinations; and
stored alternate neighbor node data indicating next-hops to which the router forwards data packets upon failure of a primary next-hop data path; and
alternate neighbor node data indicating next-hops to which the router forwards certain data packets received at the router as an alternate neighbor node.

### Claim 48 (depends on 47)

A router as claimed in claim 47 wherein the data packets received at the router as an alternative neighbor node include the U-turn data packets.

### Claim 49

A method of minimizing path values associated with paths in a network comprising:
storing a data structure defining a network of nodes and links where the links have at least one weight between nodes;
storing plural data sets, each data set corresponding to the paths that yield the solutions of a minimization function, and each element of the data set containing a path value that corresponds to the solution for a particular node of the network for that minimization function; and
for the plural data sets, maintaining a common set of candidate nodes having path values to be inherited by other nodes; and
successively selecting nodes from the set of candidate nodes and computing path values of nodes neighboring the selected nodes from path values of the selected nodes and weight values from functions of the traversed links; and
updating any path value which has been further reduced for a node neighboring the selected node and then adding that node to the common set of candidate nodes if that node is not already in that set.
