Computerarchitectuur en netwerken – 10 – TCP congestion control Netwerklaag Lennart Herlaar
6 oktober 2015
Inhoud Congestiebeheer TCP congestiebeheer Netwerk laag principes van de netwerklaag IP adressen IP (protocol) IP adressen krijgen Network Address Translation (NAT)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
1
Congestiebeheer Congestiebeheer = zorgen dat er geen ‘files’ in het netwerk ontstaan Congestiebeheer 6= Flow control Flow Control = tussen zender en ontvanger Congestiebeheer = in het netwerk
Lennart Herlaar
Computerarchitectuur en netwerken – 10
2
Congestiebeheer 1
Lennart Herlaar
Computerarchitectuur en netwerken – 10
3
Congestiebeheer 1
Lennart Herlaar
Computerarchitectuur en netwerken – 10
4
Congestiebeheer 2
Lennart Herlaar
Computerarchitectuur en netwerken – 10
5
Congestiebeheer 2 a Theoretische doorvoer b Hertransmissie wegens router vol c Timeout te kort (getallen zijn voorbeelden)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
6
Congestiebeheer 3
Lennart Herlaar
Computerarchitectuur en netwerken – 10
7
Congestiebeheer 3
Lennart Herlaar
Computerarchitectuur en netwerken – 10
8
Vormen van congestiebeheer End-to-end Geen informatie van het netwerk over congestie Verzender moet er zelf achter zien te komen Bij timeout/packetverlies: neem aan dat congestie de oorzaak is Kijk naar RTT (Round Trip Time) Aanpak bij TCP
Lennart Herlaar
Computerarchitectuur en netwerken – 10
9
Vormen van congestiebeheer End-to-end Geen informatie van het netwerk over congestie Verzender moet er zelf achter zien te komen Bij timeout/packetverlies: neem aan dat congestie de oorzaak is Kijk naar RTT (Round Trip Time) Aanpak bij TCP
Netwerkondersteund Netwerk stuurt informatie naar verzender Voorbeeld: een bit dat netwerk te belast is (SNA/ATM) Of ‘choke pakket’ met info
Lennart Herlaar
Computerarchitectuur en netwerken – 10
9
TCP congestion control TCP houdt Congestion Window bij (naast RcvWindow) we hadden al: LastByteSent − LastByteAcked ≤ RcvWindow we voegen nu toe: LastByteSent − LastByteAcked ≤ CongWindow LastByteSent − LastByteAcked ≤ min(RcvWindow, CongWindow) CongWindow wordt voortdurend aangepast (congestion avoidance): Bij hertransmissie: kleiner maken (snel) Bij een correcte ACK: groter maken (langzaam)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
10
TCP congestion control (Congestion Avoidance) Concreet: Additive Increase, Multiplicative Decrease Bij hertransmissie: halveer CongWindow Anders voeg er een constante hoeveelheid aan toe: 1 MSS/RTT (MSS = Maximal Segment Size) Nooit lager dan 1 MSS
Nadeel: in het begin duurt het lang voor je een redelijke waarde hebt opgebouwd Lennart Herlaar
Computerarchitectuur en netwerken – 10
11
Verfijningen Slow-start: Begin met een lage CongWindow (= 1 MSS) CongWindow telkens verdubbelen Indien hertransmissie, dan Treshold = CongWindow/2 en CongWindow = 1 MSS Indien Treshold bereikt, dan Congestion Avoidance
Lennart Herlaar
Computerarchitectuur en netwerken – 10
12
Verfijningen Slow-start: Begin met een lage CongWindow (= 1 MSS) CongWindow telkens verdubbelen Indien hertransmissie, dan Treshold = CongWindow/2 en CongWindow = 1 MSS Indien Treshold bereikt, dan Congestion Avoidance
Congestion Avoidance: Laat CongWindow lineair groeien Indien loss event, dan Threshold = CongWindow/2 en over op Slow-start
Lennart Herlaar
Computerarchitectuur en netwerken – 10
12
Verfijningen Slow-start: Begin met een lage CongWindow (= 1 MSS) CongWindow telkens verdubbelen Indien hertransmissie, dan Treshold = CongWindow/2 en CongWindow = 1 MSS Indien Treshold bereikt, dan Congestion Avoidance
Congestion Avoidance: Laat CongWindow lineair groeien Indien loss event, dan Threshold = CongWindow/2 en over op Slow-start
Triple dup. ACK (TCP Reno): Threshold = CongWindow/2; CongWindow = Threshold Schakel over op Congestion Avoidance (AIMD) Dit heet Fast Recovery Idee: vanwege de 3 ACKs zijn er kennelijk segmenten goed aangekomen
Andere algoritmes zijn ook mogelijk Lennart Herlaar
Computerarchitectuur en netwerken – 10
12
TCP Tahoe/Reno
Lennart Herlaar
Computerarchitectuur en netwerken – 10
13
Eerlijk delen
Lennart Herlaar
Computerarchitectuur en netwerken – 10
14
Eerlijk delen
Lennart Herlaar
Computerarchitectuur en netwerken – 10
15
TCP RTT en timeout Bij TCP is de RTT niet vooraf te berekenen Route in netwerk niet bekend Belasting van routers (queueing) niet bekend
Maak een schatting door tijd van verzenden segment tot aankomst ACK te meten gemeten RTT kan erg varieren Daarom gemiddelde nemen Echter: Resultaten uit het verleden geven geen garantie voor de toekomst Daarom resultaat uit het verleden laten vervagen
Formule EstimatedRTT = (1−α)×EstimatedRTT+α×SampleRTT
Lennart Herlaar
Computerarchitectuur en netwerken – 10
16
SampleRTT en EstimatedRTT
Lennart Herlaar
Computerarchitectuur en netwerken – 10
17
Timeout berekening Timeout berekenen uit de RTT Maar hoe?
Lennart Herlaar
Computerarchitectuur en netwerken – 10
18
Timeout berekening Timeout berekenen uit de RTT Maar hoe? Gebruik de variantie in de RTT Bereken op soortgelijke wijze uit de samples: DevRTT = (1−β)×DevRTT+β×|SampleRTT−EstimatedRTT| Aanbevolen om timeout 4×DevRTT hoger te nemen Timeout = EstimatedRTT + 4 × DevRTT
Lennart Herlaar
Computerarchitectuur en netwerken – 10
18
TCP doorvoersnelheid Eerste orde benadering: snelheid = doorvoervenster/RTT Veronderstel dat buffer groot genoeg is, dus doorvoervenster wordt bepaald door Congestion window Maximale waarde doorvoervenster = W bits (als congestie optreedt) daarna wordt gehalveerd (congestion avoidance), dus W/2 Doorvoervenster varieert lineair tussen W/2 en W. Dus gemiddeld 0,75. doorvoersnelheid =
0.75 × W RTT
Als je rekening houdt met slow start dan krijg je subtielere formules.
Lennart Herlaar
Computerarchitectuur en netwerken – 10
19
Samenvatting Transportlaag Transportlaag zorgt voor multiplexing (UDP en TCP) Eventueel ook voor betrouwbaarheid (TCP) Protocollen voor betrouwbaarheid zijn gebaseerd op Automatic Repeat reQuest (ARQ) met ACKs en volgnummers Simpele Alternating Bit Protocol is te langzaam Sliding Window protocol is beter TCP heeft ook Flow Control en Congestiebeheer
Lennart Herlaar
Computerarchitectuur en netwerken – 10
20
Netwerk Laag
Lennart Herlaar
Computerarchitectuur en netwerken – 10
21
Inhoud TCP congestiebeheer Netwerk laag ⇐= principes van de netwerklaag IP adressen IP (protocol) IP adressen krijgen Network Address Translation (NAT)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
22
Netwerklaag Doel van de netwerklaag pakketten van de ene computer naar de andere brengen vgl: transportlaag: van proces naar proces
Router: apparaat dat (delen van) netwerken met elkaar verbindt router werkt in netwerklaag heeft geen weet van hogere lagen vgl switch: werkt in datalinklaag (heeft geen weet van netwerklaag)
Subdoelen (functies) van netwerklaag: Routering: bepalen van het pad (route) dat een pakket moet doorlopen Forwarding: pakketten die in een router aankomen naar de juiste kant sturen Sommige netwerken: verbindingen beheren (niet in Internet)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
23
Netwerkvoorbeeld
Lennart Herlaar
Computerarchitectuur en netwerken – 10
24
Datagram/virtual circuit De netwerklaag kan verbindingsloos of verbindingsgericht zijn Verbindingsloos: Elk pakket wordt afzonderlijk door het netwerk gerouteerd Elk pakket moet adres van bestemming bevatten Routers behandelen elk pakket afzonderlijk datagramnetwerk
Lennart Herlaar
Computerarchitectuur en netwerken – 10
25
Datagram/virtual circuit De netwerklaag kan verbindingsloos of verbindingsgericht zijn Verbindingsloos: Elk pakket wordt afzonderlijk door het netwerk gerouteerd Elk pakket moet adres van bestemming bevatten Routers behandelen elk pakket afzonderlijk datagramnetwerk
Verbindingsgericht: Netwerk moet eerst verbinding opzetten van A naar B Pakketten worden over de verbinding (virtual circuit) gerouteerd Pakketten hoeven niet bestemming te hebben maar virtueel circuitnummer Routers weten dat pakket bij een bepaald virtueel circuit hoort Mogelijkheid om bandbreedte etc. voor een virtueel circuit te reserveren Lennart Herlaar
Computerarchitectuur en netwerken – 10
25
Transport- en netwerklaag Transportlaag: verbindingsgericht of verbindingsloos Voorbeeld: TCP vs. UDP staat in principe los van de structuur van netwerklaag Maar verbindingsloos transportlaag met virtueel circuit in netwerklaag lijkt niet erg zinvol Omgekeerd wel: TCP: verbindingsgericht transportprotocol IP: datagram netwerkprotocol
IP biedt alleen best effort dienst aan: geen geen geen geen
Lennart Herlaar
garantie dat pakketten aankomen garantie van volgorde gegarandeerde bandbreedte ‘Quality of Service’
Computerarchitectuur en netwerken – 10
26
Inhoud TCP congestiebeheer Netwerk laag principes van de netwerklaag IP adressen ⇐= IP (protocol) IP adressen krijgen Network Address Translation (NAT)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
27
IP IP = Internet Protocol IP versie 4 = huidige versie, IP versie 6 = toekomstige versie (wordt al wel gebruikt) IP V4 gebruikt 32 bits adressen voor aangesloten apparaten Genoteerd als 4 afzonderlijke bytes (131.211.80.17) Iedere interface heeft eigen IP adres Ook routers hebben een IP-adres voor elke netwerkaansluiting IP versie 6 (IP V6) gebruikt 128-bits adressen
Lennart Herlaar
Computerarchitectuur en netwerken – 10
28
IP adressen
Lennart Herlaar
Computerarchitectuur en netwerken – 10
29
Netwerk maskers In vorige voorbeeld heeft elk IP adres in een netwerk dezelfde eerste 3 bytes 223.1.1 / 223.1.2 / 223.1.3 Alle interfaces in één netwerk moeten hetzelfde beginstuk hebben De hoeveelheid bits die hetzelfde zijn bepalen het netwerkmasker In dit geval is het netwerkmasker 255.255.255.0 (255 = allemaal 1-bits) Dus 11111111.11111111.11111111.00000000 Moderne notatie: netwerk is 223.1.1.0/24 (=24 bits)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
30
IP adres klassen Oorspronkelijk IP adressen in klassen ingedeeld A, B, C netwerken, op grens van 8, 16, 24 bits Dit maakt het routeren simpel Tegenwoordig CIDR (Classless InterDomain Routing): Netwerk-deel van IP adres wordt door netwerkmasker aangegeven Als je een netwerkmasker van 21 bits hebt, kun je 11 bits gebruiken voor hostnummer binnen netwerk
Lennart Herlaar
Computerarchitectuur en netwerken – 10
31
IP adres klassen
Lennart Herlaar
Computerarchitectuur en netwerken – 10
32
Speciale IP adressen
Lennart Herlaar
Computerarchitectuur en netwerken – 10
33
CIDR CIDR = Classless Inter Domain Routing Hierbij wordt niet meer naar de classes (A,B,C,D) gekeken. Bij de classes heb je te weinig flexibiliteit met aantallen computers in netwerk Alleen 254 (28 − 2), 65534 (216 − 2) en 16777214 (224 − 2)
Voorbeeld: je wilt max. 1000 computers aansluiten in je netwerk Je hebt nu aan 10 bits genoeg (210 − 2 = 1022) Dus een /22 netwerk masker Bijvoorbeeld: 200.23.28.0/22 11001000 00010111 00011100 00000000 (de bits buiten het masker moeten 0 zijn). Adressen: {200.23.28.0 – 200.23.31.255} Je zou hier nog een ‘gat’ uit kunnen halen voor een klein netwerkje van een stuk of 14 adressen. Lennart Herlaar
Computerarchitectuur en netwerken – 10
34
CIDR Routing Een CIDR router werkt met prefixen In het vorige voorbeeld staat ergens in een router: stuur alle pakketten met een adres in 200.23.28.0/22 naar uitgang X. Dus alle adressen waarvan de eerste 22 bits hetzelfde zijn als in 200.23.28.0 worden naar lijn X gestuurd. Stel we hebben nog een klein netwerkje van 14 hosts waar we een deel van de overtollige adressen in deze range voor gebruiken, bijvoorbeeld 200.23.28.0/28. Prefix lijn Dan bevat de router: 200.23.28.0/28 Y 200.23.28.0/22 X De langste prefix wordt eerst gecheckt. Dit heet longest prefix matching. Het grootste netwerk kunnen we noteren als 200.23.28.0/22−200.23.28.0/28 (minus notatie). Lennart Herlaar
Computerarchitectuur en netwerken – 10
35
Inhoud TCP congestiebeheer Netwerk laag principes van de netwerklaag IP adressen IP (protocol) IP adressen krijgen ⇐= Network Address Translation (NAT)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
36
Het krijgen van een IP adres IP adressen worden uitgegeven door ICANN (Internet Corporation for Assigned Names and Numbers) aan ISP’s of grote organisaties Je kunt je IP nummer met de hand invoeren in je computer Of automatisch verkrijgen via DHCP DHCP = Dynamic Host Configuration protocol Geeft o.a. IP nummers aan computers in netwerk Ook adressen van routers, DNS servers e.d. Vraag hoe vind je de DHCP server?
Lennart Herlaar
Computerarchitectuur en netwerken – 10
37
DHCP server protocol DHCP server: 223.1.2.5
DHCP discover src : 0.0.0.0, 68 dest.: 255.255.255.255,67 yiaddr: 0.0.0.0 transaction ID: 654
arriving client
DHCP offer
DHCP request
time
src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 654 DHCP server: 223.1.2.5 Lifetime: 3600 secs
src: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 DHCP server: 223.1.2.5 Lifetime: 3600 secs DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 DHCP server: 223.1.2.5 Lifetime: 3600 secs
Lennart Herlaar
Computerarchitectuur en netwerken – 10
38
IP pakket (versie 4)
Lennart Herlaar
Computerarchitectuur en netwerken – 10
39
IP fragmentatie
Lennart Herlaar
Computerarchitectuur en netwerken – 10
40
IP fragmentatie
Fragmenten kunnen later weer verder gefragmenteerd worden.
Lennart Herlaar
Computerarchitectuur en netwerken – 10
41
NAT (Network Address Translation) Situatie: thuis netwerk met 5 computers, via ADSL of kabelmodem verbonden met ISP Wat voor IP adressen?
Lennart Herlaar
Computerarchitectuur en netwerken – 10
42
NAT (Network Address Translation) Situatie: thuis netwerk met 5 computers, via ADSL of kabelmodem verbonden met ISP Wat voor IP adressen? Oplossing 1: Zorg dat je 5 IP adressen van je ISP krijgt Zelfde netwerk als ISP: dus geen router nodig Hub of switch is voldoende (zelfde netwerk) Subnet kan ook, dan wel router nodig /29 is voldoende (3 bits geeft 8-2=6 adressen) als je adressen niet op 000 of 111 eindigen Je ISP moet je dan 8 adressen gegeven hebben.
Lennart Herlaar
Computerarchitectuur en netwerken – 10
42
NAT (Network Address Translation) Situatie: thuis netwerk met 5 computers, via ADSL of kabelmodem verbonden met ISP Wat voor IP adressen? Oplossing 1: Zorg dat je 5 IP adressen van je ISP krijgt Zelfde netwerk als ISP: dus geen router nodig Hub of switch is voldoende (zelfde netwerk) Subnet kan ook, dan wel router nodig /29 is voldoende (3 bits geeft 8-2=6 adressen) als je adressen niet op 000 of 111 eindigen Je ISP moet je dan 8 adressen gegeven hebben.
Oplossing 2: NAT Gebruikt eigen serie IP adressen in thuisnetwerk Series 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16 gereserveerd Deze mogen nooit op openbare Internet gebruikt worden Lennart Herlaar
Computerarchitectuur en netwerken – 10
42
NAT werking
Lennart Herlaar
Computerarchitectuur en netwerken – 10
43
NAT werking
Lennart Herlaar
Computerarchitectuur en netwerken – 10
44
NAT werking
Lennart Herlaar
Computerarchitectuur en netwerken – 10
45
NAT werking
Lennart Herlaar
Computerarchitectuur en netwerken – 10
46
NAT werking
Routers werken in de netwerklaag, maar een NAT router moet noodgedwongen ook in de transportlaag informatie kijken. Dit is tegen het lagenprincipe.
Lennart Herlaar
Computerarchitectuur en netwerken – 10
47
Samenvatting De netwerklaag zorgt dat pakketten van computer naar computer door het netwerk gerouteerd worden Netwerken kunnen verbindingsgericht (ATM) of verbindingsloos (Internet) zijn Op Internet heeft iedere aansluiting een IP adres. Deze zijn in netwerken of subnetten georganiseerd (IP-adres/netwerkmasker) De (sub)netten zijn met routers aan elkaar verbonden In de netwerklaag in het Internet worden IP-pakketten verzonden IP adressen kun je o.a. krijgen met DHCP NAT is een hack om in een (thuis)netwerk meer IP-adressen te gebruiken dan je gekregen hebt.
Lennart Herlaar
Computerarchitectuur en netwerken – 10
48
