Communication NetworksAd-Hoc Networks: Capacity & FairnessExamplesSlide 4Random NetworkSlide 6Slide 7Slide 8Slide 9Mobility EffectsFair Ad Hoc MAC?Slide 12Motivation: Exponential Backoff is UnfairMotivation: TCP cannot overcomeSlide 15Slide 16Protocol: Impatient Backoff AlgorithmProtocol: Backoff UpdateProtocol: Simplified MAC ModelProtocol: IBA MechanismSlide 21Markov Chain ModelsStar Topology: Birth-Death ChainStar Topology: Varying NeighborsTriangle Topology Markov ChainSlide 26Simulations on Random TopologyVariations in SimulationCommunication NetworksA Second CourseJean WalrandDepartment of EECSUniversity of California at BerkeleyAd-Hoc Networks: Capacity & Fairness•Examples•Random Network •Mobility Effects•Fair MAC?Examples•Links in Series•Omni-directional antennas; r(interference) < 2 r(comm)link 4 interferes with 2, 3, 5 (4 sends 2 cannot be heard) => Independent sets: {1, 4, 7}, {2, 5, 8}, {3, 6} => R < 1/3•Omni-directional antennas; r(interference) = 2 r(comm)link 4 interferes with 1, 2, 3, 5 (4 sends 1 cannot be heard) => Independent sets: {1, 5}, {2, 6}, {3, 7}, {4, 8} => R < 1/41 2 3 4 5 6 7AB8•Directional antennas; r(interference) = 2 r(comm)link 3 interferes with 2, 4 (3 sends 4 cannot be heard) => Independent sets: {1, 3, 5, 7}, {2, 4, 6, 8} => R < 1/2Note: details of protocol matter ….Examples•Links in Series•Assume each node sends R/3 to every other node. What is the maximum possible value of R?1 2 3AB•Now we distinguish link 2 () and link 2’ ()1231’2’3’r(int) < 2r(com){1’,3} do not conflict Same for {1, 3’}All other pairs conflictIndependent sets:{1’, 3}, {1, 3’}, {2}, {2’}A, B, C, D = set rates1, 3’: R; 2, 2’: 4R/3; 1’,3: R B = A = f; C = D = 4f/32f + 8f/3 = 14f/3 = 1 => f = 3/14R = 4f/3 = 2/17Random NetworkRandom network: Assume N nodes randomly placed in some unit square; they all transmit to a randomly picked destination at a total rate R. How large can R be? We show that R < O(1/N0.5). •Each node is d = O(1/N0.5) away from neighbors•Each transmission at rate R to a neighbor covers a disk of height R and area O(d2) = O(1/N) => volume R.O(1/N). •To reach a random destination, we need to cover an average distance O(1) with hops of size O(1/N0.5), we need O(N0.5) hops.•That transmission from source to destination covers a volume O(N0.5)R.O(1/N) = R.O(1/N0.5). Note: shortest hop minimizes volume: increasing hops sizes by k increases volume by k2/k = k•There are N transmissions => They use volume R.O(N0.5) •The total available volume is C.O(1)•Hence, R.O(N0.5) < C.O(1) R < O(1/N0.5) •Note that this rate is achievable if the nodes are in a regular grid; they can use a simple horizontal, then vertical routingRandom NetworkS D• About N0.5 hops of size 1/N0.5• They cover a volume equal to N0.5(R/N) => R/N0.5 per transmission• There are N such transmissions• Hence RN0.5 < C => R < C/N0.5Random NetworkThe capacity per node is O(1/N0.5)[Franceschetti et al, 2004]•We have seen the upper bound•The lower bound goes as follows. Consider square with sides n = N0.5. Divide into grid of squares with sides c. Consider nonempty squares to form bridges. If P(nonempty) > ½, then there are O(n) paths from left to right. Associate each path to a horizontal slab with O(1) height. Sources in that slab connect to path with O(log n) hop; same vertically.Random NetworkO(n) paths through each cell. Hence, R.O(n) = C.However, we need to take Interference into account and the location of the pathsbn = N0.5There are A horizontal pathsand A vertical paths.We associate a path to eachhorizontal slab of size O(1).Random NetworkAccess to path: O(log n) Rate >> O(n) Bottleneck is pathn = N0.5bO(log n)Paths: Divide square into square cells with side O(1). If square nonempty, it form a bridge.If P(bridge) > ½, one can go from left to right with a probability close to 1 as N increases. Moreover, there are many paths: O(n). Thus, one finds a path close to each slab.Mobility Effects•Basic idea:•Nodes can wait to be closer to transmit•If they move fast enough, the capacity increases•However, this may increase delay•Unfortunately, mobility assumptions are flaky.•Motivation•Protocol•Analysis•SimulationsFair Ad Hoc MAC?Work with Rajarshi GuptaFair Ad Hoc MAC?•Motivation •Protocol•Analysis•SimulationsMotivation: Exponential Backoff is Unfair•Exponential backoff scheme (e.g. 802.11b)•Nodes pick backoff uniformly in a backoff range•If collision, double the backoff range•Multiple interference domains•Node in center sees more contention and collision•It backs off more•Gets lesser share of bandwidth•Unfair towards middle nodes in network Active LinkRcvd on ARcvd on BRcvd on XA 6A,B 6 6A,X 3 3A,B,X 4 4 2A1interferenceinterferenceA2B1B2X1X2Cory HallRoom 273Cory HallRoom 264MCoryHallwayAll rates in MbpsMotivation: TCP cannot overcomeA1A2B1B2X1X2xy ySimplified Model: WFQ24yxxy6624x - lossesx, y - lossesy - lossesMotivation: TCP cannot overcomeIn complex network, constraints are non-local: Independent Sets Shadow prices cannot be computed locallyHere, we have modest goals: Improve node-fairness (max-min)….Fair Ad Hoc MAC?•Motivation•Protocol •Analysis•SimulationsProtocol: Impatient Backoff Algorithm•Approach: Nodes that face more contention should get higher priority•Key Mechanism•Upon collision, nodes decrease their backoff•Need to worry about•Stability•Fairness•ThroughputProtocol: Backoff Update•If collision or quiet•Decrease the mean backoff delay •b := b/m, where m>1•If successful transmission•Increase the mean backoff delay •b := bm•Note: Distributed reset mechanismWhen a node’s mean delay falls below threshold, node broadcasts “multiply by K” ….Protocol: Simplified MAC Model•All packet lengths are same•Transmissions occur slot by slot•Local synchronization is assumed•Similar to any slotted protocol•No RTS/CTSProtocol: IBA Mechanism•Backoff Contention Phase•Each node has mean backoff b•Picks backoff delay B using exponential variable with mean b•Sends out Slot Capture Message after B backoff mini-slots•If a node carrier senses another message sooner – it keeps quiet•Packet Transmission Phase•Starts after completion of Backoff Contention Phase•Nodes with successful Slot Capture Messages transmit•Constant packet
View Full Document
Unlocking...