Tree multicast strategies in mobile,multihop wireless networks

Tree multicast is a well established concept in wired networks. Two versions, persource tree multicast (e.g., DVMRP) and shared tree multicast (e.g., Core Based Tree), account for the majority of the wireline implementations. In this paper, we extend the tree multicast concept to wireless, mobile, multihop networks for applications ranging from ad hoc networking to disaster recovery and battlefield. The main challenge in wireless, mobile networks is the rapidly changing environment. We address this issue in our design by: (a) using soft state (b) assigning different roles to nodes depending on their mobility (2level mobility model); (c) proposing an adaptive scheme which combines shared tree and persource tree benefits, and (d) dynamically relocating the shared tree Rendezvous Point (RP). A detailed wireless simulation model is used to evaluate various multicast schemes. The results show that persource trees perform better in heavy loads because of the more efficient traffic distribution; while shared trees are more robust to mobility and are more scalable to large network sizes. The adaptive tree multicast scheme, a hybrid between shared tree and persource tree, combines the advantages of both and performs consistently well across all load and mobility scenarios. The main contributions of this study are: the use of a 2level mobility model to improve the stability of the shared tree, the development of a hybrid, adaptive persource and shared tree scheme, and the dynamic relocation of the RP in the shared tree.     

Mobility Management for Hierarchical Wireless Networks

In this paper, we consider the mobility management in large, hierarchically organized multihop wireless networks. The examples of such networks range from battlefield networks, emergency disaster relief and law enforcement etc. We present a novel network addressing architecture to accommodate mobility using a Home Agent concept akin to mobile IP. We distinguish between the physical routing hierarchy (dictated by geographical relationships between nodes) and logical hierarchy of subnets in which the members move as a group (e.g., company, brigade, battalion in the battlefield). The performance of the mobility management scheme is investigated through simulation.     

Traffic model for third generation cellular mobile telecommunication systems

Traffic analysis for third generation mobile telecommunication systems should take into account a variety of services (e.g., voice, data, video) and environments (private, public outdoor, public indoor) as well as the user mobility behavior. The analytical traffic model presented in this paper incorporates all the above mentioned features. The model utilizes a set of simplifying assumptions regarding the distribution of certain random time intervals (e.g., call duration and cell residence time) and the handover arrival process. The core of the model focuses on the estimation of the cell border crossing rate and the time it takes a busy mobile user to leave a cell area. This allows for the estimation of the handover rate and the call duration within a cell, which in turn, utilizing an iterative method, allows for the calculation of the offered traffic load per cell. The major advantages of the model are: (a) the simple closed form solutions, (b) its independence from the applied radio resource management scheme, and (c) its accuracy. The latter is validated via a simulation tool, which accommodates different cell-layout scenarios over a geographical area, representing a typical city center, modeled as a Manhattan grid.     

Simulation‐based performance evaluation of routing protocols for mobile ad hoc networks

In this paper we evaluate several routing protocols for mobile, wireless, ad hoc networks via packetlevel simulations. The ad hoc networks are multihop wireless networks with dynamically changing network connectivity owing to mobility. The protocol suite includes several routing protocols specifically designed for ad hoc routing, as well as more traditional protocols, such as link state and distance vector, used for dynamic networks. Performance is evaluated with respect to fraction of packets delivered, endtoend delay, and routing load for a given traffic and mobility model. Both small (30 nodes) and medium sized (60 nodes) networks are used. It is observed that the new generation of ondemand routing protocols use much lower routing load, especially with small number of peertopeer conversations. However, the traditional link state and distance vector protocols provide, in general, better packet delivery and endtoend delay performance.     

A general purpose proxy filtering mechanism applied to the mobile environment

Host mobility complicates the standard networking model in unexpected ways. It increases network heterogeneity, causing difficulty within applications that expect a high or constant amount of network bandwidth. Mobility increases cost when a user switches from a relatively inexpensive high bandwidth network to a low bandwidth paybycall or paybybyte network. Mobility may also reduce security when a user moves from a safe network onto a foreign one. This situation can be improved by introducing a proxy between the mobile client and its peer. The purpose of this intermediary is to process data moving between the client and peer. The type of processing performed depends on the desired result: the proxy can hide network heterogeneity via data filtering, reduce cost by using compression, and increase security through the use of secure protocols between the client and proxy. This paper presents a general purpose proxy system and how it has been applied to the mobile environment. The overall architecture is described, examples of its use given, and a study on its feasibility and performance is presented.     

