MPLSにおける高速障害回復技術動向- Fast Reroute 方式 –岩田 淳
NEC ネットワーキング研究所
E-mail: a-iwata@ah.jp.nec.com
TEL: 044-856-2123, FAX: 044-856-2230
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation1概要• (1)背景• (2) 障害回復方式概要• (3) Fast Reroute方式– Cisco方式– Juniper方式– Axiowave方式• (4) Shared Fast Reroute方式– NEC方式– 性能評価例• (5) その他課題– Interoperabilityの標準化– OAMの標準化•Nov.(6)まとめ
2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation2

障害回復方式概要 #1• MPLS LSPの障害回復方式のフレームワーク– V.Sharma (Jasmine Networks), “Framework for MPLS-based
recovery,” draft-ietf-mpls-recovery-frmwrk-03.txt, Jul. 2001

• 障害回復方式：2方式に大きく分類– (1) Rerouting方式：• (a) established-on-demand(障害発生検出後に迂回経路探索設定)• (b) pre-qualified (障害前に迂回経路資源の確認のみ実行）– (2) Protection switching方式：• pre-established (障害前に迂回経路設定)• Protection switching方式の方式の分類– (1) 1+1: Working / Recovery pathの両者に同一トラヒックを流し、Egress側で障害を検出– (2) 1:1 : Working pathの障害時にRecovery pathへ変更、それまではRecovery pathは低優先のTraffic (低Preemptionpriority)で利用されている。
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

3

障害回復方式概要 #2• 障害回復の位置による3手法

Backup LSP
Primary LSP– Local Repair (fast reroute)• Link Recovery / Restoration• Node Recovery / Restoration– Global Repair

Switch-over– Alternate Egress Repair
NotifyPrimary LSP

Primary LSP

NotifySwitch-overBackup LSP

Primary LSP
Backup LSP

Switch-over Backup LSP
Dual-homing
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

4

障害回復方式概要 #3

ReroutingLocal Repair(Link)

Local Repair(Node)

Global Repair

AlternateEgress Repair

回復時間：△
予備帯域なし回復時間：△
予備帯域なし回復時間：×
予備帯域なし回復時間：*
予備帯域なしProtection (1+1) 回復時間：◎ 回復時間：◎ 回復時間：◎ 回復時間：*
予備帯域：2倍 予備帯域：2倍 予備帯域：2倍 予備帯域：2倍
以上
以上
以上
Protection (1:1) 回復時間：○
予備帯域：低Pri user収容

回復時間：○
予備帯域：低Pri user収容

回復時間：△
予備帯域：低Pri user収容

回復時間：*
予備帯域：低Pri user収容Fast−Reroute(FRR)の狙う領域*: Local repair/Global repairのいずれの方式と組み合わせるかで回復時間が決定
All Rights Reserved, Copyright(C)5Nov. 2001,MPLS Japan

2001 NEC Corporation

Local Repair (Fast Reroute)• Cisco方式– R.Goguen e al., “RSVP Label Allocation for Backup Tunnels,”
draft-swallow-rsvp-bypass-label-01.txt, Nov.2000• Juniper方式– D. Gan et al., “A Method for MPLS LSP Fast-Reroute Using
RSVP Detours,”draft-gan-fast-reroute-00.txt, Apr.2001• Axiowave方式– D. Haskin et al., “A Metho for Setting an Alternative Label
Switched Paths to Handle Fast Reroute,” draft-haskin-mplsfast-reroute-05.txt, Nov.2000• NEC方式 (Shared Fast Reroute)– A. Iwata et al., “MPLS Signaling Extensions for Shared FastRerouting,” draft-iwata-shared-fastreroute-00.txt, Jul.2001
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

6Cisco FRR: “Bypass Tunnel” #1• Label-stack Tunnel：リン
PLR
Merge-node
ク・ノード障害に対し、同一リンク、ノード経由の複数のLSPを多重して復Switch-over
旧• PLR (Point of Local
Label-stack TunnelRepair) と Merge node間のTunnel生成
Label IP-PDU

Nov. 2001,MPLS Japan

Tunnel-label

All Rights Reserved, Copyright(C)2001 NEC Corporation

7

Cisco FRR: “Bypass Tunnel” #2
PLR

Merge-node• Working path (Primary path)のLabel値はHop-by-hopに変更 Label値• Merge nodeでのGlobal label
space の利用例（異なるI/FからSwitch-overの受信ラベル値に対して出力ラベル値を一意に決定、MergePHPの実現の容易性）
Label-stack Tunnel• PLRにおいてMerge nodeでのPrimary Pathでの受信ラベル値に変更後Bypass Tunnelヘッダ Label IP-PDU
付与• Merge nodeの1ノード前でPenultimate Hop Pop (PHP)を動作
Tunnel-label Primary pathのNov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)8受信ラベル値
2001 NEC Corporation

