Slide 1MotivationTCP Unfairness in Ad Hoc NetworksSignificant TCP UnfairnessWhy RED Does Not Work?Neighborhood and Its Distributed QueueSimplified Neighborhood Queue ModelNeighborhood Random Early Detection (NRED)Neighborhood Congestion DetectionNeighborhood Congestion Notification & Distributed Neighborhood Packet DropParameter Tuning: ScenariosPerformance Evaluation: Simple ScenarioPerformance Evaluation: Multiple Congested NeighborhoodConclusionsEnhancing TCP Fairness in Ad Hoc Wireless Networks Using Neighborhood REDKaixin Xu, Mario GerlaUniversity of California, Los Angeles{xkx, gerla}@cs.ucla.eduLantao Qi, Yantai ShuTianjin University, Tianjin, China{ltqi, ytshu}@tju.edu.cn*This work was supported in part by Office of Naval Research (ONR) "MINUTEMAN“ project under contract N00014-01-C-0016 and TRW under a Graduate Student Fellowship*This research was supported in part by the National Natural Science Foundation of China (NSFC) under grant No. 90104015.2MotivationTCP is important in ad hoc network applicationsReliable transfer of data/image files and multimedia streamingCongestion protectionEfficient utilization and fair share of the resourcesHowever, TCP has shown unfair behavior in ad hoc nets3TCP Unfairness in Ad Hoc NetworksFairness index in wireless networksWeighted MaxMin Fairness IndexWeight(i) = # of flows that compete with flow i (including itself) Simulation in QualNet simulator3 TCP flows contending with each otherWeight of 3 flows, 2:3:2F T P 1F T P 2F T P 3( 1 0 0 , 1 0 0 )( 6 0 0 , 1 0 0 )( 3 5 0 , 3 5 0 )( 3 5 0 , 7 0 0 )( 0 , 7 0 0 )( 3 5 0 , 1 0 5 0 )( 1 0 0 , 1 3 0 0 )( 6 0 0 , 1 3 0 0 )( 7 0 0 , 7 0 0 ) 2121,niiiniiitXtWntXtwtXF4Significant TCP Unfairness Three flow exampleFlow 2 is nearly starvedOriginal RED fails to improve the fairnessWeighted Fairness Index = 0.675Why RED Does Not Work?Why RED does not work in ad hoc networks?Congestion simultaneously affects multiple queuesQueue at a single node cannot completely reflect the stateExtend RED to the entire congested area – Neighborhood of the nodeRandom Early Detection (RED)Active queue management scheme qwavgwavgqq 1Average queue size: Drop probability: , proportional to buffer occupancythththpavgbpminmax)min(max6Neighborhood and Its Distributed QueueA node’s neighborhood consists of the node itself and the nodes which can interfere with this node’s signal1-hop neighbors directly interfere2-hop neighbors may interfereQueue size of the neighborhood reflects the degree of local network congestionA153426791 01 21 187Simplified Neighborhood Queue Model2-hop neighborhood queue model is not easy to operateToo much overhead to propagate queue values 2 hops awaySimplified modelOnly include 1-hop neighborsTwo queues at each neighbor:Outgoing queue“Incoming queue”= # CTS packets overheard by ADistributed neighborhood queue – the aggregate of these local queuesA153426O u t g o i n g Q u e u eI n c o m i n g Q u e u e9Neighborhood Random Early Detection (NRED)Extending RED to the distributed neighborhood queueKey ProblemsCounting the size of the distributed neighborhood queueCalculating proper packet drop probability at each nodeComponents of Neighborhood REDNeighborhood Congestion Detection (NCD)Neighborhood Congestion Notification (NCN)Distributed Neighborhood Packet Drop (DNPD)10Direct way: Announce queue size upon changesToo much overhead, exacerbates congestionOur method: Indirectly estimate an index of instant queue size by monitoring wireless channelNeighborhood Congestion DetectionAverage queue size is calculated using RED’s alg.Congestion: queue size exceeds the minimal thresholdervalsamplingtimebusychannelUbusyintChannel utilization ratioQueue size index , K is a constant busyUKq *A153426O u t g o i n g Q u e u eI n c o m i n g Q u e u eChannel busyCTS11Neighborhood Congestion Notification & Distributed Neighborhood Packet DropNeighborhood Congestion NotificationCongested node computes drop probability following RED’s alg.It broadcasts the drop probability to all neighborsDistributed Neighborhood Packet DropNeighborhood Drop Prob = Max of all drop probabilities heard from neighbors13Parameter Tuning: ScenariosQualNet simulatorBasic but typical scenariosHidden terminal situationsExposed terminal situationsConfiguration parametersMinimum threshold & Maximum thresholdSet to 100 and 240 based on previous experimentVary the maximum packet drop probability (maxp)F T P 21 2 3 4F T P 1( 1 0 0 , 0 )( 1 0 0 , 3 5 0 )( 1 0 0 , 7 0 0 ) ( 1 0 0 , 1 0 5 0 )F T P 21 2 3 4F T P 1( 1 0 0 , 0 )( 1 0 0 , 3 5 0 )( 1 0 0 , 7 0 0 ) ( 1 0 0 , 1 0 5 0 )Hidden TerminalExposed Terminal16Performance Evaluation: Simple ScenarioBoth long-term and short-term fairness is achievedLoss of aggregated throughputTradeoff between fairness and throughputChannel is not fully utilizedOverall ThroughputInstantaneous ThroughputF T P 1F T P 2F T P 3( 1 0 0 , 1 0 0 )( 6 0 0 , 1 0 0 )( 3 5 0 , 3 5 0 )( 3 5 0 , 7 0 0 )( 0 , 7 0 0 )( 3 5 0 , 1 0 5 0 )( 1 0 0 , 1 3 0 0 )( 6 0 0 , 1 3 0 0 )( 7 0 0 , 7 0 0 )17Performance Evaluation: Multiple Congested NeighborhoodMultiple congested neighborhoodsFTP2 & FTP 5 have more competing flows, are more likely to be starvedOverall ThroughputF T P 1 F T P 2 F T P 3F T P 4F T P 5F T P 620ConclusionsSignificant TCP unfairness has been found and reported in ad hoc networksNRED is a network layer solutionEasy to implementIncremental deploymentMajor ContributionsModel of neighborhood queueDistributed neighborhood queueNot FIFO, different and dynamic prioritiesNetwork layer solution for enhancing TCP fairness in ad hoc
View Full Document