Collisions & Virtual collisions in IEEE 802.11 networksOutlineProblem of Carrier-Sensing in 802.11Slide 4Slide 5Slide 6SymptomsSymptoms Throughput UnfairnessSymptoms Routing InstabilitySlide 10The New Design --for IEEE 802.11 Basic ModeThe New Design --for IEEE 802.11 RTS/CTS ModeSlide 13Performance Evaluation TCP unfairnessPerformance Evaluation Routing InstabilitySlide 16Throughput-collision tradeoffSlide 18Slide 19ConclusionThank you!Collisions & Virtual collisions in IEEE 802.11 networksLibin JiangEE228a Communication NetworksOutlineProblem of Carrier-Sensing in 802.11 Some SymptomsThe New DesignPerformance EvaluationThroughput-Collision TradeoffConclusionProblem of Carrier-Sensing in 802.11Hidden-terminal problem (causing collisions)T1R1T2Basic Mode |T2-R1|<IR;|T1-T2|<PCSRangePCSRangeR21 2Link contention Graph(Link: a Transmitter-Receiver pair)T1R1T2VCSRangeVCSRangeR2RTS/CTS mode |T2-R1|<IR;VCSRange>IRIR: Interference RangePCSRange: Physical Carrier Sensing RangeVCSRange: Virtual Carrier Sensing RangeRTS/CTSProblem of Carrier-Sensing in 802.11Collisions & unfairness still existif a receiver can sense “busy” channel but the transmitter can’tTransmitter does not know when to transmitCollisionsVirtual collisionsT2 can send RTS to R2, but R2 does not reply with a CTS(May not be a real collision)Information asymmetryT1 knows Link 3T3 does not know Link 1, resulting in collisionsLink 3 gets a much lower throughput than Link 1Cannot be solved by just using a large CS RangeCollisionVirtual CollisionT1R1R3RTS/CTS ModeVCSRange>IRVCSRangeVCSRangeT3T2R2Problem of Carrier-Sensing in 802.11Similar situation exists in "Basic Mode“, if the receiver cannot “restart” to receive a stronger packetT1R1T2PCSRangeR2Preamble, length MAC DataPreamble, length MAC Data (T2->R2)If |T1-R2|<PCSRange, R2 can miss thepacket T2->R2Basic ModePackets on Link 2 are often lost, for any PCSRange.Packet T1->R1Packet T2->R2Packets arriving at R2OutlineProblem of Carrier-Sensing in 802.11 Some SymptomsThe New DesignPerformance EvaluationThroughput-Collision TradeoffConclusionSymptomsFrequent packet collisions cause many problems [1]Throughput UnfairnessRouting Instability[1] Xu, S.; Saadawi, T., “Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks?”, Communications Magazine, IEEE, Volume: 39, Issue: 6, June 2001, Pages:130 - 137Symptoms Throughput Unfairness0 10 20 30 40 5000.511.522.5Time (s)Throughput (Mbps)TCP 1TCP 2TCP 1: node 1 node 3, starts earlier at 3.0 sec TCP 2: node 6 node 4. starts at 10.0 sec.1 2 3 4 5 6Tool: Network Simulator 2Nodes are spaced by 140mNo RTS/CTS, PCSRange = 550m.3 hops<PCSRange<4 hopsData rate: 11MbpsPacket size: 1460 BytesRouting protocol: AODV (Ad-hoc On-demand Distance Vector Routing)Symptoms Routing InstabilityA UDP flow: node 1 node 12 (11 hops).Routing instability is triggered by excessive packet collisions, which is mistaken for route unavailability1 2 3 4 5 611 12...0 10 20 30 40 500 0.2 0.4 0.6 0.8 11.2Time (s)Throughput (Mbps)OutlineProblem of Carrier-Sensing in 802.11 Some SymptomsThe New DesignPerformance EvaluationThroughput-Collision TradeoffConclusionThe New Design--for IEEE 802.11 Basic ModeRange Requirement: Transmitter must sense the interfering link(s)Receiver Requirement: Receiver assumes no role in Carrier-Sensing“Restart”: If a stronger packet arrives later, the receiver switches to receiving the packetIn any case, return ACK if receiving a DATA packetmax max Each link has an "Interference Range": ( ),where (.) is an increasing function. ( ) links , are "interfering" if | | , where{ , }, { , }.i ii j i ji i i j j ji IR f df IR f di j X X IR or IRX T R X T R==- <� �max maxmax{| |}, interfering links ,max{| |} 2i ji jPCSRange T T i jT T d IR> - "- = +T1R1R2IRmaxdmaxdmaxT2DefinitionsThe New Design--for IEEE 802.11 RTS/CTS ModeRange Requirement: transmitter must receive the RTS or CTS from interfering link(s)Receiver Requirement: Receiver assumes no role in Carrier-SensingSame as before, except…In any case, return CTS/ACK if receiving a RTS/DATA packetmax maxmax{min(| |,| |)}, interfering links ,i j i jVCSRange T T T R i jVCSRange d IR> - - "\ > +T1R1R2VCSRangeVCSRangeT2RTS/CTS modeIf VCSRange>dmax+IRmax,then |R1-R3|>IRmaxIRmaxdmaxdmaxT3R3OutlineProblem of Carrier-Sensing in 802.11 Some SymptomsThe New DesignPerformance EvaluationThroughput-Collision TradeoffConclusionPerformance Evaluation TCP unfairness0 10 20 30 40 5000.511.522.5Time (s)Throughput (Mbps)TCP 1TCP 2TCP 1: node 1 node 3, starts earlier at 3.0 sec TCP 2: node 6 node 4. starts at 10.0 sec.1 2 3 4 5 60 10 20 30 40 5000.511.522.5Time (s)Throughput (Mbps)TCP 1TCP 2Performance Evaluation Routing InstabilityA UDP flow: node 1 node 12 (11 hops).Routing instability is triggered by excessive packet collisions, which is mistaken for route unavailability1 2 3 4 5 611 12...0 10 20 30 40 500 0.511.5Time (s)Throught (Mbps)BeforeAfterOutlineProblem of Carrier-Sensing in 802.11 Some SymptomsThe New DesignPerformance EvaluationThroughput-Collision TradeoffConclusionThroughput-collision tradeofIn the design, CSRange/dmax seems to be large:A smaller PCSRange can not remove hidden-terminals, but may give a higher throughputTo study the tradeoff, consider a random network M=416 APs, 64 randomly located clientsD/M=175mdmax=175/root(2)PCSRange>468m satisfies Range RequirementAP1 AP2AP3 AP4DD/ MDmax maxmax max2PCSRange d IRVCSRange d IR> +> +Throughput-collision tradeofCollision Probability vs. PCS Range Total throughput vs. PCS Range Total Throughput01020304050607080900 100 200 300 400 500PCS Range (m )Total Throughput (Mbps)Af ter meeting "Receiver Requirement" IEEE 802.11Collision Probability00.050.10.150.20.250.30.350 100 200 300 400 500PCS Range (m )Collision ProbabilityAf ter meeting "Receiver Requirement" IEEE 802.11Range Requirement metThroughput-collision tradeofThe tradeoff always existsThe tradeoff is improved by meeting the Receiver RequirementThroughput-collision tradeoff00.050.10.150.20.250.30.350 20 40 60 80 100Total Throughput (Mbps)Collision ProbabilityAfter meeting "Receiver Requirement" IEEE 802.11Conclusion802.11 does not avoid
View Full Document
Unlocking...