Multicasting: Architectures, Algorithms and Applications

May 2 - 4, 2001
DIMACS Center, Rutgers University, Piscataway, NJ

Micah Adler, University of Massachusetts,
D. Frank Hsu, Fordham University,
Presented under the auspices of the Special Year on Next Generation Networks Technologies and Applications.



Compression Using Efficient Multicasting

Micah Adler, University of Massachusetts

Many multiprocessor systems have the ability to broadcast
and/or multicast information efficiently.  However, this ability is
often overlooked when designing algorithms for these systems.  In this
talk, we introduce a new compression technique that uses efficient
multicasting to significantly reduce the amount of information
communicated during parallel and distributed computation, resulting in
significantly faster algorithms for Fast Fourier
Transforms and sorting  on shared memory parallel models with limited
bandwidth. These algorithms demonstrate the importance of taking
advantage of efficient multicasting.  The compression technique uses a
new, natural variant of Ramsey theory, which may be of independent
(Joint work with Tom Leighton)

2. Multicast in Optical Networks J-C. Bermond Motivated by wavelength division multiplexing in all-optical networks, we consider the problem of finding a set of paths from a fixed source to a multiset of destinations, which can be coloured by the fewest number of colours so that paths of the same colour do not share an arc. We prove that this minimum number of colours is equal to the maximum number of paths that share one arc, minimized over all sets of paths from the source to the destinations. We do this by modeling the problems as network flows in two different networks and relating the structure of their minimum cuts. The problem can be efficiently solved (paths found and coloured) using network flow techniques. (this lecture covers work by B. Beauquier, P.Hell and S. Perennes)
3. Fault-Tolerant and Time-Step Optimal Multicasting in Mesh Multicomputers Using Faulty-Block-Information Dr. Xiao Chen We propose a fault-tolerant and time-step optimal multicast algorithm for mesh multicomputers based on the concept of the extended safety level which is a vector associated with each node to capture fault information in the neighborhood. In the approach each destination is reached through a minimum number of hops. In order to minimize the total number of traffic steps, three heuristic strategies are proposed. This approach can be easily implemented by pipelined circuit switching (PCS). A simulation study is conducted to measure the total number of traffic steps under different strategies. Our approach is the first attempt to address the fault-tolerant and time-step optimal multicast problem in mesh muticomputers based on limited global information with a simple model and succinct information.
4. Supporting Fast Intra-Domain Handoffs and Paging using Multicast in the Dynamic Mobility Agent (DMA) Architecture Subir Das, Archan Misra, Anthony McAuley and Sajal K. Das (Speaker) In this talk we will first propose a new architecture, called Dynamic Mobility Agent (DMA) architecture, for third and fourth generation (3/4G) wireless cellular networks. The objective is to reduce the latency of intra-domain location updates and the mobility related signaling traffic. Then we will discuss the base protocol that provide fast intra-domain handoffs by using a duration-limited, proactive packet `multicasting' scheme. We will quantify the expected buffering requirement of the proposed multicasting scheme for typical 3/4G network characteristics and compare it with alternative IP-based fast handoff solutions. We will also present a paging scheme under the base protocol that replicates the current cellular paging structure. Our paging mechanism supports generic paging strategies and can significantly reduce the mobility-related IP signaling load. Our scheme allows the use of either mobile node (MN) initiated or base station (BS) initiated handoff triggers and is applicable to multiple future link-layer technologies. Moreover, the IP-based fast handoff technique provides a secure fast handoff solution that does not assume the existence of specific layer-2 authentication functions or require the adjacent BSs to be aware of each other's identity. Finally, the IP-layer paging mechanism, which allows an idle MN to be located even though it does not perform IP-layer registration/configuration at every change in the subnet (BS), makes the scheme relatively independent of the radio technology.
5. Reducing the Multicast Routing State Michalis Faloutsos IP multicast suffers from scalability problems for large numbers of multicast groups. In mulitcast routing requires from each router to keep forwarding state for every multicast tree passing through it. Therefore, the state grows with the number of multicast groups. In this work, we propose an approach to reduce multicast forwarding states. In our approach, multiple groups are forced to share a single delivery tree. We discuss the advantages and the imlementations issues of our approach, and conclude that it is feasible and promising. We then propose metrics to quantify state reduction and analyze the bounds on state reduction of our approach. Finally, we use simulations to verify our analytical bounds and quantify the state reduction. In parallel, we study properties of multicast trees and the behavior of the members. The initial simulations suggest that our method can aggregate the routing state significantly.
6. Issues in Scalable Multicast Protocols Art Farley, Virginia Lo,(Speaker) Andrzej Proskurowski,(Speaker) Daniel Zappala We investigate two related ideas supporting development of scalable multicast protocols. They concern new network substructures (generalizing the standard distribution trees) and multiple "dissemination centers" ("multiple cores"). Our investigations include both theoretical analysis and experimental evaluation. In particular, we will present some or all of the following (time-permitting): - Definition, distributed protocols for construction, and experimental evaluation of shared network substructures (spanners and stanners). - Theoretical analysis of shared multicast trees for fixed set of sources - Experimental evaluation of multiple core trees and a distributed protocol for core placement ("k-domination") - Experimental evaluation of SSM proxies, an application-level protocol that implements any-source multicast on top of a source-specific infrastructure.
7. Computing connectivity of Cayley networks Shuhong Gao The connectivity of a network measures the number of disjoint paths between any two nodes, or from one node to several other nodes in the network. It also measures the fault tolerance of the network. Cayley networks (or Cayley graphs) are constructed from finite groups. They have many nice properties that make them excellent candidates for interconnection networks for distributed and parallel computer systems. In this talk, we show how to compute the connectivity of any given Cayley network that is connected (i.e. has only one component). Our algorithm depends only on local information, that is, the degree of a node and a small neighborhood of the node within a certain distance. The algorithm is deterministic and has a polynomial time in term of the degree. Note the number of nodes in the network is generally exponential in the degree, so our method is efficient in a strong sense.
8. Service Location Protocols and Architecture for ad-hoc Networks Guillermo GuiChal Ad-hoc networks are infrastructureless networks formed on-the-fly by devices with wireless communication capabilities. They have bandwidth and device power limitations, as well as the need to deal with mobility. If client - server interactions are to be present in such networks, a method for performing service location is needed. When two nodes that are several hops apart communicate, resources on all the intermediate nodes are wasted, so it is better to find services that are "closer" to the clients. Existing service location protocols do not seem suitable for mobile wireless environments. An underlying, low-level architecture that addresses network access issues could enable existing protocols to work in an ad-hoc environment. We have evaluated distributed and centralized architectures for service location and examined service availability and message overhead performance using simulations.
9. Building Dynamic VPN Multicast Trees Using Active Networks Yaser Haggag and Sampalli Srinivas Virtual Private Networks (VPN) have emerged as an important solution to security threats (e.g. eavesdropping, data manipulation, repudiation) surrounding the use of public networks for private communications. VPNs provide strong security by integrating a set of security components such as authentication, encryption, access control and session management to proof the identity of both communicating parties, to hide the exchanged data, to only restrict access to legitimate parties and to insure efficient operations of the established secure sessions respectively. Furthermore, VPNs have been proven to be a commercial competitor to the security offered by leased lines hence allowing geographically dispersed parties to communicate economically with each other [18,19]. With the increasing popularity of one-to-many and many-to-many applications and services being deployed over public networks, many multicast protocols are being developed to solve issues in group communications [1,2,3,4]. One major issue is scalability, which is a resultant of more members joining the broadcast session thus overwhelming the server causing a decline in server performance, which in turn slows server data delivery [5]. Another issue is security, which is required to keep the broadcast session hidden and unmodified by unauthenticated/unauthorized recipients [6,7]. One approach to solving the issue of scalability is to move the broadcast session closer to the members by caching the broadcast data onto the nearest routers securely, thus improving scalability and reducing the server loads [8,9]. In this paper we introduce a novel approach under development called "deployable virtual private networks" (DVPNs) to help build dynamic (i.e. on demand) secure multicast trees between the broadcast sever and the cached routers. The novelty of the approach comes from the use of active network technology to deploy VPNs. Active network is a new networking technology that inserts intelligence inside the network to offer on demand processing and programming capabilities to network nodes and packets traversing the network [12,13]. This allows routers to perform computations up to the application layer, thus increasing the flexibility of the network to speed up the deployment of new protocols and applications. Active networks offer many benefit in terms of secure code execution, access control, congestion control and data caching [13]. According to [13], several architectures have emerged to study the benefits offered by active networks. One architecture called active packets, inserts the programmable code only in the packets travelling the network. Another called active nodes, builds the programmable code into the intermediate nodes of the network. However, a hybrid version combing the programmability of the active packet and node approach appears to be the most promising one. This paper presents the preliminary results of an ongoing research project within the Secure Active VPN Environment (SAVE) project in active networks at Dalhousie University. PLAN (Programming Language for Active Networks) has been selected as the execution engine for developing active network applications and protocols on our test bed since it has emerged as an important hybrid architecture combining security, flexibility and efficiency [11,14,15]. DESIGN APPROACH This section describes the design approach under development to deploy VPNs for dynamic multicast trees. To build a secure multicast tree a few assumptions are in place: (a) Routers are active. (b) Routers employ Public Key Infrastructure [19]. (c) Routes with statically installed DVPN services are trusted by the organization deploying the VPN. (d) VPN multicast trees are most likely to be small or medium in member's size. (e) Trusted router can be trusted to enforce multicast session policies. In addition to the core services available to PLAN programs, we have successfully implemented and statically installed five DVPN services (i.e. functions). Our goal is to dynamically install DVPN services to demonstrate on demand VPN functionality. The following is an overview of the implemented services: 1. chuckToBlob: This service converts a chuck (a code hunk that contains code, a function to execute and bindings (e.g.. arguments such as data and destination)) into a blob (a byte array) to be able to encrypt it later using the encryptBlob service [20]. 2. encryptBlob: This service encrypts (scrambles) a blob. By this we hide any data sent (what ever type it may be) along with the service(s) required by it to be evaluated. 3. decryptBlob: This service decrypts (unscrambles) a blob to evaluate it. 4. blobDigest: This service produces a hash value [19] of the encrypted blob for the purpose of message integrity check performed by verifyBlobDigest. 5. verifyBlobDigest: This service checks the integrity of the received encrypted blob, then decrypts it to be evaluated. We have created a network configuration to test the operation of the above PLAN services by creating a tunnel between two active routers. To experiment with multicast like applications, we have created a client chat program using Java (an object orient programming language) [16] to simulate a broadcast session over active networks. When the client chat program is injected, the routers interpret the PLAN code calling on the cryptographic services installed statically and applying the passed data to them. The implemented cryptographic mechanisms ensure the exchanged chat text will remain private. This design provides so far two different levels of security, data confidentiality and integrity. The client can either select to call on the encryption and integrity services or on the encryption service only. FEATURES OF THE DESIGN The goal of this design is to develop VPN services that can be installed dynamically and can be terminated on demand to provide strong security mechanisms to a multitude of unicast and multicast applications. Current traditional VPN solutions are not flexible enough to offer on demand tunnel creation and termination and are not easy to integrate with many applications due to their complex interface. DVPNs can offer varying levels of security, flexibility and usability (such as client-to-client, client-to-node and node-to-node communication). The flexibility of the DVPN services allows for the selection between a strong secure procedure or a performance tailored one. For example, data exchanges and backups between a main office and its branch is a trusted one, on the other hand it is performance demanding. Therefore, requiring fast encryption processing and fewer authentications. Another example, communication between businesses and customers can be tailored towards more authentication than performance to ensure legitimate exchanges. Furthermore, active networks allow VPN services to be installed dynamically in a resource-controlled environment. Thus extending DVPN reachability to traverse untrusted intermediate routers and networks eliminating interoperability issues suffered by traditional VPN solutions. REFERENCES [1] B. N. Levine, J.J. Garcia-Luna-Aceves, "A Comparison of Reliable Multicast Protocols", Multimedia Systems, 1998. [2] R. Canetti, P-C. Cheng, D. Pendarakis, J. R. Rao, P. Rohatgi, D. Saha, "An Architecture for secure Internet Multicast", IETF Internet Draft (work in progress), February 1999. [3] W. Fenner, "Internet Group Management Protocol", Version 2, RFC 2236, November 1997. [4] M. Calderon, M. Sedano, A. Azcorra, C. Alonso, "Active Network Support for Multicast Applications", IEEE Network, May/June 1998, pp. 46-52. [5] B. Quinn, "IP Multicast Applications, Challenges and Solutions", IETF Internet Draft (work in progress), November 1998. [6] M. J. Moyer, J. R. Rao, P. Rohatgi, "A Survey of Security Issues in Multicast Communications", IEEE Network, November/December 1999, pp. 12-23. [7] R. Canetti, B. Pinkas, "A Taxonomy of Multicast Security Issues", IETF Internet Draft (work in progress), April 1999. [8] L. H. Lehman, S. J. Garland, D. L. Tennenhouse, "Active Reliable Multicast", IEEE INFOCOM, 1998. [9] U. Legedza, D. J. Wetherall, J. Guttag, "Improving the Performance of Distributed Applications Using Active Networks", IEEE INFOCOM, 1998. [10] D. Alexander, W. Arbaugh, A. Keromytis, J. Smith, "Security in Active Networks", University of Pennsylvania, 1999. [11] M. Hicks, P. Kakkar, J. T. Moore, C. A. Gunter, S. M. Nettles, "PALN: A Packet Language for Active Networks", in International Conference on Functional Language (ICFP '98), Baltimore, MD, 1998. [12] D. L. Tennenhouse et al, "A Survey of Active Network Research", IEEE Communications Magazine, January 1997, pp 80-86. [13] K. Psounis, "Active Networks: Application, Security, Safety and Architectures", IEEE Communications Survey, 1999, Vol. 2, No. 1. [14] M. Hicks, P. Kakkar, J. T. Moore, C. A. Gunter, S. M. Nettles, "Network Programming Using PLAN", University of Pennsylvania. DARPA. [15] Official PALN web site: [16] Sun Microsystems Java web site: [17] M. Hicks, A. Keromytis, "A Secure PLAN", University of Pennsylvania. DARPA. [18] D. Kosiur, Building and Managing Virtual Private Networks, John Wiley and Sons, Inc, USA, 1998. [19] B. Schneier, Applied Cryptography, John Wiley and Sons, Inc, USA, 1996. [20] M. Hicks, P. Kakkar, "The PLAN Tutorial", v. 3.1. DARPA.
10. Scheduled RMP and a Stock Market Application Nicholas F. Maxemchuk The reliable multicast protocol,RMP (a.k.a RBP, a.k.a the Chang/Maxemchuk protocol) was implemented in 1983, and was the first reliable multicast protocol.RMP has several characteristics that made it a likely candidate for the stock market application. In particular: 1. the receivers in RMP all place the messages from all of the sources in the same sequence, 2. we can eventually guarantee that all of the receivers have a message, and, 3. at a later time we can guarantee that all of the receivers know that all of the other receiver have the message. Using RMP, we created three international stock market systems, with useful fairness properties: 1. A unified stock ticker of the transactions that are being conducted on the various physical and electronic exchanges. This system simultaneously delivers the same composite ticker to all receivers, anywhere in the world. 2. A unified sequence of buy and sell offers that are delivered to a single exchange or a collection of exchanges. This system gives all of the traders the same fair access to an exchange, independent of their relative distances to the exchange or the delay and loss characteristics of the international network. 3. A distributed, electronic trading floor. This system has the fairness attributes of the first two systems and also conducts irrefutable, distributed trades. The original version of RMP implemented a distributed database on a local area network. There were a few tens of sources and receivers and a small number of messages per minute. The stock market applications have to accommodate tens of millions of sources and receivers, transferring millions of messages per second, internationally, in a hostile environment, here protocol participants cannot be trusted to cooperate. Most of the differences in requirements between the original RMP application and the stock market applications were solved architecturally, by good engineering, rather than by modifying the protocol.During this presentation, I will describe the architecture of the stock market systems and show how it provides the fairness and security that are required. The high message throughput and the short delivery delays in the stock market applications required a modification of the protocol. We solved these problems by changing the protocol from an event driven protocol to a scheduled protocol. The original version of RMP is driven by the arrival of source messages.Each source message is only explicitly acknowledged by one receiver, instead of by each receiver, by using a combination of positive acknowledgements, negative acknowledgements, and token passing.When a receiver accepts the token, it implicitly acknowledges all of the previously, explicitly acknowledged messages.The penalty for reducing the number of acknowledgement messages is the delay until we know that all of the receivers have received an acknowledged a message. When there are N receivers, the delay is the time required to acknowledge the next N-1 source message, and is therefore, a function of both the number of receivers and the arrival times of future source messages. The modified version of RMP sends acknowledgements at scheduled times,rather than being driven by the source messages. In this scheduled protocol if there is no negative acknowledgement by a specified time it is the same as a positive acknowledgment. As a result, we can guarantee that all of the receivers have a source message at a predetermined time after it is first acknowledged, independent of the number of other receivers or the message arrival rate. I am currently determining how tight I can make the interval between the time a message is first transmitted until I can guarantee that all of the receivers have the message.The time depends on the network loss rate and the propagation delay. In certain networks the guarantees are adequate to meet the quality of service required by real time applications.
11. Hierarchical Path QoS on the QoS-based Multicast Protocol SRSVP Yasuo Okabe, Takaaki Sekiguchi, Kenji Fujikawa, Kazuo Iwama We argue on a method to collect information of each existing multicast flow on hierarchical networks, and describe an algorithm for Qos multicast routing based on it. In computing a multicast path with per-flow QoS guarantees precisely, it is an important problem how routers collect information of each existing multicast flow. SRSVP, a QoS-based multicast routing protocol, is designed as it collects flow-specific detailed information, called PathQoS, by putting it into signaling messages, so that the derived QoS path becomes more efficient. In this paper, we have designed an algorithm to calculate PathQoS corresponding to an aggregated link state among areas on a hierarchical network for SRSVP to compute more efficient QoS paths. We have presented that the methods to calculate PathQoS among areas are classified to four cases, have considered dependence upon information needed by the calculations, and have designed an algorithm for routers to be able to process the methods efficiently. We have implemented the mechanism to collect PathQoS based on the algorithm. Now SRSVP is fully adapted to a hierarchical network model.
12. Bid-based Pricing Approaches for Multicast Sessions in Heterogeneous Networking Environments Dan Rubenstein and Micah Adler One reason that multicast has seen limited deployment is that ISPs are unsure of how they should charge for such a service. A justifiable pricing mechanism must satisfy three requirements. First, it must guarantee the network a profit. Second, the protocols that implement the pricing mechanism should must themselves be simple and efficient. Last, the mechanism must permit admission of sessions that allow for session heterogeneity: receivers within a session should be allowed to receive at differing rates, and it should not be assumed that all nodes within the network will provide multicast (i.e., some form of multicast overlay may be required). In this talk, we demonstrate that it is indeed possible to efficiently implement a bid-based pricing mechanism in a multi-rate overlay multicast that optimizes network profits when a session's transmission is restricted to a single tree. We also explore the complexities that arise when we attempt to extending the session's transmission beyond a single tree. Last, we demonstrate how these bid-based protocols can be used in heterogeneous environments to implement pricing mechanisms that are strategyproof, such that receivers have no incentive to bid less than what receiving the transmission is worth to them.
13. Distance Learning using IP Multicasting for the Ateneo Educational System Rafael P. Saldana The Ateneo Educational System consists of schools located in various parts of the Philippine archipelago. Lead by the Ateneo de Manila University, a distance education program is currently being implemented in the educational system. Due to IP multicasting technology, the delivery of high performance computing applications over the the Internet is now a reality. To enhance the delivery of distance learning in the Ateneo educational system we are proposing the utilization of IP multicasting.
14. How to spread a rumor when not everyone is talking to each other OR Multicasting in heterogeneous networks Baruch M. Schieber In heterogeneous networks, sending messages may incur different delays on different links, and each node may have a different switching time between messages. The well-studied telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of finding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic telephone model. We present a polynomial-time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the telephone model by a factor of O(logn/loglogk), where n is the total number of nodes. No approximation algorithms were known for the general model considered by us. This is joint work with Amotz Bar-Noy, Sudipto Guha and Seffi Naor
16. A Distributed QoS Multicast Routing Protocol Yuval Shavitt Many Internet multicast applications such as teleconferencing and remote diagnosis have Quality-of-Service (QoS) requirements. Such requirements can be additive (end-to-end delay), multiplicative (loss rate) or with a bottleneck nature (bandwidth). For these applications, QoS multicast routing protocols are important in enabling new receivers to join a multicast group. However, current routing protocols are either too restrictive in their search for a feasible path between a new receiver and the multicast tree, or burden the network with excessive overhead. In this talk I'll present S-QMRP, a new Stateless QoS Multicast Routing Protocol that supports all three QoS requirement types. S-QMRP is scalable because it has very small communication overhead and requires no state outside the multicast tree; yet, it retains a high success probability. S-QMRP achieves the favorable tradeoff between routing performance and overhead by carefully selecting the network sub-graph in which it conducts the search for a path that can support the QoS requirement, and by auto-tuning the selection according to the current network conditions. S-QMRP does not require any global network state to be maintained and can operate on top of any unicast routing protocol. Our extensive simulation shows that S-QMRP performs better than the previously suggested protocols. Joint work with Shigang Chen
17. Some Techniques for Multicasting in Hypercubes Hal Sudborough We consider techniques to minimize message congestion when doing multicasting in a hypercube architecture. That is, for any integer k, we consider one-to-k maps which specify, for each node x in the hyper cube, to which nodes packets are to be sent from x. Our results give techniques to route such packets that satisfy the requests in specified sets of one-to-k maps and that guarantee minimal message congestion in any of the hypercube connections.
18. The Challenge of Multicasting over Ad Hoc Mobile Wireless Networks C-K. Toh Multicasting over wireless networks has traditionally been investigated in the view of mobile users moving from the radio coverage of one cell to another. Current multicasting technqiues used in the Internet are robust but not necessarily efficient when applied to wireless networks. Most multicast routing schemes rely on building some forms of multicast trees, be it source- or core-based. In addition, assumptions were made that intermediate routers in the tree paths do not move. However, an emerging new form of totally wireless and pervasive networks known as ad hoc wireless networks have evolved. Such networks has a completely wireless backbone, and use multiple wireless links for end-to-end communications. Multicasting of audio/video/data information in such networks shall present great challenges to researchers due to the presence of mobility, bandwidth, and power constraints. One should question the suitability of multicast trees in such networks and also suggest mechanisms to deal with group membership dynamics. One should also examine scalability issues associated with multicasting in an ad hoc based wireless intranet. This talk shall reveal these problems and encourage thoughts for further investigations.
19. Deadlock-Free Prefix Multicasting in Irregular Networks Jie Wu, Fei Dai, Li Sheng A deadlock-free multicast scheme called prefix multicasting in irregular networks is studied. Prefix routing is a special type of routing where a compact routing table is associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labeling in an irregular network are done by using a pre-defined spanning tree which may or may not be minimum. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel between two branches of the tree between two phases. It is shown that the proposed routing scheme is deadlock- and livelock-free. The approach is extended to multicasting in which the multicast packet is first forwarded to the longest common prefix (LCP) of destinations in the multicast. The packet is then treated as a multi-head worm that can split at branches of the spanning tree as the packet is forwarded down the tree. Comparison between prefix multicasting and Libeskind-Hadas et al's approach for multicasting is given. Possible extensions are also discussed including reliable prefix routing and multicasting.
20. A Scalable Topology for High-Speed LAN and WAN Networks Sotirios G. Ziavras We propose a topology to implement backbone networks in the LAN or WAN environment. This network topology assumes the employment of fiber optic devices. Wavelengths used in this scalable network are reusable and a high degree of reliability is supported. We present efficient algorithms for randomized many-to-all broadcasting and multicasting in the proposed network. These implementations are tested under realistic communication traffic patterns and message generations. A modification of the multicast algorithm applies congestion control to improve the performance.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on May 1, 2001.