Internet DRAFT - draft-hou-cbt-qos
draft-hou-cbt-qos
HTTP/1.1 200 OK
Date: Tue, 09 Apr 2002 00:27:45 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Wed, 03 Mar 1999 16:09:47 GMT
ETag: "2e6d04-f828-36dd5ecb"
Accept-Ranges: bytes
Content-Length: 63528
Connection: close
Content-Type: text/plain
Internet Engineering Task Force J. Hou, H.-Y. Tyan, B. Wang
INTERNET DRAFT The Ohio State University
Y.-M. Chen
Fujitsu Labs of America
February 1999
QoS Extension to CBT
<draft-hou-cbt-qos-00.txt>
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.
Abstract
This document describes extension to the CBT protocol to maintain a
multicast tree with user-specified QoS properties. Specifically, it
describes enhancements in the member join/leave and state
update/refresh procedures to facilitate the deployment of additive
(e.g., end-to-end delay bound), multiplicative (e.g., packet loss
ratio along a path) and concave (e.g., minimum bandwidth available)
QoS.
Eligibility tests are devised to verify whether or not a new member
can join a multicast tree at adequate QoS, while not violating the
QoS received by on-tree members. Management of router state is based
on a simple state update and refresh procedure that can be readily
integrated with the tree maintenance mechanism that exists in CBT
(i.e., echo-requests and echo-replies).
Hou et al. Expires 30 September 1999 [Page 1]
Internet-Draft QoS Extension to CBT 15 March 1999
TABLE OF CONTENTS
Status of This Memo 1
Abstract 1
1. Introduction 3
1.1. Objective ................................................... 3
1.2. Network Model ............................................... 3
1.3. QoS Parameters Considered ................................... 4
1.4. Terminology ................................................. 5
1.5. Overview of QoS Extension ................................... 5
2. The QoS Extension in the Case of Imposing a Bound on Additive QoS
Parameters 7
2.1. State Kept at Each On-Tree Router ........................... 7
2.2. Eligibility Tests and Member Join Procedure ................. 8
2.3. Member Leave Procedure ...................................... 9
3. The QoS Extension in the Case of Imposing a Bound on Multiplicative
QoS Parameters 10
3.1. State Kept at Each On-Tree Router .......................... 11
3.2. Eligibility Tests and Member Join Procedure ................ 11
3.3. Member Leave Procedure ..................................... 12
4. The QoS Extension in the Case of Imposing a Bound on Concave
QoS Parameters 12
4.1. State Kept at Each On-Tree Router .......................... 13
4.2. Eligibility Tests and Member Join Procedure ................ 13
4.3. Member Leave Procedure ..................................... 14
5. State Update and Refreshed Based on the Soft State Concept 14
5.1. State Establishment ........................................ 14
5.2. State Refresh and Update ................................... 15
6. What if the QoS Requirements are Heterogeneous .................. 17
6.1. Receiver Heterogeneity in the Case of Additive QoS Parameters17
6.2. Receiver Heterogeneity in the Case of Multiplicative QoS
Parameters ................................................. 18
7. Security Considerations 18
A. Message Format 18
A.1. CBT Packet Format .......................................... 18
A.2. Options Defined in the QoS Extension ....................... 20
References 24
Hou et al. Expires 30 September 1999 [Page 2]
Internet-Draft QoS Extension to CBT 15 March 1999
1. Introduction
1.1. Objective
This Internet Draft presents a set of QoS enhancements (in the the
member join/leave and state update/refresh procedures), to allow QoS
deployment in the Core Based Tree (CBT) Protocol [1,2], with the
minimal impact to the existing infrastructure. Specifically, we
consider additive QoS (e.g., end-to-end delay bound), multiplicative
QoS (e.g., maximum packet loss ratio), and concave QoS (e.g., minimum
bandwidth available) [3], and devise a unified QoS extension
framework. In particular, we (i) devise eligibility tests to verify
whether or not a new member can join a multicast tree at adequate
QoS, while not violating the existing QoS to the other on-tree
members; (ii) determine the set of states needed to conduct
eligibility tests; and (iii) devise a state update/refresh procedure
that is based on soft state and can be readily integrated with the
tree maintenance mechanism that already exists in CBT, e.g., sending
of echo-requests and echo-replies in CBT.
Although we focus on CBT in the document, the proposed QoS extension
can be applied to any bi-directional multicast routing protocol with
the explicit member join procedure and soft state refresh procedure,
such as Simple Multicast [9].
1.2. Network Model
We consider a network that supports both best-effort traffic and
traffic with QoS requirements. The way in which network resources
are split between the two classes is irrelevant to the document,
except for the assumption that each router in the network supports
the QoS extension and is able to identify and advertise to their
immediate neighbors the QoS parameter of interest experienced by
packets when traversing links emanating from the router.
We represent a network by a weighted digraph G = (V, E), where V
denotes the set of routers and E the set of network communication
links connecting the routers. We define a link-delay (available
bandwidth) function f_D: E --> R+ (f_B: E --> R+) which assigns a
non-negative weight to each link in the network. The value of f_D(i)
is a measure of the delay which packets experience on link i in E.
(The value of f_B(i) is a measure of the bandwidth available on link
i in E.) Similarly, we define a packet loss function p_L: E -->
[0,1] which assigns a non-negative fractional weight to each link in
the network. The value of p_L(i) is the probability of packet loss
on link i in E.
Hou et al. Expires 30 September 1999 [Page 3]
Internet-Draft QoS Extension to CBT 15 March 1999
We denote as M_g (which is a subset of V) a set of routers to which
hosts that belong to a group g are attached. For notational
simplicity, we call the set M_g a multicast group with each router v
in M_g as a group member. (Actually the multicast group is the set
of hosts that are directly attached to routers in M_g.) We consider
the most general many-to-many multicast paradigm in which each router
v in M_g can be a source, in addition to being a receiver in the
group. Let M_s denote the set of group members that are also
sources. Packets originating from router v in M_s have to be
delivered to a set of receiver routers M_g - {v}. We use P_T(v_s,
v_d) to denote the path from a source router v_s to a receiver router
v_d in M-{v_s} in the tree T. We also use "x in P_T(v_s,v_d)" to
denote that P_T(v_s,v_d) traverses either router x or link x.
1.3. QoS Parameters Considered
We define m(l) as a QoS metric for link l. For any path P_T(u,v) =
(u,i,j,...,k,v), we say metric m is additive if
m(u,v) = m(u,i) + m(i,j) + ... + m(k,v).
For example, the end-to-end delay d(u,v), which packets forwarded
from router u to router v experience, is additive and is equal to the
sum of individual link metric m(i,j) along the path P_T(u,v)
We say metric m is multiplicative if
m(u,v) = m(u,i) x m(i,j) x ... x m(k,v).
For example, the probability, 1 - p_L(u,v), for a packet to reach
router v from router u along P_T(u,v) is multiplicative and is equal
to the product of individual link metric p_L(i,j) along the path
P_T(u,v).
We say metric m is concave if
m(u,v) = min[ m(u,i), m(i,j), ..., m(k,v) ].
For example, the bandwidth b(u,v), available along a path from router
u to router v, is concave and is equal to the minimum bandwidth
f_B(i,j) among the links in path P_T(u,v)
A QoS requirement may be specified as (i) an upper/lower bound on an
additive/multiplicative/concave QoS parameter, e.g., an upper bound
on the end-to-end delay, a upper bound on the packet loss ratio, or a
lower bound on the bandwidth available, from any source to the
receiver; or (ii) an upper bound on the inter-destination difference
Hou et al. Expires 30 September 1999 [Page 4]
Internet-Draft QoS Extension to CBT 15 March 1999
of an (additive or multiplicative) QoS parameter along the paths from
a source to any two receivers, e.g., an upper bound on the end-to-end
inter-destination delay jitter (defined as the difference between the
end-to-end delays along the paths from a source router to any two
receiver routers. In this document, we focus on QoS requirements
specified in terms of (i). Interested readers are referred to [12]
for a detailed account of the QoS extension with respect to
requirements specified in terms of (ii).
The need for a bounded end-to-end delay, bounded probability of
packet loss, and minimal available bandwidth has been well justified
[4,5]. The situation in which a bounded inter-destination delay
jitter among all the group members arises is also not rare [6]. One
possible scenario occurs during a teleconference in which any current
speaker should be heard by all participants at approximately the same
time to achieve the feeling of multi-party interactive face-to-face
discussions. Another application domain is the distributed
interactive simulation in which an inter-destination delay jitter
bound is needed to constrain the time during which the simulation
engines are in inconsistent states.
1.4. Terminology
Throughout the document, "downstream" refers to the direction that is
away from core. Given a router, a "subtree" refers to the router and
the multicast group members reachable by the router through an on-
tree path sourced at a downstream interface of the router.
1.5. Overview of QoS Extension
In the original CBT protocol, one router for each group is selected
as the core router (or termed elsewhere rendezvous point (RP) [11])
for the group. A tree rooted at the core is then constructed to span
all the group members. A host first expresses its interest in
joining a group by multicasting an IGMP host membership report [7] to
its local router which then sends a join-request message to the next
hop on the path toward the group's core router. The join-request
sets up transient join state (in the form of <group, downstream
interface, upstream interface>) in the routers it traverses. If the
transient join state is not ``confirmed'' with a join-acknowledgment
message from upstream, the state is eventually timed out. The join-
request message travels hop-by-hop toward the core until it reaches
the core or an on-tree router, at which point a join-acknowledgment
message is sent back along the reverse path, forming a new branch
from the tree to the requesting router. When a router receives a
Hou et al. Expires 30 September 1999 [Page 5]
Internet-Draft QoS Extension to CBT 15 March 1999
join-acknowledgment message, it updates its forwarding cache to
reflect the fact that it now becomes an on-tree router, and forwards
the join-acknowledgment message back to the requesting router.
In the case that a member leaves the group, if the local router (to
which the leaving member is attached) does not have any other
directly attached members or downstream on-tree routers, the router
sends a quit-notification message to its parent router on the tree
and deletes the corresponding forwarding cache.
To support QoS, we introduce the following QoS extension to the
current CBT specification: each join-request message carries, in
addition to the interface information, the QoS parameters of interest
along the route. When a join-request message reaches the core or an
on-tree router, the core/router performs a set of eligibility tests.
Although it is preferable that eligibility tests be conducted locally
at the on-tree router, the on-tree router may not be able to approve
a join-request only based on its local state, and may have to
collaborate with other on-tree routers to conduct the eligibility
tests. Moreover, the state kept at some other on-tree routers may
have to be changed because of the member join. That is,
collaboration among on-tree routers is sometimes inevitable in
approving a join request. Only after the branch survives the
eligibility tests will it be eligible to join the multicast tree
(under which case a join-acknowledgment message is then sent back).
In the case of member leave, the state kept at the other on-tree
routers may have to be updated and proper procedures be taken to
notify on-tree routers of the need to update their states. Note that
while changes to the current CBT protocol specification seem
unavoidable, we have attempted to keep them as small as possible.
To realize the above QoS extension, we consider, for each type of QoS
requirements, the following issues:
(1) What is the minimum set of states each on-tree router has to
keep in order to conduct the proposed work?
(2) What are the eligibility tests conducted at the time of member
join? How are eligibility tests collaboratively conducted among on-
tree routers if need be?
(3) Whether or not, and how, is the set of states kept at an on-tree
router updated in response to member leave?
(4) How is the set of states updated and refreshed at each on-tree
router?
Hou et al. Expires 30 September 1999 [Page 6]
Internet-Draft QoS Extension to CBT 15 March 1999
The rest of the document is structured as follows. In Sections 2-4,
we present the QoS extension in the cases of imposing a bound on
additive QoS parameters, of imposing a bound on multiplicative QoS
parameters, and of imposing a bound on concave QoS parameters,
respectively. (The case of imposing a bound on the maximum
difference of (additive or multiplicative) QoS parameters along the
paths from a source to any two receiver routers is elaborated on in
[12].) In Section 5, we present the state update and refresh
procedure based on the soft state concept. In Section 6, we discuss
how to extend the work in Sections 2-4 to the case of heterogeneous
receiver-initiated QoS requirements. The security issue is
considered in Section 7. Finally, Appendix A gives the message
format defined in the QoS extension.
2. The QoS Extension in the Case of Imposing a Bound on Additive QoS
Parameters
We first consider the case in which the QoS requested is expressed in
terms of additive QoS parameters. Without loss of generality, we use
the end-to-end delay as an example, and impose an upper bound, D, on
the acceptable end-to-end delay perceived by a receiver router along
any path from a source router to the receiver router in a multicast
group.
2.1. The State Kept at Each On-Tree Router
To satisfy the end-to-end delay bound, each on-tree router, u, keeps
the following state for each downstream interface:
(1) d_{max,i}(u,*): the maximum delay among the on-tree paths from
router u to the downstream on-tree group members reachable on
interface i, where interface i is a downstream interface and
downstream is defined with respect to the core.
(2) d_{max,i}(*,u): the maximum delay among the on-tree paths from
all the downstream on-tree source group members reachable on
interface i to router u.
The per-node state d_{max}(u,*) is naturally defined as the maximum
d_{max,i}(u,*) value among the downstream interfaces i of router u.
Similarly d_{max}(*,u) is defined as the maximum d_{max,i}(*,u) value
among the downstream interfaces i of router u. One can interpret
d_{max}(u,*) and d_{max}(*,u) as the maximum outgoing and incoming
delays, respectively, incurred when a multicast packet traverses the
Hou et al. Expires 30 September 1999 [Page 7]
Internet-Draft QoS Extension to CBT 15 March 1999
subtree from/to router u, i.e.,
d_{max}(u,*) = max_{i in DI} d_{max,i}(u,*)
and
d_{max}(*,u) = max_{i in DI} d_{max,i}(*,u),
where DI is the set of downstream interfaces of router u. Let T_s(u)
denote the subtree rooted at router u, then each on-tree router keeps
the state information for T_s(u). The reason for keeping per-
downstream-interface (instead of per-node) state will become clearer
when we discuss the member leave procedure in Section 2.3.
2.2. Eligibility Tests and Member Join Procedure
When a join-request message from a joining router v arrives at an
on-tree router u, router u checks if
d_{max}(*,v) = d(u,v) + d_{max}(*,u) <= D. (2.1)
In addition, if the joining member v is also a source, router u
further checks if
d_{max}(v,*) = d(v,u) + d_{max}(u,*) <= D. (2.2)
Both parameters d_{max}(u,*) and d_{max}(*,u) are kept at each on-
tree router u as the state. Both parameters, d(v,u) and d(u,v), can
be carried in the join- request message and updated as the message
travels from router v to router u.
If Eq. (2.1) holds, it implies the QoS requirement of the new member
v is fulfilled by all the source group members in T_s(u). Similarly,
if Eq. (2.2) holds, it implies the QoS requirements for the group
members in T_s(u) are not violated due to join of the new source
member v.
If Eq. (2.1) (or Eq. (2.2) in the case that router v is also a
source) does not hold, the join request is immediately rejected and a
rejection-reply message is sent back to the joining router v.
Otherwise, router u forwards upstream to its parent router w the
join-request with the updated accumulative delay information (d(w,u)
+ d(u,v) and, in addition, d(v,u) + d(u,w) if router v is also a
source). Upon receipt of the join-request on interface i, Router w
Hou et al. Expires 30 September 1999 [Page 8]
Internet-Draft QoS Extension to CBT 15 March 1999
conducts the eligibility test (i.e., Eqs. (2.1)-(2.2) except u is
replaced by w in the expressions) to verify if join of router v
violates the QoS requirements of all the on-tree group members in
T_s(w) as well as if the QoS requirement of router v is fulfilled by
all the on-tree source members on T_s(w). If the eligibility test
succeeds, router w forwards upstream to its parent router the join-
request (with the updated accumulative delay information); otherwise,
it sends downstream to its child router a rejection-reply message.
The process repeats until the join-request is either rejected at some
upstream on-tree router or forwarded to, and approved by, the core
(which then sends back a join-acknowledgment message along the
reversed on-tree path), whichever occurs first. In the former case,
the on-tree router, u, where the join-request arrives initially sends
back a rejection-reply message to the joining router v. In the
latter case, each on-tree router, w, on the path from router u and
the core updates its state upon receipt of the join-acknowledgment
message from upstream, if d(w,v) > d_{max,i}(w,*) and/or d(v,w) >
d_{max,i}(*,w), where interface i is the interface on which router w
received the corresponding join-request, and router u sends back a
join-acknowledgment message.
In short, each on-tree router u keeps only its subtree state
information (which eases the job of state update and maintenance at
the time of member join). When a join-request arrives at an on-tree
router u, it has to pass a sequence of eligibility tests before it is
approved, where each test is performed router by router on the tree-
path from router u to the core.
Note that to avoid potential QoS conflicts among multiple members
that intend to join a multicast group at the same on-tree router, an
on-tree router will not process the next request until it finishes
processing the current join request and sends back either a
rejection-reply message or a join-acknowledgment message. As a
result, a new join-request may be blocked between the time between a
previous join-request is forwarded upstream and the corresponding
response returns. We argue that since only the on-tree routers
between router u and the core are involved in jointly approving a
join-request, this transient period cannot be prohibitively long.
2.3. Member Leave Procedure
When a member router v leaves a multicast tree, it sends a quit-
notification message (with the accumulative delay information d(v,u))
to its parent router u. Upon receipt of a quit-notification message
on interface i, if router u does not have any other local members (on
the directly attached subnet) or downstream on-tree routers, it sends
Hou et al. Expires 30 September 1999 [Page 9]
Internet-Draft QoS Extension to CBT 15 March 1999
a quit-notification message to its parent router w and deletes the
corresponding forwarding cache. Otherwise, router u first deletes
from the forwarding cache the interface on which the quit-
notification message arrives (interface i), and then checks if
d(u,v) <= d_{max}(u,*), (2.3)
and in addition, in case that router v is a also source router,
d(v,u) <= d_{max}(*,u). (2.4)
If Eq. (2.3) (and in addition, Eq. (2.4), in the case that router v
is also a source router) holds, it implies the state kept at router u
as well as other on-tree (upstream) routers will not change as a
result of this member leave. Otherwise, router u first updates its
per-node state to reflect the fact that router v has left the
multicast tree and sends upstream to its parent router w a leave-
update message that carries d(u,v) + d(w,u) (and in addition, d(v,u)
+ d(u,w), if the leaving member is also a source). Upon receipt of a
leave-update message, router w checks whether or not its state is
affected by the member leave (i.e., Eqs. (2.3)--(2.4) except u is
replaced by w). The update process repeats until either the test
succeeds at some upstream router or the leave-update message reaches
the core.
The aforementioned procedure also illustrates why on-tree routers
have to keep per-downstream-interface state. If only per-node state
were kept, when a leave-request leads to the readjustment of
d_{max}(u,*) or d_{max}(*,u), the node would not have information for
the new value.
3. The QoS Extension in the Case of Imposing a Bound on Multiplicative
QoS Parameters
We now consider the case in which the QoS requested is expressed in
terms of multiplicative QoS parameters. Recall that for any path
P_T(u,v) = (u,i,j,...,k,v), we say metric m is multiplicative if
m(u,v) = m(u,i) x m(i,j) x ... x m(k,v).
Taking log of the above expression, we have
log m(u,v) = log m(u,i) + log m(i,j) + ... + log m(k,v).
That is, the QoS extension discussed in Section 2 can be readily
applied if the state is kept in the log form of a multiplicative QoS
metric. Without loss of generality, we use the packet loss ratio as
Hou et al. Expires 30 September 1999 [Page 10]
Internet-Draft QoS Extension to CBT 15 March 1999
an example and impose an upper bound, 1-L (0 <= L < 1), on the
minimum acceptable packet loss ratio along an on-tree path leading to
the receiver router.
3.1. The State Kept at Each On-Tree Router
The packet loss ratio, p_L(u,v), along a path from router u to router
v can be expressed as
1 - p_L(u,v) = prod_{l in P_T(u,v)} (1 - p_L(l)).
Taking log of the above expression, we have
log(1 - p_L(u,v)) = sum_{l in P_T(u,v)} log(1 - p_L(l)).
We define the successful transmission index, s(u,v), on the path
P_T(u,v) as s(u,v) = log (1 - p_L(u,v)).
To satisfy the upper bound on the packet loss ratio, each on-tree
router, u, keeps the following state for each downstream interface:
(1) s_{min,i} s(u,*): the minimum value of log(1 - p_L(u,v)) among
the on-tree paths from router u to the downstream on-tree routers v
reachable on interface i.
(2) s_{min,i} s(*,u): the minimum value of log(1 - p_L(v,u)) among
the on-tree paths from the downstream on-tree source routers v
reachable on interface i to router u.
The per-node state, s_{min}(u,*), defined as the minimum value of
log(1 - p_L(u,v)) among the on-tree paths from router u to downstream
on-tree routers v, and s_{min}(*,u), defined as the minimum value of
log(1 - p_L(v,u)) among the on-tree paths from the downstream on-tree
source routers v to router u, can be obtained by taking the minimum
of the corresponding per-interface states over all the downstream
interfaces.
3.2. Eligibility Tests and Member Join Procedure
Now when a join-request message from a joining router v arrives at an
on-tree router u, router u checks if
s_{min}(*,v) = s(u,v) + s_{min}(*,u) >= L. (3.1)
In addition, if router v is also a source, router u further checks if
Hou et al. Expires 30 September 1999 [Page 11]
Internet-Draft QoS Extension to CBT 15 March 1999
s_{min}(v,*) = s(v,u) + s_{min}(u,*) >= L. (3.2)
Both parameters, s(u,v) = log(1-p_L(u,v)) and s(v,u) = log(1-
p_L(v,u)), can be carried in the join-request message and updated as
the message travels from router v to router u.
The process of conducting the eligibility test (Eqs. (3.1)--(3.2))
and forwarding the join request upstream toward the core in the case
that the eligibility test succeeds is virtually the same as that
described in Section 2.2. Specifically, if Eq. (3.1) (or Eq. (3.2)
in the case that router v is also a source) does not hold, the join
request is immediately rejected and a rejection-reply message is sent
back to the joining router v. Otherwise, router u forwards upstream
to its parent router w the join-request with the updated packet loss
information (s(w,u) + s(u,v)) and in addition, s(v,u) + s(u,w), if
router v is also a source). The process repeats until the join-
request either is rejected at some upstream on-tree router or is
forwarded to, and approved by, the core, whichever occurs first. In
the former case, the first on-tree router, u, at which the join-
request arrives sends back a rejection-reply message to the joining
router v. In the latter case, each on-tree router w, on the path
from router u to the core, checks if state update is necessary upon
receipt of the join-acknowledgment message from upstream. The state
is updated if d(w,v) > d_{max,i}(w,*) and/or d(v,w) > d_{max,i}(*,w),
where interface i is the interface on which router w received the
corresponding join-request. Eventually router u receives the join-
acknowledgment message and forwards it downstream to v.
3.3. Member Leave Procedure
The procedure taken upon receipt of a quit-notification message is
virtually the same as that described in Section 2.3, except that Eqs.
(2.3)--(2.4) are now replaced by
s(u,v) >= s_{min}(u,*), (3.3)
and
s(v,u) >= s_{min}(*,u). (3.4)
4. The QoS Extension in the Case of Imposing a Bound on Concave QoS
Parameters
We now consider the case in which the QoS requested is expressed in
terms of concave QoS parameters. Without loss of generality, we use
Hou et al. Expires 30 September 1999 [Page 12]
Internet-Draft QoS Extension to CBT 15 March 1999
the bandwidth available along a path as an example and impose a lower
bound, B, on the minimum bandwidth that must be available along any
path from a source router to any receiver router in a multicast
group.
4.1. The State Kept at Each On-Tree Router
To satisfy the minimum bandwidth requirement, B, for a multicast
group, each on-tree router u needs only to keep the state B and a
counter, C, of how many source routers currently exist in the
subtree, T_s(u), rooted at router u (initially C=0).
4.2. Eligibility Tests and Member Join Procedure
When a join-request message from a joining router v arrives at an
on-tree router u, router u checks if
b(u,v) >= B, (4.1)
and in addition, if router v is also a source, router u further
checks if
b(v,u) >= B. (4.2)
Both parameters, b(v,u) and b(u,v), can be carried in the join-
request message and updated as the message travels from router v to
router u.
If Eq. (4.1) (or Eq. (4.2) in the case that router v is also a
source) does not hold, the join request is immediately rejected and a
rejection- reply message is sent back to the joining router v.
Otherwise (the join-request passes the local eligibility test), we
consider two cases:
(C1) In the case that router v is only a receiver, router u sends
back a join-acknowledgment message immediately to reserve bandwidth
of amount B, along the reversed path, for the multicast group.
(Note that if bandwidth reservation is not combined with routing,
and a separate signaling protocol such as RSVP [8] is used for
resource reservation, then the bandwidth is not reserved.) There is
no need to forward the join-request upstream, because the first
receiver router in the subtree, T_S(u), rooted at router u, has
reserved bandwidth of amount B on the path from the core to router
u.
(C2) In the case that router v is both a receiver and a source, if
Hou et al. Expires 30 September 1999 [Page 13]
Internet-Draft QoS Extension to CBT 15 March 1999
the indicator is zero (i.e., no source router exists in the subtree
T_s(u) so far), router u (i) reserves bandwidth of amount B on the
upstream on-tree link (u,w), (ii) forwards upstream to its parent
router w the join-request in order to reserve the bandwidth of
amount B on the path from router w to the core for the multicast
group; and (iii) increment the counter C by one. Otherwise, router
u sends back a join-acknowledgment to reserve bandwidth of amount B,
along the reversed path to the requesting router. The process
repeats until the join-request is either rejected (because of
insufficient bandwidth on its upstream on-tree link) or approved at
some upstream on-tree router x, whichever occurs first. In the
former case, each on-tree router, w, on the path between router u
and router x releases the reserved bandwidth in the upstream
direction, and router u sends back a rejection-reply message to the
joining router v. In the latter case, router u sends back a join-
acknowledgment message to reserve bandwidth of amount B along the
reversed path.
4.3. Member Leave Procedure
When a member router v leaves a multicast tree, it sends a quit-
notification message to its parent router u. If router u does not
have any other local members (on the directly attached subnet) or
downstream on-tree routers, it sends a quit-notification message to
its parent router w and deletes the corresponding forwarding cache.
Otherwise, router u deletes from the forwarding cache the interface
on which the quit-notification message arrives. In the latter case,
if router v is also a source, router u decrements its counter C by
one. If after decrement C becomes zero, router u releases the
bandwidth of amount B on link (u,w), and sends upstream to its parent
router w a leave-update message to release bandwidth reserved in the
upward direction. Upon receipt of a leave-update message, router w
(i) decrements its counter C by one, and (ii) releases bandwidth and
forwards the leave-update message upstream if C hits zero. The
update process repeats until either the leave-update message reaches
the core or stops at some upstream router with more than 1 source
router in its subtree.
5. State Update and Refresh Based on the Soft State Concept
We first discuss how the state is established at each on-tree router.
Then, we present the state update and refresh mechanism that exploits
the soft state approach.
5.1 State Establishment
Hou et al. Expires 30 September 1999 [Page 14]
Internet-Draft QoS Extension to CBT 15 March 1999
When a new member v joins a multicast tree, each router w on the path
from router v to router u establishes its state using the delay
information carried in the join-request and join-acknowledgment
messages. For example, the accumulative delay information (contained
in the join-request message received on interface i) between router v
and the current router w can be used by router w to establish its
transient state (d_{max,i}(w,*) = d(w,v) and d_{max,i}(*,w) =
d(v,w)). When an off-tree router w with a pending join-request
receives the corresponding join-acknowledgment from its upstream
router, it updates its forwarding cache to reflect that it now
becomes an on-tree router, and updates its transient state as an
established one. Router w also forwards the message downstream to
the requesting router.
The other on-tree routers update their state only if they receive
join-request messages as a result of a join-request being forwarded
upstream (to be jointly approved by the on-tree routers between the
on-tree router at which a join-request initially arrives and the
core).
5.2. State Refresh and Update
To be robust to message loss, many Internet protocols (e.g., DVMRP
[10], PIM [11], CBT [1,2], Simple Multicast [9]) have adopted the
soft state approach for state maintenance, i.e., the state kept at
each router is created and periodically refreshed by certain state-
refresh messages. A state is deleted if no matching refresh messages
arrive before the expiration of its associated timer. For example,
CBT maintains its tree by having each downstream router periodically
send a CBT echo-request message to its upstream neighbor router. The
receipt of an echo-request message over a valid child interface
prompts an echo-reply message that carries a list of groups for which
the corresponding interface is a child interface. If no response is
forthcoming within UPSTREAM_EXPIRE_TIME seconds, (e.g., a router's
upstream neighbor becomes unreachable), the router sends a quit-
notification message upstream, and flushes all of its downstream
branches by sending flush-tree messages, allowing them to
individually rejoin if necessary.
We adopt the soft state approach and devise the state refresh and
update procedure accordingly. The proposed state refresh procedure
can be easily integrated with the CBT tree maintenance procedure
(i.e., sending of echo-request and echo-reply messages) thus making
the overheads that result from the proposed QoS extension small.
Specifically, the state kept at an on-tree router is associated with
the same DOWNSTREAM_EXPIRE_TIME timer. When a timer expires, the
corresponding state is removed. An on-tree router initiates a state
Hou et al. Expires 30 September 1999 [Page 15]
Internet-Draft QoS Extension to CBT 15 March 1999
update process by periodically sending an echo-request message and
piggybacking its state in the message. Upon receiving an echo-
request message, a parent router updates its state if needed, resets
the associated timer, responds with an echo-reply message, and
initiates (upstream) a state update process if the its state does
change.
To deal with the situation in which message loss results in the
removal of a valid soft state, we investigate whether or not the
correctness of the proposed QoS extension is subject to loss of
control messages. To deal with the loss of echo-request/echo-reply
messages, CBT sets the UPSTREAM_EXPIRE_TIME and
DOWNSTREAM_EXPIRE_TIME timer intervals K times larger than the
ECHO_INTERVAL timer interval so that echo-request messages can be
lost (K-1) consecutive times before the state is (incorrectly)
removed. (K=3 in the current CBT protocol specification.) In the
case that echo-request messages are lost more than K consecutive
times, we consider the following two cases:
(C1) If a downstream router does not hear from its upstream router
upon the UPSTREAM_EXPIRE_TIME timer expiration, it considers the
path to its upstream router as damaged, and sends a quit-
notification message upstream, and flush-tree messages downstream to
flush the subtree rooted at it. Each downstream group member will
then individually find an alternative route to rejoin the tree.
This is the approach currently defined in the CBT protocol
specification.
(C2) If an upstream router w does not hear from its downstream
router u upon the DOWNSTREAM_EXPIRE_TIME timer expiration, it
removes the state and the forwarding cache entry as if the subtree
(rooted at router u) were ``flushed''. Later when a echo-request
message from the router u re-appears at router w, router w, instead
of re-establishing the state and the forwarding cache (as the
current CBT specification specifies), flushes the sub-tree. This is
because during the period when router w and its upstream routers
believe the sub-tree is ``flushed,'' if a new join-request arrives
at one of these on-tree routers, it may be approved when it should
actually be denied when the subtree is taken into account. Since
consecutive loss of K echo-request messages is usually a good
indication of low delivery quality of downstream links, it would
actually be better for the downstream group members to re-join the
multicast group individually along an alternative route of better
quality.
Loss of join-request, join-acknowledgment, and quit-notification
messages has been dealt with in the current CBT specification: if any
Hou et al. Expires 30 September 1999 [Page 16]
Internet-Draft QoS Extension to CBT 15 March 1999
of the join-request or join-acknowledgment messages is lost, the
transient state established at each router on the path from the
requesting router to an on-tree router is removed upon timer
expiration. The state created on the path along which a join-
acknowledgment message traverses will eventually time out, due to the
lack of echo-request messages from downstream. Similarly, if any
quit-notification message is lost, the valid state maintained at
upstream routers will eventually time out, due to the lack of echo-
request messages from downstream. The same strategy can be directly
applied to the QoS extension mechanism to deal with loss of these
messages (and rejection-replay messages as well). For example, if a
join-acknowledgment message is lost on its way back to the on-tree
router at which the join-request initially arrives, some (upstream)
router(s) have changed their temporary state into valid soft state,
while other (downstream) router(s) remove them. This does not affect
the correctness of the proposed extension, because the state at
upstream routers will be adjusted upon receipt of the next echo-
request message. Similarly, when a leave-update message is lost on
its way upstream, the soft state maintained at upstream routers will
be adjusted upon receipt of the next echo-request message. The net
effect is, however, that during the transient period new join
requests may be pessimistically rejected because of tighter
(outdated) state kept at some upstream routers. (By the same token,
leave-update messages may be totally eliminated.)
6. What if the QoS Requirements are Heterogeneous
Since CBT is a receiver-initiated multicast routing protocol, it is
especially well-suited to support heterogeneous receiver reservation,
i.e., each receiver may request different levels of QoS [8]. (Note,
however, that it does not make sense for each receiver to request
different bounds on the inter-destination delay jitter.) The
eligibility tests and the state update procedure can be modified to
support receiver heterogeneity as follows.
6.1. Receiver Heterogeneity in the Case of Additive QoS Parameters
Let D_v denote the delay bound imposed by a receiver router v, then
the eligibility test (Eqs. (2.1)-(2.2)) is modified as
d(u,v) + d_{max}(*,u) <= D_v, (6.1)
and
d(v,u) <= D_w - d(u,w), for all group members w in T_s(u). (6.2)
Hou et al. Expires 30 September 1999 [Page 17]
Internet-Draft QoS Extension to CBT 15 March 1999
Note that Eq. (5.2) can be rewritten as
d(v,u) <= min_{ w in T_s(u) } D_w - d(u,w). (6.3)
The per-interface state kept at each on-tree router u is (i)
d_{max,i}(*,u) and (ii) the minimum laxity defined as the minimum
difference between D_w and d(u,w) among all downstream on-tree group
members w reachable on interface i, i.e., min_{w in T_s(u), reachable
on interface i} (D_w - d(u,w)).
6.2. Receiver Heterogeneity in the Case of Multiplicative QoS Parameters
Let 1-L_v denote the upper bound on the packet loss ratio imposed by
a receiver router v, then the eligibility test (Eqs. (3.1)-(3.2)) is
modified as
s_{min}(*,v) = s(u,v) + s_{min}(*,u) >= L_v, (6.4)
and
s(v,u) >= L_w - s(u,w), for all group members w in T_s(u). (6.5)
The state kept at each on-tree router u is (i) s_{min,i}(*,u); and
(ii) the maximum difference between L_w and s(u,w) among all the
downstream on-tree group members w reachable on interface i, i.e.,
max_{w in T_s(u), reachable on interface i} (L_w - s(u,w)).
7. Security Considerations
Work in progress.
Appendix
A. Message Format
As mentioned above, we intend to provide the QoS extension to CBT,
with the minimum possible impact to the exciting infrastructure. All
of the component mechanisms, data structures, and data formats in CBT
remain unchanged except the following new option definitions in the
message format.
A.1 CBT Packet Format
CBT packet formats and message types are defined in the CBT protocol
Hou et al. Expires 30 September 1999 [Page 18]
Internet-Draft QoS Extension to CBT 15 March 1999
specification [1]. For completeness of the document, we briefly
summarize below the packet format that pertains to the document.
A.1.1. CBT Common Control Packet Header
All CBT control messages have a common fixed length header.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| vers | type | addr len | checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1. CBT Common Control Packet Header
CBT packet types are:
+^Ho type 0: HELLO
+^Ho type 1: JOIN_REQUEST
+^Ho type 2: JOIN_ACK
+^Ho type 3: QUIT_NOTIFICATION
+^Ho type 4: ECHO_REQUEST
+^Ho type 5: ECHO_REPLY
+^Ho type 6: FLUSH_TREE
+^Ho type 7: Bootstrap Message (optional)
+^Ho type 8: Candidate Core Advertisement (optional)
+^Ho Addr Length: address length in bytes of unicast or multicast
addresses carried in the control packet.
+^Ho Checksum: the 16-bit one's complement of the one's complement
sum
of the entire CBT control packet.
A.1.2. Packet Format for CBT Control Packet Types 0 - 6
A CBT control packet is divided into 3 parts:
+^Ho Common Control Packet Header,
Hou et al. Expires 30 September 1999 [Page 19]
Internet-Draft QoS Extension to CBT 15 March 1999
+^Ho Control Packet Payload, and
+^Ho Control Packet Option(s).
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common
| CBT Control Packet Header | Header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
|Payload Length | # of options | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control
| address #1 | Packet
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload
| address #2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| address #n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| option type | option len | option value... | Option(s)
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2. CBT Control Packet Format for Types 0 - 6.
Control Packet Field Definitions:
+^Ho # Payload Length: the length of the CBT control packet
payload, excluding the common control packet header and
option(s).
+^Ho # of options: the number of distinct options (as defined by
option type) carried in this control packet.
+^Ho address #n: control packet payload address(es). Different
control packet types carry addresses (multicast and/or
unicast) as their payload (e.g. JOIN_REQUESTs), and some
control packet types carry no addresses in the payload (e.g.
HELLOs).
+^Ho option type: unique option identifier.
+^Ho option len: option length. The number of bytes consumed by
this option's value.
+^Ho option value: variable length option value.
NOTE: all control messages are padded to a 32-bit boundary.
A.2. Options Defined in the QoS Extension
A.2.1. Definition of New Option Types
Hou et al. Expires 30 September 1999 [Page 20]
Internet-Draft QoS Extension to CBT 15 March 1999
CBT has defined 5 types of options (Type 1-5). For the QoS extension,
we further define the following options.
Table 1. Definition of New Option Types in the QoS Extension
_________________________________________________________________
Option Type QoS Parameters QoS Parameters
(Homogeneous) (Heterogeneous)
_________________________________________________________________
10 D D_v
11 d_{max}(u,*) min_{w in T_s(u)}(D_w - d(u,w))
12 d_{max}(*,u) d_{max}(*,u)
13 d(u,v) reverse d(u,v) reverse
14 d(v,u) forward d(v,u) forward
-----------------------------------------------------------------
20 L L_v
21 s_{min}(u,*) max_{w in T_s(u)}(L_w - s(u,w))
22 s_{min}(*,u) s_{min}(*,u)
23 s(u,v) reverse s(u,v) reverse
24 s(v,u) forward s(v,u) forward
-----------------------------------------------------------------
30 B B_v
-----------------------------------------------------------------
40 JOIN_ACK
41 REJECTION_REPLY
_________________________________________________________________
Definitions of the QoS parameters in Table 1 are given in the
previous sections in the document.
A.2.2. Coding of Parameter Values
In order to align to a 32-bit boundary, the actual metric field in
the option provides only 16 bits to encode the value. As links
supporting bandwidth in the range of Gbits/s are becoming reality,
linear representation of the available resource metric is not
feasible. We adopt the method of exponential encoding using
appropriately chosen implicit base value and number of bits for
encoding mantissa and the exponent. A detailed discussion on the
exponential encoding method is given in [13]. Alternative approaches
include the use of more bits to encode parameters (which are
currently under investigation).
Delay is encoded in microseconds using the same exponential encoding
method except that the base is different. Interested readers are
Hou et al. Expires 30 September 1999 [Page 21]
Internet-Draft QoS Extension to CBT 15 March 1999
referred to [13] for a detailed account.
A.2.3. Sample Control Packets
In this section, we give examples of several different CBT control
packets with the QoS extension. Specifically, we add options to
JOIN_REQUEST, JOIN_ACK, QUIT_NOTIFICATION, and ECHO_REQUEST.
Depending on the QoS desired, the options added to control packets
differ.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common
| 3 | 1 | 4 | Checksum | Header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 16 | 5 | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control
| Group Address | Packet
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload
| Core Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Join-Originating DR |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 10 | 2 | D | Option
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 11 | 2 | d_{max}(u,*) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 12 | 2 | d_{max}(*,u) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 13 | 2 | d(u,v) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 14 | 2 | d(v,u) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------
Figure 3. Sample (*, G) JOIN_REQUEST with delay QoS metric
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common
| 3 | 1 | 4 | Checksum | Header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 16 | 1 | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control
| Group Address | Packet
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload
| Core Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Join-Originating DR |
Hou et al. Expires 30 September 1999 [Page 22]
Internet-Draft QoS Extension to CBT 15 March 1999
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 30 | 2 | B | Option
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------
Figure 4. Sample (*, G) JOIN_REQUEST with bandwidth QoS metric
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common
| 3 | 2 | 4 | Checksum | Header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 12 | 1 | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control
| Group Address | Packet
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload
| Join Originating DR (copied from JOIN_REQUEST) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 40 | 0 | PADDING | Option
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------
Figure 5. Sample (*, G) JOIN_ACK
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common
| 3 | 4 | 4 | Checksum | Header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 8 + (n x 4) | 3 | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control
| ECHO_REQUEST Originating Router | Packet
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload
| Address #1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address #2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address #n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 11 | 2 | d_{max}(u,*) | Option
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 12 | 2 | d_{max}(*,u) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 14 | 2 | d(v,u) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------
Figure 6. Sample ECHO_REQUEST with delay QoS metric
We can eliminate the need for a new type of message LEAVE_UPDATE by
augmenting the QUIT_NOTIFICATION with options. The only change to the
CBT code is for it to check whether or not QUIT_NOTIFICATION packets
have options.
Hou et al. Expires 30 September 1999 [Page 23]
Internet-Draft QoS Extension to CBT 15 March 1999
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Common
| 3 | 3 | 4 | Checksum | Header
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 16 | 4 | reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Control
| Group Address | Packet
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Payload
| Core Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Join-Originating DR |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ --------
| 10 | 2 | D | Option
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 11 | 2 | d_{max}(u,*) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 12 | 2 | d_{max}(*,u) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 14 | 2 | d(v,u) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -------
Figure 7. Sample (*, G) QUIT_NOTIFICATION/LEAVE_UPDATE with
delay QoS metric
There is no need to change ECHO_REPLY.
References
[1] A. Ballardie, B. Cain, Z. Zhang, "Core based trees (CBT version
3) multicast routing - protocol specification," draft-ietf-idmr-cbt-
spec-v3-00.txt, Internet-draft, Inter-domain multicast routing, March
1998.
[2] A. Ballardie, "Core based trees (CBT) multicast routing
architecture," RFC 2201, ftp://ds.internic.net/rfc/rfc2201.txt.
[3] Z. Wang and J. Crowcroft, "Quality-of-service routing for
supporting multimedia applications," IEEE Journal on Selected Areas
in Communications, Vol. 14, No. 7, pp. 1228--1234, September 1996.
[4] C. M. Aras, J. F. Kurose, D. S. Reeves, and H. Schulzrinne,
"Real-time communication in packet-switched networks," Proceedings of
the IEEE, Vol. 82, No. 1, pp. 122--139, January 1994.
[5] H. Zhang, "Service Disciplines for guaranteed performance service
in packet-switching networks," Proceedings of the IEEE, Vol. 83, No.
Hou et al. Expires 30 September 1999 [Page 24]
Internet-Draft QoS Extension to CBT 15 March 1999
10, October 1995.
[6] G. N. Rouskas and I. Baldine, "Multicast routing with end-to-end
delay and delay variation constraints," IEEE Journal on Selected
Areas in Communications, Vol. 15, No. 1, pp. 1--9, April 1997.
[7] W. Fenner, "Internet Group Management Protocol: version 2
(IGMPv2)," draft-ietf-idmr-igmp-v2-08.txt, Internet-draft, Inter-
domain multicast routing, 1998.
[8] R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin,
"Resource ReSerVation protocol RSVP - version 1 function
specification," draft-ietf-rsvp-spec-15.ps, Internet draft, May 1997.
[9] R. Perlman, C.-Y. Lee, A. Ballardie, J. Crowcroft, Z. Wang, and
T. Maufer, "Simple multicast: a design for simple, low-overhead
multicast," http://www.ietf.org/internet-drafts/draft-perlman-
simple-multicast-01.txt, December 1998.
[10] T. Pusateri, "Distance vector multicast routing protocol,"
ftp://ds.internic.net/internet-drafts/draft-ietf-idmr-dvmrp-v3-
04.txt, Internet draft, February 1997.
[11] D. Estrin, D. Farinacci, S. Deering, D. Thaler, A. Helmy, M.
Handley, V. Jacobson, C. Liu, P. Sharma, L. Wei, "Protocol
independent multicast - sparse mode (PIM-SM): protocol
specification," http://netweb.usc.edu/pim, RFC 2362 and Internet
draft, 1998.
[12] H.-Y. Tyan, J. Hou, B. Wang, and Y.-M. Chen, "QoS extension to
CBT," Technical report, Dept. of Electrical Engineering, The Ohio
State University, Columbus, OH. Available at http://eewww.eng.ohio-
state.edu/drcl/pubs.html.
[13] G.Apostolopoulos, R. Guerin, S. Kamat, A. Orda, T. Przygienda,
and D. Williams, "QoS Routing Mechanisms and OSPF Extensions",
draft-guerin-qos-routing-ospf-04.txt.
Author Information:
Jennifer C. Hou
Department of Electrical Engineering
The Ohio State University
Columbus, OH 43210-1272, USA
e-mail: jhou@ee.eng.ohio-state.edu
voice: +1 614 292 7290 Fax: +1 614 292 7596
Hou et al. Expires 30 September 1999 [Page 25]
Internet-Draft QoS Extension to CBT 15 March 1999
Hung-Ying Tyan
Department of Electrical Engineering
The Ohio State University
Columbus, OH 43210-1272, USA
e-mail: tyanh@ee.eng.ohio-state.edu
voice: +1 614 292 3430
Bin Wang
Department of Electrical Engineering
The Ohio State University
Columbus, OH 43210-1272, USA
e-mail: bwang@ee.eng.ohio-state.edu
voice: +1 614 292 3430
Yao-Min Chen
Fujitsu Labs of America
595 Lawrence Expressway
Sunnyvale, CA 94086-3922, USA
e-mail: ychen@fla.fujitsu.com
voice: +1 408 530 4513 Fax: +1 408 530 4518
Hou et al. Expires 30 September 1999 [Page 26]
