TARDIS: Stably shifting traffic in space and time (extended version)

Richard G. Clegg, Raul Landa, João Taveira Araújo, Eleni Mykoniati, David Griffin, Miguel Rio
Extended version of SIGMETRICS 2014 short paper, 2014
This paper describes TARDIS (Traffic Assignment and Retiming Dynamics with Inherent Stability) which is an algorithmic procedure designed to reallocate traffic within Internet Service Provider (ISP) networks. Recent work has investigated the idea of shifting traffic in time (from peak to off-peak) or in space (by using different links). This work gives a unified scheme for both time and space shifting to reduce costs. Particular attention is given to the commonly used 95th percentile pricing scheme. The work has three main innovations: firstly, introducing the Shapley Gradient, a way of comparing traffic pricing between different links at different times of day; secondly, a unified way of reallocating traffic in time and/or in space; thirdly, a continuous approximation to this system is proved to be stable. A trace-driven investigation using data from two service providers shows that the algorithm can create large savings in transit costs even when only small proportions of the traffic can be shifted.
This is an extended unpublished 14 page version with all proofs of the short paper (2 pages) accepted for SIGMETRICS 2014 as a poster/short paper.
  title = {TARDIS: Stably shifting traffic in space and time (extended version)},
  authors= {Clegg, R.G. and Landa, R. and Araujo, J.T. and Mykoniati, E. and Griffin, D. and Rio, M.},
  howpublished = {\url{http://www.richardclegg.org/tardis_extended_unpublished_2014}}