Communications of the ACM
Communications of the ACM
Multicast Over Wireless Networks
Multicast over wireless networks is an important and challenging goal, but several issues must be addressed before many group applications can be deployed on a large scale.
Multicasting is a more efficient method of supporting group communication than unicasting or broadcasting, as it allows transmission and routing of packets to multiple destinations using fewer network resources. Along with widespread deployment of wireless networks, the fast-improving capabilities of mobile devices, and an increasingly sophisticated mobile work force worldwide, content and service providers are increasingly interested in supporting multicast communications over wireless networks.
Applications of wireless multicast support group-oriented mobile commerce, military command and control, distance education, and intelligent transportation systems. Many new m-commerce applications, including mobile auctions, will also gain significant benefit if group communication among mobile users is supported by wireless networks. Such applications require continued connectivity, atomic all-or-none transactions, and secure and reliable wireless multicast.
In military environments, tactical information may be multicast to users, tanks, and planes; such applications demand minimal delay and secure and reliable wireless multicast. Distance education and entertainment services can be offered to mobile or remote users; such applications require high bandwidth and near-real-time wireless multicast for quality viewing. Intelligent transportation systems involve the dynamic routing or rerouting of individual vehicles. Current traffic information, as well as the most direct and least time-consuming routes, can be multicast to drivers; in the future, commercial aircraft may fly on the most efficient routes guided, in part, by multicasts of location information concerning other nearby aircraft, objects, and destinations. The reliability and correctness of location information are major issues in wireless multicast.
Multicast communications has been supported for at least the past 10 years in the Internet environment for fixed users using wired links. In such environments, a host joins a multicast group by informing a local multicast router that in turn contacts other multicast routers; a multicast tree is thus created through a multicast routing protocol [1]. The multicast router periodically sends queries to determine whether any of the hosts in its coverage is still a member of the multicast group.
All host-multicast router communication is performed through the Internet Group Management Protocol (IGMP) [1]; Internet IP multicasting has been implemented using MBone, a virtual overlay network [3]. Since not all IP routers support multicast routing, the forwarding of multicast datagrams is handled by "multicast routers" through "tunnels" connecting multicast routers; tunnels in effect pass through but are not processed by unicast routers (see Figure 1). Tunnels are implemented by encapsulating IP multicast packets in a unicast IP packet to the next multicast-capable router.
Existing multicast support for fixed users can be extended to mobile users in wireless environments. However, applying such support to wireless multicast is difficult for many reasons (see Table 1); for example, the bandwidth available in the two directions of any given wireless link may not be equal (the links may even be unidirectional), thus affecting the amount of control and signaling information that can travel either way. The user's mobility could therefore lead to inefficient multicast tree/mesh, loss of packets, incorrect routing, even the discarding of multicast packets. The existing multicast protocols are designed for a fixed topology, though ad hoc wireless networks may experience changes of topology due to the movement of intermediate nodes during multicast sessions.
Group Membership Management in Wireless Networks
Unlike shared-medium wired LANs, in which an IGMP query or response for group membership is received by each attached device, wireless users may not receive the query, due either to point-to-point links or to interference, noise, signal attenuation, or mobility in broadcast-oriented wireless networks. Moreover, when IGMP is used over wireless links, the amount of overhead increases significantly due to joint operation and the polling of mobile users by routers. To emulate IGMP behavior in IP networks, a response from a user can be forwarded to all mobile users in the same subnet. When a mobile user moves within a subnet, multicast routers can forward the multicast packets to the new location (access point or base station), assuming there is no host in the new location already subscribing to the same group [6]. IGMP can also be modified to collect and store additional state information (such as listings of hosts per group and groups per host [12]), allowing the selective forwarding of multicast packets over point-to-point links.
In wireless and mobile networks, "leave latency," or the time during which packets continue to be forwarded to users no longer at these locations, may increase due to delayed or lost packets. Leave latency can be reduced by using explicit join/leave changes by users [12], explicit join/leave changes combined with acknowledgments [6], or by retransmission of queries by routers based on the history of links and users [6]. The first is the simplest to implement; the second reduces leave latency but increases the overhead of acknowledgment; and the third seeks to overcome the loss of acknowledgments by way of successive retransmission, though it also requires the storage and updating of the histories of individual links.
Multicast Routing for Infrastructure-based Wireless Networks
Infrastructure-based wireless networks involve base stations and switches in a fixed topology, as well as mobile users. Existing multicast routing protocols can be modified for wireless multicast; they include the Distance Vector Multicast Routing Protocol (DVMRP); Multicast extension to Open Shortest Path First (MOSPF); and Protocol Independent Multicast (PIM) in sparse and dense modes.
However, DVMRP could cause the dropping of multicast packets from mobile users, and MOSPF could lead to inefficient routing of multicast packets. PIM might allow mobile users to join from any point and provide correct routing. The Core-Based Tree (CBT) and PIM-SM (sparse mode) [2] can both be used as the routing protocol, as they route datagrams based only on destination, permitting a mobile host to send multicast packets from any point in the network [12]. To support highly mobile users, CBT can be modified to support dynamic cores whereby core functions are moved from one router to another based on a number of factors, including mobile user location and total number of hops in a multicast tree. For mobile users who have moved to a neighboring location, the last hop routing can be performed without changing the multicast tree by using mobile IP [11]. These users can then subscribe to their groups at the new location using a foreign agent or continue to receive multicast packets forwarded through a tunnel.
Multicast Routing for Ad Hoc Wireless Networks
Ad hoc wireless networks provide a high degree of mobility for all network components, including users and routers. Due to such unconstrained mobility, the path between any two users is subject to change during a session. Therefore, the multicast routing protocols designed for infrastructure-based wireless networks cannot be used in ad hoc networks. Since there is no fixed infrastructure (such as base stations and switches) in ad hoc networks, all nodes, including mobile hosts, may be required to compute, maintain, and store routing information. Figure 2 outlines several issues and possible solutions in multicast routing for ad hoc networks.
In 1998, the Internet Engineering Task Force's working group on Mobile Ad Hoc Networking (www.ietf.org/html.charters/manet-charter.html) introduced several desirable properties of multicast routing in ad hoc networks, including distributed routing, on-demand route discovery, security, and freedom from loop routing. Ad hoc wireless networks have also attracted research interest concerning the design of multicast routing protocols [9], several of which are outlined in the following sections.
Multicast routing using a tree. In the tree-based approach, multicast routing uses a source-based or shared tree among sources and receivers; only one path exists between any pair of nodes. The amount of bandwidth resources required for initializing a tree is usually less than that required for other structures. However, a multicast tree is subject to disruption due to link/node failure and node mobility; for example, if an intermediate node fails or moves out of coverage, the tree can break into two or more "subtrees," making groupwide communication difficult and possibly intermittent.
The route discovery for building a multicast tree can be done by either broadcasting when and where needed or by using well-known central points, including cores. The Ad-hoc On-demand Distance Vector (AODV) routing protocol [7] uses source-initiated broadcasting for route discovery.
Route updating in multicast routing protocols can be done in one of three ways:
- Store and update. Store the information in a routing table and update it by listening to routing messages, as in the AODV protocol [7];
- Delete all and refresh. Discard all old routes (time-out) and start over; ideally, the frequency of the updates is matched with the frequency of changes in topology but is difficult to implement; and
- Unicast protocol support. Use the services of a separate unicast routing protocol for route updating.
All three approaches have been employed in ad hoc multicast routing protocols [9].
Multicast routing using mesh. The amount of resources (bandwidth, processing, storage) required to build a mesh is usually much greater than for building a tree. However, a major advantage is multiple redundant routes for robust handling of link failure and node mobility during a multicast session. Besides requiring more resources, mesh routing reflects another disadvantagecalled loopingso measures have to be taken to avoid (or remove) routing loops.
Since the mesh allows multiple paths between a pair of nodes, the route-discovery and mesh-building process is more important than route updating. Route discovery and mesh building are accomplished in two ways: by using broadcasting to discover routes when and where needed, and by using core or central points for mesh building. The broadcasting approach is built into the On-Demand Multicast Routing Protocol [5] by the periodic flooding of control packets. Looping is avoided by using cache to detect duplicate data and control messages. For an in-depth discussion of mesh building via core or central points, see [9].
Multicast routing using other structures. Besides tree, mesh, and tree of mesh, multicast routing can be performed in two other ways: forwarding packets in many directions and functioning independently of topology. The Forwarding Group Multicast Protocol [5] uses a set of nodes that forwards multicast packets without using a formal routing structure. Topology-independent routing is implemented through flooding or broadcasting [9]; though inefficient in terms of network resources, multicast routing provides stateless topology-independent routing.
Reliable and Secure Wireless Multicast
For many applications, reliable and secure multicast is a basic requirement. Providing end-to-end reliability requires detection of packet loss, along with error recovery. Packet loss can be detected through one of two approaches:
- Sender-initiated. Receivers return acknowledgments for correctly received packets; timers can be used to detect packet losses at the sender. However, if every receiver sends an acknowledgment for a packet it receives, feedback implosion can occur.
- Receiver-initiated. Negative acknowledgments (as in the receiver-initiated approach) are used by receivers to inform the sender about packet loss via negative acknowldgments.
Loss recovery can be performed through selective retransmission to the receivers that did not receive packets. It is done either by setting up a group of receivers, dividing the group into clusters with designated cluster heads responsible for retransmission, or by local retransmission, locating a neighboring receiver that has correctly received the packets. Clustering is useful primarily when the group pattern is dense, though no such assumptions can be made for mobile users.
Security issues in wireless multicast arise due to the use of wireless links that are at risk of being eavesdropped, the inherent broadcast nature of some wireless links lacking control on receivers, and the use of flooding for tree/mesh construction. Security risks include complete loss of service, information stealing or modification, and modification of routing tree/mesh allowing unauthorized users.
The security issues can be addressed in a number of ways; for example, packets in wireless multicast can be encrypted using symmetric (private-key) or asymmetric (public-key) schemes. But the key distribution and re-key processes, in light of user mobility and membership changes, can create significant processing and network overhead. In group key encryption, a group- key management protocol securely delivers a common key to all users of a multicast group [4]. Group authentication is implicitly provided by possession of the key; sender authentication can be provided via other means, including digital signature. Firewalls can provide secure wireless multicast, though they add significant complexity and may make user interaction and collaboration more difficult if users are spread across different networks.
The scope of multicast packets can also be limited by routers and sources to provide some level of security for wireless multicast, though the distribution of wireless multicast group users may change over time, thus requiring changes in scope. The overhead of these changes and the probability that a mobile user stops receiving multicast packets for some period of time should be evaluated. Another way for network designers to provide some security for wireless multicast is to require that routing protocols enforce membership control; for example, in core-based or rooted-tree multicast protocols, the central point(s) can be given an authorization list to verify signed join-requests from receivers. It's also possible to use "trusted" routers and members [8], whereby other routers in the paths among the trusted routers are prohibited from changing routing information.
Wireless Multicast Adoption
Wireless multicast is a topic of great interest to Internet service providers, cellular and personal communication service providers, content providers, and businesses with multiple sites requiring simultaneous updates. Service providers can use multicast to support content-distribution services for which they might charge their customers a premium. Businesses can use wireless multicast to distribute software and data updates to branch offices and stores worldwide. However, many important issues must be addressed before multicast can be widely deployed, including: new business models for charging wireless customers and for revenue distribution among providers; maturity of wireless multicast software, applications, and middleware support, vendor support, and router interoperability; and the user trust necessary for conducting mobile transactions. Table 2 outlines several solutions to pricing and revenue distribution in wireless multicast.
Mobile commerce application categories include mobile financial management, mobile advertising, mobile inventory management, proactive service management, mobile auctions, mobile office functions, mobile entertainment, and multiparty games [11]. A major issue is providing multicast communications for mobile users, along with location management, quality of service, dependability, business models and pricing, application development, and regulatory issues. Multicast communications is needed for such m-commerce applications as mobile auctions, interactive games, and other group-oriented interactions, though specific requirements vary (see Table 3).
User mobility, combined with wireless link characteristics, may complicate continuous communication among group users. No response from a user for some time (possibly brief disconnectivity or intermittent connectivity) may lead to problems. Has the user left the group completely or experienced only some brief disconnectivity? The state of the application could be maintained until a time-out occurs or the user is connected again. What if the user's response would not have affected the outcome of the application's performance? How long is a reasonable time to wait? As time-out is a technique for membership management (remove users from the group application if they do not report in for a given amount of time) in such applications, it is not clear how to calculate the length of a time-out or even which ones apply. Choosing a short value would lead to frequent removal of mobile users from the group whenever they experience brief disconnectivity. Later on, these users might attempt to reconnect to the group, but since the state of the application may have changed significantly (such as in bidding in a mobile auction), they may have lost the chance to be a part of the group.
Choosing a longer interval for a time-out would force all connected users to wait for the users who might have been permanently disconnected. This result would also inhibit the performance of applications for most other users still part of the group. To avoid these extremes, finding an optimal or near-optimal time-out is necessary for achieving strong performance from m-commerce applications for most users. Figure 3 outlines a scenario involving the effect of intermittent and brief disconnectivity for which three different solutions are possible: in one, the group is forced to wait until a particular user sends an input; in the second, the group waits only for some length of time determined by previous values; and in the third, the group waits for different lengths of time, depending on user type: passive listener, active listener, or active participant.
For the first type, the passive listener can be removed from the group, allowed to join again later without affecting the group's overall status. For the second type, involving active listeners, the group can wait for some length of time. And for the third type, involving active participants, the group can wait longer, as the input from these users is likely to affect the outcome of the overall group application. A trade-off can balance overhead resulting from the continued information transmission to users who may no longer be members (longer time-outs) against the overhead of joining the operation later (shorter time-outs).
These schemes should be compared under different mobility patterns for a particular m-commerce application. Applications requiring longer response time might work better with the first one due to its simplicity and less membership overhead, though in its worst case, it lacks an upper bound on delays caused by certain users. More sophisticated m-commerce applications with minimal-delay requirements may benefit from the second or third. Choosing can hinge on tolerable processing overhead.
The loss of packets and acknowledgmentsno matter what the reasonaffects m-commerce applications differently. Losing one or more messages in a mobile advertising application is not an issue, but packet loss in a mobile auction can affect the application's overall result. Reliability can be addressed at two levels: transaction and application. At the transaction level, all steps are ordered and executed in sequence. Unless a step has been completed (or has overcome packet loss), the next step is not attempted. If a step is unable to complete in a certain time, then a time-out may occur, and the transaction may have to be aborted and attempted later. Such techniques may have to be weighed against an m-commerce application's specific reliability needs before it is deployed.
Conclusion
Wireless multicast is required for a range of emerging wireless applications employing group communication among mobile users. I've attempted here to address both infrastructure and ad hoc configurations, as well as such factors as security and reliability. In the future, as wireless devices allow users to access or roam multiple wireless networks, a group m-commerce application might span multiple heterogeneous wireless networks. Such a ubiquitous application would require both multicast protocol and middleware support to overcome differences in bit rates, channel quality, resources, location management, reliability, and security. Further effort is needed to address these issues, along with those related to widespread deployment, including business models for charging users on the network and distributing revenue among carriers and content providers.
References
1. Deering, S. Host Extension for IP Multicasting, Internet RFC 1112 (Aug. 1989).
2. Diot, C., Dabbous, W., and Crowcroft, J. Multipoint communication: A survey of protocols, functions, and mechanisms. IEEE J. Selected Areas Commun. 15, 3 (Apr. 1997), 277290.
3. Eriksson, H. MBone: The multicast backbone. Commun. ACM 37, 8 (Aug. 1994), 5460.
4. Kent, S. and Atkinson, R. Security Architecture for the Internet Protocol, IETF RFC 2401 (Nov. 1998).
5. Lee, S., Su, W., and Gerla, M. On-Demand Multicast Routing Protocol for Ad Hoc Networks (Internet-Draft). MANET Working Group, 1999.
6. Nikaein, N. and Bonnet, C. Wireless multicasting in an IP environment. In Proceedings of the 5th International Workshop on Mobile Multimedia Communication MoMuc'98 (Berlin, Germany, Oct. 1214). IEEE Computer Society Press, 1998.
7. Royer, E. and Perkins, C. Multicast operation of the ad-hoc on-demand distance vector routing protocol. In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom) (Seattle, Aug. 1519). ACM Press, New York, 1999, 207218.
8. Shields, C. and Garcia-Luna-Aceves, J. KHIP: A scalable protocol for secure multicast routing. In Proceedings of ACM SIGCOMM '99 (Boston, Aug. 31Sept. 3). ACM Press, New York, 1999, 5364.
9. Varshney, U. Multicast communications over wireless and mobile networks (tutorial notes). At the 5th ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom). (Seattle, Aug. 1519, 1999).
10. Varshney, U. and Chatterjee, S. Architectural issues in IP multicast over wireless networks. In Proceedings of the IEEE International Wireless Communications Networking Conference (WCNC) (New Orleans, Sept. 2124). IEEE Computer Society Press, 1999, 4145.
11. Varshney, U. and Vetter, R. Mobile commerce: Framework, applications, and networking support. ACM/Kluwer J. Mobile Net. Appli. 7, 3 (June 2002), 185193.
12. Xylomenos, G. and Polyzos, G. IP multicast for mobile hosts. IEEE Commun. Mag. 35, 1 (Jan. 1997), 5458.
Figures
Figure 1. IP multicast support in the MBone using tunneling.
Figure 2. Multicast routing in ad hoc wireless networks.
Figure 3. The effect of intermittent connectivity on mobile commerce applications: possible scenarios and outcomes
Tables
Table 1. Qualitative comparison of wired and wireless multicast.
Table 2. Possible solutions to pricing wireless multicast service and distribution of revenue.
©2002 ACM 0002-0782/02/1200 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2002 ACM, Inc.
No entries found