Cisco FRR: “Bypass Tunnel” #3• LocaｌRepairからGlobal Repairへの遷移による経路最適化手順
PLR
Merge-node
PathErr（Notify:local repair)

PLR

Switch-overSwitch-over

一定
時間後

Global Repair

Local Repair
Nov. 2001,MPLS Japan

Merge-node

経路長、リソース利用率の9最適化

All Rights Reserved, Copyright(C)2001 NEC Corporation

Juniper FRR #1
Backup LSP #3• リンク、ノード障害に対応し、Primary LSP上の全ノード Backup LSP #1
Primary LSP
からBackup LSP設定
Backup LSP #2• 1ホップ以上離れたノードへSwitch-overのBackup LSP• Cisco方式のようなLSPのIngress
Egress
多重化の障害回復なし Primary PATH (Fast-Reroute obj)
RESV(Record Route obj)
• Primary LSPでのRESVで
Record_Route objectによ経ＣＳＰＦ PATH (Detour obj)
路上の全ノードを知る
RESV Backup LSP #1• CSPFにより迂回経路用の経路計算実行
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)102001 NEC Corporation

Juniper FRR #2• PATH Message (for Primary LSP)迂回経路のホップ数0123
制限+-------------+-------------+-------------+-------------+– Fast Reroute object|
Length (bytes)| Class-Num |C-Type|+-------------+-------------+-------------+-------------+| Setup Prio | Hold Prio
| Hop-limit| Reserved|+-------------+-------------+-------------+-------------+|
Bandwidth|+-------------+-------------+-------------+-------------+|
Exclude colors|+-------------+-------------+-------------+-------------+|
Include colors|+-------------+-------------+-------------+-------------+• PATH Message (For Backup LSP)

迂回経路の
特性要求

PreemptionのPriority– Detour object
0123+-------------+-------------+-------------+-------------+|
Length (bytes)| Class-Num |C-Type||-------------+-------------+-------------+-------------+|
Source ID|+-------------+-------------+-------------+-------------+|
Downstream Node ID|+-------------+-------------+-------------+-------------+
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

PLR
迂回経路
11で除く
ノード

Axiowave FRR #1• Backup LSP#1はPrimary Backup LSP #2
Backup LSP #1
LSPの逆向き
Ingress
Egress• Backup LSP#2はPrimaryPrimary LSP
LSPとDisjoint path
Ring網では• Backup LSP#1,#2の経路
効率高計算の容易性Backup LSP #2
Ingress

EgressBackup LSP #1

Nov. 2001,MPLS Japan

Local Wrapping

All Rights Reserved, Copyright(C)2001 NEC Corporation

Primary LSP
12

Axiowave FRR #2• Ingressの障害検出：

Backup LSP #2– 逆向きのLSPにトラヒックを検出時点で検出
Backup LSP #1
Ingress
Egress• 迂回経路の最適化– Ingressの障害検出後、Primary LSP
Backup LSP#2へ直接迂回
Encapsulated
ルーティング– パケットのReorderingの問題
Backup LSPあり（IngressでのBuffering制御なしの場合）
Label-stack LSP #2
Label-stack LSP #1• 1:1, N:1のProtection機能
Ingress
保持Egress– Label StackingのBackup
LSP
Primary LSPs
– Egress nodeでのGlobal
Label SpaceによるLabel管理
Global Label
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)13Spaceによる管理
2001 NEC Corporation

Axiowave FRR #3• Restoration Shortcut機構

Backup LSP #2– 特にVoIPのようなDelay
Backup LSP #1
Ingress
Egresssensitiveなアプリケーションにたいして、FRR後のPrimary LSP
転送遅延を小さくするた
Shortcut LSP
めにTransit nodeからShortcut pathを許す– Shortcut pathを行う際にはもともとの経路計算の容易性は失われる

Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

14

