Syllabus For The Subject Computer Networks

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