Birkhoff-von Neumann switching with statistical traffic profiles

Offline scheduling is attractive when the traffic profile is known a priori   since the complexity of online scheduling is largely removed. Given any admissible rate matrix Λ=(λij)Λ=(λij), Birkhoff-von Neumann decomposition offers a quasi-offline scheduling strategy that can provide a service rate of at least λijλij for each flow (i,j)(i,j) without internal speedup. This paper extends the Birkhoff-von Neumann switching strategy to consider traffic profiles in which the traffic demands are specified as statistical distributions rather than fixed rates.