Chapter
1.7.2 IP Protocol Stack 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.13.1 Internet Engineering Task Force
1.13.2 International Telecommunication Union
1.14.1 Type-Length-Value (TLV)
1.14.2 Network Protocol Analyzer
2 Routing Algorithms: Shortest Path, Widest Path, and Spanning Tree
2.2 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
2.3.1 Centralized Approach
2.3.2 Distributed Approach
2.4 Comparison of the Bellman-Ford Algorithm and Dijkstra's Algorithm
2.5 Shortest Path Computation with Candidate Path Caching
2.6 Widest Path Computation with Candidate Path Caching
2.7 Widest Path Algorithm
2.7.1 Dijkstra-Based Approach
2.7.2 Distance Vector-Based Approach
2.8 Shortest Widest Path and Widest Shortest Path
2.9 Tree, Spanning Tree, and Steiner Tree Algorithms
2.9.1 Spanning Tree: Breadth First Search and Depth First Search
2.9.2 Minimum Spanning Tree
2.10 k-Shortest Paths Algorithm
3 Routing Protocols: Framework and Principles
3.1 Routing Protocol, Routing Algorithm, and Routing Table
3.2 Routing Information Representation and Protocol Messages
3.3 Distance Vector Routing Protocol
3.3.1 Conceptual Framework and Illustration
3.3.4 Can We Avoid Loops?
3.3.5 Distance Vector Protocol based on Diffusing Computation with Coordinated Updates (DUAL)
3.3.6 Babel Routing Protocol
3.4 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.5 Path Vector Routing Protocol
3.5.2 Path Vector with Path Caching
3.6.1 ARPANET Routing Metrics
3.7 Threats to Routing Protocols
4.2 Single-Commodity Network Flow
4.2.1 A Three-Node Illustration
4.2.2 Formal Description and Minimum Cost Routing Objective
4.2.3 Variation in Objective: Load Balancing
4.2.4 Variation in Objective: Average Delay
4.2.5 Summary and Applicability
4.3 Multicommodity Network Flow: Three-Node Example
4.3.1 Minimum Cost Routing: Illustration
4.3.2 Load Balancing: Illustration
4.3.3 Minimum Average Delay: Illustration
4.4 Multicommodity Network Flow: General Link-Path Formulation
4.4.1 Background on Notation
4.4.2 Minimum Cost Routing: General Link-Path Formulation
4.4.3 Load Balancing: Link-Path Formulation
4.4.4 Minimum Average Delay: Link-Path Formulation
4.4.5 How Many Nonzero Flows at Optimality?
4.5 Multicommodity Network Flow Problem: Non-Splittable Flow
4.6 Node-Link Formulation
4.6.1 Minimum Cost Single-Commodity Network Flow Problem
4.6.2 Minimum Cost Multicommodity Network Flow Problem
4.6.3 Load Balancing Multicommodity Network Flow Problem
4.6.4 Shortest Path Routing
4.7 Generating Traffic Matrix
5 IP Routing and Distance Vector Protocol Family
5.1 Routers, Networks, and Routing Information: Some Basics
5.1.2 Communication of Routing Information
5.3 Routing Information Protocol, Version 1 (RIPv1)
5.3.1 Communication and Message Format
5.3.3 Is RIPv1 Good to Use?
5.4 Routing Information Protocol, Version 2 (RIPv2)
5.5 Interior Gateway Routing Protocol (IGRP)
5.5.2 Computing Composite Metric
5.6 Enhanced Interior Gateway Routing Protocol (EIGRP)
6 OSPF and Integrated IS-IS
6.1 From a Protocol Family to an Instance of a Protocol
6.2 OSPF: Protocol Features
6.2.2 Router Classification
6.2.5 Link State Advertisement (LSA) Types
6.2.7 Routing Computation and Equal-Cost MultiPath
6.2.8 Additional Features
6.3 Multitopology Routing in OSPF
6.5 Examples of Router LSA and Network LSA
6.7 Similarities and Differences Between IS-IS and OSPF
6.8 OSPFv3 and IS-IS for IPv6
6.9 Additional Extensions to OSPF and IS-IS
7.1 Traffic, Stochasticity, Delay, and Utilization
7.1.1 What Is IP Network Traffic?
7.1.2 Traffic and Performance Measures
7.1.3 Characterizing Traffic
7.1.4 Average Delay in a Single Link System
7.1.5 Nonstationarity of Traffic
7.2.1 TCP Throughput and Possible Bottlenecks
7.2.2 Bandwidth-Delay Product
7.3 Traffic Engineering: An Architectural Framework
7.4 Traffic Engineering: A Four-Node Illustration
7.4.1 Network Flow Optimization
7.4.2 Shortest Path Routing and Network Flow
7.5 IGP Metric (Link Weight) Determination Problem for the Load Balancing Objective: Preliminary Discussion
7.6 Determining IGP Link Weights via duality of MCNF Problems
7.6.1 Illustration of Duality Through a Three-Node Network for Minimum Cost Routing
7.6.2 Minimum Cost Routing, Duality, and Link Weights
7.6.3 Illustration 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 Minimization of Average Delay, duality, and Link Weights
7.7 Illustration of Link Weight Determination through Duality
7.8 Link Weight Determination: Large Networks
7.9 IP Traffic Engineering of PoP-to-DataCenter Networks
8.1 Multicast IP Addressing
8.2 Internet Group Management Protocol (IGMP)
8.3 Multicast Listener Discovery Protocol (MLD)
8.4 Reverse Path Forwarding (RPF)
8.5 Distance Vector Multicast Routing Protocol (DVMRP)
8.8 Protocol Independent Multicast (PIM)
8.8.3 Selecting and Advertising Rendezvous Point for PIM Sparse Mode
8.8.4 Source Specific Multicast
8.9 Inter-Domain Multicast Routing
8.9.1 Border Gateway Multicast Protocol (BGMP)
8.9.2 Multiprotocol Extension of BGP and a Composite Approach
8.10 Internet Protocol Television (IPTV) Multicasting
9.1 BGP: A Brief Overview
9.2 BGP: Basic Terminology
9.4 BGP Configuration Initialization
9.5 Two Faces of BGP: External BGP (eBGP) and Internal BGP (iBGP)
9.7.1 BGP Path Selection Process
9.7.2 Route Aggregation and Dissemination
9.8 Internal BGP Scalability
9.8.1 Route Reflection Approach
9.8.2 Confederation Approach
9.10 BGP Additional Features and Extensions
9.10.2 BGP 4-byte Autonomous Systems Number Space
9.10.3 BGP Multiprotocol Extension (MP-BGP)
9.12.1 Secure BGP (S-BGP)
9.12.2 Secure Origin BGP (soBGP)
9.12.3 Resource Public Key Infrastructure (RPKI) Architecture
9.13 Finite State Machine of A BGP Connection
9.14 BGP4 Protocol Message Format
9.14.2 Message Type: OPEN
9.14.3 Message Type: UPDATE
9.14.4 Message Type: NOTIFICATION
9.14.5 Message Type: KEEPALIVE
9.14.6 Message Type: ROUTE-REFRESH
9.14.7 Path Attribute in UPDATE message
10 Routing in the Global Internet
10.1 Internet Routing Evolution
10.2 Addressing and Routing: Illustrations
10.2.1 Scenario A: Routing a Packet (Same Subnet)
10.2.2 Scenario B: Routing a Packet (Intra-Domain)
10.2.3 Scenario C: Routing a Packet (Inter-Domain)
10.2.4 Scenario D: Routing a Packet (End-to-End Routing for Fixed/Mobile Devices)
10.3 Allocation of IP Prefixes and AS Numbers
10.4 Current Architectural View of the Internet
10.4.1 Customers and Providers, Peers and Tiers, and Internet Exchange Points
10.4.2 An Illustration on Customer-Provider and Peers
10.4.3 A Representative Internet Connectivity
10.4.4 Customer Traffic Routing: A Geographic Perspective
10.5 Traffic Engineering Implications
10.6 Point of Presence (PoP) for Large ISPs
10.7 Policy-Based Routing
10.9 Detecting and Preventing IP Prefix Hijacking
10.10 Internet Routing Instability
10.11 Size and Growth of the Internet Routing Architecture
10.12 Addressing the Growth: Locator/ID Separation Protocol (LISP)
11 Routing and Traffic Engineering in Software Defined Networks
11.1 Software Defined Networks: An Overview
11.4 Traffic Engineering for Aggregated Flow Routing
11.4.1 Aggregation at Origin-Destination Level
11.4.2 Traffic Engineering for Multiple Services
11.4.3 Traffic Engineering in the Presence of Flow Table Limits
11.4.4 Remark: Using Optimization Models in Practice
11.5 Flow Management Approaches
12 Routing and Traffic Engineering in Data Center Networks
12.1 Cloud Services and Data Center Applications
12.2 Data Center Network: A Simple Illustration
12.3 Data Center Network: Routing/Forwarding Requirements
12.4 Fat-Tree Data Center Topology
12.5 PortLand Approach for the Fat-Tree Topology
12.6 Multipath Routing and Traffic Engineering for Fat-Tree Topology
12.8 Multipath Routing and Traffic Engineering for BCube Architecture
12.9 Border Gateway Protocol (BGP) in Ultra Large Data Center Networks
12.9.1 5-stage Clos Topology and eBGP for Routing
12.10 Software-Defined Networking for Data Center Networks
12.11 Convergence Time and Performance
Part 3 Router Architecture & Design
13.1 Functions of a Router
13.1.1 Basic Forwarding Functions
13.1.2 Complex Forwarding Functions
13.1.3 Routing Process Functions
13.1.4 Routing Table Versus Forwarding Table
13.1.5 Performance Indicator of Routers
13.3 Elements of a Router
13.4.1 Ingress Packet Processing
13.4.2 Egress Packet Processing
13.5 Packet Processing: Fast Path Versus Slow Path
13.5.1 Fast Path Functions
13.5.2 Slow Path Operations
13.6 Router Architectures
13.6.1 Shared CPU Architectures
13.6.2 Shared Forwarding Engine Architecture
13.6.3 Shared Nothing Architectures
13.6.4 Clustered Architectures
14 IP Address Lookup Algorithms
14.1 Impact of Addressing on Lookup
14.1.1 Address Aggregation
14.2 Longest Prefix Matching
14.2.1 Trends, Observations, and Requirements
14.4.1 Search and Update Operations
14.5.1 Prefix Transformations
14.5.2 Fixed Stride Multibit Trie
14.5.7 Variable Stride Multibit Trie
14.6 Compressing Multibit Tries
14.6.1 Level Compressed Tries
14.6.2 Lulea Compressed Tries
14.7 Search by Length Algorithms
14.7.1 Linear Search on Prefix Lengths
14.7.2 Binary Search on Prefix Lengths
14.8 Search by Value Approaches
14.8.1 Prefix Range Search
14.9.2 Ternary CAM-Based Lookup
14.9.3 Multibit Tries in Hardware
14.9.4 Field-Programmable Gate Array (FPGA)
14.10 Comparing Different Approaches
15 IP Packet Filtering and Classification
15.1 Importance of Packet Classification
15.2 Packet Classification Problem
15.2.2 Performance Metrics
15.3 Packet Classification Algorithms
15.5 Two-Dimensional Solutions
15.5.1 Hierarchical Tries: Trading Time for Space
15.5.2 Set Pruning Tries: Trading Space for Time
15.5.3 Grid-of-Tries: Best of Both Worlds
15.6 Approaches for d Dimensions
15.6.1 Geometric View of Classification: Thinking Differently
15.6.2 Characteristics of Real Life Classifiers - Thinking Practically
15.7 Extending Two-Dimensional Solutions
15.8 Divide and Conquer Approaches
15.8.2 Aggregated Bit Vector (ABV)
15.8.4 Recursive Flow Classification
15.9 Tuple Space Approaches
15.9.1 Tuple Space Search
15.9.2 Tuple Space Pruning
15.10 Decision Tree Approaches
15.10.1 Hierarchical Intelligent Cuttings
15.11 Hardware-Based Solutions
15.11.1 Ternary Content Addressable Memory (TCAM)
16.1 Generic Switch Architecture
16.2 Requirements and Metrics
16.5.1 Scaling Memory Bandwidth
16.6.1 Take-a-Ticket Scheduler
16.6.2 Factors That Limit Performance
16.7 Head-of-Line (HOL) Blocking
16.9 Virtual Output Queueing
16.9.1 Maximum Bipartite Matching
16.9.2 Parallel Iterative Matching
16.9.4 Priorities and Multicast in iSLIP
16.10 Input and Output Blocking
16.11 Scaling Switches to a Large Number of Ports
16.12.1 Complexity of Scheduling Algorithms
16.13.1 Packaging Using Short Wires
16.14 Scaling Switches for High-Speed Links
16.14.3 Distributed Scheduling
17 Packet Queueing and Scheduling
17.1.1 First-In, First-Out Queueing
17.1.3 Round-Robin and Fair Queueing
17.1.4 Weighted Round-Robin (WRR) and Weighted Fair Queueing (WFQ)
17.1.5 Deficit Round-Robin Queueing
17.1.6 Modified Deficit Round-Robin Queueing
17.2 TCP Congestion Control
17.2.2 Additive Increase, Multiplicative Decrease
17.2.3 Fast Retransmit and Fast Recovery
17.3 Implicit Feedback Schemes
17.3.2 Proactive versus Reactive Dropping
17.4 Random Early Detection (RED)
17.4.1 Computing Average Length of Queue
17.4.2 Computing Drop Probability
17.4.3 Setting Qmin and Qmax
17.5.1 Weighted Random Early Detection (WRED)
17.5.2 Adaptive Random Early Detection
17.6 Explicit Feedback Schemes
17.6.2 Explicit Congestion Notification
17.7 New Class of Algorithms
17.8 Analyzing System Behavior
18.1 Service Level Agreements
18.2 Differentiated Services
18.3 Traffic Conditioning Mechanisms
18.5.1 Comparing Traffic Policing and Shaping
18.6.2 Single-Rate Tricolor Marking
18.6.3 Two-Rate Tricolor Marking
Part 4 Routing in Reservation-Oriented Networks
19 Circuit-Switching: Hierarchical and Dynamic Call Routing
19.2 Hierarchical Call Routing
19.2.2 A Simple Illustration
19.2.3 Overall Hierarchical Routing Architecture
19.2.4 Telephone Service Providers and Telephone Network Architecture
19.3 The Road to Dynamic Routing
19.3.1 Limitation of Hierarchical Routing
19.3.2 Historical Perspective
19.3.3 Call Control and Crankback
19.3.4 Trunk Reservation (State Protection)
19.3.5 Where Does Dynamic Routing Fit with Hierarchical Routing
19.3.6 Mixing of OCC and PCC
19.4 Dynamic Non-Hierarchical Routing (DNHR)
19.5 Dynamically Controlled Routing (DCR)
19.6 Dynamic Alternate Routing (DAR)
19.7 Real-Time Network Routing (RTNR)
19.8 Classification of Dynamic Call Routing Schemes
19.9 Maximum Allowable Residual Capacity Routing
19.10 Dynamic Routing and Its Relation to Other Routing
19.10.1 Dynamic Routing and Link State Protocol
19.10.2 Path Selection in Dynamic Routing in Telephone Networks and IP Routing
19.10.3 Relation to Constraint-Based Routing
20 Traffic Engineering for Circuit-Switched Networks
20.1 Why Traffic Engineering
20.2 Traffic Load and Blocking
20.2.1 Computing Erlang-B Loss Formula
20.3 Grade-of-Service (GoS)
20.3.2 Offered Load Scaling and Blocking
20.4 Centi-Call Seconds (CCS) and Determining Offered Load
20.5 Economic CCS (ECCS) Method
20.6 Network Controls for Traffic Engineering
20.6.1 Guidelines on Detection of Congestion
20.6.2 Examples of Controls
20.6.3 Communication of Congestion Control Information
20.6.4 Congestion Manifestation
20.7 State-Dependent Call Routing
20.8 Analysis of Dynamic Routing
20.8.1 Three-Node Network
20.8.2 N-Node Symmetric Network
20.8.3 N-Node Symmetric Network with State Protection
20.8.4 Illustration Without and With State Protection
20.9 Performance for Heterogeneous Services
21 Quality of Service Routing
21.3 Adapting Shortest Path and Widest Path Routing: A Basic Framework
21.3.2 Multiple Attributes
21.3.3 Additional Consideration
21.4 Update Frequency, Information Inaccuracy, and Impact on Routing
21.5 Lessons from Dynamic Call Routing in the Telephone Network
21.6 A General Framework for Source-Based QoS Routing with Path Caching
21.6.1 Routing Computation Framework
21.6.2 Routing Computation
21.7 Routing Protocols for QoS Routing
21.7.1 QOSPF: Extension to OSPF for QoS Routing
22 MultiProtocol Label Switching (MPLS)
22.2 Traffic Engineering Extension to Routing Protocols
22.3 Multiprotocol Label Switching (MPLS)
22.3.1 Labeled Packets and LSP
22.3.2 Label Distribution
22.3.4 Traffic Engineering Extensions to OSPF and IS-IS
22.3.5 Point-to-Multipoint LSP and Multipoint-to-Multipoint LSP
22.4 Generalized MPLS (GMPLS)
22.4.2 Label Stacking and Hierarchical LSPs: MPLS/GMPLS
22.4.4 Routing Protocols in GMPLS
22.4.5 Control and Data Path Separation, and Link Management Protocol
22.5 MPLS Virtual Private Networks
22.6 Multicast VPN with MPLS
23 Routing and Traffic Engineering using MPLS
23.1 Traffic Engineering of IP/MPLS Networks
23.1.1 A Brisk Walk Back in History
23.1.2 MPLS-Based Approach for Traffic Engineering
23.2 VPN Traffic Engineering
23.2.1 Problem Illustration: Layer 3 VPN
23.2.2 LSP Path Determination: Constrained Shortest Path Approach
23.2.3 LSP Path Determination: Network Flow Modeling Approach
23.2.4 Layer 2 VPN traffic engineering
23.2.5 Observations and General Modeling Framework
23.3 Multicast VPN Traffic Engineering
23.4 Routing/Traffic Engineering for Voice over MPLS
24 Routing in Optical Networks, Multilayer Networks, and Overlay Networks
24.1 Optical Technology: Overview
24.2 How is Optical Routing Different?
24.3 SONET/SDH and OTN Routing
24.3.1 Routing in a SONET Ring
24.3.2 Routing in SONET/SDH or OTN Transport Cross-Connect Networks
24.4 WDM Routing and Wavelength Assignment
24.4.2 Routing in WDM with Full Conversion: Transport Mode
24.4.3 No Conversion Case
24.4.4 On-Demand, Instantaneous Optical Services
24.5.1 Solution Approaches
24.6 Routing in Multilayer Networks
24.6.2 IP Over SONET: Combined Two-Layer Routing Design
24.6.3 Virtual Private Networks over Substrate Network
24.7 Overlay Networks and Overlay Routing
25.1 E.164 Addressing for GSTN
25.2 National Numbering Plan
25.3 Provider Identifier: Carrier Identification Code, Mobile Country Code, and Mobile Network Code
25.4 Signaling System: SS7 and Point Code
25.4.1 SS7 Network Topology
25.5.1 Lower Layer Protocols: MTP1, MTP2, MTP3
25.5.2 Upper Layer Protocols
25.6 SS7 ISUP and Call Processing
25.6.1 Called/Calling Party Number Format
25.7 Call Routing: Single Provider Case
25.7.1 Handling Dialed Numbers
25.7.2 Illustration of Call Routing
25.8 Call Routing With Multiple Service Providers
25.9.1 What is Number Portability About?
25.9.2 Portability Classification
25.10 Non-Geographic or Toll-Free Number Portability
25.10.1 800-Number Management Architecture
25.10.2 Message and Call Routing
25.11 Fixed/Mobile Number Portability
25.11.1 Portability Architecture
25.11.3 Comparison of Routing Schemes
25.11.4 Impact on IAM Message
25.11.5 Number Portability Implementation
25.11.6 Routing in the Presence of a Transit Network
25.12 Multiple Provider Environment With Local Number Portability
26.2 GSTN Call Routing Using Internet
26.2.1 Conceptual Requirement
26.2.2 VoIP Adapter Functionality
26.2.3 Addressing and Routing
26.2.4 Service Observations
26.2.5 Traffic Engineering
26.2.6 VoIP Adapter: An Alternative Scenario
26.3 GSTN Call Routing: Managed IP Approach
26.4 IP-GSTN Interworking for VoIP
26.4.2 SIP Addressing Basics
26.4.3 SIP Phone to POTS Phone
26.4.4 POTS Phone to SIP Phone
26.4.6 Traffic Engineering
26.5 IP Multimedia Subsystem (IMS)
26.5.2 Call Routing Scenarios
26.6 Multiple Heterogeneous Providers Environment
26.6.2 Carrier Selection Alternative
26.7 All-IP Environment for VoIP Services
26.8 Addressing Revisited
Part 5 Appendices, Bibliography, and Index
A Notations, Conventions, and Symbols
A.1 On Notations and Conventions
B.1 Binary and Hexadecimal Numbers
B.2 Functions: Logarithm and Modulo
B.4 Computational Complexity
B.6 Solving Linear Programming Problems
B.7 Exponential Weighted Moving Average (EWMA)
B.8 Linear Regression Fit
B.9 Non-Linear Regression Fit
B.10 Computing Probability of Path Blocking or Loss
B.11 Four Factors in Packet Delay
B.12 Exponential Distribution and Poisson Process
B.13 Generating Normal and Lognormal Distributions
B.14 Self-Similarity and Heavy-Tailed Distributions
B.15 Markov Chain and the Birth-and-Death Process
B.15.1 Birth-and-Death Process
B.15.3 Trunk Reservation Model for Circuit-Switched Networks
B.16 Average Network Delay
B.17 Packet Format: IPv4, IPv6, TCP, and UDP
C Solutions to Selected Exercises
Network Routing
：Algorithms, Protocols, and Architectures
( 2 )
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
