Packet scheduling algorithms control the order in which a system serves network packets, which can have significant impact on system performance. Recent work in adversarial scheduling has shown that Weighted Shortest Job First (WSJF) – scheduling packets by the ratio of job size to packet size – significantly mitigates a system's susceptibility to algorithmic complexity attacks (ACAs), a particularly dangerous class of Denial-of-Service (DoS) attacks. WSJF relies on knowledge of a packet's job size, information that is not available a priori. In this work, we explore the theoretical implications of using heuristics for job size estimation. Further, we consider preemption as another technique that may help protect systems when job sizes are unknown. We find that heuristics with certain properties (e.g., estimated job-size-to-packet-size ratios increasing monotonically with the actual ratios, step function-based job categorization) can protect systems against ACAs with varying guarantees, while preemption alone does not.

10 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu