Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule

We study the problem of providing end-to-end delay guarantees in connection-oriented networks. In this environment, multiple-hop sessions coexist and interfere with one another. Parekh and Gallager (1993, 1994) showed that the weighted fair queueing (WFQ) scheduling discipline provides a worst-case delay guarantee comparable to 1/(ρi)×K _i for a session with rate ρ_i and K_i hops. Such delays can occur since a session-i packet can wait for time 1/(ρi) at every hop. We describe a work-conserving scheme that guarantees an additive delay bound of approximately 1/(ρi)+K_i . This bound is smaller than the multiplicative bound 1/(ρi)×K_i of WFQ, especially when the hop count K _i is large. We call our scheme coordinated-earliest-deadline-first (CEDF) since it uses an earliest deadline-first approach in which simple coordination is applied to the deadlines for consecutive hops of a session. The key to the bound is that once a packet has passed through its first server, it can pass through all its subsequent servers quickly. We conduct simulations to compare the delays actually produced by the two scheduling disciplines. In many cases, these actual delays are comparable to their analytical worst-case bounds, implying that CEDF outperforms WFQ