Interconnections: Bridges, Routers, Switches, and Internetworking Protocols

Copyright
Preface

Roadmap to the Book
Acknowledgments

1. Essential Networking Concepts

1.1. Layers
1.2. Service Models
1.3. Important Properties of a Network
1.4. Reliable Data Transfer Protocols
Homework

2. Data Link Layer Issues

2.1. Generic LANs
2.1.1. What Is a LAN?
2.1.2. Taking Turns
2.2. IEEE 802 LANs
2.3. Names, Addresses, Routes
2.4. LAN Addresses
2.5. Multicast versus Unicast Addresses
2.6. The Broadcast Address
2.7. Multiplexing Field
2.8. Bit Order
2.9. Logical Link Control
2.10. Issues in 802.3
2.11. Issues in 802.5
2.12. Packet Bursts
2.13. Reasons for Bridges
2.14. Point-to-Point Links
Homework

3. Transparent Bridges

3.1. The No-Frills Bridge
3.2. The Learning Bridge
3.3. Spanning Tree Algorithm
3.3.1. Configuration Messages
3.3.2. Calculation of Root ID and Cost to Root
3.3.3. Selecting Spanning Tree Ports
3.3.4. An Example
3.4. Spanning Tree Algorithm Refinements
3.4.1. Failures
3.4.2. Avoiding Temporary Loops
3.4.3. Station Cache Timeout Values
3.4.4. Networkwide Parameters
3.4.5. Port ID
3.4.6. Assigning Port Numbers
3.4.7. Performance Issues
3.4.8. One-way Connectivity
3.4.9. Settable Parameters
3.5. Bridge Message Formats
3.5.1. Configuration Message Format
3.5.2. Topology change notification format
3.6. Other Bridge Issues
3.6.1. Multiply Connected Stations
3.6.2. Configuration of Filtering
3.6.3. Not Quite Transparent
3.7. Remote Bridges
Homework

4. Source Routing Bridges

4.1. Pure Source Routing
4.1.1. The Routing Header
4.1.2. Bridge Numbers
4.1.2.1. Internal LAN Number
4.1.2.2. The Route
4.1.2.3. Reasons for Parallel Bridges
4.1.3. Bridge Algorithms
4.1.3.1. Transparent Packets
4.1.3.2. Specifically Routed Packets
4.1.3.3. All Paths Explorer Packets
4.1.3.4. Spanning Tree Explorer Packets
4.2. SR-TB Bridges
4.2.1. Packets from a TB Port
4.2.2. Packets from an SR Port
4.2.3. Loops
4.3. SRT Bridges
4.4. End-system Algorithms
4.4.1. When to Find a Route
4.4.2. How to Find a Route
4.4.2.1. Route Finding Strategy 1
4.4.2.2. Route Finding Strategy 2
4.4.2.3. Route Find Strategy 3
4.4.2.4. Route Finding Strategy 4
4.4.2.5. Route Finding Strategy 5
4.4.2.6. Route Finding Strategy 6
4.4.3. Route Discovery by the Destination
4.4.4. Route Selection
4.5. Source Routing versus Transparent Bridging
4.5.1. Bandwidth Overhead
4.5.2. Ease of Configuration
4.5.3. Universality
4.5.4. Cost and Performance of Bridges
4.6. Ideas for Improving Source Route Bridging
4.6.1. Autoconfiguration with Source Route Bridging
4.6.2. Fixing the Exponential Overhead
Homework

5. Hubs, Switches, Virtual LANs, and Fast Ethernet

5.1. Hubs
5.1.1. The Learning Hub and Security
5.1.2. Store-and-Forward and Spanning Tree
5.1.3. Mixing Layer 1 and 2 Switches
5.1.4. Products versus Standards, Layer 1 versus Layer 2
5.2. Faster LANs
5.3. Virtual LANs (VLANs)
5.3.1. Why VLANs?
5.3.2. Mapping Ports to VLANs
5.3.3. Example: VLAN Forwarding with Separate Router
5.3.4. Example: VLAN Forwarding with Switch as Router
5.3.5. Dynamic Binding of Links to VLANs
5.3.6. Dynamic VLAN Binding, Switch-Switch
Homework

6. Network Interface: Service Models

