INTERNET-DRAFT Roland Bless
Expires: September 2002 Klaus Wehrle
Internet Draft Universitaet Karlsruhe (TH)
March 2002
Document: draft-bless-diffserv-multicast-03.txt
IP Multicast in Differentiated Services Networks
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.
Distribution of this document is unlimited.
Abstract
This document presents some of the problems which will arise when IP
Multicast is used in DiffServ networks without taking special
provisions into account for supplying multicast services. Although
the basic DS forwarding mechanisms also work with IP Multicast, some
facts have to be considered which are related to the provisioning of
multicast resources. The presented problems mainly lead to
situations in which other service users are affected adversely in
their experienced quality.
Bless & Wehrle Expires: September 2002 [Page 1]
Table of Contents
1 Introduction..................................................2
1.1 Management of Differentiated Services.........................3
2 Problems of IP Multicast in DS Domains........................4
2.1 Neglected Reservation Subtree Problem (NRS Problem)...........4
2.2 Heterogeneous Multicast Groups...............................11
2.3 Dynamics of Arbitrary Sender Change..........................12
3 Solutions for Enabling IP-Multicast in Differentiated Services
Networks.....................................................12
4 Security Considerations......................................12
5 References...................................................13
6 Acknowledgements.............................................14
7 Authors' Addresses...........................................14
A Proof of the Neglected Reservation Subtree Problem...........15
A.1 Test Environment and Execution...............................15
B Simulative Study of the NRS Problem..........................17
B.1 Simulation Scenario..........................................17
B.2 Simulation Results for different router types................18
1 Introduction
Services in the Internet offering a better quality than the current
best-effort service are increasingly required. Many advanced
applications need certain assurances from the network layer, e.g., a
maximum delay, a minimum packet loss rate or guaranteed transmission
rate. The currently used IP mechanisms are not able to offer such
guarantees, especially, if group communication is additionally
required.
The "Differentiated Services" (DiffServ or DS) approach [1, 2, 3]
defines certain building blocks and mechanisms to offer
qualitatively better services than the usual "normal" best-effort
delivery service in an IP network. In the DiffServ Architecture [2]
scalability is achieved by avoiding complexity and maintenance of
per-flow state information in core nodes and by pushing unavoidable
complexity to the network edges. Therefore, individual flows
belonging to the same service are aggregated, thereby eliminating
the need for complex classification or managing state information
per flow in interior nodes.
Bless & Wehrle Expires: September 2002 [Page 2]
On the other hand, the reduced complexity in DS nodes makes it more
complex to use those "better" services together with IP Multicast
(i.e., point-to-multipoint or multipoint-to-multipoint
communication). Problems emerging from this fact are described in
section 2. Although the basic DS forwarding mechanisms also work
with IP Multicast, some facts have to be considered which are
related to the provisioning of multicast resources. However, it is
important to integrate IP Multicast functionality right from the
beginning into the architecture, and, to provide simple solutions
for those problems not defeating the gained advantages so far.
The EF PHB [9] shows also very interesting properties within a
multicast context. The very low packet loss characteristic makes it
suitable as a basis for a highly (but not absolute) reliable
multicast service. Packet loss cannot be fully precluded, because of
aggregation effects which may nevertheless lead to packet losses.
However, in reality packet losses should occur so infrequently that
many applications can tolerate these losses, or if this is not the
case, that at least very simple retransmission schemes can be
applied.
1.1 Management of Differentiated Services
At least for Per-Domain Behaviors [3] and services based on the EF
PHB admission control and resource reservation are required.
Furthermore, installation and updating of traffic profiles in
boundary nodes is necessary. Most network administrators will not
accomplish this task manually, even for long term service level
agreements (SLAs). Furthermore, offering services on demand requires
some kind of signaling and automatic admission control procedures.
Therefore, the concept of Bandwidth Brokers was already suggested by
Van Jacobson at a very early stage of DiffServ research [4]. In this
concept, the Bandwidth Broker (BB) is a dedicated node in each DS
domain, which keeps track of the amount of available and reserved
bandwidth for services, and, which processes admission control
requests from customers or BBs of adjacent domains. Additionally, it
installs or alters traffic profiles in boundary nodes.
Protocols for signaling a reservation request to a Differentiated
Services Domain are required. For accomplishing end-system signaling
to DS domains RSVP [5] may be used with new DS specific reservation
objects. RSVP is mainly designed for use in multicast scenarios and
is already supported by many operating systems. However, when
applying RSVP to a DiffServ network some problems will arise which
are described in the next section.
Bless & Wehrle Expires: September 2002 [Page 3]
2 Problems of IP Multicast in DS Domains
Although potential problems and the complexity of providing
multicast with Differentiated Services are considered in a separate
section of [2], both aspects have to be discussed in greater detail.
The simplicity of the DiffServ Architecture and its router models is
necessary to reach high scalability, but it causes also fundamental
problems in conjunction with the use of IP Multicast in DS domains.
Because Differentiated Services are unidirectional by definition, we
also consider the point-to-multipoint communication being of
unidirectional nature. In traditional IP Multicast any node can send
packets spontaneously and asynchronously to a multicast group,
respectively to their multicast group address (therefore,
traditional IP Multicast offers a multipoint-to-multipoint service).
This feature is discussed in section 2.3.
For subsequent considerations we assume, unless stated otherwise, at
least a unidirectional point-to-multipoint communication scenario in
which the sender generates packets which experience a "better" Per-
Hop Behavior than the traditional default PHB, resulting in a
service of better quality compared to the default best-effort
service. In order to accomplish this, a traffic profile
corresponding to the traffic conditioning specification has to be
installed in the sender's first-hop router (the first boundary node
of the first DS domain receiving those packets). Furthermore, it
must be assured that the corresponding resources are available on
the path from the sender to all the receivers, possibly requiring
adaptation of traffic profiles at involved domain boundaries. Note
that the latter process may also be initiated on demand of a
receiver.
2.1 Neglected Reservation Subtree Problem (NRS Problem)
Typically, resources for Differentiated Services must be reserved
before actually using them. But in a multicast scenario group
membership is often highly dynamic, therefore limiting the use of a
sender-initiated resource reservation in advance. Unfortunately,
dynamic addition of new members of the multicast group using
Differentiated Services can adversely affect existing other traffic,
if resources were not explicitly reserved before use. A practical
prove of this problem is given in appendix A.3.
IP Multicast packet replication usually takes place when the packet
is handled by the "routing" core (cf. Fig. 1), i.e., when it is
forwarded according to the routing table. Thus, a DiffServ capable
node would also copy the content of the DS field [1] into the IP
packet header of every replicate. Consequently, replicated packets
get exactly the same DS codepoint (DSCP) as the original packet,
and, therefore experience the same forwarding treatment as the
incoming packets of this multicast group (see Fig. 1, in this case
Bless & Wehrle Expires: September 2002 [Page 4]
the egress interface comprises functions for (BA-) classification,
traffic conditioning and queueing).
Interface A IP-Routing Interface C
+-----------+ +--------------+ +-----------+
MC-flow | | | replication | | egress |
---->| ingress |---->|------+-------|----->|(class.,TC,|---->
| | | | | | queueing) |
+-----------+ | | | +-----------+
| | |
Interface B | | | Interface D
+-----------+ | | | +-----------+
| | | | | | egress |
| ingress | | +-------|----->|(class.,TC,|---->
| | | | | queueing) |
+-----------+ +--------------+ +-----------+
Figure 1: Multicast packet replication in a DS router
Normally, the replicating node cannot test whether a corresponding
reservation exists for a particular flow of replicated packets on an
output link (resp. its corresponding interface), because a flow-
specific traffic profile is usually not available in boundary
(except in first-hop nodes) and interior nodes.
When a new receiver joins an IP Multicast group, the corresponding
multicast routing protocol (e.g., DVMRP [6], PIM-DM [7] or PIM-SM
[8]) accomplishes that the multicast tree is expanded by a new
subtree which connects the new receiver to the already existing
multicast tree. As a result of tree expansion and missing per-flow
classification and policing mechanisms, the new receiver will
implicitly use the service of better quality, because of the copied
"better" DSCP.
If the additional amount of resources which are consumed by the new
part of the multicast tree are not taken into account by the domain
management (cf. section 1.1), the currently provided level of
quality of service of other receivers (with correct reservations)
will be affected adversely or even violated. This negative effect on
existing traffic contracts by a neglected resource reservation -- in
the following designated as Neglected Reservation Subtree Problem
(NRS Problem) -- must be avoided under any circumstances.
One can distinguish two distinct major cases of the NRS Problem. In
order to compare their different effects a simple example of a share
of bandwidth is illustrated in Fig. 2.
Bless & Wehrle Expires: September 2002 [Page 5]
40% 40% 20%
+--------------------+---------------------+------------+
|Expedited Forwarding| Assured Forwarding | Best-Effort|
+--------------------+---------------------+------------+
---------------------------------------------------------->
output link bandwidth
Figure 2: An example bandwidth share of different
behavior aggregates
Three types of services (respectively their corresponding behavior
aggregates) share the bandwidth of the considered output link:
Expedited Forwarding [9], Assured Forwarding [10] and the
traditional Best-Effort service. In this example we assume that
routers perform simple priority queueing, where EF has the highest
and Best-Effort the lowest assigned priority. When Weighted Fair
Queueing (WFQ) would be used, the described effects would
essentially also occur, only with minor differences.
The Neglected Reservation Subtree problem appears in two different
cases:
o Case 1: If the branching point of the new subtree and the previous
multicast tree is an (egress) border router, as shown in Fig. 3,
the additional multicast flow now increases the amount of used
resources for the corresponding aggregate and will be greater than
the originally reserved amount on the affected output link.
Consequently, the policing component in the egress border router
drops packets until the traffic aggregate is in accordance to the
traffic contract. But during dropping packets, the router can not
identify the responsible flow (because of missing flow
classification functionality), and, thus randomly discards
packets, whether they belong to a correctly reserved flow or not.
As a result, there will be no longer any service guarantee for the
reserved flows.
Bless & Wehrle Expires: September 2002 [Page 6]
Sender
+---+
| S | DS domains .......
+---+ ..... / \ . ..
|| . . .. / \ .. .
..||.. .... .<- ->... ..
. || . . .
. +---+ +--+ +--+ *) +--+ +--+ +--+ +------+
. |FHN|===|IN|=====|BN|###########|BN|####|IN|######|BN|####|Recv.B|
. +---+ +--+ +--+\\ +--+ +--+ +--+ +------+
. \\ \ . \\ . \ .
. +--+ +--+ . \\ . \ .
. |IN|-----|IN| . \\ .. +--+ .
. +--+ +--+ . \\ ... ....|BN|..
. || \ ... +------+ ... +--+
. || \ . |Recv.A|
.+--+ ...+--+ +------+
|BN|..... |BN|
+--+ +--+
||
FHN: First-Hop Node S: Sender
BN: Boundary Node Recv.x: Receiver x
IN: Interior Node
===: Multicast branch with reserved bandwidth
###: Multicast branch without reservation
*) Bandwidth of EF aggregated on the output link is higher than
actual reservation, EF aggregate will be limited in bandwidth
without considering the responsible flow.
Figure 3: The NRS Problem (case 1)
Bless & Wehrle Expires: September 2002 [Page 7]
+------------------+---------------------+--------------+------+
| Expedited Forw. | Expedited Forw. | Assured Forw.| BE |
| | | | |
| with reservation | excess flow | with reserv. | |
| | without reservation | | |
+------------------+---------------------+--------------+------+
| | | |
| EF with and without reservation share | 40 % | 20% |
| 40% of reserved EF aggregate. | | |
| -> EF packets with reservation and | | |
| without reservation will be | | |
| discarded! | | |
| | | |
+------------------+---------------------+--------------+------+
(a) Excess flow has EF codepoint
+------------------+---------------------+--------------+------+
| Expedited Forw. | Assured Forwarding | Assured Forw.| BE |
| | | | |
| with reservation | excess flow | with reserv. | |
| | without reservation | | |
+------------------+---------------------+--------------+------+
| | | |
| | AF with & without reservation share| 20 % |
| | 40% of reserved EF aggregate. | |
| 40% | -> EF packets with reservation and | |
| | without reservation will be | |
| | discarded! | |
| | | |
+------------------+---------------------+--------------+------+
(b) Excess flow has AF codepoint
Figure 4: Resulting share of bandwidth in a egress
border router with a neglected reservation of
(a) an Expedited Forwarding flow or (b) an
Assured Forwarding flow.
Fig. 4 shows the resulting share of bandwidth in cases when (a)
Expedited Forwarding and (b) Assured Forwarding is used by the
additional multicast branch causing the NRS Problem. Assuming that
the additional traffic would use another 30% of the link
bandwidth, Fig. 4 (a) illustrates that the resulting aggregate of
Expedited Forwarding (70% of the outgoing link bandwidth) is
throttled down to its originally reserved 40%. In this case, the
amount of dropped EF bandwidth is equal to the amount of excess
bandwidth. Consequently the original Expedited Forwarding
aggregate (which had 40% of the link bandwidth reserved) is
affected by packet losses, too. The other services, e.g., Assured
Forwarding or Best-Effort, are not disadvantaged.
Bless & Wehrle Expires: September 2002 [Page 8]
Fig. 4 (b) shows the same situation for Assured Forwarding. The
only difference is that now Assured Forwarding is solely affected
by discards, the other services will still get their guarantees.
In either case, packet losses are restricted to the misbehaving
service class by the traffic meter and policing mechanisms in
boundary routers. Moreover, the latter problem (case 1) occurs
only in egress border routers, because they are responsible, that
not more traffic is leaving the Differentiated Services domain,
than the following ingress border router will accept. Therefore,
those violations of SLAs will be already detected and processed in
egress border routers.
Sender
+---+
| S | DS domains .......
+---+ ..... / \ . ..
|| . . .. / \ .. .
..||.. .... .<- ->... ..
. || . . .
. +---+ +--+ +--+ +--+ +--+ +--+ +-------+
. |FHN|===|IN|=====|BN|===========|BN|====|IN|======|BN|===| Recv.B|
. +---+ +--+ +--+\\ +--+ +--+ +--+ +-------+
. \\ \ . \\ . # .
. +--+ +--+ . \\ . # *) .
. |IN|-----|IN| . \\ .. +--+ .
. +--+ +--+ . \\ ... ....|BN|..
. || \ ... +------+ ... +--+
. || \ . |Recv.A| #
.+--+ ...+--+ +------+ #
|BN|..... |BN| +------+
+--+ +--+ |Recv.C|
|| +------+
FHN: First-Hop Node
S: Sender BN: Boundary Node
Recv.x: Receiver x IN: Interior Node
===: Multicast branch with reserved bandwidth
###: Multicast branch without reservation
*) Bandwidth of EF aggregated on the output link is higher than
actual reservation, EF aggregate will be limited in bandwidth
without considering the responsible flow
Figure 5: Neglected Reservation Subtree problem case 2
after join of receiver C
o Case 2: The Neglected Reservation Subtree problem can also occur,
if the branching point between the previous multicast tree and the
new subtree is located in an interior router (as shown in Fig. 5).
Because the router is not equipped with metering or policing
functions it will not recognize any amount of excess traffic and
will forward the new multicast flow. If the latter belongs to a
Bless & Wehrle Expires: September 2002 [Page 9]
higher priority service, such as Expedited Forwarding, bandwidth
of the aggregate is higher than the aggregate's reservation and
will steal bandwidth from lower priority services.
The additional amount of EF without a corresponding reservation is
forwarded together with the aggregate which has a reservation.
This results in no packets losses for Expedited Forwarding as long
as the resulting aggregate is not higher than the output link
bandwidth. Because of its higher priority, Expedited Forwarding
gets as much bandwidth as needed and as is available (strictly
speaking, it is implementation dependent whether interior routers
have something like a maximum configured service rate).
+------------------+---------------------+--------------+------+
| Expedited Forw. | Expedited Forw. | Assured Forw.| BE |
| | | | |
| with reservation | excess flow | with reserv. | |
| | without reservation | | |
+------------------+---------------------+--------------+------+
| | | | |
| 40% | 30% | 30% | 0% |
| | | | |
+------------------+---------------------+--------------+------+
EF with reservation and the excess flow use together 70%
of the link bandwidth, because EF (with or without reservation
has the highest priority.
(a) Excess flow has EF codepoint
+------------------+---------------------+--------------+------+
| Expedited Forw. | Assured Forw. | Assured Forw.| BE |
| | | | |
| with reservation | excess flow | with reserv. | |
| | without reservation | | |
+------------------+---------------------+--------------+------+
| | | |
| 40% | 60% | 0% |
| | | |
| | 10% loss | |
| | | |
+------------------+---------------------+--------------+------+
AF with reservation and the excess flow use together 60%
of the link bandwidth, because EF has the highest priority
(-> 40%). 10% of AF packets will be lost.
(b) Excess flow has AF codepoint
Figure 6: Resulting share of bandwidth in an interior
router with a neglected reservation of (a) a
Expedited Forwarding flow or (b) an Assured
Forwarding flow
Bless & Wehrle Expires: September 2002 [Page 10]
The result is, that there is no restriction for Expedited
Forwarding, but as Fig. 6 (a) shows, other services will be
extremely disadvantaged by this use of non-reserved resources.
Their bandwidth is stolen by the new additional flow. In this
case, the additional 30% Expedited Forwarding traffic preempts
resources from the Assured Forwarding traffic, which in turn
preempts resources from the best-effort traffic, resulting in 10%
packet losses for the Assured Forwarding aggregate and complete
loss of best-effort traffic. The example in Fig. 6 (b) shows that
this can also happen with lower priority services like Assured
Forwarding. When a reservation for a service flow with lower
priority is neglected, other services (with even lower priority)
can be reduced in their quality (in this case the best-effort
service). As shown in the example, the service's aggregate causing
the problem can itself be affected by packet losses (10% of the
Assured Forwarding aggregate is discarded). Besides the described
problems of case 2, case 1 will arise in the next border router,
that performs traffic metering and policing for flows of the
service aggregate.
Directly applying RSVP to Differentiated Services would also result
in an NRS Problem, because a receiver has to join the IP multicast
group BEFORE sending a resource reservation request (RESV message),
in order to receive the sender's PATH messages at first. Thus, the
join for receiving PATH messages will already cause an NRS Problem
if this situation is not handled in a special way (e.g., by marking
all PATH messages with codepoint 0).
2.2 Heterogeneous Multicast Groups
Heterogeneous multicast groups contain one or more receivers, which
would like to get another service or quality of service as the
sender provides or other receiver subsets currently use. A very
important characteristic which should be supported by Differentiated
Services is that participants requesting a best-effort quality only
should also be able to participate in a group communication which
otherwise utilizes a better service class. The next better support
for heterogeneity provides concurrent use of more than two different
service classes within a group. Things tend to get even more complex
when not only different service classes are required, but also
different values for quality parameters within a certain service
class.
A further problem is to support heterogeneous groups with different
service classes in a consistent way. It is possible that some
services will not be comparable to each other so that one service
cannot be replaced by the other and both services have to be
provided over the same link within this group.
Because an arbitrary new receiver that wants to get the different
service can be grafted to any point of the current multicast
Bless & Wehrle Expires: September 2002 [Page 11]
delivery tree, even interior routers may have to replicate packets
with the different service. At a first glance, this seems to be a
contradiction with respect to simplicity of the interior routers,
because they do not even have any profile available and should now
convert the service quality of individual receivers. Consequently,
in order to accomplish this, interior routers have to change the
codepoint value during packet replication.
2.3 Dynamics of Arbitrary Sender Change
Basically, within an IP multicast group any participant (actually,
it can be any host not even receiving packets of this multicast
group) can act as a sender. This is an important feature which
should also be available in case a specific service other than best-
effort is used within the group. Differentiated Services possess
conceptually a unidirectional character. Therefore, for every
multicast tree implied by a sender resources must be reserved
separately if simultaneous sending should be possible with a better
service. This is even true if shared multicast delivery trees are
used (e.g., with PIM-SM or Core Based Trees). If not enough
resources are reserved for a service within a multicast tree
allowing simultaneous sending of more than one participant, the NRS
problem will occur again. The same argument applies to half-duplex
traffic which would share the reserved resources by several senders,
because it cannot be ensured by the network that exactly one sender
sends packets to the group. Accordingly, the corresponding RSVP
reservation styles "Wildcard Filter" and "Shared-Explicit Filter"
[5] cannot be supported within Differentiated Services. The IntServ
approach is able to ensure the half-duplex nature of the traffic,
because every router can check each packet for conformance with the
installed reservation state.
3 Requirements to Enable Provisioning of IP-Multicast in
Differentiated Services Networks
The problems described in the previous section are mainly caused by
the simplicity of the Differentiated Services Architecture.
Solutions have to be developed which do not introduce an additional
amount of complexity which diminishes the scalability of the
DiffServ approach. An example for such a solution is given in [12],
although many other approaches may be possible and feasible.
4 Security Considerations
Basically, the security considerations in [1,2] apply. If it is not
desired that arbitrary end-systems can join a multicast group
anytime the application has usually to preclude these participants
by using authentication, authorization or ciphering techniques at
application level just as for traditional IP multicast scenarios.
Bless & Wehrle Expires: September 2002 [Page 12]
5 References
[1] F. Baker, D. Black, S. Blake, and K. Nichols. Definition of the
Differentiated Services Field (DS Field) in the IPv4 and IPv6
Headers. RFC 2474, Dec. 1998.
[2] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W.
Weiss. An Architecture for Differentiated Services. RFC 2475,
Dec. 1998.
[3] K. Nichols, B. Carpenter. Definition of Differentiated Services
Per Domain Behaviors and Rules for their Specification. RFC
3086, Apr. 2001.
[4] V. Jacobson, K. Nichols, and L. Zhang. A Two-bit Differentiated
Services Architecture for the Internet. RFC 2638, July 1999.
[5] R. Braden, S. Berson, S. Herzog, S. Jamin, and L. Zhang.
Resource ReSerVation Protocol (RSVP) -- Version 1. RFC 2205,
Sept. 1997.
[6] D. Waitzman, C. Partridge, and S. Deering. Distance Vector
Multicast Routing Protocol. RFC 1075, Nov. 1988.
[7] S. Deering, D. Estrin, D. Farinacci, V. Jacobson, A. Helmy, D.
Meyer, and L. Wei. Protocol independent multicast version 2
dense mode specification. Internet-Draft -- draft-ietf-pim-v2-
dm-03.txt, June 1999, work in progress.
[8] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M.
Handley, V. Jacobson, C. gung Liu, P. Sharma, and L. Wei.
Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
Specification. RFC 2362, June 1998.
[9] V. Jacobson, K. Nichols, and K. Poduri. An Expedited Forwarding
PHB. RFC 2598, June 1999.
[10] F. Baker, J. Heinanen, W. Weiss, and J. Wroclawski. Assured
Forwarding PHB Group. RFC 2597, June 1999.
[11] R. Bless, K. Wehrle: "Evaluation of Differentiated Services
using an Implementation und Linux"; Proceedings of the Intern.
Workshop on Quality of Service (IWQOS'99), London, 1999
[12] R. Bless, K. Wehrle. Group Communication in Differentiated
Services Networks, Internet QoS for the Global Computing 2001
(IQ 2001), IEEE International Symposium on Cluster Computing
and the Grid), May 2001, Brisbane, Australia, IEEE Press
Bless & Wehrle Expires: September 2002 [Page 13]
[13] K. Wehrle, J. Reber, V. Kahmann. A simulation suite for
Internet nodes with the ability to integrate arbitrary Quality
of Service behavior, Proceedings of Communication Networks And
Distributed Systems Modeling And Simulation Conference (CNDS
2001), Phoenix (AZ), January 2001
6 Acknowledgements
The authors like to thank all the people from the Institute of
Telematics (University of Karlsruhe) and those from the DiffServ
community which contributed to the discussion of all the topics
related to this document.
Special thanks go to Milena Neumann for the extensive efforts in
performing the simulations. We would also like to thank the KIDS
simulation team [13].
7 Authors' Addresses
Comments and questions related to this document can be addressed to
one of the authors listed below.
Roland Bless
Institute of Telematics
Universitaet Karlsruhe (TH)
Zirkel 2
D-76128 Karlsruhe, Germany
Phone: +49 721 608 6413
Email: bless@tm.uka.de
Klaus Wehrle
Institute of Telematics
Universitaet Karlsruhe (TH)
Zirkel 2
D-76128 Karlsruhe, Germany
Phone: +49 721 608 6414
Email: wehrle@tm.uka.de
Bless & Wehrle Expires: September 2002 [Page 14]
Appendix
A Proof of the Neglected Reservation Subtree Problem
In the following, it is shown that the NRS problem actually exists
and occurs in reality. Hence, we investigated the problem and its
solution using a standard Linux Kernel (v2.3.49) and the Linux-based
implementation KIDS, which is described in an early version detailed
in [11].
Additional measurements with the simulation model simulatedKIDS [13]
will be presented in appendix B. They show the effects of the NRS
problem, too.
A.1 Test Environment and Execution
Sender
+---+ FHN: First Hop Node
| S | BN: Border Node
+---+
+#
+#
+#
+---+ +--+ +------+
|FHN|++++++++++++|BN|+++++++++++| host |
| |############| |***********| B |
+---+ +--+## +------+
+# #
+# #
+# #
+------+ +------+
|host A| |host C|
+------+ +------+
+++ EF flow (group1) with reservation
### EF flow (group2) with reservation
*** EF flow (group2) without reservation
Figure A.1: Evaluation of NRS-Problem described in
Figure 3
In order to prove NRS problem case 1, as described in section 2.1, a
testbed shown in Figure A.1 was built. It is a reduced version of
the network shown in Figure 5 and consists of two DS-capable
routers, a first-hop router and an egress border router. The absence
of interior routers does not have any effects on to the proof of the
described problem.
Bless & Wehrle Expires: September 2002 [Page 15]
The testbed comprises of two Personal Computers (Pentium III at 450
Mhz, 128 MB Ram, 3 network cards Intel eepro100) used as DiffServ
routers, as well as one sender and three receiver systems (also
PCs). KIDS has been installed on the routers and an mrouted
(Multicast Routing Daemon) was used to perform multicast routing.
The network was completely built of separate 10BaseT Ethernet
segments in full-duplex mode. In [13] we evaluated the performance
of the software routers and found out that even a PC at 200Mhz had
no problem to handle up to 10Mbps DS traffic on each link.
Therefore, the presented measurements are not a result of
performance bottlenecks caused by these software routers.
The sender generated two shaped UDP traffic flows of 500kbps
(packets of 1.000 byte constant size) each and sends them to
multicast group 1 (233.1.1.1) and 2 (233.2.2.2). In both
measurements receiver A had a reservation along the path to the
sender for each flow, receiver B has reserved for flow 1 and C for
flow 2. Therefore, two static profiles are installed in the first-
hop router with 500kbps EF bandwidth and a token bucket size of
10.000byte for each flow.
In the egress border router one profile has been installed for the
output link to host B and one related for the output link to host C.
Each of them permits up to 500kbps Expedited Forwarding, but only
the aggregate of Expedited Forwarding traffic carried on the
outgoing link is considered.
In the measurement scenario of Figure A.2 hosts A and B joined to
group 1 and A, B and C joined to group 2. Those joins are using a
reservation for the group towards the sender. Only the join of host
B to group 2 has no admitted reservation. As described in section
2.1 this will cause the NRS problem (case 1). Metering and policing
mechanisms in the egress border router throttle down the EF
aggregate to the reserved 500kbps, no depending on whether
individual flows have reserved or not.
+--------+--------+--------+
| Host A | Host B | Host C |
+---------+--------+--------+--------+
| Group 1 | 500kbps| 250kbps| 500kbps|
+---------+--------+--------+--------+
| Group 2 | 500kbps| 250kbps| |
+---------+--------+--------+--------+
Figure A.2: Average bandwidth of each flow.
--> Flows of group 1 and 2 on the link to
host B share the reserved aggregate of
group 1.
Figure A.2 shows the obtained results. Host A and C received their
flows without any interference. But host B received data from group
1 only with half of the reserved bandwidth, so one half of the
Bless & Wehrle Expires: September 2002 [Page 16]
packets have been discarded. Figure A.2 also shows that receiver B
got the total amount of bandwidth for group 1 and 2, that is exactly
the reserved 500kbps. Flow 2 got Expedited Forwarding without
actually having reserved any bandwidth and additionally violated the
guarantee of group 1 on that link.
The above measurements confirm that the Neglected Reservation
Subtree problem is to be taken seriously in practice.
B Simulative Study of the NRS Problem
This section shows some results from a simulative study which shows
the described problems. A further proof of the NRS problem has also
been given in appendix A and in [12].
B.1 Simulation Scenario
In the following scenario Border Routers had a link speed of 10 Mpbs
and Interior Routers had a link speed of 12 Mbps. In Border Routers
a 5 Mbps aggregate for EF has been reserved.
The following topology was used, where Sx is a sender, BRx a Border
Router, IRx an Interior Router and Dx a destination/receiver.
+--+ +--+ +---+ +--+
|S1| |S0| /=|BR5|=====|D0|
+--+ +--+ // +---+ +--+
\\ || //
\\ || //
+--+ \+---+ +---+ +---+ +---+ +--+
|S2|===|BR1|=====|IR1|=====|IR2|======|BR3|=====|D1|
+--+ +---+ /+---+ +---+ +---+ +--+
// \\ +--+
// \\ /=|D2|
+--+ +---+ // \\ // +--+
|S3|===|BR2|=/ +---+/
+--+ +---+ /=|BR4|=\
|| +--+ // +---+ \\ +--+
+--+ |D4|=/ \=|D3|
|S4| +--+ +--+
+--+
Figure B.1: Simulation Topology
The following table shows the flows in the simulation runs, e.g.,
EF0 is sent from Sender S0 to Destination D0 with a rate of 4 Mbps
using an EF reservation.
In the presented cases (I to IV) different amounts of BE traffic
were used.
In all simulation models EF sources generated constant rate traffic
with constant packet sizes using UDP.
Bless & Wehrle Expires: September 2002 [Page 17]
The BE sources also generated constant rate traffic, where BE0 used
UDP and BE1 used TCP as transport protocol.
+----+--------+-------+----------+-----------+-----------+---------+
|Flow| Source | Dest. | Case I | Case II | Case III | Case IV |
+----+--------+-------+----------+-----------+-----------+---------+
| EF0| S0 | D0 | 4 Mbps | 4 Mbps | 4 Mbps | 4 Mbps |
+----+--------+-------+----------+-----------+-----------+---------+
| EF1| S1 | D1 | 2 Mbps | 2 Mbps | 2 Mbps | 2 Mbps |
+----+--------+-------+----------+-----------+-----------+---------+
| EF2| S2 | D2 | 5 Mbps | 5 Mbps | 5 Mbps | 5 Mbps |
+----+--------+-------+----------+-----------+-----------+---------+
| BE0| S3 | D3 | 1 Mbps | 2.25 Mbps | 0.75 Mbps |3.75 Mbps|
+----+--------+-------+----------+-----------+-----------+---------+
| BE1| S4 | D4 | 4 Mbps | 2.25 Mbps | 0.75 Mbps |3.75 Mbps|
+----+--------+-------+----------+-----------+-----------+---------+
Table B.1: Direction, amount and PHB of flows in the four
simulation cases (case I to IV)
The four cases (I to IV) used in the simulation runs had the
following characteristics:
Case I: In this scenario, the BE sources sent together exactly 5
Mbps so there is no congestion in the BE queue.
Case II: BE0 and BE1 are sending together 4.5 Mbps, so there is
residual bandwidth available.
Case III: In this case, BE0 and BE1 use together only 1.5 Mbps.
Case IV: BE0 and BE1 send together 7.5 Mbps so there is congestion
in the BE queue.
In each scenario loss rate and throughput of the considered flows
and aggregates have been metered.
B.2 Simulation Results for different router types
B.2.1 Interior Router
When the branching point of a newly added multicast subtree is
located in an Interior Router the NRS problem can occur as described
in section 2.1 (Case 2).
In the simulation runs presented in the following four subsections
D3 joins to the multicast group of sender S0 without making any
reservation or resource allocation. Consequently, a new subtree is
added to the existing multicast tree. The branching point issued by
Bless & Wehrle Expires: September 2002 [Page 18]
the join of D3 is located in IR2. On the link to BR3 no bandwidth
was allocated for the new flow (EF0).
The metered throughput of flows on the link between IR2 and BR3 in
the four different cases is shown in the following four subsections.
The situation before the new receiver joins is shown in the second
column. The situation after the join of D3 is shown in column three.
A.1.1.1 Case I:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 4.007 Mbps |
|achieved| EF1: 2.001 Mbps | EF1: 2.003 Mbps |
|through-| EF2: 5.002 Mbps | EF2: 5.009 Mbps |
|put | BE0: 1.000 Mbps | BE0: 0.601 Mbps |
| | BE1: 4.000 Mbps | BE1: 0.399 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 7.003 Mbps | EF: 11.019 Mbps |
|through-| BE: 5.000 Mbps | BE: 1.000 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 0 % |
|packet | EF1: 0 % | EF1: 0 % |
|loss | EF2: 0 % | EF2: 0 % |
|rate | BE0: 0 % | BE0: 34.8 % |
| | BE1: 0 % | BE1: 59.1 % |
+--------+-----------------+-----------------+
A.1.1.2 Case II:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 4.003 Mbps |
|achieved| EF1: 2.000 Mbps | EF1: 2.001 Mbps |
|through-| EF2: 5.002 Mbps | EF2: 5.005 Mbps |
|put | BE0: 2.248 Mbps | BE0: 0.941 Mbps |
| | BE1: 2.252 Mbps | BE1: 0.069 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 7.002 Mbps | EF: 11.009 Mbps |
|through-| BE: 4.500 Mbps | BE: 1.010 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 0 % |
|packet | EF1: 0 % | EF1: 0 % |
|loss | EF2: 0 % | EF2: 0 % |
|rate | BE0: 0 % | BE0: 58.0 % |
| | BE1: 0 % | BE1: 57.1 % |
+--------+-----------------+-----------------+
Bless & Wehrle Expires: September 2002 [Page 19]
A.1.1.3 Case III:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 3.998 Mbps |
|achieved| EF1: 2.000 Mbps | EF1: 2.001 Mbps |
|through-| EF2: 5.000 Mbps | EF2: 5.002 Mbps |
|put | BE0: 0.749 Mbps | BE0: 0.572 Mbps |
| | BE1: 0.749 Mbps | BE1: 0.429 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 7.000 Mbps | EF: 11.001 Mbps |
|through-| BE: 1.498 Mbps | BE: 1.001 Mbps |
|put | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 0 % |
|packet | EF1: 0 % | EF1: 0 % |
|loss | EF2: 0 % | EF2: 0 % |
|rate | BE0: 0 % | BE0: 19.7 % |
| | BE1: 0 % | BE1: 32.6 % |
+--------+-----------------+-----------------+
A.1.1.4 Case IV:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 4.001 Mbps |
|achieved| EF1: 2.018 Mbps | EF1: 2.000 Mbps |
|through-| EF2: 5.005 Mbps | EF2: 5.001 Mbps |
|put | BE0: 2.825 Mbps | BE0: 1.000 Mbps |
| | BE1: 2.232 Mbps | BE1: --- |
+--------+-----------------+-----------------+
|BA | EF: 7.023 Mbps | EF: 11.002 Mbps |
|through-| BE: 5.057 Mbps | BE: 1.000 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: 0 % |
|packet | EF1: 0 % | EF1: 0 % |
|loss | EF2: 0 % | EF2: 0 % |
|rate | BE0: 23.9 % | BE0: 73.3 % |
| | BE1: 41.5 % | BE1: --- |
+--------+-----------------+-----------------+
NOTE: BE1 has undefined throughput and loss in situation "after
join", because TCP is going into retransmission back-off timer phase
and closes the connection after 512 seconds.
Bless & Wehrle Expires: September 2002 [Page 20]
A.1.1.5 Summary
The effects occur as described in Case 2 of section 2.1: in this
particular case (branching point at interior router), the existing
BE aggregates are affected adversely by the new EF receiver.
B.2.2 Border Router
When the branching point of a newly added multicast subtree is
located in a Border Router the NRS problem can occur as described in
section 2.1 (Case 1).
In the simulation runs presented in the following four subsections
D3 joins to the multicast group of sender S1 without making any
reservation or resource allocation. Consequently, a new subtree is
added to the existing multicast tree. The branching point issued by
the join of D3 is located in BR3. On the link to BR4 no bandwidth
was allocated for the new flow (EF1).
The metered throughput of the flows on the link between BR3 and BR4
in the four different cases is shown in the following four
subsections. The situation before the new receiver joins is shown in
the second column. The situation after the join is shown in column
three.
A.1.1.6 Case I:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|achieved| EF1: --- | EF1: 1.489 Mbps |
|through-| EF2: 5.002 Mbps | EF2: 3.512 Mbps |
|put | BE0: 1.000 Mbps | BE0: 1.000 Mbps |
| | BE1: 4.000 Mbps | BE1: 4.002 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 5.002 Mbps | EF: 5.001 Mbps |
|through-| BE: 5.000 Mbps | BE: 5.002 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|packet | EF1: --- | EF1: 25.6 % |
|loss | EF2: 0 % | EF2: 29.7 % |
|rate | BE0: 0 % | BE0: 0 % |
| | BE1: 0 % | BE1: 0 % |
+--------+-----------------+-----------------+
Bless & Wehrle Expires: September 2002 [Page 21]
A.1.1.7 Case II:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|achieved| EF1: --- | EF1: 1.520 Mbps |
|through-| EF2: 5.003 Mbps | EF2: 3.482 Mbps |
|put | BE0: 2.249 Mbps | BE0: 2.249 Mbps |
| | BE1: 2.252 Mbps | BE1: 2.252 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 5.003 Mbps | EF: 5.002 Mbps |
|through-| BE: 4.501 Mbps | BE: 4.501 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|packet | EF1: --- | EF1: 24.0 % |
|loss | EF2: 0 % | EF2: 30.4 % |
|rate | BE0: 0 % | BE0: 0 % |
| | BE1: 0 % | BE1: 0 % |
+--------+-----------------+-----------------+
A.1.1.8 Case III:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|achieved| EF1: --- | EF1: 1.084 Mbps |
|through-| EF2: 5.001 Mbps | EF2: 3.919 Mbps |
|put | BE0: 0.749 Mbps | BE0: 0.752 Mbps |
| | BE1: 0.749 Mbps | BE1: 0.748 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 5.001 Mbps | EF: 5.003 Mbps |
|through-| BE: 1.498 Mbps | BE: 1.500 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|packet | EF1: --- | EF1: 45.7 % |
|loss | EF2: 0 % | EF2: 21.7 % |
|rate | BE0: 0 % | BE0: 0 % |
| | BE1: 0 % | BE1: 0 % |
+--------+-----------------+-----------------+
Bless & Wehrle Expires: September 2002 [Page 22]
A.1.1.9 Case IV:
+--------+-----------------+-----------------+
| | before join | after join |
| | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|achieved| EF1: --- | EF1: 1.201 Mbps |
|through-| EF2: 5.048 Mbps | EF2: 3.803 Mbps |
|put | BE0: 2.638 Mbps | BE0: 2.535 Mbps |
| | BE1: 2.379 Mbps | BE1: 2.536 Mbps |
+--------+-----------------+-----------------+
|BA | EF: 5.048 Mbps | EF: 5.004 Mbps |
|through-| BE: 5.017 Mbps | BE: 5.071 Mbps |
|put | | |
+--------+-----------------+-----------------+
| | EF0: --- | EF0: --- |
|packet | EF1: --- | EF1: 40.0 % |
|loss | EF2: 0 % | EF2: 23.0 % |
|rate | BE0: 30.3 % | BE0: 32.1 % |
| | BE1: 33.3 % | BE1: 32.7 % |
+--------+-----------------+-----------------+
A.1.1.10 Summary
The effects occur as described in Case 1 of section 2.1: in this
particular case (branching point at border router), the existing EF
aggregates are affected adversely by the new EF receiver.
Bless & Wehrle Expires: September 2002 [Page 23]