Slide1: Kunal Shah Advisor: Dr. Harish Sethu SIMULATION BASED STUDY OF TCP FAIRNESS IN MULTI-HOP WIRELESS NETWORKS Computer Communications Laboratory


Outline: Outline Introduction and Motivation Background Model Description Simulation Results and Analysis Conclusion


Introduction: Introduction Ad Hoc Networks: A collection of nodes Capable of acting as a host and a router simultaneously Communicate with each other over shared, multi-hop wireless channels Required where a fixed wired or wireless infrastructure is either unavailable or destroyed Characterized by high mobility, low bandwidths, limited physical security and continuously changing network topology Once the ad hoc network is up and running using some routing protocol, next step is to evaluate performance of transport layer protocol


Motivation: Motivation As local area wireless networks based on IEEE 802.11 standard see increasing public deployment, it is important to ensure that access to network by different users remains fair No structured studies devoted to formal investigation of TCP fairness in wireless multi-hop networks


Focus: Focus Evaluate TCP Tahoe, Reno, New Reno and SACK for fairness Motivation for selecting these TCP implementations was their popularity Fairness metric based on maximal normalized distance between user’s ideal share and actual share of service delivered by network Analyze the effects of packet size, load, TCP receive buffer size and RTS/CTS on TCP fairness


TCP Evolution: TCP Evolution Dominant reliable transport protocol since its origin Consists of sliding window mechanism, which, in conjunction with ACKs and sequence numbers, guaranteed a reliable delivery and flow control No congestion control or avoidance mechanism


TCP Evolution (Cont.): TCP Evolution (Cont.) AIMD – virtually the base of all existing TCP protocols Besides maximizing link bandwidth, TCP must be fair to rest of the flows Efficient TCP is not guaranteed to be fair


TCP Tahoe: TCP Tahoe Congestion Control Algorithms: Slow Start Congestion Avoidance Fast Retransmit Problem: Transits to slow start after each packet loss


TCP Reno: TCP Reno Extension of TCP Tahoe Added Fast Recovery along with Fast Retransmit TO: Time-out TD: Threshold Duplicate


TCP New Reno: TCP New Reno TCP Reno problem: Fast Recovery algorithm rendered inefficient in the presence of multiple losses within a single transmission window TCP New Reno remains in fast recovery mode despite receiving partial acknowledgement after fast retransmission Retransmits at the rate of one packet per RTT until all the lost packets are retransmitted No retransmit timeout


TCP SACK: TCP SACK Selective Acknowledgements are used to provide the sender with sufficient information to recover from multiple packet losses within a single transmission window Sender knows exactly which packets to retransmit and so is able to quickly recover Problem: Inefficient in the case of small sender window size


Fairness Criteria: Fairness Criteria Intuitively, one can think of fairness as the closeness of achieved throughput to its fair share


Max-Min Fairness (MMF): Max-Min Fairness (MMF) When flows have equal weights, Max-Min Fair share allocation can be defined as: Resources are allocated in order of increasing demand No user gets a resource larger than its demand Users with unmet demands get an equal share of the resource


MMF Example: MMF Example Dividing a 8 slice pizza among 4 people 2 slices 1 slice 4 slices 2 slices 2 slices 2 slices 4 slices 2 slices 2 slices 2 slices desires and gets - 1 slice = 1 slice + 1 slice = 3 slices 3 slices 2 slices 2 slices + 1 slice = 3 slices


Proposed Unfairness Criterion: Proposed Unfairness Criterion where Fi = MMFi (C, d1, d2, …, dn)


Sample Unfairness Calculation: Sample Unfairness Calculation 2 Mbps 1 Mbps 3 Mbps 0.8 Mbps 0.6 Mbps i di Ai C = 1.8 Mbps MMFi U = 0.5 0.7 Mbps 0.3 Mbps 0.6 Mbps 0.6 Mbps