A scalable wireless virtual LAN

This paper presents a Wireless Virtual Local Area Network (WVLAN) to support mobility in IPoverATM local area networks. Mobility is handled by a joint ATMlayer handoff for connection rerouting and MAClayer handoff for location tracking, such that the effects of mobility are localized and transparent to the higherlayer protocols. Different functions, such as Address Resolution Protocol (ARP), mobile location, and ATM connection admission are combined to reduce protocol overhead and frontend delay for connectionless packet transmission in connectionoriented ATM networks. The proposed WVLAN, through the use of ATM technology, provides a scalable wireless virtual LAN solution for IP mobile hosts.     

A selective location update strategy for PCS users

A new location update strategy for personal communication services (PCS) networks and its implementation using a genetic algorithm are proposed. Most of the practical cellular mobile systems partition a geographical region into location areas (LAs) and users are made to update on entering a new LA. The main drawback of this scheme is that it does not consider the individual user mobility and call arrival patterns. Combining these factors with the LAbased approach, we propose an optimal update strategy which determines whether or not a user should update in each LA, and minimizes the average location management cost derived from a userspecific mobility model and call generation pattern. The location management cost optimization problem is also elegantly solved using a genetic algorithm. Detailed simulation experiments are conducted to capture the effects of mobility and callarrival patterns on the location update strategy. The conclusion from this work is that skipping location updates in certain LAs leads to the minimization of the overall location management cost for a user with a specific mobility pattern and even with moderately high call arrival rate.     

Predictive Caching Strategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks

Route caching strategy is important in on-demand routing protocols in wireless ad hoc networks. While high routing overhead usually has a significant performance impact in low bandwidth wireless networks, a good route caching strategy can reduce routing overheads by making use of the available route information more efficiently. In this paper, we first study the effects of two cache schemes, link cache and path cache, on the performance of on-demand routing protocols through simulations based on the Dynamic Source Routing (DSR) protocol. Since the path cache DSR has been extensively studied, we focus in this paper on the link cache DSR in combination with timer-based stale link expiry mechanisms. The effects of different link lifetime values on the performance of routing protocol in terms of routing overhead, packet delivery ratio and packet latency are investigated. A caching strategy incorporating adaptive link timeout is then proposed, which aims at tracking the optimal link lifetime under various node mobility levels by adaptively adjusting the link lifetime based on the real link lifetime statistics. The performance of the proposed strategy is then compared with the conventional path cache DSR. The results show that without a timeout mechanism, a link cache scheme may suffer severe performance degradation due to the use of broken routes, while the proposed adaptive link cache strategy achieves significantly improved performance by reducing the routing overhead when the network traffic load is high.     

A reservation-based multicast (RBM) routing protocol for mobile networks: initial route construction phase

We propose a combined multicast routing, resource reservation and admission control protocol, termed Reservation-Based Multicast (RBM), that borrows the Rendezvous Point or Core concept from multicast routing algorithms proposed for the Internet, but which is intended for operation in mobile networks and routes hierarchically-encoded data streams based on user-specified fidelity requirements, real-time delivery thresholds and prevailing network bandwidth constraints. The protocol exhibits the fully distributed operation and receiver-initiated orientation of these proposed algorithms; but, unlike them, the protocol is tightly coupled to a class of underlying, distributed, unicast routing protocols thereby facilitating operation in a dynamic topology. This paper focuses on the initial route construction phase, assumed to occur during a static snapshot of the dynamic topology, and is therefore applicable to fixed networks as well, e.g. the Internet.This work was sponsored by the U.S. Navy and the American Society for Engineering Education under the U.S. Navy's Summer Faculty Research Program.Each application must specify a mechanism for ensuring that a processor is always aware of its associated entities. For example, in the current Internet architecture, a group membership protocol [2] serves a similar function of keeping routers informed of the membership their directly attached subnetworks.A processor can be viewed as either an IP router or an ATM switch.     

A framework for delivering multicast messages in networks with mobile hosts

