We propose a gaining architecture, called the overlay server system (OSS), for supporting multiparty online games over mobile networks. In OSS architecture, overlay server nodes (OSN) are distributed across the core network architecture of the mobile operator and each node is responsible for both running the game applications and performing the overlay routing. The architecture allows third party game servers that are located outside the core network of the mobile operator to push the execution of delay and bandwidth constrained game components into the core to achieve better quality of service (QoS). When a game consists of multiple mutually exclusive game objects such that each object can be maintained independently, OSS allows per object QoS optimization via selecting the jointly optimal location (i.e. OSN) and overlay routes for each object. This fine-grain optimization benefits most when different objects have different QoS requirements and they are accessed by different users. OSS dynamically adapts to the changes in game and network conditions by switching to better OSN and overlay routes. Our performance analysis on different core network topologies and usage patterns demonstrates that OSS has significant advantages over the alternative peer to peer (P2P), proxy-server, and client-server architectures. The analysis also underlines the individual contributions of object placement and jointly performed overlay route optimization to the performance gain.

Wireless local area networks (WLANs) are emerging as a popular technology for access to the Internet and enterprise networks. In the long term, the success of WLANs depends on services that support mobile network clients. Although other researchers have explored mobility prediction in hypothetical scenarios, evaluating their predictors analytically or with synthetic data, few studies have been able to evaluate their predictors with real user mobility data. As a first step towards filling this fundamental gap, we work with a large data set collected from the Dartmouth College campus-wide wireless network that hosts more than 500 access points and 6,000 users. Extending our earlier work that focuses on predicting the next-visited access point (i.e., location), in this work we explore the predictability of the time of user mobility. Indeed, our contributions are two-fold. First, we evaluate a series of predictors that reflect possible dependencies across time and space while benefiting from either individual or group mobility behaviors. Second, as a case study we examine voice applications and the use of handoff prediction for advance bandwidth reservation. Using application-specific performance metrics such as call drop and call block rates, we provide a picture of the potential gains of prediction. Our results indicate that it is difficult to predict handoff time accurately, when applied to real campus WLAN data. However, the findings of our case study also suggest that application performance can be improved significantly even with predictors that are only moderately accurate. The gains depend on the applications’ ability to use predictions and tolerate inaccurate predictions. In the case study, we combine the real mobility data with synthesized traffic data. The results show that intelligent prediction can lead to significant reductions in the rate at which active calls are dropped due to handoffs with marginal increments in the rate at which new calls are blocked.

We present an empirical registration model derived from the WLAN registration patterns of the mobile users. There exist models that accurately describe individually the spatial and temporal aspects of user registration, and demonstrate the importance of this modeling. The main distinction of the new model from the previous empirical models is that we are able to formulate the inter-dependence of space and time explicitly by a set of few equations. Our extensive studies of the WLAN traces indicate that a simple but proper notion of popularity radient suffices to capture the correlation across space and time. Indeed, when locations (i.e., AP coverage area) are differentiated with respect to the number of visits they are receiving (i.e., AP popularity), the time spent at each location i before user moves from i to k turns out to be closely related to the difference of popularity between locations i and k This observation led to the design of a joint time-space registration model (referred to as ModelT++) that builds upon the Model T, which itself models only the space aspect of the registration, but is derived from the same campus WiFi network. As part of the process of generating a joint space-time model, we further extend spatial aspects of the Model T. We evaluate our model using various metrics against a random walk model as well as the Model T by superimposing location independent time series on these space-only registration models. Our results suggest that with a slight increase in the model complexity, our joint time-space registration model is able to better capture the real network registration than the independent time models. Model T++ can be easily integrated into both WLAN and multi-hop wireless mesh network simulations that require realistic registration models.

Location is an important feature for many applications, and wireless networks may serve their clients better by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors using a two-year trace of the mobility patterns of more than 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. The surprising results provide critical evidence for anyone designing or using mobility predictors. We implemented and compared the prediction accuracy of several location predictors drawn from four major families of domain-independent predictors, namely, Markov-based, compression-based, PPM, and SPM predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors

