Apply Now
CONTENTS
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.10 Dynamic Host Configuration Protocol (DHCP) . . . . . . . . . . . . . . . . . . . . . . . . 217
7.11 Internet Control Message Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
7.12 Unnumbered Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
7.13 Mobile IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
7.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
7.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
8 IP version 6 229
8.1 The IPv6 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
8.2 IPv6 Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
8.3 Network Prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.4 IPv6 Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
8.5 IPv6 Extension Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
8.6 Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
8.7 IPv6 Host Address Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
8.8 Globally Exposed Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.9 ICMPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
8.10 IPv6 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
8.11 Using IPv6 and IPv4 Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
8.12 IPv6 Examples Without a Router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.13 IPv6 Connectivity via Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.14 IPv6-to-IPv4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
8.15 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
8.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
9 Routing-Update Algorithms 263
9.1 Distance-Vector Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9.2 Distance-Vector Slow-Convergence Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 268
9.3 Observations on Minimizing Route Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.4 Loop-Free Distance Vector Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
9.5 Link-State Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
9.6 Routing on Other Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
9.7 ECMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
9.8 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
9.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
10 Large-Scale IP Routing 291
10.1 Classless Internet Domain Routing: CIDR . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
10.2 Hierarchical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
10.3 Legacy Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
10.4 Provider-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
10.5 Geographical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.6 Border Gateway Protocol, BGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
iii
11 UDP Transport 325
11.1 User Datagram Protocol – UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
11.2 Trivial File Transport Protocol, TFTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
11.3 Fundamental Transport Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
11.4 Other TFTP notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
11.5 Remote Procedure Call (RPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
11.6 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
12 TCP Transport 355
12.1 The End-to-End Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
12.2 TCP Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
12.3 TCP Connection Establishment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
12.4 TCP and WireShark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
12.5 TCP Offloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
12.6 TCP simplex-talk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
12.7 TCP state diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
12.8 TCP Old Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
12.9 TIMEWAIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
12.10 The Three-Way Handshake Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
12.11 Anomalous TCP scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
12.12 TCP Faster Opening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.13 Path MTU Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
12.14 TCP Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
12.15 TCP Delayed ACKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
12.16 Nagle Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
12.17 TCP Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
12.18 Silly Window Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
12.19 TCP Timeout and Retransmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
12.20 KeepAlive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
12.21 TCP timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
12.22 Variants and Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
12.23 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
12.24 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
13 TCP Reno and Congestion Management 401
13.1 Basics of TCP Congestion Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
13.2 Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
13.3 TCP Tahoe and Fast Retransmit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
13.4 TCP Reno and Fast Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
13.5 TCP NewReno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
13.6 Selective Acknowledgments (SACK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
13.7 TCP and Bottleneck Link Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
13.8 Single Packet Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
13.9 TCP Assumptions and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
13.10 TCP Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
13.11 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
13.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
iv
14 Dynamics of TCP 429
14.1 A First Look At Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
14.2 Bottleneck Links with Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
14.3 TCP Fairness with Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
14.4 Notions of Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
14.5 TCP Reno loss rate versus cwnd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
14.6 TCP Friendliness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
14.7 AIMD Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
14.8 Active Queue Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
14.9 The High-Bandwidth TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 458
14.10 The Lossy-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
14.11 The Satellite-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
14.12 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
14.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
15 Newer TCP Implementations 471
15.1 Choosing a TCP on Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
15.2 High-Bandwidth Desiderata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
15.3 RTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
15.4 A Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
15.5 Highspeed TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
15.6 TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
15.7 FAST TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
15.8 TCP Westwood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
15.9 TCP Illinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
15.10 Compound TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
15.11 TCP Veno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
15.12 TCP Hybla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
15.13 DCTCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
15.14 H-TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
15.15 TCP CUBIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
15.16 TCP BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
15.17 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
15.18 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
16 Network Simulations: ns-2 507
16.1 The ns-2 simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
16.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
16.3 Two TCP Senders Competing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521
16.4 TCP Loss Events and Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . 537
16.5 TCP Reno versus TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
16.6 Wireless Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
16.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
17 The ns-3 Network Simulator 557
17.1 Installing and Running ns-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
17.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
v
17.3 Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
17.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
18 Mininet 575
18.1 Installing Mininet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
18.2 A Simple Mininet Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
18.3 Multiple Switches in a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
18.4 IP Routers in a Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582
18.5 IP Routers With Simple Distance-Vector Implementation . . . . . . . . . . . . . . . . . . . 584
18.6 TCP Competition: Reno vs Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587
18.7 TCP Competition: Reno vs BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
18.8 Linux Traffic Control (tc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
18.9 OpenFlow and the POX Controller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596
18.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
19 Queuing and Scheduling 611
19.1 Queuing and Real-Time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
19.2 Traffic Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
19.3 Priority Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
19.4 Queuing Disciplines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613
19.5 Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614
19.6 Applications of Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
19.7 Hierarchical Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
19.8 Hierarchical Weighted Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
19.9 Token Bucket Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
19.10 Applications of Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
19.11 Token Bucket Queue Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
19.12 Hierarchical Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
19.13 Fair Queuing / Token Bucket combinations . . . . . . . . . . . . . . . . . . . . . . . . . . 648
19.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
19.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
20 Quality of Service 657
20.1 Net Neutrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
20.2 Where the Wild Queues Are . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
20.3 Real-time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
20.4 Integrated Services / RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
20.5 Global IP Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662
20.6 RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
20.7 Differentiated Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
20.8 RED with In and Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
20.9 NSIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 676
20.10 Comcast Congestion-Management System . . . . . . . . . . . . . . . . . . . . . . . . . . 676
20.11 Real-time Transport Protocol (RTP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
20.12 Multi-Protocol Label Switching (MPLS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
20.13 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684
20.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684
vi
21 Network Management and SNMP 687
21.1 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
21.2 SNMP Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
21.3 SNMP Naming and OIDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
21.4 MIBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
21.5 SNMPv1 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
21.6 ASN.1 Syntax and SNMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
21.7 SNMP Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695
21.8 SNMP Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
21.9 MIB Browsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
21.10 MIB-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
21.11 SNMPv1 communities and security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
21.12 SNMP and ASN.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716
21.13 SNMPv2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
21.14 Table Row Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 730
21.15 SNMPv3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
21.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749
22 Security 751
22.1 Code-Execution Intrusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752
22.2 Stack Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
22.3 Heap Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762
22.4 Network Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767
22.5 Cryptographic Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
22.6 Secure Hashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 769
22.7 Shared-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
22.8 Diffie-Hellman-Merkle Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783
22.9 Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786
22.10 SSH and TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
22.11 IPsec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809
22.12 DNSSEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812
22.13 RSA Key Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 821
22.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
23 Bibliography 829
24 Selected Solutions 831
24.1 Solutions for An Overview of Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 831
24.2 Solutions for Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
24.3 Solutions for Other LANs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833
24.4 Solutions for Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834
24.5 Solutions for Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835
24.6 Solutions for Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 836
24.7 Solutions for IPv4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
24.8 Solutions for Routing-Update Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
24.9 Solutions for Large-Scale IP Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 839
24.10 Solutions for UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840
24.11 Solutions for TCP Reno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840
vii
24.12 Solutions for Dynamics of TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840
24.13 Solutions for Mininet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 842
Indices and tables 843
Bibliography 845
Index 853