To accommodatemobile hosts (MHs) within existing data networks, the static network is augmented with mobile support stations (MSSs) that communicate directly with MHs, usually via wireless links. Connectivity of the overall network changes dynamically as MHs connect to the static network from different locations (MSSs) at different times. Compared to their desktop counterparts, mobile hosts face a new set of constraints namely, low bandwith of the wireless links, tight constraints on power consumption and a significantly lower computing capability. Thus, even without considering failures, integration of mobile computer within existing networks pose a new set of problems. In this paper, we look at the problems associated with delivering multicast meassages to mobile hosts. First, we identify how a mobile host's ability to connect to different MSSs at different times, affects delivery of multicast messages and present schemes to deliver multicast messages to MHs fromatleast-one location, fromatmost-one location, and fromexactly-one location. Next, we introduce multicast groups of mobile hosts wherein each multicast group is associated with a host view, a set of MSSs representing theaggregate location information of the group. A host-view membership algorithm is then presented and combined with the multicast scheme for exactly-once delivery. As a result, to deliver a multicast message to a specified group, copies of the message need be propagated only to the MSSs in the group's host-view.This work was done while the author was a graduate student at Rutgers University.This research work was supported in part by ARPA under contract number DAAH04-95-1-0596, NSF grant numbers CCR 95-09620, IRIS 95-09816 and sponsors of WINLAB.     

mPERSONA: Personalized Portals for the Wireless User: An Agent Approach

The needs of the wireless and mobile user regarding information access and services are quite different than those of the desktop user. This need is not about browsing the Web but about receiving personalized services that are highly sensitive to the immediate environment and requirements of the user. Personalization appears to be the most appropriate solution to this need. It comes into aid by creating personalized portals that are specific for the wireless user, which (a) are focus on the local content and (b) directly tones down factors that break up the functionally of the Internet/wireless services when viewed through wireless devices; factors like the click count, user response time (the choice factor) and the size of the wireless network traffic. In this paper we present a flexible personalization system for the wireless user that takes into consideration user mobility, the local environment and the user and device profile. The system utilizes the various characteristics of mobile agents to support flexibility, scalability, modularity and user mobility. We present metrics appropriate to the wireless environment, and an initial performance evaluation indicating improvement ranging from 33% up to, for certain metrics, 60%.     

GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks

A mobile ad hoc network (MANET) is one consisting of a set of mobile hosts capable of communicating with each other without the assistance of base stations. One prospective direction to assist routing in such an environment is to use location information provided by positioning devices such as global positioning systems (GPS). In this paper, we propose a new routing protocol called GRID, which tries to exploit location information in route discovery, packet relay, and route maintenance. Existing protocols, as compared to ours, are either not location-aware or partially location-aware in that location knowledge is not fully exploited in all these three aspects. One attractive feature of our protocol is its strong route maintenance capability – the intermediate hosts of a route can perform a handoff operation similar to that in cellular systems when it roams away to keep a route alive. This makes routes in the MANET more stable and insensitive to host mobility. Simulation results show that our GRID routing protocol can reduce the probability of route breakage, reduce the number of route discovery packets used, and lengthen routes' lifetime.     

Mobile ATM buffer capacity analysis

This paper extends a stochastic theory for buffer fill distribution for multiple on and off sources to a mobile environment. Queue fill distribution is described by a set of differential equations assuming sources alternate asynchronously between exponentially distributed periods in on and off states. This paper includes the probabilities that mobile sources have links to a given queue. The sources represent mobile user nodes, and the queue represents the capacity of a switch. This paper presents a method of analysis which uses mobile parameters such as speed, call rates per unit area, cell area, and call duration and determines queue fill distribution at the ATM cell level. The analytic results are compared with simulation results.This paper is partially funded by ARPA contract number J-FBI-94-223.The Mathematica code for this paper can be found on http://www.tisl.ukans.edu/sbush.     

Replication Requirements in Mobile Environments

Replication is extremely important in mobile environments because nomadic users require local copies of important data. However, today's replication systems are not mobile-ready. Instead of improving the mobile user's environment, the replication system actually hinders mobility and complicates mobile operation. Designed for stationary environments, the replication services do not and cannot provide mobile users with the capabilities they require. Replication in mobile environments requires fundamentally different solutions than those previously proposed, because nomadicity presents a fundamentally new and different computing paradigm. Here we outline the requirements that mobility places on the replication service, and briefly describe ROAM, a system designed to meet those requirements.     

Scheduling and bandwidth allocation for the distribution of archived video in VOD systems

