CS 636 Internetworking Ramana Kompella ROUTER ALGORITHMICS Lecture 15: Packet scheduling Some slides courtesy of Rong Pan, Nick McKeown 1 Aggregation ◦ IP lookups scaled by using up only 150,000 prefixes for over 100 Million nodes ◦ Apply aggregation in the context of fair queuing ◦ Focus on scheduling aggregates instead of individual flows  Random aggregation  Edge aggregation CS 636 Internetworking 2 Routers keep state for a fixed amount, say 100,000 flows on which they do DRR  A packet can then be hashed based on its header fields to map to one of several queues  Multiple flows map to a given flow ◦ 200,000 flows  ~ 2 flows share same class  Problems: ◦ Flows compete with different flows at different routers ◦ No explicit differentiation between flows CS 636 Internetworking 3 Differentiated services (Diffserv) also aggregates flows into classes  Edge routers mark packet class by using a standardized value in the IP TOS field.  Expedited service ◦ Certain bandwidth reserved for this class  Assured service ◦ Lower drop rate for RED in output queues CS 636 Internetworking 45  Fair Queueing requires per flow state in routers ◦ Maybe impractical for very high speed routers  Core Stateless Fair Queueing eliminates the state at core routers …  … but only approximates FQ’s behavior CS 636 Internetworking6  Queue Management ◦ Drop as a way to feedback to TCP sources ◦ Part of a closed-loop  Traditional Queue Management ◦ Drop Tail ◦ Problems  Active Queue Management ◦ RED ◦ CHOKe ◦ AFD7 • Lock out • Full queue • Bias against bursty traffic – long delay • Global synchronization – TCP flows back off and transmit synchronously8 yes Drop the new packet end Admit packet with a probability p end AvgQsize > Maxth? yes Arriving packet no Admit the new packet end AvgQsize > Minth? no9 minth maxth 0 Average Queue Size Drop Probability 1 maxp Standard EWMA: avgq = (1-wq) avgq + wqqlen ◦ Special fix for idle periods  Upper bound on wq depends on minth ◦ Want to ignore transient congestion ◦ Can calculate the queue average if a burst arrives  Set wq such that certain burst size does not exceed minth  Lower bound on wq to detect congestion relatively quickly  Typical wq = 0.002 Problem: what to do with non-cooperative flows?  Fair queuing achieves isolation using per-flow state – expensive at backbone routers ◦ How can we isolate unresponsive flows without per-flow state?  RED penalty box ◦ Monitor history for packet drops, identify flows that use disproportionate bandwidth ◦ Isolate and punish those flows Fair Random Early Drop (Sigcomm, 1997)  Maintain per flow state only for active flows (ones having packets in the buffer)  minq and maxq  min and max number of buffers a flow is allowed occupy  avgcq = average buffers per flow  Strike count of number of times flow has exceeded maxq Flows that send little data and want to avoid loss  minq is meant to protect these  What should minq be? ◦ When large number of flows  2-4 packets  Needed for TCP behavior ◦ When small number of flows  increase to avgcq Non-adaptive flows ◦ Flows with high strike count are not allowed more than avgcq buffers ◦ Allows adaptive flows to occasionally burst to maxq but repeated attempts incur penalty Same objective as RED Penalty Box ◦ Identify and penalize misbehaving flows  Create L hashes with N bins each ◦ Each bin keeps track of separate marking/drop probability (pm) ◦ Pm is increased if # of packets > threshold and decreased if # of packets = 0. ◦ Flow uses minimum pm of all L bins it belongs to ◦ Non-misbehaving flows hopefully belong to at least one bin without a bad flow  Large numbers of bad flows may cause false positives False positives can continuously penalize same flow  Solution: moving hash function over time ◦ Bad flow no longer shares bin with same flows ◦ Is history reset does bad flow get to make trouble until detected again?  No, can perform hash warmup in background17 yes Drop the new packet end Admit packet with a probability p end AvgQsize > Maxth? yes Arriving packet no Admit the new packet end AvgQsize > Minth? no yes no Drop both matched packets end Draw a packet at random from queue Flow id same as the new packet id ? yes Drop the new packet end Admit packet with a probability p end no AvgQsize > Maxth? no18 • A randomly chosen packet more likely from the unresponsive flow • Adversary can’t fool the system UDP flow Can we add bandwidth guarantees for flows that are placed in the common queues without segregation ? ◦ E.g., an ISP wants to restrict NEWS traffic to 1Mbps ◦ UDP traffic restricted to some value.  Token bucket policing/shaping ◦ Uses a single queue ◦ One counter per flow CS 636 Internetworking 19CS 636 Internetworking 20 time Cumulative bytes ρ"σ"Number of bytes that can arrive in any period of length t is bounded by: This is called “(σ,ρ) regulation” A1(t)CS 636 Internetworking 21 Tokens at rate,ρ"Token bucket size,σ"Packet buffer Packets Packets One byte (or packet) per tokenCS 636 Internetworking 22 Tokens at rate,ρ"Token bucket sizeσ"Variable bit-rate compression To network time bytes time bytes time bytes ρ"CCS 636 Internetworking 23 Tokens at rate,ρ"Token bucket sizeσ"time bytes time bytes ρ"C Router From