Internal

ODP500039 MPLS TE Path

Calculation

ISSUE 1.0 www.huawei.com

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved

 We have learned the information
distribution of MPLS TE before, this
course will focus on how to calculate the
best LSP tunnel when we have the
TEDB.

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 2

 References

 VRP5 Operation Manual – MPLS part

 《 MPLS TE Study Direction 》

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 3

 Upon completion of this course, you
will be able to:
 Understand the process of CSPF
algorithm
 Understand the other constrained
conditions which influence the
process of path calculation

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 4

 Chapter 1 Path Calculation of CSPF

Chapter 2 Other Constrained Conditions

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 5

 Chapter 1 Path Calculation of CSPF

1.1 Overview of CSPF algorithm

1.2 Path calculation of CSPF algorithm

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 6

 Overview of CSPF Algorithm
Overview of CSPF Algorithm

 CSPF is an algorithm with constrained conditions. The constrained

conditions include:
 Cost--the same as IGP
 Bandwidth
 Link attributes
 The path determination process is not designed to find the best route to
all routers--only to the tunnel endpoint.

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 7

 Chapter 1 Path Calculation of CSPF

1.1 Overview of CSPF algorithm

1.2 Path calculation of CSPF algorithm

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 8

 Path Calculation of CSPF Algorithm

“How to choose the best  Constrained SPF—find the

route from RTA to RTF, best route to the designated

which has at least 40Mb router
bandwidth?”

RTB RTF
10
OC3 10 RTE OC3
RTA 10 DS3
10
10
OC3
OC3 10 DS3
10 RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 9

 Path Calculation of CSPF Algorithm

“How to choose the best

route from RTA to RTF,
which has at least 40Mb
 Constrained SPF—find the
bandwidth?” best route to the designated
router

RTA

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 10

 Path Calculation of CSPF Algorithm

“How to choose the best ro

ute from RTA to RTF, whic
 Constrained SPF—find the best
h has at least 40Mb bandwi
route to the designated router
dth?”

RTB
OC3
RTA

OC3

RTC

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 11

 Path Calculation of CSPF Algorithm

“How to choose the best

route from RTA to RTF,
 Constrained SPF—find the best
which has at least 40Mb
route to the designated router
bandwidth?”

RTB
OC3
RTA

OC3

DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 12

 Path Calculation of CSPF Algorithm
“How to choose the best
 Constrained SPF—find the
route from RTA to RTF,
best route to the designated
which has at least 40Mb router
bandwidth?”

RTB
OC3 DS3 RTE
RTA

OC3

DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 13

 Path Calculation of CSPF Algorithm
“How to choose the best
 Constrained SPF—find the
route from RTA to RTF,
which has at least 40Mb best route to the designated
bandwidth?” router

RTB
RTF
OC3 DS3 RTE
OC3
RTA

OC3
OC3
RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 14

 Path Calculation of CSPF Algorithm
“How to choose the best
 Constrained SPF—find the best
route from RTA to RTF,
route to the designated router
which has at least 40Mb
bandwidth?”

RTB
RTF
OC3 DS3 RTE
OC3
RTA

OC3
OC3 DS3
RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 15

 Path Calculation of CSPF Algorithm
 Constrained SPF—find the
“How to choose the best best route to the designated
route from RTA to RTF, router
which has at least 40Mb
bandwidth?”

RTB
RTF
OC3 DS3 RTE
OC3
RTA

OC3
OC3 DS3
RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 16

 Path Calculation of CSPF Algorithm
 Constrained SPF—find the
“How to choose the best
best route to the designated
route from RTA to RTF,
router
which has at least 40Mb
bandwidth?”

RTB
RTF
OC3 DS3 RTE
OC3
RTA

OC3
OC3
RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 17

 Path Calculation of CSPF Algorithm

“How to choose the best

route from RTA to RTF,  Constrained SPF—find the best
which has at least 40Mb route to the designated router
bandwidth?”

RTB
RTF
OC3 DS3 RTE
OC3
RTA

OC3

DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 18

 Path Calculation of CSPF Algorithm

“How to choose the best rou

te from RTA to RTF, which h
 Constrained SPF—find the
as at least 40Mb bandwidth?
best route to the designated
” router

RTB
RTF
OC3 DS3 RTE
OC3
RTA

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 19

 Path Calculation of CSPF Algorithm