Providing costeffective videoondemand (VOD) services necessitates reducing the required bandwidth for transporting video over highspeed networks. In this paper, we investigate efficient schemes for transporting archived MPEGcoded video over a VOD distribution network. A video stream is characterized by a timevarying traffic envelope, which provides an upper bound on the bit rate. Using such envelopes, we show that video streams can be scheduled for transmission over the network such that the perstream allocated bandwidth is significantly less than the source peak rate. In a previous work [13], we investigated stream scheduling and bandwidth allocation using global traffic envelopes and homogeneous streams. In this paper, we generalize the scheduling scheme in [13] to include the heterogeneous case. We then investigate the allocation problem under windowbased traffic envelopes, which provide tight bounds on the bit rate. Using such envelopes, we introduce three streamscheduling schemes for multiplexing video connections at a server. The performance of these schemes is evaluated under static and dynamic scenarios. Our results indicate a significant reduction in the perstream allocated bandwidth when stream scheduling is used. While this reduction is obtained through statistical multiplexing, the transported streams are guaranteed stringent, deterministic quality of service (i.e., zero loss rate and small, bounded delay). In contrast to video smoothing, our approach requires virtually no buffer at the settop box since frames are delivered at their playback rate.     

A Layer 3 Movement Detection Algorithm Driving Handovers in Mobile IP

The evolution and the spreading of wireless access technology and the consequent increase of user mobility will make handover procedures critical for the provision of Quality of Service in the next generation wireless Internet. Often, layer 3 handovers are supposed to be driven by access layer procedures. In this way, the movement detection delay can be reduced, but at the expenses of making the Mobile IP protocol dependent of lower layer implementations. Furthermore, this approach may not be effective when users roam among heterogeneous networks. Nevertheless, movement detection algorithms, which operate at the Mobile IP layer, imply appreciable delays, usually intolerable for real time services.In this paper, we propose a Mobile IP handover scheme based on a novel movement detection algorithm at layer 3, able to timely manage migrations by exploiting advertisements losses, combined with a two-timers mechanism.We analyze the performance of our algorithm in terms of handover delay and throughput, and we show that our solution is able to decrease the movement detection delay as much as 47% with respect to other literature solutions that pursue similar approaches. In addition, this feature implies also higher values of the throughput seen by the TCP layer.This work has been carried out in the framework of the FIRB Project PRIMO, co-financed by the Italian Ministry for Education, Higher Education and Research (MIUR).Nicola Blefari Melazzi received his Laurea degree in Electrical Engineering in 1989, magna cum laude with publication of his thesis, and earned the Dottore di Ricerca (Ph.D.) in Information and Communication Engineering in 1994, both at the University of Roma La Sapienza, Italy. In 1993 he joined the University of Roma Tor Vergata, as an Assistant Professor. From 1998 to 2002 he has been an Associate Professor at the University of Perugia. In 2002 he came back to the University of Roma Tor Vergata as a Full Professor of Telecommunications.Dr. Blefari-Melazzi has been involved in consulting activities and research projects, including standardization and performance evaluation work. His research projects have been funded by the Italian Ministry of Education, University and Research, by the Italian National Research Council, by industries, by the European Union and by the European Space Agency. He also reviewed research proposals and research projects.Dr. Blefari-Melazzi served as reviewer, TPC member, session chair and guest-editor to IEEE conferences and journals.His research interests include the performance evaluation, design and control of broadband integrated networks, wireless LANs and satellite networks. He is also conducting research on multimedia traffic modeling, mobile and personal communications, quality of service guarantees and real time services support in the Internet.Mauro Femminella received his Laurea degree in Electronic Engineering in 1999, magna cum laude with publication of his thesis, and earned the Ph.D. degree in Electronic Engineering in 2003, both at the University of Perugia, Italy. He was Consulting Engineer for the University of Perugia, and for the consortia CoRiTel and RadioLabs. Actually he holds a position as contract researcher at the Department of Information and Electronic Engineering at the University of Perugia.He was involved in a number of research projects co-funded by the European Union (programs ACTS and IST), by the Italian Ministry for Education, Higher Education and Research (MIUR), and by the European Space Agency (ESA).He is co-author of a number of papers in international conferences and journals.His research interests focus on design and performance evaluation of satellite networks, content delivery networks, IP quality of service and IP mobility.Fabio Pugini received his laurea degree (M.S.) in Electronic Engineering (magna cum laude) in 2000 from University of Rome La Sapienza. He was with the INFOCOM Dept. of the same University during 2001 and 2002 as Ph.D. student in Computer Science. His main research interests regarded Mobility issues and QoS provision in IP networks. He was consulting engineer for the DIEI Department of the University of Perugia and was involved in the following European Projects: SUITED, WHYLESS.COM, FIFTH. In 2002 he received his M.B.A. degree from University of Rome Tor Vergata. He worked as a system analyst in MBDA Missile Defense Systems and currently he is with McKinsey & Company as a Junior Associate.     

