Internet Draft INTERNET-DRAFT Werner Almesberger Tiziana Ferrari Jean-Yves Le Boudec ICA, EPFL-DI, Switzerland November 1997 Scalable Resource Reservation for the Internet <draft-almesberger-srp-00.txt> 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 view the entire list of current Internet-Drafts, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). 1. Abstract Current resource reservation architectures for multimedia networks don't scale well for a large number of flows. We propose a new architecture that aggregates flows on each link in the network. Therefore, the network has no knowledge of individual flows, and resource management functions traditionally implemented in the network (such as flow acceptance control) are delegated to hosts. 2. Introduction Many resource reservation architectures and protocols that have been proposed for integrated service networks borrow heavily from the architecture of the telephony network: - routers or switches between the communicating hosts are required to store per-flow state information - reservations, once granted, are stringent and conformance of traffic is carefully controlled (policing) - most of the difficult work (e.g. admission control) is entirely Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 1] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 handled by the network The general intention is to provide a network service that is as deterministic as possible. While a highly deterministic service is certainly attractive, the complexity and lack of scalability of the aforementioned architectures and protocols makes their usefulness for many applications questionable. Particularly Internet telephony creates a need for very inexpensive means to obtain a dependable quality of service for a very large number of concurrent flows. This goal can be achieved by aggregating flows so that the reservation mechanism only needs to be aware of a comparably small number of (aggregated) flows. The architecture we propose in this paper goes even beyond concepts for aggregation on top of traditional reservation architectures (e.g. [1] for ATM) in that it makes aggregation the standard behaviour of the network and not a special case requiring additional protocol activity. It differs from approaches ensuring relative fairness (e.g. [2] and [3]) in that admission control is an integral part of it. In short, our reservation model works as follows. A source that wishes to make a reservation (for example for Internet telephony) starts by sending data packets marked with a REQUEST flag to the destination. These packets are forwarded normally by routers, who also take a flow admission decision on each of them. After enough REQUEST packets have been sent, the source learns from the destination its estimate of how much of the reservation has been accepted in the network. The source may then send data packets marked with a RESERVED flag at the accepted rate. Routers that have admitted, and thus forwarded, REQUEST packets have committed to have enough resources to accept subsequent RESERVED packets sent by the source at the accepted rate. The accepted rate is computed independently by sources and routers, using a "learn by example" procedure. The accepted rate is guaranteed as long as there is a minimum activity by the source. The reservation disappears by timeout after the source has stayed idle for a while. Figure 1 shows an idealized view of our model, and a more detailed example is given in section "Reservation example". The initial data packets sent by the source can be thought of as "sticky": once a router has accepted some of them at a given rate, it must continue to accept packets at the same rate until the source becomes idle. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 2] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 Reservation (Bandwidth) ^ | |Rsv Rsv use and Rsv |setup refresh timeout |<--->|<------------>|<-->| | / = REQUEST | _______________..... | / | __ = RESERVED | / | | / | .. = No traffic | / | |/ | +-----------------------------> Time Figure 1: Idealized reservation procedure. A key feature of our proposal is that routers do not keep state information per flow; routers only remember their reservation commitments globally per output port. This is made possible by two features: - routers rely on end-systems not to exceed their accepted rates; - routers maintain reservations by learning, namely, by monitoring the actual reserved traffic. We discuss these two design directions in the rest of this section. Section "Architecture overview" describes the fundamental architecture. Section "Additional aspects" elaborates on that and also points out areas where more research is needed. The paper concludes with section "Conclusion". 2.1 The TCP case For best-effort traffic, the Internet has illustrated that network internals can be simple: besides routing, which has grown significant complexity, there are no "intelligent" services inside the network. Responsibility for congestion control is given entirely to the end systems (e.g. TCP), which are in turn expected to have some degree of complexity of their own. Also, instead of providing stringent isolation among users, the Internet relies on guided cooperation. Applying this approach to resource reservation means to let end systems perform flow acceptance control and to trust them not to exceed the agreed upon reservations. In order to protect the network from errors in application programs, the reservation protocol handling needs to be implemented in the networking kernel of the operating system. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 3] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 If needed, policing functions can be implemented per flow at some network access points; we believe that such policing is not needed at inter-carrier exchanges, or in general anywhere beyond Internet access points. Because flow acceptance control is inherently flow-specific, delegating it to end systems is a requirement for enabling routers to efficiently aggregate arbitrary flows. The proposed architecture slightly extends the traditional Internet design by introducing the concept of packet types to distinguish reserved traffic from best-effort traffic. This also allows routers to give more precise admission control indications than just a simple forward-or-discard decision. 2.2 Adaptive applications The desire to run multimedia applications over the current best-effort Internet with all its imperfections has motivated the development of increasingly sophisticated adaptive applications [4,5]. Adaptive applications tolerate variations in packet loss rates, in bandwidth, and in delay. Of course, even adaptive applications have certain minimum requirements. This is typically a minimum bandwidth, below which no useful operation is possible. If additional bandwidth is available, it is used to improve the service (e.g. better audio quality). The proposed architecture aims mainly to ensure that adaptive applications can obtain their minimum bandwidth. The service goals are similar to the ones of the INTSERV controlled-load service [6]: Availability of enough bandwidth is guaranteed but all other parameters (such as delay, loss rate, etc.) remain unspecified, although an application can assume that they are in a "reasonable" range. The presence of adaptive applications also implies that there is usually enough best-effort traffic in the network that only a small fraction of the total bandwidth will be used for reserved traffic and that resource shortage for reserved traffic will be an infrequent situation. 2.3 Learning by example New reservations are set up by sending data packets with a REQUEST flag. When a router accepts such requests, it predicts the arrival of future packets and changes its reservation state accordingly. Because the reservation information is sent directly with the Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 4] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 data, the reservation and the actual traffic are automatically synchronized. Central to our proposal is the concept of an estimation module used by sources, routers, and destinations. Assuming that sources emit traffic in regular periodic patterns, a simple implementation could just count the number of requests during a time interval and use that to predict the increase of total reserved bandwidth. Note that the period of a source must be reasonably short compared to the observation interval for such measurements to be meaningful. The same principle is also used to detect decreases in the use of reserved bandwidth: Routers monitor the amount of reserved traffic and adjust reservations automatically if sources reduce their bandwidth or stop sending.* We describe this simple implementation in sections "Reservation dynamics" and "Reservation example". * A discussion of measurement-based admission control for similar purposes can be found in [7]. 3. Architecture overview The proposed architecture uses two protocols to manage reservations: a reservation protocol to establish and maintain them, and a feedback protocol to inform the sender about the reservation status. Data and reservations | +--------+ +--------+ | +--------+ +--------+ | | | | | | | | | | |----->| Router |---...-->| Router |----->| | | Sender | | | | | |Receiver| | | +--------+ +--------+ | | | |<------------------...-------------------| | +--------+ | +--------+ | Feedback Figure 2: Network structure overview. Figure 2 illustrates the operation of the two protocols: - Data packets with reservation information are sent from the sender to the receiver. The reservation information is processed by routers. They may modify the reservation information or they may also discard packets. - The receiver sends feedback information back to the sender. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 5] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 Routers only forward this information; they don't need to process it. Routers monitor the effectively present reserved traffic and adjust their reservations accordingly. 3.1 Reservation protocol The reservation protocol is used in the direction from the sender to the receiver. It is processed by the sender, the receiver, and the routers between them. In order to simplify processing of the reservation protocol, the reservation information is represented as a packet type which is included in normal data packets.* * The encoding is yet unspecified. One possible approach is to define a new IP option to carry the packet type. The reservation protocol uses three packet types: RESERVED The reservation has already been established (and confirmed). The packet of type RESERVED uses that reservation. REQUEST A reservation is needed for packets like the current one, but a reservation has not yet been confirmed (e.g. because no request was sent yet or because the feedback hasn't reached the sender yet). BEST EFFORT No reservation is needed. Packet types are initially assigned by the sender, as shown in figure 3. A traffic source (i.e. the application) specifies for each packet if that packet needs a reservation. If no reservation is necessary, the packet is simply sent as BEST-EFFORT. If a reservation is needed, the protocol entity checks if an already established reservation covers the current packet. If yes, the packet is sent as RESERVED. Otherwise, an additional reservation is requested by sending the packet with the REQUEST flag. Application | Protocol stack | | | +-------------+ Yes Needs reservation -------->| Reservation |--------> RESERVED | |established ?|--------> REQUEST | +-------------+ No Doesn't need | reservation --------------------------------------> BEST-EFFORT | Figure 3: Initial packet type assignment by sender. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 6] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 Each router performs the following processing (see also figure 4): - If a REQUEST can be accepted, the reservation is made and the packet is forwarded unchanged. Otherwise, its type is set to BEST-EFFORT and best-effort processing is performed. - If a RESERVED packet is received, the router verifies that a suitable reservation exists. This is normally the case and the packet is forwarded unchanged and with priority over best-effort traffic. If no reservation exists, either a protocol error or a route change has occurred (see section "Route changes"). In order to stabilize the reservation, the packet type is changed to REQUEST and request processing is performed.* Furthermore, BEST-EFFORT packets may be discarded during congestion. * Considering that RESERVED packets will "magically" become requests if necessary, one may be tempted at this point to avoid the use of a REQUEST packet type entirely. At least in the given framework, this does not work. Requests are needed to isolate already established reservations from increases or new reservations: if packets from "old" and "new" reservations were both of type RESERVED, a router experiencing resource shortage had no way of knowing which ones to degrade or even to discard and it would consequently also penalize the "old" reservations. +-------------+ Yes RESERVED ---------->| Reservation |---------> RESERVED |established ?| +-------------+ | No v +-------------+ Yes REQUEST ----------->| Reservation |---------> REQUEST | possible ? | +-------------+ | No v +-------------+ Yes BEST-EFFORT ------->| Resources |---------> BEST-EFFORT | available ? | +-------------+ | No X Figure 4: Packet type processing by routers. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 7] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 Note that the reservation protocol may "tunnel" through routers that don't implement reservations. This allows the use of unmodified equipment in parts of the network which are dimensioned such that congestion is not a problem. The receiver does no packet-type specific processing. Instead, it counts incoming packets and sends feedback to the sources. 3.2 Feedback protocol The feedback protocol is used to convey information on the success of reservations and on the network status from the receiver to the sender. Unlike the reservation protocol, the feedback protocol does not need to be interpreted by routers, because they can determine the reservation status from the sender's choice of packet types. Feedback information is collected by the receiver and it is periodically sent to the sender. The feedback consists of the receiver's estimate of the current reservation. The receiver computes this estimate by executing an algorithm like the one routers use to estimate the actual resource use. Additional information can be included in feedback messages to improve stability and to provide additional information on network performance, e.g. the loss rate along the path or the round-trip time. The reservation estimated by the receiver is an upper bound for the rate at which the sender may send requests and is used by the function that decides if packets are sent as RESERVED or as REQUEST. Receivers collect feedback information independently for each sender and senders maintain the reservation state independently for each receiver. Note that, if more than one flow to the same destination exists, attribution of reservations is a local decision at the source. The feedback mechanism can be implemented on top of a protocol like RTCP [8]. 3.3 Reservation dynamics Reservations are set up for the traffic profile reflected by the requests sent by the source. A router can for instance count the number of requests it receives (and accepts) during a certain observation interval and use this as an estimate for the bandwidth that will be used in future intervals of the same duration. In addition to requests for new reservations, the use of existing Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 8] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 reservations needs to be measured too. This way, reservations of sources that stop sending or that decrease their sending rate can automatically be removed. The use of reservations can be simply measured by counting the number of RESERVED packets that are received in a certain interval. With such measurements for time t, the amount of resources to reserve at time t+1 can be predicted as follows: reserve(t+1) = requests(t)+rsv_seen(t) with requests(t) being the sum of the resources requested and rsv_seen(t) being the resources used by reserved traffic, both measured during the observation interval starting at time t. To compensate for deviations caused by delay variations, spurious packet loss (e.g. in a best-effort part of the network), etc., reservations can be "held" for more than one observation interval. This can be accomplished by remembering the observed traffic over several intervals and using the maximum of these values. With a hold time of h observation intervals, the reservation is computed as follows: reserve(t+1) = max(requests(t-h+1)+ rsv_seen(t-h+1),..., requests_t+rsv_seen_t) The definition and evaluation of the algorithms for reservation calculation in hosts and routers is still ongoing work. The formulas above should serve only as examples. [ Figure 5: Algorithms in the senders, routers, and receivers. ] We call this algorithm an estimator, since it attempts to estimate, based on past traffic, the resources that will need to be reserved in the future. Figure 5 shows how the estimator algorithm is used in all network elements: - Senders use the estimator for an optimistic prediction of the reservation the network will perform for the traffic they emit. This, in conjunction with feedback received from the receiver, is used to decide whether to send REQUEST or RESERVED packets. - Routers use the estimator for packet-wise admission control and also to detect anomalies (see section "Route changes"). - In receivers, the estimator is fed with the received traffic and it generates a (conservative) estimate of the reservation at the last router. This is sent as feedback to the source. A source always uses the minimum of the (optimistic) estimation of the reservation at the next router and the (conservative) feedback. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 9] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 As described in section "Reservation protocol", a sender keeps on sending requests until successful reservation setup is indicated with a feedback packet. This means that the sender sends more requests than needed if the round-trip-time is greater than the observation interval. Routers can detect this by the lack of RESERVED packets and they consequently refrain from increasing the reservation. The feedback that is returned to the sender may also show an increased number of requests.* The sender must not interpret those requests as a direct increase of the reservation, because the routers didn't either. Instead, the sender uses the same algorithm as the routers to correct the feedback information accordingly. * Some of them can, however, also be refused in the network and either become best-effort or even get discarded. 3.4 Resource reservation in a router This section gives an example of how resource reservation can be handled in a simple router where only output buffer space is controlled. Depending on its architecture, a real router may have to take the status and utilization of many other components into account. Figure 6 illustrates the packet processing in the example router: After passing the router fabric, the reservation information in each packet is examined and acted upon (see section "Reservation protocol"). Packets of type REQUEST or RESERVED are put into the queue for reserved traffic. All other packets are put into the best-effort queue or they are discarded. The queues are emptied by a scheduler which gives priority to the reserved traffic queue. [ Figure 6: Example router. ] Placing the reservation mechanisms directly before the output queues naturally leads to aggregation: since the critical resource at this point is queue space, one can for instance express reservations as allocations of such space within a given interval. The sum of the allocations then corresponds to the aggregate bandwidth, which is reserved on that port. [ Figure 7: Reservation control in router. ] Detection of malfunction can be improved without impacting scalability by calculating reservations not only for each output port, but for each input and output port pair (which is called an "intersection" in figure 7). 3.5 Reservation example Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 10] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 In this section, we illustrate the operation of the reservation mechanism in a very simple example. The network we use is shown in figure 8: the sender sends over a delay-less link to the router, which performs the reservation and forwards the traffic over a link with a delay of two time units to the receiver. The receiver periodically returns feedback to the sender. [ Figure 8: Example network configuration. ] The bandwidth reservation in the router and the reservation that has been acknowledged in a feedback message from the receiver are measured. In figure 9, they are shown with a thin continuous line and a thick dashed line, respectively. The packets emitted by the source are indicated by arrows on the reservation line. A full arrow head corresponds to REQUEST packets, an empty arrow head corresponds to RESERVED packets. For simplicity, the sender and the router use exactly the same observation interval in this example, and the feedback rate is constant. [ Figure 9: Protocol operation example. ] The source sends one packet per time unit. First, the source can only send requests and the router reserves some resources for each of them. At point (1), the router discovers that it has established a reservation for six packets in four time units, but that the source has only sent four packets. Therefore, it corrects its estimate and proceeds. The first feedback message reaches the sender at point (2). It indicates a reservation level of five packets in four time units (i.e. the estimate at the receiver at the time when the feedback was sent), so the sender can now send RESERVED packets instead of REQUESTs. At point (3), the next observation interval ends at the router and the estimate is corrected once more. Finally, the second feedback arrives at point (4), indicating the final rate of four packets in four time units. The reservation does no change after that. 4. Additional aspects This section describes further details of the proposed reservation architecture and discusses areas requiring further research. 4.1 Starvation Reservation establishment is incremental. It is therefore possible for a sender to obtain only a fraction of the required resources if a shortage occurs before all the requests have been accepted. This can lead to starvation if several senders (unsuccessfully) compete for same resource for an extended period of time. A sender can react to this situation in the following ways: Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 11] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 - give up and report reservation failure to the application - try to proceed with the partial reservation (e.g. if the shortage occurred during an attempt to increase an older reservation) - back off and try again later In the latter case, the sender has to wait for the hold time plus a random delay before sending new requests. The random delay should be exponentially increased on repeated reservation failures to the same destination. 4.2 Generation of inelastic best-effort traffic Degrading REQUEST packets to BEST-EFFORT during resource shortage is desirable, because it allows the communicating hosts to easily distinguish a mere reservation failure from a total communication breakdown. Unfortunately, blindly converting all REQUEST packets to BEST-EFFORT may have disastrous effects on other best-effort traffic: since a sender emits requests at the full rate of the desired reservation, the resulting inelastic best-effort traffic would be grossly unfair with respect to protocols like TCP, which perform end-to-end congestion control (see also [9]). If the network implements a packet type for inelastic best-effort traffic* or generally a lower priority type than normal best-effort traffic, that type should be used when degrading REQUEST packets. Otherwise, a more aggressive discard policy has to be used for those packets. This could for instance be modulated by measuring congestion-controlled traffic (e.g. TCP) flowing to the same destination. * Such a type would for instance have service characteristics like a low delay but a higher loss probability. 4.3 Route changes Like most other reservation architectures, the proposed one may fail to provide the promised service if there is a route change. Architectural means to reduce the number of route changes to the absolutely necessary minimum (e.g. "route pinning" [10]) are outside the scope of this paper. Once a route change occurs, e.g. due to a link failure, it typically has the following effects: The traffic is redirected to a path on which no prior reservation exists ( b, c). In order to limit the impact of this, the first router that detects the change should change RESERVED packets to REQUEST. In figure 10, routers A and B can orderly try to establish reservations on links a and Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 12] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 b (and on all downstream links) if router A changes the type of redirected packets. Note that A cannot distinguish older reserved traffic sharing the path via a and b from redirected traffic and that it may therefore degrade RESERVED packets of the former to requests. [ Figure 10: Route change example. ] A further anomaly can occur, if the original path and the redirected path merge again further downstream ( d): The original reservation and the new requests that were generated to repair the reservation can collide and yield an artificially high reservation. This is similar to the time-to-feedback problem discussed in section "Reservation dynamics" and the same mechanisms can be used to overcome it. 4.4 Discussion of the estimation module We have presented in section "Reservation dynamics" an estimation module based on counting the number of bytes in request and reservation packets per time interval. We discuss now some implications of this estimation module. The estimated bandwidth required for one output for the tth time interval is reserve(t). Call T the length of the time interval. If the estimation is correct, this means that an arrival curve for the aggregate flow is a(u) = (T + u ) reserve(t). If the aggregate flow is served at a line rate c, this implies that the maximum delay variation for this flow is T/(reserve(t)*c) [11]. With this estimation module, the value of T is thus linked to the delay imposed on reserved traffic. This is undesirable, because we may want to choose a large value for T in order to smooth out jitter, without increasing the delay. It is possible to modify the estimation module as follows in order to remove this dependency. In section "Reservation dynamics", define requests(t) as the phdeterministic effective bandwidth for a delay bound D [11] of the flow of requests over the tth time interval, and rsv_seen(t) the deterministic effective bandwidth for the same delay bound D of the flow of reservations. The deterministic effective bandwidth is the amount of bandwidth that is required to serve an observed flow within a given delay bound. This modification makes the estimation module more complex, but it makes it possible to have an observation interval T much larger than the delay bound D. A more detailed analysis of the estimation module is the object of current research. 4.5 Multicast The reservation mechanism described can be slightly extended to a multicast scenario. The extensions concern the feedback and the Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 13] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 reservation protocol at the source. They are needed to cope with several problems which are typical in a multicast environment: - the joining mechanism: how to establish reservations to a new group member without affecting the reservation already in place; - transparency: events like route instability, topology changes, joining and leaving of some group members and situations like heterogeneous connectivity should only affect their limited scope. They should be completely transparent to the remaining session members and also to the connections established by other applications. - feedback implosion: the feedback protocol which works well in a unicast scenario does not scale well in a multicast environment. Establishing reservations in a multicast tree The mechanism described here to build up reservations in a multicast context fits for multicast routing algorithms in which sources do not flood traffic periodically to the network. In this way reservations (REQUEST and RESERVED packets) can be restricted to the links belonging to the multicast tree. The source starts sending request messages to the multicast routers which explicitly joined the group as a reply to the source register message. Members of a session are divided into two sets: 1. joining members, forming the REQUEST multicast group; 2. "old" members, forming the RESERVED multicast group. This distinction is necessary in order to make the joining operation transparent to the hosts and to the branches already belonging to the session.* The purpose of this division is to forward REQUEST packets only on the path from the nearest multicast router belonging to the reserved group to the new member, as shown in figure 11. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 14] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 * New members cannot join directly the reserved group because this would have the effect of injecting RESERVED packets into links on which the corresponding amount of resources was not allocated before. Since routers have no means to distinguish "legal" from "illegal" packets, non-conforming data would affect other reservations already in place. Vice versa, the sending of REQUEST packets would have the effect of increasing the reservation level on the trunks already belonging to the reserved tree. [Source] [...] and // = on RESERVED tree // \\ <...> and / = on REQUEST tree // \\ [Router] [Router] // \ \ // \ \ [Member]/ \ / \ Figure 11: Request and reserved multicast group. The join request is issued hop-by-hop toward a multicast router already on the reserved tree. Routers already receiving reserved traffic start sending the multicast traffic to the member after receiving the join request. In addition to that, they also switch the RESERVED flag to REQUEST. Members of the request group can compare their reservation estimate to the target amount indicated by the source. If the reservation offered is acceptable, then the member can leave the request group and join the reserved group.* * This mechanism requires that the interval between the leaving and the joining is small compared to the life time of the reservation just established. This mechanism can be implemented by associating two multicast addresses to the two distinct groups. The addresses can be different only in the least significant bit - for example it can be 0 for the request group and 1 for the reserved group. Then, the algorithm executed by the multicast router when a multicast packet is received, is the following: if ((pck_addr is multicast) and (pck_type == rsvd)) { forward pck to reserved group; if (router is in the request group) { newpck = copy(pck); newpck_type = req; Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 15] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 forward newpck to request group; } } Transparency In a network with bottlenecks the algorithm should avoid that the link with worst connectivity (e.g. with the lowest bandwidth availability) limits the reservation offered to each member of the group. To cope with this heterogeneity multicast members could be grouped into separate sets and layered coding [12] could be used. Hosts which can apply for the same reservation level, are associated to different multicast groups. All the receivers are included in a common multicast tree for the distribution of the fundamental coding layer, then other coding layers can be added to it. The traffic distribution of each layer can be implemented through the reserved and request group described above and each member can join several groups at the same time depending on the quality of its connectivity. Feedback The problem of feedback implosion is solved by simply not sending any explicit feedback but by using group membership as an implicit indicator instead. The multicast source can fix an a priori value for the minimum amount of reservations required to forward the traffic of a given coding layer. After joining the request group the receiver does flow acceptance control. If the estimated reservation is acceptable compared to the target set by the source, then it can leave the REQUEST group and join the RESERVED, otherwise it leaves the REQUEST group and gives up. So, the absence of a reserved group of a session can mean two things: no members have joined the request group yet or no members can accept the reservation offered. Since the source does not receive any feedback, it can statically fix the reservation threshold of each multicast group. If that amount of resources can not be allocated, hosts will leave both groups, the multicast trees disappear and the (partial) reservations time out. 5. Conclusion We have proposed a new scalable resource reservation architecture for the Internet. Our architecture achieves scalability for a large number of concurrent flows by aggregating flows at each link. This aggregation is made possible by entrusting traffic control decisions to end systems - an idea borrowed from TCP. Reservations are controlled with estimation algorithms, which predict future resource usage based on previously observed traffic. Furthermore, protocol processing is simplified by attaching the reservation control Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 16] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 information directly to data packets. We did not present a conclusive specification but rather described the general concepts, and gave examples for basic implementations of core elements of the architecture. Further research is needed to resolve open issues needed for a comprehensive specification and to improve efficiency, robustness, and versatility of the algorithms and procedures outlined in this paper. 6. References [1] Gauthier, Eric; Giordano, Silvia; Le Boudec, Jean-Yves. Reduce Connection Awareness, http://lrcwww.epfl.ch/scone/scone_paper2.ps, Technical Report 95/145, DI-EPFL, September 1995. [2] Floyd, Sally; Jacobson, Van. Link-sharing and Resource Management Models for Packet Networks, IEEE/ACM Transactions on Networking, Vol. 3 No. 4, pp. 365-386, August 1995. [3] Liebeherr, Joerg; Akyildiz, Ian F.; Sarkar, Debapriya. Bandwidth Regulation of Real-Time Traffic Classes in Internetworks, Computer Networks and ISDN Systems, Vol. 28, No. 6, April 1996, pp. 855 - 872. [4] Diot, Christophe; Huitema, Christian; Turletti, Thierry. Multimedia Applications should be Adaptive, ftp://www.inria.fr/rodeo/diot/nca-hpcs.ps.gz, HPCS'95 Workshop, August 1995. [5] Bolot, Jean; Turletti, Thierry. Adaptive Error Control For Packet Video in the Internet, Proceedings of IEEE ICIP '96, pp. 232-239, September 1996. [6] Wroclawski, John. Specification of the Controlled-Load Network Element Service (work in progress), Internet Draft draft-ietf-intserv-ctrl-load-svc-05.txt, May 1997. [7] Floyd, Sally. Comments on Measurement-based Admissions Control for Controlled-Load Services, ftp://ftp.ee.lbl.gov/papers/admit.ps.Z, July 1996. [8] RFC1889: Schulzrinne, Henning; Casner, Stephen L.; Frederick, Ron; Jacobson, Van. RTP: A Transport Protocol for Real-Time Applications, IETF, January 1996. [9] Floyd, Sally; Fall, Kevin. Router Mechanisms to Support End-to-End Congestion Control, ftp://ftp.ee.lbl.gov/papers/collapse.ps, Technical report, LBL, February 1997. [10] RFC1633; Braden, Bob; Clark, David; Shenker, Scott. Integrated Services in the Internet Architecture: an Overview., IETF, June 1994. [11] Le Boudec, Jean-Yves. Network calculus made easy, http://lrcwww.epfl.ch/PS_files/d4paper.ps, Technical Report 96/218, EPFL-DI, submitted to IEEE TIT, December 1996. [12] McCanne, Steven; Jacobson, Van; Vetterli, Martin. Receiver-driven Layered Multicast, ACM SIGCOMM '96, August 1996. Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 17] INTERNET-DRAFT draft-almesberger-srp-01.txt November 1997 7. Author's address Werner Almesberger Jean-Yves Le Boudec Institute for computer Communications and Applications Swiss Federal Institute of Technology (EPFL) CH-1015 Lausanne Switzerland email: almesber,leboudec@lrc.di.epfl.ch Tiziana Ferrari DEIS, University of Bologna viale Risorgimento, 2 I-40136 Bologna Italy and Italian National Inst. for Nuclear Physics/CNAF viale Berti Pichat, 6/2 I-40127 Bologna Italy email: ferrari@lrc.di.epfl.ch Almesberger, Ferrari & Le Boudec Expires 5/98 [Page 18]