Carlberg, Kenneth Gustav Enrique Fernando; (2000) QoS multicast using single metric unicast routing. Doctoral thesis (Ph.D), UCL (University College London).

Preview

Text QoS_multicast_using_single_met.pdf Download (6MB) | Preview

Abstract

Multicast routing protocols are designed to construct and maintain trees. These trees distribute data on a one-to-many basis in which the replication and distribution of data is accomplished by nodes of the tree. Initial efforts in designing the first IP multicast routing protocol focused on the development of algorithms that produced a separate tree for each source of the multicast group. For those edges of the tree that do not have group members, special control messages, referred to as Prunes, are sent hop-by-hop towards the source to ensure that data is only sent to those nodes that have downstream receivers. However, even with the inclusion of Prune messages, each router in the network was required to retain source/group state for every active source of every group. Shared tree algorithms and protocols were developed in an attempt to reduce the amount of state stored by source tree protocols. The fundamental design in this approach centered on leaf routers sending an explicit unicast join message to the shared root of the tree, thus grafting a branch from the receiver onto the shared tree. Two of the more widely known attempts to achieve this are known as Core Based Trees (CBT) and Protocol Independent Multicast (PIM). In general terms, the former constructs bi-directional trees in which any on-tree node can be used to initiate the distribution of data to the group members. The latter constructs unidirectional trees were only the root is allowed to initiate the distribution of data to the group members. Both protocols were designed to operate independent of any underlying unicast routing protocol, and both rely on an a priori selection of the shared core. This approach in building shared trees works well in an environment that is comprised of just best effort service and routing protocols that calculate a single shortest path to a destination. However, the introduction of new service models in the network layer fosters a need to change today's multicast framework so that branches can reflect the desired Quality of Service (QoS) of an application. My thesis presents a new approach for building shared trees so that branches reflects the desired QoS of receivers. The approach follows a design parameter of CBT and PIM in that the construction of a shared tree is accomplished independently over any unicast routing protocol. However, I introduce a paradigm shift by having leaf routers use a one-to-many join mechanism to discover multiple paths from which to graft a branch onto the shared tree. These paths can be associated with a variety of metrics or criterion. This allows the network to support applications or system administrators in constructing QoS sensitive trees. Congruent to this selection, is that the shared root is dynamically selected as a function of group membership, which I will show can significantly lessen the impact of core placement in terms of delay from source to receivers. The innovative approach I use to construct QoS sensitive shared trees is based on a one-to-many join mechanism and is described in my thesis through the Yet Another Multicast (YAM) protocol. The algorithm that acts as the foundation of the YAM protocol represents a variation of the Greedy algorithm and allows the protocol to operate in a scaleable manner in constructing multi-metric trees. I present some of my experiences in implementing the YAM protocol to articulate the problem space of introducing a QoS sensitive multicast protocol within the current IP multicast service model as it exists today. The primary basis used to validate my claims is done through simulation, and statistical analysis of the data produced from simulated scenarios. Real-time measurements of the design are not presented because an in-depth examination would require an actual test network of considerable depth (i.e., many nodes spanning the boundaries of a network). I describe simulations of the YAM protocol in order to quantify cases in which QoS multicast can be more beneficial than the current single shortest-hop designs being developed today. These simulations also allow me to present a means of representing the impact on the system in using a one-to-many joining mechanism and in having group members migrate over time. Finally, while several existing algorithms are used in tandem to produce QoS sensitive trees, I do not introduce new algorithms in the design, and thus I do not present an in-depth algorithmic analysis in my thesis.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item