Active tracking: Locating mobile users in personal communication service networks

The problem of tracking mobile users in Personal Communication Service (PCS) networks is discussed. We propose a novel approach for reducing the wireless cost of tracking users. The basic idea is to use nonutilized system resources for initiating queries about the location of mobile users, in addition to the process of user registration. Queries are applied at each cell, independently of the other cells, whenever the load on the local control channel drops below a predefined threshold. Our study focuses on two issues: (1) proposing the initiated queries approach and an algorithm for its application, and (2) studying and quantifying the value of location information and evaluating the parameters affecting it. Our analysis shows that the expected benefit due to location knowledge in a Markovian motion model depends, among other things, on the determinant of the transition matrix and on the variability of the location distribution function. The active tracking approach, as opposed to other dynamic strategies, does not require any modification of user equipment. The importance of this property is in its practicality: An implementation of a new registration strategy in current systems would require a modification of the users equipment. Moreover, the proposed method can be easily implemented in addition to any known tracking strategy, to reduce further the tracking cost. The performance of the active tracking method is evaluated under two registration strategies: The geographicbased strategy, currently used in cellular networks, and the profilebased strategy, suggested elsewhere. Under both strategies, it significantly reduces the tracking cost.     

Demand re‐registration for PCS database restoration

In a Personal Communications Services (PCS) network, mobility databases such as Home Location Register (HLR) and Visitor Location Register (VLR) are utilized to support mobility management for Mobile Stations (MSs). If the location databases fail, the location information loss or corruption will seriously degrade the service offered to the subscribers. In this paper, we propose a new VLR failure recovery scheme called demand reregistration. In this scheme, the VLR broadcasts a reregistration request to all MSs after the VLR failure. When an MS receives the reregistration request, it sends a registration message to the VLR to recover the location record. Since all MSs will reregister after receiving the broadcasting request, traffic jam (and thus collisions) may occur. If a collision occurs, then the involved MSs must resend the registration messages. This paper studies the performance of demand reregistration by investigating how effectively the reregistration can recover the location record for an MS before the first MS call termination occurs. Our results indicate that demand reregistration can effectively recover VLR failure.     

Quality Determination for Gate Delay Fault Tests Considering Three-State Elements

Most industrial digital circuits contain three-state elements besides pure logic gates. This paper presents a gate delay fault simulator for combinational circuits that can handle three-state elements like bus drivers, transmission gates and pulled busses. The well known delay faults--slow-to-rise and slow-to-fall--are considered as well as delayed transitions from isolating signal state high impedance to binary states 0 and 1 and vice versa. The presented parallel delay fault simulator distinguishes between non-robust, robust and hazard free tests and determines the quality of a test. Experimental results for ISCAS85/89 benchmark circuits are presented as well as results for industrial circuits containing three-state elements.     

Admission control with priorities: Approaches for multi‐rate wireless systems

Priority based linkbandwidth partitioning is required to support wireless multimedia services, having diverse QoS (delay, throughput) requirements, in mobile ad hoc networks with multimedia nodes. A new class of service disciplines, termed batch and prioritize or BP admission control (AC), is proposed. The BP algorithms use the delay tolerance of applications to batch requests in time slots. Bandwidth assignment is made either at the end of the slot, or during the slot, on a priority basis. Analytical and simulation models are developed to quantify the performance of the BP schemes. The results are compared with those obtained for a FirstComeFirstServed (FCFS) service discipline. The class of BP schemes trade off the delay and loss tolerance of applications to improve the net carried traffic on the link. Further, such schemes enable an easy implementation for adaptive prioritization, where the degree of precedence given to an application varies with offered load and the link capacity.