EECS 122: Introduction to Computer Networks Multiaccess ProtocolsISO OSI Reference Model for LayersUp Until Now...This LectureMedium Access ProtocolsProblem StatementWhat Layer?Focus of LectureWhere it all Started: AlohaNetAloha Transmission StrategySimple, but Radical in Concept!Why Better than Time Slot Schemes?Variation: Slotted AlohaPerformance of Slotted AlohaEfficiency of Slotted AlohaEthernetCSMA and CSMA/CDCSMA: Carrier Sense Multiple AccessCSMA collisionsCSMA/CD (Collision Detection)CSMA/CD Collision DetectionEthernet Frame StructureEthernet Frame Structure (more)Ethernet’s CSMA/CDEthernet’s CSMA/CD (more)Next Few SlidesMinimum Packet SizeMinimum Packet Size (more)Ethernet Technologies: 10Base210BaseT and 100BaseT10BaseT and 100BaseT (more)GigaBit EthernetInterconnecting LANsEthernet vs 802.11802.11Physical LinkCollision Avoidance: The ProblemsMultiple Access with Collision Avoidance (MACA)Other NodesSummaryWhat You Need to KnowKatz, Stoica F04EECS 122: Introduction to Computer Networks Multiaccess ProtocolsComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04ISO OSI Reference Model for LayersApplicationPresentationSessionTransportNetworkDatalinkPhysicalService: -Framing (attach frame separators) -Send data frames between peers-Others:•Arbitrate the access to common physical media•Per-hop reliable transmission•Per-hop flow controlMedia Access3Katz, Stoica F04Up Until Now...Short-term contention is lossless: just wait-Main resource (link bandwidth) is controlled by router-Router deals with short-term contention by queueing packets-Switch algorithms and router buffers ensure no packets are dropped due to short-term contentionHave focused on managing long-term contention-Queueing schemes (FQ, FIFO, RED, etc.)-End-to-end congestion control (TCP)4Katz, Stoica F04This LectureShort-term contention for media yields losses!Focus on networking over shared media-Ethernet-Short-range radio (e.g., wireless LANs)-Long-range radio (e.g., packet radio, satellite)AKA “multiple-access” problem-Don’t go through central router to get access to link-Instead, multiple users can access shared medium5Katz, Stoica F04Medium Access ProtocolsChannel partitioning-Divide channel into smaller “pieces” (e.g., time slots, frequency, code selection)-Allocate a piece to given node for exclusive useRandom access-Allow collisions-“Recover” from collisions“Taking-turns”-Tightly coordinate shared access to avoid collisions6Katz, Stoica F04Problem StatementManaging shared media-If two users send at the same time, collision results in no packet being received (e.g., interference)-If no users send, channel goes idle-Thus, want to have only one user send at a timeAchieve high network utilization-TDMA doesn’t give high utilizationBut also use a simple distributed algorithm-No fancy token-passing schemes to avoid collisions7Katz, Stoica F04What Layer?Where should short-term contention be handled?Network layer?Application layer?Link layer?8Katz, Stoica F04Focus of LectureUnderstanding basic algorithmic choicesSimple performance analysisWill not stress the practical details-Framing, packet formats, etc.9Katz, Stoica F04Where it all Started:AlohaNetNorm Abramson left Stanford in search of surfingSet up first radio-based data communication system connecting the Hawaiian islands-Hub at Alohanet HQ (Univ. Hawaii, Oahu)-Other sites spread among the islandsHad two radio channels:-Random access: sites sent data on this channel-Broadcast: only used by hub to rebroadcast incoming data10Katz, Stoica F04Aloha Transmission StrategyWhen new data arrived at site, send to hub for transmissionSite listened to broadcast channel-If it heard data repeated, knew transmission was rec’d-If it didn’t hear data correctly, it assumed a collisionIf collision, site waited random delay before retransmitting11Katz, Stoica F04Simple, but Radical in Concept!Aloha is to multiple access what Internet is to telephony, i.e., revolutionary!Previous attempts all partitioned channel-TDMA, FDMA, CDMA, etc.Aloha optimized the common case (few senders) and dealt with collisions through retries-Sound familiar?12Katz, Stoica F04Why Better thanTime Slot Schemes?In TDMA, you have to wait your turn-Delay proportional to number of participating sitesIn Aloha, can send immediatelyAloha gives much lower delays, at the price of lower utilization (as we will see)13Katz, Stoica F04Variation: Slotted AlohaDivide time into slots-Requires some way to synchronize geographically distributed sites (non-trivial problem!)Contend for transmission only at the beginning of slots, never in the middle of slotsEffect is to decreases chance of “partial collisions”14Katz, Stoica F04Performance of Slotted AlohaTime is divided into equal size slots (packet transmission time)Node with new arriving packet: transmit at beginning of next slot If collision: retransmit packet in future slots with probability p, until successful.Success (S), Collision (C), Empty (E) slots15Katz, Stoica F04Efficiency of Slotted AlohaWhat is the maximum fraction of successful transmissions? Suppose N stations have packets to send-Each transmits in slot with probability p-Probability of successful transmission S is(very approximate analysis!): by a particular node i: Si = p (1-p)(N-1)by exactly one of N nodesS = Prob (only one transmits) = N p (1-p)(N-1) <= 1/e = 0.37but must have p proportional to 1/N16Katz, Stoica F04EthernetBob Metcalfe, Xerox PARC, visits Hawaii and gets an idea!Shared medium (coax cable)Can “sense” carrier to see if other nodes are broadcasting at the same time-Sensing is subject to time-lag-Only detect those sending a short while beforeMonitor channel to detect collisions-Once sending, can tell if anyone else is sending too17Katz, Stoica F04CSMA and CSMA/CDCarrier sense multiple access: CSMA-Listen before you start sendingCSMA with collision detect: CSMA/CD-Stop sending when you detect another station is sending18Katz, Stoica F04CSMA: Carrier Sense Multiple AccessCS (Carrier Sense) implies that each node can distinguish between an idle and a busy linkSender operations:-If channel sensed idle: transmit entire packet-If channel sensed busy, defer transmission•Various retry
View Full Document
Unlocking...