Virtual time reference system: A unifying scheduling framework for scalable support of guaranteed services

We propose and develop a novel virtual time reference system as a unifying scheduling framework to provide scalable support for guaranteed services, T his virtual time reference system is designed as a conceptual framework upo n which guaranteed services can be implemented in a scalable manner using t he DiffServ paradigm, The key construct in the proposed virtual time refere nce system is the notion of packet virtual time stamps, whose computation i s core stateless, i,e,, no per-flow states are required for its computation . In this paper, we lay the theoretical foundation for the definition and c onstruction of packet virtual time stamps. We describe how per-hop behavior of a core router (or rather its scheduling mechanism) can be characterized via packet virtual time stamps, and based on this characterization, establ ish end-to-end per-flow delay bounds. Consequently, we demonstrate that, in terms of its ability to support guaranteed services, the proposed virtual time reference system has the same expressive power and generality as the I ntServ model. Furthermore, we show that the notion of packet virtual time s tamps leads to the design of new core stateless scheduling algorithms, espe cially work-conserving ones. In addition, our framework does not exclude th e use of existing scheduling algorithms such as stateful fair queuing algor ithms to support guaranteed services.