Network routing : algorithms, protocols, and architectures / Deepankar Medhi, Karthikeyan Ramasamy.

Incluye CD-ROM, N°I RE0470

CONTENIDO
Part 1: Network Routing: Basics and Foundations 1
1 Networking and Network Routing: An Introduction 2
1.1 Addressing and Internet Service: An Overview 4
1.2 Network Routing: An Overview 5
1.3 IP Addressing 7
1.3.1 Classful Addressing Scheme 8
1.3.2 Subnetting / Netmask 9
1.3.3 Classless Interdomain Routing 10
1.4 On Architectures 11
1.5 Service Architecture 12
1.6 Protocol Stack Architecture 13
1.6.1 OSI Reference Model 13
1.6.2 IP Protocol Stack Architecture 14
1.7 Router Architecture 19
1.8 Network Topology Architecture 20
1.9 Network Management Architecture 21
1.10 Public Switched Telephone Network 21
1.11 Communication Technologies 22
1.12 Standards Committees 24
1.12.1 International Telecommunication Union 24
1.12.2 Internet Engineering Task Force 25
1.12.3 MFA Forum 25
1.13 Last Two Bits 25
1.13.1 Type-Length-Value 25
1.13.2 Network Protocol Analyzer 26
2 Routing Algorithms: Shortest Path and Widest Path 30
2.1 Background 31
2.2 Bellman-Ford Algorithm and the Distance Vector Approach 33
2.2.1 Centralized View: Bellman-Ford Algorithm 33
2.2.2 Distributed View: A Distance Vedor Approach 36
2.3 Dijkstra's Algorithm 38
2.3.1 Centralized Approach 38
2.3.2 Distributed Approach 40
2.4 Comparison of the Bellman-Ford Algorithm and Dijkstra's Algorithm 42
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 Bellman-Ford-Based Approach 49
2.8 k-Shortest Paths Algorithm 49
3 Routing ProtocoIs: Framework and Principles 56
3.1 Routing Protocol, Routing Algorithm, and Routing Table 57
3.2 Routing Information Representation and Protocol Messages 59
3.3 Distance Vedor Routing Protocol 60
3.3.1 Conceptual Framework and Illustration 60
3.3.2 Why Timers Matter 66
3.3.3 Solutions 70
3.3.4 Can We Avoid Loops? 74
3.3.5 Distance Vedor Protocol Based on Diffusing Computation with Coordinated Update 74
3.4 Link State Routing Protocol 82
3.4.1 Link State Protocol: In-Band Hop-by-Hop Disseminations 83
3.4.2 Link State Protocol: In-Band Based on End-to-End Session 91
3.4.3 Route Computation 92
3.5 Path Vector Routing Protocol 93
3.5.1 Basic Principle 93
3.5.2 Path Vector with Path Caching 97
3.6 Link Cost 102
3.6.1 ARPANET Routing Metrics 102
3.6.2 Other Metrics 103
4 Network Flow Modeling 108
4.1 Terminologies 109
4.2 Single-Commodity Network Flow 110
4.2.1 A Three-Node Illustration 110
4.2.2 Formal Description and Minimum Cost Routing Objective 111
4.2.3 Variation in Objective: Load Balancing 114
4.2.4 Variation in Objective: Average Delay 116
4.2.5 Summary and Applicability 117
4.3 Multicommodity Network Flow: Three-Node Example 118
4.3.1 Minimum Cost Routing Case 118
4.3.2 Load Balancing 123
4.3.3 Average Delay 125
4.4 Multicommodity Network Flow Problem: General Formulation 128
4.4.1 Background on Notation 129
4.4.2 Link-Path Formulation 130
4.4.3 Node-Link Formulation 135
4.5 Multicommodity Network Flow Problem: Non-Splittable Flow 137
Part II: Routing in IP Networks 141
5 IP Routing and Distance Vector Protocol Family 142
5.1 Routers, Networks, and Routing Information: Some Basics 143
5.1.1 Routing Table 143
5.1.2 Communication of Routing Information 146
5.2 Static Routes 146
5.3 Routing Information Protocol, Version 1 (RIPv1) 147
5.3.1 Communication and Message Format 147
5.3.2 General Operation 149
5.3.3 Is RIPv1 Good to Use? 150
5.4 Routing Information Protocol, Version 2 (RIPv2) 150
5.5 Interior Gateway Routing Protocol (IGRP) 153
5.5.1 Packet Format 153
5.5.2 Computing Composite Metric 154
5.6 Enhanced Interior Gateway Routing Protocol (EIGRP) 157
5.6.1 Packet Format 157
5.7 Route Redistribution 160
6 OSPF and Integrated IS-IS 166
6.1 From Protocol Family to an Instance of a Protocol 167
6.2 OSPF: Protocol Features 168
6.2.1 Network Hierarchy 168
6.2.2 Router Classification 168
6.2.3 Network Types 169
6.2.4 Flooding 170
6.2.5 Link State Advertisement Types 171
6.2.6 Subprotocols 171
6.2.7 Routing Computation and Equal-Cost Multipath 172
6.2.8 Additional Features 176
6.3 OSPF Packet Format 177
6.4 Examples of Router LSAs and Network LSAs 183
6.5 Integrated IS-IS 185
6.5.1 Key Features 186
6.6 Similarities and Differences Between IS-IS and OSPF 189
7 IP Traffic Engineering 194
7.1 Traffic, Stochasticity, Delay, and Utilization 195
7.1.1 What Is IP Network Traffic? 195
7.1.2 Traffic and Performance Measures 195
7.1.3 Characterizing Traffic 196
7.1.4 Average Delay in a Single Link System 197
7.1.5 Nonstationarity of Traffic 199
7.2 Applications´ View 200
7.2.1 TCP Throughput and Possible Bottleneeks 200
7.2.2 Bandwidth-Delay Product 201
7.2.3 Router Buffer Size 202
7.3 Traffic Engineering: An Architectural Framework 203
7.4 Traffic Engineering: A Four-Node Illustration 204
7.4.1 Network Flow Optimization 204
7.4.2 Shortest Path Routing and Network Flow 206
7.5 Link Weight Determination Problem: Preliminary Discussion 211
7.6 Duality of the MCNF Problem 213
7.6.1 Illustration of Duality Through a Three-Node Network 213
7.6.2 General Case: Minimum Cost Routing 215
7.6.3 Minimization of Maximum Link Utilization 219
7.6.4 A Composite Objective Function 221
7.6.5 Minimization of Average Delay 222
7.7 Illustration of Link Weight Determination Through Duality 226
7.7.1 Case Study: I 226
7.7.2 Case Study: II 231
7.8 Link Weight Determination: Large Networks 232
8 BGP238
8.1 BGP: A Brief Overview 239
8.2 BGP: Basic Terrninology 242
8.3 BGP Operations 243
8.3.1 Message Operations 243
8.3.2 BGP Timers 244
8.4 BGP Configuration Initialization 245
8.5 Two Faces of BGP: External BGP and Internal BGP 247
8.6 Path Attributes 250
8.7 BGP Decision Process 254
8.7.1 BGP Path Selection Process 254
8.7.2 Route Aggregation and Dissemination 256
8.7.3 Recap 257
8.8 Internal BGP Scalability 257
8.8.1 Route Reflection Approach 258
8.8.2 Confederation Approach 261
8.9 Route Flap Dampening 262
8.10 BGP Additional Features 265
8.10.1 Communities 265
8.10.2 Multiprotocol Extension 265
8.11 Finite State Machine of a BGP Connection 266
8.12 Protocol Message Format 270
8.12.1 Common Header 270
8.12.2 Message Type: OPEN 270
8.12.3 Message Type: UPDATE 272
8.12.4 Message Type: NOTIFICATION 274
8.12.5 Message Type: KEEPALIVE 274
8.12.6 Message Type: ROUTE-REFRESH 274
8.12.7 Path Attribute in UPDATE message 276
9 Internet Routing Architectures 280
9.1 Internet Routing Evolution 281
9.2 Addressing and Routing: Illustrations 283
9.2.1 Routing Packet: Scenario A 285
9.2.2 Routing Packet: Scenario B 286
9.2.3 Routing Packet: Scenario C 288
9.3 Current Architectural View of the Internet 290
9.3.1 Customers and Providers, Peering and Tiering, and Exchange Points 291
9.3.2 A Representative Architecture 294
9.3.3 Customer Traffic Routing: A Geographic Perspective 297
9.3.4 Size and Growth 298
9.4 Allocation of IP Prefixes and AS Number 301
9.5 Policy-Based Routing 304
9.5.1 BGP Wedgies 306
9.6 Point of Presence 307
9.7 Traffic Engineering Implications 309
9.8 Internet Routing Instability 311
Part III: Routing in the PSTN 315
10 Hierarchical and Dynamic Call Routing in the Telephone Network 316
10.1 Hierarchical Routing 317
10.1.1 Basic Idea 317
10.1.2 A Simple Illustration 318
10.1.3 Overall Hierarchical Routing Architecture 320
10.1.4 Telephone Service Providers and Telephone Network Architecture 321
10.2 The Road to Dynamic Routing 322
10.2.1 Limitation of Hierarchical Routing 322
10.2.2 Historical Perspective 323
10.2.3 Call Control and Crankback 325
10.2.4 Trunk Reservation 326
10.2.5 Where Does Dynamic Routing Fit with Hierarchical Routing? 326
10.2.6 Mixing of OCC and PCC 327
10.2.7 Summary 327
10.3 Dynamic Nonhierarchical Routing 328
10.4 Dynamically Controlled Routing 330
10.5 Dynamic Alternate Routing 333
10.6 Real-Time Network Routing 334
10.7 Classification of Dynamic Call Routing Schemes 336
10.8 Maximum Allowable Residual Capacity Routing 337
10.9 Dynamic Routing and Its Relation to Other Routing 339
10.9.1 Dynamic Routing and Link State Protocol 339
10.9.2 Path Selection in Dynamic Routing in Telephone Networks and IP Routing 339
10.9.3 Relation to Constraint-Based Routing 340
10.10 Recap 340
11 Traffic Engineering in the Voice Telephone Network 344
11.1 Why Traffic Engineering? 345
11.2 Traffic Load and Blocking 346
11.2.1 Computing Erlang-B Loss Formula 349
11.3 Grade-of-Service and Trunk Occupancy 350
11.4 Centi-Call Seconds and Determining Offered Load 352
11.5 Economic CCS Method 354
11.6 Network Controls for Traffic Engineering 356
11.6.1 Guidelines on Detection of Congestion 357
11.6.2 Examples of Controls 357
11.6.3 Communication of Congestion Control Information 361
11.6.4 Congestion Manifestation 361
11.7 State-Dependent Call Routing 362
11.8 Analysis of Dynamic Routing 363
11.8.1 Three-Node Network 364
11.8.2 N-No de Symmetric Network 366
11.8.3 N-No de Syrnmetric Network with Trunk Reservation 367
11.8.4 Illustration Without and with Trunk Reservation 369
12 SS7: Signaling Network for Telephony 374
12.1 Why SS7? 375
12.2 SS7 Network Topology 375
12.2.1 Node Types 376
12.2.2 SS7 Links 376
12.3 Routing in the SS7 Network 378
12.4 Point Codes: Addressing in SS7 380
12.4.1 North American Point Code 380
12.4.2 ITU Point Code 381
12.5 Point Code Usage 382
12.5.1 Address Assignment 382
12.5.2 Relationship Between a Telephone Switch and an SSP 382
12.5.3 Interworking of SS7 Networks with Different Addressing Schemes 383
12.6 SS7 Protocol Stack 384
12.6.1 Lower-Layer Protocols: MTP1, MTP2, and MTP3 384
12.6.2 Upper-Layer Protocols 388
12.7 SS7 Network Management 388
12.8 ISUP and Call Processing 389
12.8.1 Called/Calling Party Number Format 395
12.9 ISUP Messages and Trunk Management 396
12.10 ISUP Messages and Dynamic Call Routing 396
12.10.1 Functionalities 397
12.10.2 Illustration 398
12.11 Transaction Services 400
12.11.1 SCCP: Signaling Connection Control Part 400
12.11.2 TCAP: Transaction Capabilities Application Part 401
12.12 SS7 Link Traffic Engineering 402
12.12.1 SS7 Network Performance Requirements 403
13 Public Switched Telephone Network: Architecture and Routing 406
13.1 Global Telephone Addressing 407
13.1.1 National Numbering Plan 409
13.1.2 Dialing Plan 412
13.2 Setting Up a Basic Telephone can and Its Steps 415
13.3 Digit Analysis versus Translation 417
13.4 Routing Decision for a Dialed call 417
13.5 Call Routing: Single National Provider Environment 417
13.5.1 Handling Dialed Numbers 418
13.5.2 Illustration of can Routing 419
13.5.3 Some Observations 423
13.6 Call Routing: Multiple Long-Distance Provider Case 424
13.6.1 Illustration of can Routing 427
13.6.2 Impact on Routing 430
13.7 Multiple-Provider Environment: Multiple Local Exchange Carriers 432
13.8 Routing Decision at an Intermediate TDM Switch 433
13.9 Number Portability 434
13.9.1 Introduction 434
13.9.2 Portability Classification 435
13.10 Nongeographic or Toll-Free Number Portability 436
13.10.1 800-Number Management Architecture 437
13.10.2 Message and can Routing 438
13.11 Fixed/Mobile Number Portability 439
13.11.1 Portability Architecture 439
13.11.2 Routing Schemes 442
13.11.3 Comparison of Routing Schemes 446
13.11.4 Impact on IAM Message 446
13.11.5 Number Portability Implementation 448
13.11.6 Routing in the Presence of Transit Network 448
13.12 Multiple-Provider Environment with Local Number Portability 451
Part IV: Router Architectures 457
14 Router Architectures 458
14.1 Functions of a Router 459
14.1.1 Basic Forwarding Functions 460
14.1.2 Complex Forwarding Functions 460
14.1.3 Routing Process Functions 461
14.1.4 Routing Table versus Forwarding Table 462
14.1.5 Performance of Routers 463
14.2 Types of Routers 463
14.3 Elements of a Router 465
14.4 Packet Flow 468
14.4.1 Ingress Packet Processing 468
14.4.2 Egress Packet Processing 469
14.5 Packet Processing: Fast Path versus Slow Path 470
14.5.1 Fast Path Functions 471
14.5.2 Slow Path Operations 474
14.6 Router Architectures 475
14.6.1 Shared CPU Architectures 476
14.6.2 Shared Forwarding Engine Architectures 479
14.6.3 Shared Nothing Architectures 481
14.6.4 Clustered Architectures 484
15 IP Address Lookup Algorithms 488
15.1 Impact of Addressing on Lookup 489
15.1.1 Address Aggregation 490
15.2 Longest Prefix Matching 492
15.2.1 Trends, Observations, and Requirements 493
15.3 Naive Algorithms 495
15.4 Binary Tries 495
15.4.1 Search and Update Operations 496
15.4.2 Path Compression 498
15.5 Multibit Tries 500
15.5.1 Prefix Transformations 500
15.5.2 Fixed Stride Multibit Trie 502
15.5.3 Search Algorithm 503
15.5.4 Update Algorithm 504
15.5.5 Implementation 505
15.5.6 Choice of Strides 506
15.5.7 Variable Stride Multibit Trie 506
15.6 Compressing Multibit Tries 507
15.6.1 Level Compressed Tries 507
15.6.2 Lulea Compressed Tries 510
15.6.3 Tree Bitmap 514
15.7 Search by Length Algorithms 519
15.7.1 Linear Search on Prefix Lengths 520
15.7.2 Binary Search on Prefix Lengths 520
15.8 Search by Value Approaches 522
15.8.1 Prefix Range Search 522
15.9 Hardware Algorithms 525
15.9.1 RAM-Based Lookup 525
15.9.2 Ternary CAM-Based Lookup 526
15.9.3 Multibit Tries in Hardware 528
15.10 Comparing Different Approaches 530
16 IP Packet Filtering and Classification 534
16.1 Importance of Packet Classification 535
16.2 Packet Classification Problem 537
16.2.1 Expressing Rules 538
16.2.2 Performance Metrics 538
16.3 Packet Classification Algorithms 540
16.4 Naive Solutions 540
16.5 Two-Dimensional Solutions 541
16.5.1 Hierarchical Tries: Trading Time for Space 541
16.5.2 Set Pruning Tries: Trading Space for Time 544
16.5.3 Grid-of-Tries: Optimizing Both Space and Time 545
16.6 Approaches for d Dimensions 548
16.6.1 Geometric View of Classification: Thinking Differently 549
16.6.2 Characteristics of Real-Life Classifiers: Thinking Practically 551
16.7 Extending Two-Dimensional Solutions 552
16.7.1 Naive Extensions 552
16.7.2 Native Extensions 553
16.8 Divide and Conquer Approaches 555
16.8.1 Lucent Bit Vector 556
16.8.2 Aggregated Bit Vector 558
16.8.3 Cross-Producting 560
16.8.4 Recursive Flow Classification 562
16.9 Tuple Space Approaches 568
16.9.1 Tuple Space Search 569
16.9.2 Tuple Space Pruning 570
16.10 Decision Tree Approaches 571
16.10.1 Hierarchical Intelligent Cuttings 572
16.10.2 HyperCuts 575
16.11 Hardware-Based Solutions 576
16.11.1 Ternary Content Addressable Memory (TCAM) 576
16.12 Lessons Learned 578
Part V: Toward Next Generation Routing 582
17 Quality of Service Routing 584
17.1 Background 585
17.2 QoS Attributes 589
17.3 Adapting Shortest Path and Widest Path Routing: A Basic Framework 590
17.3.1 Single Attribute 590
17.3.2 Multiple Attributes 591
17.3.3 Additional Consideration 592
17.4 Update Frequency, Information Inaccuracy, and Impact on Routing 593
17.5 Lessons from Dynamic Call Routing in the Telephone Network 595
17.6 Heterogeneous Service, Single-Link Case 596
17.7 A General Framework for Source-Based QoS Routing with Path Caching 599
17.7.1 Routing Computation Framework 600
17.7.2 Routing Computation 601
17.7.3 Routing Schemes 602
17.7.4 Results 603
17.8 Routing Protocols for QoS Routing 608
17.8.1 QOSPF: Extension to OSPF for QoS Routing 608
17.8.2 ATM PNNI 609
18 MPLS and GMPLS 612
18.1 Background 613
18.2 Traffic Engineering Extension to Routing Protocols 614
18.3 Multiprotocol Label Switching 614
18.3.1 Labeled Packets and LSP 616
18.3.2 Label Distribution 619
18.3.3 RSVP-TE for MPLS 619
18.3.4 Traffic Engineering Extensions to OSPF and IS-IS 625
18.4 Generalized MPLS 626
18.4.1 GMPLS Labels 627
18.4.2 Label Stacking and Hierarchical LSPs: MPLS/GMPLS 628
18.4.3 RSVP-TE for GMPLS 629
18.4.4 Routing Protocols in GMPLS 630
18.4.5 Control and Data Path Separation and Link Management Protocol 632
18.5 MPLS Virtual Private Networks 634
18.5.1 BGP/MPLS IP VPN 635
18.5.2 Layer 2 VPN 639
19 Routing and Traffic Engineering with MPLS 642
19.1 Traffic Engineering of IP/MPLS Networks 643
19.1.1 A Brisk Walk Back in History 643
19.1.2 MPLS-Based Approach for Traffic Engineering 644
19.2 VPN Traffic Engineering 647
19.2.1 Problem Illustration: Layer 3 VPN 647
19.2.2 LSP Path Determination: Constrained Shortest Path Approach 650
19.2.3 LSP Path Determination: Network Flow Modeling Approach 652
19.2.4 Layer 2 VPN Traffic Engineering 656
19.2.5 Observations and General Modeling Framework 657
19.3 Routing/Traffic Engineering for Voice Over MPLS 657
20 VoIP Routing: Interoperability Through IP and PSTN 662
20.1 Background 663
20.2 PSTN Call Routing Using the Internet 664
20.2.1 Conceptual Requirement 664
20.2.2 VoIP Adapter Functionality 666
20.2.3 Addressing and Routing 666
20.2.4 Service Observations 670
20.2.5 Traffic Engineering 671
20.2.6 VoIP Adapter: An Alternative Scenario 673
20.3 PSTN Call Routing: Managed IP Approach 673
20.4 IP-PSTN Interworking for VoIP 675
20.4.1 Gateway Function 675
20.4.2 SIP Addressing Basics 676
20.4.3 SIP Phone to POTS Phone 677
20.4.4 POTS Phone to SIP Phone 680
20.4.5 PSTN-IP-PSTN 680
20.4.6 Traffic Engineering 683
20.4.7 Relation to Using MPLS 684
20.5 IP Multimedia Subsystem 684
20.5.1 IMS Architecture 685
20.5.2 Call Routing Scenarios 686
20.6 Multiple Heterogeneous Providers Environment 688
20.6.1 Via Routing 688
20.6.2 Carrier Selection Alternative 690
20.7 All-IP Environment of VoIP Services 690
20.8 Addressing Revisited 691
Appendix A: Notations, Conventions, and Symbols 696
A.1 On Notations and Conventions 697
A.2 Symbols 699
Appendix B: Miscellaneous Topics 700
B.1 Functions: Logarithm and Modulo 701
B.2 Fixed-Point Equation 701
B.3 Computational Complexity 702
B.4 Equivalence Classes 704
B.5 Using CPLEX 704
B.6 Exponential Weighted Moving Average 706
B.7 Nonlinear Regression Fit 707
B.8 Computing Probability of Path Blocking or Loss 708
8.9 Four Factors in Packet Delay 709
B.10 Exponential Distribution and Poisson Process 710
B.11 Self-Similarity and Heavy-Tailed Distributions 712
B.12 Markov Chain and Birth-and-Death Process 713
B.12.1 Birth-and-Death Process 714
B.12.2 M / M /1 System 715
B.12.3 Trunk Reservation Model 716
B.13 Average Network Delay 717
B.14 Packet Format: IPv4, IPv6, TCP, and UDP 717
Solutions to Selected Exercises 720
Bibliography 724
Index 768