lesson-06.html 14.1 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  Computer Networks (6)
Please wait, while our marmots are preparing the hot chocolate…
# @chunk: chunks/title.md# @chunk: chunks/objectives.md## Computer Networks {var-cours-n}: Plan {#plan overview}@SVG: media/stack-index.svg 100px 400px {svg floatright appTrans margin-left-minus-100}- Goal: transport layer {shaded} - understand its main roles and mechanisms - understand the how TCP (and UDP) are implemented- Overview - Transport layer: context and services (role) {it1} // see how it fits between application and network - Multiplexing and demultiplexing {it3} - UDP {it4} - Reliable communications, please! {it5} - Pipelining: principle and algos {it6} - Implementation of TCP {it7} - Online timeout estimation {it8} - Congestion: principle and algos {it9} - TCP: optimality? equity? {it10}# @copy:#plan# @copy:#plan: %+class:inred: .it7## TCP: Transmission Control Protocol
[RFC 793,1122,1323, 2018, 2581] // 2018: selective repeat- TCP communication - between two processes - reliable, ordered - stream-based: no separation between messages // even if sent as segments - bi-directional - connection oriented, stateful, handshake at the beginning // initialize the state between sender and receiver - pipelined (with a variable window size) // congestion - with flow control // limits bitrate to the receiver## TCP: formats of segment headers {libyli}@SVG: media/part3/segment-structure-tcp.svg 250px 500px {floatright withmargin}- Total size: variable (20 bytes minimum)- Source and dest. ports (16 bits each)- Sequence and ack numbers: **in bytes** // ! not the packet number- *offset*: size of the header (cf. options)- *flags*, booleans, including - ACK: this segment contains a ACK - SYN: connection initialization
(exchange of the initial sequence number) - FIN: end of connection- *receive window*: size in bytes that the receiver wants // flow control- *checksum* as in UDP## TCP: sequence and ack numbers {libyli}@SVG: media/part3/segment-structure-tcp.svg 150px 300px {floatright withmargin}- Reminder: TCP handles a stream of bytes- Sequence numbers - index in the stream of the first byte of the segment- Acknowledgment (ack) - cumulative acknowledgment (as in go-back-N) - stream index of the next byte to be received - ACK flag is set to 1@SVG: media/part3/tcp-sequence-number.svg 350px 100px {floatright clearright withmargin}- go-back-N or selective repeat? - cumulative acknowledgment - TCP, by default, does not specify what to do with out-of-order packets - RFC2018: option for using *selective repeat* (SACK)## TCP: examples@SVG: media/part3/tcp-sequence-ex1.svg 350px 350px {floatleft}@SVG: media/part3/tcp-sequence-ex2.svg 450px 500px {floatright second}- @anim: #e11 |#e12 |#e13 |#e14 |#l2r |#r2l- @anim: .second, #s1 |#s2 |#a1 |#a2 |#s3 |#s4 |#a3 |#a4 |#s5## TCP: multiples acknowledgment {libyli}- TCP acknowledgment (reminder) - ack with the index of the next expected byte - out-of-order packets ⇒ double ack- Using double acks for fast re-transmission - the timeout is generally long - if we receive multiple double acks, there was probably a loss - TCP strategy - on the 3rd double ack (4th identical) - send the packet again- @anim: .floatright@SVG: media/part3/tcp-sequence-ex3.svg 250px 250px {floatright}## TCP Fast Retransmit@SVG: media/part3/tcp-sequence-ex3.svg 450px 500px {centered}- @anim: #send1 |#ac1 |#ac2 |#ac3 |#ac4 |#send2## TCP Flow Control@SVG: media/part3/segment-structure-tcp.svg 200px 500px {floatright withmargin}- Goal: do not flood the receiver- TCP has a receive buffer - typical size: 4096 kB - the system can adapt it dynamically- rcv win {slide} - send in the tcp header of every segment - amount of available space in the buffer## TCP Connection Opening@SVG: media/part3/tcp-sequence-handshake.svg 200px 500px {floatright withmargin}- Client {slide} - generation of a sequence number - emission of a SYN packet- Server {slide} - generation of a sequence number - emission of a SYNACK packet (ACK + SYN)- Client {slide} - emission of a ACK packet - can also start sending data in this packet# @copy:#plan: %+class:inred: .it8## What should be the timeout in TCP?
(before retransmitting
a non-ACK'd packet){question}## Timeout and Round Trip Time- Choice of the timeout - longer than RTT - but RTT varies - if too short: useless retransmissions - if too long: long delay on loss // still we have the 3dup acks fast retransmit- Estimation of RTT{slide} - $\text{obsRTT}_i$: time between sending packet $i$ and receiving its ACK - $\text{obsRTT}_i$ varies and is unstable ⇒ moving average{slide}## Timeout in TCP: RTT estimation@SVG: media/part3/running-average.svg 700px 300px {graph}- @anim: .truc | .graph- At each new ACK ($\text{obsRTT}_i$){truc} - $\text{avg} = (1-\alpha) \; \text{avg} + \alpha \; \text{obsRTT}_i$ - moving/rolling/running average - exponential weighting{slide} - value for $\alpha$ : 0.125{slide}## Timeout Computation in TCP- Estimation of RTT{slide} - $\text{avg} = (1-\alpha) \; \text{avg} + \alpha \; \text{obsRTT}_i$- Estimation of the mean deviation{slide} - $\text{dev} = (1-\beta) \; \text{dev} + \beta \; \left| \text{obsRTT}_i - \text{avg}\right|$ // absolute- Transmission delay $= \text{avg} + 4 \cdot \text{dev}{}${slide}- Values: $\alpha = 0.125 \;\; \beta = 0.25${slide}- @anim: .centered@SVG: media/part3/tcp-timeout-estimation.svg 700px 200px {centered}# @copy:#plan: %+class:inred: .it9## Congestion: principles (infinite queue)@SVG: media/part3/congestion-infinite.svg 800px 350px {centered}- Ideal case of an infinite queue {a}- Maximal bandwidth {b}- Unreasonable delays (time spend in the queue){c} // even before reaching C/2- @anim: #lin |#lout |#finf |#axes |#curve |.a |.b |.c## Congestion: principles@SVG: media/part3/congestion-bounded.svg 800px 350px {centered}- More realistic case with limited buffers and packet loss{a}- Retransmitting packets due to timeout (loss, delay){b}- Reduced bandwidth due to retransmissions {c}- @anim: .centered |#lin |#lout |#finf |#axes |#curve |.a |.b |.c## Congestion: in a network@SVG: media/part3/congestion-network.svg 800px 350px {centered}- Augmenting the rate of a connection can penalize the rest {a}- When a router drops packets,
all the bandwidth used to bring the packet there is wasted {b}- @anim: #mask+#blue |#green |#red |#graph |.a |.b## Congestion Control/avoidance:
two kinds of approaches- Congestion-control assisted by the network{slide} - smart routers - router→host messages on congestion level {slide} - the network tells the host what bandwidth to use {slide} - disadvantages {slide} - expensive routers - difficult to get robustness // more complex- Congestion-control at a host level{slide} - the network is a black box // we still suppose its behavior (drops, ...) - based on observed delays and losses {slide} - used by TCP{slide} // we will see only the case of TCP# @copy:#plan: %+class:inred: .it10## TCP Congestion Control (+reminders)@svg: media/part3/tcp-sequence-number.svg 400px 100px {floatright withmargin}- Sequence number in bytes- Sliding window {slide} - limitation on the sender side - (last byte sent - last byte ACK'd) ≤ N{slide} - N is also denoted $cwnd$ (Congestion Window){slide}- TCP transmission rate{slide} - approximately: $\frac{cwnd}{RTT}{}$ // explication...- Congestion control in TCP{slide} - dynamic adaptation of $cwnd$ - as a function of the observed delays and losses - different possible algorithms (still evolving)## TCP Congestion Control: principles- Given $MSS$: maximum TCP segment size{slide}- Increases the window size (emission rate){slide} - goal: use at best the available bandwidth - additive increase ($cwnd = cwnd + MSS$){slide} - reacts in case of packet loss {slide}- In case of loss {slide} - diminishes the window size - multiplicative decrease ($cwnd = 0.5 \times cwnd$)- Concept of “slow start” {slide} - initial phase - goal: reach/find as fast as possible the bandwidth limit - multiplicative increase at the beginning ($cwnd = 2 \times cwnd$)## TCP Slow Start@svg: media/part3/tcp-sequence-slowstart.svg 200px 500px {floatright withmargin}- Exponential increase of the window size - initialization: $cwnd = MSS$ - $MSS$: maximum segment size - $cwnd = 2\times cwnd$ at each RTT{slide} - $cwnd = cwnd + MSS$ at each ACK{slide} // in practice- Slow start{b} - starts with a low rate - increases the rate exponentially - end of the slow start phase - in case of loss - or, when a threshold is reached: $cwnd \ge ssthres$- @anim: #g1 |#g2 |#g4 |#g8 |.b## TCP Congestion Avoidance (CA)@svg: media/part3/tcp-congestion-graph.svg 700px 400px {centered}- @anim: #slowstart |#lin1 |#half1 |#rest + .a- Additive increase {a}- Multiplicative decrease{a}## Loss Detection+Compensation (TCP Reno)- Timeout expiration {slide} // an actual problem, not normal - re-initialization: $cwnd = MSS$ ; then slow start again- Triple double-ACK (4 times the same ACK){slide} // less problematic: the network is operation, just bad luck or BEGIN of congestion - $cwnd = 0.5 \times cwnd$ ; then linear increase - TCP Tahoe (older): re-initializing cwnd- @anim: .centered@svg: media/part3/tcp-congestion-graph-precise.svg 700px 290px {centered}## Number of packets emitted…
from the start to the 1st red arrow?
up to the 2nd red arrow?{question bottom} // to validate understanding of the graph@svg: media/part3/tcp-congestion-graph-how-many-packets.svg 700px 290px {hum}## Optimality and Equity of TCP@SVG: media/part3/tcp-fairness.svg 700px 400px {svg}@anim: #lienC | #graph | #equity |#gstart |#gs1 |#climit |#gs2 |#gs3 |#gs4 |#gs5 |#gs6 |#gs7## (In)Equity of TCP- UDP has no congestion control {slide} - sends packets, interpolation/correction in case of packet loss - no emission reduction in case of congestion - some routers are blocking UDP?- Multiple TCP connections{slide} - TCP provides connection-equity - opening of multiple connections - common for web browsers, etc - example, if there are already 4 connections {slide} - the new application opens 1 connection ⇒ effective rate of $\frac{R}{5}{}$ - the new application opens 4 connections ⇒ effective rate of $\frac{R}{2}{}$ {slide} - NB: routers can still do IP based drop {slide}

/ will be replaced by the authorwill be replaced by the title