Document Related

Document Description

CMPE 255: Advanced Computer Communication LECTURE 2:. Medium Access Control Protocols forAd Hoc Networks. RTS. RTS. CTS. CTS. S to R. R to S. S. S. S. RTS. CTS. time. RTS. H to R. noise is heard. FAMA: Floor Acquisition Multiple Access.

Document Share

Document Transcript

CMPE 255: Advanced Computer CommunicationLECTURE 2: Medium Access Control Protocols forAd Hoc NetworksUCSC cmpe255RTSRTSCTSCTSS to RR to SSSSRTSCTStimeRTSH to Rnoise is heardFAMA: Floor Acquisition Multiple AccessStations use carrier sensing to send any packet. The CTS lasts much longer than an RTS to force the interfering sources to detect carrier (from the receiver) and back off. RTS from S arrives at R with no collisions.RTS from H must start within one prop. delay from CTS from R to S.H must hear noise from CTS and backs off!UCSC cmpe255Packetready Floor Taken?yesnosend RTSdelay packettransmission k timeswait for a round-trip timeCTSback?compute randombackoff integer ksend packetnoyesBasic FAMA ProtocolNon-persistent strategy.Same basic algorithm for all CSMA/CA schemesUCSC cmpe255A packet is successful with probabilityFor we can approximate:Throughput of FAMATwo mutually exclusive events: packet is successful or a collision occurs. Therefore:The utilization period is only that portion of a packet transmission that has no overhead, that is:Notice the impact of the RTS-CTS overhead!Substituting:UCSC cmpe255Throughput of FAMAFAMA (and all collision-avoidance protocols) is always below CSMA/CD. UCSC cmpe255RIMA-DP timing diagramsWaiting periodXRTRDATANode X sends an RTR and after seconds receives a DATA packet and then sends its DATADATAZWaiting periodRTRDATAXNode X sends an RTR and node Z replies with a CTS; node X sends its DATAZCTSXRTRNodes X and Z send RTRs within seconds and therefore a collision occursZRTRchannelcollisionBACKOFFNoise detected at ZXRTRNTRBACKOFFDue to interference from node Z, node X sends an NTR to stop the handshakeZinterferenceUCSC cmpe255Throughput of RIMA-DPThe probability of success is the probability that an RTR is sent in the clear, because any RTR produces one or two data packets, i.e., The probability with which the polled node has data is The probability with which the poled node has no data is The length of an average busy period always includes an RTR, a prop delay, and the average time between the first and the last RTR of the busy period; therefore, UCSC cmpe255first packet starts (A)last interfering packet starts (B)NEWNEWARTRBtimesuccessful packet:idle period:collision interval:Throughput of RIMA-DPNEWDATACTSThe length of the average idle period is simply 1/lambda The average utilization period is idleperiodUCSC cmpe255Throughput of RIMA-DPThe throughput is simple the length of the ave. utilization period divided by the length of the average cycle: UCSC cmpe255Throughput Analysis500 Byte data packets; 1Mbps network speed; maximum distance between nodes is 1 mile; on the left a 10 node network; on the right a 50 node network UCSC cmpe255Limitations of Colision AvoidanceCollision avoidance is meant for unicast packets. A large number of network-level control and data packets are multicast and broadcast in nature. UCSC cmpe255Collision-Avoidance Transmission Scheduling (CATS)A contention and reservation based topology-dependent multi-channel scheduling protocol. Schedules unicasting, multicasting and broadcasting traffics simultaneously. Data packets are sent collision-free in the presence of hidden terminals. Supports real-time applications and node mobility. Provides better spatial reuse than topology-independent scheduling since frame length depends only on node degree. Works well with commercial SFH radios in ISM bands. UCSC cmpe255Time and Channel OrganizationTime is slotted and slots are grouped into frames. A slot is further divided into six mini-slots. Multiple channels are available: one signaling channel (SCH), one broadcast data channel (BCH) and a number of other data channels (DCHs). A data link refers to a particular DCH or the BCH in a particular slot. Small control packets called beacons are used to contend for and reserve data links. UCSC cmpe255Identifying Reservations and Data TransmissionFrameslot 1slot 2slot 3slot LLRBUnicast Data PacketUnicastLRBLRBLRBMulticast Data PacketMulticastLRBBroadcast Data PacketBroadcastMS1MS2MS3MS4MS5MS6Signaling CHBroadcast CHReserved Data CH'sLRB: Link Reservation BeaconUCSC cmpe255Frameslot 1slot 2slot 3slot 4slot LUnsuccessfulSLSLRUBRLC/Nunicast contentionSuccessfulSLSLRUBRLCUBUCDunicast contentionUnsuccessfulSLSLRMBSMB/Nmulticast contentionSuccessful multicastSLSLRMBClearMCDcontentionUnsuccessfulSLRBBSBB/Nbroadcast contentionSuccessfulSLRBBClearBCDbroadcast contentionMS1MS2MS3MS4MS5MS6Signaling CHData CHRUB: Request Unicast Beacon, RMB: Request Multicast Beacon, RBB: Request Broadcast BeaconCUB: Concur with Unicast Breacon, SMB: Stop Multicast Beacon, SBB: Stop Broadcast BeaconUCD: UniCast Data, MCD: MultiCast Data, BCD: BroadCast Data, SL: Sender ListensRL: Receiver Listens, C/N: Clear/NoiseMaking Reservations for Data TransmissionsRLSLRLSLSLSLBroadcast CHUCSC cmpe255Frame LengthWorst-case minimum frame length L and number of DCHs C (assuming N > d2, d: the max node degree, and N: the node population in the network):For broadcast: L = d2 + 1. For unicast: L = 2d, C = d, if each node unicasts once in each frame; Or L = 2(2d -1), C = 2d -1, if each node unicasts to each neighbor once in each frame. UCSC cmpe255Approximate Unicast Throughput Analysis ResultsBAMA: d=10, L=20 slots, C=10 DCH's, AFL in slots10.90.80.70.6Throughput per Node S0.50.40.30.2AFL=100AFL=10AFL=20.1AFL=1000.20.40.60.811.2Offered Load per Node Gd: node degreeL: frame lengthAFL: average flow (message) lengthUCSC cmpe255BAMA: N=16 nodes, L=16 slots, AFL in slots10.90.80.70.6Throughput per Node S0.50.40.30.2AFL=100AFL=10AFL=20.1AFL=1000.10.20.30.40.50.60.70.80.9Offered Load per Node GApproximate Broadcast Throughput Analysis ResultsN: number of nodesL: frame lengthAFL: average flow (message) lengthUCSC cmpe255Approximate Performance AnalysisThroughput is analyzed for two cases: unicast traffic over a hyper-cube topology and broadcast traffic over a fully-connected topology. Each node can reserve at most one slot for transmission in each frame with the worst-case minimum frame length and number of data channels. We consider Poison sources and geometrically distributed variable-length flows (messages). Throughput is defined as the probability that a node has a reserved link for transmission in a frame. UCSC cmpe255Likmitations in CATSCollision avoidance dialogue is needed! How can we eliminate the CA in CATS? Goal is to have a topology-dependent transmission schedule! Protocol needs to implement a distributed election of schedules and such schedules must be transmitted persistently without eating too much bandwidth! UCSC cmpe255Collision Resolution and Backoff StrategiesUsed to stabilize the system by preventing traffic loads that exceed its capacity. Collision resolution: Let packet that collide resolve when each is transmitted and block new traffic from entering the system. Backoff strategies: Increase the time between retransmissions when traffic load (that creates collisions) increases. UCSC cmpe255Nodes 1 to 49 can try again; node 5 succeeds! (must be only node in range)Nodes 5, 50, 70, 80 collideNodes 76 to 100 must wait;Node 80 waitsNodes 50 to 100 must wait for all collisions from 1 to 49 to be resolvedNodes 50 to 75 can try;50 and 70 collideNodes 50 to 62 can try;50 succeeds(must be only in range)Node 70 waitsNodes 63 to 70 can try;70 succeedsNodes 76 to 100 can try;80 succeeds!Collision Resolution AlgorithmAssume a fully-connected network. Each node maintains a stack, a HighID, a LowID and knows the maximum ID in the system UCSC cmpe255Average Delay of MAC ProtocolsWe want to measure or compute the average time from the instant the first bit of a packet is first transmitted to the moment the last bit is received correctly at the destination. Assume that arrivals (of new and retransmitted data or control packets) to the channel are Poisson. Assume fully-connected networks. UCSC cmpe255The average number of transmissions needed for a packet to be received correctly isTherefore, the number of retransmissions is Average Delay in ALOHAAssumptions:A satellite channel with propagation delay NxP, where P is the packet length and NxP >> PA retransmission is sent after an average backoff time of BxP seconds.Direct method:A packet is transmitted (G/S-1) times in error (due to collisions) and each such transmission wastes P+NxP +BxP seconds.The last transmission is successful and must take P+NxP seconds.Therefore, the average delay incurred is: UCSC cmpe255START ENDBACKOFFAverage Delay in ALOHAIndirect Method:Based on the fact that the success of a transmission is independent of others, and knowing how many times we have retransmitted does not change the likelihood of success in the next transmission!We use a diagram showing possible states, probabilities of transition, and delay incurred in that transition. From the diagram. we obtain a number of simultaneous equations that we solve to obtain delay from START to END.UCSC cmpe255From the diagram we have:Substituting we obtain the same result.Average Delay in ALOHASolving these two equations:The same method can be applied on the other MAC protocols!UCSC cmpe255Average Delay of ALOHAThe delay increases exponentially with heavy load, which is not acceptable for real-time applications. UCSC cmpe255UCSC cmpe255UCSC cmpe255UCSC cmpe255UCSC cmpe255UCSC cmpe255

Search Related

Previous Slide

Next Slide

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks