CS 536 ParkDirect Link Communication I:Basic TechniquesData TransmissionLink speed unit: bps−→ abstraction−→ ignore carrier frequency, coding etc.Point-to-point link:−→ wired or wireless−→ includes broadcast caseCS 536 ParkInterested in completion time:−→ time elapsed between sending/receiving first bit• Single bit:→≈L/SOL (lower bound)→ latency (or propagation delay)→ optical fiber, wireless: exact• Multiple, say S, bits:→≈L/SOL + S/B→ latency + transmission timeLatency vs. transmission time: which dominates?−→ a lot to send, a little to send, ...−→ satellite, Zigbee, WLAN, broadband WANCS 536 ParkMulti-hop link (generalize 2-hop case):• Case 1: B1= B2→ 2(L/SOL + S/B)+ε→ ε: processing overhead at intermediate node→ minor detail: impact of packetization• Case 2: B1<B2• Case 3: B1>B2→ without memory, i.e., buffer: information loss→ loss rate = 1 − (B2/B1) at full throttle→ how much buffer space required for no loss?CS 536 ParkReliable TransmissionPrincipal methodology: ARQ (Automatic Repeat reQuest)−→ use retransmission−→ used in both wired/wireless• function duplication→ link layer, transport layer, etc.• alternative: FEC→ not assured→ hybrid schemesCS 536 ParkThree components:• timer• acknowledgment (ACK)• retransmitdataACKtimerCS 536 ParkStop-and-WaitAssumption: Frame is “lost” due to corruption; discardedby NIC after error detection.datatimeouttimeACKtimeouttimedatatimeouttimedatatimeouttimeACKdatadataACKdataACKdataACKACKCS 536 ParkIssue of RTT (Round-Trip Time) & timer management:• what is proper value of timer?→ RTT estimation• easier for single link→ RTT is more well-behaved• more difficult for multi-hop path in internetwork→ latency + queueing effectCS 536 ParkAnother key problem: not keeping the pipe full.−→ delay-bandwidth product−→ volume of data travelling on the linkHigh throughput: want to keep the pipe fullStop-and-wait throughput (bps):• RTT• frame size (bits)−→ throughput = frame size / RTTCS 536 ParkEx.: Link BW 1.5 Mbps, 45 ms RTT• delay-bandwidth product:→ 1.5 Mbps × 45 ms = 67.5 kb ≈ 8kB• if frame size 1 kB, then throughput:→ 1024 × 8/0.045 = 182 kbps→ utilization: only 182 kbps/1500 kbps = 0.121Solution: increase frame size• brute increase of frame size can be problematic→ bully problem→ existing LAN frame standards (legacy compatible)• send blocks of data, i.e., sequence of framesCS 536 ParkSliding Window Protocol−→ send window/block of dataIssues:• Shield application process from reliability manage-ment chore→ exported semantics: continuous byte stream→ simple app abstraction: e.g., read system call• Both sender and receiver have limited buffer capacity→ efficiency: space-bounded computation→ task: “plug holes & flush”Sender Receiver12345345Dropped12CS 536 ParkSimple solution when receiver has infinite buffer capacity:• sender keeps sending at maximum speed• receiver informs sender of holes→ i.e., negative ACK• sender retransmits missing frames−→ sender’s buffer capacity?−→ need for positive ACK?With finite buffer:−→ issue of bookkeepingFlow control & congestion control:→ sending too much is counterproductive→ regulate sending rateCS 536 ParkSet-up:SWSLAR LFSRWSNFE LFASender:Receiver:• SWS: Sender Window Size (sender buffer size)• RWS : Receiver Window Size (receiver buffer size)• LAR: Last ACK Received• LFS: Last Frame Sent• NFE: Next Frame Expected• LFA: Last Frame AcceptableCS 536 ParkAssign sequence numbers to frames.−→ IDsMaintain invariants:• LFA − NFE+1≤ RWS• LFS − LAR + 1 ≤ SWSSender:• Receive ACK with sequence number X• Forwind LAR to X• Flush buffer up to (but not including) LAR• Send up to SWS − (LFS − LAR + 1) frames• Update LFSCS 536 ParkReceiver:• Receive packet with sequence number Y• Forwind to (new) first hole & update NFE→ NFE need not be Y +1• Send cumulative ACK (i.e., NFE)• Flush buffer up to (but not including) NFE to appli-cation• Update LFA ← NFE + RWS − 1CS 536 ParkACK variants:• piggyback• negative ACKs• selective ACKsSequence number wrap-around problem:SWS < (MaxSeqNum + 1)/2.−→ note: stop-and-wait is special binary