Designing router scheduling policies: A privacy perspective

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.