6.1. What Is the Network Layer?
6.2. Network Service Types
6.2.1. Performance Guarantees
6.2.2. Sample Service Model Choices
6.2.3. Hybrid Schemes
6.2.4. Connectionless versus Connection-oriented
Homework

7. Connection-oriented Nets: X.25 and ATM

7.1. Generic Connection-oriented Network
7.2. X.25: Reliable Connection-oriented Service
7.2.1. The Basic Idea
7.2.2. Virtual Circuit Numbers
7.2.3. Call Setup
7.2.4. Data Transfer
7.2.5. Flow Control
7.2.6. Facilities
7.2.7. Call Release
7.2.8. Interrupts
7.3. Implementing X.25 Inside the Net
7.3.1. Circuit Method
7.3.2. Reliable Connections over Datagrams Method
7.3.3. Comparison
7.4. Asynchronous Transfer Mode
7.4.1. Cell Size
7.4.2. Virtual Circuits and Virtual Paths
7.4.3. ATM Service Categories
7.4.4. ATM Cell Header Format
7.4.5. Setting Up and Releasing Calls
7.4.6. ATM Adaptation Layers
7.4.6.1. AAL1
7.4.6.2. AAL3/4
7.4.6.3. AAL5
Homework

8. Generic Connectionless Service

8.1. Data Transfer
8.2. Addresses
8.3. Hop Count
8.4. Service Class Information
8.4.1. Priority
8.4.2. Bandwidth Reservation and Service Guarantees
8.4.3. Special Route Computation
8.5. Network Feedback
8.6. Fragmentation and Reassembly
8.7. Maximum Packet Size Discovery
Homework

9. Network Layer Addresses

9.1. Hierarchical Addresses with Fixed Boundaries
9.2. Hierarchical Addresses with Flexible Boundaries
9.3. Owning versus Renting Addresses
9.4. Types of Addresses
9.5. IP
9.5.1. IP Address Conventions
9.5.2. Text Representation of IP Addresses
9.6. IPX
9.6.1. Privacy Issue with Unique IDs
9.6.2. Ugly Rumors about IPX
9.6.3. Administering IPX Addresses
9.6.4. Internal IPX Network Numbers
9.7. IPX+
9.8. IPv6
9.8.1. The IPv6 Version Number Story
9.8.2. Written Representation of IPv6 Addresses
9.8.3. Written Representation of IPv6 Prefixes
9.8.4. EUI-64
9.8.5. EUI-64 As Used by IPv6
9.8.6. IPv6 Address Conventions
9.8.7. Transition from IPv4 to IPv6
9.9. CLNP Network Layer Addresses
9.9.1. Autoconfiguration
9.9.2. Embedded DTE Addresses
9.10. AppleTalk Network Layer Addresses
9.11. DECnet Phases III and IV
9.11.1. A Bit of History
9.11.2. DECnet Phase IV Address
9.11.3. Mapping DECnet Address to Ethernet Address
9.12. NAT/NAPT
Homework

10. Connectionless Data Packet Formats

10.1. Pieces of a Connectionless Network Layer
10.2. Data Packets
10.3. Summary of Packet Formats for Easy Reference
10.3.1. IP
10.3.2. IPX
10.3.3. IPX+
10.3.4. AppleTalk
10.3.5. IPv6
10.3.6. DECnet
10.3.7. CLNP
10.4. Technical Issues and Comparisons in Data Packet Formats
10.4.1. Destination Address
10.4.2. Source Address
10.4.3. Destination and Source Sockets
10.4.4. Header Length
10.4.5. Packet Length
10.4.6. Header Checksum
10.4.7. Fragmentation Allowed
10.4.8. Packet Identifier
10.4.9. Fragment Offset
10.4.10. Prefragmentation Length
10.4.11. More Fragments Follow
10.4.12. Lifetime
10.4.13. Version
10.4.14. Padding
10.4.15. Protocol
10.4.16. Type
10.4.17. Error Report Requested
10.4.18. Congestion Feedback: Source Quench versus DEC Bit
10.4.19. Type of Service
10.4.19.1. TOS Field in IPv4
10.4.19.2. TOS in CLNP
10.4.19.3. TOS in IPX, AppleTalk, and DECnet
10.4.19.4. New Ideas for TOS
10.4.20. Options
10.4.20.1. Options in CLNP
10.4.20.2. Options in IP
10.5. Source Routing
10.5.1. Loose versus Strict Source Routing
10.5.2. Overwriting a Source Route with an Outgoing Link Address
10.5.3. Overwriting a Destination Address with a Next Source Route Destination
10.5.4. A Security Flaw with the Source Route Option
10.6. The Great IPX Frame Format Mystery
10.6.1. IPX's Four Frame Formats
10.6.2. Dealing with Multiple IPX Frame Formats
10.7. Error Reports and Other Network Feedback to the Endnode
10.7.1. CLNP Error Messages
10.7.2. ICMP: IP Error Messages
10.7.3. IPv6 Error Messages
Homework

