# US 2006/0067217 A1 · Method and apparatus for path selection in telecommunication networks

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

- Number: US 2006/0067217 A1
- Document ID: US20060067217A1
- Status: Published application
- Kind: A1
- Application number: 11/230,286
- Filed: 2005-09-19
- Published: 2006-03-30
- Earliest claimed: 2004-09-30
- Assignees: Fujitsu Limited; Guangdong Telecom Academy of Science and Technology
- Inventors: Lei Li; Yangchun Li; Hitoshi Yamada; Xun Chen
- Web page: https://patentgrep.com/patent/US20060067217A1

## CPC

- H04L 47/125: by balancing the load, e.g. traffic engineering
- H04L 41/12: Discovery or management of network topologies
- H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 45/20: {Hop count for routing purposes, e.g. TTL}
- H04L 45/302: Route determination based on requested QoS
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04L 43/0882: Utilisation of link capacity
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

This invention provides a method and an apparatus for selecting path in a telecommunication network. In the invention, a control strategy parameter is generated based on a control strategy, and a network condition parameter is generated based on the condition of the network, a path cost for each of a plurality of candidate paths is calculated based on the control strategy parameter and the network condition parameter, then a path with the minimal path cost is selected from among the candidate paths.

## Claims

### Claim 1

A method for path selection in a telecommunication network, comprising steps of:
(a) defining a control strategy, and generating a control strategy parameter Util_weight based on the control strategy;
(b) generating a network condition parameter based on the condition of the network;
(c) calculating a path cost for each of a plurality of candidate paths based on said control strategy parameter, said network condition parameter, and network topology information; and
(d) selecting a path with the minimal path cost from the candidate paths.

### Claim 2 (depends on 1)

The method of claim 1, wherein
said network condition parameter is link utilization Ulink; and
said method further comprises:
calculating a link cost Clink for each of the links included in a path based on said control strategy parameter Util_weight and said link utilization Ulink; and
summating the link costs Clink of all the links included in the path as said path cost.

### Claim 3 (depends on 2)

The method of claim 2, wherein in the case of QoS routing, said link cost Clink is calculated with the equation of:
C
link
=
1
1
-
Util_weight
×
U
link

### Claim 4 (depends on 3)

The method of claim 3, further comprises:
setting the maximal link utilization in a path as the link utilization for each respective link in the path.

### Claim 5 (depends on 2)

The method of claim 2, wherein in the case of dynamic load balancing for best-effort traffic, said link cost Clink is calculated with the equation of:
C
link
=
{
1
1
-
Util_weight
×
U
link
,
Util_weight
×
U
link
<
1
Max_Cost
,
Util_wieght
×
U
link
≥
1
where Max_cost is a predetermined constant.

### Claim 6 (depends on 1)

The method of claim 1, wherein said control strategy parameter Util_weight is generated based on at least one of a threshold for hop number of the path and a threshold for link utilization.

### Claim 7 (depends on 6)

The method of claim 6, wherein in the case of QoS routing, said control strategy parameter Util_weight is generated with the equation of:
Util_weight
=
m
(
m
+
n
)
-
n
·
U
max
where n is the number of hops in the minimal-hop path among the candidate paths, m is the difference between said threshold for hop number of the path and n, and Umax is said threshold for link utilization.

### Claim 8 (depends on 6)

The method of claim 6, wherein in the case of the dynamic load balancing for best-effort traffic, said control strategy parameter Util_weight is generated with the equation of:
Util_weight
=
1
U
max
where Umax is said threshold for link utilization.

### Claim 9 (depends on 1)

The method of claim 1, wherein said control strategy is defined in any one of the schemes of:
the same strategy being applied to the whole network;
different strategies being applied to different ingress-egress pairs; and
different strategies being applied to traffics of different levels in a single ingress-egress pair.

### Claim 10

An apparatus for path selection in a telecommunication network, comprising:
a control strategy parameter generating means for generating a control strategy parameter Util_weight based on a control strategy;
a network condition parameter generating means for generating a network condition parameter based on the condition of the network;
a path cost calculating means for calculating a path cost for each of a plurality of candidate paths based on said control strategy parameter, said network condition parameter and network topology information; and
a path determining means for selecting a path with the minimal path cost from the candidate paths.

### Claim 11 (depends on 10)

The apparatus of claim 10, wherein
the network condition parameter generating means monitors and logs link utilization Ulink of each link in the network as said network condition parameter; and
the path cost calculating means calculates a link cost Clink for all of the links included in the path based on said control strategy parameter Util_weight and said link utilization Ulink, and summates the link costs of all the links included in the path as said path cost.

### Claim 12 (depends on 11)

The apparatus of claim 11, wherein in the case of QoS routing, the path cost calculating means calculates the link cost Clink with the equation of:
C
link
=
1
1
-
Util_weight
×
U
link

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the path cost calculating means sets the maximal link utilization in a path as the link utilization for each respective link in the path.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein in the case of dynamic load balancing for best-effort traffic, the path cost calculating means calculates the link cost Clink with the equation of:
C
link
=
{
1
1
-
Util_weight
×
U
link
Max_Cost
,
,
Util_weight
⁢
×
U
link
<
1
Util_weight
⁢
×
U
link
≥
1
where Max_cost is a predetermined constant.

### Claim 15 (depends on 10)

The apparatus of claim 10, wherein the control strategy parameter generating means generates said control strategy parameter based on at least one of a threshold for hop number of the path and a threshold for link utilization.

### Claim 16 (depends on 12)

The apparatus of claim 12, wherein in the case of QoS routing, the control strategy parameter generating means generates said control strategy parameter Util_weight with the equation of:
Util_weight
=
m
(
m
+
n
)
-
n
·
U
max
where n is the number of hops of the minimal-hop path in the candidate paths, m is the difference between said threshold for hop number of the link and n, and Umax is said threshold for link utilization.

### Claim 17 (depends on 12)

The apparatus of claim 12, wherein in the case of the dynamic load balancing for best-effort traffic, the control strategy parameter generating means generates said control strategy parameter Util_weight with the equation of:
Util_weight
=
1
U
max
where Umax is said threshold for link utilization.
