Internet DRAFT - draft-bianchi-qos-multicast-over-diffserv
draft-bianchi-qos-multicast-over-diffserv
Internet Engineering Task Force G. Bianchi
INTERNET-DRAFT University of
Palermo, Italy
Document: N. Blefari-Melazzi
draft-bianchi-qos-multicast-over-diffserv-00.txt University of Roma,
Tor Vergata, Italy
G. Bonafede
University of Roma,
La Sapienza, Italy
E. Tintinelli
University of Roma,
La Sapienza, Italy
Category: Informational December 2002
Expires June 2003
MultiGRIP: Quality of Service Aware Multicasting over DiffServ
Status of this Memo
This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026. 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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
1 Abstract
Efficient delivery of real-time multicast traffic imposes on the
underlying network infrastructure the burden of supporting Quality of
Service (QoS). This can be quite a complex issue in a Differentiated
Services (DiffServ) IP network, especially if multicast users are
allowed to dynamically join and leave the multicast tree. In fact, since
DiffServ lacks of explicit reservation states, i) a replicating node
cannot test whether a corresponding reservation exists on an output
link, and ii) upon a dynamic join of a QoS multicast user, the DiffServ
network lacks of control functions to verify whether resources are
available along the new path. In this document, we present a solution to
support dynamic multicast with QoS over a DiffServ network. Our solution
combines two ideas. First, resource availability along a new QoS path is
verified via a probe-based approach. Second, QoS is maintained by
marking replicated packets with a special DSCP value, before forwarding
them on the QoS path. We are fully aware that the possible application
of the principles described in this draft in the Internet raises many
Bianchi&Blefari Informational - Expires June 2003 [Page 1]
Quality of Service Aware Multicasting over DiffServ December 2002
issues, which we do not address. Our aim, then, is not proposing a
fully-fledged solution, but contributing to the on-going discussions in
the international arena on these matters, by means of what we may see
also as a problem statement document.
Table of Contents
1 Abstract...........................................................1
2 Introduction.......................................................2
3 Motivation and directions..........................................4
4 QoS Multicast forwarding...........................................5
5 Establishing QoS...................................................8
6 Numerical Results.................................................13
7 Conclusions.......................................................16
8 Appendix: Security considerations.................................16
9 References........................................................17
10 Author's Addresses...............................................18
11 Full Copyright Statement.........................................19
2 Introduction
The Internet is witnessing the emergence of several Web-based real-time
multimedia and multicast applications, such as video-conferencing,
staggered multimedia information retrieval, etc. Unfortunately, the
current best-effort Internet does not offer Quality of Service (QoS)
guarantees to effectively support unicast streaming services, let alone
multicast ones.
Several proposals have appeared in the literature in the area of QoS
multicast (see [1]). Most of the work concerns the development of
multicast QoS routing protocols (e.g., [2], [3]and references therein
contained), i.e., protocols that select multicast paths under QoS
constraints. Conversely, the issue of endowing current multicast
protocols with resource reservation and admission control mechanisms has
been generally confined to be a somehow straightforward extension of
related unicast protocols. For example, [4] proposes a reservation
mechanism for multicast traffic based on a reference Internet model very
similar to that proposed in the Integrated Services approach. In
addition, the RSVP protocol specification, version 1, [5] has been
devised to efficiently support multicast traffic.
We argue that novel problems arise in QoS multicast when the reference
unicast QoS architecture is not based on explicit and stateful resource
reservation protocols. This is specifically the case for the
Differentiated Services (DiffServ) framework [6]. DiffServ is a current
trend in the Internet community for the development of a QoS
architecture not burdened with the complex task of reservation states
creation and maintenance. The potential problems, and the complexity of
supporting multicast in a DiffServ environment are sketched in [6] and,
in greater details, in [7], [8], [9] (and therein contained references).
In particular, [7] highlight the following issues.
Bianchi&Blefari Informational - Expires June 2003 [Page 2]
Quality of Service Aware Multicasting over DiffServ December 2002
- First, dynamic addition of new members to a multicast group can
adversely affect existing other traffic, if resources are not
explicitly reserved after each join, since replicated packets get
the same Differentiated Services Code Point (DSCP) [6] of the
original packet and thus experience the relevant treatment,
consuming un-reserved resources.
- Second, resources should be reserved separately for each multicast
tree associated to a given sender, to allow simultaneous sending
by multiple sources, with QoS constraints.
- Finally, it appears difficult to support heterogeneous multicast
groups, i.e., groups in which different users have different
necessities.
More into details, as regards the last point, participants who can cope
with a best-effort service should coexist with participants needing
specified and different levels of QoS assurances, so that the same
multicast group can deliver differentiated services. For instance, a
user could browse a multicast multimedia session in best-effort mode and
then decide to switch to a QoS mode (eventually by paying for it).
Other related works are the following. The paper [8] proposes a solution
for QoS support in DiffServ based on tunneling mechanisms (multicast
packets encapsulated in DiffServ), which, in coherence with Internet
principles, pushes the complexity to the borders of the DiffServ
domains. The paper [9] devises a solution which succeeds in maintaining
the integrity of negotiated Service Level Agreement (SLA) by means of
weighted traffic conditioning and receiver-initiated marking schemes;
admission control operations are performed by suitably signaling network
management entities (e.g., Bandwidth Brokers û BB -, or suitable
functionality within ingress routers). This solution also supports
heterogeneous requirements within a multicast group by encapsulating the
markings for each of the branches with such heterogeneous QoS
requirements in the packet header, at the ingress router of the domain.
Finally, it is worth pointing out that QoS multicasting is a challenging
issue also because DiffServ is a sender-driven paradigm whereas
multicasting is inherently receiver-driven (more details on this aspect
can be found in [9]).
In this document, we propose a QoS multicast solution for DiffServ IP
networks. The goal of our proposed solution is i) to provide flexible
QoS support with respect to heterogeneous multicast groups, and ii) to
maintain compatibility with currently deployed multicast protocols, with
specific reference to PIM (Protocol Independent Multicast) [10], [11].
The rest of this document is organized as follows. The basic motivations
and directions of our proposed solution are outlined in section 3. Our
solution is illustrated in section 4, which explains how a QoS user
joins a multicast tree, and in section 5, which details how resource
reservation is performed on a QoS branching path. For convenience of the
reader, section 5 contains also a sub-section that is devoted to briefly
Bianchi&Blefari Informational - Expires June 2003 [Page 3]
Quality of Service Aware Multicasting over DiffServ December 2002
review a unicast DiffServ QoS solution, formerly proposed in [12], [13]
by some authors of this document, and used as a basic brick for our
multicast solution. Section 6 contains some introductory performance
evaluation results, based on simulations. Conclusions and further
research issues are presented in section 7.
3 Motivation and directions
The design requirements for our proposed solution were:
- QoS should be envisioned as an incremental addition to existing
multicast protocols devised for Best-Effort traffic - in other
terms, the QoS multicast solution should be backward compatible;
- We aim at devising an overlay solution, i.e., whose applicability
over the DiffServ network should be done with minimal modification
in the DiffServ router operation and in the underlying routing
protocols;
- The solution should be flexible with respect to heterogeneity of
users within a group, and of distribution trees (source-based or
core-based);
Because of these design requirements, we have selected PIM (Protocol
Independent Multicast), in the Sparse Mode (SM) version [10], [11], as
the reference multicast routing protocol. The reason is that PIM is
independent on the underlying unicast routing protocols, and it allows
several different configurations of the multicast distribution tree
(unique group shared distribution tree based on a central Core Router;
different distribution trees per specific source sending to a group;
coexistence of shared and source-specific trees for the same group).
To provide QoS multicast over DiffServ, two important issues need to be
considered. The first issue is how to differentiate the service level
supported on different paths inside the multicast distribution tree. The
second one is how to provide an admission control function in order to
support dynamic Joins, from QoS-enabled users. In both cases, recall
that no per-flow reservation state can be employed in the DiffServ
routers, whose role, as specified in the DiffServ architecture [6], is
simply to apply different forwarding disciplines to packet aggregates,
based on their DSCP value.
To solve the first issue, Bless and Wherle [7] suggest to add an
additional field in the Multicast Routing Table (MRT), which specifies
the DSCP(s) to be used for each output link. It is thus possible to
specify whether the next hop is QoS-enabled (i.e., mark packets with a
specified DSCP, corresponding to a negotiated QoS level), or not (i.e.,
mark packets with the Best-Effort DSCP). This solution allows
heterogeneous users to share the same multicast distribution tree, as
well as it allows deployment of several different QoS levels in the
network.
Bianchi&Blefari Informational - Expires June 2003 [Page 4]
Quality of Service Aware Multicasting over DiffServ December 2002
As discussed in section III below, our solution inherits from [7] this
marking strategy. However, this handy tool is not sufficient by itself
to provide QoS-aware and differentiated services in a multicast
environment. As a matter of fact, the authors of [7] assume to rely on
nonspecific control plane entities (e.g., Bandwidth Brokers), which
performs an admission control test, and list the following requirements:
- "there must be a mechanism for DiffServ nodes to inform a
management entity about the join request of a new subtree";
- "a mechanism must be supplied for instructing a router to suitably
change (and update) the DSCP value in the related multicast
routing table entry. This mechanism may be also incorporated into
an existing multicast routing protocol as an extension."
In our proposal, we combine a marking strategy very similar to that
proposed in [7] with a data plane DiffServ-compliant admission control
function, called GRIP (Gauge & Gate Reservation with Independent Probing
[12], [13]). As explained in section 5, GRIP can be adapted to the PIM-
SM framework.
4 QoS Multicast forwarding
This section shows the basic protocol operation. More details on the
joining operation of a QoS user to the multicast distribution tree will
be given in section 5. For convenience of presentation, we focus on the
example network scenario illustrated in Fig. 1.
Our discussion will assume PIM-SM as the multicast protocol of
reference, being the particularization to PIM-SSM (Source-Specific
Multicast) rather straightforward. In the basic operation of PIM-SM, a
router, called Rendez-vous Point (RP), is used, for all traffic sources
S, as the root of the distribution tree for the multicast group.
Destination hosts Hi avail themselves of Designated Routers (DRi) on
their LAN, which act on behalf of those hosts as far as the PIM-SM
protocol is concerned. In other words, the DR manages, on one side, all
local group management information (e.g., via the IGMP protocol), and,
on the other side, it emits PIM join/prune messages towards the RP. We
assume that all routers are DiffServ capable. In addition, we assume
that while routers A, B and C in Fig. 1 support PIM, intermediate
DiffServ routers, indicated with the label "R", are transparent to the
multicast protocol.
Multicast packets are replicated at each multicast router (these routers
are the nodes of the multicast tree), and are delivered to the multicast
destinations according to the routing information provided by the PIM
protocol operation (see [11]) and stored in a table called Multicast
Routing Table (MRT). Obviously, multicast routers are stateful,
according to the standard multicast protocols, while DiffServ routers
are stateless. In this scenario, scalability derives from the fact that
only a fraction (possibly small) of the network routers should be
multicast capable. Note that the tunneling solution adopted in [8] has
the effect of pushing all the handling of multicast states at the border
Bianchi&Blefari Informational - Expires June 2003 [Page 5]
Quality of Service Aware Multicasting over DiffServ December 2002
of the domains. In this sense, also [8] improves scalability by limiting
the number of stateful routers.
Following [7], we also assume that each multicast routing table (MRT)
stores, for each router output interface (oif), an additional entry.
This entry represents the Differentiated Services Code Point (DSCP)
value, which is used to mark replicated packets that are forwarded along
the considered interface.
Fig. 1 shows, in the leftmost column, labeled "Only H1+H2", the MRT
states for routers A, B, and C, in the assumption that only hosts H1
(QoS-enabled) and H2 (Best-Effort) are members of the multicast group.
In Fig. 1, we use the label "BE" to denote a Best-Effort service, (i.e.,
DSCP 000000) and the label "QoS" to denote a service with pre-defined
QoS requirements. For the sake of simplicity, in what follows we assume
that the network provides a single QoS level, in addition to the Best-
Effort service. Extension to multiple QoS levels is discussed in section
7.
+--+ time
|S | --------------------------------->
+--+ Only H1+H2 H3 joins H4 joins
|| +--------+ +--------+ +--------+
+--+ +------> | MRT-A |->| MRT-A |->| MRT-A |
|RP| | |oif|DSCP| |oif|DSCP| |oif|DSCP|
+--+ | | 1 | BE| | 1 | BE| | 1 | QoS|
+---+ || | | 2 | QoS| | 2 | QoS| | 2 | QoS|
|DR1|\ +--+ | +---+----+ +---+----+ +---+----+
+---+\===|A |-----------+ +--------+ +--------+ +--------+
|| +--+ +---> | MRT-B |->| MRT-B |->| MRT-B |
+--+ || | |oif|DSCP| |oif|DSCP| |oif|DSCP|
|H1| +--+ | | 1 | BE| | 1 | BE| | 1 | BE|
+--+ |R | -----------+ | 2 | -| | 2 | BE| | 2 | QoS|
QoS User +--+ / +---+----+ +---+----+ +---+----+
|| / +--------+ +--------+ +--------+
+---+ +--+/ +--+ +--+-------> | MRT-C |->| MRT-C |->| MRT-C |
|DR2|===|B |==|R |=|C |=\ |oif|DSCP| |oif|DSCP| |oif|DSCP|
+---+ +--+ +--+ +--+ \\ | 1 | -| | 1 | BE| | 1 | BE|
|| // \\ | 2 | -| | 2 | -| | 2 | QoS|
+--+ // \\ +---+----+ +---+----+ +---+----+
|H2| +---+ +---+
+--+ |DR3| |DR4|
BE user +---+ +---+ |RP: Rendez-vous Point
|| || |A,B,C: Multicast routers
+--+ +--+ |R: Non multicast routers
|H3| |H4| |DR: Designated Router
+--+ +--+ |oif: output interface
BE user QoS user |BE: Best Effort
Fig. 1 û Example network scenario
By looking at Fig. 1, we see that the MRT of router A marks packets
directed to host H1 (interface 2) with a QoS marking, while it labels
Bianchi&Blefari Informational - Expires June 2003 [Page 6]
Quality of Service Aware Multicasting over DiffServ December 2002
packets forwarded to interface 1 as BE. In the MRT of router B, clearly,
only the interface 1 is active, while router C has no multicast state,
at the moment. Let us now discuss what happens when, first the Best-
Effort host H3, and then the QoS host H4, join the multicast group.
In the case of H3, we adopt a standard PIM Join operation. The
Designated Router of H3, DR3, sends a PIM Join(*,G) message towards the
RP. When a multicast router receives this message, it adds a new entry
to its multicast routing table (MRT), with a BE value, for the
associated DSCP marking field. This state will indicate that future
datagrams destined for group G must be marked as BE, and forwarded on
the interface where the join message came from. The Join(*,G) message is
regenerated upstream along what we define as the Branching Path. This is
the path from the requesting DR to the first router that already has a
Join(*,G) state for that group, which is called Branching Router.
Eventually, the Branching Router could coincide with the RP itself. In
the specific case of Fig. 1, the Branching Path goes from DR3 to router
B, which is the Branching Router, since it already has a (*,G) state
created by the Join message coming from host H2, by way of DR2. The
second column of Fig. 1, labeled "H3 joins", shows the modified
multicast routing tables in routers A, B and C after a successful join
of the BE host H3.
In the case of QoS-host H4, a fundamental difference is the extent of
the Branching Path. If the Designated Router DR4 were to send a standard
Join(*,G) message, the Branching Router would have been router C, since
it already has a (*,G) state. However, when a QoS host wants to join the
group, it needs to send a modified join message, hereafter referred to
as Join(*,G,QoS) message, which explicitly carries the QoS level the
host is requesting.
(note that the new PIM messages considered in this document,
i.e., Join(*,G,QoS), Confirm(*,G,QoS), Prune(*,G,QoS), can be
built upon the PIM message format specifications, as extensions.
In fact, PIM defines only 8 different packets, while a 4-bit
packet type field (i.e., 16 possibilities) is available.)
This Join(*,G,QoS) message travels upstream until it either reaches the
RP, or a router with a (*,G,QoS) state (i.e., a state that instructs a
router to send QoS marked traffic over at least one of its interfaces).
We define "QoS Branching Path" the path from the Designated Router to
the first router that already has a Join(*,G,QoS) state for that group.
We name such a router as QoS Branching Router (note that it may be the
RP itself).
In Fig. 1, the QoS Branching Router for host H4 results to be router A.
The rightmost column of Fig. 1, labeled "H4 joins", shows the modified
multicast routing tables in routers A, B and C after a successful join
of the QoS host H4. As a side comment, note that now the distribution
tree has a QoS path from RP to DR4. Therefore, hosts H2 and H3 will
receive a BE service only on the last hop of their path. In other words,
Bianchi&Blefari Informational - Expires June 2003 [Page 7]
Quality of Service Aware Multicasting over DiffServ December 2002
the fact that some members of the multicast groups require QoS,
indirectly brings benefits also to Best-Effort users of the same group,
even if they are not paying for such benefitsà(see section 6 for
performance results).
Finally, note that a given host may upgrade its service level. For
example, an host may first send a Join(*,G) message to preview the
multicast group, and then upgrade to QoS by sending a Join(*,G,QoS).
This second message is regenerated upstream along the QoS Branching
Path, and, along its way, it modifies the state of the crossed multicast
router(s).
It remains to show, in the following section, how resource availability
along the QoS Branching Path is checked and reserved during a
Join(*,G,QoS) procedure.
5 Establishing QoS
This section focuses on the detailed operation necessary for a QoS user
joining the multicast tree to establish QoS on the new QoS Branching
Path. With reference to the example discussed in Fig. 1, in our
presentation we focus on the establishment of QoS on the QoS Branching
Path from router A as a starting point (the network path from RP to
router A is already QoS enabled, because of QoS user H1), to designated
router DR4 as a destination point.
(we assume that QoS on the last hop DR4 -> H4 is provided by some
layer-2 mechanism, or, in other words, that when the host H4 wants
to join the multicast tree with QoS, a local admission control
function on the last-hop segment has been already performed with
positive answer.)
Our proposal consists in adapting, to the multicast case, a DiffServ
compatible stateless admission control operation based on pure data-
plane operation, called GRIP, proposed in [12], [13] with unicast
traffic in mind. For convenience of the reader, the basic principles of
GRIP are briefly reviewed in section 5.1, while the adaptations of GRIP
to multicast are tackled in sections 5.2 and 5.3.
5.1 Review of the basic, unicast, GRIP operation
Provisioning of QoS in DiffServ networks is frequently assumed to be
accomplished via static over-provisioning (i.e., over-dimensioning of
core network links with respect to the expected offered traffic). When
dynamic provisioning of DiffServ domains is considered, the traditional
approach is to rely on centralized control entities, often referred to
as Bandwidth Brokers (BB). A BB is an agent that has sufficient
knowledge of resource availability and network topology to make
admission control decisions. Border routers use control protocols to
interact with this agent. The existence of BBs has been assumed in [7],
[9] to manage multicast traffic handling strategies.
Bianchi&Blefari Informational - Expires June 2003 [Page 8]
Quality of Service Aware Multicasting over DiffServ December 2002
We have shown in [12], [13] that per-flow admission control can be
supported on stateless DiffServ domains, i.e., with no need of managing
per-flow states within each core router. We recall that, in the DiffServ
approach, core routers should not support any explicit signaling
protocol (this would imply parsing and interpreting higher layer
information contained in signaling packets payload). Instead, their
unique duty is to implement low-layer mechanisms devised to forward/drop
packets, and apply packet scheduling mechanisms, on the basis of the
DSCP value marked on each IP packet header.
Our admission control procedure, named GRIP (Gauge & Gate Reservation
with Independent Probing), is based on the idea of using "implicit
signaling", i.e., GRIP uses pure data-plane operation (packet
dropping/forwarding) to convey, at the network borders, the information
that the network is congested and a new flow cannot be accepted. A GRIP
router is a plain DiffServ router, which handles a number of aggregate
classes. A packet belongs to a class on the basis of its DSCP value. A
GRIP router supports at least three different DSCP values: Best Effort
(BE) packets, QoS information packets, and QoS probing packets. The
following description will assume that only one QoS level and one
traffic class is supported (i.e., only one information and one probing
DSCP label in addition to BE), although we remark that the GRIP router
operation can be extended to support several levels of QoS and different
traffic classes.
(to support several levels of QoS it is necessary to: i) add a new
pair of DSCP values (for information and probing packets) for each
additional QoS class, and ii) by suitably configuring the
(standard) DiffServ scheduling rules among the supported QoS
classes to reciprocally protect each of them from congestion
eventually arising on other QoS classes. This is perfectly coherent
with the DiffServ paradigm, as different QoS classes are handled in
a differentiated way. It is worth to note that different DSCP pairs
can also be used to manage heterogeneous traffic classes (where a
traffic class is defined as a set of sources with equal or very
similar traffic parameters, e.g., peak rate, sustainable rate,
etc.). In this case, different traffic classes are handled by
separate GRIP modules, each implementing a suitably engineered
measurement module and decision criterion. Other ways to handle
different traffic classes without using separate GRIP modules and
DSCP tags, but at the expense of a loss in efficiency, can be found
in [15]. Thus, defining the number of traffic classes is a matter
of a trade-off between complexity and efficiency. However, we note
that separate traffic classes are not necessarily a synonym of
complexity and simplistic treatment, but can lead to a greater
flexibility).
A measurement element in each GRIP module is in charge of taking a
smoothed and filtered measure of the load offered by information
packets. It will soon be clear that this is a measure of the aggregate
Bianchi&Blefari Informational - Expires June 2003 [Page 9]
Quality of Service Aware Multicasting over DiffServ December 2002
accepted traffic. On the basis of these traffic measurements, and
according to a suitable Decision Criterion, the measurement module
drives an Accept/Reject switch. When the switch is in the ACCEPT state,
incoming probing packets are forwarded to the output interface.
Conversely, probing packets are dropped when the switch is in the REJECT
state. In other words, the router acts as a gate for packets labeled as
probing, where the gate is opened or closed on the basis of traffic
estimates taken on the aggregate accepted load (hence the Gauge&Gate in
the acronym GRIP). As thoroughly shown in [12], the described operation
is not only compatible with DiffServ, but it is already supported in the
specification of the DiffServ Assured Forwarding Per-Hop Behavior (AF-
PHB) [14].
Admission control support via implicit signaling arises when the above
described operation (localized and independent within each core router)
is combined with a suitable end-point operation. When a user terminal
requests a unicast connection for the considered QoS and traffic class,
the source node transmits a packet whose DSCP is marked as probing.
Meanwhile, the source node activates a probing phase timeout, lasting
for a reasonable time. If no response is received from the destination
node before the timeout expiration, the source node enforces rejection
of the connection setup attempt. Otherwise, if a feedback packet is
received in time, the connection is accepted, and control is given back
to the user application, which starts a data phase, simply consisting in
the transmission of data packets, whose DSCP is marked as information.
In order for a call setup procedure to succeed, the probing packet needs
to find all the routers along the path in the ACCEPT state (if the
probing packet encounters a router in the REJECT state, it gets
discarded; hence it does not reach the destination, no feedback packet
will be relayed back, and the call will be blocked as soon as the
probing phase timeout expires).
It remains to understand which level of QoS provisioning can be offered
by the GRIP operation. Since the decision criterion is locally taken by
each router, on the basis of filtered and smoothed measurements taken on
the aggregate accepted load (i.e., throughput), GRIP effectiveness is
comparable to Measurement Based Admission Control (MBAC) schemes. In
fact, GRIPÆs measurement module can make use of state-of-the art MBAC
mechanisms (e.g., [16] and references therein contained), for which it
has been shown that a target QoS performance can be obtained by simply
controlling throughput. An example of a very simple Decision Criterion
is to switch from ACCEPT to REJECT state when the aggregate load
measurement exceeds a given threshold, and conversely. A more specific
example of a Decision Criterion is proposed in [13], where we show that,
with suitable additional assumptions, it is possible to provide as much
as hard performance guarantees.
To conclude, it is useful to recall that, even if GRIP bases the
accept/reject decision on end-point operations, it does not strictly
belong to the family of schemes generally referred to as Endpoint
Bianchi&Blefari Informational - Expires June 2003 [Page 10]
Quality of Service Aware Multicasting over DiffServ December 2002
Admission Control (EAC - see [17] and references therein contained). In
fact, these schemes assume that the admission control decision is taken
at the end-point, as a result of a probing phase whose goal is to allow
the end-points to measure whether network resources are available (i.e.,
external network measures). Conversely, in GRIP the probing phase is
limited in principle to a single probing packet transmitted in the
network; the goal of the probing packet is to cross through the core
routers, and being dropped or forwarded on the basis of internal network
measurements, which clearly result to be much more effective, as they
are not bounded to last (as in EAC schemes) for just the call setup
duration, i.e., few hundreds of ms, for reasonably bounded call set-up
times. Finally, we remark that GRIP does not require modifying the basic
router operation by introducing packet marking schemes within routers or
by forcing routers to parse and interpret higher layer information, as
done in some literature proposal (quoted in [13]).
5.2 Adaptation of unicast GRIP to multicast
Let us look back at Fig. 1, remembering that we want to establish QoS,
considering the network router A as a starting point and the designated
router DR4 as a destination point. When the QoS Branching Router A first
receives a Join(*,G,QoS) message, it sends a GRIP Probe down on the
multicast tree. As reviewed above, the probe is a normal packet, which
is distinguished from information packets via a special DSCP marking.
Specifically, if QoS packets are marked with DSCP value, say X1, GRIP
Probes are marked with a different DSCP value, say X2, which is
logically associated to X1. For each QoS level, a different pair of
DSCPs should be reserved. All network routers (i.e., both multicast-
capable routers and non-multicast capable routers) support a DiffServ
Per-Hop-Behavior (i.e., a data-plane mechanism) which consists in
letting packets marked as X2 go through only, for instance, if the load
run-time measured on X1-marked packets is lower than a given threshold.
The result of this operation is that a GRIP Probe is received at the
destination DR4 only if all the routers along the path are found in a
non-congested state, defined with a suitable criterion (see e.g., [13]).
When the GRIP Probe arrives at DR4, a Confirm(*,G,QoS) message is sent
back as a feedback packet, to notify the sender node A that all the
routers along the QoS Branching Path can accept a QoS connection. When
the Confirm(*,G,QoS) message is finally received at router A, the
multicast data can be forwarded on the new path. As discussed in section
4, subsequent replicated packets are marked according to the DSCP value
specified in the Multicast Routing Table.
5.3 State handling in Multicast Routers
While this basic operation appears a straightforward extension of GRIP,
there are several details than need to be clarified. A first problem is
that, although the aim of the GRIP Probe is to check whether the "point-
to-point" communication from A to DR4 can support QoS, in practice it is
necessary to route the GRIP Probe as a Multicast packet. In fact, the
Bianchi&Blefari Informational - Expires June 2003 [Page 11]
Quality of Service Aware Multicasting over DiffServ December 2002
GRIP probe needs to follow the same path of the multicast data packets.
We have solved this problem by using a multicast packet type, for the
GRIP probe, and by updating the Multicast State within each multicast
node so as to route the GRIP Probe down to the appropriate output
interfaces only. This is accomplished by extending the PIM-SM state
machine associated to each multicast router interface, to manage two
additional states per QoS class (see Fig. 2):
- Probing State (PRB state): when a multicast router output
interface is in the PRB state, it means that a Join(*,G,QoS)
message has been received, but no Confirm(*,G,QoS) message has
been received yet.
- Join-QoS state: this state is activated after a confirmation
message, and it implies that the router output interface is QoS-
enabled. When in the Join-QoS state, the multicast routing table
is set as described in section 4.
- When in the PRB state, packets are forwarded according to the
following rules:
- Packets labeled as information packets are replicated and
forwarded according to the existing Multicast Routing Table. With
reference to the example of Fig. 1, while host H4 is joining the
multicast group (i.e., before a Confirm(*,G,QoS) has arrived),
routers A and B continue to operate according to the previous MRT
(central column in Fig. 1), i.e., they replicate and forward
packets labeled as BE, while router C does not replicate multicast
data packets on the output interface 2.
- Probes are recognized based on their special DSCP value. They are
forwarded only toward interfaces whose state is PRB. With
reference to the considered example, a Probe packet is generated
at router A and forwarded only on interface 1, while the same
Probe packet is forwarded only on interface 2 at both routers B
and C.
The extended PIM-SM state machine is illustrated in Fig. 2, in the
assumption of a single QoS class. In case of more QoS classes, each
class will have its own Probing and Join-QoS state.
Moreover, for convenience of illustration, we have not explicitly
reported in the figure the PIM-SM Prune-Pending state, and a similar
QoS-Prune-Pending state necessary to handle the QoS class. Entrance in
this state occurs when a Prune(*,G) message (or, in the case of QoS, a
Prune(*,G,QoS) message) is received. The system remains in this state
until a timeout expires, or a Join(*,G) (or Join(*,G,QoS), in the case
of QoS) is received to refresh the multicast state. In fact, we recall
that multicast states are "soft" i.e., as long as a group G is active on
a router interface, the router will periodically receive Join(*,G)
messages in order to refresh the relevant states. When information
transfer for this group is no longer desired, the requiring entity
should stop sending joins for that group, so that the relevant state
expire. In alternative, an explicit PIM Prune(*,G) message (or a
Prune(*,G,QoS) in the case of QoS) can be sent towards the RP for that
multicast group.
Bianchi&Blefari Informational - Expires June 2003 [Page 12]
Quality of Service Aware Multicasting over DiffServ December 2002
Prune(*,G)
[Via Prune-Pending-QoS]
+---------------------------------------------------+
| |
| +---------+ Confirm(*,G,QoS) +--------+
| | Probing |-------------------------------->|Join-QoS|
| +---------+ +--------+
| A A |
| | | Prune(*,G,QoS)|
| | | [via Prune-Pending-QoS]|
| | | |
| | +------------------------------------- |
| | | |
| |Join(*,G,QoS) Join(*,G,QoS)| |
| | | V
| +---------+ Join(*,G) +--------+
+->| No Info |-------------------------------->| Join |
+---------+ +--------+
A |
| Prune(*,G) [via Prune Pending] |
+-------------------------------------------+
Fig. 2 û PIM-SM extended state machine
6 Numerical Results
As discussed in 5.1, GRIP requires a suitable Decision Criterion, to
drive the Accept/Reject switch. Here, we adopt the Decision Criterion
proposed in [13], which is based on the runtime estimation of the number
of active traffic sources, assumed to be suitably regulated at the
boundary of the domain by standard Dual Leaky Buckets (DLBs).
In the presence of DLB regulated sources, specific target performance
(e.g., loss/delay) levels can be hard-guaranteed whenever the maximum
number of admitted flows does not overflow a suitable threshold K. We
consider K as a "tuning knob", which allows the domain operator to set
target performance levels. The relationship between K and the guaranteed
performance levels results from an off-line computation (see [13]). In
other words, we choose target performance levels; we map such
performances in a value of K by means of a suitable algorithm and then
GRIP enforces such value; as a consequence the QoS traffic will perceive
the desired performance.
In state-based admission control schemes, the enforcement of the
threshold K is very simple: it is sufficient to keep track, by means of
signaling exchanges, of the number of admitted flows N, and accept a new
connection setup request as long as N.K-1. In our, stateless, procedure
we estimate at runtime the number of flows, N, avoiding signaling and
state maintenance, but incurring in possible inefficiencies (see [13]
for details).
Bianchi&Blefari Informational - Expires June 2003 [Page 13]
Quality of Service Aware Multicasting over DiffServ December 2002
Our criterion does not need assumptions on the traffic source behavior
beyond the DLB characterization. However, to generate the simulated
traffic, we have to load the DLBs with specific sources. Our simulator
has been developed in ns (network simulator, developed at ISI,
University of Southern California), which allows using several traffic
models (including recorded traces). For the sake of simplicity, here we
present results relevant to on-off exponential voice sources. However,
we performed other experiments by loading the DLBs with, e.g., MPEG,
H.263 (video) and G.7xx (audio) traces. The sources used in the
following have On and Off state durations with average values of 352 ms
and 650 ms, respectively. The bit rate during the On period is equal to
8 Kbytes/s. The sources are regulated by DLBs with parameters: Peak
rate= 8 Kbytes/s; Sustainable rate= 3.4 Kbytes/s; Token Bucket Size=
10600 bytes. The packet size is 106 bytes.
In [18] we report graphically the performance experienced by different
sets of users in a specific network scenario. Members that joined the
multicast tree in QoS mode experience differentiated performance, and
lose no packet in our simulation runs, at the expense of BE members. As
regards delay, we showed in [18] that by increasing without bound the BE
load, queuing delay increases up to queue saturation, while our scheme
protects users who requested QoS, by keeping the relevant mean delay
constant and under 1 ms, for whatever value of the BE traffic load.
(zero loss and 1ms of delay were the pre-tuned performance figures to be
guaranteed to QoS traffic by our scheme).
A more complex simulation scenario, devised to analyze the interaction
between QoS and BE flows, is plotted in Fig. 3. Here we load the system
with 100 QoS multicast sources (the same On-Off ones described above);
their destinations are located in hosts attached to DR1, DR2, DR3 and
DR4. Background unicast BE traffic is added over links L1 and L2, to
create bottlenecks (L1 has an offered load of 120% and L2 of 101%).
We run three different experiments. In the first one, only users
attached to DR1 request QoS, while all other users are in BE mode. In
the second and third experiment QoS is requested only by users attached
to DR2 and DR3, respectively.
The aim of this scenario is to show that when some members of a
multicast group require QoS, they indirectly bring benefits also to BE
users belonging to the same multicast group and sharing part of the
distribution tree. This is shown in Tab. 1.
For instance, users attached to DR1 experience zero loss and minimum
delay in all experiments, even if they actually request QoS only in
experiment 1. Users attached to DR4, who never requested QoS, experience
better performances when users in QoS mode get closer. We note that this
effect could be an advantage from the network efficiency point of view.
Bianchi&Blefari Informational - Expires June 2003 [Page 14]
Quality of Service Aware Multicasting over DiffServ December 2002
+-----+ +-----+
100 QoS sources -> | SQ1 |..|SQ100|
+-----+ +-----+
\\ //
\\ //
+---+
|RP |
+---+
|| 20 Mbps
+---+
| A |=======\
** +---+ \\
L1, 100 BE unicast * || +---+ Host attached here
background traffic * || |DR1| request QoS only in
<** +---+ +---+ Experiment 1
| B |=======\
** +---+ \\
L2, 65 BE unicast * || +---+ Host attached here
background traffic * || |DR2| request QoS only in
<** +---+ +---+ Experiment 2
| C |
+---+
// \\
// \\
Host attached here +---+ +---+ Hosts attached
request QoS only in |DR3| |DR4| here request
Experiment 3 +---+ +---+ always BE
Fig. 3 û Simulator topology
However, from a commercial point of view, this might ultimately be a
concern: best effort users experiencing excellent performance (because
of their closeness to QoS users) might be unwilling to pay in order to
upgrade the multicast service to QoS-mode. The Limited Effort (LE) PHB
proposed in [7], could be applied to mitigate this problem.
Ploss Experim. 1 Experim. 2 Experim. 3
DR1 0.00% 0.00% 0.00%
DR2 17.49% 0.00% 0.00%
DR3 17.49% 2.39% 0.00%
DR4 17.49% 2.39% 0.00%
Mean delay Experim. 1 Experim. 2 Experim. 3
DR1 0.2 0.2 0.2
DR2 413.3 0.3 0.3
DR3 414.6 374.8 0.3
DR4 414.6 374.8 0.3
Tab. 1û Loss (percentage) and delay (in ms), scenario B
Bianchi&Blefari Informational - Expires June 2003 [Page 15]
Quality of Service Aware Multicasting over DiffServ December 2002
7 Conclusions
In this document, we have proposed a QoS multicast solution for DiffServ
domains. Our solution is built on top of existing multicast protocols
(PIM) and allows support for both best-effort and QoS users as well as
upgrading a BE user to a QoS one.
Additional research activities, not presented here because of space
limitations, include issues such as the simultaneous and flexible
handling of both source-based and core-based multicast trees. Since PIM
allows to dynamically change from the latter to the former during a
multicast session, our solution supports this feature via suitably
upgraded state machines and procedures; this material is available on
request [18]. In addition, we defined in details state machines,
procedure and message formats of our solution, taking PIM as the
reference protocol. On the other hand, we remark that our solution could
be deployed starting also from other existing multicast models, such as
Core Based Tree (CBT) and Source Specific Multicast (SSM).
A number of possible issues deserving future research include:
- extension to the support of multiple QoS levels, especially those
appearing when different PHBs are simultaneously operating on the
same link; a possible solution to this issue is addressed in [9];
- support of the so-called Limited Effort (LE) PHB, proposed in [7]
to protect already existing traffic (including BE) from new users
joining the multicast tree.
- end-to-end, inter-domain issues: this document is essentially
limited to intra-domain issues, even if the unicast GRIP
definition does take into account inter-domain operation and some
inter-domain issues are addressed in [8];
- fault tolerance: unicast GRIP faults are discussed in [13], PIM
faults are taken into account in the protocol specification, but
we still have to address faults deriving from the combination of
these two techniques;
8 Appendix: Security considerations
As all admission control functions, our solution presents the risk of
theft of resources through the unauthorized admission of traffic.
Although, logically, user terminals are the natural nodes where the
endpoint admission control should operate, this is not always realistic,
for the obvious reason that the user may bypass the admission control
test and directly send probe packets. Identity authentication and
integrity protection are therefore needed in order to mitigate this
potential for theft of resources [see RFC2990]. Administrators are then
expected to protect network resources by configuring secure policers at
interfaces (e.g., access routers) with untrusted customers. Similar
protections must be provided at the interface between different domains.
In particular, it may be necessary to restrict the access to the DS
Bianchi&Blefari Informational - Expires June 2003 [Page 16]
Quality of Service Aware Multicasting over DiffServ December 2002
class(es) used for admission controlled traffic. For example, a DS
domain should re-mark packets when they come from an un-trusted adjacent
DS domain. In more generality, we remark that policing and conditioning
rules enforced at the border routers of each domain depend on the usage
of the considered class within the specific domain and thus have to be
accounted of in the definition of each specific PDB supporting admission
control.
A quite obvious security hazard is flooding the network with probe
packets. The objective is twofold. On one side, denial of service
situations can be easily created, as a massive loading of the network
with probe packets prevent the setup of normal connection. On the other
side, the goal might be to affect fairness: the continuous transmission
of probe packets at a rate higher than normal connection requests is a
mean to gain faster access to resources when these are made available by
a router along the path. This implies that some form of traffic
conditioning and policing is necessary over probe streams. While it is
simple to recognize an hard attack, by monitoring the probe packets
crossing an edge router (the probe traffic û at most a few packets per
originating connection - is minimal in normal conditions, and thus
sudden increments of the probe load are suspicious), it may be not
straightforward for DS boundary routers to recognize smoother fairness
attacks. However, note that the same fairness problem is present also in
more complex reservation mechanisms, such as RSVP (malicious users can
continuously require setup to increase their access possibility with
respect to normal users).
Finally, all the security considerations expressed in [RFC2990] and in
multicasting related RFCs apply also to our solution.
9 References
[1] Striegel, G. Manimaran: "A survey of QoS multicasting issues",
IEEE Communications, pp. 82-87, June 2002.
[2] S. Chen, K. Nahrstedt, Y. Shavitt: "A QoS-aware multicast
routing protocol", IEEE JSAC, Vol. 18, No. 12, Dec. 2000.
[3] Y. Shuqian Yan, M. Faloutsos, A. Banerjea: "QoS-aware multicast
routing for the Internet: the design and evaluation of QoSMIC",
IEEE/ACM Transactions on Networking, Vol. 10, No. 1, pp. 54-66,
Feb. 2002.
[4] V. Firoiu, D. Towsley: "Call admission and resource reservation
for multicast sessions", IEEE INFOCOM 1996, pp. 94-101.
[5] R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin: "Resource
ReSerVation Protocol (RSVP) - Version 1 Functional
Specification", RFC 2205, Sep. 1997.
[6] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, W. Weiss:
"An Architecture for Differentiated Services", RFC 2475, Dec.
1998.
[7] R. Bless, K. Wehrle: "IP Multicast in Differentiated Services
Networks", Internet Draft, draft-bless-diffserv-multicast-
03.txt, March 2002, work in progress.
Bianchi&Blefari Informational - Expires June 2003 [Page 17]
Quality of Service Aware Multicasting over DiffServ December 2002
[8] Striegel, G. Manimaran: "A Scalable Protocol for Member
Join/Leave in DiffServ Multicast", in Proc. of Local Computer
Networks (LCN) 2001, Tampa, Florida, Nov. 2001.
[9] Yang, P. Mohapatra: "Multicasting in Differentiated Service
Domains", IEEE Globecom 2002.
[10] Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M.
Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei: "Protocol
Independent Multicast-Sparse Mode (PIM-SM): Protocol
Specification", RFC 2362, June 1998.
[11] Fenner, M. Handley, H. Holbrook, I. Kouvelas: "Protocol
Independent Multicast - Sparse Mode (PIM-SM) Protocol
Specification (Revised)", draft-ietf-pim-sm-v2-new-05.txt,
Internet-Draft, work in progress, March 2002.
[12] G. Bianchi, N. Blefari-Melazzi: "Admission Control over Assured
Forwarding PHBs: a Way to Provide Service Accuracy in a DiffServ
Framework", IEEE Globecom 2001, San Antonio, Texas, USA, 25-29
November 2001.
[13] G. Bianchi, N. Blefari-Melazzi, M. Femminella: "Per-flow QoS
Support over a Stateless DiffServ Domain", Computer Networks,
Elsevier, special issue on "Towards a New Internet
Architecture", Vol. 40, Issue 1, September 2002, pp. 73 û 87.
[14] J. Heinanen, T. Finland, F. Baker, W. Weiss, J. Wroclawski:
"Assured Forwarding PHB Group", IETF, RFC 2597, June 1999.
[15] G. Bianchi, N. Blefari-Melazzi, M. Femminella, F. Pugini:
"Performance Evaluation of a Measurement-Based Algorithm for
Distributed Admission Control in a DiffServ Framework", IWDC
2001, 17-20 September, 2001, Taormina, Italy (in Lecture Notes
in Computer Science, Springer-Verlag, Sergio Palazzo, Ed.).
[16] L. Breslau, S. Jamin, S. Schenker: "Comments on the performance
of measurement-based admission control algorithms", IEEE Infocom
2000, Tel-Aviv, March 2000.
[17] L. Breslau, E. W. Knightly, S. Schenker, I. Stoica, H. Zhang:
"Endpoint Admission Control: Architectural Issues and
Performance", ACM SIGCOMM 2000, Stockholm, Sweden, August 2000.
[18] G. Bianchi, N. Blefari-Melazzi, G. Bonafede, E. Tintinelli:
"QUASIMODO: QUAlity of ServIce-aware Multicasting Over DiffServ
and Overlay networks", to appear on IEEE Network, special issue
on "Multicasting: An Enabling Technology", January/February
2003. Available on request.
10 Author's Addresses
Giuseppe Bianchi
DIE, University of Palermo
Viale delle Scienze, Parco d'Orleans
90128 Palermo, ITALY
Tel: +39 091 6566 276
E-mail: bianchi@elet.polimi.it
Nicola Blefari-Melazzi
DIE, University of Roma, Tor Vergata
Bianchi&Blefari Informational - Expires June 2003 [Page 18]
Quality of Service Aware Multicasting over DiffServ December 2002
Via del Politecnico, 1
00133 - Roma, ITALY
Tel: +39 06 7259 7501
e-mail: blefari@uniroma2.it
Giuliano Bonafede
Infocom Dpt, University of Roma, La Sapienza
Via Eudossiana, 18
00184 - Roma, ITALY
Emiliano Tintinelli
Infocom Dpt, University of Roma, La Sapienza
Via Eudossiana, 18
00184 - Roma, ITALY
11 Full Copyright Statement
"Copyright (C) The Internet Society (date). All Rights Reserved. This
document and translations of it may be copied and furnished to others,
and derivative works that comment on or otherwise explain it or assist
in its implementation may be prepared, copied, published and
distributed, in whole or in part, without restriction of any kind,
provided that the above copyright notice and this paragraph are included
on all such copies and derivative works. However, this document itself
may not be modified in any way, such as by removing the copyright notice
or references to the Internet Society or other Internet organizations,
except as needed for the purpose of developing Internet standards in
which case the procedures for copyrights defined in the Internet
Standards process must be followed, or as required to translate it into
languages other than English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assignees.
This document and the information contained herein is provided on an "AS
IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK
FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT
LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT
INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR
FITNESS FOR A PARTICULAR PURPOSE.
Bianchi&Blefari Informational - Expires June 2003 [Page 19]
