1. Please describe briefly what multicast is used for.

In general, multicast is the enabling technology for efficient 'group' communication, where multiple senders and receivers engage in a 'session' or a conference.

Example applications of multicast include distance learning, multimedia tele-conferencing, tele-medicine, multi-party gaming, to name only a few.

In ad hoc networks context, multicast may be used for search-and-rescue teams, disaster relief, mobile classrooms, reconnaissance and discovery missions, sensory or oceanography, among others.

Unlike conventional point-to-point 'unicast-based' communication that establishes streams between individual senders and receivers, multicast instead builds distribution branches (either tree or mesh) that links senders to receivers. If unicast is used for group communication then a sender would send 'n' streams to 'n' receivers, whereas in a multicast scenario only a single stream is sent from the sender and is distributed appropriately to the 'n' receivers over the distribution branches. Thus the load on the network is reduced drastically by using multicast.

The standard IP multicast model allows for any network node to potentially join any group (given that it has the right key, security, etc.). Hence, at the beginning of a session participants do not know the individual identities of the other participants, which provides architectural scalability.

At the same time this creates what is called a 'rendezvous' problem. That is, how do new members of a group know about senders to the group and receive their packets. The two existing solutions in the multicast literature are known as 'broadcast and prune' (or dense mode) and 'rendezvous core' (or sparse mode). In the former, a sender broadcasts its packets to the whole network (by flooding) and nodes not interested in the broadcasts send 'prune' messages to stop the flow of packets down those branches. Obviously, this approach does not scale beyond a campus area network (e.g., hundreds of nodes).

The rendezvous core approach, by contrast, elects a node (called the 'rendezvous point' (RP)) to act as an intermediary that all nodes in the network know about through a mechanism called the 'bootstrap mechanism'. Senders that wish to send to the group send their packets to the RP, and receivers who wish to join the group send their join messages towards the RP. This provides a more scalable architecture than broadcast-and-prune, but the bootstrap mechanism uses broadcast messages limiting the network size to which such scheme is applicable.

Hierarchical architectures tend to improve scalability of multicast, but have proven to be practically complex for IP multicast.

In ad hoc networks, the environment is even more dynamic with all nodes being mobile and more likely to crash. Hence, the RP-based approach suffers from single-point-of-failure and the bootstrap mechanism needs to be even more complex to cope with the network dynamics and failures. This leads to undesirable disruption of multicast services with the failure or movement of the RP. So, we need a new approach for multicast that is better suited for large-scale ad hoc networks. This is the focus of my research paper.

2. What is the state of research in multicast for large, mobile ad hoc networks?

This work is the first work (that I am aware of) that explicitly addresses multicast for large-scale ad hoc networks with, perhaps, tens of thousands of nodes.

Recently, the area of multicast in ad hoc networks has attracted a lot of attention and it may be incomplete or unfair to try to characterize all the recent works in that area. Having said that let me make some general statements about research trends from my point-of-view. Previous work on multicast in ad hoc networks has addressed small to medium size networks (with tens to hundreds of nodes). Some approaches use broadcast of sender messages to update other nodes of the state of the group. Other approaches attempt to mimic the RP-based approach in ad hoc networks. One main contribution of multicast in ad hoc networks so far has been to propose to build a 'mesh' instead of a multicast 'tree', which provides more robustness to failures and movement. In general, the proposed multicast protocols for ad hoc networks thus far, however, do not scale well as the number of nodes grows in the network.

Other related work includes work on hierarchy formation in ad hoc networks. This process may include dividing the network into collaborative 'clusters' and exchanging information about clusters (instead of nodes), thus reducing the overhead. For ad hoc networks, forming and maintaining such hierarchy may be quite expensive since power consumption (due to communication) is a primary design parameter. The simpler the hierarchy formation, in general, the less maintenance overhead it requires but the less aggregation it provides. This has been an issue of research for some time.

3. What is the specific advancement you are reporting in your paper?

My paper provides an architectural framework for providing multicast in large-scale ad hoc networks. The paper provides the architectural components required for multicast in an infrastructure-less environment. Hence, the protocols and mechanisms proposed were designed to be self-configuring and highly adaptive.

The first component is hierarchy formation. The paper adopts a simple 'zone-based' hierarchy, where a node maintains information about neighbors up to 'R' hops away using local periodic exchange of information. This scheme per se does not scale well. However, by linking it to a novel idea (I call 'contacts'), scalability may be improved drastically. While node 'mobility' has been usually viewed by others as a burden on the architecture, I view it as an advantage. Since nodes are in continuous movement, previous neighbors of a node (that used to have a highly overlapped view of the network) move away and obtain a lightly overlapped (or non-overlapped) view of the network. By remaining in 'contact' with (some) of the older neighbors, a node may increase its view of the network by exchanging information with its contacts.

