1、Channel Allocation ProtocolsDynamic Channel Allocation Parameters Station Model.N independent stations,each acting as a Poisson Process for the purpose protocol analysis Single Channel Assumption.A single channel is available for all communication.Collision Assumption.If transmitted frames overlap i
2、n time,the resulting signal is garbled.Transmission Discipline:Continuous time Frames can be transmitted at any time Slotted time Frames can be transmitted at particular time points Sensing capability:Station cannot sense the channel before trying to use it.Stations can tell if the channel is in use
3、 before trying to use itPoisson Process The Poisson Process is a celebrated model used in Queuing Theory for“random arrivals”.Assumptions leading to this model include:The probability of an arrival during a short time interval t is proportional to the length of the interval,and does not depend on th
4、e origin of the time interval(memory-less property)The probability of having multiple arrivals during a short time interval t approaches zero.Poisson Distribution()()!ktkteP tkThe probability of having k arrivals during a time interval of length t is given by:where is the arrival rate.Note that this
5、 is a single-parameter model;all we have to know is.Pure ALOHA ProtocolWhile there is a new frame A to send DO1.Send frame A and wait for ACK2.If after“some”time ACK is not received(timer times out),wait a random amount of time and go to 1.EndPure ALOHAIn pure ALOHA,frames are transmitted at complet
6、ely arbitrary times.Analysis of Pure ALOHA Notation:Tf=frame time(processing,transmission,propagation)S:Average number of successful transmissions per Tf;that is,the throughput or efficiency.G:Average number of total frames transmitted per Tf D:Average delay between the time a packet is ready for tr
7、ansmission and the completion of successful transmission.We will make the following assumptions All frames are of constant length The channel is noise-free;the errors are only due to collisions.Frames do not queue at individual stations The channel acts as a Poisson process.Analysis of Pure ALOHA Si
8、nce S represents the number of“good”transmissions per frame time,and G represents the total number of attempted transmissions per frame time,then we have:S=G (Probability of good transmission)The vulnerable time for a successful transmission is 2Tf So,the probability of good transmission is not to h
9、ave an“arrival”during the vulnerable time.9Analysis of Pure ALOHA(4)t0t0+tt0+2tt0+3tCollides withthe start ofthe shadedframeCollides withthe end ofthe shadedframeVulnerableTimeVulnerable period for the shaded frametAnalysis of Pure ALOHAUsing:!)()(kettPtkkAnd setting t=2Tf and k=0,we get20202(2)(2)0
10、!becasue.Thus,fTfGfGfTePTeGSGeT11Analysis of Pure ALOHA If we differentiate S=Ge-2G with respect to G and set the result to 0 and solve for G,we find that the maximum occurs when G=0.5,and for that S=1/2e=0.18.So,the maximum throughput is only 18%of capacity.ALOHANET uses a data rate of 9600bps.This
11、 means the maximum total throughput(sum of data arriving from all user nodes)is only 0.18 9600=1728bps.Pure ALOHA Throughput versus offered traffic for ALOHA systems.Analysis of Pure ALOHA;another approach There are N stations Each station transmits with probability p For a typical node i to have a
12、successful transmission means that there was no prior overlapping transmissions before or after,each with probability(1-p)N-1 Thus the probability of node i having a successful transmission is p(1-p)2(N-1)Therefore,the probability of a successful transmission is Np(1 p)2(N-1)The maximum value for th
13、e above term when N is large is 1/2eAnalysis of Pure ALOHA;another approach2(1)2(1)2(1)12(1)12(1)1*2(1)*(1)(1)2(1)(1)(1)(1)(1)2(1)(1)1210211112121NNNNNNfNppdfNpNpNpdpdfNppNpNppNpdpdfpdpNfNNNExpected number of transmissions In Pure ALOHA,what is the expected number of transmissions per frame?Let x be
14、 the random variable representing the number of transmissions.Thus,x will take on values 1,2,3,etc The probability Pk that x takes value k is when we have(k-1)unsuccessful transmissions followed by a successful transmission.For PURE ALOHA,the probability of a successful transmission is e-2GExpected
15、number of transmissionsThus Ex grows exponentially with G,which means that a small increase in the channel load,that is G,can drastically reduce its performance.The ALOHA protocol is an example of an unstable protocol.221221211Thus (1).So,we have(1)GGkkGGkGkkkPeeE xkPkeee17Slotted ALOHAChannel is or
16、ganized into uniform slots whose size equals the frame transmission time.Transmission is permitted only to begin at a slot boundary.Here is the procedure:While there is a new frame A to send do1.Send frame A at a slot boundary and wait for ACK2.If after“some”time ACK is not received,wait a random am
17、ount of time and go to 1.EndAnalysis of Slotted ALOHA Note that the vulnerable period is now reduced in half.Using:!)()(kettPtkkAnd setting t=Tf and k=0,we get00()()0!because .Thus,fTfGfGfTePTeGSGeTSlotted ALOHAThroughput versus offered traffic for ALOHA systems.Alternate Analysis for Slotted Aloha
18、Use of alternate approach for throughput of slotted aloha is left as exerciseCarrier Sense Multiple Access(CSMA)Additional assumption:Each station is capable of sensing the medium to determine if another transmission is underwayNon-persistent CSMAWhile there is a new frame A to send DO1.Check the me
19、dium2.If the medium is busy,wait some time,and go to 1.3.(medium idle)Send frame A and wait for ACK4.If after some time ACK is not received(timer times out),wait a random amount of time and go to 1.End1-persistent CSMAWhile there is a new frame A to send do1.Check the medium2.If the medium is busy,g
20、o to 1.3.(medium idle)Send frame A and wait for ACK4.If after some time ACK is not received(timer times out),wait a random amount of time and go to 1.End.p-persistent CSMAWhile there is a new frame A to send do1.Check the medium2.If the medium is busy,go to 1.3.(medium idle)With probability p send f
21、rame A and the go to 4,and probability(1-p)delay one time slot and go to 1.4.If after some time ACK is not received(timer times out),wait a random amount of time and go to 1.End.25CSMA SummaryNon-persistent:Transmit if idle Otherwise,delay,try againConstant or variableDelayChannel busyReady1-persist
22、ent:Transmit as soon as channel goes idleIf collision,back off and try againTimep-persistent:Transmit as soon as channel goes idle with probability p Otherwise,delay one slot,repeat processCSMA persistence and backoff Nonpersistent 1-persistent p-persistentPersistent and Non-persistent CSMACompariso
23、n of throughput versus load for various random access protocols.CSMA with Collision Detection Stations can sense the medium while transmitting A station aborts its transmission if it senses another transmission is also happening(that is,it detects collision)Question:When can a station be sure that i
24、t has seized the channel?Minimum time to detect collision is the time it takes for a signal to traverse between two farthest apart stations.CSMA with Collision DetectionCSMA/CD can be in one of three states:contention,transmission,or idle.CSMA/CD A station is said to seize the channel if all the oth
25、er stations become aware of its transmission.There has to be a lower bound on the length of each frame for the collision detection feature to work out.Ethernet uses CSMA/CDCSMA/CA Identical to CSMA/CD but used when listening is not possible while transmitting Idle channel reservation is done by sending a short request message asking other nodes to defer transmission If collison is detected then,then random wait is used Wireless IEEE 802.11 uses CSMA/CA with an RTS/CTS mechanism
