Multiple AccessReadings: Peterson & Davie,2.6.2, 2.7, 2.8.2Multiple Access Multiple hosts sharing the samemedium What are the new problems?Shared Media Ethernet bus Radio channel Token ring network …Multiple Access protocols Single shared broadcast channel Two or more simultaneous transmissions by nodes:interference Collision if node receives two or more signals at the same timeMultiple Access Protocol Distributed algorithm that determines how nodes sharechannel, i.e., determine when node can transmit Communication about channel sharing must use channelitself! No out-of-band channel for coordinationChannel Partitioning Frequency Division Multiplexing Each node has a frequency band Time Division Multiplexing Each node has a series of fixed time slots What networks are these good for?Computer NetworkCharacteristics Transmission needs vary Between different nodes Over time Network is not fully utilizedIdeal Multiple Access ProtocolBroadcast channel of rate R bps1. When one node wants to transmit, it cansend at rate R.2. When M nodes want to transmit, each cansend at average rate R/M3. Fully decentralized: no special node to coordinate transmissions no synchronization of clocks, slots4. SimpleRandom Access Protocols When node has packet to send transmit at full channel data rate R. no a priori coordination 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 delayedretransmissions) Examples of random access MAC protocols: slotted ALOHA ALOHA CSMA, CSMA/CD, CSMA/CASlotted ALOHAAssumptions all frames same size time is divided into equalsize slots, time totransmit 1 frame nodes start to transmitframes only at beginningof slots nodes are synchronized if 2 or more nodestransmit in slot, all nodesdetect collisionOperation when node obtains freshframe, it transmits in nextslot no collision, node can sendnew frame in next slot if collision, noderetransmits frame in eachsubsequent slot with prob.p until successSlotted ALOHAPros single active node cancontinuously transmit at fullrate of channel highly decentralized: onlyslots in nodes need to be insync simpleCons collisions, wasting slots idle slots nodes may be able todetect collision in lessthan time to transmitpacket clock synchronizationSlotted Aloha efficiency Efficiency is the long-run fraction of successfulslots when there are many nodes, each withmany frames to send Suppose N nodes with many frames to send,each transmits in slot with probability p prob that node 1 has success in a slot = p(1-p)N-1 prob that any node has a success = Np(1-p)N-1Optimal choice of p For max efficiency with N nodes, find p* thatmaximizesNp(1-p)N-1 For many nodes, take limit of Np*(1-p*)N-1 as Ngoes to infinity, gives 1/e = .37 Efficiency is 37%, even with optimal pPure (unslotted) ALOHA unslotted Aloha: simpler, no synchronization when frame first arrives transmit immediately collision probability increases: frame sent at t0 collides with other frames sent in[t0-1,t0+1]Pure Aloha efficiencyP(success by given node) = P(node transmits) . P(no other node transmits in [t0-1,t0] . P(no other node transmits in [t0,t0+1] = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) … choosing optimum p and then letting n -> ∞ ... Efficiency = 1/(2e) = .18Even worse !Carrier Sense Multiple AccessCSMA: listen before transmit:If channel sensed idle: transmit entire frame If channel sensed busy, defer transmission Human analogy: don’t interrupt others!CSMA collisionscollisions can still occur:propagation delay meanstwo nodes may not heareach other’s transmissioncollision:entire packet transmissiontime wastednote:role of distance & propagationdelay in determining collisionprobabilityCSMA/CD (Collision Detection)CSMA/CD: carrier sensing, deferral as in CSMA collisions detected within short time colliding transmissions aborted, reducing channelwastage collision detection: easy in wired LANs: measure signal strengths,compare transmitted, received signals difficult in wireless LANs: receiver shut off whiletransmitting human analogy: the polite conversationalistCSMA/CD collision detectionEthernetdominant wired LAN technology: cheap $20 for 100Mbs! first widely used LAN technology Simpler, cheaper than token LANs and ATM Kept up with speed race: 10 Mbps – 10 GbpsMetcalfe’s EthernetsketchEthernet TopologiesBus Topology: SharedAll nodes connectedto a wireStar Topology:All nodes connected to acentral repeaterEthernet Connectivity10Base5 –ThickNet< 500mControllerVampire TapTransceiverBus TopologyEthernet Connectivity10Base2 –ThinNet< 200mControllerBNC T-JunctionTransceiverBus TopologyEthernet Connectivity10BaseT< 100mControllerStar TopologyEthernet Frame StructureSending adapter encapsulates IP datagram (or othernetwork layer protocol packet) in Ethernet framePreamble: 7 bytes with pattern 10101010 followed by one bytewith pattern 10101011 Used to synchronize receiver, sender clock rates(Manchester encoding)Ethernet Frame Structure(more) Addresses: 6 bytes if adapter receives frame with matching destinationaddress, or with broadcast address (eg ARP packet), itpasses data in frame to net-layer protocol otherwise, adapter discards frame Type: indicates the higher layer protocol (mostly IPbut others may be supported such as Novell IPXand AppleTalk) CRC: checked at receiver, if error is detected, theframe is simply droppedEthernet Specifications Coaxial Cable Up to 500m Taps > 2.5m apart Transceiver Idle detection Sends/Receives signal Repeater Joins multiple Ethernet segments < 5 repeaters between any two hosts < 1024 hostsEthernet MAC Algorithm Sender/Transmitter If line is idle (carrier sensed) Send immediately Send maximum of 1500B data (1527B total) Wait 9.6 µs before sending again If line is busy (no carrier sense) Wait until line becomes idle Send immediately If collision detected Stop sending and jam signal Try again laterCollisionsA BHow can we ensure that A knows about the collision?Collision Detection
View Full Document
Unlocking...