EECS 122 Introduction to Computer Networks Multiaccess Protocols Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 ISO OSI Reference Model for Layers Application Presentation Session Transport Network Datalink Physical Service Framing attach frame separators Send data frames between peers Others Arbitrate the access Media Access to common physical media Per hop reliable transmission Per hop flow control Katz Stoica F04 2 Up 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 contention Have focused on managing long term contention Queueing schemes FQ FIFO RED etc End to end congestion control TCP Katz Stoica F04 3 This Lecture Short 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 medium Katz Stoica F04 4 Medium Access Protocols Channel partitioning Divide channel into smaller pieces e g time slots frequency code selection Allocate a piece to given node for exclusive use Random access Allow collisions Recover from collisions Taking turns Tightly coordinate shared access to avoid collisions Katz Stoica F04 5 Problem Statement Managing 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 time Achieve high network utilization TDMA doesn t give high utilization But also use a simple distributed algorithm No fancy token passing schemes to avoid collisions Katz Stoica F04 6 What Layer Where should short term contention be handled Network layer Application layer Link layer Katz Stoica F04 7 Focus of Lecture Understanding basic algorithmic choices Simple performance analysis Will not stress the practical details Framing packet formats etc Katz Stoica F04 8 Where it all Started AlohaNet Norm Abramson left Stanford in search of surfing Set up first radio based data communication system connecting the Hawaiian islands Hub at Alohanet HQ Univ Hawaii Oahu Other sites spread among the islands Had two radio channels Random access sites sent data on this channel Broadcast only used by hub to rebroadcast incoming data Katz Stoica F04 9 Aloha Transmission Strategy When new data arrived at site send to hub for transmission Site listened to broadcast channel If it heard data repeated knew transmission was rec d If it didn t hear data correctly it assumed a collision If collision site waited random delay before retransmitting Katz Stoica F04 10 Simple 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 Katz Stoica F04 11 Why Better than Time Slot Schemes In TDMA you have to wait your turn Delay proportional to number of participating sites In Aloha can send immediately Aloha gives much lower delays at the price of lower utilization as we will see Katz Stoica F04 12 Variation Slotted Aloha Divide 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 slots Effect is to decreases chance of partial collisions Katz Stoica F04 13 Performance of Slotted Aloha Time 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 slots Katz Stoica F04 14 Efficiency of Slotted Aloha What 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 nodes S Prob only one transmits N p 1 p N 1 1 e 0 37 but must have p proportional to 1 N Katz Stoica F04 15 Ethernet Bob 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 before Monitor channel to detect collisions Once sending can tell if anyone else is sending too Katz Stoica F04 16 CSMA and CSMA CD Carrier sense multiple access CSMA Listen before you start sending CSMA with collision detect CSMA CD Stop sending when you detect another station is sending Katz Stoica F04 17 CSMA Carrier Sense Multiple Access CS Carrier Sense implies that each node can distinguish between an idle and a busy link Sender operations If channel sensed idle transmit entire packet If channel sensed busy defer transmission Various retry algorithms Katz Stoica F04 18 CSMA collisions Collisions can occur spatial layout of nodes along ethernet propagation delay means two nodes may not hear each other s transmission Collision entire packet transmission time wasted Note role of distance and propagation delay in determining collision probability Katz Stoica F04 19 CSMA CD Collision Detection Collisions detected within short time Colliding transmissions aborted reducing channel wastage This is relatively easy in wired LANs Measure signal strengths Compare transmitted received signals Difficult in wireless LANs Katz Stoica F04 20 CSMA CD Collision Detection Katz Stoica F04 21 Ethernet Frame Structure Sending adapter encapsulates IP datagram Preamble 7 bytes with pattern 10101010 followed by one byte with pattern 10101011 Used to synchronize receiver sender clock rates Katz Stoica F04 22 Ethernet Frame Structure more Addresses 6 bytes frame is received by all adapters on a LAN and dropped if address does not match Type 2 bytes indicates the higher layer protocol E g IP Novell IPX AppleTalk CRC 4 bytes checked at receiver if error is detected the frame is simply dropped Data payload maximum 1500 bytes minimum 46 bytes Katz Stoica F04 23 Ethernet s CSMA CD Sense
View Full Document
Unlocking...