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 showed that the Weighted Fair Queueing (WFQ) scheduling discipline provides a worst-case delay guarantee comparable to 1 over pi x K sub i for a session with rate p sub i and K sub i hops. Such delays can occur since a session-i packet can wait for time 1 over pi at every hop. We describe a work-conserving scheme that guarantees an additive delay bound of approximately 1 over pi + K sub i. This bound is smaller than the multiplicative bound 1 over pi x K sub i of WFQ, especially when the hop count K sub 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 dealines 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.