Internet Engineering Task Force D. Clark / J. Wroclawski INTERNET-DRAFT MIT LCS draft-clark-diff-svc-alloc-00.txt July, 1997 Expires: 12/97 An Approach to Service Allocation in the Internet Abstract This note describes the Service Allocation Profile scheme for differential service allocation within the Internet. The scheme is based on a simple packet drop preference mechanism at interior nodes, and highly flexible service profiles at edges and inter- provider boundary points within the net. The service profiles capture a wide variety of user requirements and expectations, and allow different users to receive different levels of service from the network in a scalable and efficient manner. The note describes the basic form of the mechanism, discusses the range of services that users and providers can obtain by employing it, and gives a more detailed presentation of particular technical, deployment, standardization, and economic issues related to its use. Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress". To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet- Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). NOTE: This draft is a snapshot of a document in progress, and was somewhat arbitrarily cast into its current form at the Internet-Draft Clark/Wroclawski Expires 12/97 [Page 1]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 submission deadline for the Munich IETF. The authors apologize in advance for a certain raggedness of presentation.. 1. Introduction This document describes a framework for providing what has been called differentiated service, or allocated capacity service, in the Internet. The goal of the mechanism is to allocate the bandwidth of the Internet to different users in a controlled way during periods of congestion. The mechanism applies equally to traditional applications based on TCP, such as file transfer, data base access or Web servers, and new sorts of applications such as real time audio or video. The mechanism we describe can provide users with a predictable expectation of what service the Internet will provide to them in times of congestion, and can allow different users to obtain different levels of service from the network. This contrasts with today's Internet, in which each user gets some unpredictable share of the capacity. Our mechanism provides two additional things that are important to this task. First, it allows users and providers with a wide range of business and administrative models to make capacity allocation decisions. In the public Internet, where commercial providers offer service for payment, the feedback will most often be different prices charged to customers with different requirements. This allows the providers to charge differential prices to users that attach greater value to their Internet access, and thus fund the deployment of additional resources to better serve them. But whether pricing, or some other administrative control is used (as might apply in a corporate or military network), the same mechanism for allocating capacity can be used. The mechanism also provides useful information to providers about provisioning requirements. With our mechanism in place, service providers can more easily allocate specific levels of 3assured2 capacity to customers, and can easily monitor their networks to detect when the actual service needs of their customers are not being met. While this document does describe a mechanism, this is a small part of its goal. There are a number of mechanisms that might be proposed, and the issue is not just demonstrating which of them works (most do work in some fashion), but to discuss what the problem to be solved actually is, and therefore which of the possible mechanisms best meets the needs of the Internet. This document is thus as much about what the problem actually is, as it is about a preferred solution. Clark/Wroclawski Expires 12/97 [Page 2]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 1.1 Separating results from mechanism An essential aspect of this scheme is the range of services the user can obtain using the mechanism. The mechanism is obviously not useful if it does not meet a current need. Some initial requirements we see for services are that they must be useful, easy to understand, possible to measure (so the user can tell whether he is getting the service he contracted for), and easy to implement. At the same time, we should try very hard not to embed a specific set of services into the core of the Internet. As we gain experience in the marketplace, we may discover that our first speculations are wrong about what service the user actually wants. It should be possible to change the model, evolve it, and indeed to try different models at the same time to see which better meets the needs of the user and the market. So this scheme has the two goals: defining and implementing a first set of services, but permitting these services to be changed without modifying the "insides" of the Internet, specifically the routers. We will return later to the discussion of different sorts of services. 2. Outline of this document This document is organized as follows: Section 3 describes the basic mechanism, to give a general idea of how such a service can be implemented. Section 4 discusses the services which might be desired. It proposes a first set of services that might be implemented, and discusses the range of services that can be built out of this mechanism. Section 5 describes the location of service profiles in the network. Section 6 describes details of the mechanism. These include our specific algorithm for the dropper, issues concerning rate control of TCP, and dealing with non-responsive flows. Section 7 compares this mechanism with some alternatives. Section 8 discusses deployment issues, incremental deployment, and what portions of the mechanism require standardization. Section 9 discusses security issues. 3. The basic scheme Clark/Wroclawski Expires 12/97 [Page 3]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 The general approach of this mechanism is to define a service profile for each user, and to design a mechanism in the router that favors traffic that is within those service profiles. The core of the idea is very simple -- monitor the traffic of each user as it enters the network, and tag packets as being "in" or "out" of their service profile. Then at each router, if congestion occurs, preferentially drop traffic that is tagged as being "out". Inside the network, at the routers, there is no separation of traffic from different users into different flows or queues. The packets of all the users are aggregated into one queue, just as they are today. Different users can have very different profiles, which will result in different users having different quantities of "in" packets in the service queue. A router can treat these packets as a single commingled pool. This attribute of the scheme makes it very easy to implement, in contrast to a scheme like current RSVP reservations, in which the packets must be explicitly classified at each node. We have more to say about this issue below. To implement this scheme, the routers must be augmented to implement our dropping scheme, and a new function must be implemented to tag the traffic according to its service profile. This algorithm can be implemented as part of an existing network component (host, access device or router) or in a new component created for the purpose. Conceptually, we will refer to it as a distinct device called a "profile meter". We use the term "meter" rather than "tagger", because, as we will discuss below, the profile meter can actually take a more general set of actions. The idea of a service profile can be applied at any point in the network where a customer-provider relationship exists. A profile may describe the needs of a specific user within a campus, the service purchased by a corporate customer from an ISP, or the traffic handling agreement between two international providers. We discuss the location of profiles further in Section 5. The description above associates the profile with the traffic sender. That is, the sender has a service profile, the traffic is tagged at the source according to that profile, and then dropped if necessary inside the network. In some circumstances, however, it is the receiving user that wishes to control the level of service. The web provides a simple example; a customer using his browser for business research may be much more interested in a predictable level of performance than the casual surfer. The key observation is that "value" in the network does not always flow in the same direction as the data packets. Thus, for full generality, a "dual" mechanism is required, that can Clark/Wroclawski Expires 12/97 [Page 4]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 be either "sender driven" or "receiver driven". Most of this document is written, for simplicity, in terms of a sender scheme, but we briefly describe the receiver version as well, and discuss the circumstances in which it is important. In evaluating alternative mechanisms, it is important to see if both a sender and receiver version can be built. In later sections, we discuss the specifics of the profiling or tagging mechanism and the treatment of profiled packets within the network. First we turn to the question of the range of services the mechanism ought to support. 4. Range of services As discussed above, there are two general issues concerning service models. First, we want to start out by implementing a simple set of services, which are useful and easy to understand. At the same time, we should not embed these services into the mechanism, but should build a general mechanism that allows us to change the services as our experience matures. Our scheme provides this flexibility. To oversimplify, a service is defined by the profile meter, which implements the user's service profile. To change the service, it is necessary "only" to change the profile meter. The routers in the interior of the network implement a single common mechanism which is used by the different meters to provide different services. Three things must be considered when describing a service: - what exactly is provided to the customer (an example might be "one megabit per second of bandwidth, continuously available") - to where this service is provided (examples might be a specific destination, a group of destinations, all nodes on the local provider, or "everywhere") - with what level of assurance is the service provided (or alternately, what level of performance uncertainty can the user tolerate) These things are coupled; it is much easier to provide "a guaranteed one megabit per second" to a specific destination than to anywhere in the Internet. 4.1 A first service model As a place to start, a particularly simple service might provide the equivalent of a dedicated link of some specified bandwidth from source to destination. (The virtue of this simple model has been Clark/Wroclawski Expires 12/97 [Page 5]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 clearly articulated by Van Jacobson.) This model is easy for the user to understand -- he can take his existing application, connect it across a physical link and see how it performs. If he can make it work in that context, then this service will allow him to run that application over the Internet. This model has been implemented in a number of network architectures, with different "enhancements". The CBR service of ATM is an example, as is (to some extent) the CIR mechanism of Frame Relay. However, there are some issues and limitations to this very simple model. One very important limit to a pure virtual link model is that the user may not wish to purchase this virtual link full time. He may need it only some of the time, and in exchange would hope to obtain a lower cost. A provider could meet this desire by offering a more expressive profile; say a committed bandwidth with some duty cycle, e.g. "3 mb/s with a 5% duty cycle measured over 5 minutes". Or, the provider could offer the user a rebate based on observed (non)usage, or allow him to reserve the capacity dynamically on demand. A second issue is whether the user can exceed the capacity of the virtual link when the network is unloaded. Today, the Internet allows its users to go faster under that circumstance. Continuing to capture that benefit may be important in user acceptance. The CIR of Frame Relay works this way, and it is an important aspect of its market appeal. An equally important issue is that the user may not wish to set up different distinguished committed bandwidth flows to different destinations, but may prefer to have a more aggregated commitment. There are several drawbacks to making distinct bandwidth commitments between each source and destination. First, this may result in a large number of flow specifications. If the user is interested in 1000 network access points, he must specify one million source- destination pairs. Frame Relay has this specification problem. Second, the sum of the distinct commitments for any source (or destination) cannot exceed the physical capacity of the access link at that point, which may force each individual assurance to be rather small. Finally, the source-destination model implies that the user can determine his destinations in advance, and in some cases that he understands the network topology; two situations which are not universally true. In fact, several variations of service commitment might make sense to different users; from one source to a specific destination, from a source to a pool of specified destinations (one might configure a Virtual Private Network in this way) and finally from a source to "anywhere", which could mean either all points on the ISP, on a Clark/Wroclawski Expires 12/97 [Page 6]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 collection of ISPs, or any reachable node. The latter sorts of commitments are by their nature more difficult to offer with high assurance. There is no way to know for sure what the service will be to any specific destination, because that depends on what other traffic is leaving the source, and what other traffic is arriving at the destination. Offering commitments to "anywhere within the ISP" implies that the ISP has provisioned its resources adequately to support all in-profile users simultaneously to the same destination. Offering commitments to "anywhere at all" implies that all ISPs in any reachable path from the user have provisioned sufficiently, which is most unlikely. 4.2 Managing bursty traffic Not all Internet traffic is continuous in its requirement for bandwidth. Indeed, based on measurements on the Internet, much of the traffic is very bursty. It may thus be that a service model based on a fixed capacity "virtual link" does not actually meet user's needs very well. Some other more complex service profile that permits bursty traffic may be more suitable. It is possible to support bursty traffic by changing the profile meter to implement this new sort of service. The key issue is to insure, in the center of the network, that there is enough capacity to carry this bursty traffic, and thus actually meet the commitments implied by the outstanding profiles. This requires a more sophisticated provisioning strategy than the simple "add 'em up" needed for constant bit-rate virtual links. A body of mathematics that is now maturing provides a way to relate the bursty behavior of a single flow to the resulting implications for the required overall bandwidth when a number of such flows are combined. (see, for example [Kelly97]). This sort of analysis can be employed as a way to predict the capacity that must be provided to support profiles describing bursty traffic. As a practical matter, in the center of the existing Internet, at the backbone routers of the major ISPs, there is such a high degree of traffic aggregation that the bursty nature of individual traffic flows is essentially invisible. So providing bursty service profiles to individual users will not create a substantial provisioning issue in the center of the network, while possibly adding significant value to the service as perceived by the user. 4.3 Degrees of assurance The next aspect of sorting out services is to consider the degree of assurance that the user will receive that the contracted capacity will actually be there when he attempts to use it. Clark/Wroclawski Expires 12/97 [Page 7]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 Statistical bandwidth allocation allows the Internet to support an increased number of users, use bandwidth vastly more efficiently, and deal flexibly with new applications and services. However, it does lead to some uncertainty as to the bandwidth that will be available at any instant. Our approach to allocating traffic is to follow this philosophy to the degree that the user can tolerate the uncertainty. In other words, we believe that a capacity allocation scheme should provide a range of service assurance. At one extreme, the user may demand an absolute service assurance, even in the face of some number of network failures. (Wall Street traders often have two phones on their desk, connected by different building wiring to different phone exchanges, so that they can continue to make money even if a central office goes down or half the building burns.) Less demanding users may wish to purchase a service profile that is "usually" available, but may still fail with low probability. The presumption is that a higher assurance service will cost substantially more to implement. We have called these statistically provisioned service profiles "expected capacity" profiles. This term was picked to suggest that the profiles do not describe a strict guarantee, but rather an expectation that the user can have about the service he will receive during times of congestion. This sort of service will somewhat resemble the Internet of today in that users today have some expectation of what performance they will receive; the key change is that our mechanism by which different users can have very different expectations. Statistical assurance is a matter of provisioning. In our scenario, an ISP can track the amount of traffic tagged as "in" crossing various links over time, and provide enough capacity to carry this subset of the traffic, even at times of congestion. This is how the Internet is managed today, but the addition of tags gives the ISP a better handle on how much of the traffic at any instant is "valued" traffic, and how much is discretionary or opportunistic traffic for which a more relaxed attitude can be tolerated. For traffic that requires a higher level of commitment, more explicit actions must be taken. The specific sources and destinations must be determined, and then the paths between these points must be inspected to determine if there is sufficient capacity. There are two approaches. The static approach involves making a long term commitment to the user, and reserving the network resources to match this commitment. This involves some computation based on the topology map of the network to allocate the needed bandwidth along the primary (and perhaps secondary) routes. The dynamic approach involves using a setup or reservation protocol such as RSVP to request the service. This would explore the network path at the time of the request, and reserve the bandwidth from a pool available for Clark/Wroclawski Expires 12/97 [Page 8]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 dynamic services. Information concerning this pool would have to be stored in the routers themselves, to support the operation of RSVP. We have proposed a lightweight version of RSVP, called RSVP with Trusted TOS Tags, or T3, as a way to implement this dynamic service efficiently. Within one ISP, the reservation could be submitted to a central location for acceptance, depending on the design adopted for bandwidth management. It is important to note that traffic requiring this higher level of assurance can still be aggregated with other similar traffic. It is not necessary to separate out each individual flow to insure that it receives it promised service. It is necessary only to insure that sufficient capacity is available between the specific sources and destinations desiring the service, and that the high-assurance packets can draw on that capacity. This implies that there would be two queues in the router, one for traffic that has received a statistical assurance, and one for this higher or "guaranteed" assurance. Within each queue, "in" and "out" tags would be used to distinguish the subset of the traffic that is to receive the preferred treatment. However, some other discriminator must be used to separate the two classes, and thus sort packets into the two queues. Our specific proposal, which we detail later, is that two values of the TOS field be used, one to mean statistical assurance, and one to mean guaranteed assurance. Statistical assurance would correspond to the service delivered across the Internet today, augmented with "in" and "out" tags. An ISP could avoid the complexity of multiple queues and still provide the high-assurance service by over-provisioning the network to the point where all "in" traffic is essentially never dropped, no matter what usage patterns the users generate. It is an engineering decision of the ISP whether this approach is feasible. 4.4 A service profile for the access path In some cases, what the user is concerned with is not the end-to-end behavior he achieves, but the profile for utilizing his access path to the network. For example, users today buy a high-speed access path for two different reasons. One is to transfer a continuous flow of traffic, the other to transfer bursts at high speed. The user who has bursty traffic might want on the one hand an assurance that the bursts can go through at some known speed, but on the other hand a lower price than the user who delivers a continuous flow into the Internet. Giving these two sorts of users different service profiles that describe the aggregated traffic across the access link will help discriminate between them, and provide a basis for differential charging. Clark/Wroclawski Expires 12/97 [Page 9]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 A service profile of the sort discussed here is a reasonable way to capture this sort of requirement. By tagging the traffic that crosses the access path according to some service profile, the ISP commits to forward that subset of the traffic within its region, and only delivers the rest if the network is underloaded. It is instructive to compare this approach to pricing an access path to the more traditional "usage-based" scheme. In the traditional scheme, the actual usage is metered, and the user is charged a fee that depends on the usage. If the user sends more, he pays more. However, since TCP goes faster if the net is underloaded, it is hard for the user (or the ISP aggregating his traffic) to actually regulate his usage. In contrast, a service profile allows two users with different needs to be distinguished (and presumably charged differently) but each user could be charged a known price based on the profile. If the traffic exceeds the profile, the consequence is not increased fees, but congestion pushback if the network is congested. 4.5 An example of a more sophisticated profile Our initial service profile modeled a dedicated link of some set capacity. This service profile is easy to understand at one level, but once one runs TCP over this link, it becomes much harder to predict what behavior can actually be achieved. TCP hunts for the correct rate by increasing its window size until a packet is discarded at the bottleneck point, and then cutting its window size by two (in many current implementations). How this behavior interacts with a link of fixed size is a function of buffer size and implementation details in TCP. A more sophisticated service profile would be one that attempted to provide a specified and predictable throughput to a TCP stream, so long as the TCP was "well-behaved". This would actually make it easier for the user to test the profile, because he could just run a TCP-based application and observe the throughput. This is an example of a "higher-level" profile, because it provides a service which is less closely related to some existing network component and more closely related to the user's actual needs. These profiles are more difficult to define, because they depend on the behavior of both the network and the end-nodes. However, we have experimented with the design of such a profile, and believe that it is possible to implement this sort of service as well. A more detailed description of the profile needed to fix a TCP transfer rate is given in Appendix B. 5. Location of Service Profiles in the Network In the simple sender-based scheme described so far, the function that checks whether traffic fits within a profile is implemented by Clark/Wroclawski Expires 12/97 [Page 10]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 tagging packets as in or out of profile at the edge of the network. The complete story is more complex. A profile describes an expectation of service obtained by a customer from a provider. These relationships exist at many points in the network, ranging from individual users and their campus LANs to the peering relationships between global ISP's. Any such boundary may be an appropriate place for a profile meter. Further, the packet tagging associated with this service profile will, in the general case, be performed by devices at either side of the boundary. One sort, located on the traffic sourcing side of a network boundary, is a "policy meter". This sort implements some policy by choosing the packets that leave the network (or user's machine) with their in-profile bit set, and thus receive the assured service. Another sort, a "checking meter", sits on the arriving- traffic side of a network boundary, checks the incoming traffic, and marks packets as out of profile (or turns off excess in-profile bits) if the arriving traffic exceeds the assigned profile. A general model is that the first meter that the traffic encounters should provide the highest degree of discrimination among the flows. A profile meter could be integrated into a host implementation of TCP and IP, where it could serve to regulate the relative use of the network by individual flows. The subsequent meters, looking only at larger aggregates, serve to verify that there is a large enough overall service contract in place at that point to carry all of the traffic tagged as "in" (the valuable traffic) at the interior points. When a traffic meter is placed at the point where a campus or corporate network connects to an ISP, or one ISP connects to another, the traffic being passed across the link is highly aggregated. The ISP, on the arriving- traffic side of the link, will check only to verify the total behavior. On the traffic sourcing side of the link, an additional profile meter can be installed to verify that tags have been applied according to policy of the user. Additional profile meters installed at intermediate points can provide good feedback on network demand. Consider a specific situation, where traffic is tagged at individual hosts according to policies specific to these hosts, and then passes through a second meter at the point of attachment from the private network to the public Internet. If the number of "in" packets arriving at that point exceeds the aggregate service profile purchased at that point, this means that the user has not purchased enough aggregate capacity to match the needs of his individual policy setting. In the short run, there is no choice but to turn some of these "in" packets to "out", (or to charge an extra fee for carrying unexpected overloads), but in the long run, this provides a basis to negotiate a higher service level with the ISP. So traffic meters actually provide a basis for Clark/Wroclawski Expires 12/97 [Page 11]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 monitoring user needs, and moving users to a higher service profile as needed. 5.1 Controlling the scope of profiles Even in the case where the user wants to obtain a service profile that is not specific to one destination, but rather applies to "all" possible destinations, it is clear that the "all" cannot be literally true. Any service profile that involves an unspecified set of destinations will have to bound the scope of the agreement. For example, a single ISP or a set of co-operating ISPs may agree to provide an assured service profile among all of their end points, but if the traffic passes beyond that point, the profile will cease to apply. The user might be given further options in the design of his profile. For example, if there are regions of restricted bandwidth within the Internet, some users may wish to pay more in order to have their "in" tags define their service across this part of the net, while others may be willing to have their "in" tags reset if the traffic reaches this point. This could be implemented by installing a profile meter at that point in the network, with explicit lists of source-destination pairs that are and are not allowed to send "in" traffic beyond this point. The alternative would be some sort of "zone system" for service profiles that is specified in the packets themselves. See [Clark97] for a discussion of a zone system. 6. Details of the Mechanism This section describes several aspects of our proposed mechanism in more detail. 6.1 Design of the dropper One of the key parts of this scheme is the algorithm in the router that drops "out" packets preferentially during times of congestion. The behavior of this algorithm must be well understood and agreed on, because the taggers at the edge of the network must take this behavior into account in their design. There can be many taggers, with different goals as to the service profile, the degree of aggregation etc. There is only one dropper, and all the routers have to perform an agreed behavior. The essence of our dropper is an algorithm which processes all packets in order as received, in a single queue, but preferentially drops "out" packets. There are other designs that could be proposed Clark/Wroclawski Expires 12/97 [Page 12]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 for queue management, for example to put the "in" packets in a higher priority queue. There are specific reasons why we prefer drop preference to priority queuing for the allocation of best effort traffic, but we delay that discussion until Section 7. The primary design goals of the dropper are the following: - It must allow the taggers to implement a range of service profiles in a useful and understandable way. - If the router is flooded with "out" packets, it must be able to discard them all without harming the "in" packets. In other words, it must deal well with non-conforming flows that do not adjust their sending rate when they observe packet loss. - If the router is receiving a number of "well-behaved" TCP flows, which will (as TCP always does) speed up until they encounter a lost packet, it must have enough real buffering available that once it starts to get overloaded with packets, it can discard "out" packets and still receive traffic bursts for a round trip until the affected TCP slows down. 6.2 RIO -- RED with In and Out Our specific dropping scheme is an extension of the Random Early Detection scheme, or RED, that is now being deployed in the Internet. The general behavior of RED is that, as the queue begins to build up, it drops packets with a low but increasing probability, instead of waiting until the queue is full and then dropping all arriving packets. This results in better overall behavior, shorter queues, and lower drop rates. Our approach is to run two RED algorithms at the same time, one for "in" packets, and one for "out" packets. The "out" RED algorithm starts dropping at a much shorter average queue length, and drops much more aggressively than the "in" algorithm. With proper setting of the parameters, the "out" traffic can be controlled before the queue grows to the point that any "in" traffic is dropped. We call this scheme RIO. There are some subtle aspects to this scheme. The "in" dropper must look at the number of "in" packets in the queue. The "out" dropper must look at the total queue length, taking into account both "in" and "out". This is because the link can be subjected to a range of overloads, from a mix of "in" and "out" traffic to just "out". In both cases, the router must start dropping "outs" before the "in" traffic is affected, and must continue to achieve the basic function of RED; preserving enough free buffer space to absorb transient loads with a duration too short to be affected by feedback congestion Clark/Wroclawski Expires 12/97 [Page 13]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 control. 6.3. Rate control of TCP A useful, but challenging, problem is to build a traffic meter that causes a TCP to send at a specified maximum rate in periods of congestion. Such a meter works by causing the TCP's bandwidth usage (actually congestion avoidance) algorithm to "hunt" between somewhat over and somewhat under the target rate, by tagging packets such that the RIO algorithm will drop them appropriately when the network is loaded. An important aspect of this is that the meter and RIO work together to avoid *too many* closely spaced packet discards, forcing the TCP into slow-start and causing it to obtain less than the desired bandwidth. A detailed description of a traffic meter which meets these objectives is given in Appendix B of this note. 6.4. Dealing with non-responsive flows A well-behaved TCP, or other traffic source that responds similarly to congestion signaled by packet loss, will respond well to the RIO dropper. As more of its packets are marked as "out", one will eventually be dropped. At this point, the source will back off. As a result, most of the time a network of well-behaved TCPs will contain just enough "out" packets to use up any excess capacity not claimed by the "in" packets being sent. But what if there is a source of packets that does not adjust? This could happen because of a poorly implemented TCP, or from a source of packets, such as a video data application, that does not or cannot adjust. In this circumstance, if the unresponsive flow1s packets are marked as out of profile, the flood of "out" packets will cause a RIO router to operate in a different way, but well behaved TCPs and similar flows must continue to receive good service. (If the unresponsive flow1s packets are in profile, the network should be able carry them, and there is no issue.) 6.4.1. Robustness against non-responsive flows In the RIO scheme, once the level of "out" packets exceeds a certain average level, all the incoming "out" packets will be discarded (this is similar to the non-RIO RED behavior). This behavior has the consequence of increasing the router1s queue length. The average queue length will increase by the number of "out" packets that are allowed to sit in the queue before RIO switches over to the phase Clark/Wroclawski Expires 12/97 [Page 14]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 where it drops every "out". There must be enough physical room in the buffer so that even when there are this many "out" packets present, there is enough room for the normal instantaneous bursts of "in" packets which would be seen in any event. Thus, a RIO router may require slightly larger queues than a non-RIO router. In the simulations summarized in Appendix B, the maximum number of "out" packets is approximately 15. (This particular number is not magic -- the point is that it is not 1, nor 100.) So to operate RIO, it will be necessary to increase the minimum physical buffer size by perhaps this amount, or a little more, to allow for swings in the instantaneous numbers of "out" packets as well. But in most circumstances, this is a modest increase in the buffer size. 6.4.2. Filtering out non-responsive flows Although RIO is reasonably robust against overload from non- responsive flows, it may be useful to consider the alternative strategy of singling out non-conforming flows and selectively dropping them in the congested router. There has been work [FF97] towards enhancing the traditional RED scheme with a mechanism to detect and discriminate against non-conforming flows. Discriminating against these flows requires the installation of a packet classifier or filter that can select these packet flows, so that they can be discarded. This adds complexity and introduces scaling concerns to the scheme. These concerns are somewhat mitigated because only the misbehaving flows, not the majority of flows that behave, need be recognized. Whatever classification scheme that basic RED might use can be used by RIO as well. The difference between our framework and RED is that the designers of RED are working to design an algorithm that runs locally in each router to detect non-conforming flows, without any concept of a service profile. In that case, the only sort of traffic allocation that can be done is some form of local fairness. However, with the addition of profile tags, the router can look only at the "out" packets, which by definition represent that portion of a flow that is in excess. This might make it easier to detect locally flows that were non- conforming. The alternative approach would be an indication from the traffic meter that the flow is persistently exceeding the service profile in a time of congestion. This indication, a control packet, could either install a classifier in each potential point of congestion, or flow all the way back to the traffic meter nearest the sender, where the traffic can be distinguished and discarded (or otherwise discriminated against). The latter approach has the benefit that the control packet need not follow the detailed hop-by-hop route of the data packet in reverse, which is hard to do in today's Internet with asymmetric routes. Clark/Wroclawski Expires 12/97 [Page 15]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 We consider the question of whether such a mechanism provides sufficient benefit over the approach of employing local detection of non-responsive flows at each node to be unresolved at present. 7. Alternatives to the mechanism Schemes for differential service or capacity allocation differ in a number of respects. Some standardize on the service profiles, and embed them directly in the routers. As discussed above, this scheme has the advantage that the actual service profile is not a part of what is standardized, but is instead realized locally in the traffic meter, which gives this scheme much greater flexibility in changing the profile. 7.1. Drop preference vs. priority One possible difference is what the router does when it is presented with an overload. Our scheme is based on a specific algorithm for drop preference for packets marked as "out". An alternative would be to put packets marked as "out" in a lower priority queue. Under overload that lower priority queue would be subjected to service starvation, queue overflow and eventually packet drops. Thus a priority scheme might be seen as similar to a drop preference scheme. They are similar, but not the same. The priority scheme has the consequence that packets in the two queues are reordered by the scheduling discipline that implements the priority behavior. If packets from a single TCP flow are metered such that some are marked as "in" and some as "out", they will in general arrive at the receiver out of order, which will cause performance problems with the TCP. In contrast, the RIO scheme always keeps the packets in order, and just explicitly drops some of the "out" packets if necessary. That makes TCP work much better under slight overload. The priority scheme is often proposed for the case of a restricted class of service profiles in which all the packets of a single flow are either "in" or "out". These schemes include the concept of a "premium" customer (all its packets are "in"), or a rate-limited flow (packets that exceed the service profile are dropped at the meter, rather than being passed on.) These proposals are valid experiments in what a service profile should be, but they are not the only possibilities. The drop preference scheme has the advantage that it seems to support a wider range of potential service profiles (including the above two), and thus offers an important level of flexibility. 7.2. More bits? Clark/Wroclawski Expires 12/97 [Page 16]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 A variation on this scheme is to have more than two levels of control -- more than simple "in" and "out". One reason to have more than two levels is to allow the user to express his range of values more completely. With three or four levels of tagging, the user could express what service profile he would like at different levels of congestion -- none, low, medium and severe. The question is whether this actually brings much real incremental value. In commercial networks, which are usually provisioned in a conservative fashion, it is not clear that there will be enough congestion to discriminate between more than two states. In other circumstances, for example military networks where severe service degradation might occur under adverse circumstances, having several levels of usage preference might be helpful. Asking the user to define these several tiers of service profiles raises one issue, however; it presumes that the user is actually able to determine what his needs are to this degree of precision. It is not actually clear that the user has this level of understanding of how he would trade off usage against cost. There is an alternative way to deal with variation in the degree of congestion. Instead of coding the user's desires into each packet, one could imagine a management protocol running in the background that reports to the edges of the network what the current level of congestion is, or whether a special or crisis circumstance exists. Based on information from that protocol, the service profile of the user could be changed. Both approaches may have advantages. An advantage of the first is the lack of need for a management protocol. An advantage of the second is that the management protocol can express a much wider range of policies and reallocation actions. Another reason to have multiple levels of control is to achieve a smoother transition between the two states of a flow. As discussed above, when controlling TCP, because of the specific congestion schemes used in TCP, it is helpful not to drop a number of packets from one flow at once, because it is likely to trigger a full TCP slow- start, rather then the preferable fast recovery action. Having more bits might enhance this discrimination. However, based on our simulations, if we are going to use more bits from the packet header for control, it might be a better option to move to an Explicit Congestion Notification design for the Internet, which seems to provide a better degree of control overall. 8. Deployment Issues 8.1. Incremental deployment plan. No scheme like this can be deployed at once in all parts of the Internet. It must be possible to install it incrementally, if it is to succeed at all. Clark/Wroclawski Expires 12/97 [Page 17]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 The obvious path is to provide these capabilities first within a single ISP. This implies installing RIO routers within the ISP, and tagging the traffic at the access points to that ISP. This requires a profile meter at each access link into that ISP. The meter could maintain a large amount of user-specific information about desired usage patterns between specific sources and destinations (and this might represent a business opportunity), but more likely would provide only rough categories of traffic classification. A user of this ISP could then install a profile meter on his end of the access link, which he controls and configures, to provide a finer- grained set of controls over which traffic is to be marked as "in" and "out". Eventually, meters might appear as part of host implementations, which would permit the construction of profiles that took into account the behavior of specific applications, and which would also control the use of network resources within the campus or corporate area. At the boundary to the region of routers implementing RIO, all traffic must be checked, to make sure that no un-metered traffic sneaks into the network tagged as "in". So the implementation of this scheme requires a consistent engineering of the network configuration within an administrative region (such as an ISP) to make sure that all sources of traffic have been identified, and either metered or "turned out". If some routers implement RIO, and some do not, but just implement simple RED, the user may fail to receive the committed service profile. But no other major failures will occur. That is, the worst that the user will see is what he sees today. One can achieve substantial incremental improvements by identifying points of actual congestion, and putting RIO routers there first. 8.2. What has to be standardized In fact, very little of this scheme needs to be standardized in the normal pattern of IETF undertakings. What is required is to agree on the general approach, and set a few specific standards. 8.2.1. Semantics of router behavior It is necessary to agree on the common semantics that all routers will display for "in" and "out" bits. Our proposal is that routers implement the RIO scheme, as described above. The parameters should be left for operational adjustment. For the receiver-based scheme, the router has to tag packets rather than drop them. We omit the description of the tagging algorithm, Clark/Wroclawski Expires 12/97 [Page 18]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 only noting that it, too, must be agreed to if a receiver-based scheme is to be deployed. 8.2.2. Use of IP precedence field Currently, the three bit precedence field in the IP header is not widely used. Bit x of this field will be used as the "in/out" bit. This bit will be known as the In Profile Indicator, or IPI. The meaning of the IPI is that a 1 value implies "in". This has the effect that the normal default value of the field, 0, will map to the baseline behavior, which is out of profile service. 8.2.3. Use of IP TOS field This document proposes to view Type of Service in a slightly different way than has been usual in the past. While previous RFCs have not been explicit (e.g. RFC 1349), the role of the ToS field has been thought of more to control routing than scheduling and dropping within the router. This document explicitly proposes to specify these features. The TOS field can be used for this purpose, but doing so will preclude its use in the same packet to select the service defined in RFC 1349 and RFC 1700: low delay, high throughput, low cost, high reliability and high security. According to RFC 1349, the TOS field should be viewed as a 4 bit integer value, with certain values reserved for backwards compatibility. We propose that the six defined values of TOS be associated with the statistical service profiles ("expected capacity profiles") defined in this document. That is, the use of the IPI is legal with any of these value of TOS, and the difference among them is routing options. A new value of TOS (yyyy) shall be used to specify the assured service profile, which has a level of assurance for the service profile that is not statistical in nature. As part of the design of this type of service, the routing will have to be controlled to achieve this goal, so the value yyyy for the TOS will also imply some routing constraints for the ISPs. It is an engineering decision of the service provider how this sort of traffic is routed, so that it follows the routes along which the resources have been reserved. 8.2.4. Additional issues for the sender/receiver based scheme The combined sender-receiver scheme is capable of expressing a much more complex set of value relationships than the sender-based scheme. However, it implies more complexity and more bits in the header. It does not appear possible to encode all the necessary information for the combined scheme in an IPv4 header. This option is thus proposed Clark/Wroclawski Expires 12/97 [Page 19]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 as a consideration for IPv6, if there seems to be sufficient demand. 9. Security considerations This scheme is concerned with resource allocation, and thus the major security concern is theft of resources. Resources can be stolen by injecting traffic that is marked as "in" but which has not passed through a legitimate profile meter into a RIO-controlled region of the network. To protect against this, it is necessary to define "regions of shared trust", and engineer and audit all the links that bring traffic into each of these regions to insure that a profile meter has been installed in each such link. Such a region might correspond to a single ISP, the backbone component of a single ISP, a collection of co-operating ISPs and so on. In general, the presence of a profile meter is an indication of a possible boundary where trust is not shared, and the traffic has to be verified. It is a matter for further research whether algorithms can be designed to detect (locally, at each router) a flow of packets that is not legitimate. 10. Acknowledgments The simulations reported in this paper were performed by Wenjia Fang. Earlier simulations that proved the concepts of the profile meter and the receiver-based scheme were performed by Pedro Zayas. We acknowledge the valuable discussions with the members of the End-to- End research group. Appendix A: Description of a receiver-based scheme The tagging scheme described above implements a model in which the sender, by selecting one or another service profile, determines what service will govern each transfer. However, the sender- controlled model is not the only appropriate model for determining how Internet transmissions should be regulated. For much of the traditional Internet, where information has been made available, often for free, to those users who care enough to retrieve it, it is the value that the receiver places on the transfer, not the sender, that would properly dictate the service allocated to the transfer. In this document, we do not debate the philosophical tradeoff between sender and receiver controlled schemes. Instead, we describe a mechanism that implements receiver control of service, which is similar in approach and meshes with the sender controlled tagging scheme. One technique that does not work is to have the receiver send some Clark/Wroclawski Expires 12/97 [Page 20]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 credentials to the sender, on the basis of which a flag is set in the packet. This runs the risks of great complexity, but more fundamentally does not deal with multicast, where one packet may go to several receivers, each of which attaches a different value to the transfer. A critical design decision is whether the scheme must react to congestion instantly, or with one round trip delay. If it must react instantly, then each point of congestion must have stored state, installed by the receiver, that will allow that point to determine if the packet is "in" or "out" of profile. This runs the risk of formidable complexity. If, however, we are willing to have the reaction to congestion occur one round trip later, several quite tractable schemes can be proposed, which are similar to the sender controlled scheme in spirit. A receiver controlled scheme can be built using a traffic meter at the receiver, similar to the traffic meter at the sender in the sender tagging scheme. The meter knows what the current usage profile of the receiver is, and thus can check to see whether a stream of received packets is inside of the profile. A (different) new flag in the packet, called Forward Congestion Notification, or FCN, is used to carry information about congestion to the receiver's traffic meter. A packet under this receiver controlled scheme starts out from the sender with the FCN bit off, and when the packet encounters congestion the bit is set on. As the packet reaches the destination, the receiver's traffic meter notes that the bit is on, and checks to see if the packet fits within the profile of the receiver. If it does, the service profile of the receiver is debited, and the bit is turned off in the packet. If the packet cannot fit within the profile of the user, the bit remains on. When the receiver receives a packet with the FCN on, which means that the receiver's profile does not have sufficient capacity to cover all the packets that encountered congestion, the sender must be instructed to slow down. This can occur in a number of ways. One, for TCP, the receiver could reduce the window size. That is, the receiver as well as the sender could compute a dynamic congestion window. This is complex to design. Second, again for TCP, the ACK packet or a separate control message (such as an ICMP Source Quench) could carry back to the sender some explicit indication to slow down. Third, for TCP, if the traffic meter noted that the receiver seemed to have taken no action in response to the FCN bit, the meter can delete some returning ACKs or an incoming data packet, which will trigger a congestion slowdown in the sender. The paper by Floyd [Floyd95] contains a detailed discussion of enhancing TCP to include explicit congestion notification, using Clark/Wroclawski Expires 12/97 [Page 21]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 either bits in the header or the ICMP Source Quench message with redefined semantics. The range of algorithms explored there for implementing explicit notification are directly applicable to this scheme. In fact, the end node behavior (the source and destination TCP) for her scheme is exactly the same as the scheme here. What is different is the method of notifying the end node of the congestion. In her scheme, random packets are selected to trigger congestion notification. In this scheme, during periods of congestion all packets are marked, but these marks are then removed by the receiver's traffic meter, unless the rate exceeds the installed service profile. We have simulated the receiver-based scheme, using the ECN mechanism proposed by Floyd to notify the sending TCP to slow down. Because of the very well-behaved characteristics of the ECN scheme, we can regulate TCPs to different sending rates essentially flawlessly. A key question in the successful implementation of the receiver scheme is defining what constitutes congestion in the router -- under what conditions the router should start setting the FCN bit. Hypothetically, the router should start setting the bit as soon as it detects the onset of queuing in the router. It is important to detect congestion and limit traffic as soon as possible, because it is very undesirable for the queue to build up to the point where packets must be discarded. Key differences between sender and receiver control There are a number of interesting asymmetries between the sender and the receiver versions of this tag and profile scheme, asymmetries that arise from the fact that the data packets flow from the sender to the receiver. In the sender scheme, the packet first passes through the meter, where it is tagged, and then through any points of congestion, while in the receiver payment scheme the packet first passes through any points of congestion, where it is tagged, and then through the receiver's meter. The receiver scheme, since it only sets the FCN bit if congestion is actually detected, can convey to the end point dynamic information about current congestion levels. The sender scheme, in contrast, must set the IPI and tag the packet as "in" or "out" without knowing if congestion is actually present. Thus, it would be harder, in the sender scheme, to construct a service that billed the user for actual usage during periods of congestion. While the receiver scheme seems preferable in that it can naturally implement both static and dynamic payment schemes, the sender scheme has the advantage that since the packet carries in it the explicit assertion of whether it is in or out of profile, when it reaches a Clark/Wroclawski Expires 12/97 [Page 22]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 point of congestion, the treatment of the packet is evident. In the receiver scheme, the data packet itself carries no indication of whether it is in or out of profile, so all the point of congestion can do is set the FCN bit, attempt to forward the packet, and trust that the sender will correctly adjust its transmission rate. The receiver scheme is thus much more indirect in its ability to respond to congestion. Of course, the controller at the point of congestion may employ a scheme to discard a packet from the queue, as it does now. However, the receiver scheme gives no guidance as to which packet to delete. Another difference between the two schemes is that in the sender scheme, the sending application can set the In Profile Indicator in different packets to control which packets are favored during congestion. In the receiver scheme, all packets sent to the receiver pass through and debit the traffic meter before the receiving host gets to see them. Thus, in order for the receiving host to distinguish those packets that should receive preferred service, it would be necessary for it to install some sort of packet filter in the traffic meter. This seems feasible but potentially complex. However, it is again a local matter between the traffic meter and the attached host. While this scheme works well to control TCP, what about a source that does not adjust when faced with lost packets, or otherwise just floods the congested router? In the receiver-based scheme, there is an increase need for some sort of notification message that can flow backwards through the network from the receiver's traffic meter towards the source of the traffic (or towards the congested routers along the path) so that offending traffic can be distinguished and discriminated against. This sort of mechanism was discussed above in the section on Filtering out Non-Responsive Flows. Appendix B: Designing traffic meters to control TCP throughput We have suggested that a useful goal for a traffic meter is to let a well-behaved TCP operate at a specific speed. This is more complex than a service that mimics a link of a specific speed, since a TCP may not be able to fully utilize a physical link because of its behavior dealing with congestion. In order to design a traffic meter that allows a TCP to go at a set speed, the designer must take into account the behavior of TCP. This appendix presents a quick review of the relevant TCP behavior, describes the preliminary design of a traffic meter that directly controls TCP bandwidth, and summarizes some simulation results. Further details of this work can be found in [CF97]. TCP attempts to adjust its performance by varying its window size. Clark/Wroclawski Expires 12/97 [Page 23]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 Within the limit imposed by the receive window, the sender increases its window size until a packet is discarded; then reduces its window size and begins again. This process controls the TCP1s effective throughput rate. There are several different operating regions for TCP. When a number of packets are lost, a TCP reduces its window size to 1, and then (roughly) doubles it each round trip until a threshold is reached. (This threshold is often referred to by the variable name used to implement it in the Berkeley Unix code: ss-thresh.) Once the send window has exceeded ss-thresh, it increases more slowly -- one packet per round trip. When only one (or a small number) of packets are lost, the window size is reduced less drastically; it is cut in half, and ss-thresh is set to the new current window size. It is this latter behavior that is the desired one in order to achieve a reasonable control over the sending rate of the TCP. When TCP is in this part of its operating range, its window size resembles a saw-tooth, swinging between two values differing by a factor of two. The effect of this saw-tooth window size is to slowly fill up the buffer at the point of congestion until a packet is discarded, then cut the window size by two, which allows the buffer to drain, and may actually cause a period of underutilizing the link. Some thought will suggest that the actual average throughput achieved by the TCP is a function of the buffer size in the router, as well as other parameters. It is difficult to predict. To design a traffic meter that allows a TCP to achieve a given average rate, it is necessary for the meter to recognize the swings, and fit them into the profile. One approach would be to build a meter that looks at the very long-term average rate, and allows the TCP to send so long as that average is less than the target rate. However, this has the severe drawback that if the TCP undersends for some time because it has no data to send, it builds up a credit in the meter that allows it to exceed the average rate for an excessive time. This sort of overrun can interfere with other TCPs. The alternative is to build a meter that measures the rate of the sending TCP, and looks for a peak rate (the high point of the saw- tooth). A simple approach is to build a meter that looks for short term sending rates above 1.33 times the target rate R. Once that rate is detected, the meter starts tagging a few packets as "out". When one of these is discarded, the TCP cuts its window size by a factor of two, which will cause some sort of rate reduction, perhaps also to a factor of two. The TCP will thus swing between 1.33 R and .66 R, which averages out to R. One can build a meter that does this, but it is necessary to consider several factors. Clark/Wroclawski Expires 12/97 [Page 24]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 The relationship between the window size of a TCP and its sending rate is complex. Once the buffer at the point of congestion starts to fill up, increasing the window size does not increase the sending rate. Each packet added to the window adds one packet in circulation, but adds to the round trip delay by the transmission time of one packet because of the increased waiting time in the buffer. The combination of these two effects is to leave the achieved throughput unchanged. If, on the other hand, the buffer is largely empty, then if the window is cut by 2, the rate will be cut by two. It is important that the RIO dropper operate in this region, both so that it has enough empty buffer to handle transient congestion, and to improve its ability to control the TCP throughput. With RIO, the average buffer utilization by "out" packets is small, although the instantaneous buffer size can fluctuate due to traffic bursts. As soon as the TCP exceeds its short-term target rate of 1.33 R, some number of "out" packets begin to appear, and if they generate a queue in the router, a packet is dropped probabilistically, which causes the TCP in question to cut its rate by 2. (Note that in a properly provisioned network, there is enough capacity to carry all the offered "in" packets, and thus "in" packets do not contribute to the RIO buffer load. In a sufficiently underprovisioned network, "in" packet dropping will be triggered, and the TCP congestion control mechanism will limit the packet load as always. Loss of "in" packets indicates to the customer that his provider's provisioning is inadequate to support the customer's profile.) An important issue in the design of this meter is finding the time period over which to average in order to detect the 1.33 R peak. Average over too long a time, and the average takes into account too much of the saw-tooth, and underestimates the peak rate. Average over too short a period, and the meter begins to detect the short- term bursty nature of the traffic, and detects the 1.33 R peak too soon. Since the round trip of different TCPs can differ by at least one order of magnitude and perhaps two, designing a meter (unless it is integrated into the host implementation and knows the round trip) is difficult. However, reasonable parameters can be set which work over a range of round trip delays, say 10 to 100 ms. One objection to this approach, in which the meters looks for a short term peak at 1.33 R, is that a creative user could abuse the design by carefully adjusting the window manually so that it achieved a steady-state rate somewhat above R (the long term target average) but below 1.33R. To detect this, the meter has two rate measurements, one of which looks with a short averaging time for a peak of 1.33 R, and Clark/Wroclawski Expires 12/97 [Page 25]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 a second one, with a substantially longer period (longer than a saw- tooth) for a flow that exceeds R. If the flow falls short of R, no action is taken, because this might simply be a lack of data to send. But if the TCP exceeds the rate R over a long time, the parameters of the short-term averaging meter are adjusted. This meter is a sophisticated objective, because it represents a difficult control problem. First, it attempts to set a rate for a sending TCP, rather then just emulating a physical link. Second, it is operating at a low level of traffic aggregation (we have simulated situations with as few as two flows). Third, the meter operates without knowledge of the round-trips of the individual flows. Integrating the meter into the host, so that it can know the measured RTT (which TCP computes anyway) greatly simplifies the design. However, this non-integrated design is more appropriate for an incremental deployment strategy using unmodified hosts. Avoiding slow-start As noted above, it is desirable to keep TCP operating in the region where, in response to a lost packet, it cuts its window size in half and sets ss-thresh equal to this new window size. However, if several packets are lost at once, the TCP will execute a different algorithm, called "slow-start", in which it goes idle for some period of time and then sets the window size to 1. It is preferable to avoid this behavior. One way to avoid this is to avoid dropping several packets in close proximity. There are two halves to achieving this goal. The first is that the dropper should avoid dropping a block of packets if it has not recently dropped any. That it, it should undergo a gradual transition between the states where it is not dropping any packets, and where it starts to drop. RED, and by extension RIO, has this behavior. Up to some average queue length, RED drops no packets. As the average packet length starts to exceed this length, the probability of loss starts to build, but it is a linear function of how much longer the average is than this minimum. So at first, the rate of drops is very low. However, if the dropper is overloaded with "out" packets, it will be forced to drop every one that arrives. To deal with this situation, the meter, when it starts tagging packets as "out", also should at first tag the packets infrequently. It should not suddenly enter a mode where it tags a block of packets as "out". However, if the TCP continues to speed up, as it will if the path is uncongested and it can sustain the speed, more and more of the packets will be marked as out, so a gradual transition to tagging in the meter is not Clark/Wroclawski Expires 12/97 [Page 26]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 sufficient to avoid all cases of clumped dropping. Both halves of the scheme, the meter and the dropper, must enter the control phase gradually. In essence, this strategy introduces low-pass filters into both the traffic metering and congestion detection data. These filters are needed to address the two separate cases of the system dropping out packets because the TCP exceeding its profile in an otherwise loaded network, and the system dropping out packets because of new congestion in a network with TCP1s previously operating above profile Brief simulation results We have performed some simulations of this traffic meter and the RIO dropper. In this note we show one test case from our simulations. The first column is the target rate, the second column is the actual rate, the third column is the round trip delay. Target rate Actual rate TCP RTT .1 mb/s .158 mb/s 20 ms. 1 1.032 20 .1 .193 40 1 1.02 40 .1 .165 60 1 1.01 60 .1 .15 80 1 .95 80 .1 .15 100 1 .93 100 In this simulation, the actual link capacity was exactly the sum of the target rates, so there was no "headroom" for overshoot. As the numbers indicate, we can control the rates of the large flows to within 10% over a range of round trips from 20 to 100 ms, with the longer delay flows having the greater difficulty achieving full speed. The smaller flows, for a number of reasons, are more opportunistic in using any unclaimed capacity, and exceed their target ranges. By adjusting the RIO parameters and the parameters in the meter, different detailed behavior can be produced. We are using this research to fine tune our best understanding of the RIO parameters, as well as the design of advanced meters. New TCP designs help greatly Improvements to the dynamic performance of TCP have been proposed for reasons unrelated to this scheme, but rather to more general goals for improved operation. These include SACK TCP, which supports selective acknowledgment when specific packets are lost, and other Clark/Wroclawski Expires 12/97 [Page 27]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 TCP tuning changes that deal better with multiple losses. We have simulated our taggers and droppers with these newer TCPs, and the effect is to make the approach work much better. The reason for this is that much of the care in the detailed design is required to avoid triggering slow-start rather than fast recovery, and thus reduce our ability to control the TCP's throughput. The newer TCP designs, which achieve that same goal generally, make our design much more robust. Another way to improve the operation of this scheme is to use an Explicit Congestion Notification scheme, as has been proposed by Sally Floyd. In this variation of RIO, RIO-ECN, the algorithm does not drop "out" packets at first, but just sends an ECN indication to the destination, where it is returned to the source. The design of Floyd's ECN takes into account the round-trip time, and avoids inadvertent triggering of a slow-start. RIO-ECN, together with a suitable profile meter at the destination, allows us to control TCP sending rates almost without flaw in our simulations. Appendix C: Economic issues This is a technical note. However, any discussion of providing different levels of service to different users of a commercial network cannot be complete without acknowledging the presence of economic issues. The scheme presented here has been conceived in the context of the public commercial Internet, where services are offered for money. It also works in the context of private, corporate or military networks, where other more administrative allocations of high-quality service may be used. But it must work in the context of commercial service. It is therefore crucial that it take into consideration the varying business models of Internet service customers and providers, and that it be consistent with some relevant economic principles. We discuss these matters briefly below. Note that we are not suggesting that any specific business model, pricing strategy, or service offering be universally adopted. In fact, we believe that a strength of this framework is that it cleanly separates technical mechanism from economic decisions at different points within the network. Congestion pricing The first economic principle is that there is only a marginal cost to carrying a packet when the network is congested. When the network is congested, the cost of carrying a packet from user A is the increased delay seen by user B. The traffic of user B, of course, caused delay Clark/Wroclawski Expires 12/97 [Page 28]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 for A. But if A somehow were given higher priority, so that B saw most of the delay, A would be receiving better service, and B paying a higher price, in terms of increased delay and (presumably) dissatisfaction. According to economic principles, A should receive better service only if he is willing to pay enough to exceed the "cost" to B of his increased delay. This can be achieved in the marketplace by suitable setting of prices. In principle, on can determine the pricing for access dynamically by allowing A and B to bid for service, although this has many practical problems. For an example of such a proposal, see [MMV95]. When the network is underloaded, however, the packets from A and from B do not interfere with each other. The marginal or incremental cost to the service provider of carrying the packets is zero. In a circumstance where prices follow intrinsic costs, the usage-based component of the charge to the user should be zero. This approach is called "congestion pricing". The scheme described here is consistent with the framework of congestion pricing. What the user subscribes to, in this scheme, is an expectation of what service he will receive during times of congestion, when the congestion price is non-zero. When the net is underloaded, this scheme permits the user to go faster, since both "in" and "out" packets are forwarded without discrimination in that case. Pricing need not (and often does not) follow abstract economic principles. An ISP might choose to prevent users from going faster in times of light load, to assess some price for doing so, or whatever. But the scheme is capable of implementing a price/service structure that matches an economically rational model, and we would argue that any scheme should have that characteristic. This line of reasoning has some practical implications for the design of service profiles. If a provider sells a profile that meters usage over some very long period (so many "in" packets per month, for example) then there will be a powerful incentive for the user not to expend these packets unless congestion is actually encountered. This consequence imposes an extra burden on the user (it is not trivial to detect congestion) and will yield no benefit to either the user or the provider. If there is no cost to sending traffic when the network is underloaded, then there is no cost to having some of those packets carry "in" tags. In fact, there is a secondary benefit, in that it allows providers to track demand for such traffic during all periods, not just during overload. But profiles could be defined that would motivate the user to conserve "in" tags for times of congestion, and these seem misguided. Clark/Wroclawski Expires 12/97 [Page 29]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 Getting incentives right The second economic principle is that pricing can be used as an incentive to shape user behavior toward goals that benefit the overall system, as well as the user. The "incentive compatibility" problem is to structure the service and pricing in such a way that beneficial aggregate behavior results. Service profiles represent an obvious example of these issues. If a profile can be shaped that closely matches the user's intrinsic need, then he will purchase that profile and use it for those needs. But if the only profile he can get provides him unused capacity, he will be tempted to consume that capacity in some constructive way, since he has been required to purchase it to get what he wants. He may be tempted to resell this capacity, or use it to carry lower value traffic, and so on. These uses represent distortions of the system. In general, resale of capacity, or arbitrage, results when pricing is distorted, and does not follow cost. It is difficult to design a technical mechanism that can prevent arbitrage, because the mechanism does not control pricing, but the mechanism should not of necessity create situations where arbitrage is a consequence. Generally speaking, this means that price should follow cost, and that profiles should be flexible enough to match the intrinsic needs of a range of users. This scheme attempts to capture this objective by allowing the traffic meters to implement a range of service profiles, rather than standardizing on a fixed set. Inter-provider payments One of the places where a traffic meter can be installed is at the boundary between two ISPs. In this circumstance, the purpose is to meter how much traffic of value, i.e. "in" packets, are flowing in each direction. This sort of information can provide the basis for differential compensation between the two providers. In a pure sender-based scheme, where the revenues are being collected from the sender, the sender of a packet marked as "in" should presumably pay the first ISP, who should in turn pay the second ISP, and so on until the packet reaches its final destination. In the middle of the network, the ISPs would presumably negotiate some long term contract to carry the "in" packets of each other, but if asymmetric flows result, or there is a higher cost to carry the packets onward in one or the other direction, this could constitute a valid basis for differential payment. As is discussed in [Clark97], the most general model requires both sender and receiver based payments, so that payments can be extracted Clark/Wroclawski Expires 12/97 [Page 30]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 from all participants in a transfer in proportion to the value that each brings to the transfer. In this case, the direction of packet flow does not determine the direction of value, and thus the direction of compensating payment. See the referenced paper for a full development of the details of a mixed sender-receiver scheme. It is interesting to note that the sender and receiver-based schemes are to some extent associated with different business models. The basic sender-based scheme considered in much of this note makes sense in many business contexts. For example, a user with multiple sites, who wants to connect those sites with known service, can equally well express all of these requirements in terms of behavior at the sender, since the senders are all known in advance. In contrast to this "closed" system, consider the "open" system of a node attached to the public Internet, who wants to purchase some known service profile for interaction with other sites on the Internet. If the primary traffic to that site is incoming (for example, browsing the Web), then it is the receiver of the traffic, not the sender, who associates the value with the transfer. In this case the receiver-based scheme, or a zone scheme, may best meet the needs of the concerned parties. References [Clark97] D. Clark, "Combining Sender anbd Receiver Payment Schemes in the Internet"; Proceedings of the Telecommunications Policy Research Conference, Solomon, MD, 1996 [CF97] D. Clark and W. Fang, "Explicit Allocation of Best Effort Packet Delivery Service", (soon) to be available as http://ana.lcs.mit.edu/papers/exp-alloc.ps [Floyd93] S. Floyd and V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance", IEEE/ACM Trans. on Networking, August 1993 [Floyd95] S. Floyd, "TCP and Explicit Congestion Notification", Computer Communication Review, v 24:5, October, 1995 [FF97] S. Floyd and K. Fall, "Router Mechanisms to Support End-to-End Congestion Control", available at http://www-nrg.ee.lbl.gov/nrg- papers.html [Kalevi97] K. Kilkki, "Simple Integrated Media Access" Internet Draft, June 1997, <draft-kalevi-simple-media-acccess-01.txt> [Kelly97] F. Kelly, "Charging and Accounting for Bursty Connections" in "Internet Economics", L. McKnight and J. Bailey, eds., MIT Press, Clark/Wroclawski Expires 12/97 [Page 31]
INTERNET-DRAFT draft-clark-diff-svc-alloc-00.txt July, 1997 1997 [MMV95] "Pricing the Internet" in "Public Access to the Internet", B. Kahin and J. Keller, eds., Prentice Hall, 1995. Available as http://www.spp.umich.edu/ipps/papers/info- nets/Pricing_Internet/Pricing_the_Internet.ps.Z Authors' Addresses: David D. Clark MIT Laboratory for Computer Science 545 Technology Sq. Cambridge, MA 02139 jtw@lcs.mit.edu 617-253-6003 617-253-2673 (FAX) John Wroclawski MIT Laboratory for Computer Science 545 Technology Sq. Cambridge, MA 02139 jtw@lcs.mit.edu 617-253-7885 617-253-2673 (FAX) Clark/Wroclawski Expires 12/97 [Page 32]