1Stan KurkovskyComputer NetworksComputer NetworksLink Layer ServicesLink Layer ServicesError Correction and DetectionError Correction and DetectionBased on Computer Networking, 4thEdition by Kurose and RossStan KurkovskyLink Layer: IntroductionLink Layer: IntroductionSome terminology:Some terminology:•• hosts and routers are hosts and routers are nodesnodes•• communication channels that communication channels that connect adjacent nodes along connect adjacent nodes along communication path are communication path are linkslinks•• wired linkswired links•• wireless linkswireless links•• LANsLANs•• layerlayer--2 packet is a 2 packet is a frameframe,,encapsulates datagramencapsulates datagram••datadata--link layerlink layer has responsibility of has responsibility of transferring datagram from one node transferring datagram from one node to adjacent node over a linkto adjacent node over a link“link”2Stan KurkovskyLink layer: contextLink layer: context•• Datagram transferred by different link protocols over different links:Datagram transferred by different link protocols over different links:•• e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last linklink•• Each link protocol provides different servicesEach link protocol provides different services•• e.g., may or may not provide rdt over linke.g., may or may not provide rdt over linktransportation analogytransportation analogy•• trip from Princeton to Lausannetrip from Princeton to Lausanne•• limo: Princeton to JFKlimo: Princeton to JFK•• plane: JFK to Genevaplane: JFK to Geneva•• train: Geneva to Lausannetrain: Geneva to Lausanne•• tourist = tourist = datagramdatagram•• transport segment = transport segment = communication linkcommunication link•• transportation mode = transportation mode = link layer protocollink layer protocol•• travel agent = travel agent = routing algorithmrouting algorithmStan KurkovskyLink Layer ServicesLink Layer ServicesFraming, link access:Framing, link access:•• encapsulate datagram into frame, encapsulate datagram into frame, adding header, traileradding header, trailer•• channel access if shared mediumchannel access if shared medium•• “MAC” addresses used in frame “MAC” addresses used in frame headers to identify source, dest headers to identify source, dest •• different from IP address!different from IP address!Reliable delivery between adjacent Reliable delivery between adjacent nodesnodes•• we learned how to do this already we learned how to do this already (chapter 3)!(chapter 3)!•• seldom used on low bit error link seldom used on low bit error link (fiber, some twisted pair)(fiber, some twisted pair)•• wireless links: high error rateswireless links: high error rates•• Q: why both linkQ: why both link--level and endlevel and end--end reliability?end reliability?Flow Control:Flow Control:•• pacing between adjacent sending pacing between adjacent sending and receiving nodesand receiving nodesError Detection:Error Detection:•• errors caused by signal attenuation, errors caused by signal attenuation, noise. noise. •• receiver detects presence of errors: receiver detects presence of errors: •• signals sender for retransmission signals sender for retransmission or drops frame or drops frame Error Correction:Error Correction:•• receiver identifies receiver identifies and correctsand correctsbit bit error(s) without resorting to error(s) without resorting to retransmissionretransmissionHalfHalf--duplex and fullduplex and full--duplexduplex•• with half duplex, nodes at both ends with half duplex, nodes at both ends of link can transmit, but not at same of link can transmit, but not at same timetime3Where Is the Link Layer Implemented?Where Is the Link Layer Implemented?•• in each and every hostin each and every host•• link layer implemented in link layer implemented in “adaptor” (aka “adaptor” (aka network network interface cardinterface cardNIC)NIC)•• Ethernet card, PCMCI card, Ethernet card, PCMCI card, 802.11 card802.11 card•• implements link, physical implements link, physical layerlayer•• attaches into host’s system attaches into host’s system busesbuses•• combination of hardware, combination of hardware, software, firmwaresoftware, firmwareStan Kurkovskycontrollerphysicaltransmissioncpu memoryHost bus (e.g., PCI)network adaptercardhost schematicapplicationtransportnetworklinklinkphysicalStan KurkovskyAdaptors CommunicatingAdaptors Communicating•• sending sending side:side:•• encapsulates datagram in a frameencapsulates datagram in a frame•• adds error checking bits, adds error checking bits, rdtrdt, flow control, etc., flow control, etc.•• receiving sidereceiving side•• looks for errors, looks for errors, rdtrdt, flow control, etc, flow control, etc•• extracts datagram, passes to extracts datagram, passes to rcvingrcving nodenode•• adapter is semiadapter is semi--autonomousautonomous•• link & physical layerslink & physical layerssendingnodeframercvingnodedatagramframeadapteradapterlink layer protocol4Stan KurkovskyError DetectionError Detection•• EDC= Error Detection and Correction bits (redundancy)EDC= Error Detection and Correction bits (redundancy)•• D = Data protected by error checking, may include header fields D = Data protected by error checking, may include header fields •• Error detection not 100% reliable!Error detection not 100% reliable!•• protocol may miss some errors, but rarelyprotocol may miss some errors, but rarely•• larger EDC field yields better detection and correctionlarger EDC field yields better detection and correctionStan KurkovskyParity CheckingParity CheckingSingle Bit Parity:Single Bit Parity:Detect single bit errorsDetect single bit errorsTwo Dimensional Bit ParityTwo Dimensional Bit Parity::Detect Detect and correctand correctsingle bit errorssingle bit errors5Stan KurkovskyInternet checksumInternet checksumGoal:Goal: detect “errors” (e.g., flipped bits) in transmitted segment (note: used detect “errors” (e.g., flipped bits) in transmitted segment (note: used at transport layerat transport layeronlyonly))Sender:Sender:•• treat segment contents as sequence of 16treat segment contents as sequence of 16--bit integersbit