The nice thing about this idea is the fact that these contact nodes used to be in the neighborhood of a node. Hence a node already knows how to route packets to them and knows information about their mobility, power and capability characteristics. Thus keeping in contact requires light overhead. In addition, a smart choice of contacts may be based on previous information readily available at the node.

This architecture avoids the complexity and overhead of maintaining hierarchical 'clusters' while retaining the hierarchical scalability.

The second component of the architecture is the multicast service. The paper presents a new multicast model called 'sender push, server cache, receiver pull'. This model avoids global broadcasts and allows only restricted local broadcasts (e.g., geographically constrained broadcasts called "geocasts"), where senders advertise their existence locally within a given region. This information is kept by dynamically elected servers in a specific region, called the 'rendezvous region' (RR). Mapping from a group address to RR is done in every node by using a simple algorithmic well-known mapping function. Receivers send queries (using geocast) to the RR to get new information about the group.

Both the above multicast model and the rendezvous region ideas are novel. Furthermore, the paper proposes an adaptive election mechanism for the servers according to group popularity. Based on observed sender advertisements and receiver queries, a node may promote itself to become a server for the group. This reduces the overhead of geocasts significantly, as the servers become located near group participants. This feature further improves the scalability of the architecture. This mechanism is called 'adaptive anycast' and is also a new idea presented in the paper.

One thing to mention here is that the paper gives an architectural overview of the proposed mechanisms, but does not go into algorithmic details. On-going studies by my research group will address protocol specifications and mechanistic/algorithmic details. Also, much work is still needed to fine-tune the mechanistic parameters and conduct extensive performance evaluation and analysis using network simulation and testing. This will be done at the USC Electrical Engineering networking laboratory for protocol design and testing.

4. How is your approach a hybrid? Which pieces of what architectures does it combine?

I consider my approach hybrid in two aspects. The first is in the ad hoc routing protocol. In general, ad hoc routing protocols may be classified as either pro-active (also called table-driven) or re-active (also called on-demand). Pro-active approaches send periodic routing messages to update the routing tables at the nodes and capture network and node dynamics. The advantage of this approach lies in providing routes in anticipation of traffic and hence the route discovery delay is minimized. The downside, however, is that many routing entries may not be used and become obsolete. Hence the overhead that was used to create and maintain them is wasted. Re-active approaches, on the other hand, do not send periodic routing messages and avoid unnecessary overhead when routes are not used. These approaches, however, suffer long route discovery delay, as a request needs to be sent to discover the path when a demand is issued. Also, usually broadcast is used for route discovery, which does not scale well in a flat (non-hierarchical) architecture.

The approach proposed in the paper uses pro-active routing within the zone and with the contacts, since these routes will be frequently used. Routes outside the zone and the contacts are discovered on-demand using re-active routing between nodes and zone-borders. This hybrid approach attempts to combine advantages of both approaches for routing.

The second aspect of the hybrid approach lies in the choice of the hierarchy formation mechanism. One type of hierarchy is based on 'cluster-head's, in which one node is selected to represent and communicate on-behalf of a set of other nodes. When a node moves from one cluster to another, a join process is invoked to add this node to the new cluster and remove it from the older cluster. When the cluster-head moves or fails, a complex re-election process needs to take place, which consumes a lot of network resources and may disrupt routing. Another type of hierarchy is the zone-based hierarchy in which each node has its own view of a 'zone' (the neighbors near it up to 'R' hops away). This hierarchy obviates the need for complex join and re-election mechanisms, but does not scale as well. The approach proposed in the paper is a hybrid approach where zone-based hierarchy is extended with the notion of elected 'contacts'. This extension requires low overhead but increases the scalability of the architecture.

5. How does "small world graphs" fit in?

The concept of small world graphs was studied by Watts. He observes that we can create graphs with high clustering but low path length by choosing random far away links as short cuts (instead of close by neighbors). Hence, short cuts maintain high clustering but reduce the average path length drastically. In my paper, zone-based hierarchy is proposed. Alone, zone-based hierarchy has very high clustering (due to choice of neighbors in the zone) but long average path length. So, the zone is extended by choosing contacts to operate as short cuts to reduce the average path length (in our case they reduce the query steps required for route and resource discovery).

In our architecture, however, we do not choose these contacts randomly, since that would lead to unexpected overhead to discover and maintain routes to those contacts. Instead, we choose contacts in a way that reduces overhead of discovery and maintenance, while at the same time increasing the node view of the network drastically.
We expect that the resulting graphs in our case will have characteristics similar to those of small world graphs. The eventual characteristics of resulting graphs, however, depend also on mobility patterns of nodes and shall be investigated further in our future work.

6. Considering only technological issues, how soon will practical applications be possible? (I'm just looking for a rough timeframe like 2 to 5 years, 10 to 20 years, etc.)

I would estimate 3-5 years

8. What is your title?

Ahmed Helmy
Assistant Professor of Computer Networks
Electrical Engineering Department
University of Southern California
http://ceng.usc.edu/~helmy
helmy@ceng.usc.edu