Providing Guaranteed Services Without Per Flow Management * Ion Stoica., Hui Zhang Carnegie Mellon University Pittsburgh, PA 15213 e-mail: { istoica, hzhang}Qcs . emu . edu Existing approaches for providing guarant.eed services re- quire routers to manage per fiow states and perform per flow operations [9, 211. Such a statefIr/ network architecture is less scalable and robusl than stateless network architectures like the original IP and the recently proposed Diffserv [3]. However, services provided with current stateless solutions, Diffserv included, have lower flexibility, utilization, and/or assurance level as compared to the services that can be pro- vided with per flow mechanisms. In this paper, we propose techniques that do not require per flow management (either control or data planes) at core routers, but can implement guaranteed services with levels of flexibility, utilization, and assurance similar to those that can be provided with per flow mechanisms. In this way we can simultaneously achieve high quality of service, high scal- ability and robustness. The key technique we use is called Dynamic Packet State (DPS), which provides a lightweighl; and robust mechanism for routers to coordinate actions and implement distributed algorithms. We present an imple- mentation of the proposed algorithms that has minimum incompatibility with IPvI. 1 Introduction Cut-rent IP networks provide one simple service: the best- effort datagram delivery. Such a simple service model allows IP routers to be stateless: except routing state, which is highly aggregated, routers do not keep any ot,her fine grain information about traffic. Providing a minimalist service model and having the “stateless waist” in the protocol hour- glass allows the Internet to scale with both the size of the network and heterogeneous applications and technologies. Together, they are two of the most important technical rea- sons behind the success of the Internet. ‘This research was sponsored by DARPA under contract numbers N66001-96-C-8528 and E3060?-97-2-0387, and by NSF under grant numbers Career Award NCR-9624979 and ANI-9814929. Additional support was provided by Intel Corp. Views and conclusions contained in this document. are those OC the authors and should not be inter- preted as representing the official policies, either expressed or implied, of DARPA, NSF, Intel, OF the U.S. government. Permission to make digital or hard copies of all or part of fhis work for personal or classroom use is granted without fee provided fhat copies are not made or distributed for profit or commercial advan- tage and that copies bear this notice and the full citation on the first page. To copy otherwise, fo republish, to post on servers or fo redistribute fo lists. requires prior specific permission and/or a fee. SIGCOMM ‘99 E/99 Cambridge, MA, USA 0 1999 ACM 1.56113.135.6/99/0006...$5.00 As the Internet evolves into a global communication in- frastructure, there is a growing need to support more so- phisticated services (e.g., traffic management, QoS) than the traditional best-effort service. Two classes of solut.ions emerge: those maintaining the stateless property of the orig- inal IP architecture, and those requiring a new statefular- chitecture. Examples of stateless solutions are RED for con- gestion control [ll] and Differentiated Service (Diffserv) [3] for &OS. The corresponding examples of stalefvl solutions are Fair Queueing [8] for congestion control and Integrated Service (Intserv) [31] for QoS. In general, stat,eful solu(;ions can provide more powerful and flexible services. For exam- ple, compared with RED, Fair Queueing can protect well- behaving flows from misbehaving ones and accommodate heterogeneous end-to-end congestion control algorithms [16, 221. Similarly, as discussed in Section 2, services provided by lntserv solutions have higher flexibility, utilization, and/or assurance level than those provided by Diffserv solutions. However, as also discussed in Section 2, stateful solutions are less scalable and robust than their stateless counterparts. The question we want t,o answer is: is it possible to have the best of the two worlds, i.e.: providing services as powerful as those implemented by stateful networks, while utilizing algorit.hms as scalable and robust as those used in stateless net,works? While we cannot. answer the above question in its full generality, we can answer it in some specific cases of practical interest. We consider a network architecture similar to the Diffserv architecture, called Scalable Core or SCORE, in which only edge routers perform per flow management., while core routers do not. As illustrated in Figure 1, t,he goal of a SCORE network is to approximate the service provided by a reference statefulnetwork. In [26] we have shown that a SCORE network can achieve fair bandwidth allocation by approximating the service provided by a reference network in which every node performs fair queueing. In this paper, we will show that a SCORE network can provide end-to-end per flow delay and bandwidth guaran- tees as defined in Intserv. Current Intserv solutions assume a stateful network in which two types of per flow state are needed: forwarding state, which is used by the forward- ing engine to ensure fixed path forwarding, and QoS state’, which is used by both the admission control module in the control plane and the classifier and scheduler in the dat.a plane. In [27], we have proposed an algorithm that imple- ments fixed path forwarding with no per flow forwarding ‘In the context of RSVP, we use “QoS” state to refer to both the flow spec and the filter spec. 81(a) Reference Nelwork (b) SCORE Network Figure 1: (a) .4 reference