Multiple AccessSlide 2Shared MediaMultiple Access protocolsChannel PartitioningComputer Network CharacteristicsIdeal Multiple Access ProtocolRandom Access ProtocolsSlotted ALOHASlide 10Slotted Aloha efficiencyOptimal choice of pPure (unslotted) ALOHAPure Aloha efficiencyCarrier Sense Multiple AccessCSMA collisionsCSMA/CD (Collision Detection)CSMA/CD collision detectionEthernetEthernet TopologiesEthernet ConnectivitySlide 22Slide 23Ethernet Frame StructureEthernet Frame Structure (more)Ethernet SpecificationsEthernet MAC AlgorithmCollisionsCollision DetectionSlide 30RetransmissionBinary Exponential BackoffSlide 33CSMA/CD efficiencyFrame ReceptionCollision Detection Techniques: Bus TopologyCollision Detection Techniques: Hub Topology10Mbps Ethernet Media100Mbps Ethernet MediaEthernet in PracticeMultiple AccessReadings: Peterson & Davie, 2.6.2, 2.7, 2.8.2Multiple AccessMultiple hosts sharing the same mediumWhat are the new problems?Shared MediaEthernet busRadio channelToken ring network…Multiple Access protocolsSingle shared broadcast channel Two or more simultaneous transmissions by nodes: interference Collision if node receives two or more signals at the same timeMultiple Access ProtocolDistributed algorithm that determines how nodes share channel, i.e., determine when node can transmitCommunication about channel sharing must use channel itself! No out-of-band channel for coordinationChannel PartitioningFrequency Division MultiplexingEach node has a frequency bandTime Division MultiplexingEach node has a series of fixed time slotsWhat networks are these good for?Computer Network CharacteristicsTransmission needs varyBetween different nodesOver timeNetwork is not fully utilizedIdeal 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 transmissionsno synchronization of clocks, slots4. SimpleRandom Access ProtocolsWhen node has packet to sendtransmit at full channel data rate R.no a priori coordination among nodestwo or more transmitting nodes ➜ “collision”,random access MAC protocol specifies: how to detect collisionshow to recover from collisions (e.g., via delayed retransmissions)Examples of random access MAC protocols:slotted ALOHAALOHACSMA, CSMA/CD, CSMA/CASlotted ALOHAAssumptionsall frames same sizetime is divided into equal size slots, time to transmit 1 framenodes start to transmit frames only at beginning of slotsnodes are synchronizedif 2 or more nodes transmit in slot, all nodes detect collisionOperationwhen node obtains fresh frame, it transmits in next slotno collision, node can send new frame in next slotif collision, node retransmits frame in each subsequent slot with prob. p until successSlotted ALOHAProssingle active node can continuously transmit at full rate of channelhighly decentralized: only slots in nodes need to be in syncsimpleConscollisions, wasting slotsidle slotsnodes may be able to detect collision in less than time to transmit packetclock synchronizationSlotted Aloha efficiencyEfficiency is the long-run fraction of successful slots when there are many nodes, each with many frames to sendSuppose N nodes with many frames to send, each transmits in slot with probability pprob that node 1 has success in a slot = p(1-p)N-1prob that any node has a success = Np(1-p)N-1Optimal choice of p For max efficiency with N nodes, find p* that maximizes Np(1-p)N-1For many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives 1/e = .37Efficiency is 37%, even with optimal pPure (unslotted) ALOHAunslotted Aloha: simpler, no synchronizationwhen 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) = .18 Even worse !Carrier Sense Multiple AccessCSMA: listen before transmit:If channel sensed idle: transmit entire frameIf channel sensed busy, defer transmission Human analogy: don’t interrupt others!CSMA collisionscollisions can still occur:propagation delay means two nodes may not heareach other’s transmissioncollision:entire packet transmission time wastednote:role of distance & propagation delay in determining collision probabilityCSMA/CD (Collision Detection)CSMA/CD: carrier sensing, deferral as in CSMAcollisions detected within short timecolliding transmissions aborted, reducing channel wastage collision detection: easy in wired LANs: measure signal strengths, compare transmitted, received signalsdifficult in wireless LANs: receiver shut off while transmittinghuman analogy: the polite conversationalistCSMA/CD collision detectionEthernetdominant wired LAN technology: cheap $20 for 100Mbs!first widely used LAN technologySimpler, cheaper than token LANs and ATMKept up with speed race: 10 Mbps – 10 Gbps Metcalfe’s EthernetsketchEthernet TopologiesBus Topology: SharedAll nodes connected to a wireStar Topology: All nodes connected to a central repeaterEthernet Connectivity10Base5 – ThickNet< 500mControllerVampire TapTransceiverBus TopologyEthernet Connectivity10Base2 – ThinNet< 200mControllerBNC T-JunctionTransceiverBus TopologyEthernet Connectivity10BaseT< 100mControllerStar TopologyEthernet Frame StructureSending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet framePreamble: 7 bytes with pattern 10101010 followed by one byte with pattern 10101011Used to synchronize receiver, sender clock rates (Manchester encoding)Ethernet Frame Structure (more)Addresses: 6 bytesif adapter receives frame with matching destination address, or with broadcast address (eg ARP packet), it passes data in frame to net-layer protocolotherwise, adapter discards frameType: indicates the higher layer protocol (mostly IP but others may be supported such as Novell IPX and AppleTalk)CRC: checked at receiver, if error is detected, the frame is simply
View Full Document
Unlocking...