# US 6,321,271 B1 · Constrained shortest path routing method

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

- Number: US 6,321,271 B1
- Document ID: US6321271B1
- Status: Granted
- Kind: B1
- Application number: 09/218,576
- Filed: 1998-12-22
- Granted: 2001-11-20
- Earliest claimed: 1998-12-22
- Assignees: Lucent Technologies Inc.
- Inventors: Muralidharan Sampath Kodialam; Wing Cheong Lau; Anlu Yan
- Web page: https://patentgrep.com/patent/US6321271B1

## CPC

- H04Q 11/0478: {Provisions for broadband connections}
- H04L 2012/562: {Routing}
- H04L 2012/5623: {Network design, dimensioning, topology or optimisation}
- H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A real-time method for routing subject to an acceptable delay constraint between nodes in high-speed data networks, such as PNNI protocol networks, uses an illustrative two-phase algorithm employing Dijkstra's algorithm at each phase. In an illustrative first phase, the Dijkstra SPF algorithm is used in seeking the shortest cumulative delay from the destination to the source, thereby generating cumulative delay labels from a node j to the destination node k. The delay results are then employed in the second phase, where the Dijkstra SPF algorithm is illustratively employed for determining administrative weight (AW) as the link metric subject to modification in accordance with results obtained in the first phase.

## Claims

### Claim 1

A method for choosing a path in a network from a source to a destination, the network comprising a plurality of nodes, each node connected to a plurality of other nodes by links, each link having a weights reflecting at least first and second link parameters, paths connecting said source and said destination comprising a plurality of links, said paths being subject to a constraint on the cumulative value of said second parameter for links in a path, the method comprising the steps of:
a. for paths from said destination to said source, performing a minimum-weight path identification based on said second parameter for paths in said network, thereby to generate labels identifying weights for said second parameter for each nodej to destination k,
b. for paths from said source to said destination performing a minimum-weight path identification from said source using said first parameter as a link metric, and
c. eliminating any nodes that would cause the constraint on said cumulative value for said second parameter to be violated.

### Claim 2 (depends on 1)

The method of claim 1 wherein said minimum-weight path identification for paths from said destination is accomplished using a Dijkstra SPF algorithm.

### Claim 3 (depends on 2)

The method of claim 2 wherein said minimum-weight path identification for paths from said source is accomplished using a Dijkstra SPF algorithm.

### Claim 4 (depends on 3)

The method of claim 3 wherein the method further comprises repeating steps a, b and c for paths between said source node and each possible destination node in said network.

### Claim 5 (depends on 4)

The method of claim 4 wherein for destination nodes after a first destination node, path information from said source to one or more other destinations is used in determining acceptable paths to each said nodes after said first destination.

### Claim 6 (depends on 1)

The method of claim 1 wherein said step of performing a minimum-weight path identification from said source comprises (i) labeling a node i with cumulative AW from the source node, and (ii) tracking cumulative delay (Ds,i) from the source based on values for said second parameter during said minimum-weight path identification from said destination.

### Claim 7 (depends on 6)

The method of claim 6 wherein said step of eliminating comprises labeling neighboring nodes j of a permanently labeled node i only if (Ds,i+dj,k+δi,j) is less than the specified end-to-end constraint on said second parameter, where δi,j is the value of said second parameter for the link between nodes i and j, and dj,k is the value for said second parameter for the link between nodes j and k.

### Claim 8 (depends on 7)

The method of claim 7 wherein said second parameter is link delay.

### Claim 9 (depends on 6)

The method of claim 6 wherein said second parameter is link delay.

### Claim 10 (depends on 1)

The method of claim 1 wherein operation of said network is in accordance with PNNI protocols.

### Claim 11 (depends on 10)

The method of claim 10 wherein said second parameter is link delay.

### Claim 12 (depends on 1)

The method of claim 1 wherein said first parameter is administrative weight (AW).

### Claim 13 (depends on 1)

The method of claim 1 comprising the further step of eliminating any paths in said minimum-weight path identification for paths from said source for which the cumulative value for said first parameter exceeds a predetermined maximum.
