ECE544: Communication Networks-II Spring 2010Today’s LectureLink Layer: IntroductionLink Layer ServicesLink Layer CommunicationLayer 2 vs. Layer 3Slide 7Binary EncodingManchester EncodingPoint-to-Point Data Link ProtocolPPP FunctionsPPP Data FrameByte StuffPPP Link Control Protocol (LCP)High-Level Data Link Control (HDLC)Error DetectionParity CheckingInternet ChecksumCyclic Redundancy Check (CRC)CRC ExampleAutomatic Repeat reQuest(ARQ)Sliding WindowSliding Window (Cont)Sliding WindowShared Media NetworksMedium Access SublayerMedia Access ProtocolMAC ClassificationPure (Unslotted) ALOHAAloha AlgorithmPure Aloha efficiencyAnother Method to Analyze AlohaSlotted AlohaEfficiency of Slotted ALOHAAnother Method to Analyze Slotted AlohaPerformance of ALOHACarrier Sense Multiple Access (CSMA)Non-persistent CSMA1-persistent CSMAP-persistent CSMAPropagation DelayCSMA Performance AnalysisAnalysis of Non-persistent CSMAComparison of the channel utilization versus load for various random access protocolsCSMA with Collision DetectionHow to Detect CollisionCSMA/CAProblems with carrier sensingSlide 49Solving Hidden Node problem with RTS/CTSRTS/CTS exchange example“Taking Turns” MAC protocolsTDMAFixed TDMADynamic TDMAFDMASpread Spectrum and CDMASpread SpectrumSpread Spectrum (cont)Code Division Multiple Access (CDMA)LAN technologiesEthernet OverviewEthernet FrameMAC AddressMAC Address vs. IP AddressDifferent Flavors of Ethernet FormatUnreliable, connectionless serviceEthernet CSMA/CDEthernet CSMA/CD (Cont)Collisions10BaseT and 100BaseTLegacy EthernetGbit EthernetEthernet PerformanceToken Ring OverviewToken Ring (cont)Timed Token AlgorithmToken Ring PriorityFailure DetectionToken MaintenanceWireless LANsToday’s HomeworkECE544: Communication Networks-II Spring 2010D. RaychaudhuriLecture IIIncludes teaching materials from L. Peterson, J. KuroseToday’s Lecture•Recap of network architecture & top-down design–architecture paper discussion•Shared media (MAC) protocols–Ethernet–Token ring–IEEE 802.11Link Layer: Introduction•Some terminology:–hub/repeater (layer 1), bridge/LAN switch (layer 2), router (layer 3), host (layers 1-3 + app)–Links are communication channels that connect adjacent nodes along communication path (point-to-point, shared, wired, wireless)–Layer-2 frame: encapsulates payload/datagram/IP packet/service unitRouterSwitchLinkHostLinkLAN 1LAN 2SwitchLinkHostLink Layer Services•Data-link layer: transfer datagram from one node to adjacent node over a link–Framing: encapsulate datagram into frame, adding header, trailer. •Identify what set of bits constitute a frame, that is, determining the beginning and the end of a frame–channel access if shared medium•MAC addresses used in frame headers to identify source, destination•different from IP address!–Reliable delivery between adjacent nodes•Error detection •Error recovery: forward error correction code, retransmission (ARQ)Link Layer Communication•Link layer implemented in adaptor (NIC) and driver (Ethernet card, WLAN card)•Sending side: encapsulates higher layer payload in a frame, adds error checking bits, flow control, etc.•Receiving side: error detection, flow control, extracts payload, passes to the receiving nodeCPUCacheMemoryControl status registerBus interfaceLinkinterfaceHostNICI/ObusNetworkDatagramFrameAdaptorSendingnodeDatagramFrameAdaptorRecvnodeLink layer protocolLayer 2 vs. Layer 3 •Layer 2 switching–Based on MAC address–Self configuring and plug & play–Transparent to protocols above the MAC layer –Fast and inexpensive–Does not limit the scope of broadcasts –Does not scale to extremely large networks •Layer 3 routing–Based on IP address–Must get IP address (DHCP or manual assign)–Easily connect LANs that uses different link protocols–Scalable to large network by subnet routing–Broadcast limited only in a subnet•Link Layer Techniques–Encoding (more Physical Layer stuff)–Framing & PPP Protocol–Error Detection & Correction –ARQ•Self study topics (see Ch2 & slides)Binary Encoding•Binary Encoding: turn the binary data (bits) into signals to transmit on cable or optical fiber link (physical layer stuff, but better to know)•Baseband, not modulate to high frequency•Nonreturn To Zero (NRZ): 1=high signal, 0=low signal–May stay on high or low signal too long for a long strings of consecutive 1s or 0s => baseline wander, clock recovery problems.•Nonreturn to Zero Inverted (NRZI): 1 = signal transition (low to high, or high to low), 0=no change.–Solve the problem of consecutive 1s, but not consecutive 0sManchester Encoding •Manchester Encoding: NRZ_encode data XOR clock –Clock cycle (a low/high pair) = 2 x signal interval–Baud rate (the signal change rate) = 2 x bitrate–0 =high-to-low transition, 1 = low-to-high transition–Clock recovery•Variation: Differential Manchester–1 = the first half of the signal equal to the last half of the previous bit’s signal–0 = the first half of the signal opposite to the last half of the previous bit’s signal1 1101 0000 11 0BitsNRZClockManchesterNRZIPoint-to-Point Data Link Protocol•Two types of links–point-to-point link (easier than broadcast link)•one sender, one receiver on the link, NO Media Access Control•no need for explicit MAC addressing•e.g., dialup link, ISDN line–Broadcast (shared wire or medium)•popular point-to-point DLC protocols:–PPP (point-to-point protocol): byte-oriented•PPP for dial-up access•PPP over Ethernet (DSL)–HDLC (High level data link control): bit-orientedPPPModemPPP Functions•Framing: encapsulation of network-layer datagram in data link frame –Identify what set of bits constitute a frame, that is, determining the beginning and the end of a frame•carry data of any network layer protocol (not just IP) at same time–ability to demultiplex upwards•bit transparency: must carry any bit pattern in the data field•error detection (no correction)•connection liveness: detect, signal link failure to network layer•network layer address negotiation: endpoint can learn/configure each other’s network address•PPP –no error correction/recovery–no flow control–out of order delivery OK –no need to support multipoint links (e.g., polling)PPP Data Frame•Flag: delimiter (framing)•Address: •Control: •Protocol: upper layer protocol to which frame carried (e.g. IP)•Info: upper layer data•Check: