[Search] [txt|ps|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
INTERNET-DRAFT                              Anindo Banerjea (U. of Toronto)
Inter-Domain Multicast Routing           Michalis Faloutsos (U. of Toronto)
Expires: October 1998                             Rajesh Pankaj (QUALCOMM)
File: draft-banerjea-qosmic-00.txt



            Designing QoSMIC: A Quality of Service sensitive
               Multicast Internet protoCol


STATUS OF THIS MEMO

This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, and
its working groups. Note that other groups may also distribute working
documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet- Drafts as reference material
or to cite them other than as "work in progress."

To view the entire list of current Internet-Drafts, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on

ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it
(Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East
Coast), ftp.isi.edu (US West Coast).


ABSTRACT

 We present, QoSMIC, a multicast protocol for the Internet that
supports QoS-sensitive routing, and minimizes the importance of a priori
configuration decisions (such as core selection). The protocol is
resource-efficient, robust, flexible, and scalable. In addition, our
protocol is provably loop-free.

Our protocol starts with a resources-saving tree (Shared Tree) and
individual receivers switch to a QoS-competitive tree (Source-Based
Tree) when necessary. In both trees, the new destination is able to
choose the most promising among several paths. An innovation is that we
use dynamic routing information without relying on a link state exchange
protocol to provide it. Our protocol limits the effect of pre-
configuration decisions drastically, by separating the management from
the data transfer functions; administrative routers are not necessarily
part of the tree. This separation increases the robustness, and
flexibility of the protocol. Furthermore, QoSMIC is able to adapt
dynamically to the conditions of the network.

The QoSMIC protocol introduces several new ideas that make it more
flexible than other protocols proposed to date. In fact, many of the
other protocols, (such as YAM, PIM-SM, BGMP, CBT) can be seen as special



Expires October 1998                                            [Page 1]


Draft                The QoSMIC Multicast Protocol            April 1998


cases of QoSMIC. The goal of this document is to present the motivation
behind, and the design of QoSMIC, and to provide both analytical and
experimental results to support our claims.


NOTE: The text version of the draft is missing several figures, that
facilitate the understanding of the work.  For this, the authors suggest
the postscript version.




Contents

1 Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Model Definition and Background Work 6

2.1 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . 8

3 Overview 9 4 Detailed Description 11

4.1 The Search for Candidates . . . . . . . . . . . . . . . . . . 11
4.2 Connection Establishment . . . . . . . . . . . . . . . . . . .14
4.3 Leaving a Group . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Candidate Selection. . . . . . . . . . . . . . . . . . . . . .15
4.5 Manager and Inter-domain Issues . . . . . . . . . . . . . . . 17

5 The Control Overhead 18 6 Experimental Results 21

6.1 Routing Efficiency . . . . . . . . . . . . .. . . . . . . . . .22
6.2 Overhead Complexity . . . . . . . . . . . . . . . . . . . .  . 23

7 Implementation Details 25

7.1 Intree Router State . . . . . . . . . . . . . . . . . . . .  . 25
7.2 Router Actions . . . . . . . . . . . . . . . . . . . . . . . . 27

7.2.1 Joining a session . . . . . . . . . . . . . . . . . . . . . .27
7.2.2 Leaving a Group . . . . . . . . . . . . . . . . . . . . . . .28
7.2.3 The TAKE-OVER procedure. . . . . . . . . . . . . . . . . . . 28
7.3 Source Specific State . . . . . . . . . . . . . . . . . . . .. 29

8  Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 30
A Efficiency Parameters of Multicast Protocols  . . . . . . . . .  33



1 Introduction

Multicasting can be defined as the distribution of the
same information stream from one to many nodes concurrently. In the last
few years, multicast routing has attracted a lot of attention from the



Expires October 1998                                            [Page 2]


Draft                The QoSMIC Multicast Protocol            April 1998


networks community, since many emerging applications are of multicast
nature, such as teleconferencing, tele-education, and computer supported
collaborative work. A multicast connection can substitute for many
unicast connections carrying the same information, while reducing the
load on the network. Multicast algorithms try to minimize the routing
cost of the tree, which forms the simple multicast routing problem, or
Steiner tree problem [24]. In practice, the applications and practical
constraints complicate the problem with additional requirements [7].

The Internet is a packet-switching network that principally provides
best-effort service. That is, there are no guarantees for the services
and applications that run over it; applications may "starve", end-to-end
delays may be arbitrary, and packets may be lost. Traditional Internet
routing protocols do not consider Quality of Service (QoS) metrics. For
the support of multicast connections, a multicast backbone (MBone) was
introduced as a virtual network "on top" of the Internet [9] in 1992.
The MBone is expected to be phased out, as the routers in the Internet
become multicast capable. In the rest of this document, we use the term
router to imply a "multicast capable Internet router", unless otherwise
stated.

Our work is motivated by the need to support QoS-sensitive multicast
applications. The marketability of any kind of service depends heavily
on its ability to to provide a level of quality. Currently, the services
over the Internet are limited by the best-effort nature of the network.
However, the scope of our work extends beyond the current use of the
Internet to a fully-commercialized environment with competing service
providers. We are convinced that such commercial services will need to
guarantee their QoS, and that some users will be willing to pay to have
such guarantees.
In addition, QoS in multicasting is not as problematic as in
point-to-point connections. The reason is that in multicasting we keep
anyway connection specific state in routers. Thus, adding QoS
connection specific information is straightforward and increases
the routing state only by a constant.

A multicast protocol that considers QoS in its routing phase can create
a tree better suited to the needs of QoS-sensitive applications.
However, the straightforward approach of exchanging dynamic link-state
metrics to compute QoS based routes does not scale to large networks. We
can distinguish two categories among Internet multicast protocols based
on QoS considerations: QoS-oblivious protocols [1] [10], [19] [17]; and
QoS-sensitive
protocols [3] [25]. An overview of the above protocols is presented in
the next section.

Our protocol was designed with the following primary goals [27].



Expires October 1998                                            [Page 3]


Draft                The QoSMIC Multicast Protocol            April 1998


 1. QoS Support. We want to provide a framework to support arbitrary
QoS requirements of users. To achieve this, we have to consider multiple
paths, and handle the link asymmetry, e.g. for satellite connections.
Note, that multiple paths can also be necessary for policy reasons. ffl

 2. Limited Impact of Pre-configuration Decisions. We want to limit the
impact of any a priori configuration decisions, such as the choice of
special status routers (PIM-SM, CBT, and BGMP), or a special
partitioning of the multicast address space (BGMP [19] [12]).

In our effort to propose an improved protocol, we identified a group of
weaknesses of some of the current and proposed MBone protocols. We
transformed this group into the following list of secondary design
guidelines.

1. Efficiency. Our protocol should construct distribution trees that use
the network resources efficiently.

2. Application sensitive. It should accommodate diverse applications
types with minimal user input.

3. Scalability. It should scale well for large networks, many groups, large
group-sizes etc

4. Robustness. It should be robust to failures, even of special status
components, e.g. core routers. 5. Loop-freedom. It should not create
cycles.

Our protocol constructs trees based on a greedy heuristic [18], that
connects each user to the "closest" branch of the existing tree and
leads to efficient resource use. Using the greedy approach, our protocol
offers alternate paths to enable the support of QoS requirements. The
protocol uses dynamic routing information, without assuming an
underlying protocol to provide it. Another innovation is that our
protocol does not require pre-configuration decisions; its efficiency
does not depend on the selection of a special status router, or a
special partitioning of the multicast address space. Finally, our
protocol can be seen as a flexible framework that encompasses the
behaviour of most of the previous protocols, when sensitivity to QoS is
not required.

The rest of this document is structured as follows. In Section 2, we
present our model and related work. Section 3, we present an overview of





Expires October 1998                                            [Page 4]


Draft                The QoSMIC Multicast Protocol            April 1998


 our protocol, while in Section 4, we offer a more detailed description.
 In Section 5,
we compare the resource and control efficiency of our protocol with that
of other protocols. Section 6 provides some simulation results
concerning resource and message efficiency. In Section 7, we present
some implementation details of our protocol. In Section 8, we summarize
our work.

2 Model Definition and Background Work

Conceptually, the structure of
the Internet can be decomposed into three levels (see Fig.1). The
workstations (hosts) of the users are connected to a Local Area Network
(LAN) such as Ethernet. Each LAN has a Designated router which
communicates directly with each host using the Internet Group Membership
Protocol (IGMP) [6]. This is the first or LAN level. We use the term
Destination to refer to the designated router that has a group member in
its LAN. The designated router is connected with other routers forming
domains, which is the second or intra-domain level. The domains are
interconnected with routers that are called Border routers. The network
of domains is the third or inter-domain level. This creates a three
level hierarchy that allows the co-existence of different technologies
and facilitates the scalability of the network. We can have different
protocols at the intra-domain and inter-domain levels, as long as they
can interoperate. Routing at the inter-domain level imposes more
restrictions due to scalability considerations. Our protocol could be
used in both levels. It is flexible enough to adapt to the needs of
different environments, and scales well in the inter-domain case.

A multicast group is associated with a Class-D or multicast address. A
host knows the address of the group it wants to join through an
advertising or query mechanism such as the Session Description Protocol
(SDP) [15]. A multicast group can have multiple sources and the
distribution of the packets can be done in two ways. First, each source
can create its own distribution tree, called a Source-Based Tree, with
itself as the root. Second, all sources can distribute their packets
using the same tree, called a Shared Tree. Source-Based Trees have
better end-to-end performance (e.g. lower delay), and distribute the
traffic of each group across the network, but lead to large routing



Expires October 1998                                            [Page 5]


Draft                The QoSMIC Multicast Protocol            April 1998







tables [2] [23].
[NOTE: Source-Based Trees require a routing entry per source per group, while
Shared Trees require a single routing entry per group.]
 On the other hand, Shared Trees concentrate the
traffic of a group onto a few links in the network. This concentration
is bad in the case where all sources are active simultaneously (e.g.
Distributed Interactive Simulation), but it can be beneficial when
sources take turns in transmitting (e.g. audio-conferencing). The two
approaches have complementary behavior, and are both useful in different
situations.

The efficiency of a multicast protocol can be defined by set of
functional properties. End-to-end delay and setup time are properties of
interest to the application, while traffic concentration, packet
replication, routing state and control overhead are important to the
service provider. Scalability of the above properties to large networks
is an overriding concern for protocol and network architecture design.
In Appendix A, we present an extended list of the efficiency aspects of
protocols.

In our protocol, we compare paths in terms of their ability to support
an application at a specific QoS level. Quality of Service (QoS) denotes
the user-perceived quality. Recently, Zappala et al. [25] used the term
Quality of Route (QoR) to refer to multiple static parameters of the
route (e.g. link capacity, delay, or reliability), and this was adopted
in the YAM protocol [3] (In a private communication, the authors  stated
 that they have also been considering the use of dynamic information.).
 In our work, we suggest the use of dynamic
metrics, (e.g. available bandwidth, current delay), because these
provide paths that can meet QoS requirements at a given moment.
Furthermore, routing with dynamic metrics can respond pro-actively to
link congestion. However, exchange of dynamic link-state metrics has
scaling problems. Thus, we do not require the use of dynamic metrics in
the link state exchange protocol. Dynamic metrics are used instead to
evaluate and select from the alternate paths proposed by our protocol.
This distinction will become more clear after the protocol overview. To
summarize, our protocol enjoys the benefits of QoS routing,
without suffering from the scalability restrictions.



For the rest of this document, the term "QoS of a route" denotes the
quality that the route is expected to deliver to a connection given its



Expires October 1998                                            [Page 6]


Draft                The QoSMIC Multicast Protocol            April 1998


current state, and is calculated from dynamic metrics of properties such
as bandwidth or delay. However, the terms "distance" and "proximity" for
routers are defined using static metrics of the same properties. It is
important to stress that our protocol is compatible with any metric of
the routing quality of a path, and the specific metric to use is
application dependent.

2.1 Previous Work

 QoS-oblivious protocols. These protocols provide one
route when a new member joins, and QoS is not considered in the
selection of the route. Example of such protocols are Core Based Trees
(CBT) [1], Protocol Independent Multicasting - Sparse Mode (PIM-SM)
[10], Border Gateway Multicast Protocol (BGMP) [19], and Multicast
Internet Protocol (MIP) [17]. All these protocols assume rooted trees,
with a core router which is the center of the distribution tree. BGMP
and MIP imply the use of rooted trees. In BGMP, for example, each
domains "owns" an address space and is the root of the distribution tree
with such an address. In all these protocols, the tree is the union of
the reverse shortest paths between the core and each destination.
Reverse shortest paths are used because they can be computed from the
unicast routing database without requiring additional information. CBT
creates only Shared Trees while PIM-SM and BGMP, permit the creation of
Source-Based Trees for very active sources (high data rate). The MIP
protocol introduces novelties on administrative and correctness issues,
and guarantees loop-free Shared Trees and Source-Based Trees. The
assumption of rooted trees simplifies routing, but introduces the core
selection [20] and address partitioning [12] problems, which can affect
the protocol performance significantly.

QoS-sensitive protocols. These protocols offer multiple routes to a new
member, who selects the best such path. Carlberg and Crowcroft [3] [4]
suggested the YAM protocol, which creates Shared Tree considering
multiple routes. The destination router searches its neighborhood and
finds routers that are part of the tree of the desired group. This way,
the new router selects the most promising route. Routing in YAM relies
mainly on this neighborhood search, but this procedure can increase the
control overhead significantly. A suggested method to address this
problem requires a sense of source/root domain, which is not applicable
in Shared Trees unless we assume an address partitioning mechanism.
Zappala et al. [25] suggested
a multicast protocol that provides alternate routes to avoid a
bottleneck link. This protocol does not seem applicable in the case
where QoS suffers from several mildly-congested links. Finally, both
protocols use only static routing information, which can lead to poor
QoS performance3. An analogy from real life is driving: when we drive we
want to have the option of multiple routes, but also we want up to date



Expires October 1998                                            [Page 7]


Draft                The QoSMIC Multicast Protocol            April 1998


information of the traffic on each of them. Following small streets is
faster than driving on a congested highway.

The YAM protocol can be seen to implement the greedy heuristic. The
greedy routing scheme has been shown to outperform the commonly used
Shortest Paths routing in various analytical [18] [16] [13] and
experimental [21] [8] [22] studies. On average, the studies suggest a
10-30% advantage of the greedy approach in the efficiency (cost) of the
distribution tree.

3 Overview

[**]
Figure 2: An overview of QoSMIC.

 Our protocol creates Shared Trees by
default and Source-Based Trees when needed. In both cases, the protocol
offers alternate paths for each connection (see Fig. 2(a)).

We introduce the notion of a Manager router of a group. The Manager
administers a specific multicast group, and facilitates the joining of
the new group members. The fundamental difference between a core router
and a
Manager is that the distribution tree is not rooted at the Manager. This
way, the selection of the Manager has marginal effect on the topology of
the tree. Furthermore, we can have multiple Managers and change the
Managers during the lifetime of the group without any data loss, as we



Expires October 1998                                            [Page 8]


Draft                The QoSMIC Multicast Protocol            April 1998


will see later in this section.

Joining a group. The Designated router of the new member, which we call
New router, will try to connect to the most promising path to the tree,
according dynamic metrics defined by the application. The New router
identifies several intree routers as Candidates or potential points to
join to the tree. This search is conducted by two procedures: one from
the side of the New router (Local Search), and one from the side of the
tree (Multicast Tree Search) (see Fig.2.b), both operating in parallel.
For the moment, we consider a purely intra-domain or purely inter-domain
scenario.

1. The Local Search Procedure. The New router searches its neighbor
hood, using a reverse path multicast of probe messages, with scope
limited by use of the time-to-live (TTL) field for its closest intree
router. Every intree router that receives the probe message is
considered a Candidate router, and responds with an "advertisement
message" unicast to the New router. This procedure is also used in the
YAM protocol.

2. The Multicast Tree Search Procedure. The New router contacts the

Manager router of the group, and the Manager router "informs" the tree
of the New router. Some intree routers are selected as Candidates. They
advertise themselves to the New router with a unicast "advertisement"
message. In the next section, we propose several mechanisms, centralized
and distributed, to select Candidates.

Eventually, the New router compares all the possible connection paths,
and selects the best path according to the needs of the application. The
New router sends one more message (JOIN) towards the selected Candidate,
to set up the routing state along the path and the chosen router starts
forwarding the data. The routing state is soft-state, but pinned, so
that as long as the New router keeps sending JOIN refreshes, the route
does not change. It should be clear from the above description that our
protocol implements a greedy routing heuristic.

The path chosen by the advertisement messages depends on the static QoR
metrics contained in the routing information base. The specific metric
used by the routing protocol depends on the needs of the application.
For example, real-time applications will prefer paths of minimum end-
to-end delay, while data transfers may prefer paths of maximum bandwidth
 or low
packet loss ratio. Current routing protocols already have the ability to



Expires October 1998                                            [Page 9]


Draft                The QoSMIC Multicast Protocol            April 1998


carry multiple static metrics.

However, the advertisement messages can collect up-to-date dynamic QoS
metrics along the path that they travel (e.g, by interacting with RSVP
[26], or using measurement based metrics). Thus, although the paths that
the Candidates choose is restricted by the static information in the
routing information base, the New router selects among these paths using
dynamic routing information.

Source-Based Trees. Using Shared Trees minimizes the routing table
information to an entry per group. However, Shared Trees may fail in the
following two cases. First, when a group has many highly active sources
simultaneously, the bandwidth of the shared links may not be able to
accommodate all the traffic. Second, when the QoS requirements of a user
are not met along the Shared Tree, we have to find a different source-
to destination path. In both these cases, we resort to Source-Based
Trees. The switch from a Shared Tree to a Source-Based Tree of a
specific source is initiated by the Designated router of a receiver. The
procedure for establishing the Source-Based Tree is similar to the
procedure of the Shared Tree and uses the Local Search and the Multicast
Tree Search procedure to identify routers in the Source-Based Tree. To
avoid packet duplication, the Shared Tree is pruned on a source-specific
basis, for the sources for which Source-Based Trees have been
established. More details for the co-existence the two types of trees is
provided in Section 7.

4 Detailed Description

 In this section, we describe the messages and
mechanisms used by our protocol in detail. After that, we explain the
process of Candidate selection, Manager selection, and interdomain
operation. Table 1 lists the different roles of the routers. Table 2
contains a list of the protocol messages.

4.1 The Search for Candidates

We assume that the New router receives a
request to join a multicast group. To simplify the presentation, we
assume that the new member is a receiver4.

A source joins a group in a way similar to a receiver; it connects to
the closest router of the Shared Tree. A difference is that the dynamic
metrics of the path are collected "towards the tree", i.e., in the
direction the data will flow.

Table 1 --  START

Router Name  ---  Role

  Manager router: Supervises the group and facilitates the
joining procedure; does not necessarily participate in the
data distribution tree.

Candidate router: Considered as possible joining point for a new



Expires October 1998                                           [Page 10]


Draft                The QoSMIC Multicast Protocol            April 1998


connection.

 Designated router:  Connected to a set of users (e.g. LAN),
receives requests
from users (e.g., using IGMP) and initiates searches.

 New router: Designated router of the LAN containing the new member.

 Destination router: Designated router of a LAN that has active group
 members.

Intree router: All routers that are part of the distribution tree.

Intermediate router: Intree router that is not a Destination or a Source.

Border router:  Router that connects multiple domains.

Table 1: The different roles of the routers. -- END

Table 2 --- START

MESSAGE Explanation

BID-REQ: New router searches locally for intree neighbors

BID: Candidate "proposes" to the New router; Message
collects dynamic QoS metrics along the path

M-JOIN: New router contacts the Manager who initiates a
Multicast Tree Search

BID-ORDER: The Manager "orders" the intree nodes to
send bids

JOIN: The New router sends a message up its selected
path to the tree to establish/refresh routing state

PRUNE: Departing Destination tears down unwanted part
of tree; can be for a source or for a group

Table 2: An explanation of the messages of our protocol. --- END



Expires October 1998                                           [Page 11]


Draft                The QoSMIC Multicast Protocol            April 1998

[***]
Figure 3: The Take-Over procedure: an intree router that lies in the
path from the Candidate to the New router can replace the Candidate.

The Join is received via IGMP on a LAN at the intra-domain level, or
from an intra-domain protocol at a Border router at the inter-domain
level. If the New router is part of the group already, the connection is
established locally. If the New router is not part of the group, the
Local Search and the Multicast Tree Search procedures are employed.

Local Search. The New router tries to identify neighboring intree
routers.

1. The New router "floods" a BID-REQ message in its neighborhood.
Reverse path multicasting with scope controlled by the Time To Live
(TTL) field is used to control the message complexity of this phase.
This procedure is the same as proposed in YAM, but because we also have
the Multicast Tree Search, we can keep the final TTL much smaller. This
advantage is quantified later analytically and experimentally. 2. Every
intree router that receives a BID-REQ message, becomes a Candidate
router, and replies with a BID message, which is unicast to the
New router. The BID message on its way collects information on the
expected performance of the path, based on dynamic QoS metrics. The
Candidate router considers the New router as a tentative dependant, and
cannot leave the tree unless the tentative status is timed out.

 3. The New router collects the BID messages. The procedure terminates
unsuccessfully, if the New router does not receive any replies before
the expiration of a timer set for this purpose. Otherwise, we enter the
phase of establishing the connection (see Section 4.2).


Multicast Tree Search. The New router contacts the Manager and the
Manager causes some of the intree nodes to propose themselves as
Candidate routers. The selection of Candidates is an important aspect of
our protocol and it is discussed  later in this section. The sequence
of actions is as follows:

  1. New router sends an M-JOIN message to the Manager of the group.
  2.The Manager "orders" a bidding session with a BID-ORDER message.
Some subset of the routers that receive the BID-ORDER are selected as
Candidates.
  3. The Candidates unicast BIDs to the New router. The BIDs
are identical to the BIDs in the Local Search.



Expires October 1998                                           [Page 12]


Draft                The QoSMIC Multicast Protocol            April 1998


For both the Local and the Multicast Tree Search, if an intree router
receives a BID message (for the same tree), the router takes the place
of the Candidate by "dumping" the original BID and initiating a new BID
message in a procedure called Take-Over (see Fig. 3). This is important
to prevent multiple copies of packets. If a router with tentative state
(i.e., one that has received a BID but not yet established a
connection), receives a BID for the same (tree, New router, Candidate),
the BID is discarded to maintain loop freedom.

4.2 Connection Establishment

Having performed the BIDding phase, we will
examine how the connection is established.

  1. The New router selects the best Candidate according to the dynamic
QoS metrics collected by the BIDs.
  2. The New router sends a JOIN message to its best BID. This message
traverses in the opposite direction the path used by the BID message,
and establishes soft state along the path.
  3. When the chosen Candidate receives the JOIN message, it changes
state to the connected state, and starts transmitting data packets on
the newly set up path.
  4. If an intree router receives a JOIN message
for a different Candidate,
it performs a TAKE-OVER, terminates the message and starts forwarding
data on the newly set up path.


4.3 Leaving a Group

 A Designated router receives a leave request through
the same protocol that communicated the join request. The request can be
for a whole group or for a source of a group. Whenever a router senses5
a change in the membership, it removes the link from the distribution
tree, and checks whether it has become a leaf of the related tree. If
so, it sends a PRUNE message up the tree and removes state for the tree
from its database, thereby ceasing to be an intree router for that tree.

4.4 Candidate Selection.

 During the Multicast Tree Search, the Manager
must select an appropriate subset of the intree routers as Candidates.
This can proceed in a centralized or a distributed way.

  1. Centralised Selection. If the Manager has sufficient knowledge of the
tree and the network topology, the manager can select the set of
Candidates directly. This can happen if the domain is running a link
state protocol, or if the manager has access to a routing information
database. In this case, the Manager identifies promising Candidates,



Expires October 1998                                           [Page 13]


Draft                The QoSMIC Multicast Protocol            April 1998


either on demand or statically. Then, the Manager unicasts the BIDORDER
to them. If the selection is based on accurate information, we can find
the right Candidates with limited overhead cost. Note, that with this
mechanism, our protocol can behave like CBT or BGMP; a Manager can
trivially act as a core router by considering itself as the only
Candidate.
  2. Distributed Selection. In the absence of centralized
information, each
intree router has to decide whether to become a Candidate in a
distributed way. We assume that each router has a static estimate of its
distance to the New router. We have the Manager join the tree as a
source6 and multicast the BID-ORDER along the tree
(Note, that this does not contradict the flexibility of the role of the
Manager, since
it only transmits control messages and receives nothing. For example,
the Manager can change without disrupting the data distribution.).
 All intree routers
receive the BID-ORDER and decide in a distributed way if they should
become Candidates. Naturally, the more intree routers become Candidates,
the more "accurately" we find the closest Candidate to
the New router, but the more the control overhead. We propose the
following orthogonal mechanisms that can be used in combination to
strike the balance in this trade-off.

(a) Directivity. We discourage distant routers from becoming Candidates.
The BID-ORDER keeps track of the (so far) minimum distance of
the tree and the New router. A router with a distance greater than this
minimum does not become a Candidate, and, if the relative distance
exceeds a threshold, the BID-ORDER is not forwarded further.
(Note that a similar mechanism appears in YAM [3], but it is used to
reduce the overhead of its Local Search. YAM needs to assume rooted
trees for this).

(b) Local Minima. In absence of global knowledge, we select locally
optimal routers as Candidates. As the BID-ORDER message travels along a
branch, the distance to the New router of the previous two routers is
included in the message. If router i + 1 sees that router i was closer
to the destination than both routers i+1 and i- 1, it sends a
message back to router i, which becomes a Candidate.

(c) Fractional Choice. We can choose as Candidates a representative



Expires October 1998                                           [Page 14]


Draft                The QoSMIC Multicast Protocol            April 1998


fraction (1/n) of either all intree routers or the ones that meet the
other two criteria. For the implementation, we only need a log n-bit
wrap-around counter in the BID-ORDER message.

Choice of Mechanisms. We identify combinations of the previous
mechanisms that seem more promising. The final choice will have to
consider the network topology and the traffic behavior. Some preliminary
analysis is presented in Section 5. More detailed simulation studies are
needed in this direction.

If topology information for the entire domain is available, Manager
Selection offers the lowest control overhead for a reasonable selection
of Candidates. In the absence of such information, Fractional Choice and
Directivity together is simple to implement, and may lead to
satisfactory solution with a careful choice of parameters. Local Minima,
Fractional Choice and Directivity is more sophisticated and promises
improved results, but we want to determine if the gain justifies the
slightly increased complexity.





4.5 Manager and Inter-domain Issues

Manager Address Distribution. For the Multicast Tree Search,
the New router needs to know the address of
the Manager and of the group and both addresses can be made known
through the same mechanism (e.g. Session Directory tool [15]).
Alternatively, the address of a local Manager within a domain can be
broadcasted via the Domain Wide Reporting [14] or can be provided on
demand (by the Border routers or an administrative database).

Manager versus Core Router. The main purpose of the Managers is to
invoke the Multicast Tree Search. Since Managers are not key routers for
data distribution, we can replace a Manager during a session by simply
advertising a new Manager. In contrast to a core change, a Manager
change does not cause any data loss or any change in the distribution
tree. For a smooth transition, the old Manager can "resign", after the
new Manager has been around for a sufficiently long time (depending on
the size of the network).

Multi-Domain Multi-Level Operation. Our protocol can be used at both the
intra-domain and the inter-domain level. If the domain already has
active group members, the search for Candidate routers is carried out
within the domain. If not, the connection has an intra-domain and an
interdomain part. Inside the domain, the New router contacts one or more
Border routers. The Border routers find their best path to the group at



Expires October 1998                                           [Page 15]


Draft                The QoSMIC Multicast Protocol            April 1998


the inter-domain level. If the inter-domain protocol is QoSMIC, then the
Border routers initiate searches using the procedures of QoSMIC. Each
Border router that finds a path to the tree proposes itself to the New
router (BID message). The New router chooses the "best" Border router.
The selected Border router becomes the Designated Border router for this
group (or Source-Based Tree). Finally, if one of the levels is running a
different protocol, an interface similar to that in [19] will allow
interoperation.

Selecting Manager Routers. In practice, we want to have multiple
Managers that will co-operate for efficient and scalable solutions with
reduced set-up time. For this we have concluded in the following scheme.
We have at least one Manager per domain. This way the intra-domain and
inter-domain protocol can be independent. We prefer Border routers for
Managers. This way, the Manager can communicate with routers inside and
outside the domain more easily. Thus, by default, we select the
Designated Border router of the group to be the Manager in a domain. In
the creation of a session, the Border router nearest to the session
initiator becomes the Designated router. For a domain that joins the
distribution tree, the selection of the Designated router was described
in the previous paragraph.

Table 3 -- START
Symbol:  Explanation

t: The maximum TTL value of the Local Search
c: The number of Candidates
w: The average degree of a router
T: The average size of a multicast tree
Hop(a; b): The average distance in hops from a to b
Hop_avg:  The average hop distance between Manager and Candidates
Join(c): The message complexity of the joining part with c Candidates

Table 3: Analysis parameters and their symbols.

For a Source-Based Tree, we select the source as the Manager in its own
domain to simplify the administration of the tree. It is important to note
that these choices are the default ones, but as the execution progresses, we
can change to more appropriate Managers without any service disruption.


5 The Control Overhead

 We compare the control overhead of  YAM and
QoSMIC with analytical methods. We do not consider other protocols,
since they do not try to achieve QoS and resource optimized trees. Table
3 lists the parameters and their symbols. Most of these parameters
depend on the topology and the membership behavior of the applications.
In Table 3, the first two parameters can be altered by the protocol; t
depends on protocol decisions solely in all cases, while c, the number
of Candidates for the Multicast Tree Search is directly defined by the
protocol for the centralized case, and indirectly controlled for the



Expires October 1998                                           [Page 16]


Draft                The QoSMIC Multicast Protocol            April 1998


distributed cases. Note that the protocol can modify its parameters
during the life-time of the group, and this accounts for the
adaptability of our protocol.

The Complexity of Selecting Candidates. The Local Search. Assume w to be
the average degree of a router. For simplicity, we consider only one
search with the a maximum TTL value of t. We consider the complexity to
be a function of the t, since the average degree, w, is given. In a
broadcast, a router that receives a message will forward it to w Gamma
1 links on average. Assuming a reverse path multicasting method, every
router in the neighborhood receives such a message exactly
once. This way, the complexity8 of the Local Search with one expanding
search is as follows

Local(t) = w *(w-1)^(t-1)

While for multiple expanding rings the complexity becomes

Local(t) = Sum_[i=1 to t] w * (w-1)^i

Since YAM depends entirely on the Local Search to find the Candidates,
we can assume that YAM will need to perform expanding rings search to
keep the complexity under control, while QoSMIC can perform a single
search with a small t, which explains the complexity difference in Table
5.



Expires October 1998                                           [Page 17]


Draft                The QoSMIC Multicast Protocol            April 1998


The Multicast Tree Search. This procedure exists only in QoSMIC, and can
differ depending on which Candidate mechanism is used. The complexity is
c  Centralised mechanism and loosely upper bounded by the size of the
tree, jT j, in the distributed mechanisms. In more detail, Table 4
demonstrates the complexity of the selection procedure and the relative
advantages for each of the four Candidate mechanisms we saw earlier.

The Complexity of Joining. In any case, the joining overhead is low
compared to the overhead of the search. Assume we have c Candidates.
Each of them sends a BID message to the New router. The New router sends
a JOIN message to one selected Candidate. The associated complexity
is approximately the same in both YAM and QoSMIC
as long as the number of candidates selected is kept roughly equal.

We compare the performance of the selection of Candidates in QoSMIC and
YAM protocols according to: the message complexity of searching, the
type of the selection, the information used in the selection. The
comparison is shown in Table 5. In terms of messages, QoSMIC can reduce
drastically the complexity given that it can rely on the Multicast Tree
Search procedure. In the centralised case it can be limited arbitrarily
(down to one Candidate),

[NOTE We calculate an upper bound of the complexity based on the average
degree of a the graph. A more precise bound would depend on the
topological properties of the graph. Such a study extends beyond the
scope of this document.]





Expires October 1998                                           [Page 18]


Draft                The QoSMIC Multicast Protocol            April 1998


[**]
Table 4: Comparing the four Candidate selection methods in the Multicast
Tree Search.

[**]
Table 5: A comparison of the search procedures of QoSMIC and YAM.
Adaptable complexity type means that during the execution the protocol
can limit the overhead control while still offering at least one path
per join.

Table 6  -- START

Symbol: Protocol: Comments

Offline: -- : The off-line greedy algorithm used for reference
QoSMIC: QoSMIC, YAM: Greedy on-line using minimum cost join path



Expires October 1998                                           [Page 19]


Draft                The QoSMIC Multicast Protocol            April 1998


RSP:  PIM-SM, CBT, BGMP: Reverse Shortest Paths using a hop metric.

SP :   --         : PIM-SM, CBT, BGMP could do Shortest Paths routing.

Table 6: The protocols in our simulations. --- END

 and if necessary, we can also
dispense completely with the Local Search. In the distributed case the
Multicast Tree Search complexity is upper bounded by the size of the
tree. YAM relies uniquely on the Local Search procedure whose extent
should be large enough to reach the tree, and thus
we claim that the Local Search of YAM is more expensive.

6 Experimental Results

 We study several aspects of our protocol through
simulations. Here, we present only two of our studies. We compare the
resource efficiency of the greedy routing scheme (YAM and QoSMIC) with
the Shortest Paths routing scheme of other protocols. We also examine
the overhead complexity of the Local Search, which dominates the
overhead complexity of YAM and QoSMIC. Other parameters necessary to
complete the efficiency profile of a protocol are end-to-end QoS, set-up
delay, traffic concentration and robustness.

We vary two parameters in the experiments. The group density (Grp) is
defined as the ratio of the group size over the network size (both
measured in nodes). The maximum asymmetry A is defined as the maximum
ratio of the opposite edges between a pair of routers, for all such
pairs. Naturally, for A = 1, we have an undirected graph. For each
figure, we supply the values of these two previous parameters.

For our network, we use the map of the major routers of the MBone in May
1994 produced by Casner [5]. This graph is appropriate for our
experiments, since it represents an actual instance of the inter-domain
multicast network. We eliminate routers with only one incident edge,
since such routers do not affect routing. We create a directed version
of the map replacing its unidirectional edge with a pair of directed
edges which we call opposite edges. The final graph has 32 routers, 80
pairs of opposite edges, and average degree of 2:5 .


For QoS-sensitive routing, the model should consider more than just a
hop metric. We need to include the notions of QoS performance of links
and of asymmetry (e.g. satellite links). For this reason, each link is
associated with a cost; a higher cost can be interpreted as congestion
or low QoS ability of the link. In our simulator, we initialize the cost
of each pair of directed links to a constant and then introduce
uniformly distributed asymmetry between 1 and A. Naturally, the cost of
a tree is the sum of the cost of its edges.

The protocols we simulate are presented in Table 6. We present



Expires October 1998                                           [Page 20]


Draft                The QoSMIC Multicast Protocol            April 1998


measurements of the path lengths of a new branch and the efficiency of
the distribution tree. More accurately, we focus on the Shared Tree that
is created between one core (PIM, CBT) or one source (YAM, QoSMIC, BGMP)
and a set of receivers. Recall that PIM, CBT, BGMP create their Shared
Tree using the reverse shortest paths (receiver towards source) based on
the hop count metric that we denote by RSP. We use hop counts rather
than the cost metric for RSP, because that is what these protocols do,
and also because it is better than using the actual cost in the wrong
direction in an asymmetric link. However, we think that these three
protocols can easily become cost and direction sensitive, which would
correspond to the the Shortest Paths approach (SP).

In creating a session, we choose the participants and the core/source
randomly. We start from the core/source and add one receiver at a time.
We run every experiment 45 times to smooth the irregularities of special
cases. The 95% confidence interval was roughly within 5% of the plotted
value, and it is displayed when this does not clutter the figure.

6.1 Routing Efficiency In Figure 4, we study the cost of the
distribution tree of the different protocols. Figure 4(a) shows the tree
cost versus the group density for an asymmetry of ten. In Figure 4(b),
we plot the tree cost versus the maximum asymmetry for a group density
of 18%. Given the uniform distribution of the asymmetry, the average
asymmetry is (A + 1)=2 , A=2. Based on these figures, we make the
following observations.

QoSMIC and YAM create more efficient trees. The greedy routing of QoSMIC
and YAM outperforms SP by up to 20% (Fig.4(a)) and RSP by up to 60%
(Fig.4(b)), in agreement with previous literature (see Sec.3).

Direction-aware routing is crucial. In asymmetric environments the
awareness of the data flow is significant. The direction-aware Shortest
Paths approach, SP, outperforms RSP by as much 42%. This suggests that
the




Expires October 1998                                           [Page 21]


Draft                The QoSMIC Multicast Protocol            April 1998


[**]
(a) Tree Cost versus group density (b) Tree Cost versus maximum
asymmetry
 Figure 4: Routing Efficiency relative to the Offline multicast
tree.

PIM, CBT, BGMP can benefit greatly from a consideration of the directed
cost.

6.2 Overhead Complexity The complexity of Local Search depends on the
TTL value, which should be at least as large as the expected hop-
distance between the New router and the closest point to the tree. In
Figure 5, we study the paths that QoSMIC and YAM use for their joins. In
Figure 5(a), we plot the average path length versus the group density
for a symmetric network. In Figure 5(b), we plot the distribution of
paths according to their length in a symmetric network for groups up to
half the size of the network. For comparison, we plot the path
distribution of SP. We extract the following two conclusions.

Using Local Search pays off. In Figure 5(a), path length reduces quickly
as the group density increases. This way, the Local Search can be useful
even for relatively sparse groups. This is supported also by the
evidence in Figure 5(b): more than 50% of the paths (first two columns)
have length less than 2. Therefore, we conclude that a Local Search even
with a small TTL value can be beneficial.

The importance of Multicast Tree Search. In Figure 5(b), we see that a
small percentage of the paths have lengths as large as 8. If we rely
uniquely on the Local Search (as YAM does) then the TTL of the search
should be at least as large or else some routers would be excluded from
some





Expires October 1998                                           [Page 22]


Draft                The QoSMIC Multicast Protocol            April 1998


[**]
(a) Average path length versus group density. (A = 1; Grp = 1 Gamma
100% )
(b) The number of paths versus the path length (A = 1; Grp = 3 Gamma
50%)
Figure 5: The path length of a new join for QoSMIC.

 distant multicast
sessions. This suggests that Local Search alone would need large TTL
values, which increases the overhead complexity significantly.

As a conclusion, we want to have a limited Local Search to take
advantage of the many "short" joins, but we need a second search
mechanism to provide solutions when the Local Search falls short. For
this environment, a single Local Search of 2 hops seems a reasonable
choice for QoSMIC, while YAM would have to go up to 8.

Scalability of message complexity. Using data from our simulations, we
calculate of the overhead of the searches of YAM and QoSMIC using the
analysis of Section 5. Namely, from the experiment of Figure 5(b), we
get the number of joins, and the distance of the node from the tree.

YAM: The maximum TTL of a Local Search should be at least as large as
the maximum path length or else some routers would be excluded from some
distant multicasts. Thus, the maximum TTL is set equal to the path
length of the join. We increase the diameter of each expanding ring by
one. This way, although the set-up delay may suffer, we attempt to
minimize the message complexity of YAM.




Expires October 1998                                           [Page 23]


Draft                The QoSMIC Multicast Protocol            April 1998


QoSMIC: The Local Search does not have to succeed for every join, since
we have the Multicast Tree Search to fall back on. This way, we choose a
maximum TTL value of 2, as suggested earlier. In addition, we over-
estimate

[**]
Figure 6: The control overhead of the Candidate search in YAM and
QoSMIC.

the messages of Multicast Tree Search by considering it equal to the
number of intree nodes. However, using the mechanisms, the number of
messages should be smaller in practice.

In Figure 6, we calculate the message complexity per join for various
average degrees. The message complexity of YAM increases dramatically
with the average degree, due to its large Local Search. In comparison,
QoSMIC avoids this problem: having the Multicast Tree Search to fall
back to we can afford to keep the Local Search small. Similarly, YAM
would suffer from large networks, where the TTL value of the Local
Search would have to be large. As a conclusion, YAM can be applied in
small or sparse networks, but QoSMIC scales well to dense or large
networks.

7 Implementation Details The goal of this section is to highlight some
implementation details of our protocol.

7.1 Intree Router State

For clarity, when we discuss the routing
information of a router, we associate every link with a set of entries
for each group. Note, that we try to use the terminology of the PIM-SM
proposal [10] [11] to facilitate the readers familiar with these works.
Furthermore, some of the actions of our protocol are done in a similar
way to that of PIM-SM and we refer the interested






Expires October 1998                                           [Page 24]


Draft                The QoSMIC Multicast Protocol            April 1998


[**]
Router A Figure 7: The entries at the routing table for Shared Trees,
Source Based trees and their transition. The figure shows the flow of
packets from the source.

reader there.

We can distinguish the following routing entries for each link.

 A (*, G) entry corresponds to the shared tree of a group. By
default, it is bidirectional.

 An (S, G) entry corresponds to a source-based tree of source S of
group G. It is by definition uni-directional, so we can distinguish IN-only
(S, G, IN) and OUT-only (S, G, OUT) entries.

 We enable source-specific pruning that we denote by (not-S, G). A
packet that arrives from a link with such state is dropped. The main
reason is to avoid packet duplication for destinations that have joined
an Source-Based Tree.

We use (*/S, G) as an abbreviation of the expression (*, G) or (S,G).



Expires October 1998                                           [Page 25]


Draft                The QoSMIC Multicast Protocol            April 1998




7.2 Router Actions

Here we study the actions of a router as triggered by control messages.

7.2.1 Joining a session Join request.

The request (*/S, G) can be either to the Designated router (via the
IGMP protocol) or the border router (via an intradomain protocol).

If the router is already part of the requested (*,G) or (S,G) tree, the
join is accommodated there. If not, the router considers itself a
destination router that we denote as New router, and performs the Local
Search and Multicast Tree Search procedures. For the Multicast Tree
Search, the New router sends an M-JOIN(*/S, G, New router) to the
Manager of the group. For the Local Search, the New router broadcasts
BID-REQ(*/S, G, New router, TTL) message in expanding rings. The
messages follow a reverse path multicast. The TTL is initialised to a
value as we saw before. A timer is set to monitor the responses. If the
timer expires before any responses, then a new broadcast (ring) takes
place with an increased TTL. The value of the TTL is bounded by a
default value or is explicitly specified. When the timer expires for the
maximum TTL value, without any responses, the procedure terminates
unsuccessfully.

BID-REQ(*/S, G, New router, TTL) message. On reception of a BID-
REQ(*/S,G) message, a router that is part of the tree in question
replies with a BID message. In a Source-Based Tree, the Candidate
incorporates in the message estimates of the QoS it experiences (quality
of the path from the source to the Candidate), when these are available.
Note, that this way, we can maximize the end-to-end QoS that the New
router will receive. In more detail, the BID message is of the form
BID(*/S, G, New router, Candidate, Metrics): it includes the address of
the Candidate, and estimates of the QoS of the path. The BID message on
its way updates its metrics at each router to estimate the quality of
the path.

MJOIN(*/S, G, New router) message. This message is unicasted to the
Manager of the group. For a (*,G) message, the manager sends BID-
ORDER(*/S, G, bid-mechanism). The "bid-mechanism" represents the
selection mechanisms that we saw earlier. The BID-ORDER can be either
multicasted over the tree, or unicasted to pre-selected routers
depending on the mechanism in use.

BID-ORDER(*/S, G, New router, bid-mechanism) message. The actions on
this message depend on the "bid-mechanism". In general,





Expires October 1998                                           [Page 26]


Draft                The QoSMIC Multicast Protocol            April 1998


the message is either unicasted to the chosen Candidate or multicasted
over the tree. In the first case, on receiving the message, the router
unicasts a BID(*/S, G, Metrics) to the New router. In the second case,
the router examines the criteria defined by the bid-mechanism, and if
they are fulfilled, a BID message is sent to the New router, and the
BID-ORDER is forwarded further along the tree.

BID(*/S, G, New router, Candidate, Metrics) message. On receiving this
message, if the router is the New router specified in the message, it
updates a list of the best BIDs. An intree router invokes the TAKE-OVER
procedure, and the router replace the Candidate. Any other router that
receives a BID message, updates the Metrics field and forwards the
packet.

JOIN(*/S, G, New router, Candidate) message. This message travels
towards the selected Candidate. When the Candidate router receives the
message, it considers the connection as permanent (as opposed to
tentative) and sets-up the path. Any intree router that receives the
message invokes the TAKE-OVER procedure and starts forwarding data.

7.2.2 Leaving a Group

 The leave request (*/S, G) can be either to the
Designated router (via the IGMP protocol), the border router (via an
intradomain protocol), or with a PRUNE message, or the result of state
time out (assuming soft state refresh mechanism). If the request arrived
from a LAN with active group members, the router does not do anything.
In any other case, the link is removed from the distribution tree. Then,
the router examines whether it has become a leaf of the tree.

  1. If the router has become a leaf of the (*/S,G) tree
[Note, that leaf here implies also that the router does not have any
hosts attached to its LAN.], it sends a
PRUNE(*/S,G) message to its only tree link.

  2. If the router has two or more links in the tree (tentative or real),
it does not take any further actions.

7.2.3 The TAKE-OVER procedure.

 An intree router that receives a message
between the Candidate and New router, may be able to take the position
of the Candidate(see Fig. 3). This
could lead to shorter delays and more efficient trees. This interception



Expires October 1998                                           [Page 27]


Draft                The QoSMIC Multicast Protocol            April 1998


can happen in the messages: BID, JOIN.

 * The message is (*, G).

- If the router is in (*, G), then TAKE-OVER. - If the router is in
(S,G), then just forward the message.

 * The message is (S, G).

- If the router is in (S,G), then TAKE-OVER. Optional refinement:
if the current QoS from the source to here is worse than the expected
QoS along the bidding path, then switch to the best path.

- If the router is in (*,G). If the current QoS is not worse than the
QoS of the bidding path, then TAKE OVER. If not, then just forward the
message.

7.3 Source Specific State

 The source-specific pruning is similar to that
of PIM (see Fig. 7). A router that is part of both the (S, G) and the
(*, G) tree, ignores packets from source S that do not arrive from the
(S,G, IN) link. Furthermore, when a router receives an (S,G) packet from
another link (the link that the Shared Tree used for the S-packets), it
sends an S-specific prune message on that link. We denote by (not-S, G)
the state of such a Shared Tree link.

When we switch from the (*, G) to the (S, G) tree (see Fig.7), we want
to minimize the data loss by stopping the reception of packets from the
(*,G) tree only when data starts to arrive from the (S,G) tree. We use a
flag SBTFLAG, which is similar to the SPT-bit of the PIM-SM protocol.
When the request for Source-Based Tree is sent, we install an (S,G,
SBT-FLAG= OFF) entry, but we continue to forward S-packets that we
receive from the (*,G) link. The first data packet from the (S,G) link
sets the flag (SBT-FLAG= ON). When this happens, we drop any S-packets
coming from the (*, S) link, and we send S-specific PRUNE(S) messages
along these links to stop the transmission of the S-packets from the
previous router. This continues recursively along the path that does not
require S-packets anymore.


8 Conclusions

 We propose QoSMIC, a protocol for supporting QoS-sensitive
multicast applications over the MBone. Our protocol identifies multiple
paths, and selects the most promising one using dynamic information that
the control messages collect. Our protocol creates Shared Trees by
default and destinations switch to Source-Based Trees in order to
accommodate the needs of different applications. This switch can take



Expires October 1998                                           [Page 28]


Draft                The QoSMIC Multicast Protocol            April 1998


place for highly active sources or when the QoS requirements of
receivers are not met.

Our protocol includes the main concepts of the YAM protocol [3], and
introduces several new ideas. Below, we list the characteristics of our
protocol that differentiate it from YAM and/or the other protocols.

  1. Limited Impact of Pre-configuration Decisions.
We separate the management from the data transfer functions, by
introducing the concept of the group Manager in the place of the core
router (PIM, CBT, BGMP, MIP). The choice of the Manager does not
affect the distribution tree.  This way we eliminate the problems of
core router selection and the address partitioning problems of other
protocols.


 2. Dynamic Routing Information.
Our protocol uses dynamic routing information without relying on
external mechanisms/protocols for information exchange.

 3. Scalability. We introduce the Multicast Tree Search,
which allows us to reduce the scope of the Local Search.  The
complexity of the Local Search appears as the bottleneck in YAM.


 4. Efficient Resource Use.
QoSMIC uses a greedy routing policy, which has been shown to outperform
the Reverse Shortest Paths routing used by other protocols.

 5. Sensitivity to direction.
QoSMIC takes care to compute metrics in the direction that the data will
flow. This ensures much better performance in asymmetric networks.

 6. Robustness.
The only special status router of QoSMIC are the Managers. If they fail,
the recovery can be fast and  with minimal data loss. Having multiple
managers further enhances the robustness.

 7.Adaptivity during execution time.
In the MBone it is rather difficult to foresee the behavior of the
application and the users. Our protocol can adapt to the changing
network conditions and requirements during the life of the group, for
example, by changing the protocol parameters (see Section 5) or by
switching Managers.

Our simulations and analysis support the above claims.


Future work. Several functions of our protocol, such as the candidate
selection, can be implemented in different ways. A number of parameters
of the protocol also need to be selected. While we have some analytic



Expires October 1998                                           [Page 29]


Draft                The QoSMIC Multicast Protocol            April 1998


bounds on the expected behaviour, more detailed evaluation is needed to
finalize the details. Currently, we are simulating in more detail our
protocol and intend to implement a prototype. In parallel, we are interested
in the QoS metric selection problem: we are examining the type of routing
information appropriate for the different stages of our protocol, to
describe the QoR and QoS of the routes. We believe that with the
appropriate routing information our protocol can become an efficient
solution for QoS-sensitive applications.

References

[1] A. Ballardie. Core Based Trees (CBT version 2) multicast routing.
Internet Draft: IETF RFC 2201, 1997.

[2] T. Billhartz, J. B. Cain, E. Farey-Goudreau, D. Fieg, and S. G.
Batsell. Performance and resource cost comparisons for CBT and PIM
mulitcast routing protocols. IEEE Journal of Selected Areas in
Communications, 15(3):304-315, April 1997.

[3] K. Carlberg and J. Crowcroft. Building shared trees using a one-to-
many joining mechanism. ACM Computer Communication Review, pages 5-11,
January 1997.

[4] K. Carlberg and J. Crowcroft. Yet another multicast (YAM) routing
protocol: Specification version 1. Unpublished manuscript, 1997.

[5] S. Casner. Major MBONE routers and links. Available from
ftp.isi.edu:mbone/mbone-topology.ps, 1994.

[6] S. Deering. Host extensions for IP multicasting. Internet-Draft:
IETF RFC 1112, 1989.

[7] C. Diot, W. Dabbous, and J. Crowcroft. Multipoint communications: A
survey of protocols, functions, and mechanisms. IEEE Journal of Selected
Areas in Communications, 15(13):277-290, April 1997.



Expires October 1998                                           [Page 30]


Draft                The QoSMIC Multicast Protocol            April 1998


[8] M. Doar and I. Leslie. How bad is naive multicast routing? Proc.
IEEE INFOCOM, pages 82-89, 1993.

[9] H. Eriksson. Mbone: The multicast backbone. ACM Communications,
37(8):54-60, 1994.

[10] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M.
Handley, V. Jacobson, C. Liu, F. Sharma, and L. Wei. Protocol independent
multicast-sparse mode (PIM-SM): Protocol specification. Internet-Draft:
IETF RFC 2117 available from ftp://ftp.ietf.org/internet-drafts/, 1997.

[11] D. Estrin, D. Farinacci, A. Helmy, D. Thaler, S. Deering, M.
Handley, V. Jacobson, C. Liu, F. Sharma, and L. Wei. The PIM architecture
for wide area multicast routing. IEEE/ACM Transactions on Networking,
4(2):153-161, April 1997.

[12] D. Estrin, M. Handley, S. Kumar, and D. Thaler. The Multicast
Address Set Claim protocol. Internet-Draft:draft-ietf-idmr-masc-00.txt, 1997.

[13] M. Faloutsos, R. Pankaj, and K. C. Sevcik. Bounds for the on-line
multicast problem in directed graphs. Proceedings of 4th International
Colloquium on Structural Information and Communication Complexity
(SIROCCO '97), Monte Verita', Ascona, Switzerland July 24-26, pages 81-
98, 1997.

[14] W. Fenner. Domain wide multicast group membership reports.
Distributed in the IDMR mailing list. To appear as a Working Draft, 1997.

[15] M. Handley and V. Jacobson. SDP: Session description protocol.
Internet Draft. Work in porgress., 1995.




Expires October 1998                                           [Page 31]


Draft                The QoSMIC Multicast Protocol            April 1998


[16] M. Imase and B.M. Waxman. Dynamic Steiner tree problem. SIAM
Journal on Discrete Mathematics, 4:369-384, 1991.

[17] M. Parsa and J. J. Garcia-Luna-Aceves. A protocol for scalable
loop-free multicast routing. IEEE Journal of Selected Areas in Communications,
15(13):316- 331, April 1997.

[18] H. Takahashi and A. Matsuyama. An approximate solution for the
Steiner problem in graphs. Math. Japonica, 24(6):573-577, 1980.

[19] D. Thaler, D. Estrin, and D. Meyer. Grand Unified Multicast (GUM):
Protocol specification. Internet-Draft: draft-ietf-idmr-gum-00.txt, 1997.

[20] D.G. Thaler and C.V. Ravishankar. Distributed center-location
algorithms. IEEE Journal of Selected Areas in Communications, 15(13):291-303,
 April 1997.

[21] B. M. Waxman. Routing of multipoint connections. IEEE Journal of
Selected Areas in Communications, pages 1617-1622, 1988.

[22] B. M. Waxman. Performance evaluation of multipoint routing
algorithms. Proc. IEEE INFOCOM, pages 980-986, 1993.

[23] L. Wei and D. Estrin. The trade-offs of multicast trees and
algorithms. International Conference on Computer Communications and
Networks, 1994.

[24] P. Winter. Steiner problem in networks: a survey. Networks,
17:129-167, 1987. [25] D. Zappala, D. Estrin, and S. Shenker. Alternate
path routing and pinning for interdomain multicast routing. Technical
Report USC CS TR 97-655, U.  of South California, 1997.



Expires October 1998                                           [Page 32]


Draft                The QoSMIC Multicast Protocol            April 1998


[26] L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala. RSVP:
A new resource reservation protocol. IEEE Network, September 1993.

 [27] M.  Faloutsos and A. Banerjea and R. Pankaj,
QoSMIC: a QoS Multicast Internet protoCol, ACM SIGCOMM Sep 2-4,
 Vancouver BC, 1998.

APPENDIX

A Efficiency Parameters of Multicast Protocols

 The efficiency of a
multicast protocol can be defined by set of functional properties.

1. The efficiency of the multicast tree can be measured by the packet

replication which reflects the number of packets that a single piece of
information causes. In more detail, this can be defined as the number of
packets exchanged between neighbor routers, Px, over the number of
packets with distinct content, Pd, over the number of receivers, M :
Px=(Pd finition, we can characterize trees independently of the amount
of data transmitted (Pd) or the group size (M ).

2. The end-to-end delay is defined as the time it takes a packet to
travel from the source to a destination router.

The maximum and average end-to-end delay over all source and
destinations pairs could be used to characterize the end-to-end
performance of the tree.

3. The traffic concentration can be defined as the maximum link load
over the average link load (for the traffic of a given multicast group
or of all groups).

4. The control overhead represents the number of control packets that
are required to support multicast connections.

5. The routing table is the table maintained by each router to support
multicasting.

6. The set-up time is the time it takes a user to join a group: the time
from the join request until the arrival of the first data packet.


CONTACT INFORMATION

 Anindo Banerjea
 Dept. of Electrical and ComputerEngineering
 University of Toronto
 10 King's College Road Toronto,
 Ontario M5S 3G4 Canada
 banerjea@comm.toronto.edu



Expires October 1998                                           [Page 33]


Draft                The QoSMIC Multicast Protocol            April 1998


Michalis Faloutsos
Dept. of Computer Science
U. of Toronto Toronto
ON M5S 3G4 Canada
mfalou@cs.toronto.edu

Rajesh Pankaj
Qualcomm Inc
6455 Lusk Blvd San Diego CA 92121 USA
pankaj@qualcomm.com










































Expires October 1998                                           [Page 34]