We derive an empirical model for spatial registration patterns of mobile users as they move within a campus wireless local area network (WLAN) environment and register at different access points. Such a model can be very useful in a variety of simulation studies of the performance of mobile wireless systems, such as that of resource management and mobility management protocols. We base the model on extensive experimental data from a campus WiFi LAN installation, representing traces from about 6000 users over a period of about 2 years. We divide the empirical data available to us into training and test data sets, develop the model based on the training set, and evaluate it against the test set.The model shows that user registration patterns exhibit a distinct hierarchy, and that WLAN access points (APs) can be clustered based on registration patterns. Cluster size distributions are highly skewed, as are intra-cluster transition probabilities and trace lengths, which can all be modeled well by the heavy-tailed Weibull distribution. The fraction of popular APs in a cluster, as a function of cluster size, can be modeled by exponential distributions. There is general similarity across hierarchies, in that inter-cluster registration patterns tend to have the same characteristics and distributions as intra-cluster patterns.We generate synthetic traces for intra-cluster transitions, inter-cluster transitions, and complete traces, and compare them against the corresponding traces from the test set. We define a set of metrics that evaluate how well the model captures the empirical features it is trying to represent. We find that the synthetic traces agree very well with the test set in terms of the metrics. We also compare the model to a simple modified random waypoint model as a baseline, and show the latter is not at all representative of the real data.The user of the model has the opportunity to use it as is, or can modify model parameters, such as the degree of randomness in registration patterns. We close with a brief discussion of further work to refine and extend the model.

Energy is a fundamental resource limitation in mobile and wireless devices. Much research in mobile and wireless networking over the past decade has examined ways of reducing energy usage, including specific techniques such as energy-aware protocols for routing and communication. However, to our knowledge, no systematic way has been developed for reasoning generally about the energy consumption of algorithms. A method for analyzing energy complexity at an abstract algorithmic level would be invaluable. However, it is not clear if we can develop a uniform abstract model of energy complexity that has both theoretical and practical value. This paper surveys techniques for modeling and minimizing energy consumption at various system levels, so as to place algorithmic energy complexity in perspective. We then discuss the attributes an energy complexity model should have, and describe our initial approach towards developing such a model. We end by discussing future technical directions.

We consider the problem of maintaining end-to-end security in the presence of intelligent proxies that may adaptively modify data being transmitted across a network. The video coding community considers this problem in the context of transcoding media streams, but their approaches either fail to address authentication or fail to provide meaningful security guarantees. We present two provably-secure schemes, LISSA and TRESSA, that allow an intelligent network intermediary to intercept a stream signed by a content provider, and adapt it dynamically, while preserving the ultimate receiver's ability to securely verify the content provider's signature (and, hence, authenticity and integrity of the data received). Our schemes allow the intermediary to selectively remove portions of the stream and, thus, permit common media transcoding techniques such as scalable compression and multiple file switching. Moreover, a content provider only has to encode and sign its entire data stream once, as opposed to nondynamically encoding and signing different versions for each anticipated combination of device, network configuration, and channel condition. Our implementation results demonstrate efficiency.

We present algorithms for estimating the location of stationary and mobile users based on heterogeneous indoor RF technologies. We propose two location algorithms, selective fusion location estimation (SELFLOC) and region of confidence (RoC), which can be used in conjunction with classical location algorithms such as triangulation, or with third-party commercial location estimation systems. The SELFLOC algorithm infers the user location by selectively fusing location information from multiple wireless technologies and/or multiple classical location algorithms in a theoretically optimal manner. The RoC algorithm attempts to overcome the problem of aliasing in the signal domain, where different physical locations have similar RF characteristics, which is particularly acute when users are mobile. We have empirically validated the proposed algorithms using wireless LAN and Bluetooth technology. Our experimental results show that applying SELFLOC for stationary users when using multiple wireless technologies and multiple classical location algorithms can improve location accuracy significantly, with mean distance errors as low as 1.6 m. For mobile users we find that using RoC can allow us to obtain mean errors as low as 3.7 m. Both algorithms can be used in conjunction with a commercial location estimation system and improve its accuracy further.

