Review❒ Multicast Routing❍ Three options❍ source-based tree: one tree per source• shortest path trees•reverse path forwarding❍ group-shared tree: group uses one tree• minimal spanning (Steiner) • center-based trees❒ Data Link Layer Services❍ Error detection•Single bit •Two dimensional❒ Recitation tomorrow for Project 3Some slides are in courtesy of J. Kurose and K. RossOverview❒ Error Detection: CRC❒ Multiple access protocols❒ LAN addresses and ARP❒ EthernetChecksumming: Cyclic Redundancy Check❒ view data bits, D, as a binary number❒ choose r+1 bit pattern (generator), G❒ goal: choose r CRC bits, R, such that❍ <D,R> exactly divisible by G (modulo 2) ❍ receiver knows G, divides <D,R> by G. If non-zero remainder: error detected!❍ can detect all burst errors less than r+1 bits❒ widely used in practice (ATM, HDCL)CRC ExampleWant:D.2rXOR R = nGequivalently:D.2r= nG XOR R equivalently:if we divide D.2rby G, want remainder RR = remainder[ ]D.2rGOverview❒ Error Detection: CRC❒ Multiple access protocols❒ LAN addresses and ARP❒ EthernetMultiple 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 LANMultiple 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!Ideal Multiple 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. SimpleMAC Protocols: a taxonomyThree broad classes:❒ Channel Partitioning❍ divide channel into smaller “pieces” (time slots, frequency, code) – TDMA, FDMA, CDMA❍ allocate piece to node for exclusive use❒Random Access❍ channel not divided, allow collisions❍ “recover” from collisionsRandom Access Protocols❒ When node has packet to send❍ transmit at full channel data rate R.❍ no a prioricoordination among nodes❒two or more transmitting nodes -> “collision”,❒ random access MAC protocol specifies: ❍ how to detect collisions❍ how to recover from collisions (e.g., via delayed retransmissions)❒Examples of random access MAC protocols:❍ slotted ALOHA❍ ALOHA❍ CSMA, CSMA/CD, CSMA/CASlotted ALOHAAssumptions❒ all frames same size❒ time is divided into equal size slots, time to transmit 1 frame❒ nodes start to transmit frames only at beginning of slots❒ nodes are synchronized❒ if 2 or more nodes transmit in slot, all nodes detect collisionOperation❒ when node obtains fresh frame, it transmits in next slot❒ no collision, node can send new frame in next slot❒ if collision, node retransmits frame in each subsequent slot with prob. p until successSlotted ALOHAPros❒ single active node can continuously transmit at full rate of channel❒ highly decentralized: only slots in nodes need to be in sync❒ simpleCons❒ collisions, wasting slots❒ idle slots❒ nodes may be able to detect collision in less than time to transmit packetSlotted Aloha efficiency❒ Suppose N nodes with many frames to send, each transmits in slot with probability p❒ prob that 1st node has success in a slot= p(1-p)N-1❒ prob that any node has a success = Np(1-p)N-1❒ For max efficiency with N nodes, find p* that maximizes Np(1-p)N-1❒ For many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives 1/e = .37Efficiency is the long-run fraction of successful slots when there’s many nodes, each with many frames to sendAt best:channelused for useful transmissions 37%of time!CSMA (Carrier Sense Multiple Access)CSMA: listen before transmit:❒ If channel sensed idle: transmit entire frame❒ If channel sensed busy, defer transmission ❒ Human analogy: don’t interrupt others!CSMA collisionscollisions canstill occur:propagation delay means two nodes may not heareach other’s transmissioncollision:entire packet transmission time wastedspatial layout of nodes note:role of distance & propagation delay in determining collision probabilityCSMA/CD (Collision Detection)CSMA/CD: carrier sensing, deferral as in CSMA❍ collisions detectedwithin short time❍ colliding transmissions aborted, reducing channel wastage ❒ collision detection:❍ easy in wired LANs: measure signal strengths, compare transmitted, received signals❍ difficult in wireless LANs: receiver shut off while transmitting❒ human analogy: the polite conversationalistCSMA/CD collision detectionSummary of MAC protocols❒ What do you do with a shared media?❍ Channel Partitioning, by time, frequency or code• Time Division,Code Division, Frequency Division❍ Random partitioning (dynamic), • ALOHA, CSMA, CSMA/CD• carrier sensing: easy in some technologies (wire), hard in others (wireless)• CSMA/CD used in EthernetOverview❒ Error Detection: CRC❒ Multiple access protocols❒ LAN addresses and ARP❒ EthernetLAN technologiesData link layer so far:❍ services, error detection/correction, multiple access Next: LAN technologies❍ addressing❍ Ethernet❍ hubs, bridges, switches❍ 802.11❍ PPP❍ ATMLAN Addresses and ARP32-bit IP address:❒network-layeraddress❒ used to get datagram to destination IP network (recall IP network definition)LAN (or MAC or physical or Ethernet) address: ❒ used to get datagram from one interface to another physically-connected interface (same network)❒ 48 bit MAC address (for most LANs) burned in the adapter ROMLAN Addresses and ARPEach adapter on LAN has unique LAN addressLAN Address (more)❒ MAC address allocation administered by IEEE❒ manufacturer buys portion of MAC address space (to assure uniqueness)❒ Analogy:(a) MAC address: like Social Security Number(b) IP address: like postal address❒ MAC flat address => portability ❍ can move LAN card from one LAN to another❒IP hierarchical address NOT portable❍ depends on IP network to which node is attachedRecall earlier routing