Please wait, while our marmots are preparing the hot chocolate…
# @chunk: chunks/ # @chunk: chunks/ ## 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