Location is an important feature for many applications, and wireless networks can better serve their clients by anticipating client mobility. As a result, many location predictors have been proposed in the literature, though few have been evaluated with empirical evidence. This paper reports on the results of the first extensive empirical evaluation of location predictors, using a two-year trace of the mobility patterns of over 6,000 users on Dartmouth's campus-wide Wi-Fi wireless network. We implemented and compared the prediction accuracy of several location predictors drawn from two major families of domain-independent predictors, namely Markov-based and compression-based predictors. We found that low-order Markov predictors performed as well or better than the more complex and more space-consuming compression-based predictors. Predictors of both families fail to make a prediction when the recent context has not been previously seen. To overcome this drawback, we added a simple fallback feature to each predictor and found that it significantly enhanced its accuracy in exchange for modest effort. Thus the Order-2 Markov predictor with fallback was the best predictor we studied, obtaining a median accuracy of about 72% for users with long trace lengths. We also investigated a simplification of the Markov predictors, where the prediction is based not on the most frequently seen context in the past, but the most recent, resulting in significant space and computational savings. We found that Markov predictors with this recency semantics can rival the accuracy of standard Markov predictors in some cases. Finally, we considered several seemingly obvious enhancements, such as smarter tie-breaking and aging of context information, and discovered that they had little effect on accuracy. The paper ends with a discussion and suggestions for further work.

Most development of cellular communications technology has been focused on providing services to the wealthiest 20% of the world's population - the top of the economic pyramid. We discuss the motivation for serving the bottom of the pyramid (BoP), loosely defined as the 4 billion people earning less that US$2000/year. We consider the design requirements for a rural wireless telecommunications system for the BoP, and how they differ from traditional cellular system and WLL requirements. We discuss alternative technologies and architectures for meeting these requirements, ranging from satellite to WLAN systems. We then present our initial link analysis showing that cellular systems based on WCDMA or OFDM meet the requirements with small modifications. We end with some discussion of open problems and further work.

There has been a surge of interest in the delivery of personalized information to users (e.g., personalized stocks or travel information), particularly as mobile users with limited terminal device capabilities increasingly desire updated and targeted information in real time. When the number of information recipients is large and there is sufficient commonality in their interests, as is often the case, IP multicast is an efficient way of delivering the information. However, IP multicast services do not consider the structure and semantics of the information in the multicast process. We propose the use of Content-Based Multicast (CBM) where extra content filtering is performed at the interior nodes of the IP multicast tree; this will reduce network bandwidth usage and delivery delay, as well as the computation required at the sources and sinks. We evaluate the situations in which CBM is advantageous. The benefits of CBM depend critically upon how well filters are placed at interior nodes of the IP multicast tree and the costs depend upon those introduced by filters themselves. Further, we consider the benefits of allowing the filters to be mobile so as to respond to user mobility or changes in user interests and the corresponding costs of filter mobility. The criterion that we consider is the total network bandwidth utilization. For this criterion, we develop an optimal filter placement algorithm, as well as a heuristic that executes faster than the optimal algorithm. We evaluate the algorithms by means of simulation experiments. Our results indicate that filters can be effective in substantially reducing bandwidth. We also find filter mobility is worthwhile if there is marked large-scale user mobility. We conclude with suggestions for further work.

This paper examines the use of Bluetooth for a collaborative music creation system called codeBLUE where the low cost, low power and small dimensions of Bluetooth technology are critical. Dancers using the codeBLUE system wear clothing incorporating Bluetooth-enabled sensors that measure and transmit information about the dancers' movements to a Bluetooth access point positioned in the demonstration area, which in turn forwards the information to a control system. The system software transforms the simple dance movements into musical modifications in real time, altering the melodic, rhythmic, and dynamic properties of the music stream in terms of MIDI parameters. A configuration console allows the DJ to modify the effects that each type of sensor produces, providing him or her yet another channel of creativity and keeping the codeBLUE experience fresh for participants. The paper describes the architecture, design, and hardware and software implementation of the codeBLUE proof-of-concept prototype. The paper also discusses our evaluation of the technology used for this application. The system has been successfully demonstrated to a live audience.