11. Neighbor Greeting and Autoconfiguration

11.1. Endnodes Attached via Point-to-Point Links
11.2. Endnodes Attached via LANs
11.2.1. ES-IS: The CLNP Solution
11.2.2. The IP Solution
11.2.2.1. IP: Finding Neighbors' Layer 2 Addresses
11.2.2.2. ARP/RARP Message Format
11.2.2.3. Redirect Messages
11.2.2.4. IP: Endnode Autoconfiguration
11.2.3. The IPX Solution
11.2.4. The DECnet Solution
11.2.5. The AppleTalk Solution
11.2.5.1. Knowing Who Is on Your LAN
11.2.5.2. Finding a Router
11.2.5.3. Acquiring an AppleTalk Address
11.2.5.4. Seed Routers
11.2.5.5. Some Wrinkles
11.2.5.6. Finding the Best Router for a Given Destination
11.2.6. The IPv6 Solution
11.2.7. Review and Comparisons
11.2.7.1. Endnodes Acquire a Layer 3 Address
11.2.7.2. Router Finds Out Layer 3 Addresses of Endnode Neighbors
11.2.7.3. Router Finds Out Layer 2 Addresses of Endnode Neighbors
11.2.7.4. Endnodes Find a Router
11.2.7.5. Endnode Neighbors Send Directly to Each Other
11.2.7.6. Finding the Best Router
11.2.7.7. Routerless LAN
11.2.8. Comparisons
11.2.8.1. ES-IS versus ARP
11.3. Endnodes Attached via Nonbroadcast Multiaccess Media
11.3.1. Various Solutions
11.3.2. Providing Multicast in the Protocol Y Cloud
11.3.2.1. Bridging
11.3.2.2. Multicast in IPX
11.3.2.3. Multicast in ATM
11.3.2.4. Multicast in SMDS
11.3.3. LAN Emulation
11.3.3.1. Some LANE Jargon
11.3.3.2. A Client (LEC) Boots Up
11.3.3.3. Joining an ELAN
11.3.3.4. Transmitting to Another LEC
11.3.3.5. Sending a Multicast Packet
11.3.4. Classical IP and ARP over ATM
11.3.5. Cutting Out Extra Hops
11.4. Finding Things
11.4.1. Finding Services, Generically
11.4.2. AppleTalk's Scheme
11.4.3. Service Advertising Protocol for NetWare
Homework

12. Routing Algorithm Concepts

12.1. Distance Vector Routing
12.1.1. Why Not Distance Vector?
12.1.1.1. Hold-down
12.1.1.2. Reporting the Entire Path
12.1.1.3. Split Horizon
12.1.1.4. Two Metrics
12.1.1.5. Triggered Updates
12.1.1.6. Poison Reverse
12.1.1.7. DUAL
12.2. Link State Routing
12.2.1. Meeting Neighbors
12.2.2. Constructing an LSP
12.2.3. Disseminating the LSP to All Routers
12.2.3.1. Timestamps
12.2.3.2. Sequence Number/Age Schemes
12.2.3.3. The ARPANET LSP Distribution Scheme
12.2.3.4. New, Improved LSP Distribution
12.2.4. Computing Routes
12.3. Comparison of Link State and Distance Vector Routing
12.3.1. Memory
12.3.2. Bandwidth Consumed
12.3.3. Computation
12.3.4. A Note about Computation Cost
12.3.5. Robustness
12.3.6. Functionality
12.3.7. Speed of Convergence
12.4. Load Splitting
12.5. Link Costs
12.6. Migrating Routing Algorithms
12.6.1. Running Both Algorithms
12.6.2. Manual Node-by-Node Switch
12.6.3. Translation
12.7. LANs
12.7.1. Making the LAN a Node
12.7.2. Disseminating Routing Information
12.8. Types of Service
12.8.1. Handling Directives
12.8.2. Multiple Metrics
12.8.3. Policy-based Routing and Policy-based Constraints
12.8.4. Static Routes
12.8.5. Filters
12.8.6. Source Routing
12.8.7. Routing-domain-specific Policy
12.8.8. Service-class-specific Policy
12.9. Partition Repair: Level 1 Subnetwork Partition
Homework

