Syllabus For The Subject Networks

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

DMCA.com Protection Status