Scheduling algorithms for bounded delay service in virtual networks

With their widespread deployment, the need to provide QoS in virtual networks is being realized. We show that traditional scheduling algorithms like WFQ are incapable of providing a bounded delay service in a virtual network. The problem arises because traffic of a number of sessions sharing a virtual link in a virtual network is aggregated and tunneled through the physical network, which cannot isolate the traffic of well behaved sessions from that of misbehaving sessions. We show that this problem can be solved by regulating output burstiness on virtual links. Using the theory of latency rate servers, we show that latency rate servers with bounded output burstiness, may be used in a virtual network to provide bounded delay service. This gives a method to design a generic class of scheduling algorithms for virtual networks. Finally, we discuss how to integrate best effort and real-time traffic in a virtual network