Tang Haitao
Laboratory of Computer and Information Science
Helsinki University of Technology
Haitao.Tang@hut.fi
1. Introduction
The Internet protocol is based on the "datagram" paradiam. Packets are routed
independently of each other, without any concept of "connection." There is
no notion of "quality of service." The throughput is not guaranteed; the
transmission delay is not bounded. The network is simply expected to do its
"best effort" to satisfy its clients, i.e., to render a service proportional
to the client's investment (if the network has been equipped with faster
lines, we expect shorter response times). However, the simple best-effort
service is not well fitted for the new multimedia applications. For example,
sending voice and video in real time requires the guarantee that the data
will flow at a stable rate, with a constant or almost constant delay.
This is why the telephone network uses a "circuit switching" paradiam - each
time a person starts a phone conversation, the telephone network reserves
"a circuit," in fact a sufficient share of every transmission link on the
path between the two partners.
Figure 1: The connection between two Internet Hosts
Faced with the demands for new transmission facilities, the Internet research groups have initiated several efforts. The first response has been to demonstrate the asynchronous-packet switching technology can provide guarantees of services if sufficient resources are reserved in the routers for real-time flows. As a follow-up, several teams have started to develop "resource reservation" protocols, so that strict application requirements could be satisfied, if needed. In parallel, other teams have started to deploy multimedia applications on the existing Internet, demonstrating that the supposedly strict requirements are in fact more flexible than expected and that reservation is often not needed [1]. In our opinion, the "flexible" is in fact supported by the flow adaptation of the applications. It is quite limited and may not be reliable at all in the existing and future Internet. From a lot of experiences [13, 14, 15], we have the feeling that it may not be possible to guarantee the bounded delay all the time. For this reason, we believe that a certain degree of resource reservation is needed in future integrated services Internet.
ATM networks are widely seen as good backbone networks for Internet. Unlike the simply traffic multiplex link technology, ATM allowing several virtual channels to be established over a single wire (or fiber) potentially based on an applications' network performance objectives. It could make IPng over ATM subnetworks to facilitate a virtual circuit per application while also maintaining support for the transport of IPng packets across conventional subnetworks. The involvement of ATM makes the resource reservation more desirable and feasible.
Certainly, the the resource reservation should be independent with Internet routing protocol as much as possible. It is because the evolution phase of the routing protocol can be different from that of the resource reservation.
In the following sections, we will introduce the principles behind resource reservation and the way to facilitate the resource reservation for an integrated services Internet.
2. The Principles Relating Resource Reservation through Queuing and Scheduling
Today, most Internet routers operate in a strict "first-come, first-served"
fashion. Packets will be transmitted in the order of arrival. This behavior has
the advantage of being easy to understand and implement, but the delays then
vary as a function of the network load. It is not suitable for the the new
multimedia applications in real time. To cope with the problem, some methods
related to resource reservation have been introduced. We will summarize some
of them in this section.
2.1 Fair Queuing
A traditional datagram switches packets independently. There is no memory of
the past history, no state in the network.
The "fair queuing" algorithm was developed as a way to impose some fairness
in the switching process. The principle of fair queuing
[1, 7] is precisely to
introduce some state in the switches by separating the incoming traffic into
well-identified "flows" and by guaranteeing each flow an equal share of the
transmission capacity.
In the simplest form of the fair queuing algorithm, one will associate to each queue x the value S(x,i) and F(x,i) of R(ti) at the beginning and at the end of the transmission of the packet of rank i from that queue, where R(ti) denote the number of rounds of scheduling (e.g., round-robin) between ti-1 and ti. Let ti and pi denote the arrival time of the packet and its length. Fair queuing will be achieved if:
S(x,i)=MAX(F(x,i-1),R(ti))
F(x,i)=S(x,i)+Pi
One can then associate to each packet the value F(x,i) that is computed when it arrives and use it to define the sending order of the packets.However, it does not require certain QoS parameters from the service interface. This makes the fair queuing method not attractive for the future IP, which plans to support the new multimedia services.
2.2 Weighted Fair Queuing
Weighted fair queuing is in fact the "Virtual Clock" presented in
[8].
Virtual Clock algorithm also deals with well-identified flows which have been
established through some management procedure. Its purposes are
[1]:
d=P/ARi
where P is the length of the packet.The packet is stamped with the new value of VCi. Then, the packets from all the flows are transmitted by increasing the order of the stamps.
To solve the problem caused by the possible burstness of the packet flow, an auxiliary virtual clock auxVC is introduced in [8]. Thus, the full version of Virtual Clock algorithm can be presented as following:
auxVCi=MAX(real time, auxVCi)
VCi=VCi+P/ARi
auxVCi=auxVCi+P/ARi
Stamp the packet with auxVCi and transmit packets from all the flows by increasing the order of the stamps. When the buffer is full, drop the last packet from the queue. Every AIi period, adjust VCi to real time if VCi is smaller than real time or take control actions if "VCi - real time" is larger than certain positive threshold. Furthermore, if replacing the real time by "real time - Pi", the priority of flow can be handled.
2.3 Shared Links
Shared links are in fact a framework for utilizing various queuing and
scheduling methods to achieve the wanted link share. There could be link share
among several organizations or among different packet flow classes or both.
The basic structure is hierarchical. There must be a certain classification
method employed to classify the class of a flow. The models presented are
the Class Based Queuing by Van Jacobson and Sally Floyd and
[9] by David Clark, Scott Shenker, and Lixia Zhang.
In addition to the link share
procedures like WFQ and FIFO+, [9] also introduces
the relevant service
interface, admission control, etc, which are also needed for the
classification.
The application is not identified in the IP header. One has to look at the protocol type (TCP or UDP) and at the source and destination ports, which are placed in the first bytes of the pay load. Their information is needed for implementing a shared link.
Recently, A. Parekh and R. Gallager have proven that, if a flow has a limited data rate and if it gets a sufficient service rate, then the propagation delays are bounded [1]. It proves that it is possible for Internet to offer real-time service.
3. RSVP - A Reservation Protocol
RSVP is a resource reservation setup protocol which is designed for an
integrated services Internet [2]. Reservation
protocols are used to signal the network, or more precisely to the
intermediate routers, the needs of the users and of their applications.
The following is mainly referred to [2].
3.1 The Principles of RSVP
The RSVP protocol is used by a host, on behalf of an application data
stream, to request a specific quality of service (QoS) from the
network. The RSVP protocol is also used by routers to deliver QoS
requests to all nodes along the path(s) of the data stream and to
establish and maintain state to provide the requested service. RSVP
requests will generally, although not necessarily, result in
resources being reserved along the data path.
RSVP requests resources for simplex data streams, i.e., it requests resources in only one direction. Therefore, RSVP treats a sender as logically distinct from a receiver, although the same application process may act as both a sender and a receiver at the same time. RSVP operates on top of IP (either IPv4 or IPv6), occupying the place of a transport protocol in the protocol stack. However, RSVP does not transport application data but is rather an Internet control protocol, like ICMP, IGMP, or routing protocols. Like the implementations of routing and management protocols, an implementation of RSVP will typically execute in the background, not in the data forwarding path, as shown in Figure 2.
RSVP is not itself a routing protocol; RSVP is designed to operate with current and future unicast and multicast routing protocols. An RSVP daemon consults the local routing database(s) to obtain routes. In the multicast case, for example, a host sends IGMP messages to join a multicast group and then sends RSVP messages to reserve resources along the delivery path(s) of that group. Routing protocols determine where packets get forwarded; RSVP is only concerned with the QoS of those packets that are forwarded in accordance with routing.
Figure 2: RSVP in Hosts and Routers
Each node that is capable of resource reservation passes incoming data packets through a "packet classifier", which determines the route and the QoS class for each packet. For each outgoing interface, a " packet scheduler" then makes forwarding decisions for each packet to achieve the promised QoS on the particular link-layer medium used by that interface.
If the link-layer medium is QoS-active, i.e., if it has its own QoS management capability, then the packet scheduler is responsible for negotiation with the link layer to obtain the QoS requested by RSVP. This mapping to the link layer QoS may be accomplished in a number of possible ways; the details will be medium-dependent. On a QoS- passive medium such as a leased line, the scheduler itself allocates packet transmission capacity. The scheduler may also allocate other system resources such as CPU time or buffers.
In order to efficiently accommodate heterogeneous receivers and dynamic group membership, RSVP makes receivers responsible for requesting QoS. A QoS request, which typically originates from a receiver host application, is passed to the local RSVP implementation, shown as a daemon process in Figure 1. The RSVP protocol then carries the request to all the nodes (routers and hosts) along the reverse data path(s) to the data source(s).
At each node, the RSVP daemon communicates with two local decision modules, "admission control" and "policy control". Admission control determines whether the node has sufficient available resources to supply the requested QoS. Policy control determines whether the user has administrative permission to make the reservation. If both checks succeed, the RSVP daemon sets parameters in the packet classifier and scheduler to obtain the desired QoS. If either check fails, the RSVP program returns an error notification to the application process that originated the request. We refer to the packet classifier, packet scheduler, and admission control components as "traffic control".
RSVP is designed to scale well for very large multicast groups. Since both the membership of a large group and the topology of large multicast trees are likely to change with time, the RSVP design assumes that router state for traffic control will be built and destroyed incrementally. For this purpose, RSVP uses "soft state" in the routers. That is, RSVP sends periodic refresh messages to maintain the state along the reserved path(s); in absence of refreshes, the state will automatically time out and be deleted.
RSVP protocol mechanisms provide a general facility for creating and maintaining distributed reservation state across a mesh of multicast or unicast delivery paths. RSVP transfers reservation parameters as opaque data (except for certain well-defined operations on the data), which it simply passes to traffic control for interpretation. Although the RSVP protocol mechanisms are largely independent of the encoding of these parameters, the encodings must be defined in the reservation model that is presented to an application.
3.2 RSVP Protocol Mechanisms
We like to introduce only those interesting mechanisms.
Figure 3: Router Using RSVP Figure 3 illustrates RSVP's model of a router node. Each data stream arrives from a "previous hop" through a corresponding "incoming interface" and departs through one or more "outgoing interface"(s). The same physical interface may act in both the incoming and outgoing roles for different data flows in the same session. Multiple previous hops and/or next hops may be reached through a given physical interface, as a result of the connected network being a shared medium, or the existence of non-RSVP routers in the path to the next RSVP hop. An RSVP daemon preserves the next and previous hop addresses in its reservation and path state, respectively.
There are two fundamental RSVP message types: Resv and Path.
Each receiver host sends RSVP reservation request (Resv) messages upstream towards the senders. These reservation messages must follow exactly the reverse of the routes the data packets will use, upstream to all the sender hosts included in the sender selection. Resv messages are delivered to the sender hosts themselves so that the hosts can set up appropriate traffic control parameters for the first hop.
Each RSVP sender host transmits RSVP Path messages downstream along the uni-/multicast routes provided by the routing protocol(s), following the paths of the data. These "Path" messages store "path state" in each node along the way. This path state includes at least the unicast IP address of the previous hop node, which is used to route the Resv messages hop-by-hop in the reverse direction. (In the future, some routing protocols may supply reverse path forwarding information directly, replacing the reverse-routing function of path state).
Path messages are sent with the same source and destination addresses as the data, so that they will be routed correctly through non-RSVP clouds. On the other hand, Resv messages are sent hop-by-hop; each RSVP-speaking node forwards a Resv message to the unicast address of a previous RSVP hop.
Path and Resv messages are idempotent. When a route changes, the next Path message will initialize the path state on the new route, and future Resv messages will establish reservation state there; the state on the now-unused segment of the route will time out. Thus, whether a message is "new" or a "refresh" is determined separately at each node, depending upon the existing state at that node.
RSVP sends its messages as IP datagrams with no reliability enhancement. Periodic transmission of refresh messages by hosts and routers is expected to handle the occasional loss of an RSVP message. If the effective cleanup timeout is set to K times the refresh timeout period, then RSVP can tolerate K-1 successive RSVP packet losses without falsely erasing a reservation. It is recommended that the network traffic control mechanism be statically configured to grant some minimal bandwidth for RSVP messages to protect them from congestion losses.
The state maintained by RSVP is dynamic; to change the set of senders Si or to change any QoS request, a host simply starts sending revised Path and/or Resv messages. The result will be an appropriate adjustment in the RSVP state in all nodes along the path.
There are two types of RSVP teardown message, PathTear and ResvTear. A PathTear message travels towards all receivers downstream from its point of initiation and deletes path state, as well as all dependent reservation state, along the way. An ResvTear message deletes reservation state and travels towards all senders upstream from its point of initiation. A PathTear (ResvTear) message may be conceptualized as a reversed-sense Path message (Resv message, respectively).
Therefore, there will be policy control as well as admission control over the establishment of reservations. As input to policy control, RSVP messages may carry policy data. Policy data may include credentials identifying users or user classes, account numbers, limits, quotas, etc. Like flowspecs, policy data will be opaque to RSVP, which will simply pass it to a "Local Policy Module" (LPM) for a decision.
RSVP messages may carry integrity objects that can be created and verified by neighbor RSVP-capable nodes. These objects use a keyed cryptographic digest technique and assume that RSVP neighbors share a secret [3].
4. RSVP and ATM Subnetwork
When the RSVP on a node makes resource reservation along a route whose
link-layer medium is an ATM subnetwork (i.e., a QoS-active medium) as shown
in Figure 4. The packet scheduler in Figure 2 is
responsible for negotiation with the ATM subnetwork to obtain the QoS
requested by RSVP.
Figure 4: The ATM Subnetwork
The ATM User-Network Interface (UNI) signaling protocol based on ITU-TS Q.93B allows many different service parameters to be specified for describing connection characteristics. These parameters can be grouped into several categories: ATM adaptation layer (AAL) information, network QoS objectives, connection traffic descriptor, and transit network selector. The AAL information specifies negotiable parameters such as AAL type and maximum packet sizes. The network QoS objectives describe the service that the ATM user expects from the network. Q.93B allows for one of five service classes to be selected by the ATM user. The service classes are defined as general traffic types such as circuit emulation (class A), variable bit rate audio and video (class B), connection-oriented data transfer (class C), connectionless data transfer (class D), best effort service (class X), and unspecified [15]. Each of these categories are further specified through network provider objectives for various ATM performance parameters. These parameters may include cell transfer delay, cell delay variation, and cell loss ratio. The connection traffic descriptor specifies characteristics of the data generated by the user of the connection. This information allows the ATM network to commit the resources necessary to support the traffic flow with the quality of service the user expects. Characteristics defined in the ATM Forum UNI specification include peak cell rate, sustainable cell rate, and maximum and minimum burst sizes [15]. Lastly, the transit network selection parameter allows an ATM user to select a preferred network provider to service the connection [15].
There are several parameters required to map ATM services from a higher level service like IPng. These ATM parameters can be categorized in the following manner: addressing parameters, connection QoS-related parameters, connection management information, and ATM virtual circuit identifier. The first three categories provide support for ATM signaling. The last parameter, a connection identifier that maps IPng packets to ATM virtual circuits, provides support for an ATM virtual circuit per application when the end-to- end connection travels across an ATM subnetwork(s) (this does not assume that ATM is the only type of subnetwork that this connection travels across).
IPng packets need not explicitly contain information parameters describing an application's traffic characteristics and network performance objectives (e.g., delay = low, throughput = 10 Mb/s). This information is mapped from the RSVP QoS request.
4.1 The Reservation Setup through ATM
The good way for the reservation setup of RSVP over ATM (both unicast
and multicast) is called ``ATM shortcut''. For an application with QoS
requirements the classical
IP over ATM architecture does allow for QoS support over the VCs between the
routers. This solution is not altogether satisfactory since it may not
provide the QoS which would be possible if a direct VC through the ATM
network was established along the path through the ATM network.
Such a direct connection is referred to as a ``ATM shortcut'', which
eliminates the level 3 processing at the routers and thus allows better
performance, see Figure 4.
A Resv message is considered new when it represents either a reservation requests for a new flow or a request to modify the reservation of an existing flow. When such a Resv message arrives at B, B inserts its own ATM address as an object into this message, and forwards the message along the default routed path to A. Intermediate routers recognize the Resv message but do not create any session or reservation and simply forward the message upstream. When this Resv message arrives at A it carries in addition to the regular RSVP information, both the ATM address of the egress router B and QoS information necessary to determine the type of ATM VC that needs to be setup.
Since intermediate nodes do not need to process the Resv message, an alternative here is to encapsulate the Resv message into an IP datagram that is then tunneled from B to A. Tunneling provides the advantage that packet processing is expedited (along the fast-path through the router) since there is no special processing at intermediate nodes. On the other hand, the packet is not treated as a signaling packet and is susceptible to normal loss at intermediate nodes.
After the shortcut VC from A to B is set up, B needs to be able to associate the newly created VC with the RSVP flow. In order to achieve this, the flow identifier consisting of the tuple
(sourceIPaddress;destinationIPaddress; transportlayer)
is carried in the SETUP message in the Broadband High Layer Information (B-HLI) element (the length of this field would have to be extended from its current size of 8 bytes). The source and destination IP addresses cannot be inferred from the ATM addresses in the router--router case. The source and destination addresses themselves further consist of pairs of the form(IPaddress;portnumber)
Note also that the receipt of the SETUP message provides an implicit acknowledgment that the Resv message was received at router A. This means that router A also has received all the information necessary to forward Resv messages upstream, i.e. the RSVP filter and service specifications that are not directly available from the ATM connection characteristics. As a result, the egress router B now suppresses the transmission of Resv refreshes towards router A, unless they carry a modified service specification.
4.2 Flow Mapping between RSVP and ATM
RSVP defines a session as the set of data flows with the same
(unicast or multicast) destination. As a result, at an endpoint of a
flow (sender or receiver) the data flow is uniquely identified by the pair
(sourceIPaddress;destinationIPaddress)
The source and destination addresses themselves further consist of pairs of the form(IPaddress;portnumber)
where the destination IP address can be a multicast IP address.The ATM UNI identifies a connection through the Connection Identifier used in the SETUP, CONNECT, etc. messages. Connection Identifier is associated to an ATM flow from one sender to one or more receivers and is unique at the sender. A call can be uniquely identified in the ATM network by the pair (Connection Identifier, sender ATM address).
From the above discussion, we see that a node at the boundary between IP and ATM networks can map the quadruplet (source IP address, source port number, destination IP address, destination port number) that uniquely identifies an RSVP flow, to an ATM GCID consisting of (call identifier, sender ATM address).
5. Discussion
People have found that only ATM alone may not be possible to meet fully the
needs of the future data service. There are a lot of efforts have been made to
build certain integrated services networks like the B-ISDN and the integrated
services Internet. Maybe, in the long run, the integrated services Internet
will be further integrated into B-ISDN. However, for the seeable future,
the integrated services Internet will still be very popular, which will gives
a large set of services, both the predictive and guaranteed from traffic point
of view. The predictive services are like ftp, telnet, etc. The guaranteed
services are like some multimedia services on the Internet, e.g., voice and
video services in real time, etc. Especially when ATM is employed as the
backbone subnetwork of the integrated services Internet, the capacity and
flexibility of the Internet will be greatly increased. The high capacity alone
can make more feasible for the Internet to support the traffic-guaranteed
services. Certainly, the current Internet does not fully support the
traffic-guaranteed services. Except the link capacity, the lack of
QoS-supporting function in the current internet can be the main cause of the
weakness. For this reason, building suitable resource reservation mechanism
for the Internet is badly needed today. As a resource reservation protocol for
the Internet, RSVP is still an experiment, but it is a popular one.
In fact, there may be some complemental or even stand-alone methods which can be employed together with RSVP to support the "real-time" services. Adaptive source data compression or adaptive source data rate can be the one among the methods. For example, the output data rates of the voice compression algorithms are from 2.4 Kbps to 64 Kbps. It is clear that we can adjust the data rate according to the network load. We have seen certain kinds of voice services which already exist in the current Internet although they may not work or work without suitable reliability or wanted satisfaction when network load is high. When the QoS request mapping between application and the network is possible, the adaptive source data rate can be a good complement for RSVP. The QoS request mapping between application and the network should be supported in the future Internet.
Here, we like to introduce the good opinion given by [1]. For the predictive services, resource reservation is not needed in order to get the maximal global satisfaction, which is like the current situation. For the guaranteed services, resource reservation is needed if the traffic needs to be strictly guaranteed. Thus, to get the global maximal satisfaction in the integrated services Internet, the flows from both classes of the services should be "separated," i.e., certain "fire-wall" should be built for them to share only the resource of their own class.
After all, in addition to RSVP, sufficient link capacity is the necessary condition for the future Internet to support the "real-time" services. The future Internet is likely to be built with the ATM backbone networks and numerous LANs. Thus, the LAN should also have enough link capacity if an end user of it needs the "real-time" services.