Walrand Final Review 2005EECS 122 1Review – FinalEECS 122University of CaliforniaBerkeley2REVIEW - Final TCP DNS QoS Security Ad Hoc Check ListContents –Index–Review2 3TCP Service Protocol Phases Error Control Congestion Control Flow ControlTOC – Congestion Control 4TCP Service:IPTransportABC[A | B | p1 | p2 | …]p1 p2 p1 p2 p3 p1 p2portsApplicationHTTPDNSftpTCP: Byte Stream Ordered, reliable, well-pacedTOC – Transport – Overview – Illustration 5SYN kSYN n; ACK k+1DATA k+1; ACK n+1ACK k+n+1data exchangeFINFIN ACK½ closeFINFIN ACK½ closeProtocol Phases3-way handshakeTOC – Transport – TCP –Steps 6Error Control: Go Back N Sender: Transmitter window = {A + 1, …., A + N}where A = last ACK received without gap Transmit packets in transmitter window If timeout for ACK(k), retransmit k, k+1, …[Variation: fast retransmit: after 3DA] Receiver: Receiver window = {P + 1, …., P + N}where P = last received packet without gap When gets a packet in receiver window, ACK withsequence number of next expected packetTOC – Transport – TCP – SWP – GBN – DefinitionWalrand Final Review 2005EECS 122 27Congestion Control: Flows share links:How to share the links bandwidth?TOC – Congestion Control - The Problem 8TCP Algorithm: AIMDCxyA BxC D EyLimit rates:x = yTOC – Congestion Control - TCP Algorithm –AIMD Try to be fair9TCP Algorithm:TOC – Congestion Control - TCP Algorithm –AIMD Slow Start: Start with W = 1 Discover quickly available throughput Increase window fast W = W + 1 at each ACK (exponential over time) When TO: ssthresh = W/2; restart SS until ssthress; CA Congestion Avoidance: AIMD W = W + 1/W at each ACK (linear over time) W = W/2 when congestion is detected (3DA) Fast retransmit + fast recovery After timeout: ssthresh = W/2 SS until ssthresh Timer value: A + 3D A = average, D = deviation Ignore retransmissions in calculations After TO: Double timeout value; reset after new ACK10Refinements: SummaryW164KBX0.5TO3DAX0.53DATOX0.5X0.5SS CASSCA33TOC – Congestion Control - TCP Refinements –Summary 11Flow Control Objective: Avoid saturating destination Algorithm: Receiver avertizes window RAWRAWwindow = min{RAW– OUT, W}whereOUT = Oustanding = Last sent – last ACKedW = Cong. Window from AIMD + refinements[ACK | RAW | …]TOC – Congestion Control - TCP Refinements – Flow Control 12Congestion Control: Summary Slow Start: Discover available bandwidth Congestion Avoidance: AIMD Tries to be fair Refinements: Fast Retransmit: 3DA Fast Recovery: Reset W to W/2 (instead of W = 1)[More precisely: ssthresh = W/2, W = ssthresh + 3, W = W + 1 per DA after 3rdDA,W = ssthresh when get new ACK.] TO: set ssthresh = W/2, W = 1, SS until W = ssthresh, then CA Timers: Timeout = Average + 4 Deviations If time out Timeout x 2Reset after new packet or new ACK Flow Control: Window = min{RAW – OUT, W}TOC – Congestion Control -SummaryWalrand Final Review 2005EECS 122 313DNS Names and Servers Iterated Queries SummaryTOC – Congestion Control -Summary February 5, 2003Abhay Parekh, EE122 S2003: Version draws from Stoica EE122 F200214Names and Serversrooteducomgov milorgnet uk frberkeleymiteecssimsargusrooteducomgov milorgnet uk frberkeleyeecssimsA zone corresponds to an administrative authority that is responsible for that portion of the hierarchy15Iterated QueriesIterated query: Contacted server replies with name of server to contact “I don’t know this name, but ask this server”requesting hostwhistler.cs.cmu.eduwww.berkeley.eduroot name serverlocal name servermango.srv.cs.cmu.edu123467authoritative name serverns1.berkeley.eduintermediate name server(edu server)58iterated query16DNS Summary DNS is a crucial part of the internet Namespace is hierarchical Administration is distributed It is vulnerable in various ways but no more than other parts of the internet infrastructure Its performance is enhanced by caching DNS “Hacks” can enable many interesting things17QoS: Token Buckets/GPS/WFQ Token Buckets GPS WFQ Comparison TB + WFQ18Token Bucketr tokens/sup to s tokensToken CounterPacket BufferWalrand Final Review 2005EECS 122 419GPS: Generalized Processor Sharing Definition: Packets are classified: K classes Each class k has a “weight” wk At each time, scheduler serves backlogged classes at a rate proportional to their weight Notes: This is idealized since scheduler does not respect packet boundaries (mixes bits of different packets) Model is a simple approximation of WFQ Class k is guaranteed a service rate Cwk/Σiwi20GPS…..wKww2Class KD2(t)DK(t)C21WFQ: Weighted Fair Queuing Definition: Packets are classified: K classes Each class j has a “weight” wj At each time, scheduler serves backlogged classes at in increasing order of their departure times under GPS, assuming no more arrivals22Comparison Define Gn= departure time of packet n under GPS Fn= departure time of packet n uner WFQ ThenFn≤ Gn+ M/CwhereM = maximum packet sizeC = link rate23WFQ and TBwCA(s, t) := A(t) – A(s) ≤ σ + ρ(t – s), all 0 ≤ s < tSum of weights = 1Fact: If wC > ρ, then the delay under WFQ is at most (σ/w + M)/CFact: If wC > ρ, then the delay under WFQ is at most (σ/w + M)/C24SecurityContents –Index– Review2 - Security Threats DDOS Cryptography SystemsWalrand Final Review 2005EECS 122 525ThreatsMessage authentication codeEncryption IntegrityConfidentiality Documents Signature, password, watermarkEncryption, relay IdentityPrivacy Users Physical security Virus detectionFirewall, passportPhysicalInfectionIntrusion ComputersDetect/FilterDetect/Isolate?Detect/FilterLink – DDOS- Physical Routers – TablesDNS – DDOSNetwork ProtectionTypeAgainst Contents –Index– Review2 - Security Threats26DDOSContents –Index– Review2 – Security DDOS Distributed Denial of Service Attack Basic Mechanism Saturate a link to a host by sending requests from many nodes across the Internet Effect Host is incapacitated Remedies Verify that source IP exists (i.e., is not spoofed) Block packets that DDOS tools use (some ICMPs) Limit rate of ICMP flows Limit rate of SYNs Trace back from last router upstream to block packets toward that link27CryptographyContents
View Full Document