“Need to create another LSP  On the basis of which we have done, create
tunnel from RTA to RTG, another LSP tunnel from RTA to RTG
which has at least 40M  At the time, the available bandwidth has
bandwidth, how about the changed.
process?”

RTB RTF
OC3 RTE OC3
RTA
5MB

OC3
OC3 DS3
RTG
DS3
RTC RTD
HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 20
 Path Calculation of CSPF Algorithm

 On the basis of which we have done, create

“Need to create another another LSP tunnel from RTA to RTG
LSP tunnel from RTA to  At the time, the available bandwidth has
RTG, which has at least changed.
40M bandwidth, how
about the process?”

RTA

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 21

 Path Calculation of CSPF Algorithm

“Need to create another LSP

tunnel from RTA to RTG,
which has at least 40M  On the basis of which we have done, create
bandwidth, how about the another LSP tunnel from RTA to RTG
process?”
 At the time, the available bandwidth has
changed.
RTB

OC3
RTA

OC3

RTC

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 22

 Path Calculation of CSPF Algorithm
“Need to create another  On the basis of which we have done, create
LSP tunnel from RTA to another LSP tunnel from RTA to RTG
RTG, which has at least  At the time, the available bandwidth has
40M bandwidth, how changed.
about the process?”

RTB

OC3
RTA

OC3
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 23

 Path Calculation of CSPF Algorithm
“Need to create another LSP  On the basis of which we have done, create
tunnel from RTA to RTG, another LSP tunnel from RTA to RTG
which has at least 40M  At the time, the available bandwidth has
bandwidth, how about the changed.
process?”

RTB

OC3 RTE
RTA
5MB

OC3
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 24

 Path Calculation of CSPF Algorithm

“Need to create another LSP  On the basis of which we have done, create

tunnel from RTA to RTG, another LSP tunnel from RTA to RTG
which has at least 40M  At the time, the available bandwidth has
bandwidth, how about the changed.
process?”

RTB

OC3 RTE
RTA
5MB

OC3
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 25

 Path Calculation of CSPF Algorithm

“Need to create another  On the basis of which we have done, create

LSP tunnel from RTA to another LSP tunnel from RTA to RTG
RTG, which has at least  At the time, the available bandwidth has
40M bandwidth, how changed.
about the process?”

RTB

OC3
RTA

OC3
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 26

 Path Calculation of CSPF Algorithm

“Need to create another LSP

 On the basis of which we have done, create
tunnel from RTA to RTG,
another LSP tunnel from RTA to RTG
which has at least 40M
bandwidth, how about the  At the time, the available bandwidth has
process?” changed.

RTA

OC3
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 27

 Path Calculation of CSPF Algorithm
“Need to create another  On the basis of which we have done, create
LSP tunnel from RTA to another LSP tunnel from RTA to RTG
RTG, which has at least
 At the time, the available bandwidth has
40M bandwidth, how
about the process?” changed.

RTE
RTA

OC3 DS3
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 28

 Path Calculation of CSPF Algorithm

“Need to create another

LSP tunnel from RTA to  On the basis of which we have done, create
RTG, which has at least another LSP tunnel from RTA to RTG
40M bandwidth, how  At the time, the available bandwidth has
about the process?”
changed.

RTF

RTE OC3
RTA

OC3
OC3 DS3
RTG
DS3
RTC

HUAWEI TECHNOLOGIES CO., LTD. RTD

All rights reserved Page 29
 Path Calculation of CSPF Algorithm
“Need to create
another LSP tunnel
 On the basis of which we have done, create
from RTA to RTG,
another LSP tunnel from RTA to RTG
which has at least
40M bandwidth, how  At the time, the available bandwidth has
about the process?” changed.

RTA RTE

OC3
OC3 DS3
RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 30

 Path Calculation of CSPF Algorithm--Result
Node Next-Hop Cost
 Final result
B B 10 Tunnel0 form RTA to RTF choose:
C C 10 RTA->RTB->RTE->RTF
D C 20 Tunnel1 form RTA to RTG
E B 20 choose:
F Tunnel0 30 RTA->RTC->RTD->RTE->RTG
G Tunnel1 40
 MPLS TE can distribute traffic to
several links rationally, this can make
load-balancing.

RTB
RTF
DS3
OC3 RTE OC3
RTA

OC3 OC3
DS3
RTG
DS3
RTC RTD

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 31

 Tiebreaker in CSPF