We present a dynamic joint source and channel coding adaptation algorithm for the AMR speech codec based on the ITU-T Emodel. This model takes both delay and packet loss into consideration. We address the problem of finding the optimal choice of source and channel bit rates given QoS information about the wired and wireless IP network and subject to constraints on maximum packet loss, maximum delay and maximum allowed transmission rate. Our results show that an adaptation is necessary to preserve acceptable levels of quality while making optimal use of the allowed bandwidth. Our technique requires a small number of computations that allows real time operation in parallel to voice streams.

Future mobile devices will increasingly have multiple sources of location information associated with them, such as GPS, cellular cell-sector ID, Bluetooth or 802.11 wireless LAN. In fact, cellular phones with GPS receivers and 802.11 wireless LAN are already becoming available. However, not all location technologies will operate everywhere (e.g. GPS typically will not work indoors whereas 802.11 coverage may be available) and they typically have different accuracies and range. This paper presents an experimental study of the feasibility of using multiple wireless technologies simultaneously for location estimation. We have collected signal strength information from both IEEE 802.11 and Bluetooth wireless network technologies, developed and applied algorithms for determining location using data for each wireless technology, and then used a simple algorithm for fusing the location estimates from both technologies to try to enhance the accuracy of the location estimates.

We investigate fast IP handoffs in wireless LAN networks. As a simple mobile-controlled approach, we introduce mobile initiated tunneling handoff protocol for IPv4 (MITHv4). Our experimental results show that MITHv4 can achieve optimized low latency and low loss IP handoffs in wireless LAN networks. Furthermore, MITHv4 significantly reduces the link layer trigger requirements and substantial access network support to synchronize link layer and IP layer handoffs that fast Mobile IPv4 (FMIPv4) protocols heavily rely on. These benefits of MITHv4 are crucial for wireless LAN networks where the required link layer triggers for FMIPv4 are not feasible due to limited access network control.

The next generation of scripting languages for creating value-added services in converged networks will be based upon XML. Industry forums, like Parlay, JAIN and OSA, have developed open standard application program interfaces (APIs) to enable service creation in converged next generation networks (NGN). While services can be developed in traditional programming languages (e.g. Java or C++) using these APIs, XML-based scripting languages offer some advantages. While not as flexible or powerful as a programming language, scripting languages are typically easier to learn, and are language and platform independent. We describe the architecture and framework (creation, deployment and execution) of XML-based service scripts in NGN. We focus on the service control markup language (SCML) being developed by the JAIN forum for call control scripts that is closely tied to the JAIN Java call control (JCC) API. SCML is intended to be part of a family of NGN service scripting languages that include facilities for user interaction, mobility, and other open NGN API functions. We compare SCML to the call processing language (CPL) defined by the IETF and note that SCML offers several advantages. We also briefly compare it to the requirements that are being developed by the W3C voice browser working group.

In this paper we evaluate the situations in which CBM is advantageous. The benefits of CBM depend critically upon how well filters are placed at interior nodes of the IP multicast tree, and the costs depend upon those introduced by filters themselves. Further, we consider the benefits of allowing the filters to be mobile so as to respond to user mobility or changes in user interests, and the corresponding costs of filter mobility. We consider two criteria: minimizing total network bandwidth utilization and minimizing mean information delivery delay. For each criterion we develop an optimal filter placement algorithm, as well as a heuristic that executes faster than the optimal algorithm. Finally, we evaluate all the algorithms by means of simulation experiments. Our results indicate that filters can be effective in substantially reducing bandwidth and delay. We also find filter mobility is worthwhile if there is sufficient locality in the interests of users, or there is marked large-scale user mobility. We conclude with suggestions for further work.