Related work on TCP Fairness: Related work on TCP Fairness When flows with different end-to-end propagation delays shared a link, the bandwidth allocation was far from being fair Constant rate window increase algorithm Increase-by-K policy Congestion Avoidance with Normalized Interval of Time (CANIT) Wireless links are characterized by long RTT and above schemes react by opening up the congestion window at a much higher rate Increased probing harmful as slow 56k modem links and band-limited wireless links are themselves a bottleneck in the network Performance degradation not only due to transmission errors and losses but also due to congestion at base station → Fast TCP Flow that got head-start occupied large amount of bandwidth and starved the flows starting later on → split buffer queues Unfair packet dropping policy at Internet routers → RED policy


Related work on TCP Performance: Related work on TCP Performance Explicit Congestion Notification (ECN) Explicit Link Loss Notification M-TCP Split TCP Snoop TCP


MAC Layer Fairness: MAC Layer Fairness IEEE 802.11 uses per-node queue with per node back-off Head-of-line packet headed towards a receiver that is in high contention neighborhood can block other flow transmissions to lightly loaded neighbors Node with many flows penalizes its flow unfairly Flows that experience more contention will block more contending flows while transmitting Implementing changes made to MAC layer are impractical given the wide deployment of wireless networks using IEEE 802.11 standard Lot of research done in improving MAC layer fairness and TCP performance but no real effort made in studying TCP fairness


Model Description - Node: Model Description - Node


Application Process Model: Application Process Model


TCP Process Model: TCP Process Model


AODV Background: AODV Background Source-based routing protocol based on DSDV and DSR Utilizes sequence number of DSDV and on-demand route discovery and maintenance mechanisms of DSR Power Efficient No flooding or periodic update messages


AODV Process Model: AODV Process Model


WLAN Process Model: WLAN Process Model


Simulation Scenario: Simulation Scenario


Simulation Setup: Simulation Setup Every TCP connection is of type FTP and all flows start at the same time In each scenario, if user 1 (node 1) wants to send x Mbps, then user 2 wants to send 2x Mbps, user 3 wants to send 3x Mbps and so forth Mobility pattern is static Battery power is infinity and transmitter power is 0.25 Watts


Simulation Setup (Cont.): Simulation Setup (Cont.) Packet sizes are varied from 128 bytes to 1,024 bytes but ACKs are kept at 40 bytes long TCP receive buffer size is varied from 8,760 bytes to 131,072 bytes Load is varied from 1.5 Mbps to 7.5 Mbps to simulate low, medium and high traffic loads Load is varied from 1.5 Mbps to 7.5 Mbps but with RTS/CTS enabled for packet sizes larger than 255 packets


Simulation Setup (Cont.): Simulation Setup (Cont.) All other parameters were left unchanged as per IEEE 802.11b standard Simulation was conducted for TCP Tahoe, Reno, New Reno and SACK


Simulation Results – TCP Receive Buffer Size: Simulation Results – TCP Receive Buffer Size


Simulation Results – TCP Receive Buffer Size: Simulation Results – TCP Receive Buffer Size


Simulation Results – Load with No RTS/CTS: Simulation Results – Load with No RTS/CTS


Simulation Results – Load with RTS/CTS: Simulation Results – Load with RTS/CTS


Simulation Results – Packet Size: Simulation Results – Packet Size


Conclusion: Conclusion Using the maximal normalized distance between the actual allocation and the max-min fair share allocation as a fairness metric, TCP fairness was evaluated for TCP Tahoe, Reno, New Reno and SACK by varying TCP receive buffer size, load with and without RTS/CTS and packet size TCP Tahoe was the least unfair protocol but suffered from low throughput


Tentative Conclusions: Tentative Conclusions Fairness best when: TCP receive buffer size is large Load is high and No RTS/CTS is deployed Load is low and RTS/CTS is deployed Packet size is larger for large TCP buffer size


Future Work: Future Work Tentative conclusions need to be studied in much more depth to comprehend the complex behavior of TCP in wireless networks Analyze suggested TCP improvements like Split TCP and ECN for fairness Introduce mobility and then analyze TCP fairness


Acknowledgements: Acknowledgements I am sincerely grateful to my advisor Dr. Harish Sethu for watching, directing and guiding me throughout each stage of this work I am thankful to Dr. Constantine Katsinis and Dr. Kapil Dandekar for serving in my thesis committee I thank all the members of Computer Communications Laboratory for their support and responsiveness


Questions?: Questions?