13. Fast Packet Forwarding

13.1. Using an Additional Header
13.2. Address Prefix Matching
13.3. Longest Prefix Match with Trie
13.3.1. Collapsing a Long Nonbranching Path
13.3.2. Trading Memory for Search Time
13.3.3. Binary Search on Prefix Lengths
13.3.4. Exploiting Parallelism with Special Hardware
13.3.4.1. Preparing the Data Structure for the Lookup Engine
13.3.4.2. Doing a Lookup
13.3.4.3. Optimizations
13.4. Binary Search
13.4.1. Sort the Prefixes
13.4.2. Add Prefix Length to 1-padded Prefixes
13.4.3. Get Rid of Duplicate Padded Prefixes
13.4.4. K-ary Search
13.4.5. Doing a Lookup
Homework

14. Specific Routing Protocols

14.1. A Brief History of Intradomain Routing Protocols
14.2. RIP
14.2.1. RIP Version 2
14.3. RTMP, IPX-RIP, and DECnet
14.4. IS-IS, OSPF, NLSP, and PNNI
14.4.1. Hierarchy
14.4.1.1. IS-IS Hierarchy
14.4.1.2. NLSP Hierarchy
14.4.1.3. OSPF Hierarchy
14.4.1.4. PNNI Hierarchy
14.4.2. Area Addresses
14.4.2.1. IS-IS Area Addresses
14.4.2.2. OSPF Area Addresses
14.4.2.3. NLSP Area Addresses
14.4.2.4. PNNI Peer Group Names
14.4.3. LANs and Designated Routers
14.4.3.1. IS-IS Designated Router Election
14.4.3.2. OSPF Designated Router Election
14.4.3.3. NLSP Designated Router Election
14.4.3.4. PNNI Peer Group Leader Election
14.4.4. Reliable Propagation of LSPs on LANs
14.4.4.1. IS-IS and NLSP Link State Information Propagation
14.4.4.2. OSPF Link State Information Propagation
14.4.4.3. Comparison
14.4.5. Parameter Synchronization
14.4.5.1. IS-IS Parameter Synchronization
14.4.5.2. OSPF Parameter Synchronization
14.4.5.3. PNNI Parameter Synchronization
14.4.6. Destinations per Packet
14.4.7. LSP Database Overload
14.4.7.1. IS-IS Database Overload
14.4.7.2. OSPF Database Overload
14.4.7.3. PNNI Database Overload
14.4.8. Authentication
14.4.9. IS-IS Details
14.4.9.1. IS-IS for IP
14.4.9.2. LAN Designated Router
14.4.9.3. Big Packets
14.4.9.4. Partitioned Areas
14.4.9.5. Partitioned Level 2 Network
14.4.9.6. Multiarea Bridged LANs
14.4.9.7. Packets Used by IS-IS
IS-to-IS Hello
LSP
Sequence Numbers Packet
14.4.10. OSPF
14.4.10.1. General Packet-encoding Issues
14.4.10.2. Terminology
14.4.10.3. Area Partitions
14.4.10.4. Level 2 Partitions
14.4.10.5. Finding the Right Level 2 Router
14.4.10.6. Neighbor Initialization
14.4.10.7. Types of LSAs
14.4.10.8. Packet Encoding
Hello Packets
Database Description Packets
Link State Request
Link State Update
Link State Acknowledgment
Link State Advertisement
Router Links Advertisement
Network Links Advertisement
Summary Link Advertisement
AS External Link Advertisement
14.4.11. PNNI Details
14.4.11.1. Path Setup
14.4.11.2. Area Partitions
14.5. Interdomain Routing Protocols
14.5.1. Static Routing
14.5.2. EGP
14.5.2.1. Neighbor Acquisition
14.5.2.2. Neighbor Reachability
14.5.2.3. Routing Information
14.5.3. BGP
14.5.3.1. BGP Neighbors
14.5.3.2. BGP Attributes
14.5.3.3. BGP Policies
14.5.3.4. Confederations
14.5.3.5. Message Types
14.5.3.6. Message Formats
Open Message Format
Update Message Format
Notification Message Format
Keepalive Message Format
Homework

