Link Layer: IntroductionLink layer: contextLink Layer ServicesLink Layer Services (more)Adaptors CommunicatingError DetectionMultiple Access Links and ProtocolsMultiple Access protocolsDesired PropertiesClassification of MAC protocolsIdeal Mulitple Access ProtocolMAC Protocols: a taxonomyChannel Partitioning MAC protocols: TDMAChannel Partitioning MAC protocols: FDMAChannel Partitioning (CDMA)CDMA Encode/DecodeCDMA: two-sender interferenceRandom Access ProtocolsSlotted ALOHASlide 20Slotted Aloha efficiencySlotted ALOHA AnalysisPure (unslotted) ALOHAPure Aloha efficiencyPure Aloha AnalysisCSMA (Carrier Sense Multiple Access)CSMA collisions“Taking Turns” MAC protocolsSlide 29Summary of MAC protocolsNetwork Layer 4-1Link Layer: IntroductionSome terminology:hosts and routers are nodes (bridges and switches too)communication channels that connect adjacent nodes along communication path are linkswired linkswireless linksLANs2-PDU is a frame, encapsulates datagram“link”data-link layer has responsibility of transferring datagram from one node to adjacent node over a linkNetwork Layer 4-2Link layer: contextDatagram transferred by different link protocols over different links:e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last linkEach link protocol provides different servicese.g., may or may not provide rdt over linktransportation analogytrip from Princeton to Lausannelimo: Princeton to JFKplane: JFK to Genevatrain: Geneva to Lausannetourist = datagramtransport segment = communication linktransportation mode = link layer protocoltravel agent = routing algorithmNetwork Layer 4-3Link Layer ServicesFraming, link access: encapsulate datagram into frame, adding header, trailerchannel access if shared medium‘physical addresses’ used in frame headers to identify source, dest •different from IP address!Reliable delivery between adjacent nodeswe learned how to do this alreadyseldom used on low bit error link (fiber, some twisted pair)wireless links: high error rates•Q: why both link-level and end-end reliability?Network Layer 4-4Link Layer Services (more)Flow Control: pacing between adjacent sending and receiving nodesError Detection: errors caused by signal attenuation, noise. receiver detects presence of errors: •signals sender for retransmission or drops frame Error Correction: receiver identifies and corrects bit error(s) without resorting to retransmissionHalf-duplex and full-duplexwith half duplex, nodes at both ends of link can transmit, but not at same timeNetwork Layer 4-5Adaptors Communicatinglink layer implemented in “adaptor” (aka NIC)Network cardsending side:encapsulates datagram in a frameadds error checking bits, rdt, flow control, etc.receiving sidelooks for errors, rdt, flow control, etcextracts datagram, passes to rcving nodesendingnodeframercvingnodedatagramframeadapteradapterlink layer protocolNetwork Layer 4-6Error 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 correctionNetwork Layer 4-7Multiple Access Links and ProtocolsTwo types of “links”:point-to-pointPPP for dial-up accesspoint-to-point link between Ethernet switch and hostbroadcast (shared wire or medium)traditional Ethernetupstream HFC802.11 wireless LANNetwork Layer 4-8Multiple Access protocolssingle shared broadcast channel two or more simultaneous transmissions by nodes: interference only one node can send successfully at a time multiple access protocoldistributed algorithm that determines how nodes share channel, i.e., determine when node can transmitcommunication about channel sharing must use channel itself! what to look for in multiple access protocols:Network Layer 4-9Desired PropertiesA way to share the common transmission channel. The protocol must control the way in which users access the channel.Use medium efficiently– maximize throughput.Fair allocation of resources. Should handle different traffic types.Protocol should be stable– increase in load should not make the system unstable.Robust w.r.t equipment failure or changing conditions. Any user not obeying the rules should affect the rest as little as possible.Network Layer 4-10Classification of MAC protocolsNetwork Layer 4-11Ideal Mulitple Access ProtocolBroadcast channel of rate R bps1. When one node wants to transmit, it can send at rate R.2. When M nodes want to transmit, each can send at average rate R/M3. Fully decentralized:no special node to coordinate transmissionsno synchronization of clocks, slots4. SimpleNetwork Layer 4-12MAC Protocols: a taxonomyThree broad classes:Channel Partitioningdivide channel into smaller “pieces” (time slots, frequency, code)allocate piece to node for exclusive useRandom Accesschannel not divided, allow collisions“recover” from collisions“Taking turns”tightly coordinate shared access to avoid collisionsNetwork Layer 4-13Channel Partitioning MAC protocols: TDMATDMA: time division multiple access access to channel in "rounds" each station gets fixed length slot (length = pkt trans time) in each round unused slots go idle example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle TDM (Time Division Multiplexing): channel divided into N time slots, one per user; inefficient with low duty cycle users and at light load.Network Layer 4-14Channel Partitioning MAC protocols: FDMAFDMA: frequency division multiple access channel spectrum divided into frequency bandseach station assigned fixed frequency bandunused transmission time in frequency bands go idle example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle frequency bandstimeNetwork Layer 4-15Channel Partitioning (CDMA)CDMA (Code Division Multiple Access) unique “code” assigned to each user; i.e., code set partitioningused mostly in wireless broadcast channels (cellular, satellite, etc)all users share same frequency, but each user has own “chipping” sequence (i.e., code) to encode dataencoded signal = (original data) X (chipping sequence)decoding: inner-product of encoded signal and chipping sequenceallows multiple