  Network routing problems are common across many engineering applications.
Computing optimal routing policies requires knowledge about network demand,
i.e., the origin and destination (OD) of all requests in the network. However,
privacy considerations make it challenging to share individual OD data that
would be required for computing optimal policies. Privacy can be particularly
challenging in standard network routing problems because sources and sinks can
be easily identified from flow conservation constraints, making feasibility and
privacy mutually exclusive.
  In this paper, we present a differentially private algorithm for network
routing problems. The main ingredient is a reformulation of network routing
which moves all user data-dependent parameters out of the constraint set and
into the objective function. We then present an algorithm for solving this
formulation based on a differentially private variant of stochastic gradient
descent. In this algorithm, differential privacy is achieved by injecting
noise, and one may wonder if this noise injection compromises solution quality.
We prove that our algorithm is both differentially private and asymptotically
optimal as the size of the training set goes to infinity. We corroborate the
theoretical results with numerical experiments on a road traffic network which
show that our algorithm provides differentially private and near-optimal
solutions in practice.