Local Repair方式の課題• Cisco / Juniper / Axiowave 方式:– SONET protectionと同等レベルの障害回復性能を実現• 50 msec restoration– 基本的にBackup LSP (Local Repair LSP)に対して帯域確保– => Backup LSP間の帯域資源をできるかぎり共有化による網資源の効率的運用が必要• Backup LSPの帯域資源の共有化に関する提案方式– S. Kini et al., Draft-kini-restoration-shared-backup-01.txt– 単一リンク、ノード障害復旧を保証する際の全 Backup LSPの中からできるかぎり共有化– => OSPF / ISIS の拡張による共有計算方法の提案– => 本コンセプトはFast-reroute (FRR)へは適用されていない。
– Nov.
=>2001,MPLS
FRRへの適用(NECShared Fast Reroute方式)
JapanAll Rights Reserved, Copyright(C)152001 NEC Corporation

NEC FRR- Shared Fast Reroute方式• (2) Shared fast-reroute方式の目的• (3) Shared fast reroute方式概要– (I) 単一primary LSPの場合– (ii) 複数のload-balanced primary LSPの場合• (4) RSVP-TE signaling概要– (I) IngressからEgress方向への分散CSPF– (ii) Ingress node 主体のCSPF– (iii) Egress からIngress方向への分散CSPF• (5) 性能評価例
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

16

Shared fast-reroute方式の目的• (1) Backup LSPの帯域資源の最小化– LSP資源を共有化するための2つの手法• (I) Label merge: LSP資源全体を共有化 (label ID と帯域)
• (ii) Logical merge:帯域のみ共有し、Labelは非共有• (2) Backup LSPの共有化の計算負荷を最小化– (I) 単一Primary LSPのBackup LSPについては最低共有化– (ii) 異なる Primary LSPに対するBackup LSPsについては、
S.Kini の手法で可能（計算負荷が許せば）– >> 最低単純な(I)の資源共有化のアプローチを採用すべき

Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

17

Shared fast reroute 方式概要
- 単一primary LSPの場合• Primary path上の全ノードが Ingress Primary LSP Egress
Egress向けのbackup LSPの#1
#2 #3
計算 (CSPF)– Juniper方式の特別な状況• Backup LSPの網リソースの最大共有化

Backup LSPs

– Backup LSP #1に帯域を共有す
るようにLSP #2, #3を設定
Ingress– Label mergeを加えてさらにラベ#1
ル資源も共有可能Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

BW is shared
Label mergeでLabel資源も低減
Egress#2#3

18

Shared fast reroute 方式概要
- 複数 load-balanced primary LSPの場合#1Primary LSP #1• Ingress – Egress pairのトラ
X%
Ingress
Egress
ヒックをLoad balancingのた
100-X%
めにLoad splitting
Primary LSP #2– X% for #1, 100-X% for #2• (1) Primary LSP #1, #2に対して共有Backup LSP #3を計算
Ingress• >> N 個load balanced LSPへ拡張可能#1
Max{x, 100-x}(%)の帯域のみ予約

Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

Egress#2#3
Backup LSP#319

Shared fast reroute 方式概要
- 複数 load-balanced primary LSPの場合 #2Primary LSP #1• (2) primary LSP #1, #2 に対X%
Ingress
Egress
して独立にBackup LSP #1,100-X%#2を計算
Primary LSP #2• >> N 個load balanced LSP
へ拡張可能
Ingress
Egress#1#1#2 #2 #3 #3

Ingress

Label merge
Egress#2 #2 #3 #3

Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

20

