-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathece358.html
More file actions
2137 lines (2137 loc) · 114 KB
/
ece358.html
File metadata and controls
2137 lines (2137 loc) · 114 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>ece358</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<link rel="stylesheet" href="../pandoc.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js"></script>
<script>document.addEventListener("DOMContentLoaded", function () {
var mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") { katex.render(texText.data, mathElements[i], { displayMode: mathElements[i].classList.contains("display"), throwOnError: false } );
}}});</script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="ece-358">ECE 358</h1>
<h1 id="introduction">1: Introduction</h1>
<h2 id="what-is-the-internet">1.1 What <em>is</em> the Internet?</h2>
<p>Millions of connected computing devices.</p>
<ul>
<li><strong>Hosts</strong> = <strong>End systems</strong>.</li>
<li>Running <strong>network apps</strong>.</li>
</ul>
<p><strong>Protocols</strong> define <strong>format</strong>, <strong>order</strong> of messages sent and received among network entities, and <strong>actions taken</strong> on message transmission, receipt.</p>
<h2 id="network-structure">1.2 Network Structure</h2>
<ul>
<li><p><strong>Network Edge</strong>: Hosts (clients and servers). Servers are often in data centers.</p></li>
<li><p><strong>Access Networks, Physical Media</strong>: Wired, wireless communication links.</p></li>
<li><p><strong>Network Core</strong>: Interconnected routers, a network of networks.</p></li>
</ul>
<h3 id="wired-access-networks">Wired Access Networks</h3>
<blockquote>
<p>Shared <em>wireless</em> access network connects end systems to router via a base station (<em>access point</em>).</p>
</blockquote>
<p><strong>Wireless LANs</strong>: Within building (100ft), 802.11 b/g (WiFi), 11 / 54 Mbps transmission rate.</p>
<p><strong>Wide-Area Wireless Access</strong>: Provided by telco (cellular) operator. 1-10 Mbps transmission rate.</p>
<p>Hosts break application message into smaller chunks known as <strong>packets</strong>, of length <span class="math inline">L</span> bits. Packets are transmitted across the network at a transmission rate <span class="math inline">T</span>. The transmission delay is then <span class="math inline">\frac{L}{R}</span>.</p>
<h3 id="physical-media">1.3 Physical Media</h3>
<ul>
<li><strong>Bit</strong>: propagates between transmitter / receiver pairs.</li>
<li><strong>Physical Link</strong>: What lies between the transmitter and receiver.</li>
<li><strong>Guided Media</strong>: Signals propagate in solid media (copper, fiber, coax).
<ul>
<li><strong>Coaxial Cable</strong>: Two concentric copper conductors. Bidirectional. Broadband (multiple channels on cable).</li>
<li><strong>Fiber Optic Cable</strong>: Glass fiber carrying light pulses, each pulse is a bit. High speed point-to-point transmission. Low error rate because repeaters are spaced far apart, and they are immune to electromagnetic noise.</li>
</ul></li>
<li><strong>Unguided Media</strong>: Signals propagate freely (radio).
<ul>
<li><strong>Radio</strong>: Signal carried in electromagnetic spectrum. Propagation environment effects (reflection, obstruction, interference).</li>
</ul></li>
<li><strong>Twisted Pair (<em>TP</em>)</strong>: Two insulated copper wires.</li>
</ul>
<h3 id="network-core">1.4 Network Core</h3>
<blockquote>
<p>Mesh of interconnected routers.</p>
</blockquote>
<h3 id="packet-switching">Packet Switching</h3>
<p>Hosts break application-layer messages into <strong>packets</strong>. Packets are forwarded from one router to the next, across links on a path from source to destination.</p>
<ul>
<li><strong>Store and forward</strong>: Entire packet must arrive at router before it can be transmitted to the next link.</li>
<li><strong>End-end delay</strong>: <span class="math inline">\frac{2L}{R}</span> assuming zero propagation delay.</li>
<li><strong>Queuing and Loss</strong>: If the arrival rate to the link exceeds the transmission rate of the link, packets can be dropped if memory (buffer) fills up.</li>
</ul>
<p>The two key network core functions are <strong>routing</strong> and <strong>forwarding</strong>.</p>
<h4 id="circuit-switching">Circuit Switching</h4>
<ul>
<li>Instead of breaking up packets into smaller messages, divide the end-end resources and assign to “calls” between source and destination.</li>
<li>Circuit segment is idle if it is not used in a call.</li>
<li>Dedicated resources allow for circuit-link (guaranteed) performance.</li>
<li>Commonly used in traditional telephone networks.</li>
</ul>
<h4 id="packet-switching-vs.circuit-switching">Packet Switching vs. Circuit Switching</h4>
<blockquote>
<p>Packet switching allows for more users to use the network.</p>
</blockquote>
<ul>
<li>Great for “bursty” data. There is no call setup, and resources are shared.</li>
<li><strong>Excessive congestion</strong> is possible which could lead to packet delay and loss. There is a need for protocols (reliable data transfer, congestion control).</li>
<li>Bandwidth guarantees are needed for audio / video applications.</li>
</ul>
<h2 id="loss-and-delay-in-networks">1.4 Loss and Delay in Networks</h2>
<blockquote>
<p>Four sources of packet delays.</p>
</blockquote>
<ol type="1">
<li><strong>Nodal Processing</strong>: Checking bit errors, determining the output link. Usually < 1ms.</li>
<li><strong>Queueing Delay</strong>: Time waiting at output link for transmission. Depends on the level of congestion at the router.</li>
<li><strong>Transmission Delay</strong>: <span class="math inline">\frac{L}{R}</span>, where <span class="math inline">L</span> is the packet length and <span class="math inline">R</span> is the link bandwidth.</li>
<li><strong>Propagation Delay</strong>: <span class="math inline">\frac{d}{s}</span> where <span class="math inline">d</span> is the length of the physical link and <span class="math inline">s</span> is the propagation speed in the medium.</li>
</ol>
<p><strong>Throughput</strong>: Rate at which bits are transferred between the sender and receiver.</p>
<h2 id="internet-protocol-stack">Internet protocol stack</h2>
<p><strong>Application</strong>: Running the network applications that you want (HTTP, FTP, SMTP). Implemented using software only.<br />
<strong>Transport</strong>: Responsible for communication of processes between layers (TCP, UDP). Mainly implemented using software.<br />
<strong>Network</strong>: Responsible for routing from source to destination. Implemented using software and hardware.<br />
<strong>Link</strong>: Transferring to data between physically connected (adjacent) hubs (e.g. Computer -> Router, Router -> Router …). Hardware.<br />
<strong>Physical</strong>: How you are transferring physical bits on the wire. Not covered in this course.</p>
<blockquote>
<p>Before the internet, there were two extra section that were planned.</p>
</blockquote>
<p><strong>Presentation</strong>: Applications to interpret meaning of data (e.g. encryption, compression, etc.).<br />
<strong>Session</strong>: Synchronization, checkpointing.</p>
<p>If you want these features, it must be implemented in the application layer.</p>
<h3 id="encapsulation">Encapsulation</h3>
<p><strong>Switch</strong>: Link and physical layers. <strong>Router</strong>: Network, link, and physical layers.</p>
<p>Information is added from the above layer to the lower.</p>
<blockquote>
<p><strong>Transport</strong>: Segment<br />
<strong>Network Layer</strong>: Datagram<br />
<strong>Link Layer</strong>: Frame</p>
</blockquote>
<p>When passing data through, you need to pop the stack (<strong>decapsulation</strong>) and then replace (<strong>encapsulation</strong>).</p>
<h2 id="network-security">Network Security</h2>
<p>Internet was not designed with security in mind. How can bad guys attack and how can we defend? How can we design architectures that are immune to attacks.</p>
<p>In real life: Hackers hack your system and then you fix the error and catch up.</p>
<p><strong>Malware</strong> any harmful software.</p>
<blockquote>
<p><strong>Virus</strong>: Interaction required.<br />
<strong>Worm</strong>: Weakness in application you are already running.<br />
<strong>Spyware</strong>: Record keystrokes, web sites, etc.</p>
</blockquote>
<p>Infected hosts can be enrolled in <strong>botnet</strong> to help in future attacks.</p>
<h3 id="examples-of-attacks">Examples of Attacks</h3>
<p><strong>Denial of Service (DoS)</strong>: Attackers infect local computers with a worm in order to all send messages to the target at the same time. Target will be busy services request so they cannot service normal customers.</p>
<p><strong>Packet “sniffing”</strong>: Passive program that is on the link which listens to and records packets.</p>
<p><strong>IP spoofing</strong>: Send a message with a false source address.</p>
<p><strong>Routers</strong>: Implements the bottom 3 layers (network, data link, physical).</p>
<p><strong>Switches</strong>: Implements the bottom 2 layers (data link, physical).</p>
<h1 id="application-layer">2: Application Layer</h1>
<h2 id="principles-of-network-applications">2.1: Principles of network applications</h2>
<h3 id="creating-a-network-app">Creating a network app</h3>
<p>Only write to run on end systems (not on the internal network). Does not matter if they are servers or clients. We also only care about what we want to do on the application layer and then push to the transport layer which will take care of transmitting the data. This allows for fast development.</p>
<p><strong>Client-Server</strong>: Server is always on with a static IP. Client will communicate with servers (intermittent). Client IP addresses will be dynamic.</p>
<p><strong>P2P</strong>: Arbitrary end systems directly communicate. Peers request service from other peers and provide service in return (<em>self scalability</em>). There is more complex management because there is no central network that controls all uses. Security is also a big issue.</p>
<h3 id="process-communication">Process Communication</h3>
<p><strong>Process</strong>: program running within a host.</p>
<ul>
<li>Within same host, two process communication using <em>inter-process communication</em> defined by the OS.</li>
<li>Processes in different hosts communicate by exchanging messages.</li>
</ul>
<p><strong>Client process</strong>: Process that initiates communication.</p>
<p><strong>Server process</strong>: Process that waits to be contacted.</p>
<h3 id="sockets">Sockets</h3>
<blockquote>
<p>Process sends / recieves messages to / from it’s <strong>socket</strong>.</p>
</blockquote>
<p><strong>Socket</strong>: The gate between the application layer and the transport layer. Sockets are similar to doors. Sending process shoves message out of door and relies on the other side of the door to deliver message to the socket at the receiving process.</p>
<p>Example: Chrome tabs. How do we know which tab to put data? There is an identifier for each socket to route the data to the correct tab (You will always talk to port 80 of a server for HTTP requests but you will use a random port).</p>
<p><strong>Sockets</strong> consists of two parts (for now).</p>
<ol type="1">
<li>Address of host.</li>
<li>Port number.</li>
</ol>
<p>The combination of the two parts will create a <strong>unique identifier</strong> for the socket. Each process has it’s own unique socket (there are over 65k ports).</p>
<h3 id="application-layer-protocol-defines">Application Layer Protocol Defines …</h3>
<blockquote>
<p><strong>Rules</strong> for when and how process send and respond to messages.</p>
</blockquote>
<p><strong>Types of messages exchanged</strong>: Request, response.</p>
<p><strong>Message syntax</strong>: What does each field mean and how fields are delineated.</p>
<p><strong>Message semantics</strong>: What do you want the information in the fields to mean.</p>
<p>Examples of open protocols are <strong>HTTP</strong> and <strong>DNS</strong> which are defined in RFCs (<em>Request For Comments</em> is a formal document from the Internet Engineering Task Force). An example of a proprietary protocol is <strong>Skype</strong>.</p>
<h3 id="what-transport-services-does-an-application-need">What Transport Services Does an Application Need?</h3>
<blockquote>
<p>Will be implemented at the application level.</p>
</blockquote>
<ol type="1">
<li><strong>Data Integrity</strong>. Some applications require 100% data transfer whereas other applications (e.g. audio) can tolerate some loss.</li>
<li><strong>Timing</strong>. Time sensitive applications (e.g. Internet telephone, interactive games) require low delay to be <em>effective</em>.</li>
<li><strong>Throughput</strong> (How fast the data can be transferred). Some applications require a minimum amount to be <em>effective</em>.</li>
<li><strong>Security</strong>. Encryption.</li>
</ol>
<table>
<thead>
<tr class="header">
<th>Application</th>
<th>Data Loss</th>
<th>Throughput</th>
<th>Time Sensitive</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>File Transfer</td>
<td>No</td>
<td>Elastic</td>
<td>No</td>
</tr>
<tr class="even">
<td>E-Mail</td>
<td>No</td>
<td>Elastic</td>
<td>No</td>
</tr>
<tr class="odd">
<td>Web Documents</td>
<td>No</td>
<td>Elastic</td>
<td>No</td>
</tr>
<tr class="even">
<td>Real-Time AV</td>
<td>Tolerant</td>
<td>Minimum requirements</td>
<td>Yes, 100’s ms</td>
</tr>
<tr class="odd">
<td>Stored AV</td>
<td>Tolerance</td>
<td>Minimum requirements</td>
<td>Yes, few seconds</td>
</tr>
<tr class="even">
<td>Interactive Games</td>
<td>Tolerant</td>
<td>Minimum requirements</td>
<td>Yes, 100’s ms</td>
</tr>
<tr class="odd">
<td>Text Messaging</td>
<td>No</td>
<td>Elastic</td>
<td>Yes and No</td>
</tr>
</tbody>
</table>
<h3 id="internet-transport-protocol-services">Internet transport protocol services</h3>
<blockquote>
<p>What is offered by the transport layer? Which protocol should I Use? There are two main protocols …</p>
</blockquote>
<ol type="1">
<li><strong>TCP</strong> (<em>Transport Control Protocol</em>)
<ul>
<li><strong>Reliable transport</strong> between sending and receiving process. Everything will get there without errors and in order.</li>
<li><strong>Flow control</strong>: Sender won’t overwhelm receiver.</li>
<li><strong>Congestion control</strong>: Throttle sender when network is overloaded.</li>
<li><strong>Does not provide</strong>: Timing, minimum throughput guarantee, security.</li>
<li><strong>Connection-oriented</strong>: Setup required between client and server processes.</li>
</ul></li>
<li><strong>UDP</strong> (<em>User Datagram Protocol</em>)
<ul>
<li><strong>Unreliable data transfer</strong>: No data integrity or reliability between sending and receiving process.</li>
<li><strong>Does not provide</strong>: Reliability, flow control, congestion control, timing, throughput guarantee, security, or connection setup.</li>
</ul></li>
</ol>
<p>Why bother with UDP?</p>
<ul>
<li><strong>UDP</strong> is faster than <strong>TCP</strong>. There is no connection setup.</li>
<li>There are no <strong>overhead</strong> bits required.</li>
</ul>
<table>
<thead>
<tr class="header">
<th>Application</th>
<th>Application Protocol</th>
<th>Transport Protocol</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>Email</td>
<td>SMTP</td>
<td>TCP</td>
</tr>
<tr class="even">
<td>Remote Terminal Access</td>
<td>Telnet</td>
<td>TCP</td>
</tr>
<tr class="odd">
<td>Web</td>
<td>HTTP</td>
<td>TCP</td>
</tr>
<tr class="even">
<td>File Transfer</td>
<td>FTP</td>
<td>TCP</td>
</tr>
<tr class="odd">
<td>Streaming Multimedia</td>
<td>HTTP, RTP</td>
<td>TCP or UDP (Usually UDP)</td>
</tr>
<tr class="even">
<td>Internet Telephone</td>
<td>SIP, RTP</td>
<td>TCP or UDP</td>
</tr>
</tbody>
</table>
<h3 id="securing-tcp">Securing TCP</h3>
<p><strong>TCP</strong> and <strong>UDP</strong> have no encryption. Plaintext passwords send into sockets.</p>
<p>If you want security, you can use <strong>SSL</strong> (<em>secury socket layer</em>) which provides encryption for <strong>TCP</strong> connection. <strong>SSL</strong> is used at the application layer (need to use a <strong>SSL</strong> library such as OpenSSL).</p>
<h2 id="web-and-http">2.2: Web and HTTP</h2>
<blockquote>
<p>A <em>web page</em> consists of <em>objects</em>. (HTML, JPEG, Java applet, auto file, …).</p>
</blockquote>
<ul>
<li>Web page consists of <strong>base HTML-file</strong> which includes several referenced objects.</li>
<li>Each object is addressable by a <strong>URL</strong> (Uniform Resource Locator).</li>
</ul>
<p><strong>HTTP</strong> (hypertext transfer protocol): We have a client / server model. The client sends requests to the server and the server replies with an HTTP request.</p>
<ol type="1">
<li>HTTP uses TCP. The client initiates TCP connection (creates socket) to server, port 80. (A random port is used on the client side).</li>
<li>Server accepts TCP connection from client.</li>
<li>HTTP messages (application-layer protocol messages) exchanged between browser (HTTP client) and Web server (HTTP server).</li>
<li>TCP connection closed.</li>
</ol>
<p><em>HTTP is “stateless”</em>. The server maintains no information about past client requests.</p>
<blockquote>
<p>Protocols that maintain “state” are complex. Past history must be maintained and if the client / server crashes, their views of the “state” may be inconsistent.</p>
</blockquote>
<h3 id="types-of-http-connections">Types of HTTP Connections</h3>
<ol type="1">
<li><strong>Non-Persistent HTTP</strong>
<ul>
<li>At most one object sent over TCP connection.</li>
<li>Downloading multiple objects requires multiple connections.</li>
<li>Server is free more frequently to server other users.</li>
</ul></li>
<li><strong>Persistent HTTP</strong>
<ul>
<li>Multiple objects sent over a single TCP connection.</li>
<li>Avoid excessive overhead when requesting multiple objects.</li>
</ul></li>
</ol>
<h3 id="response-time">Response Time</h3>
<p><strong>RTT</strong> (<em>Round Trip Time</em>): Time it takes a small packet to travel from client to server and back.</p>
<p><strong>HTTP Response Time</strong></p>
<ul>
<li>One RTT to initiate TCP</li>
<li>One RTT for HTTP request and first few bytes of HTTP response in return.</li>
<li>File transmission time (<em>transmission delay</em>).</li>
</ul>
<blockquote>
<p>Non-Persistent HTTP Response Time = 2RTT + transmission time.<br />
Persistent HTTP Response Time = RTT + n(RTT + transmission time).</p>
</blockquote>
<p>For non-persistent HTTP, we require 2 RTT per object. There is OS overhead for <em>each</em> TCP connection. Browsers often open parallel TCP connections to fetch referenced objects.</p>
<p>For persistent HTTP, subsequent HTTP messages between client / server will be over the same connection so the client will sent requests as soon as it encounters a referenced object. There is as little as on RTT per referenced object.</p>
<h3 id="http-request">HTTP Request</h3>
<p><img src="https://i.imgur.com/loyZ7qQ.png" /></p>
<ul>
<li>Request Line (method URL version).</li>
<li>Header Lines (header_field_name value).</li>
</ul>
<h3 id="http1.0">HTTP/1.0</h3>
<ul>
<li>GET (request data).</li>
<li>POST (send data).</li>
<li>HEAD (leave requested object out of response).</li>
</ul>
<h3 id="http1.1">HTTP/1.1</h3>
<ul>
<li>PUT (uploads file in entry to path specified in URL).</li>
<li>DELETE (delete files specified in URL).</li>
</ul>
<h3 id="http-response">HTTP Response</h3>
<p><img src="https://i.imgur.com/gvVkbUt.png" /></p>
<ul>
<li>Status Line (protocol status_code status_phrase).</li>
<li>Header Lines (content_length).</li>
<li>Data Requested (e.g. HTML file).</li>
</ul>
<h3 id="cookies">Cookies</h3>
<blockquote>
<p>Used to identify users. ID is stored in client side which is sent in the header of subsequent messages.</p>
</blockquote>
<ol type="1">
<li>Cookie header line in HTTP <em>response</em> from server.</li>
<li>Cookie header line in next HTTP <em>request</em> from client.</li>
<li>Cookie file kept client-side.</li>
<li>Back-end database for server.</li>
</ol>
<p>Cookies are used to keep <strong>state</strong>.</p>
<h3 id="web-caches-proxy-server">Web Caches (Proxy Server)</h3>
<blockquote>
<p>Satisfy client request without involving the original server.</p>
</blockquote>
<p>All requests are sent through a proxy server instead which caches requests and responses. If the request is already cached, it does not have to travel all the way to the original server.</p>
<ul>
<li>Typically the cache is installed by ISP.</li>
</ul>
<p>Example:</p>
<blockquote>
<p>Average object size: <span class="math inline">100\ K bits</span>.<br />
Average request rate: <span class="math inline">15\ /\ sec</span>.<br />
RTT from institutional router to original server: <span class="math inline">2\ sec</span><br />
Access link rate: <span class="math inline">1.54\ Mbps</span></p>
<p>We then have LAN utilization: <span class="math inline">\frac{1.5\ Mbps}{1\ Gbps} = 0.15\%</span><br />
Access link utilization: <span class="math inline">\frac{1.5\ Mbps}{1.54\ Mbps} = 97.4\%</span><br />
Total Delay = Internet Delay + Access Delay + LAN Delay<br />
Access Delay: <span class="math inline">\frac{100\ K}{(1 - 0.974)1.54\ Mbps}</span>. (New users can only use whatever is left of the access link).<br />
LAN Delay: <span class="math inline">\frac{100\ K}{(1 - 0.0015)1\ Gbps}</span><br />
Total Delay <span class="math inline">= 2 + 2.5 + 0.0001</span></p>
</blockquote>
<p>Solutions:</p>
<ol type="1">
<li><p>Get a faster access link. If the access link rate was increased to <span class="math inline">154\ Mbps</span>, the access link delay drops to <span class="math inline">0.0007</span> so the total delay is only <span class="math inline">2</span> sec.</p></li>
<li><p>Caching. If the cache hit rate was 0.4, 40% of requests are satisfied at the cache. The data rate to browsers over the access link is <span class="math inline">0.6 \cdot 1.50\ Mbps = 0.9\ Mbps</span>. Utilization becomes <span class="math inline">0.58</span>. Total Delay <span class="math inline">= 0.6 \cdot</span>(delay from original servers) + <span class="math inline">0.4 \cdot</span>(delay when satisfied by the cache) <span class="math inline">= 0.6(2.15) = 1.29\ sec</span>.</p></li>
</ol>
<p><strong>Conditional GET</strong> - If the cache has an up-to-date version, don’t send the object. - The web server sends a conditional get with the <em>If-modified-since</em>. - Response code <strong>304 Not Modified</strong> if the cached version is fine. - Response code <strong>200 OK</strong> will send the updated data.</p>
<h2 id="dns">2.3: DNS</h2>
<blockquote>
<p>Domain Name System.</p>
</blockquote>
<p>Internet uses 32-bit IP address to identify hosts connected to the internet. The public cannot remember the real address so we use easy to remember names.</p>
<ul>
<li><strong>Distributed Database</strong>: Implemented in hierarchy of many <em>name servers</em></li>
<li>Main function is to resolve names into addresses (IP address).</li>
</ul>
<blockquote>
<p>For complex objects, we push complexity to the edge (host systems).</p>
</blockquote>
<h3 id="dns-services">DNS Services</h3>
<ul>
<li>Hostname to IP address translation.</li>
<li>Host aliasing.</li>
<li>Mail server aliasing.</li>
<li>Load distribution.
<ul>
<li>Many IP addresses correspond to the same name.</li>
</ul></li>
</ul>
<h3 id="why-not-centralize-dns">Why Not Centralize DNS?</h3>
<blockquote>
<p>Not scalable.</p>
</blockquote>
<ul>
<li>Single point of failure.</li>
<li>Traffic volume.</li>
<li>Distant centralized database.</li>
<li>Maintenance.</li>
</ul>
<h3 id="hierarchy">Hierarchy</h3>
<ul>
<li>Bottom Tier: amazon.com, umass.edu.</li>
<li>Middle Tier: com DNS servers, edu DNS servers.</li>
<li>Top Tier: Root DNS servers.</li>
</ul>
<p>If the client wants the IP for www.amazon.com.</p>
<blockquote>
<ol type="1">
<li>Queries root domain server to find com DNS server.</li>
<li>Queries .com DNS server to get amazon.com DNS server.</li>
<li>Queries amazon.com DNS server to get IP address for www.amazon.com.</li>
</ol>
</blockquote>
<h3 id="tld-servers">TLD Servers</h3>
<ul>
<li>Responsible for com, org, etc.</li>
<li>Network Solutions maintains servers for .com TLD</li>
<li>Educause for .edu TLD</li>
</ul>
<h3 id="authoritative-dns-servers">Authoritative DNS Servers</h3>
<ul>
<li>Organization’s own DNS server(s), providing authoritative hostname to IP mappings for organization.</li>
</ul>
<h3 id="local-dns-name-server">Local DNS Name Server</h3>
<ul>
<li>Each ISP has one, acts as a proxy and forwards query to hierarchy.</li>
</ul>
<p>If the host at cis.poly.edu wants IP address for gaia.cs.umass.edu.</p>
<blockquote>
<p><strong>Iterated Query</strong>: - Contacted server replies with name of server to contact. - “I don’t know this name, but ask this server”.</p>
<p><strong>Recursive Query</strong>: - Puts burden of name resolution on contacted name server. - Heavy load at upper levels of hierarchy?</p>
</blockquote>
<p>Once (any) name server learns the mapping, it <strong>caches</strong> mapping.</p>
<ul>
<li>Cache entries timeout after some time (TTL).</li>
<li>TLD servers typically cached in local name servers.</li>
<li>Cached entries may be <em>out-of-date</em> until everyone’s TTLs expire.</li>
</ul>
<h3 id="dns-records">DNS Records</h3>
<blockquote>
<p>Distributed database storing resource records (RR).</p>
</blockquote>
<p><strong>RR Format: (Name, Value, Type, TTL).</strong></p>
<ul>
<li>type = A.
<ul>
<li><strong>name</strong> is hostname.</li>
<li><strong>value</strong> is IP address.</li>
<li>(www.amazon.com, 220.180.90.10, A, TTL).</li>
</ul></li>
<li>type = NS.
<ul>
<li><strong>name</strong> is domain (e.g. foo.com).</li>
<li><strong>value</strong> is hostname of authorative name server for this domain.</li>
<li>(uwaterloo.ca, dns.uwaterloo.ca, NS, TTL).</li>
</ul></li>
<li>type = CNAME.
<ul>
<li><strong>name</strong> is alias name for some “canonical” (the real) name.</li>
<li><strong>value</strong> is canonical name.</li>
<li>(www.ibm.com, servereast.backup2.ibm.com, CNAME, TTL).</li>
</ul></li>
<li>type = MX.
<ul>
<li><strong>value</strong> is the name fo mailserver associated with <strong>name</strong>.</li>
</ul></li>
</ul>
<h3 id="dns-protocol-messages">DNS Protocol, Messages</h3>
<blockquote>
<p><em>Query</em> and <em>reply</em> messages have the same <em>message format</em>.</p>
</blockquote>
<p><strong>msg Header</strong>:</p>
<blockquote>
<p>Chapter 2 slides have a better visualization for format.</p>
</blockquote>
<ul>
<li><strong>Identification</strong> (<em>2 bytes</em>)16 bit number for query, reply to user uses the same number.</li>
<li><strong>Flags</strong> (<em>2 bytes</em>):
<ul>
<li>Query or reply.</li>
<li>Recursion desired.</li>
<li>Recursion available.</li>
<li>Reply is authoritative.</li>
</ul></li>
<li><strong>Questions</strong>: Name, type fields for a query.</li>
<li><strong>Answers</strong>: RRs in response to a query.</li>
<li><strong>Authority</strong>: Records for authoritative servers.</li>
<li><strong>Additional Info</strong>: Additional “helpful” info that may be used.</li>
</ul>
<h3 id="attacking-dns">Attacking DNS</h3>
<ol type="1">
<li>DDoS Attacks.
<ul>
<li>Bombard root servers with traffic.
<ul>
<li>Not successful to date.</li>
<li>Traffic filtering (not all traffic provided to root servers).</li>
<li>Local DNS servers cache IPs of TLD servers, allow the root server to be bypassed.</li>
</ul></li>
<li>Bombard TLD servers.
<ul>
<li>Potentially more dangerous.</li>
</ul></li>
</ul></li>
<li>Redirect Attacks.
<ul>
<li>Man-in-middle.
<ul>
<li>Attacker intercepts query and returns a <em>modified</em> response. They can redirect you to their own websites.</li>
</ul></li>
<li>DNS poisoning.
<ul>
<li>Inserts an incorrect record to the DNS server.</li>
</ul></li>
</ul></li>
<li>Exploit DNS for DDoS.
<ul>
<li>Use already existing DNS to attack.</li>
<li>Send a DNS query and claim it is from the victim.
<ul>
<li>The victim is busy processing all of the responses.</li>
</ul></li>
<li>Requires amplification (difficult to launch because you need to query many servers at the same time).</li>
</ul></li>
</ol>
<h1 id="transport-layer">3: Transport Layer</h1>
<h2 id="transport-layer-services">3.1: Transport-Layer Services</h2>
<ul>
<li>Provides <strong>logical communication</strong> between a process on the source to a process on the receiver.</li>
<li>Transport protocols run in end systems.
<ul>
<li>Source side: breaks app messages into <em>segments</em>, passes into network layer.</li>
<li>Receiving side: Reassembles segments into <em>messages</em>, passes to the application layer.</li>
</ul></li>
<li>More than one transport protocol available to apps.
<ul>
<li>Internet: TCP and UDP.</li>
</ul></li>
</ul>
<h3 id="transport-layer-vs.network-layer">Transport Layer vs. Network Layer</h3>
<ul>
<li><strong>Network layer</strong>: Logical communication between hosts.</li>
<li><strong>Transport layer</strong>: Logical communication between processes.
<ul>
<li>Relies on enhanced network layer services.</li>
</ul></li>
</ul>
<p><strong>Household Analogy</strong></p>
<blockquote>
<p>12 kids in Ann’s house sending letters to 12 kids in Bill’s house. - <strong>hosts</strong>: houses. - <strong>processes</strong>: kids. - <strong>app messages</strong>: letters in envelopes. - <strong>transport protocol</strong>: Ann and Bill who demux to in-house siblings. - <strong>network protocol</strong>: postal service.</p>
</blockquote>
<h3 id="internet-transport-layer-protocols">Internet Transport-Layer Protocols</h3>
<ul>
<li>Reliable, in-order delivery (TCP).
<ul>
<li>Congestion control (about the network itself).</li>
<li>Flow control (sender will not overflow the receiver).</li>
<li>Connection setup.</li>
</ul></li>
<li>Unreliable, unordered delivery (UDP).
<ul>
<li>No-frills extension of <em>best-effort</em> IP.</li>
</ul></li>
<li>Services not available are <strong>delay guarantees</strong> and <strong>bandwidth guarantees</strong>.</li>
</ul>
<h2 id="multiplexing-demultiplexing">3.2: Multiplexing / Demultiplexing</h2>
<p><strong>Multiplexing at sender</strong>: Handle data from multiple sockets, add transport header (later used for demultiplexing).</p>
<p><strong>Demultiplexing at receiver</strong>: Use header info to deliver received segments to the correct socket.</p>
<h3 id="how-demultiplexing-works">How Demultiplexing Works</h3>
<ul>
<li>Host receives IP datagrams.
<ul>
<li>Datagram has a source IP address, destination IP address.</li>
<li>Datagram carries one transport-layer segment.</li>
<li>Segment has source, destination port number.</li>
</ul></li>
<li>Host uses <em>IP addresses</em> and <em>port numbers</em> to direct segment to appropriate socket.</li>
</ul>
<h3 id="connectionless-demultiplexing">Connectionless Demultiplexing</h3>
<ul>
<li>When creating a datagram to send into UDP socket, we must specify the destination IP address and port number.</li>
<li>When a host receives a UDP segment, it checks the destination port number and directs the segment to the proper socket.</li>
<li>If IP datagram shave the same destination port but different source IP addresses or source port, numbers will be directed to the <strong>same socket</strong> at the destination.</li>
</ul>
<h3 id="connection-oriented-demux">Connection-oriented Demux</h3>
<ul>
<li>TCP socket identified by a 4 tuple: (source IP address, source port number, destination IP address, destination port number).</li>
<li>Web servers have different sockets for each connecting client.
<ul>
<li>Non-persistent HTTP will have a different socket for each request. Multiple segments will be sent to the host at port 80 but will be demultiplexed to different sockets.</li>
</ul></li>
</ul>
<h2 id="connectionless-transport-udp">3.3 Connectionless Transport: UDP</h2>
<blockquote>
<p>When we want the speed to be as fast as possible and we are loss tolerant.</p>
</blockquote>
<ul>
<li>“No frills”, “bare bones” Internet transport protocol.</li>
<li>“Best effort” service, UDP segments may be lost or delivered out-of-order to app.</li>
<li><strong>Connectionless</strong> meaning that there is no handshaking between UDP sender and receiver. Each UDP segment is handled independently of others.</li>
<li>UDP is used in streaming multimedia apps, DNS, SNPM (Simple Network Management Protocol).</li>
<li>Reliable transfer over UDP can be achieved by adding reliability at the application layer such as application-specific error recovery.</li>
</ul>
<p>UDP adds a segment header of 64 bits. The first 32 are used for the source port number and the destination port number. The next 16 are used for the length in bytes of the segment (including header), and the final 16 are used for <strong>checksum</strong>.</p>
<h3 id="udp-checksum">UDP Checksum</h3>
<blockquote>
<p>We want to detect “errors” (e.g. flipped bits) in transmitted segmet.</p>
</blockquote>
<p>The sender treats the segment’s contents as a sequence of 16-bit integers. The checksum is the addition (one’s complement sum) of segment contents. The receiver then computes their own checksum and compares. (When adding numbers, a carryout from the msb gets re-added to the result).</p>
<h2 id="principles-of-reliable-data-transfer">3.4 Principles of Reliable Data Transfer</h2>
<ul>
<li>When we have a reliable channel, we do not have to worry about reliable data transfer.</li>
<li>Characteristics of unreliable channels will determine the complexity of reliable data transfer protocol (rdt).</li>
</ul>
<p>rdt_send() is called from the application layer whenever we have data to send which passes udt_send() to transfer the packet over the unreliable channel to receiver. It is received by rdt_rcv() which gets passed to the protocol on the transport layer. After some processing, it is passed to the upper application layer through deliver_data().</p>
<h3 id="rdt-1.0-reliable-transfer-over-a-reliable-channel.">RDT 1.0: Reliable transfer over a reliable channel.</h3>
<blockquote>
<p>Underlying channel is perfectly reliable. There are no bit errors and no loss of packets.</p>
</blockquote>
<p>We have separate Finite State Machines (FSMs) for sender, receiver. The sender sends data into the underlying channel and the receiver reads data from the underlying channel.</p>
<h3 id="rdt-2.0-channel-with-bit-errors">RDT 2.0: Channel with Bit Errors</h3>
<blockquote>
<p>Underlying channel may flip bits in packet which is detected by the checksum.</p>
</blockquote>
<ul>
<li><strong>ACKs</strong> (<em>acknowledgements</em>): The receiver explicitly tells sender that the packet was received ok.</li>
<li><strong>NAKs</strong> (<em>negative acknowledgements</em>): The receiver explicitly tells sender that the packet has errors.
<ul>
<li>Sender retransmits packet on receipt of NAK.</li>
</ul></li>
<li>The sender needs to add a checksum to the data and will wait for ACK or NAK.</li>
<li>There is a <strong>fatal flaw</strong> because if ACK / NAK is corrupted, the sender does not know what happened at the receiver.</li>
</ul>
<h4 id="rdt-2.1">RDT 2.1</h4>
<ul>
<li>The sender retransmits the current packet if ACK / NAK is corrupted and adds a <em>sequence number</em> to each packet.
<ul>
<li>We only need 2 sequence numbers (0, 1) so that we can distinguish between consecutive messages.</li>
</ul></li>
<li>The receiver discards duplicate packets.</li>
</ul>
<blockquote>
<p><strong>Stop and Wait</strong> protocol: sender sends 1 packet and then waits for receiver response.</p>
</blockquote>
<h4 id="rdt-2.2-nak-free">RDT 2.2: NAK-free</h4>
<ul>
<li>We can have less state transitions if we only use ACKs.</li>
<li>The receiver can send a packet number as well.</li>
<li>Duplicate ACK at sender results in the same action as NAK: <em>retransmit the current packet</em>.</li>
</ul>
<h3 id="rdt-3.0-channels-with-errors-and-loss">RDT 3.0: Channels with Errors <em>and</em> Loss</h3>
<blockquote>
<p>Now the underlying channel can also lose packets (data, ACKs).</p>
</blockquote>
<ul>
<li>Checksum, sequence number, ACKs, retransmission will be of help … but it is not enough.</li>
</ul>
<blockquote>
<p>The sender will wait a “reasonable” amount of time for ACK. It will retransmit if no ACK is received in time.</p>
</blockquote>
<ul>
<li>If packet of ACK is delayed (not lost), the retransmission would be a duplicate, but we already handle this with sequence numbers.</li>
<li>This approach works but the performance is bad.
<ul>
<li>Example: 1 Gbps link, 15 ms propagation delay, 8000 bit packet.</li>
</ul>
<blockquote>
<p><span class="math inline">D_{trans} = \frac{L}{R} = \frac{8000\ bits}{10^9\ bits/sec} = 8\ \mu s</span>.<br />
<span class="math inline">U_{sender}</span>: <strong>utilization</strong>, the fraction of the time the sender is busy sending.<br />
<span class="math inline">U_{sender} = \frac{L/R}{RTT + L/R} = \frac{0.008}{30.008} = 0.00027</span>.</p>
</blockquote>
<ul>
<li>Throughput is just the utilization multiplied by the link rate.</li>
</ul></li>
<li>The solution is to transfer more packets!</li>
</ul>
<h2 id="pipelined-protocols">Pipelined Protocols</h2>
<blockquote>
<p>Sender allows multiple, “in-flight”, packets. - The range of sequence numbers must be increased. - There is buffering at the sender and / or receiver.</p>
</blockquote>
<h3 id="go-back-n">Go-Back-N</h3>
<ul>
<li>The sender can have up to N unACKed packets in a pipeline.</li>
<li>The receiver only sends a <strong>cumulative ACK</strong> (doesn’t ACK packet if there is a gap).</li>
<li>Sender has a timer for the oldest unACKed packet. When the timer expires, it retransmits <em>all</em> unACKed packets.</li>
<li>Any out of order packet (at the receiver) or duplicate ACK (at the sender) will be discarded.</li>
</ul>
<h3 id="selective-repeat">Selective Repeat</h3>
<ul>
<li>The sender can have up to N unACKed packets in the pipeline.</li>
<li>The receiver sends <strong>individual ACK</strong> for each packet.</li>
<li>Sender maintains a timer for each unACKed packet and only transmits that specific packet when the timer expires.</li>
</ul>
<h4 id="sender">Sender</h4>
<ul>
<li><strong>Data from above</strong>: If next available sequence number in window, send packet.</li>
<li><strong>Timeout(<span class="math inline">n</span>)</strong>: Resent packet <span class="math inline">n</span>, restart timer.</li>
<li><strong>ACK(<span class="math inline">n</span>)</strong> (<span class="math inline">n \in [send\_base, send\_base + N - 1]</span>): Mark packet <span class="math inline">n</span> as received, if <span class="math inline">n</span> is the smallest unACKed packet, advance the window base to the next unACKed sequence number.</li>
</ul>
<h4 id="receiver">Receiver</h4>
<ul>
<li><strong>Packet <span class="math inline">n \in [rcv\_base, rcv\_base + N - 1]</span></strong>: Send ACK(<span class="math inline">n</span>). If <span class="math inline">n</span> is out of order we need to buffer. If <span class="math inline">n</span> is in order, we can deliver until the next not received packet.</li>
<li><strong>Packet <span class="math inline">n \in [rcn\_base - N, rcv\_base - 1]</span></strong>: ACK(<span class="math inline">n</span>) (We need to acknowledge duplicate packets to move the sender’s window).</li>
</ul>
<p><strong>Selective Repeat: Dilemma</strong>: While sliding windows, we may accidentally accept old data as new. The problem is that the receiver knows nothing about the sender. We can <em>fix</em> this by setting the window size to be equal to less than half of the sequence number space.</p>
<h3 id="performance-of-sliding-window">Performance of Sliding Window</h3>
<p><strong>No Errors</strong>: <span class="math inline">\rho = \min(1, \frac{W\frac{L}{C}}{t_T})</span>.</p>
<h2 id="automatic-repeat-request-arq-protocols">Automatic Repeat Request (<em>ARQ</em>) Protocols</h2>
<blockquote>
<p>Applied at the transport and link layers.</p>
</blockquote>
<ol type="1">
<li>Stop-and-Wait Protocol.</li>
<li>Go-Back-N.</li>
<li>Selective Repeat.</li>
</ol>
<h2 id="connection-oriented-transport-tcp">3.5 Connection-Oriented Transport: TCP</h2>
<ul>
<li><strong>Connection-Oriented</strong>: Handshaking (exchanging control messages), initializes sender and receiver state before data exchange.</li>
<li><strong>Point-To-Point</strong>: One sender, one receiver.</li>
<li><strong>Reliable, In-Order <em>Byte</em> Steam</strong>: No “message boundaries”, byte by byte.</li>
<li><strong>Full Duplex Data</strong>: Bidirectional. MSS: Maximum Segment Size.</li>
<li><strong>Pipelined</strong>: TCP congestion and flow control set window size.</li>
<li><strong>Flow Controlled</strong>: Sender will not overwhelm receiver.</li>
</ul>
<h3 id="tcp-segment-structure">TCP Segment Structure</h3>
<ul>
<li>16 bits for source port number, 16 for destination port number.</li>
<li>32 bits for sequence number (for the bytes).</li>
<li>Acknowledgement number (for the bytes).</li>
<li>Header length, not used (URG: urgent data, ACK: ACK # valid, PSH: push data now, RST, SYS, FIN: connection establishment).</li>
<li>Receive window for the number of bytes the receiver is willing to accept.</li>
<li>16 bits for checksum, URG data pointer for the last byte of urgent data (16 bits).</li>
<li>Options (variable length).</li>
<li>Application data (variable length).</li>
</ul>
<p>Default header length is 20 bytes compared to UDP 8 bytes.</p>
<p>Acknowledgements include the sequence number of the next byte expected from the other side (cumulative ACK). The TCP spec doesn’t say how to handle out-of-order segments, it is up to the implementer. There are two choices, discard or buffer. Buffering is used in practice.</p>
<h3 id="tcp-round-trip-time-timeout">TCP Round Trip Time, Timeout</h3>
<blockquote>
<p>How to set TCP timeout value?</p>
</blockquote>
<p>It should be longer than the RTT, but the RTT varies. If it is too short, we will have unnecessary retransmissions. If it is too long, we will have slow reactions to segment loss.</p>
<p>We estimate RTT by sampling from segment transmissions. <span class="math inline">SampleRTT</span> is the measured time from segment transmission to ACK receipt (ignoring retransmissions). We use an exponential weighted moving average, <span class="math inline">EstimatedRTT = (1 - \alpha)\cdot EstimatedRTT + \alpha \cdot SampleRTT</span>. The typical value is <span class="math inline">\alpha = 0.125</span>.</p>
<p>Is this estimation enough? We want to add a <em>safety margin</em> so that a large variation in <span class="math inline">EstimateRTT</span> results in a larger safety margin. We use 4 standard deviations. <span class="math inline">DevRTT = (1 - \beta)\cdot DevRTT + \beta \cdot |SampleRTT - EstimatedRTT|</span>. The typical value is <span class="math inline">\beta = 0.25</span>.</p>
<p>The timeout interval is then <span class="math inline">TimeoutInterval = EstimatedRTT + 4 \cdot DevRTT</span>.</p>
<h3 id="tcp-reliable-data-transfer">TCP Reliable Data Transfer</h3>
<p>TCP Created a RDT service on top of IP’s unreliable service. It uses pipelined segments, cumulative ACKs, and single retransmission timer (similar to Go-Back-N). Retransmission are triggered by timeouts or duplicate ACKs.</p>
<p>Let’s initially consider a simplified TCP sender with no duplicate ACKs and ignoring flow / congestion control.</p>
<h3 id="tcp-sender-events">TCP Sender Events:</h3>
<blockquote>
<p>Three major events in sender.</p>
</blockquote>
<ol type="1">
<li>Data received from application layer.
<ul>
<li>Create segment with sequence number.</li>
<li>Sequence number is byte-stream number of the first data byte in the segment.</li>
<li>Start timer if not already running.</li>
</ul></li>
<li>Timeout.
<ul>
<li>Retransmit segment that caused timeout.</li>
<li>Restart timer.</li>
</ul></li>
<li>ACK received.
<ul>
<li>If ACK acknowledges previously unACKed segments, we update and then start timer if there are still unACKed segments.</li>
</ul></li>
</ol>
<h3 id="tcp-ack-generation">TCP ACK Generation</h3>
<table>
<colgroup>
<col style="width: 50%" />
<col style="width: 50%" />
</colgroup>
<thead>
<tr class="header">
<th>Event At Receiver</th>
<th>TCP Receiver Action</th>
</tr>
</thead>
<tbody>
<tr class="odd">
<td>Arrival of in-order segment with expected sequence number. All data up to the expected sequence number are already ACKed.</td>
<td>Delayed ACK. Wait up to 500ms for the next segment. If no next segment, send ACK.</td>
</tr>
<tr class="even">
<td>Arrival of in-order segment with expected sequence number. One other segment has ACK pending.</td>
<td>Immediately send single cumulative ACK, ACKing both in-order segments.</td>
</tr>
<tr class="odd">
<td>Arrival of out-of-order segment (heigher than expected sequence number). Gap detected.</td>
<td>Immediately send <em>duplicate ACK</em>, indicating sequence number of the next expected byte.</td>
</tr>
<tr class="even">
<td>Arrival of segment that partially or completely fills the gap.</td>
<td>Immediate send ACK, provided that the segment starts at the lower end of the gap.</td>
</tr>
</tbody>
</table>
<h3 id="tcp-fast-retransmit">TCP Fast Retransmit</h3>
<p>If you receive 3 duplicate ACKs, it is an indicator that a packet has been lost. The sender will retransmit immediately instead of waiting for the timeout.</p>
<h3 id="tcp-flow-control">TCP Flow Control</h3>
<blockquote>
<p>Receiver controls sender, so that the sender won’t overflow receiver’s buffer by transmitting too much, too fast.</p>
</blockquote>
<p>Applications may remove data from TCP socket buffers slower than the TCP receiver is delivering (sender is sending).</p>
<ul>
<li>Receiver “advertises” free buffer space by including <strong>rwnd</strong> value in the TCP header of receiver-to-sender segments.
<ul>
<li><strong>RcvBuffer</strong> size is set via socket options (typical default is 4096 bytes).</li>
<li>Many operating systems auto adjust <strong>RcvBuffer</strong>.</li>
</ul></li>
<li>Sender limits the amount of unACKed (<em>in-flight</em>) data to the receiver’s <strong>rwnd</strong> value.</li>
<li>This guarantees that the buffer will not overflow.</li>
</ul>
<h3 id="connection-management">Connection Management</h3>
<blockquote>
<p>Before exchanging data, the sender and receiver “handshake” (agree to establish connection, agree on connection parameters).</p>
</blockquote>
<h2 id="principles-of-congestion-control">3.6 Principles of Congestion Control</h2>
<blockquote>
<p>Too many sources sending too much data too fast for the <strong>network</strong> to handle.</p>
</blockquote>
<ul>
<li>Different from flow control.</li>
<li>Manifests as lost packets (buffer overflow at routers) and long delays (queueing in router buffers).</li>
</ul>
<h3 id="causes-costs-of-congestion">Causes / Costs of Congestion</h3>
<ol type="1">
<li>Infinite buffer, 2 senders and 2 receivers use the same link with an output link capacity of <span class="math inline">R</span>.
<ul>
<li>Maximum per-connection throughput: <span class="math inline">\frac{R}{2}</span>.</li>
<li>Large delay as the arrival rate <span class="math inline">\lambda_{in}</span> approaches <span class="math inline">\frac{R}{2}</span>.</li>
</ul></li>
<li>Finite buffer. Input and output rates are the same.
<ul>
<li>Transport-layer input includes <em>retransmissions</em>: <span class="math inline">\lambda_{in}^\prime \ge \lambda_{in}</span> (<em>offered load</em>).</li>
</ul></li>
<li>Multiple routers.
<ul>
<li>One connection may take up all of the routers’ time.</li>
<li>More routers involved in delivering data means more wasted network efforts. This is the reason for sudden drop on throughput.</li>
<li>When packet is dropped, any “upstream” transmission capacity is wasted!</li>
</ul></li>
</ol>
<h3 id="approaches-to-congestion-control">Approaches to Congestion Control</h3>
<blockquote>
<p>Two broad approaches.</p>
</blockquote>
<ol type="1">
<li>End-End Congestion Control.
<ul>
<li>No explicit feedback from network.</li>
<li>Congestion inferred from end-system observed loss, delay.</li>
<li>Approach taken by TCP.</li>
</ul></li>
<li>Network-Assisted Congestion Control.
<ul>
<li>Routers provide feedback to end systems.
<ul>
<li>Single bit indicating congestion.</li>
<li>Explicit rate for sender to send at.</li>
</ul></li>
</ul></li>
</ol>
<h2 id="tcp-congestion-control">3.7 TCP Congestion Control</h2>
<blockquote>
<p>Additive increase, multiplicative decrease (<strong>AIMD</strong>).</p>
</blockquote>
<ul>
<li>Sender increases transmission rate (window size), probing for usable bandwidth, until loss occurs.
<ul>
<li>Increase <strong>cwnd</strong> by 1 MSS (<em>maximum signal size</em>) every RTT until loss detected.</li>
<li>Cut <strong>cwnd</strong> in half after loss.</li>
</ul></li>
<li>Recall that the sender limits transmission.
<ul>
<li><span class="math inline">LastByteSent - LastByteAcked \le \min(cwn, cwnd)</span>.</li>
</ul></li>
<li>TCP sending rate is roughly sending <strong>cwnd</strong> bytes, then waiting an RTT for ACKs.
<ul>
<li><span class="math inline">\frac{cwnd}{RTT}</span> bytes / sec.</li>
</ul></li>
</ul>
<h3 id="tcp-slow-start">TCP Slow Start</h3>
<ul>
<li>Initially <strong>cwnd</strong> is 1 MSS and is doubled for every RTT.
<ul>
<li>This is done by incrementing <strong>cwnd</strong> for every ACK received.</li>
</ul></li>
<li>Initial rate is slow but ramps up exponentially fast.</li>
</ul>
<h3 id="detecting-reacting-to-loss">Detecting, Reacting to Loss</h3>
<ul>
<li>Loss indicated by timeout.
<ul>
<li><strong>cwnd</strong> set to 1 MSS.</li>
<li>Window then grows exponentially (as in slow start) to the threshold, then grows linearly.</li>
</ul></li>
<li>Loss indicated by 3 duplicate ACKs (<em>TCP RENO</em>).
<ul>
<li>Duplicate ACKs indicate that the network is capable of delivering some segments.</li>
<li><strong>cwnd</strong> is cut in half and then the grows linearly.</li>
</ul></li>
<li>(<em>TCP TAHOE</em>) always sets <strong>cwnd</strong> to 1 (timeout of 3 duplicate ACKs).</li>
</ul>
<h3 id="switching-from-slow-start-to-ca-congestion-avoidance">Switching from Slow Start to CA (<em>Congestion Avoidance</em>)</h3>
<blockquote>
<p>When should the exponential increase switch to linear?<br />
When <strong>cwnd</strong> gets to <span class="math inline">\frac{1}{2}</span> of its value before timeout.</p>
</blockquote>
<p>Implemented with a variable <strong>ssthresh</strong>. On a loss event, <strong>ssthresh</strong> is set to <span class="math inline">\frac{1}{2}</span> of <strong>cwnd</strong> before loss event.</p>
<h3 id="tcp-throughput">TCP Throughput</h3>
<ul>
<li>Average TCP throughput as a function of window size, RTT?
<ul>
<li>Ignore slow start, assume we always have data to send.</li>
</ul></li>
<li>Throughput fluctuates between the max of <span class="math inline">\frac{W}{RTT}</span> (<em>congestion</em>) and <span class="math inline">\frac{W}{2RTT}</span> (<em>after congesion, drop rate</em>).
<ul>
<li>Average window size is <span class="math inline">\frac{3W}{4}</span>.</li>
<li>Average throughput is <span class="math inline">\frac{3W}{4RTT}</span> bytes / sec.</li>
</ul></li>
</ul>
<p>Example: Average Throughput = 10 Gbps, 100ms RTT, 1500 byte segment = 3/4 W/RTT bytes/sec Solve for W, Number of segments is W / 1500</p>
<p>Throughput in terms of segment loss probability <span class="math inline">L = \frac{1.22 \cdot MSS}{RTT \sqrt L}</span>, MSS -> Maximum Segment Size.</p>
<p>To achieve a 10gbps throughput, we need a lost rate of <span class="math inline">L = 2\cdot10^{-10}</span> which is a very small loss rate.</p>
<p>We need a new version of TCP for high-speed. It is hard to implement TCP because there are hardware that implement and are hard to change.</p>
<h3 id="tcp-fairness">TCP Fairness</h3>
<blockquote>
<p><strong>Fairness goal</strong>: If <span class="math inline">K</span> TCP sessions share the same bottleneck link of bandwidth <span class="math inline">R</span>, each should have average rate of <span class="math inline">\frac{R}{K}</span>.</p>
</blockquote>
<p>Two competing sessions will have additive increase which gives slope of 1, as throughput increases. Multiplicative decrease decreases throughput proportionally.</p>
<p><img src="https://i.imgur.com/Ec9MFxB.png" /></p>
<p>Multimedia apps often do not use TCP because they do not want the rate throttled by congestion control. They send audio / video at constant rate, tolerate packet loss.</p>
<p>This is fair over each connection, but you can cheat the system by having multiple TCP connections.</p>
<h1 id="network-layer">4. Network Layer</h1>
<blockquote>
<p>Unlike the application and transport layers, the network layer is implemented <strong>every</strong> host and router.</p>
</blockquote>
<p><strong>Recall</strong>: Transport layer encapsulates the data by breaking it into segments and adding headers.</p>
<p>The network layer further encapsulates segments by adding it’s own headers.</p>
<h2 id="two-key-functions">Two Key Functions</h2>
<ol type="1">
<li><strong>Forwarding</strong>: Move packets from router’s input to appropriate router output.</li>
<li><strong>Routing</strong>: Determining route taken by packets from source to destination.</li>
</ol>
<p>Some network architectures require connection setup. Before datagrams flow, two end hosts <em>and</em> intervening routers establish virtual connection.</p>
<p><strong>Recall</strong>: Network layer connection service is between two hosts (may also involve intervening routers in case of VCs). Transport layer connection service is between two processes.</p>
<h2 id="network-service-model">Network Service Model</h2>