15. WAN Multicast

15.1. Introduction
15.1.1. Layer 2 Multicast
15.1.2. Reasons for Layer 3 Multicast
15.1.3. Dimensions to Consider
15.1.4. Multihop Multicast (other than in IP)
15.2. Multicast in IP
15.2.1. Centralized versus Decentralized Multicast
15.2.2. Could We Do Without Layer 3 Multicast?
15.2.3. Mapping NL Multicast to DL Multicast
15.2.4. IGMP Protocol
15.2.5. IGMP Snooping
15.2.6. Reverse Path Forwarding
15.2.7. Distance Vector Multicast Routing Protocol
15.2.8. Multicast OSPF
15.2.9. Core-based Trees
15.2.10. PIM-DM
15.2.11. PIM-SM
15.2.12. BGMP/MASC
15.2.13. Multicast Source Distribution Protocol
15.2.14. Simplifying Multicast
15.2.14.1. Creating a Group in Simple Multicast: Choosing C
15.2.14.2. How Do Endnodes Discover C?
15.2.14.3. Isn't a Shared Tree Suboptimal?
15.2.14.4. Single Point of Failure?
15.2.14.5. Controlling Who Can Send
15.2.14.6. Policy
15.2.14.7. Specifying C in Join Messages
15.2.14.8. Specify Both C and G in Data Messages
15.2.14.9. Dense-mode Groups
15.2.14.10. Express
15.2.14.11. What Is Simpler About Simple Multicast?
Homework

16. Sabotage-proof Routing

16.1. The Problem
16.2. All You Need to Know about Cryptography
16.3. Overview of the Approach
16.3.1. Robust Flooding
16.3.1.1. Summary of Robust Flooding
16.3.2. Robust Routing
16.4. Detailed Description of the Approach
16.4.1. Robust Flooding Revisited
16.4.1.1. A Priori Information
16.4.1.2. Dynamic Database
16.4.1.3. Dealing with Multiple Public Key Distributors
16.4.1.4. Packets
16.4.1.5. Distribution of Public Key List Packets
16.4.1.6. Distribution of LSPs
16.4.1.7. Receipt of Acks
16.4.1.8. Running Out of Sequence Number
16.4.2. Robust Data Routing
16.4.3. Additional Dynamic Database
16.4.3.1. Additional Packets
16.4.3.2. Receipt of Route-setup Packets
16.4.3.3. Receipt of Data Packets
16.4.3.4. Nonfunctioning Routes
16.5. Summary
16.6. For Further Reading
Homework

17. To Route, Bridge, or Switch: Is That the Question?

17.1. Switches
17.2. Bridges versus Routers
17.3. Extensions to Bridges
17.3.1. Using More Than the Spanning Tree
17.3.2. Fragmenting Bridges
17.3.3. IGMP Snooping
17.4. Extensions to Routers
17.4.1. Faster Routers
17.4.2. Multiprotocol Routers
17.4.3. Single-protocol Backbone
17.4.4. Brouters

18. Protocol Design Folklore

18.1. Simplicity versus Flexibility versus Optimality
18.2. Knowing the Problem You're Trying to Solve
18.3. Overhead and Scaling
18.4. Operation Above Capacity
18.5. Compact IDs versus Object Identifiers
18.6. Optimizing for the Most Common or Important Case
18.7. Forward Compatibility
18.7.1. Large Enough Fields
18.7.2. Independence of Layers
18.7.3. Reserved Fields
18.7.4. Single Version-number Field
18.7.5. Split Version-number Field
18.7.6. Options
18.8. Migration: Routing Algorithms and Addressing
18.9. Parameters
18.9.1. Avoiding Parameters
18.9.2. Legal Parameter Setting
18.9.2.1. "Report My Values" Method
18.9.2.2. "Detect Misconfiguration" Method
18.9.2.3. "Use My Parameters" Method
18.10. Making Multiprotocol Operation Possible
18.11. Running over Layer 3 versus Layer 2
18.12. Robustness
18.13. Determinism versus Stability
18.14. Performance for Correctness
18.15. In Closing

Glossary