RSVP-TE signaling 概要- IngressからEgress方向への分散CSPF Ingress
N2 N3• Primary LSPが設定された後でBackup LSP設定#1#2#3• Ingress, N2, N3が分散的にCSPF によりBackup LSPを設定
N5N6• Ingress ：IngressN2 N5 N3 N6– Primary LSPに対してEgress宛のDisjoint なBackup LSP #1計算
PATH #1– “Backup LSP Trigger” ＋ERO#1
RESV #1(Backup LSP#1の 経 路）をN2へ送信
Backup LSP– N2はERO#1へマージできるように Trigger
CSPF(ERO #1)• 中継ノード：– Nth backup LSP をBackup LSP#1
へマージできるようにCSPF
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

PATH #2
RESV #2

EgressEgressLabel merge
PATH #3
RESV #3

Backup LSP
Trigger Ack

21

RSVP-TE signaling 概要-Ingress node 主体のCSPF -• Primary LSPが設定された後でBackup LSP設定• Ingress, N2, N3が分散的にCSPF によりBackup LSPを設定

Ingress

N2

N3

#1

#2

#3

N5Trigger– ERO#1, ERO#2, ERO#3 (ERO #1)をそれぞれIngressが計算• 共有可能なBackup LSPの生成が容易
Nov. 2001,MPLS Japan

N6IngressN2 N5 N3 N6PATH #1
RESV #1• Ingress がすべてのBackup LSP経路を集中的に計算Backup LSP

PATH #2Egress

Label merge

RESV #2

Backup LSP
Trigger Ack

All Rights Reserved, Copyright(C)2001 NEC Corporation

Egress

PATH #3
RESV #322

RSVP-TE signaling overview- Egress からIngress方向への分散CSPF Ingress

N2N3Egress• Primary LSPとBackupLSPとを同時に設定。
#1#2#3• Primary LSP設定のAck
N5
N6(RESV)の通知と同期させIngressN2 N5 N3 N6ながらBackup LSP設定
Egress
PATH #P• RESV messageがRESV #P
PATH #3
Backup LSPのEROを前RESV #P
段のLSRへ通知することでRESV #3
ERO #3
Backup LSPの共有化を
RESV #P PATH #2
図る。
ERO #2#3 RESV #2
Label merge
PATH #1

RESV #1
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

23

性能評価
• 比較方式– (ALL) ネットワーク内全体の複数の異なるPrimary LSP間でBackup LSPの共有化• 最も必要な資源が少なくなるがネットワーク全体のBackup LSP情報を用いた最適化のため設計は複雑– (Primary) 一つのPrimary LSP用のBackup LSPのみ共有化• 設計は簡単だが ALLに比べて最適化度は低い– (Dedicated) Primary LSP用のBackup LSPの共有化を行わない（従来方式)• ネットワークモデル– 100回のLSP設計要求が到着するシナリオ– 1回の設計要求で1-10個のTraffic要求あり– トラヒック要求の対地はランダムに選択、要求容量は0.1 – 10.0で変化– 物理リンク容量は (16node,26link): 500, (22node,45link): 300• 本容量は ALLの方式ですべてトラヒック要求を収容できるものとしている– 本性能評価結果詳細：2001.11.21の電子情報通信学会NS研究会にて発表予定 (斎藤他, “障害迂回LSPの最適設計法”)
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

24

性能評価結果
3000
e5e4e3n3n4n2e6

Demand生成

Offered Traffic Demand2500
Accommodated Capacity(a) (16node,26link)e2n6e7n1n7(b) (22node,45link)e8n2e2

Shared(ALL)
Shared(Primary)

1500
1000
Dedicated
500

n8e1

2000

LSR0020e1n1n6e7n7n5e8n4n8e5e11

Nov. 2001,MPLSn9 Japane92000Shared(ALL)1500
Shared(Primary)
1000
Dedicated
500

n11n10100

Offered Traffic Demand2500
Accommodated Capacity

e3
e480

3000

e6n34060
Request Sequence

All Rights Reserved, Copyright(C)002001
NECCorporation
e10204060
Request Sequence8025100

その他課題• (1) MPLSのFRR方式の標準がない（本質的な問題）– 各社独自方式でInteroperabilityなし• (2) 異なるFRR方式間のInteroperability問題– A. Atlas (Avici) et al., “MPLS RSVP-TE Interoperability for
Local Protection/Fast Reroute”, draft-atlas-rsvp-local-protectinterop-00.txt, Jul.2001– Cisco, Juniper方式のInteroperabilityに関する提案• (3) OAM方式の標準化– N.Harrison (British Telecom) et al.,“Requirements for OAM
in MPLS Networks,” draft-harrison-mpls-oam-req-00.txt,
May.2001– 障害回復を行う際の基準となる障害検知のためにOAMが必要であるという提案。
Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)262001 NEC Corporation

まとめ• MPLSにおける障害回復方式概要、ならびに高速障害回復方式 (Fast Reroute: FRR)に関する標準化動向を述べた。
• IETF MPLS/CCAMP WGにおいてFRRに関し標準化の合意を行うのが先決• 障害回復方式の性能面、実装容易性などに踏み込んだ詳細な議論が不可欠

Nov. 2001,MPLS JapanAll Rights Reserved, Copyright(C)2001 NEC Corporation

27