An introdution to computer Networks

An Introduction to Computer Networks

Release 1.8.16

Peter L Dordal

December 31, 2015

CONTENTS

0 Preface 3

0.1 Licensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

0.2 Classroom Use . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

0.3 Progress Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

0.4 Technical considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

0.5 Recent Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

0.6 Future Plans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1 An Overview of Networks 9

1.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Data Rate, Throughput and Bandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3 Packets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Datagram Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6 Routing Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.7 Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.8 Packets Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.9 LANs and Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.10 IP - Internet Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.11 DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.12 Transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.13 Firewalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.14 Network Address Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1.15 Some Useful Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

1.16 IETF and OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1.17 Berkeley Unix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.18 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.19 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2 Ethernet 39

2.1 10-Mbps Classic Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.2 100 Mbps (Fast) Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.3 Gigabit Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2.4 Ethernet Switches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.5 Spanning Tree Algorithm and Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.6 Virtual LAN (VLAN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

i

2.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3 Other LANs 65

3.1 Virtual Private Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.2 Carrier Ethernet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.3 Token Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.4 Virtual Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.5 Asynchronous Transfer Mode: ATM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.6 Adventures in Radioland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

3.7 Wi-Fi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3.8 WiMAX and LTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

3.9 Fixed Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

3.10 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

4 Links 103

4.1 Encoding and Framing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.2 Time-Division Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.3 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

5 Packets 115

5.1 Packet Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

5.2 Packet Delay Variability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

5.3 Packet Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.4 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.5 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

6 Abstract Sliding Windows 129

6.1 Building Reliable Transport: Stop-and-Wait . . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.2 Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

6.3 Linear Bottlenecks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6.4 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

7 IP version 4 149

7.1 The IPv4 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

7.2 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

7.3 Special Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

7.4 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

7.5 The Classless IP Delivery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

7.6 IPv4 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

7.7 DNS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

7.8 Address Resolution Protocol: ARP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

7.9 Dynamic Host Configuration Protocol (DHCP) . . . . . . . . . . . . . . . . . . . . . . . . . 170

7.10 Internet Control Message Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

ii

7.11 Unnumbered Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

7.12 Mobile IP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

7.13 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

7.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

8 IP version 6 181

8.1 The IPv6 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

8.2 IPv6 addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

8.3 Network Prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184

8.4 IPv6 Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

8.5 IPv6 Extension Headers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

8.6 Neighbor Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

8.7 IPv6 Host Address Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

8.8 Globally Exposed Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

8.9 ICMPv6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

8.10 IPv6 Subnets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

8.11 Using IPv6 and IPv4 Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

8.12 IPv6 Examples Without a Router . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

8.13 IPv6 Connectivity via Tunneling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

8.14 IPv6-to-IPv4 connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

8.15 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205

8.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

9 Routing-Update Algorithms 207

9.1 Distance-Vector Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 208

9.2 Distance-Vector Slow-Convergence Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 212

9.3 Observations on Minimizing Route Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

9.4 Loop-Free Distance Vector Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

9.5 Link-State Routing-Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

9.6 Routing on Other Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

9.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

9.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

10 Large-Scale IP Routing 229

10.1 Classless Internet Domain Routing: CIDR . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

10.2 Hierarchical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

10.3 Legacy Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

10.4 Provider-Based Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

10.5 Geographical Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

10.6 Border Gateway Protocol, BGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

10.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

10.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

11 UDP Transport 259

11.1 User Datagram Protocol – UDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

11.2 Fundamental Transport Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

11.3 Trivial File Transport Protocol, TFTP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

11.4 Remote Procedure Call (RPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

iii

11.5 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

11.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

12 TCP Transport 285

12.1 The End-to-End Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

12.2 TCP Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

12.3 TCP Connection Establishment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

12.4 TCP and WireShark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

12.5 TCP simplex-talk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293

12.6 TCP state diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

12.7 TCP Old Duplicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

12.8 TIMEWAIT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

12.9 The Three-Way Handshake Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

12.10 Anomalous TCP scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

12.11 TCP Faster Opening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

12.12 Path MTU Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

12.13 TCP Sliding Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

12.14 TCP Delayed ACKs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

12.15 Nagle Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

12.16 TCP Flow Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

12.17 Silly Window Syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

12.18 TCP Timeout and Retransmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

12.19 KeepAlive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

12.20 TCP timers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

12.21 Variants and Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

12.22 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

12.23 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

13 TCP Reno and Congestion Management 319

13.1 Basics of TCP Congestion Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

13.2 Slow Start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

13.3 TCP Tahoe and Fast Retransmit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

13.4 TCP Reno and Fast Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

13.5 TCP NewReno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

13.6 SACK TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

13.7 TCP and Bottleneck Link Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

13.8 Single Packet Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

13.9 TCP Assumptions and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

13.10 TCP Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

13.11 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340

13.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

14 Dynamics of TCP Reno 345

14.1 A First Look At Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345

14.2 Bottleneck Links with Competition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

14.3 TCP Fairness with Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

14.4 Notions of Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

14.5 TCP Reno loss rate versus cwnd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361

iv

14.6 TCP Friendliness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

14.7 AIMD Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

14.8 Active Queue Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367

14.9 The High-Bandwidth TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

14.10 The Lossy-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371

14.11 The Satellite-Link TCP Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371

14.12 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

14.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372

15 Newer TCP Implementations 379

15.1 High-Bandwidth Desiderata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

15.2 RTTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

15.3 Highspeed TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

15.4 TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382

15.5 FAST TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384

15.6 TCP Westwood . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

15.7 TCP Veno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388

15.8 TCP Hybla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389

15.9 TCP Illinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

15.10 H-TCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391

15.11 TCP CUBIC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

15.12 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396

15.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397

16 Network Simulations: ns-2 403

16.1 The ns-2 simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403

16.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405

16.3 Two TCP Senders Competing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417

16.4 TCP Loss Events and Synchronized Losses . . . . . . . . . . . . . . . . . . . . . . . . . . 432

16.5 TCP Reno versus TCP Vegas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443

16.6 Wireless Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

16.7 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

16.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451

17 The ns-3 Network Simulator 455

17.1 Installing and Running ns-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

17.2 A Single TCP Sender . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456

17.3 Wireless . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464

17.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470

18 Queuing and Scheduling 471

18.1 Queuing and Real-Time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

18.2 Traffic Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472

18.3 Priority Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472

18.4 Queuing Disciplines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473

18.5 Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474

18.6 Applications of Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486

18.7 Hierarchical Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487

v

18.8 Hierarchical Weighted Fair Queuing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490

18.9 Token Bucket Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496

18.10 Applications of Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501

18.11 Token Bucket Queue Utilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502

18.12 Hierarchical Token Bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504

18.13 Fair Queuing / Token Bucket combinations . . . . . . . . . . . . . . . . . . . . . . . . . . 506

18.14 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508

18.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508

19 Quality of Service 513

19.1 Net Neutrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

19.2 Where the Wild Queues Are . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514

19.3 Real-time Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515

19.4 Integrated Services / RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

19.5 Global IP Multicast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518

19.6 RSVP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522

19.7 Differentiated Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524

19.8 RED with In and Out . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

19.9 NSIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528

19.10 Comcast Congestion-Management System . . . . . . . . . . . . . . . . . . . . . . . . . . 529

19.11 Real-time Transport Protocol (RTP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530

19.12 Multi-Protocol Label Switching (MPLS) . . . . . . . . . . . . . . . . . . . . . . . . . . . 535

19.13 Epilog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

19.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

20 Network Management and SNMP 539

20.1 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541

20.2 SNMP Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541

20.3 SNMP Naming and OIDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542

20.4 MIBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544

20.5 SNMPv1 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545

20.6 ASN.1 Syntax and SNMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546

20.7 SNMP Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547

20.8 SNMP Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551

20.9 MIB Browsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556

20.10 MIB-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557

20.11 SNMPv1 communities and security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565

20.12 SNMP and ASN.1 Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567

20.13 SNMPv2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569

20.14 Table Row Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580

20.15 SNMPv3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588

20.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597

21 Security 601

21.1 Code-Execution Intrusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602

21.2 Stack Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603

21.3 Heap Buffer Overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612

21.4 Network Intrusion Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617

vi

21.5 Secure Hashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618

21.6 Shared-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620

21.7 Diffie-Hellman-Merkle Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629

21.8 Public-Key Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631

21.9 SSH and TLS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635

21.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645

22 Bibliography 649

23 Selected Solutions 651

Indices and tables 657

Bibliography 659

Index 667

vii

viii

An Introduction to Computer Networks, Release 1.8.16

Peter L Dordal

Department of Computer Science

Loyola University Chicago

Contents:

CONTENTS 1

An Introduction to Computer Networks, Release 1.8.16

2 CONTENTS

0 PREFACE

“No man but a blockhead ever wrote, except for money.” - Samuel Johnson

The textbook world is changing. On the one hand, open source software and creative-commons licensing

have been great successes; on the other hand, unauthorized PDFs of popular textbooks are widely available,

and it is time to consider flowing with rather than fighting the tide. Hence this open textbook, released for

free under the Creative Commons license described below. Mene, mene, tekel pharsin.

Perhaps the last straw, for me, was patent 8195571 for a roundabout method to force students to purchase

textbooks. (A simpler strategy might be to include the price of the book in the course.) At some point,

faculty have to be advocates for their students rather than, well, Hirudinea.

This is not to say that I have anything against for-profit publishing. It is just that this particular book does

not – and will not – belong to that category; the online edition will always be free. In this it is in good

company: there is Wikipedia, there is Gnu/Linux, and there is an increasing number of other free online

textbooks out there. The market inefficiencies of traditional publishing are sobering: the return to authors

of advanced textbooks is at best modest, and costs to users are quite high. (None of this is meant to imply

there will never be a print edition; when I started this project it seemed inconceivable that a print publisher

would ever agree to having the online edition remain free, but times are changing.)

The official book website (potentially subject to change) is intronetworks.cs.luc.edu. The book is available

there as online html, as a zipped archive of html files, in .pdf format, and in other formats as may prove

useful.

0.1 Licensing

This text is released under the Creative Commons license Attribution-NonCommercial-NoDerivs. This text

is like a conventional book, in other words, except that it is free. You may copy the work and distribute it

to others for any noncommercial use, but all reuse requires attribution. Creation of derivative works – eg

modifying chapters or creating additional chapters and distributing them as part of this work – also requires

permission.

The work may not be used for commercial purposes without permission. Permission is likely to be granted

for use and distribution of all or part of the work in for-profit and commercial training programs, provided

there is no direct charge to recipients for the work and provided the free nature of the work is made clear to

recipients (eg by including this preface). However, such permission must always be requested. Alternatively,

participants in commercial programs may be instructed to download the work individually.

The Creative Commons license does not precisely spell out what constitutes “noncommercial” use. The

author considers any sale of this book, even by a non-profit organization and even if the price just covers

expenses, to be commercial use.

3

An Introduction to Computer Networks, Release 1.8.16

0.2 Classroom Use

This book is meant as a serious and more-or-less thorough text for an introductory college or graduate course

in computer networks, carefully researched, with consistent notation and style, and complete with diagrams

and exercises. My intent is to create a text that covers to a reasonable extent why the Internet is the way it is,

to avoid the endless dreary focus on TLA’s (Three-Letter Acronyms), and to remain not too mathematical.

For the last, I have avoided calculus, linear algebra, and, for that matter, quadratic terms (though some

inequalities do sneak in at times). That said, the book includes a large number of back-of-the-envelope

calculations – in settings as concrete as I could make them – illustrating various networking concepts.

Overall, I tried to find a happy medium between practical matters and underlying principles. My goal has

been to create a book that is useful to a broad audience, including those interested in network management,

in high-performance networking, in software development, or just in how the Internet is put together.

One of the best ways to gain insight into why a certain design choice was made is to look at a few alterna￾tive implementations. To that end, this book includes coverage of some topics one may never encounter in

practice, but which may be useful as points of comparision. These topics arguably include ATM (3.5 Asyn￾chronous Transfer Mode: ATM), SCTP (12.21.2 SCTP) and even 10 Mbps Ethernet (2.1 10-Mbps Classic

Ethernet).

The book can also be used as a networks supplement or companion to other resources for a variety of

other courses that overlap to some greater or lesser degree with networking. At Loyola, earlier versions of

this material have been used – coupled with a second textbook – in courses in computer security, network

management, telecommunications, and even introduction-to-computing courses for non-majors. Another

possibility is an alternative or nontraditional presentation of networking itself. It is when used in concert

with other works, in particular, that this book’s being free is of marked advantage.

Finally, I hope the book may also be useful as a reference work. To this end, I have attempted to ensure that

the indexing and cross-referencing is sufficient to support the drop-in reader. Similarly, obscure notation is

kept to a minimum.

Much is sometimes made, in the world of networking textbooks, about top-down versus bottom-up se￾quencing. This book is not really either, although the chapters are mostly numbered in bottom-up fashion.

Instead, the first chapter provides a relatively complete overview of the LAN, IP and transport network layers

(along with a few other things), allowing subsequent chapters to refer to all network layers without forward

reference, and, more importantly, allowing the chapters to be covered in a variety of different orders. As a

practical matter, when I use this text to teach Loyola’s Introduction to Computer Networks course, I cover

the IP/routing and TCP material more or less in parallel.

A distinctive feature of the book is the extensive coverage of TCP: TCP dynamics, newer versions of TCP

such as TCP Cubic, and a chapter on using the ns-2 simulator to explore actual TCP behavior. This has

its roots in a longstanding goal to find better ways to present competition and congestion in the classroom.

Another feature is the detailed chapter on queuing disciplines.

One thing this book makes little attempt to cover in detail is the application layer; the token example in￾cluded is SNMP. While SNMP actually makes a pretty good example of a self-contained application, my

recommendation to instructors who wish to cover more familiar examples is to combine this text with the

appropriate application documentation.

For those interested in using the book for a “traditional” networks course, I with some trepidation offer the

following set of core material. In solidarity with those who prefer alternatives to a bottom-up ordering, I

4 0 Preface

An Introduction to Computer Networks, Release 1.8.16

emphasize that this represents a set and not a sequence.

• 1 An Overview of Networks

• Selected sections from 2 Ethernet, particularly switched Ethernet

• Selected sections from 3.7 Wi-Fi

• Selected sections from 5 Packets

• 6 Abstract Sliding Windows

• 7 IP version 4 and/or 8 IP version 6

• Selected sections from 9 Routing-Update Algorithms and 10 Large-Scale IP Routing

• 11 UDP Transport

• 12 TCP Transport

• 13 TCP Reno and Congestion Management

With some care in the topic-selection details, the above can be covered in one semester along with a survey

of selected important network applications, or the basics of network programming, or the introductory con￾figuration of switches and routers, or coverage of additional material from this book, or some other set of

additional topics. Of course, non-traditional networks courses may focus on a quite different sets of topics.

Peter Dordal

Shabbona, Illinois

0.3 Progress Notes

Edition 1.0 was declared complete as of March 2014; the current edition is 1.8.16.

The intronetworks.cs.luc.edu website carries both edition 1.0 and also the current 1.8.16 edition.

My plan is to make sure, as far as is possible, that all editions are classroom-compatible: existing exercises

will not be renumbered, and section renumbering will be avoided to the extent practical. New exercises are

regularly inserted, but with fractional numbers. Existing integral exercise numbers are sometimes given a

trailing .0, to reduce confusion between exercise 12.0, say, and 12.5.

As of December 2014 chapters on network management and security have been added; this completes the

set of chapters originally envisioned.

At this point I am actively seeking reviewers – either for style or for technical accuracy.

0.3 Progress Notes 5