We argue that pervasive computing offers not only tremendous opportunities and exciting research challenges but also possible negative environmental impacts, particularly in terms of physical waste and energy consumption. These environmental impacts will come under increasing government and consumer scrutiny, and like other disciplines (e.g. architecture, transportation), pervasive computing will have to adapt accordingly. Further, we argue that software-related issues will play an increasing role in reducing the environmental impact of computing. We thus propose that an important challenge for pervasive computing is to develop research in new architectures, design methodologies, metrics, algorithms and operating systems to minimize these impacts. We then discuss specific research issues and questions that arise in three phases of the device lifecycle: minimizing resource usage for manufacture and operation, maximizing device lifetime, and improving recyclability.

Article Free Access Share on MultECommerce: a distributed architecture for collaborative shopping on the WWW Authors: Stefano Puglia Applied Research, Telcordia Technologies, 445 South St, Morristown, NJ Applied Research, Telcordia Technologies, 445 South St, Morristown, NJView Profile , Robert Carter Applied Research, Telcordia Technologies, 445 South St, Morristown, NJ and Honeywell Technology Center, Minneapolis, MN Applied Research, Telcordia Technologies, 445 South St, Morristown, NJ and Honeywell Technology Center, Minneapolis, MNView Profile , Ravi Jain Applied Research, Telcordia Technologies, 445 South St, Morristown, NJ Applied Research, Telcordia Technologies, 445 South St, Morristown, NJView Profile Authors Info & Claims EC '00: Proceedings of the 2nd ACM conference on Electronic commerceOctober 2000 Pages 215–224https://doi.org/10.1145/352871.352895Published:17 October 2000Publication History 17citation918DownloadsMetricsTotal Citations17Total Downloads918Last 12 Months37Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Mobile agent technology has been proposed as an alternative to traditional client-server computing for personalized information retrieval by mobile and wireless users from fixed wired servers. We develop a very simplified analytical model that examines the claimed performance benefits of mobile agents over client-server computing for a mobile information retrieval scenario. Our evaluation of this simple model shows that mobile agents are not necessarily better than client-server calls in terms of average response times; they are only beneficial if the space overhead of the mobile agent code is not too large or if the wireless link connecting the mobile user to the fixed servers of the virtual enterprise is error-prone. We quantify the tradeoffs involved for a variety of scenarios and point out issues for further research.

The mobile IP (MIP) protocol for IP version 4 provides continuous Internet connectivity to mobile hosts. However, currently it has some drawbacks in the areas of survivability, performance, interoperability with protocols for providing QoS. We have proposed an alternative protocol, mobile IP with location registers (MIP-LR), which overcomes some of these drawbacks and is closer to the "service node" database approach used in the public switched telephone network (PSTN): before launching a packet to the mobile host, the sender first queries a database, called the home location register (HLR), to obtain the recipient's current location. MIP-LR is designed for operation in enterprise environments or within logical administrative domains. We focus on showing how MIP-LR enhances the survivability of MIP by eliminating some of the functions which MIP introduces for mobility support, allowing the HLR to be placed outside the mobile's home network in case the latter is particularly vulnerable, and replicating and distributing HLRs. We present two schemes for managing the multiple HLRs and enabling mobile and correspondent hosts to dynamically discover the addresses of the HLRs serving a given mobile host. The first scheme introduces a set of translation server (TS) databases while the second uses a form of quorum consensus based on the triangle lattice (TL); for the latter we present an enhanced protocol called the optimistic TL(OTL). For both schemes we present algorithms for mobile host registration and packet delivery, protocols for recovery from HLR failures, and complexity analysis of the overhead involved.

The mobile IP (MIP) protocol for IP version 4 as being standardized by the Internet community provides continuous Internet connectivity to mobile hosts, without requiring any changes to existing routers and higher-layer applications. We propose an alternative protocol, mobile IP with location registers (MIP-LR) which is closer to the "service node" database approach used in the public switched telephone network (PSTN): before launching a packet to the mobile host, the sender first queries a database to obtain the recipient's current location. MIP-LR is designed for operation in enterprise environments or within logical administrative domains, as it requires a sending host to be aware of which hosts are potentially mobile and implement the MIP-LR protocol. The benefits of MIP-LR are that potentially long routes, called "triangle routes", from the sender to the mobile host are avoided, encapsulation of packets sent to a mobile host is not required, the load on the home network as well as the home and foreign agents is reduced, and there is substantially improved interoperability with protocols such as RSVP for providing QoS guarantees. We carry out a simplified average-case analysis of the costs and benefits of MIP-LR and show it can result in significant reductions in mean network costs compared to MIP.

