Designing router scheduling policies: A privacy perspective

Sachin Kadloor, Xun Gong, Negar Kiyavash, Parv Venkitasubramaniam

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We examine a queuing side channel which results from a shared resource between two users in the context of packet networks. We consider the scenario where one of them is a legitimate user and the other is an attacker who is trying to learn about the former's activities. We show that the waiting time of an adversary sending a small but frequent probe stream to the shared resource (e.g., a router) is highly correlated with traffic pattern of the user. Through precise modeling of the constituent flows and the scheduling policy of the shared resource, we describe a dynamic program to compute the optimal privacy preserving policy that minimizes the correlation between user's traffic and attacker's waiting times. While the explosion of state-space for the problem prohibits us from characterizing the optimal policy, we derive a sub-optimal policy using a myopic approximation to the problem. Through simulation results, we show that indeed the sub-optimal policy does very well in high traffic regime. Furthermore, we compare the privacy/delay trade-offs among various scheduling policies, some already widely deployed in scheduling and others suggested by us based on the intuition from the myopic approximation.

Original languageEnglish (US)
Title of host publicationCCS'10 - Proceedings of the 17th ACM Conference on Computer and Communications Security
Number of pages3
StatePublished - 2010
Event17th ACM Conference on Computer and Communications Security, CCS'10 - Chicago, IL, United States
Duration: Oct 4 2010Oct 8 2010

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


Other17th ACM Conference on Computer and Communications Security, CCS'10
Country/TerritoryUnited States
CityChicago, IL


  • Algorithms
  • Security
  • Theory

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Designing router scheduling policies: A privacy perspective'. Together they form a unique fingerprint.

Cite this