Part 0: Networking ReviewError controlBit level error detectionParity CheckingInternet checksumRecovering from lost packetsrdt3.0: channels with errors and lossrdt3.0 senderrdt3.0 in actionSlide 10Forward error controlSlide 12Flow Control (in TCP)Principles of Congestion ControlCauses/costs of congestion: scenario 1Causes/costs of congestion: scenario 2Causes/costs of congestion: scenario 3Slide 18Approaches towards congestion controlTCP Congestion ControlTCP congestion control:TCP SlowstartTCP Congestion Avoidance: TahoeSlide 24Network layer functionsNetwork service modelVirtual circuitsVirtual circuits: signaling protocolsDatagram networks: the Internet modelDatagram or VC network: why?RoutingRouting: only two approaches used in practiceDistance Vector Routing AlgorithmHierarchical RoutingSlide 35Intra-AS and Inter-AS routingSlide 37AddressingAddressing: network layerIP AddressingIP addresses: how to get one?Slide 42Link Layer: setting the contextSlide 44Link Layer ServicesLAN Addresses and ARPLAN AddressesLAN Address (more)From IP to MAC addressesARP protocolSlide 51Synthesis: which protocols involved?Protocols involved in http GETSlide 54Slide 55Slide 561-1Part 0: Networking Review Goals: review key topics from intro networks courseequalize backgroundsidentify remedial work ease into courseOverview:overviewerror controlflow controlcongestion controlroutingLANsaddressingsynthesis:“a day in the life”control timescales1-2Error controlreliable point-point communicationgeneric problem: app-to-app, over path, over linkerror model?bits flipped in packetpackets “lostpackets delayed or reorderedprovided serviceservice implementation1-3Bit level error detectionEDC= Error Detection and Correction bits (redundancy)D = Data protected by error checking, may include header fields • Error detection not 100% reliable!• protocol may miss some errors, but rarely• larger EDC field yields better detection and correction1-4Parity CheckingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correct single bit errors00Much more powerful error detection/correction schemes: Cyclic Redundancy Check (CRC)Simple form of forwarderror correction (FEC)1-5Internet checksumSender:treat segment contents as sequence of 16-bit integerschecksum: addition (1’s complement sum) of segment contentssender puts checksum value into UDP checksum fieldReceiver:compute checksum of received segmentcheck if computed checksum equals checksum field value:NO - error detectedYES - no error detected. But maybe errors nonetheless? Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layer only)1-6Recovering from lost packetswhy are packets lost?limited storage, discarded in congestionoutages: eventually reroute around failure (~sec recovery times hopefully)dropped at end system e.g., on NICARQ: Automatic Repeat reQuestsender puts sequence numbers on packets (why)receiver positively or negatively acknowledges correct receipt of packetsender starts (logical) timer for each packet, timeout and retransmits1-7rdt3.0: channels with errors and lossAssumption: underlying channel can corrupt, lose packets (data or ACKs)need checksum, seq. #, ACKs, retransmissions, timerseq #sdetect reorderingACK, NAKingdetect missing packetduplicate detection due to retransmissionsApproach: sender waits “reasonable” amount of time for ACK retransmits if no ACK received in this timeif pkt (or ACK) just delayed (not lost):retransmission will be duplicate, but use of 0,1 seq. #’s already handles thisreceiver must specify seq # of pkt being ACKedrequires countdown timerReference: section 3.4 in K&R1-8rdt3.0 sendersndpkt = make_pkt(0, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)Wait for ACK0rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,1) )wait for call from abovesndpkt = make_pkt(1, data, checksum)udt_send(sndpkt)start_timerrdt_send(data)rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||isACK(rcvpkt,0) )rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) stop_timerstop_timerudt_send(sndpkt)start_timertimeoutudt_send(sndpkt)start_timertimeoutrdt_rcv(rcvpkt)wait for call from aboveWait for ACK1rdt_rcv(rcvpkt)FSM specification of sender (details not important)011-9rdt3.0 in action1-10rdt3.0 in action1-11Forward error controladd redundancy to recover from lossesoriginal file (n blocks)encoded number of blocksencodinglossy channelreceive n(1+) blocksrecover filedecoding1-12Part 0: Networking Review Goals: review key topics from intro networks courseequalize backgroundsidentify remedial work ease into courseOverview:overviewerror controlflow controlcongestion controlroutingLANsaddressingsynthesis:“a day in the life”control timescales1-13Flow Control (in TCP)receiver: explicitly informs sender of (dynamically changing) amount of free buffer space RcvWindow field in TCP segmentsender: keeps the amount of transmitted, unACKed data less than most recently received RcvWindowsender won’t overrunreceiver’s buffers bytransmitting too much, too fastflow controlreceiver bufferingRcvBuffer = size of TCP Receive BufferRcvWindow = amount of spare room in Buffer1-14Principles of Congestion ControlCongestion:informally: “too many sources sending too much data too fast for network to handle”different from flow control!manifestations:lost packets (buffer overflow at routers)long delays (queueing in router buffers)1-15Causes/costs of congestion: scenario 1 two senders, two receiversone router, infinite buffers no retransmissionlarge delays when congestedmaximum achievable throughputunlimited shared output link buffersHost Ain : original dataHost Bout1-16Causes/costs of congestion: scenario 2 one router, finite buffers sender retransmission of lost packetfinite shared output link buffersHost Ain : original dataHost Bout'in : original data, plus retransmitted data‘out : original data, duplicates“costs” of congestion: more work (retrans) for given “goodput”unneeded retransmissions: link carries multiple copies of pkt1-17Causes/costs of congestion: scenario 3 four sendersmultihop pathstimeout/retransmitinQ: what happens as