There has been considerable interest in delivering information to distributed mobile clients via wireless broadcast. Information transmitted periodically over wireless media can be regarded as a virtual disk, which we call an airdisk, analogous to a standard magnetic disk. Airdisks offer an efficient mechanism for delivering personalized information services to mobile clients with portable or laptop computers by broadcasting data and allowing clients to filter out the items of interest to them. We study the problem of scheduling the order in which data items are broadcast so as to minimize the access time of the clients, focusing on the case where the server inserts an index at the start of the broadcast period. We observe that the problem is analogous to that of determining how data should be laid out on the disk, and show that the problem is in general NP-complete. We develop a branch-and-bound procedure for solving the problem optimally, and then develop a fast, simple heuristic. The results of our simulation experiments show that the heuristic runs substantially faster than the branch-and-bound procedure, and yet produces schedules that are only slightly longer.

Future wired networks with an ATM backbone will need to support PCS and wireless subscriber services. One of the key functions required to support PCS and wireless subscribers with non-geographic phone numbers (NGPN) will be the ability to efficiently identify which home location register (HLR) database serves the subscriber. (Note that the same functionality is also needed to serve subscribers with portable phone numbers.) In a previous paper we have presented a scheme for NGPN translation based upon distributed, dynamic hashing. The scheme uses a hash function in the visitor location registers (VLR) and a set of distributed translation servers (TS) which store the NGPN-to-HLR mapping. We develop a simplified model for estimating the capital investment cost of deploying the NGPN translation scheme we have proposed. The model focuses on the incremental cost of providing NGPN service by estimating the installed first cost (IFC) of deploying TSs. The cost model assumes that PCS subscribers adopt NGPNs following the classic Fisher-Pry model of technological adoption, and takes into account user mobility, caching, the projected growth in the performance of computing servers, and projected decline in their cost, as well as inflation, the time value of money, and population growth. The cost model is fully parameterized, allowing network planners to substitute appropriate values to evaluate "what-if" scenarios. We illustrate its use for an example scenario. We also point out that the cost model itself is quite generic and may be applicable to other network costing and operations planning tasks.

An asymmetric air interface protocol is one which allocates more capacity for one direction of data transfer (in our case, the downlink) than the other. In this paper we report ongoing work on the need and initial design calculations for an asymmetric indoor air interface protocol which is suitable for integrated voice and data applications, and specifically for wireless Internet access. As an example we consider PACS-UB, a symmetric protocol for voice communication in the isochronous unlicensed PCS band (1920-1930 MHz), and present a mechanism for making it statically asymmetric, as well as dynamically asymmetric in response to traffic demands. We also present a simplified worst-case two-dimensional model of co-channel interference when the air interface protocol is dynamically asymmetric. The quantitative results of the model indicate that an asymmetric protocol can result in significant gains in spectral efficiency. In the worst case downlink co-channel interference can be significant, and we discuss possible mitigating techniques that could be used.

Current cellular subscribers have a geographic phone number (e.g., in AMPS and US digital cellular systems) or a number which contains the network provider's identity (e.g., in GSM), and whenever subscribers register or receive (and possibly, originate) a call, a home location register (HLR) database has to be queried. The wired infrastructure supports a function called global title translation (GTT) that converts the subscriber's number to an HLR database address. A special feature of next generation wireless access service will be to support personal communication services (PCS) and wireless subscribers with portable personal numbers, or nongeographic phone numbers (NGPNs), that do not indicate the service provider or HLR database serving the user. In addition, the GTT function may not be available when the wired backbone is an ATM network. Thus a key function required in future wireless access systems with wired ATM backbones will be the ability to translate an NGPN to the identity of the HLR which serves the subscriber, a process we call NGPN translation. We discuss the requirements of NGPN translation and some alternative schemes. We propose two schemes for fast, efficient, scalable and flexible NGPN translation which use ideas of dynamic hashing, caching, and indirection. The schemes use a hash function in the visiting location registers (VLRs) (or serving SCP) and a set of distributed translation servers which store the NGPN-to-HLR mapping. We discuss how the operations required to maintain the translation information can be performed. Finally, we perform a simplified analysis of the scalability of the alternative schemes as well as the hash-based schemes we propose.