Tiebreaker in CSPF

 In regular SPF, it is ok to use multiple paths to the destination that

have the same cost. This is called ECMP (Equal-Cost MultiPath).
 In CSPF, only one path will be choose to a destination. When there
are several paths which meet the basic conditions, how to use tiebr
eaker in CSPF?
 Choose the path which has the lowest IGP cost
 Take the path with the largest minimum available bandwidth
 Take the path with the lowest hop count
 If there is still a tie, take one path at random

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 32

 Tiebreaker
The cost is 25,
{cost, available bandwidth} not the lowest
Choose a best path from
cost
RTA to RTZ which has at {10,100M}
least 20M bandwidth?

{8,80M}
RTA RTZ
{4,90M}

{8,90M}
All the remain
All the remain links on the
links on the left {8,90M} right
{10,100M} {5,50M}

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 33

 Tiebreaker
Choose a best path from the largest minimum
RTA to RTZ which has at {cost, available bandwidth} available bandwidth is
least 20M bandwidth? 80M, less than other
paths’

{8,80M}
RTA RTZ
{4,90M}

{8,90M}
All the remain links All the remain
on the left links on the
{10,100M} right
{8,90M} {5,50M}

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 34

 Tiebreaker
Choose a best path from The hop-count to
RTA to RTZ which has at {cost, available bandwidth} destination is 4,
least 20M bandwidth? the others are 3

RTA RTZ
{4,90M}

{8,90M}
All the remain links on All the remain
the left links on the right
{10,100M} {8,90M} {5,50M}

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 35

 Tiebreaker
Choose a best path from Choose a path
RTA to RTZ which has at at random
{cost, available bandwidth}
least 20M bandwidth?

RTA RTZ

{8,90M}

All the remain

All the remain links on the left {8,90M} links on the right
{10,100M} {5,50M}

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 36

 Tiebreaker

Choose a best path from

RTA to RTZ which has at {cost, available bandwidth}
least 20M bandwidth?

RTA RTZ

All the remain links on the left {8,90M} All the remain links
{10,100M} on the right
{5,50M}

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 37

 Chapter 1 Path Calculation of CSPF

Chapter 2 Other Constrained Conditions

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 38

 TE Metric

TE Metric

 In the decision process of LSP tunnel, there are two types of

metric:
 IGP Metric
 TE Metric
 By default, IGP Metric is adopted, once TE Metric is enabled,
then IGP Metric is disabled.
 TE Metric is configured in the ingress interface of tunnel, and it
influent the local decision process only.

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 39

 Explicit Path
Explicit Path
 besides CSPF, we can use Explicit Path to control the process of path
selection.
 To support of Explicit Path is the biggest charm of MPLS TE, we can define
the path of LSP according to the actual demand, to define the path of LSP
can enhance the operational and manageable ability.
 The explicit path consists of a series of nodes. Two kinds of relations exist
between adjacent nodes on an explicit path:
 Strict next-hop: The two nodes must be connected directly.
 Loose next-hop: Other routers can exist between the two nodes.
 When nodes are added or modified in the explicit path, the include
parameter indicates that the established LSP must pass the specified nodes.
The exclude parameter indicates that the established LSP cannot pass the
specified nodes.

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 40

 Strict Explicit Path
Strict Explicit Path

So-called Strict Explicit Path means that the next-hop is connected

directly with pre-hop.
Through Strict Explicit Path, we can control the LSP path precisely.

Egress
C E F
LSR
ERO
B strict;
C strict;
E strict;
D strict;
F strict;

A B D

Ingress Strict
LSR

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 41

 Loose Explicit Path

Loose Explicit Path

 Loose Explicit Path can define that the path must pass
some routers, but there can be some other routers
between the router and its pre-hop.
Egress
C E F
LSR
ERO

D loose;

A B D

Ingress Loose
LSR

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 42

 Question

 What is the difference between CSPF and normal SPF?

 What is the process of Tiebreaker in CSPF?

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 43

  MPLS TE use CSPF to calculate path, and
consider the factors of cost, bandwidth, link
attributes.
Summary
 The purpose of TE tunnel creation is to choose a
best path from source to destination which meet
the constrained conditions, this path may not be a
shortest path.
 MPLS TE support Explicit Path, this is one of the
biggest charm of MPLS TE.

HUAWEI TECHNOLOGIES CO., LTD. All rights reserved Page 44

Thank You
www.huawei.com