NETWORKS 0 Preface 3 0.1 Licensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0.2 Classroom Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 0.3 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 0.4 Progress Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 0.5 Technical considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 0.6 A Note On the Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 0.7 Recent Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1 An Overview of Networks 13 1.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2 Data Rate, Throughput and Bandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3 Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4 Datagram Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Routing Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.7 Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.8 Packets Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.9 LANs and Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.10 IP - Internet Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.11 DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.12 Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.13 Firewalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.14 Some Useful Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.15 IETF and OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.16 Berkeley Unix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.17 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 1.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2 Ethernet 45 2.1 10-Mbps Classic Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2 100 Mbps (Fast) Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3 Gigabit Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.4 Ethernet Switches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5 Spanning Tree Algorithm and Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 i 2.6 Virtual LAN (VLAN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.7 TRILL and SPB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.8 Software-Defined Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.9 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3 Other LANs 85 3.1 Virtual Private Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.2 Carrier Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3 Token Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 3.4 Virtual Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.5 Asynchronous Transfer Mode: ATM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.6 Adventures in Radioland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.7 Wi-Fi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.8 WiMAX and LTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 3.9 Fixed Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 3.10 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4 Links 137 4.1 Encoding and Framing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.2 Time-Division Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 4.3 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 5 Packets 149 5.1 Packet Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 5.2 Packet Delay Variability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 5.3 Packet Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 5.4 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 5.5 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 6 Abstract SlidingWindows 165 6.1 Building Reliable Transport: Stop-and-Wait . . . . . . . . . . . . . . . . . . . . . . . . . . 165 6.2 Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 6.3 Linear Bottlenecks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 6.4 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 7 IP version 4 185 7.1 The IPv4 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 7.2 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 7.3 Special Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 7.4 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7.5 The Classless IP Delivery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 7.6 IPv4 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 7.7 Network Address Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 ii 7.8 DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 7.9 Address Resolution Protocol: ARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 7.10 Dynamic Host Configuration Protocol (DHCP) . . . . . . . . . . . . . . . . . . . . . . . . 214 7.11 Internet Control Message Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 7.12 Unnumbered Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 7.13 Mobile IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 7.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 7.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 8 IP version 6 225 8.1 The IPv6 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 8.2 IPv6 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 8.3 Network Prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 8.4 IPv6 Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 8.5 IPv6 Extension Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 8.6 Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 8.7 IPv6 Host Address Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 8.8 Globally Exposed Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 8.9 ICMPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 8.10 IPv6 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 8.11 Using IPv6 and IPv4 Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 8.12 IPv6 Examples Without a Router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 8.13 IPv6 Connectivity via Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 8.14 IPv6-to-IPv4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 8.15 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 9 Routing-Update Algorithms 259 9.1 Distance-Vector Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 260 9.2 Distance-Vector Slow-Convergence Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 264 9.3 Observations on Minimizing Route Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 9.4 Loop-Free Distance Vector Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 9.5 Link-State Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 9.6 Routing on Other Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 9.7 ECMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 9.8 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 9.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280 10 Large-Scale IP Routing 287 10.1 Classless Internet Domain Routing: CIDR . . . . . . . . . . . . . . . . . . . . . . . . . . . 287 10.2 Hierarchical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289 10.3 Legacy Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 10.4 Provider-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 10.5 Geographical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 10.6 Border Gateway Protocol, BGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 10.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 iii 11 UDP Transport 321 11.1 User Datagram Protocol – UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 11.2 Trivial File Transport Protocol, TFTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 11.3 Fundamental Transport Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 11.4 Other TFTP notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 11.5 Remote Procedure Call (RPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 11.6 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 12 TCP Transport 351 12.1 The End-to-End Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 12.2 TCP Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 12.3 TCP Connection Establishment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 12.4 TCP and WireShark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358 12.5 TCP Offloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 12.6 TCP simplex-talk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360 12.7 TCP state diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 12.8 TCP Old Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 12.9 TIMEWAIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371 12.10 The Three-Way Handshake Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 12.11 Anomalous TCP scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 12.12 TCP Faster Opening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375 12.13 Path MTU Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 12.14 TCP Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376 12.15 TCP Delayed ACKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 12.16 Nagle Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 12.17 TCP Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 12.18 Silly Window Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 12.19 TCP Timeout and Retransmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 12.20 KeepAlive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 12.21 TCP timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 12.22 Variants and Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 12.23 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 12.24 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 13 TCP Reno and Congestion Management 397 13.1 Basics of TCP Congestion Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 13.2 Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 13.3 TCP Tahoe and Fast Retransmit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 13.4 TCP Reno and Fast Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 13.5 TCP NewReno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 13.6 Selective Acknowledgments (SACK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 13.7 TCP and Bottleneck Link Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 13.8 Single Packet Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 13.9 TCP Assumptions and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 13.10 TCP Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 13.11 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419 13.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 iv 14 Dynamics of TCP 425 14.1 A First Look At Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 14.2 Bottleneck Links with Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 14.3 TCP Fairness with Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434 14.4 Notions of Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 14.5 TCP Reno loss rate versus cwnd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 14.6 TCP Friendliness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 14.7 AIMD Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 14.8 Active Queue Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449 14.9 The High-Bandwidth TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 14.10 The Lossy-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 14.11 The Satellite-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 14.12 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 14.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 15 Newer TCP Implementations 467 15.1 Choosing a TCP on Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467 15.2 High-Bandwidth Desiderata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 15.3 RTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 15.4 A Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 15.5 Highspeed TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 15.6 TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 15.7 FAST TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 15.8 TCP Westwood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 15.9 TCP Illinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 15.10 Compound TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 15.11 TCP Veno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 15.12 TCP Hybla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 15.13 DCTCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 15.14 H-TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 15.15 TCP CUBIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 15.16 TCP BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493 15.17 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497 15.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 16 Network Simulations: ns-2 503 16.1 The ns-2 simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 16.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 16.3 Two TCP Senders Competing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 16.4 TCP Loss Events and Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . 533 16.5 TCP Reno versus TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 16.6 Wireless Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544 16.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550 17 The ns-3 Network Simulator 553 17.1 Installing and Running ns-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553 17.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554 v 17.3 Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563 17.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569 18 Mininet 571 18.1 Installing Mininet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572 18.2 A Simple Mininet Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 18.3 Multiple Switches in a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575 18.4 IP Routers in a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 18.5 IP Routers With Simple Distance-Vector Implementation . . . . . . . . . . . . . . . . . . . 580 18.6 TCP Competition: Reno vs Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 18.7 TCP Competition: Reno vs BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588 18.8 Linux Traffic Control (tc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589 18.9 OpenFlow and the POX Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592 18.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604 19 Queuing and Scheduling 607 19.1 Queuing and Real-Time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 19.2 Traffic Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608 19.3 Priority Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608 19.4 Queuing Disciplines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609 19.5 Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610 19.6 Applications of Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622 19.7 Hierarchical Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 19.8 Hierarchical Weighted Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 19.9 Token Bucket Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 19.10 Applications of Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638 19.11 Token Bucket Queue Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 19.12 Hierarchical Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643 19.13 Fair Queuing / Token Bucket combinations . . . . . . . . . . . . . . . . . . . . . . . . . . 644 19.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 19.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 20 Quality of Service 653 20.1 Net Neutrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654 20.2 Where the Wild Queues Are . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654 20.3 Real-time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 20.4 Integrated Services / RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657 20.5 Global IP Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658 20.6 RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 20.7 Differentiated Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667 20.8 RED with In and Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 20.9 NSIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672 20.10 Comcast Congestion-Management System . . . . . . . . . . . . . . . . . . . . . . . . . . 672 20.11 Real-time Transport Protocol (RTP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673 20.12 Multi-Protocol Label Switching (MPLS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 678 20.13 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680 20.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680 vi 21 Network Management and SNMP 683 21.1 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685 21.2 SNMP Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685 21.3 SNMP Naming and OIDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687 21.4 MIBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689 21.5 SNMPv1 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690 21.6 ASN.1 Syntax and SNMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690 21.7 SNMP Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 21.8 SNMP Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696 21.9 MIB Browsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701 21.10 MIB-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702 21.11 SNMPv1 communities and security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711 21.12 SNMP and ASN.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712 21.13 SNMPv2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 21.14 Table Row Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 21.15 SNMPv3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734 21.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744 22 Security 747 22.1 Code-Execution Intrusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 22.2 Stack Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749 22.3 Heap Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 758 22.4 Network Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763 22.5 Cryptographic Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764 22.6 Secure Hashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765 22.7 Shared-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770 22.8 Diffie-Hellman-Merkle Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779 22.9 Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782 22.10 SSH and TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786 22.11 IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805 22.12 RSA Key Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808 22.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811 23 Bibliography 815 24 Selected Solutions 817 24.1 Solutions for An Overview of Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 817 24.2 Solutions for Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818 24.3 Solutions for Other LANs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819 24.4 Solutions for Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820 24.5 Solutions for Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 821 24.6 Solutions for Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822 24.7 Solutions for IPv4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824 24.8 Solutions for Routing-Update Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 824 24.9 Solutions for Large-Scale IP Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825 24.10 Solutions for UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826 24.11 Solutions for TCP Reno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826 24.12 Solutions for Dynamics of TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826 vii 24.13 Solutions for Mininet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828 Indices and tables 829 Bibliography 831 Index 839
NETWORKS
0 Preface 3
0.1 Licensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.2 Classroom Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.3 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.4 Progress Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.5 Technical considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.6 A Note On the Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.7 Recent Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1 An Overview of Networks 13
1.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Data Rate, Throughput and Bandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Datagram Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Routing Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.7 Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.8 Packets Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.9 LANs and Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.10 IP - Internet Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.11 DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.12 Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.13 Firewalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.14 Some Useful Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.15 IETF and OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.16 Berkeley Unix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.17 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2 Ethernet 45
2.1 10-Mbps Classic Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2 100 Mbps (Fast) Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3 Gigabit Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.4 Ethernet Switches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.5 Spanning Tree Algorithm and Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
i
2.6 Virtual LAN (VLAN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.7 TRILL and SPB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
2.8 Software-Defined Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.9 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3 Other LANs 85
3.1 Virtual Private Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2 Carrier Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.3 Token Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.4 Virtual Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.5 Asynchronous Transfer Mode: ATM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.6 Adventures in Radioland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.7 Wi-Fi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.8 WiMAX and LTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.9 Fixed Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
3.10 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
4 Links 137
4.1 Encoding and Framing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.2 Time-Division Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
4.3 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
5 Packets 149
5.1 Packet Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
5.2 Packet Delay Variability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
5.3 Packet Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
5.4 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.5 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6 Abstract SlidingWindows 165
6.1 Building Reliable Transport: Stop-and-Wait . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.2 Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6.3 Linear Bottlenecks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
6.4 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7 IP version 4 185
7.1 The IPv4 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
7.2 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
7.3 Special Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
7.4 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
7.5 The Classless IP Delivery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
7.6 IPv4 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.7 Network Address Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
ii
7.8 DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
7.9 Address Resolution Protocol: ARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.10 Dynamic Host Configuration Protocol (DHCP) . . . . . . . . . . . . . . . . . . . . . . . . 214
7.11 Internet Control Message Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
7.12 Unnumbered Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
7.13 Mobile IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
7.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
7.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
8 IP version 6 225
8.1 The IPv6 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
8.2 IPv6 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
8.3 Network Prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229
8.4 IPv6 Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.5 IPv6 Extension Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.6 Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
8.7 IPv6 Host Address Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.8 Globally Exposed Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
8.9 ICMPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.10 IPv6 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
8.11 Using IPv6 and IPv4 Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.12 IPv6 Examples Without a Router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
8.13 IPv6 Connectivity via Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
8.14 IPv6-to-IPv4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
8.15 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
8.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
9 Routing-Update Algorithms 259
9.1 Distance-Vector Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 260
9.2 Distance-Vector Slow-Convergence Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9.3 Observations on Minimizing Route Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
9.4 Loop-Free Distance Vector Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
9.5 Link-State Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
9.6 Routing on Other Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9.7 ECMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
9.8 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
9.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
10 Large-Scale IP Routing 287
10.1 Classless Internet Domain Routing: CIDR . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
10.2 Hierarchical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
10.3 Legacy Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
10.4 Provider-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
10.5 Geographical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
10.6 Border Gateway Protocol, BGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
10.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
iii
11 UDP Transport 321
11.1 User Datagram Protocol – UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
11.2 Trivial File Transport Protocol, TFTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
11.3 Fundamental Transport Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
11.4 Other TFTP notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
11.5 Remote Procedure Call (RPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
11.6 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
12 TCP Transport 351
12.1 The End-to-End Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
12.2 TCP Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
12.3 TCP Connection Establishment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
12.4 TCP and WireShark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
12.5 TCP Offloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
12.6 TCP simplex-talk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
12.7 TCP state diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
12.8 TCP Old Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
12.9 TIMEWAIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
12.10 The Three-Way Handshake Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
12.11 Anomalous TCP scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
12.12 TCP Faster Opening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
12.13 Path MTU Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
12.14 TCP Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
12.15 TCP Delayed ACKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
12.16 Nagle Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.17 TCP Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.18 Silly Window Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.19 TCP Timeout and Retransmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.20 KeepAlive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
12.21 TCP timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.22 Variants and Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.23 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
12.24 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
13 TCP Reno and Congestion Management 397
13.1 Basics of TCP Congestion Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
13.2 Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
13.3 TCP Tahoe and Fast Retransmit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
13.4 TCP Reno and Fast Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
13.5 TCP NewReno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
13.6 Selective Acknowledgments (SACK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
13.7 TCP and Bottleneck Link Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
13.8 Single Packet Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
13.9 TCP Assumptions and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
13.10 TCP Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
13.11 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
13.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
iv
14 Dynamics of TCP 425
14.1 A First Look At Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
14.2 Bottleneck Links with Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
14.3 TCP Fairness with Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
14.4 Notions of Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
14.5 TCP Reno loss rate versus cwnd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
14.6 TCP Friendliness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
14.7 AIMD Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
14.8 Active Queue Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
14.9 The High-Bandwidth TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
14.10 The Lossy-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14.11 The Satellite-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14.12 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
14.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
15 Newer TCP Implementations 467
15.1 Choosing a TCP on Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
15.2 High-Bandwidth Desiderata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
15.3 RTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
15.4 A Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
15.5 Highspeed TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
15.6 TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
15.7 FAST TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
15.8 TCP Westwood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
15.9 TCP Illinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
15.10 Compound TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
15.11 TCP Veno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
15.12 TCP Hybla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
15.13 DCTCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
15.14 H-TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
15.15 TCP CUBIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
15.16 TCP BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
15.17 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
15.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
16 Network Simulations: ns-2 503
16.1 The ns-2 simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
16.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
16.3 Two TCP Senders Competing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
16.4 TCP Loss Events and Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . 533
16.5 TCP Reno versus TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
16.6 Wireless Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
16.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 550
17 The ns-3 Network Simulator 553
17.1 Installing and Running ns-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
17.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
v
17.3 Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
17.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569
18 Mininet 571
18.1 Installing Mininet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572
18.2 A Simple Mininet Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574
18.3 Multiple Switches in a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575
18.4 IP Routers in a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
18.5 IP Routers With Simple Distance-Vector Implementation . . . . . . . . . . . . . . . . . . . 580
18.6 TCP Competition: Reno vs Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
18.7 TCP Competition: Reno vs BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
18.8 Linux Traffic Control (tc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
18.9 OpenFlow and the POX Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
18.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
19 Queuing and Scheduling 607
19.1 Queuing and Real-Time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
19.2 Traffic Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
19.3 Priority Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
19.4 Queuing Disciplines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 609
19.5 Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
19.6 Applications of Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
19.7 Hierarchical Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625
19.8 Hierarchical Weighted Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
19.9 Token Bucket Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
19.10 Applications of Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
19.11 Token Bucket Queue Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
19.12 Hierarchical Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
19.13 Fair Queuing / Token Bucket combinations . . . . . . . . . . . . . . . . . . . . . . . . . . 644
19.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
19.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
20 Quality of Service 653
20.1 Net Neutrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654
20.2 Where the Wild Queues Are . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654
20.3 Real-time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655
20.4 Integrated Services / RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
20.5 Global IP Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
20.6 RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663
20.7 Differentiated Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
20.8 RED with In and Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
20.9 NSIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672
20.10 Comcast Congestion-Management System . . . . . . . . . . . . . . . . . . . . . . . . . . 672
20.11 Real-time Transport Protocol (RTP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
20.12 Multi-Protocol Label Switching (MPLS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
20.13 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
20.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
vi
21 Network Management and SNMP 683
21.1 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
21.2 SNMP Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 685
21.3 SNMP Naming and OIDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687
21.4 MIBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
21.5 SNMPv1 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
21.6 ASN.1 Syntax and SNMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
21.7 SNMP Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
21.8 SNMP Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696
21.9 MIB Browsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
21.10 MIB-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
21.11 SNMPv1 communities and security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
21.12 SNMP and ASN.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
21.13 SNMPv2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
21.14 Table Row Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
21.15 SNMPv3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
21.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744
22 Security 747
22.1 Code-Execution Intrusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
22.2 Stack Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749
22.3 Heap Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 758
22.4 Network Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763
22.5 Cryptographic Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
22.6 Secure Hashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765
22.7 Shared-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770
22.8 Diffie-Hellman-Merkle Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 779
22.9 Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
22.10 SSH and TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786
22.11 IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805
22.12 RSA Key Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808
22.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
23 Bibliography 815
24 Selected Solutions 817
24.1 Solutions for An Overview of Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 817
24.2 Solutions for Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818
24.3 Solutions for Other LANs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819
24.4 Solutions for Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820
24.5 Solutions for Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 821
24.6 Solutions for Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822
24.7 Solutions for IPv4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
24.8 Solutions for Routing-Update Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
24.9 Solutions for Large-Scale IP Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825
24.10 Solutions for UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
24.11 Solutions for TCP Reno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
24.12 Solutions for Dynamics of TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
vii
24.13 Solutions for Mininet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828
Indices and tables 829
Bibliography 831
Index 839
Leave us your details we will revert you as soon as possible.
Copyright © 2014 - All Rights Reserved - nimtweb.org Google
Powered by Nasbar Infotech