Transcript Document
Design, and Evaluation of a Partial State Router Phani Achanta A. L. Narasimha Reddy Dept. of Electrical Engineering Texas A&M University June 22 2004, ICC [email protected] Texas A & M University 1 Motivation Increasing non-responsive traffic Increased DoS attacks Multimedia traffic reduced fairness Bandwidth denial attacks appear as nonresponsive traffic Need for mechanisms to control the high bandwidth flows Identification of high bandwidth flows Control of High bandwidth flows [email protected] Texas A & M University 2 Previous work Per-flow queuing mechanisms address these issues Maintain per flow state FQ, LQD Scalability concerns Scalable single queue mechanisms cannot provide ‘flow isolation’ Stateless schemes base decisions on overall characteristics observable at the router Droptail, RED, Diffserv Fail to contain aggressive flows [email protected] Texas A & M University 3 Previous work Denial of Service Attacks are addressed on a per-attack basis Network ingress filtering Need for scalable mechanisms Partial state mechanisms [email protected] Texas A & M University 4 Observations Internet traffic is heavy tailed Bulk of traffic is carried by a few flows (elephants) Bulk of the flows are short-lived (mice) Dropping packets from short-term flows does not alleviate the network congestion Class based congestion control does not take into account responsiveness of the traffic Need a scheme for a quantitative policydriven control of bandwidth Partial State schemes [email protected] Texas A & M University 5 Partial State Routers Maintain a fixed amount of state State is managed by sampling or caching techniques Challenge: How do you manage state effectively to capture information about elephants? [email protected] Texas A & M University 6 Scheme - Outline Partial state can be used to identify non-responsive flows, bandwidth hogs or high bandwidth flows Normal flows are handled in a stateless fashion [email protected] Texas A & M University 7 LRU-FQ Partial state scheme Identification of high-bandwidth, nonresponsive flows Cache contains Least Recently Used (LRU) flows Probabilistically replaces the bottom entry of LRU List contains mostly non-responsive high bandwidth flows Penalizing of non-responsive flows Employ fair queuing mechanism between nonresponsive (cached) and responsive classes Ensures granular control of the proportion of nonresponsive traffic that a router wants to handle [email protected] Texas A & M University 8 LRU-FQ flow chart – enqueue event Packet Arrival No Is Flow in Cache? Yes Does Cache Have space? No Admit flow with Probability ‘p’ Yes Record flow details Initialize ‘count’ to 0 Increment ‘count’ Move flow to top of cache Is ‘count’ >= ‘threshold’ Yes Is Flow Admitted? No No Yes Enqueue in Partial state Queue [email protected] Texas A & M University Enqueue in Normal Queue 9 LRU-FQ flow chart – dequeue event Dequeue event results in selection of a packet from either queues based on the Start Time Fair Queue algorithm The weights assigned to the individual queues determine the service allotted to each class of flows [email protected] Texas A & M University 10 LRU cache behavior LRU policy with probabilistic admission ensures only high bandwidth flows remain over a period of time Non-responsive high bandwidth flows percolate to the top of the LRU cache. Web mice which might corrupt the cache are controlled by the ‘threshold’ parameter [email protected] Texas A & M University 11 Implementation Issues on Linux [email protected] Texas A & M University 12 Linux IP packet forwarding Local packet Deliver to upper layers UPPER LAYERS Route to destination Update Packet Error checking Verify Destination IP LAYER Packet Enqueued Scheduler invokes Bottom half Request Scheduler To invoke bottom half Packet Arrival Design space Scheduler runs Device driver LINK LAYER Device Prepares packet Packet Departure Check & Store Packet Enqueue pkt [email protected] Texas A & M University 13 Linux Kernel Traffic control Filters are used to distinguish between different classes of flows Each class of flows can be further categorized into subclasses using filters Queuing disciplines control how the packets are enqueued and dequeued [email protected] Texas A & M University 14 LRU-FQ Implementation LRU-FQ is distributed among various QoS components of Linux. LRU component of the scheme is implemented as a filter. All parameters of LRU – threshold, probability, and cache size – are passed as parameters to the filter LRU cache is maintained within the filter. [email protected] Texas A & M University 15 LRU-FQ implementation Start Time Fair queuing is implemented as a queuing discipline. Each queue is scheduled based on its weight Existing Linux FQ queue disciplines work only for flows within a queue. Modified packet structure skbuff to carry STFQ start and finish tags. [email protected] Texas A & M University 16 LRU-FQ Validation Timing Analysis Timing Analysis 95.72 95.7 Received Tput (Mbps) 95.68 Normal Routing 95.66 Diffserv Routing Start Time FQ & LRU 95.64 95.62 95.6 0 5 10 15 20 25 30 35 40 45 Time Delay (usec) [email protected] Texas A & M University 17 LRU-FQ validation [email protected] Texas A & M University 18 Experimental Setup and Results [email protected] Texas A & M University 19 Experimental Test bed [email protected] Texas A & M University 20 Experiment 1 – Non-responsive flows Containing nonresponsive flows: [email protected] cache size=12, threshold=125, p=1/50 20 TCP long term flows varying number of UDP flows to study cache efficacy on varying weights of the queues. Texas A & M University 21 Results – Non-responsive [email protected] Texas A & M University 22 Experiment 2 – Non-responsive flows To study effectiveness of scheme with reduced non-responsive flow rates threshold = 125, probability = 1/50 cache size=12 20 long term TCP flows [email protected] Texas A & M University 23 Results – Non-responsive [email protected] Texas A & M University 24 Experiment 3 – Web mice vs Elephants Web mice versus elephants effect of long term loads on web mice long term load contains both responsive an nonresponsive loads probability=1/50, threshold=125, cache=12 [email protected] Texas A & M University 25 Results – Web mice [email protected] Texas A & M University 26 Results – Web mice [email protected] Texas A & M University 27 Experiment 4 – Cache size Effect of varying cache size to study impact of cache size on performance of the scheme probability= 1/55, threshold = 125 number of TCP flows=20 equal weights for both queues. [email protected] Texas A & M University 28 Results – Cache size [email protected] Texas A & M University 29 Experiment 5 - Workloads Performance under normal workloads working of scheme when non-responsive loads are absent or use their fair share of bandwidth cache size = 9, threshold =125 probability = 1/55 [email protected] Texas A & M University 30 Results – Normal workload [email protected] Texas A & M University 31 Results – Mixed workload [email protected] Texas A & M University 32 Conclusion Proposed, implemented and evaluated an LRU based partial state scheme (LRU-FQ) LRU-FQ shown to enable quantitative control of non-responsive traffic LRU-FQ shown to provide better performance for web mice flows [email protected] Texas A & M University 33 Future work Study of aggregate traffic instead of flow-specific schemes source based aggregation can help identifying DoS attacks from a single network Identification of proportion of nonresponsive traffic in order to automate tuning of the LRU-FQ scheme [email protected] Texas A & M University 34 Stateless AQM schemes DropTail FIFO based - Easy to implement Full Queues and Lock-Out problems variants – Drop from front, Random Drop RED manages the average queue length by marking or dropping packets early does not contain aggressive flows [email protected] Texas A & M University 35 Stateless AQM schemes BLUE bases decisions on two events – packet losses due to Full queues and link idle times. the two events control congestion signaling probability does not contain aggressive flows. CHOKe Incoming packets are matched with random packet in queue to arrive at a drop strategy. does not contain aggressive flows. [email protected] Texas A & M University 36 Stateful AQM schemes Longest Queue Drop (LQD) per flow queue of packets packets from longest queue dropped upon exhaustion of buffers Flow RED (FRED) employs per flow RED and Fair Queuing alleviates some RED problems but requires per-flow queue [email protected] Texas A & M University 37 Packet State AQM schemes Diffserv packets marked ‘in’ and ‘out’ based on QoS contract. ‘out’ packets dropped disproportionately thus securing QoS for ‘in’ packets. Core-Stateless Fair Queuing packets carry the edge router’s estimate of fair rate on the outgoing link the fair rate is used to arrive at the forwarding probability. [email protected] Texas A & M University 38 Partial State AQM schemes Stabilized RED: SRED identification of misbehaving flows – ‘zombie’ list list is pruned by probabilistic replacement of a random entry with the incoming packet SACRED random sampling and holding to maintain a cache of ‘marked’ flows Random flows observed when average queue length exceeds a sampling threshold. At dropping threshold, packets are dropped from observed flows exceeding a limit share threshold [email protected] Texas A & M University 39 Partial State AQM schemes Red-PD makes use of the drop history observed at an RED router arrives at a list of flows exceeding a target threshold LRU-RED maintains an LRU to identify top ‘n’ flows. modifies RED to penalize them more than normal flows. [email protected] Texas A & M University 40 Active Queue Management schemes 1. Stateless 2. decisions based on overall characteristics observable at the router queue like average queue length, aggregate arrival and departure rates etc. DropTail, RED, BLUE, CHOKe Stateful per-flow state maintained to administer the scheme. Longest Queue Drop (LQD), FRED [email protected] Texas A & M University 41 Active Queue Management schemes Packet state 3. state is maintained within packets routers base decisions on the state within packets Diffserv, CSFQ Partial state 4. maintain a limited amount of state state is pruned using sampling and caching SRED, SACRED, RED-PD, LRU-RED [email protected] Texas A & M University 42 Denial of Service Solutions Network ingress filtering Traceback algorithms filter spoofed addresses throttle the attacker at the source network MULTOPS multi-level tree containing packet statistics proposed for bandwidth attack detection [email protected] Texas A & M University 43 Observations Stateful schemes are effective but not scalable Stateless schemes fail to protect normal flows from aggressive flows Earlier partial state schemes rely on RED mechanism for resource control Earlier work provides qualitative improvement of performance for responsive flows and short term flows [email protected] Texas A & M University 44 Possible Applications of Partial State schemes Control of non-responsive proportion of traffic Identification of top bandwidth hogs to alleviate certain DoS scenarios Better service for web mice lower delay bounds and larger connection rates weights of the fair queuing control the delay Control of Bandwidth allocation for normal traffic buffers assigned per queue control the bandwidth [email protected] Texas A & M University 45