The I/O bottleneck in parallel computer systems has recently begun receiving increasing interest. Most attention has focused on improving the performance of I/O devices using fairly low level parallelism in techniques such as disk striping and interleaving. Widely applicable solutions, however, will require an integrated approach which addresses the problem at multiple system levels, including applications, systems software, and architecture. We propose that within the context of such an integrated approach, scheduling parallel I/O operations will become increasingly attractive and can potentially provide substantial performance benefits. We describe a simple I/O scheduling problem and present approximate algorithms for its solution. The costs of using these algorithms in terms of execution time, and the benefits in terms of reduced time to complete a batch of I/O operations, are compared with the situations in which no scheduling is used, and in which an optimal scheduling algorithm is used. The comparison is performed both theoretically and experimentally. We have found that, in exchange for a small execution time overhead, the approximate scheduling algorithms can provide substantial improvements in I/O completion times.

Current cellular subscribers have a geographic phone number (e.g. in AMPS and US digital cellular systems) or a number which contains the network provider's identity (e.g. in GSM), and whenever subscribers register or receive (and possibly, originate) a call, a home location register (HLR) database has to be queried. A special feature of next generation wireless access service will be to support PCS and wireless subscribers with portable personal numbers, or non-geographic phone numbers (NGPN), that do not indicate the service provider or HLR database serving the user. In addition the global title translation (GTT) function that converts the subscriber's number to an HLR database address may not be available when the wired backbone is an ATM network. Thus a key function required will be to translate an NGPN to the ID of the HLR which serves the subscriber, a process we call NGPN translation. (Note that the same functionality is also needed for subscribers with local, portable phone numbers.) We discuss the requirements of NGPN translation and some alternative schemes. We propose a scheme for fast, efficient, scalable and flexible NGPN translation which applies ideas of dynamic hashing, caching, and indirection. The scheme uses a hash function in the visiting location registers (VLR) (or serving SCP) and a set of distributed translation servers which store the NGPN-to-HLR mapping.

We propose a parameterized, randomized edge coloring algorithm for use in coordinating data transfers in fully connected distributed architectures such as parallel 1/0 subsysateness of each heuristic for a variety of different architectural models and applications.

We propose an auxiliary strategy, called per-user caching, for locating users who move from place to place while using Personal Communications Services (PCS). The caching strategy augments the basic location strategy proposed in existing standards such as GSM and IS-41, with the objective of reducing network signaling and database loads in exchange for increased CPU processing and memory costs. Since technology trends are driving the latter costs down, the auxiliary strategy will become increasingly attractive. The idea behind caching is to reuse the information about a called user's location for subsequent calls to that user, and is useful for those users who receive calls frequently relative to the rate at which they change registration areas. This idea attempts to exploit the spatial and temporal locality in calls received by users, similar to the idea of exploiting locality of file access in computer systems. We use a reference PCS architecture and the notion of a user's local call-to-mobility ratio (LCMR) to quantify the costs and benefits of using caching and classes of users for whom it would be beneficial. We also present two simple algorithms for estimating users' LCMR and the situation in which each is preferable. We show that under a variety of assumptions caching is likely to yield significant net benefits in terms of reduced signaling network traffic and database loads.>

A communication switching system is considered where nodes communicate through transmitters and receivers that have the same bandwidth. Communication constraints are imposed so that the number of active transmitters or receivers on designated subsets of nodes is bounded by prespecified values. The constraints are assumed to have a hierarchical structure. An algorithm is given that produces minimal length schedules of data transfers through the system if transmission preemption is allowed. A variation of the switching system when nodes communicate through transceivers is also considered, and accompanying scheduling algorithms are presented. Applications to transmission scheduling in packet radio networks are discussed.>