Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Network routing - algorithms, protocols, and architectures
Nội dung xem thử
Mô tả chi tiết
Network Routing
Algorithms, Protocols, and
Architectures
Second Edition
Network Routing
Algorithms, Protocols, and
Architectures
Second Edition
Deep Medhi
Karthik Ramasamy
Morgan Kaufmann is an imprint of Elsevier
50 Hampshire Street, 5th Floor, Cambridge, MA 02139, United States
Copyright © 2018 Elsevier Inc. All rights reserved.
No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including
photocopying, recording, or any information storage and retrieval system, without permission in writing from the publisher. Details on
how to seek permission, further information about the Publisher’s permissions policies and our arrangements with organizations such as
the Copyright Clearance Center and the Copyright Licensing Agency, can be found at our website: www.elsevier.com/permissions.
This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as may be noted
herein).
Notices
Knowledge and best practice in this field are constantly changing. As new research and experience broaden our understanding, changes
in research methods, professional practices, or medical treatment may become necessary.
Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any information,
methods, compounds, or experiments described herein. In using such information or methods they should be mindful of their own safety
and the safety of others, including parties for whom they have a professional responsibility.
To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any injury and/or
damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or operation of any methods,
products, instructions, or ideas contained in the material herein.
Library of Congress Cataloging-in-Publication Data
A catalog record for this book is available from the Library of Congress
British Library Cataloguing-in-Publication Data
A catalogue record for this book is available from the British Library
ISBN: 978-0-12-800737-2
For information on all Morgan Kaufmann publications
visit our website at https://www.elsevier.com/books-and-journals
Publishing Director: Jonathan Simpson
Acquisition Editor: Brian Romer
Editorial Project Manager: Ana Claudia A. Garcia
Production Project Manager: Punithavathy Govindaradjane
Designer: Mark Rogers
Typeset by VTeX
To Karen: the distance cost is now infinite and yet does not feel so
To Deuta: the man who new infinity, probabilistically
To Maa: who has the indefinable ability to see infinity
To Neiloy & Robby: there are infinite paths – take the one you like
— Deep/Debu/Dad
To my wife, Monika, with love
— Karthik
CONTENTS
Foreword (1st Edition) . . . . ... . . . .............. . . . . . ... ... . . ... . . .. ............ .. xxv
Preface (2nd Edition) ........................................................... xxvii
Preface (1st Edition) ......... .................... ............ ...... ............. xxix
About the Authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. xxxv
PART 1 ROUTING: BASICS ANO FOUNDATIONS
CHAPTER 1
1.1
1.2
1.3
1.4
1.5
1.6
1.7
Networking and Network Routing: An Introduction ...... .•...............
Addressing and Internet Service: An Overview . . ..... " ...... .•.. ••.. ......
Network Routing: An Overview . . ......••... , . • •.. .•..
IPv4 Addressing ................................. . . . .... .. .
1.3.1 Classful IPv4 Addressing Scheme ... . . . . . . . . . . . ........ .
l.3.2 SubnettinglNetmask in IPv4 ............................... .
1.3.3 Classless Inter-Domain Routing (CIDR) ........ .
IPv6 Addressing ......... .. .... __ ..... ..... ... ......... ....... .
On Architectures . . . . . . . . . . . . . . . . . .. . . . . . . . . . .
Service .Architecture ...... .... ...••.. ...... , .•.. .•. .....• ... •.......
Protocol Stack Architecture ... . . ..... ....... ......••. ....• ...••. ....•.
1.7.1 as I Reference Model. ...... ... ... .. . ... . . . .... .. . .. . . . . . .... .. .
1.7.2 IP Protocol Stack Architecture ........ ..•....
1.8 Router Architecture. . . . . . . . . . . . . . . . . ... . ... . ... ..... . . . . . .. . . .
1. 9 Network Topology Architecture ... . .. . . . ...... . . .. . . . . . .
1.10 Network Management Architecture .. . ... ..•....
1.11 Global Telephone Network ......... ... ..... . .... . . ...... . . ... .. . . .
1.12 Communication Technologies . . ............. .... ..••..... .•.. .......•.
1.13 Standards Committees ........ ............. ......• ...... •...•. .....•..
1.\3.1 Internet Engineering Task Force ....... ......•. ..... ......
2
4
5
7
8
9
lO
II
1 I
J2
14
J4
J5
20
21
22
22
24
25
26
1.13.2 fnternational Telecommunication Union ......••... , .... . ..... 26
1.14 Last Two Bits. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.14.1 Type.Length. Value (TLV) . . . . . . . . . . . . . . . . . . .. . . 27
1.14.2 Network Protocol Analyzer. . . . . . . . . . . . . . . . ... . . . . ... . . ... . . 27
1.15 Summary 28
CHAPTER 2
2.1
2.2
Further Lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Exercises ... . . . .... . .... ..... . ....... .... . .... ........ . ...... . ... .
Routing Algorithms: Shortest Path, Widest Path, and Spanning Tree ....... .
Background ....... . ... .. .... ....... . ..... ... ........... . . .......... .
Bellman-Ford Algorithm and the Distance Vector Approach . ..... . . ...... . .
2.2.1 Centralized View: Bellman-Ford Algorithm ........... ... ••..
2.2 .2 Distributed View: A Distance Vector Approach ........ ... •.. .......
29
30
31
33
33
36
vii
............ -------------------------------------------- VIII CONTENTS
2.3 Dijkstra's Algorithm ..... ... ........ .•..... .•...•.. .... ..........
2.3.1 Centralized Approach ..................................... .
2.3.2 Distributed Approach ........ ....... . .. . .... ........ . . . ... .
38
38
40
2.4 Comparison of the Bellman-Ford Algorithm and Dijkstra's Algorithm. . . . •... 4J
2.5 Shortest Path Computation with Candidate Path Caching . . ......... __ . 43
2.6 Widest Path Computation with Candidate Path Caching ..... _ . . . . . . . 45
2.7 Widest Path Algorithm ... . . . . . . . . . . . .. . . . . .. . . . . . . . . . . .... . . 47
2. 7.1 Dijkstra-Based Approach.. . . . ... . . . . .. . . . . . . . . . . .....•.. . . 47
2. 7.2 Distance Vector-Based Approach . . . . . . . . . . .. . . . . . 49
2.8 Shortest Widest Path and Widest Shortest Path . . . . . . . . . . . . . . ... . . 49
2.9 Tree, Spanning Tree, and Steiner Tree Algorithms . . . . . . . . . . . . 49
2. 9.1 Spanning Tree: Breadth First Search and Depth First Search ...... .... 50
2. 9.2 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . ..... . . . . . . . . . . ... . . 53
2. 9.3 Steiner Tree . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 55
2.10 k-Shortest Paths Algorithm . . . . . . . • . . . . . . . . . . .... . . . . . . . . . . ... . . 57
2.11 Summary . .... ... . .... ..... . . ..... .............. . . . . . . . . 59
CHAPTER 3
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3 .8
Further Lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • . . . . 60
Exercises . . . . .... . .... .
Routing Protocols: Framework and Principles
Routing Protocol, Routing Algori thm, and Routing Table . . ......•. ..... •...
Routing Information Representation and Protocol Messages, , . .... ... , , , , .. .
Distance Vector Routing Protocol . . ........ _ ...... _ ...•• .....• • _ .
3.3.1 Conceptual Framework and lllustration ... .......... __ .. .
3.3.2 Why Timers Matter . . ..... ..... ... ... .......... ...... . . .
3.3.3 Solutions . . ..... ....... ...... ... ...... ........ ... ............ .
3.3.4 Can We Avoid Loops? ......................................... .
3.3.5 Distance Vector Protocol based on Diffuslng Computation with
Coordinated Updates (DUAL) . .... ... . . . .. . . .. . . . . ... . ... ...... .
3. 3.6 Babel Routing Protocol .. . . . . . . . . . . . . . . ... .
Link State Routing Protocol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ...... .
3.4.1 Link State Protocol: In-Band Hop-by-Hop Dissemination ............ .
3.4.2 Link State Protocol: In-Band Based on End-to-End Session . . . . . . . .. . .
3. 4.3 Route Computation. . . . . . . . . . . ... ... .. . . . . . . .
Path Vector Routing Protocol . . . . . . . . . . . . . . . . . • . . • . . . .•.....
3.5.1 Basic Principle . . ...... ........ . . . . ..•. ..•.... ......•...
3.5.2 Path Vector with Path Caching . . . . . . . . . . . . . . . . .... . .... .
Link Cost . . . ... ............... ........•.... ...... ....•....
3.6.1 ARPANET Routing Metrics ........ ...•...... .... ....•......•...
3.6.2 Other Metrics ... ...... ....... .... .... ......... .... .....•.. ....
Threats to Routjng Protocols ..... ....• ... ....•... . . ... ..•...•.. ..... ...
Sum.mary .. . . . ........ . • .... ..•...•..... .....••. .... •...
Further Looku p ....... ..•...... .•.. . • ... ...•..•• ..... .....•....
Exercises ..
61
64
65
68
69
69
74
78
8J
82
89
90
91
98
99
JOO
JOl
J03
108
108
110
IlD
III
112
112
--------------------------------------------� ............
CHAPTER 4
4.1
4.2
CONTENTS IX
Network Flow Models. . . . . . . . . . . . . . . . . • . • . . . . . . • . . .• . . . . . . . . . . . . . .. 114
Terminologies ... ....... ..... ........ •.... ......••. .... ••.. •... •..•.. I 15
Single-Commodity Network Flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 116
4.2.1 A Three-Node Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.2.2 Formal Description and Minimum Cost Routing Objective _ . 1 17
4.2. 3 Variation in Objective: Load Balancing . . . . . . . . . . . 120
4.2.4 Variation in Objective: Average Delay. . . . . . . . . . . . . ... . . 122
4.2.5 Summary and Applicability. . . . . . . . . . . . 123
4.3 Multicommodity Network Flow: Three-Node Example........... .... 124
4.3.1 MinimuJU Cost Routing: Illustration. . . . . . . . . . . . . . . . . . . . . .. 124
4.3.2 Load Balancing: Illustration ........ . . . . . . . . . . . . . . . . . .. . . . . . . 130
4.3.3 Minimulll Average Delay: Illustration ............ . . . . . . . . . . . . .. 1 33
4.4 Multicommodity Network Flow: Gen eral Lin k-Path Formulation. . . . . . . . . . • .. ] 36
4.4.1 Background on Notation ... .......... .... ... . . . . . . . . . . . . . . • .. 137
4.4.2 Minimum Cost Routing: Gen eral Link-Path Fonnu]atlon . . . . , , . . . . . .. 139
4.4. 3 Load Balancing: Link-Path Formulation .... ......... .....• ..•..... 141
4.4.4 Minimum Average Delay: Link-Path Formulation. . . . . . ...•. . . . . .•.. 142
4.4. 5 How Man y Nonzero Flows at Optimal ity? ... . . ..... . . ..... . 143
4.5 Multicomillodity Network Flow Problem: Non-Splittablc Flow ... ........•.. 145
4.6 Node-Link Formulation. . . . . . . . ... . . . . . . . . . . .... . . . . . . . . . .... . 147
4.6.1 Minimum Cost Single-Commodity Network Flow Problem .. . 147
4.6.2 Minimum Cost Multicommodity Network Flow Problem. . . . 150
4.6.3 Load Balan cing Multicommodity Network Flow Problem .... 151
4.6.4 Shottest Path Routing. . . . . . . . . . . . . . . . . . . . . . . 15 2
4.6.5 Shortest Path Tree. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 153
4.7 Gene rating Traffic Matrix. . . . . . . . . ... . . . . . . . . . . . . .. . . . . . . . . .. . . 153
4.8 Summary . . . . . . . . . . . . . . . • . . . . . •• . . . . . . . . • . 154
Further Lookup . . . . . . . . . . . • . . . . . . • . . . . . . . . . . . . . . • . . . . . . . . . . • . . . . . . . . 154
Exe rcises ....... , . .. .. . ISS
PART 2 INTERNET ROUTING
CHAPTER 5
5.1
5.2
5.3
5.4
5.5
IP Routing and Distance Vector Protocol Family. . . . . . . . . . . . . . . . . . . . . . . .. 160
Routers, Networks, and Routing [nfonnation: Some Basics. . . . . . . . .. . . . . . . .. ] 61
5.1.1 Routing Tabl e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . ] 61
5.1.2 Communication of Routing Informatjon . . . . . . . . 1 64
Static Routes . . . . . . . . . . . . . . . . ... . . . . . .. . . . .. . 164
Routing lnformation Protocol, Version I (RIPv I) . . . . . . . . . . . . . . . 165
5.3.1 Communication and Message Format....... ....... .......... 165
5.3.2 Gen eraIOperation.................... ............... ......... 167
5.3.3 [s RIPvl Good to Use? . . ....... ...... .... ........• ... .......... 168
Routing Information Protocol. Version 2 (RIPv2) . . . . . .. . . • . ... . . . .. . • . . ... 168
Interior Gateway Routing Protocol (IGRP) ..... .....•.. . . . . ... .•......•.. 171
5.5.1 PacketFormat ......... ........ ..... ......••. .... .•.. •... ...•.. 171
............ -------------------------------------------- X CONTENTS
5.5.2 Computing Composite Metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 172
5.6 Enhanced Interior Gateway Routing Protocol (EIGRP) . . . . . . . . . .. . . . . . . . . .. 175
5.7
5.8
CHAPTER 6
6.1
6.2
5.6.1 Packet Format. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. 175
Route Redistribution
Summary .. .
Further Lookup ... ..... .
Exercises ........ ...... ..... ........ ... ......... ..... ....•....
177
179
181
182
OSPF and Integrated IS-IS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 184
From a Protocol Family to an Instance of a Protocol
OSPF: Protocol Features . . . . .... .. ..... .. ... ... .. .
6.2.1 Network Hierarchy ..................................... .
6.2.2 Router Classification .. . . ... .... . . . . .... .... . . ..... .
6.2.3 Network Types ......................................... .
6.2.4 Flooding.. .. . . . . .. . .. ... . .. .. .. .. ... .
6.2.5 Link State Advertisement (LSA) Types ..................... .
6.2.6 Sub-Protocols ................................................ .
185
186
186
186
187
188
189
189
6.2.7 Routing Computation and Equal-Cost MuJtipa th .................... 190
6.2.8 Additional Features . . ... . ...... ... ...... . ... .... ..... . .... . . ... 194
6.3 MuJtitopo1ogy Routing In OSPF . .. ...... .. ...... . ........... .. ..... .. .. 195
6.4 OSPF Packet Format. . . . . . . . . . . . . . . . . . . . .. ... . . . . . . . . . .. . . . 195
6.5 Examples of Router LSA and Network LSA . . . . . . . . 202
6.6 Integrated IS-IS. . . . . . . . . . . . . . . . . . . . . . . . ... . . 203
6.6.1 Key Features. .. .. . . . . . . . . . . .. . . . . . .. . . . . . . . .. .. . . 204
6.7 Similarities and Differences Between IS-[S and OSPF 207
6.8 OSPFv3 and IS-IS for IPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 209
6.9 Additional Extensions to OSPF and IS-IS. . . . . . • . . . . . . . . . ... . . • . . . . . . . . .. 210
6.10 Summary .. .. .. .. .. .. .. .. .. . .. .. .. .. .. . .. .. . .. . .. .. . 2 11
CHAPTER 7
7.1
7.2
7.3
7.4
Further Lookup . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .. 211
Exercises .. 2 12
IP Traffic Engineering .............................. ................ 214
Traffic, Stochasticity, Delay, and Utilization .............................. 215
7.1.1 What Is IP Network Traffic? .. .. .. .. ...... . . . .. . ....... . .. . 2'15
7.1.2 Traffic and Performance Measures . . . . .. . . . .. . . . . . .. .. .. . . . . . .. ... 216
7.1.3 Characterizing Traffic. . . . . . . . .. . . . . . .. . . . .. . . .. . . .. .. .. . . . . .. ... 216
7.1.4 Average Delay in a Single Link System. . . . . .. . . . . . .. . . . . . . . . . . . . .. 217
7.1.5 Nonstationarity of Traffic. . . . . .. . . . . . .. . . . . . . . .. .. .. . .... . 2J 9
Applications' View . . . . . . . . . . ... . . 220
7.2.1 TCP Throughput and Possible Bottlenecks. . . . . . . . . ...... 220
7.2.2 Bandwidth-Delay Product . . . . . . . . . . . . . ... ........ . 221
7.2.3 Router Buffer Size . .. .. .. .. .. .. .. .. .. .. .. .. 222
Traffic Engineering: An Architectural Framework 222
Traffic Engineer ing; A Four-Node Illustration. . . . . . . . . . . . . . . . . .. . . . . . . . . .. 224
7.4.1 Network Flow Optimization ..................................... 224
--------------------------------------------� ............
7.5
7.6
7.7
7.8
7.9
7.10
CHAPTER 8
8. 1
8.2
8.3
8.4
8.5
8.6
8.7
8.8
8.9
8. 10
8.11
CHAPTER 9
9.1
9. 2
CONTENTS XI
7.4.2 Shortest Path Routing and Network Flow ........... .
IGP Metric (Link Weight) Determination Problem for the Load Balancing
Objective: Preliminary Discussion __ .......... ___ .......... ____ .
Determining IGP Link Weights via Duality of MCNF Problems ... .
7.6. 1 TIIustration of Duality Through a Three-Node Network for Minimum
Cost Routing .... . _ . . . . . . . . . . . . . ..... .. . . ... ...... .
7.6.2 Minimum Cost Routing, Duality. and Link Weights .... .... .
7.6.3 mustration of Duality Through a Three-Node Network for the Load
Balancing Objective . . . . .. . . . . . . . ..... . . . . . . . ...... ... . . . . . . . .. .
7.6.4 Load Balancing Problem, Duality, and Link Weights ... . .... .
7.6.5 A Composite Objective Function, Duality, and Link Weights .
7.6.6 Minim.izatjon of Average Delay, Duality, and Link Weights ..
Illustration of Link Wejght Determination Through Duality
7.7.1 Case Study: I .......................................... .
7.7.2 Case Study: 11 . . . . . . . . . . ..... . . . ....•..
Link Weight Detennlnation: Large Networks . . ..... .. . ...• ... .•..
IP Traffic Engineering of PoP-ta-Datacenter Networks ........ __
Sumn1ary . .. . . , . , ..... , .. , .. , ...... , , , , , , , ..... , , , , , , , •...• , , . , , , . , .
Further Lookup . . . . . . . .... . . . . . ...... . .. . . . ....... . . ... .... .... . .. .
Exercises ... . ,', ........•. " . , ..•....... ', .•. ..•...... •...• ', . . . . . . .
Multicast Routing _ .... _ ... __ .... __ ... .........•. _ . • . . _ _ ... __ .... __
Multicast [P Addressing . . ... . . _. _ . . . .... . . ... . .
I nternet Group Management Protocol (IGMP) . . . _ . . . . . .....•.
Multicast Listener Discovery Protocol (MLD) . . .......• ... .....
Reverse Path Forwarding (RPF) . . . . .......... . . ..........•. ...• ....... .
Distance Vector Multicast Routing Protocol (DVMRP) . . ...... ... •.........
Multicast OSPF . . ....... ... .... ... ........ ..... ........ .•.. ••. .....
Core Based Trees .................................................. .
Protocol Independent Multicast (P[M) . . . . . . .....•.
8.8.1 PIM-Dense Mode . . .... . . . . . . . ..... . .. . . .. . . ..... .. . . . .
8.8.2 PIM-Sparse Mode .................................... .
8.8.3 SeJectjng and Advertising Rendezvous Point for PIM Sparse Mode
8.8.4 Source Specific Multicast . . . . . . . . . . . . . . ... . . . .
Inter-Domain Multicast Routing .......................... .
8.9.1 Border Gateway Multicast Protocol (BGMP) ..
8.9.2 Multiprotocol Extension of BGP and a Composite Approach ...
226
231
233
233
235
239
240
242
243
247
247
2 52
253
256
256
256
257
260
261
266
267
268
269
270
273
274
275
277
279
280
280
280
2Sl
Internet Protocol Television (IPTV) Multicasting.... . . . . . . . . ...... . 283
Summary ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . • . . . 284
Further Lookup . . . .. . . . .. . . . . . .. . • . . . . . . . . .. .. . . • . . . . . . • . . . • . . . . . . . .. 284
Exercises . . . . . . . . . . . . . . . • . . . . . . . . . . . . . . . . . . . • . 285
BGP ....... . . ................. ... ..•.•....... ...•............... 286
BGP: A Brief Overview . . . . . . . •. . . • . . . . . . . . . . . . . . •. . . . . . •. . . . •. . . . . . .. 287
8GP: Basic Terminology . . . . . . • . . . • . . . . . . . . . . • . . . . . . . . . . . . . . •. . . . . . . .. 290
............ -------------------------------------------- XII CONTENTS
9.3
9.4
9.5
9.6
9.7
9.8
9.9
9.10
BO P Operations .................................................... . .
9.3.1 Message Operations . ..... ... .. ..... . .. ... . ...... .... . . ........ .
9.3.2 BOP Timers .................................................. .
BGP Configur3tjon Initialization ....................................... .
Two Faces of BOP: External BOP (eBOP) and Internal BOP (iBOP) ......... .
Path Attributes. . . . . . . . . . . ..... ....... ..... . ....... .... . .
BGP Decision Process __ . . ........ ___ ... ......... .
9.7.1 BOP Path Selection Process
9.7.2 Roule Aggregation and Dissemination .. ...... ... .. . ...... . .
9.7.3 Recap. . . ... .... ... .. ..... ... ... .. ...... .. ... ..... .
Internal BOP Sca lability ... .. ....... ... ... ........... .. ........ .
9.8.1 Route Refle ction Approach ..... . . . .. ........ . . . ... ....... .. .
9.8.2 Confederation Approach ....... ... . . ..... ........ ...........•...
Route Flap Damping ............... . . ... ....•........ .............. ...
BOP Additional Features and Extensions ........................... .
9.10.1 Communities ................................................. .
9.10.2 BOP 4-byte Autonomous Systems Number Space ............ .
9.10.3 BOP Mulliprotocol Extension (MP-BOP) ......................... .
9.10.4 BOPforIPv6 ................................................ . .
9.10.5 BOP/MPLS .. . . . . .. ...... . . .. . ..... . . .. . .. ...... . . .
9.11 BOP Vulnerabilities ..... . .. .... .
9.12 Securing BOP ... .. ........... ............ .... .
9.12.1 Secure BOP (S-BOP) . . . . . . . . . . . . . . . . . . . . . . . . ...... .
9.12.2 Secure Origin BGP (soBGP) .
9.12.3 Resource Public Key Infrastructure (RPKI) Architecture
9.13 Fi nite State Machine of A BGP Connection . . ... .... .... . . .... . .
9.14 BGP4 Protocol Message Fonnat .. . . . . ........ ... .......... . . .... .
9.14.1 CommonHeader ...... ................... ..
9.14.2 Message Type: OPEN .................. . .. . . .. ..
9.14.3 Message Type: UPDATE. . .... .... .... ... .... ... . .
9.14.4 Message Type: NOTIFICAT[ON ........................... .
9.14.5 Message Type: KEEPALIVE .................................. ..
9.14.6 Message Type: ROUTE-REFRESH ... ...... • . ..... .........
9.14.7 Path Attribute in UPDATE message .............................. .
291
291
292
293
295
298
302
302
304
305
306
307
309
311
3'13
3'13
314
314
314
314
316
317
317
318
318
320
324
324
324
326
328
328
328
330
9.1 5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .. 331
Further Lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. 332
Exercises ........ . . .................... ........ ...... ........... .... 333
CHAPTER 10 Routing in the Global Internet ...................................... , 334
10.1 Internet Routing Evolution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 335
10.2 Addressing and Routing: Illustrations. . . . . . . . . . . . . . . . . . . . . .. . 337
10.2.1 Scenari o A: Routi ng a Packet (Same Sub net) ....... .....•. ...... ... 339
10.2.2 Scenari o B: Routing a Packet (Intra-Domain) . .... . . . . ..... . . . . . . . . . 340
10.2.3 Scenari o C: Routing a Packet (lnter-Domain) ...... ..•.. .•.......... 343
--------------------------------------------� ............
CONTENTS XIII
10.2.4 Scenario D: Routing a Packet (End-to-End R outing for FixedfMobile
Devices) . . . .. . . . . . . . . . . ... . . . . . . . .... . . ........... . . . . .
10.3 Allocation ofIP Prefixes and AS N umbers ...................... .
345
34 8
10.4 Current Architectural View of the Internet....................... 349
10.4.1 Customers and Providers. Peers and Tiers, and Internet Exchange Points 350
10.4.2 An Illustration on Customer-Provider and Peers ..... . . . .. . . . ..... . . 353
10.4.3 A Representative Internet Connectivity . . . . . . . . . . . . . . 353
10.4.4 Customer Traffic Routing: A Geographic Perspective 356
10.5 Traffic Eng ineering Implications . .. ..... .. ... .. ...... .. ... ... . .... .. ... 358
10.6 Point of Presen ce (PoP) for Large (SPs . . . . . . . . . .. . . . . . . . . . . . .. . .. . . . . . 359
10.7 Pohcy-Based Routing ........................................ 361
10.7.1 BGPWedgies . ....... ............. ....... .. ...... 363
10.8 IP Prefix Hijacking .. .... . . . . . . . . . . . . . ... . . . . . . . . . .. . . . 365
10.9 Detecting and Preventing (P Prefix Hijacking . . . . . . . ....... . . . 368
10.10 Internet Routing Instability. . . . . . . . . . . ... 369
10.11 Size and Growth of thelnternet Routing Architecture. . . . . . . . . . . . . 370
10.12 Addressing the Growth: LocatorflD Separation Protocol (LISP) . . . . . 37 3
10.13 Summary ...... ........ .... .......... .... ......... .......... ....... 375
CHAPTER 11
11.1
11.2
11.3
11.4
11.5
11.6
CHAPTER 12
12.1
12.2
12.3
12.4
12.5
12.6
Further Look up ..................................................... 375
Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 37 6
Routing and Traffic Engineering in Software Defined Networks. . . . . . . . . . .. 378
Software Defined Networks: An Overview. . . . . . . . . . . . . . . . . .. . . 379
OpenFlow .. .... ........... . ............. . . ..... . ..... . .. ..... . .
Routing Decisions ......... .... __ .......... ___ . . ..•. __ .... .
Traffic Engineering for Aggregated Flow Routin g. . . ... . _ .. .
J 1.4.1 Aggregation at Origin-Dest.ination Level ......................... .
11.4.2 Traffic Engineering for Multiple Services . . . ... ........ . .... ... .
1 1.4.3 Traffic Engi neering in the Presence of Flow Table Limits ......... .
1.1.4.4 Remark: Using Optimization Models in Practice
Flow Management Approaches ..................................... .
Summary ...... ............ . ..... ........ . ... .... .
Furrher Lookup .. ..... .. . . . . . . . . . . . . . . . . .. .... .
Exercises . . ...... ....... .
Routing and Traffic Engineering in Data Center Networks . .............. .
Cloud Services and Data Center Applications
Data Center Network: A Simple Illustration ..
Data Center Network: RoutingfForwarding Requirements . . ..... . . .
Fat-Tree Data Center Topology ......................... .
12.4.1 Addressing ...... ...... ... ... . ...... ... ... ............. . .
12.4.2 Routing Table ... . . . . . . . .. .. . . . ... ... .. .
12.4.3 Routing Paths ....................................... .
Portland Approach for the Fat-Tree Topology . . . ........... . ........... .
Multipath Ro uting and Traffic Engineering for Fat-Tree Topology .......... .
382
386
388
388
389
390
392
392
394
394
394
396
397
39 8
400
401
402
404
40 5
405
40 7
............ -------------------------------------------- XIV CONTENTS
12.7 BCube ................................................... . 409
12.7.1 RoutiJlgPaths .... . . ............. ....... ...... ......... 411
12.7.2 Routing ProtocoL ... ..... .... . . ... . .. .... . ........ . .......... .. 412
12.8 Multipath Routing and Traffic Engineering for BCube Architecture. . . . . . . . .. 412
12.9 Border Gateway ProtocoL (BGP) in Ultra Large Data Center Networks . 413
12.9.1 5 -stage CLos Topology and eBGP for Routing. . . . . . . . . . . . . . . . . . . . .. 414
12.10 Software-Defined Network.ing for Data Center Networks. . . . . . . . . . . . . . . . . .. 417
12.11 Convergence Time and Performance .... . . ........ ...... .....••..•.. .... 4 19
12.12 Summary . . ... ..... . . ... . . ........ .... ..... . ... . ... .... .... ... . . ... 420
Further Lookup ....•.. .•... ....• ..•. ... ..••..• • . ... ..•. ..•...... 420
Exercises _ . 4 21
PART 3 ROUTER ARCHITECTURE & DESIGN
CHAPTER 13
13.1
13.2
13.3
13.4
13.5
13.6
13.7
CHAPTER 14
14.1
14.2
Router Architectures. . .. .. . . .. .. . .. .. . . . . . . • . . . . . . . .. . . .. .. . .. .. .. 424
Functions of a Router . . .... , ...... .. , ... , ..• ...•.... , , ....•......
13. '1.1 Basic Forwarding Functions . __ ..... ..•... •... ... ....••..
] 3.1.2 Complex FOlwardjng Functions ...... . ..... .
13.1.3 Routing Proce<s Functions. .. .. .. .. . .. . . .... .. .
13.1.4 Routing TabLe Versus Forwarding Table . . .. . . ...... ... _. _ .. .
13.1.5 Performance Indicator of Routers ... . . . . ... .. .
Types of Routers . . .... .... ..... ..... ..... .....•. ... ............
E1elnents of a Router ...... , .........• ... ............ ......•.. .•.. .....
Packet FLow .............................................. .
13.4.1 Jngress Packet Processing ... ,.,', .. , . . . . , .. ,.,',. ," , . . ,.
13.4.2 Egress Packet Processing. . . . . . . . . . . . . . .. ...... . . . . .
Packet Processing: Fast Path Versus Slow Path .... _ ...... ...... .
13.5.1 Fast Path Functions. . ... ... ........... . .
13.5.2 SLow Path Operations .................................. .
Router A rchitectures . . . . , . . . ... .. , . . , . . . . . . .. , . . . , . . . . . , ....... , . .. , ,
13.6.1 Shared CPU Architectures ............................... .
13.6.2 Shared Forwarding E ngine Architecture ........... ....• ...•.. •...
13.6.3 Shared Nothing Architectures. . . . ...•... ... ... _ ••..
] 3.6.4 Clustered Architectures . ... ... . . . . . . . • . . . . . . . . .. .. .
Summary ... ..... ....... . . ... . . .... . .... .. .
Further Lookup .......... ......•.. ....... .• _ ... ...... ....• _ ...
Exercises ..
425
426
426
42 7
428
428
429
430
433
434
435
435
43 7
43 9
441
441
444
447
4 49
450
451
451
IP Address Lookup Algorithms. . . . . .. .. . . . . . . • . • . . . . . .. . . .. .. . .. .. .. 454
Impact of Addressing On Lookup. . . . . . .. . . . . . . . . . . . . ... . . . 455
14.1.1 Address Aggregation . . .. . . . ... . . . . .. . . . . .. . ........... . . 457
Longest Prefix Matching. . . . . . . . . . . . . . . . . . . . . . . . . . 458
14.2.1 Trends, Observations, and Requirements .... _ .... ......• _... 459
14.3 NaIve Algorithms . . . . . . . . . . . .. . . . . . . . . . . •. . ... .. . ..•. 460
14.4 Binary Tries ..... ..... .... ........ . . ... ..••.... ...... •...•. ..... .... 461
--------------------------------------------� ............
1 4.5
1 4.6
1 4.7
1 4.8
1 4.9
CONTENTS XV
14.4.1 Search and Update Operations ......... .•.. .•......• ...•..
14.4.2 Path Compression . ...... . ...... .............. ............. ... .
Multibit Tries ................................................. .
14.5.1 Prefix Transformations.
14.5.2 Fixed Stride Multibit Trie
14.5.3 Search Algorithm ...... ....... ..... ... ...••..... .•..•. ......
14.5.4 Update Algorithm ..... •...•.. ....... .....•. ..•.. •...•• ........
14.5.5 Implementation................ . .. , ... .... . . .... ..
14.5.6 Choice of Strides . .. . . . . .. .. . . . ... . .. .. . .... . . .
14.5.7 Variable Stride Multibit Trie
Compressing Multibit Tries . . . . . . . . . . . . . . . . . . .. . . . . .... .. . . .
14.6. 1 Level Compressed Tries .... •........ ..•. ..•...... ....•. ........
14.6.2 Lulea Compressed Tries . . ..•... •..... .....•. ..•.. •.. ...........
14.6.3 Tree Bitmap ................................................. .
Search by Length Algorithms. . . . . . . . . . . . . . . . . . . . • ... .....
14.7.1 Linear Search on Prefix Lengths ........... .... .
14.7.2 Binary Search on Prefix Lengths ............ . ...... . ...... .
Search by Value Approaches .... ........... ... ...•. ..... ••...• ... .....
14.8.'1 Prefix Range Search. . . . . .. . . . . . ...... . . .. ... ........ . .
Hardware A.lgorithl.ns ........ , ........... , ....... ...•.... .... , . ..... .
14.9.1 RAM-Based Lookup. . ..... ......•. ..... ••.. ••...
462
464
465
466
468
468
469
471
471
472
472
473
475
480
484
48 5
485
48 7
487
490
490
14.9.2 Ternary CAM-Based Lookup . .. ........ ... . .. .. . .. 491
14.9.3 Multibit Tries in Hardware.. . . . . . . . . . . ...... . . . ..... 494
14.9.4 Field-Programmable G ate Array (FPGA) ....•. . . • . . . .. . . . 495
1 4.10 Comparing Different Approaches. . . . . . . . . . . . . . . . .•. . . • . . . . . . •. . . . . . . .. 496
1 4.11 Summary ...... ....... ...... .... ...... .... ....•. ...... ... •.... ..... 497
Further Lookup ............... ...... ...... .•. .......... ...•. ........ 497
CHAPTER 15
1 5.1
1 5.2
1 5.3
1 5.4
1 5.5
1 5.6
1 5.7
Exercises. __ ... ....... ........ __ ... . . . .... _ . . ... . ... . _ .... .... .
IP Packet Filtering and Classification .....•.•....• .•.•...............
Importance of Packet Classification .................................... .
Packet Classification Problem . . ........ .... ......•. ..... ....•. ....... .
15.2.1 Expressing Rules ....... ..... .
] 5.2.2 Performance Metrics . . .............. . ...... ........... .. . .
Packet Classification Algorithms
Nai've Solutions . .. . .... . ...... __ .......... ___ .
Two-Dimensional Solutions, .. , ...... , .. , ... ... .......... ..... .... , .. .
15.5.1 Hierarchical Tries: Trading Time for Space ..................... .
15.5.2 Set Pruning Tries: Trading Space for Time ... , . , . , , , , .. .. , , . , , , , , .
1 5.5.3 Grid-of-Tries: Best of Both Worlds ...................... .
Approaches for d Dimensions ................................ .
15.6.1 Geometric View of Classification: Thinking DifFerently
15.6.2 Characteristics of Real Life Classifiers - Thinking Practically
Extending Two-Dimensional Solutions. . . . . . . . . . . . ...... .
15.7.1 Naive Extensions ......................... . . . ... ...... . .
498
500
501
503
504
50 5
505
506
507
507
510
511
5 14
5 14
517
5 18
518