PagedAttention is a popular approach for dynamic memory allocation in LLM serving systems. It enables on-demand allocation of GPU memory to mitigate KV cache fragmentation - a phenomenon that crippled the batch size (and consequently throughput) in prior systems. However, in trying to allocate physical memory at runtime, PagedAttention ends up changing the virtual memory layout of the KV cache from contiguous to non-contiguous. Such a design leads to non-trivial programming and performance overheads.

Large multimodal models (LMMs) demonstrate impressive capabilities in understanding images, videos, and audio beyond text. However, efficiently serving LMMs in production environments poses significant challenges due to their complex model architectures and heterogeneous characteristics across their multi-stage inference pipelines and modalities.

Deep Learning training jobs process large amounts of training data using many GPU devices, often running for weeks or months. When hardware or software failures happen, these jobs need to restart, losing the memory state for the Deep Neural Network (DNN) model trained so far, unless checkpointing mechanisms are used to save training state periodically. However, for large models, periodic checkpointing incurs significant steady state overhead, and during recovery, a large number of GPUs need to redo work since the last checkpoint. This is especially problematic when failures are frequent for large DNN (such as Large Language Model) training jobs using many GPUs. In this paper, we present a novel approach of just-in-time checkpointing when failures happen, which enables recovery from failures with just a single minibatch iteration of work replayed by all GPUs. This reduces the cost of error recovery from several minutes to a few seconds per GPU, with nearly zero steady state overhead. This also avoids the guesswork of choosing a checkpointing frequency since failure rates usually have high variance. We discuss how just-in-time checkpointing can be enabled in training code, as well as design of key mechanisms for transparent just-in-time checkpointing without user code change. We analyze the wasted GPU work of just-in-time checkpointing and show that it is less than periodic checkpointing for large numbers of GPUs. We present results from our implementation in modern AI cluster infrastructure.

Extreme Classification (XC) architectures, which utilize a massive One-vs-All (OvA) classifier layer at the output, have demonstrated remarkable performance on problems with large label sets. Nonetheless, these architectures falter on tail labels with few representative samples. This phenomenon has been attributed to factors such as classifier over-fitting and missing label bias, and solutions involving regularization and loss re-calibration have been developed. This paper explores the impact of label variance - a previously unexamined factor - on the tail performance in extreme classifiers. It also develops a method to systematically reduce label variance in XC by transferring the knowledge from a specialized tail-robust teacher model to the OvA classifiers. For this purpose, it proposes a principled knowledge distillation framework, LEVER, which enhances the tail performance in extreme classifiers with formal guarantees on generalization. Comprehensive experiments are conducted on a diverse set of XC datasets, demonstrating that LEVER can enhance tail performance by around 5\% and 6\% points in PSP and coverage metrics, respectively, when integrated with leading extreme classifiers. Moreover, it establishes a new state-of-the-art when added to the top-performing Renee classifier. Extensive ablations and analyses substantiate the efficacy of our design choices. Another significant contribution is the release of two new XC datasets that are different from and more challenging than the available benchmark datasets, thereby encouraging more rigorous algorithmic evaluation in the future. Code for LEVER is available at: aka.ms/lever.

When Large Language Models (LLMs) are compressed using techniques such as quantization, the predominant way to demonstrate the validity of such techniques is by measuring the model's accuracy on various benchmarks. If the accuracies of the baseline model and the compressed model are close, it is assumed that there was negligible degradation in quality. However, even when the accuracy of baseline and compressed model are similar, we observe the phenomenon of flips, wherein answers change from correct to incorrect and vice versa in proportion. We conduct a detailed study of metrics across multiple compression techniques, models and datasets, demonstrating that the behavior of compressed models as visible to end-users is often significantly different from the baseline model, even when accuracy is similar. We further evaluate compressed models qualitatively and quantitatively using MT-Bench and show that compressed models exhibiting high flips are worse than baseline models in this free-form generative task. Thus, we argue that accuracy and perplexity are necessary but not sufficient for evaluating compressed models, since these metrics hide large underlying changes that have not been observed by previous work. Hence, compression techniques should also be evaluated using distance metrics. We propose two such distance metrics, KL-Divergence and flips, and show that they are well correlated.

Extreme Classification (XC) seeks to tag data points with the most relevant subset of labels from an extremely large label set. Performing deep XC with dense, learnt representations for data points and labels has attracted much attention due to its superiority over earlier XC methods that used sparse, hand-crafted features. Negative mining techniques have emerged as a critical component of all deep XC methods, allowing them to scale to millions of labels. However, despite recent advances, training deep XC models with large encoder architectures such as transformers remains challenging. This paper notices that memory overheads of popular negative mining techniques often force mini-batch sizes to remain small and slow training down. In response, this paper introduces NGAME, a light-weight mini-batch creation technique that offers provably accurate in-batch negative samples. This allows training with larger mini-batches offering significantly faster convergence and higher accuracies than existing negative sampling techniques. NGAME was found to be up to 16% more accurate than state-of-the-art methods on a wide array of benchmark datasets for extreme classification, as well as 3% more accurate at retrieving search engine queries in response to a user webpage visit to show personalized ads. In live A/B tests on a popular search engine, NGAME yielded up to 23% gains in click-through-rates. Code for NGAME is available at https://github.com/Extreme-classification/ngame

Several papers argue that wide minima generalize better than narrow minima. In this paper, through detailed experiments that not only corroborate the generalization properties of wide minima, we also provide empirical evidence for a new hypothesis that the density of wide minima is likely lower than the density of narrow minima. Further, motivated by this hypothesis, we design a novel explore-exploit learning rate schedule. On a variety of image and natural language datasets, compared to their original hand-tuned learning rate baselines, we show that our explore-exploit schedule can result in either up to 0.84% higher absolute accuracy using the original training budget or up to 57% reduced training time while achieving the original reported accuracy.

Systems for training massive deep learning models (billions of parameters) today assume and require specialized "hyperclusters": hundreds or thousands of GPUs wired with specialized high-bandwidth interconnects such as NV-Link and Infiniband. Besides being expensive, such dependence on hyperclusters and custom high-speed inter-connects limits the size of such clusters, creating (a) scalability limits on job parallelism; (b) resource fragmentation across hyperclusters.

We present Gandivafair, a distributed, fair share scheduler that balances conflicting goals of efficiency and fairness in GPU clusters for deep learning training (DLT). Gandivafair provides performance isolation between users, enabling multiple users to share a single cluster, thus, maximizing cluster efficiency. Gandivafair is the first scheduler that allocates cluster-wide GPU time fairly among active users.

Emerging smart cities are typically equipped with thousands of outdoor cameras. However, these cameras are usually not calibrated, i.e., information such as their precise mounting height and orientation is not available. Calibrating these cameras allows measurement of real-world distances from the video, thereby enabling a wide range of novel applications such as identifying speeding vehicles and city road planning . Unfortunately, robust camera calibration is a manual process today and is not scalable. In this article, we propose AutoCalib, a system for scalable, automatic calibration of traffic cameras. AutoCalib exploits deep learning to extract selected key-point features from car images in the video and uses a novel filtering and aggregation algorithm to automatically produce a robust estimate of the camera calibration parameters from just hundreds of samples. We have implemented AutoCalib as a service on Azure that takes in a video segment and computes the camera calibration parameters. Using video from real-world traffic cameras, we show that AutoCalib is able to estimate real-world distances with an error of less than 12%.

Interference in WiFi deployments is a growing problem due to the increasing popularity of WiFi. Therefore it is important that APs find the right channel to operate upon. Through a large scale measurement study involving over 10,000 WiFi APs we show that channel measurements and selection are most effective when performed frequently (every few minutes). This is because of the highly dynamic nature of WiFi traffic congestion. Our key contribution in this paper is a novel approach to distributed channel selection -- Ineffective time Quantum (IQ) Hopping, that is simple enough to be described in three lines and has provable optimality guarantees. IQ-Hopping does not require any explicit channel measurements and can react within a matter of several seconds to bad channel conditions, including microwave ovens, hidden interferers, or dynamically varying congestion. Through implementation and experiments on off-the-shelf WiFi routers (OpenWRT, MadWiFi), we demonstrate the effectiveness of IQ-Hopping.

To minimize battery drain due to background communication in cellular-connected devices such as smartphones, the duration for which the cellular radio is kept active should be minimized. This, in turn, calls for scheduling the background communication so as to maximize the throughput. It has been recognized in prior work that a key determinant of throughput is the wireless link quality. However, as we show here, another key factor is the load in the cell, arising from the communication of other nodes. Unlike link quality, the only way, thus far, for a cellular client to obtain a measure of load has been to perform active probing, which defeats the goal of minimizing the active duration of the radio.

Many networked applications that run in the background on a mobile device incur significant energy drains when using the cellular radio interface for communication. This is mainly due to the radio-tail, where the cellular radio remaining in a high energy state for up to 20s after each communication spurt. In order to cut down energy consumption, many recent devices employ fast dormancy, a feature that forces the client radio to quickly go into a low energy state after a fixed short idle period. However, aggressive idle timer values for fast dormancy can increase signaling overhead due to frequent state transitions, which negatively impacts the network. In this work, we have designed and implemented RadioJockey, a system that uses program execution traces to predict the end of communication spurts, thereby accurately invoking fast dormancy without increasing network signaling load. We evaluate RadioJockey on a broad range of background applications and show that it achieves 20-40\% energy savings with negligible increase in signaling overhead compared to fixed idle timer-based approaches.

The increase in WiFi physical layer transmission speeds from 1~Mbps to 1 Gbps has reduced transmission times for a 1500 byte packet from 12 ms to 12 us. However, WiFi MAC overheads such as channel access and acks have not seen similar reductions and cumulatively contribute about 150 us on average per packet. Thus, the efficiency of WiFi has deteriorated from over 80% at 1 Mbps to under 10% at 1 Gbps.

Cellular radios consume more power and suffer reduced data rate when the signal is weak. According to our measurements, the communication energy per bit can be as much as 6x higher when the signal is weak than when it is strong. To realize energy savings, applications must preferentially communicate when the signal is strong, either by deferring non-urgent communication or by advancing anticipated communication to coincide with periods of strong signal. Allowing applications to perform such scheduling requires predicting signal strength, so that opportunities for energy-efficient communication can be anticipated. Furthermore, such prediction must be performed at little energy cost.

To realize the potential of opportunistic and participatory sensing using mobile smartphones, a key challenge is ensuring the ease of developing and deploying such applications, without the need for the application writer to reinvent the wheel each time. To this end, we present a Platform for Remote Sensing using Smartphones (PRISM) that balances the interconnected goals of generality, security, and scalability. PRISM allows application writers to package their applications as executable binaries, which offers efficiency and also the flexibility of reusing existing code modules. PRISM then pushes the application out automatically to an appropriate set of phones based on a specified set of predicates. This push model enables timely and scalable application deployment while still ensuring a good degree of privacy. To safely execute untrusted applications on the smartphones, while allowing them controlled access to sensitive sensor data, we augment standard software sandboxing with several PRISM-specific elements like resource metering and forced amnesia.

WiFi radios in smart-phones consume a significant amount of power when active. The 802.11 standard allows these devices to save power through an energy-conserving Power Save Mode (PSM). However, depending on the PSM implementation strategies used by the clients/Access Points (APs), we find competing background traffic results in one or more of the following negative consequences: a significant increase, up to 300%, in a client's energy consumption, a decrease in wireless network capacity due to unnecessary retransmissions, and unfairness.

Cellular radio communication is a significant contributor to battery energy drain on smartphones, in some cases inflating the energy cost by a factor of 5 or more compared to the energy cost of the base device. Stratus is a system to reduce this energy consumption by leveraging cloud resources to make data communication on smartphones more efficient. Using a cloud-based proxy, Stratus employs optimizations that adapt an application's incoming and outgoing traffic to better match the energy characteristics of the radio interface. The optimizations include (a) aggregation to bunch up sporadic transmissions, (b) asymmetric dictionary-based compression to reduce the number of bits transmitted over the air, and (c) opportunistic scheduling to avoid communication during periods of poor signal reception. These optimizations can be used individually, or in combination, subject to an application's delay tolerance. For example, using our Stratus prototype, the aggregation and compression optimizations together achieve up to 50% energy savings for web browsing, while the aggregation and scheduling optimizations together achieve up to 35% energy savings for a media streaming application.

We consider the problem of providing ubiquitous yet affordable Internet connectivity to devices at home, at work, and on the move. In this context, we take advantage of two significant technology trends: the commoditization of WiFi WLAN technology and the rapid growth of cellular data services. We propose an architecture called Cool-Tether that harnesses the cellular radio links of one or more mobile smartphones in the vicinity, builds a WiFi hotspot on-the-fly, and provides energy-efficient, affordable connectivity.

IP multicast applications such as live lecture broadcasts are being increasingly used in enterprise and campus networks. In many cases, end hosts access these multicast streams using Wi-Fi networks. However, multicast over Wi-Fi suffers from several well-known problems such as low data rate, high losses and unfairness vis-a-vis other contending unicast transmissions. In this paper we present DirCast, a system to solve many of these problems. DirCast requires no changes to the 802.11 MAC protocol or the wireless access points. Software changes are required on clients only if they wish to participate in multicast sessions. The aim of DirCast system is to minimize the airtime consumed by the multicast traffic, while simultaneously improving client experience. To meet these goals, the DirCast converts multicast packets to unicast packets targeted to certain selected clients; other clients receive these packets by listening in promiscuous mode. The target clients are carefully selected to minimize loss rate experienced by the non-targeted clients. If necessary, clients are forced to change the AP they are associated with. In addition, DirCast uses proactive adaptive FEC to further reduce the loss rate and implements a novel virtual multicast interface in order to be compatible with the security needs of the enterprise. We demonstrate the effectiveness of DirCast using extensive experiments in a Wi-Fi prototype implementation and through large-scale simulations.

We present muNet, a wireless mesh network design and implementation to harness the multiuser capacity of wireless channels. Traditionally, media access control is designed to schedule one transmission between one sender and one receiver without interference at any given time. However, this design is suboptimal in terms of achieving the multiuser capacity of multi-access wireless channels. In muNet, we implement effective physical layer techniques called superposition coding and successive interference cancellation to enable simultaneous unicast transmissions from a single transmitter to multiple receivers as well as from multiple transmitters to a single receiver. We design the first practical MAC protocol that leverages such a physical layer and exposes the multiuser capacity to upper layers. We also present a simple, effective routing protocol that increases simultaneous transmission opportunities for the MAC layer. A proof-of-concept muNet is implemented on the GNU radio platform. Measurements on the implementation shows that the throughput gains of muNet are significant (up to 93%).

A major barrier for the adoption of wireless mesh networks is severe limits on throughput. Many in-network packet mixing techniques at the network layer [1], [2], [3] as well as the physical layer [4], [5], [6] have been shown to substantially improve throughput. However, the optimal mixing algorithm that maximizes throughput is still unknown. We propose iPack, an algorithm for in-network generation of composite packets that integrates coding at two different layers of the protocol stack: XOR-based network coding and physical layer superposition coding. Using extensive simulations, we find that the throughput gain of the joint coding iPack algorithm is 30% more than the better performer of network coding and superposition coding in a wide range of scenarios, and automatically takes advantage of the best available coding opportunities. In a typical wireless mesh network when more traffic is between the clients and access points, the average throughput improvement of iPack, our joint optimization scheduler, can be 324%, while there can be little gain (less than 10%) if network coding alone is used. We also validate our results by implementing iPack on a small-scale testbed based on GNU Radio.

We consider the problem of monitoring road and traffic conditions in a city. Prior work in this area has required the deployment of dedicated sensors on vehicles and/or on the roadside, or the tracking of mobile phones by service providers. Furthermore, prior work has largely focused on the developed world, with its relatively simple traffic flow patterns. In fact, traffic flow in cities of the developing regions, which comprise much of the world, tends to be much more complex owing to varied road conditions (e.g., potholed roads), chaotic traffic (e.g., a lot of braking and honking), and a heterogeneous mix of vehicles (2-wheelers, 3-wheelers, cars, buses, etc.).

We consider the problem of monitoring road and traffic conditions in a city. Prior work in this area has required the deployment of dedicated sensors on vehicles and/or on the roadside, or the tracking of mobile phones by service providers. Furthermore, prior work has largely focused on the developed world, with its relatively simple traffic flow patterns. In fact, traffic flow in cities of the developing regions, which comprise much of the world, tends to be much more complex owing to varied road conditions (e.g., potholed roads), chaotic traffic (e.g., a lot of braking and honking), and a heterogeneous mix of vehicles (2-wheelers, 3-wheelers, cars, buses, etc.).To monitor road and traffic conditions in such a setting, we present Nericell, a system that performs rich sensing by piggybacking on smartphones that users carry around with them. In this demo, we show the use of accelerometer to detect bumps and braking. We also use the microphone to enable honk detection. Nericell addresses several challenges including virtually reorienting the accelerometer on a phone that is at an arbitrary orientation, and performing honk detection and localization in an energy efficient manner.

As third-generation (3G) wireless networks with high data rate get widely deployed, optimizing the transmission control protocol (TCP) performance over these networks would have a broad and significant impact on data application performance. In this paper, we make two main contributions. First, one of the biggest challenges in optimizing the TCP performance over the 3G wireless networks is adapting to the significant delay and rate variations over the wireless channel. We present window regulator algorithms that use the receiver window field in the acknowledgment (ACK) packets to convey the instantaneous wireless channel conditions to the TCP source and an ACK buffer to absorb the channel variations, thereby maximizing long-lived TCP performance. It improves the performance of TCP selective ACK (SACK) by up to 100 percent over a simple drop-tail policy, with small buffer sizes at the congested router. Second, we present a wireless channel and TCP-aware scheduling and buffer sharing algorithm that reduces the latency of short flows while still exploiting user diversity for a wide range of user and traffic mix.

Broadcast operation, which disseminates information network-wide, is very important in multi-hop wireless networks. Due to the broadcast nature of wireless media, not all nodes need to transmit in order for the message to reach every node. Previous work on broadcast support can be classified as probabilistic (each node rebroadcasts a packet with a given probability) or deterministic approaches (nodes pre-select a few neighbors for rebroadcasting). In this paper, we show how network-coding can be applied to a deterministic broadcast approaches, resulting in significant reductions in the number of transmissions in the network. We propose two algorithms, that rely only on local two-hop topology information and makes extensive use of opportunistic listening to reduce the number of transmissions: 1) a simple XOR-based coding algorithm that provides up to 45% gains compared to a non-coding approach and 2) a Reed-Solomon based coding algorithm that determines the optimal coding gain achievable for a coding algorithm that relies only on local information, with gains up to 61% in our simulations. We also show that our coding-based deterministic approach outperforms the coding-based probabilistic approach presented in (C. Fragouli et al, 2006).

A major barrier for the adoption of wireless mesh networks is severe limits on throughput. In this paper, we apply superposition coding to substantially improve network capacity of large, dense wireless mesh networks. Superposition coding is a physical layer technique that allows a transmitter to simultaneously send independent packets to multiple receivers. While superposition coding has been studied extensively by the physical layer community, we present the first design of practical and effective MAC protocols to take advantage of superposition coding in wireless mesh networks. Extensive evaluations show that superposition coding can be a practical method to increase the throughput of large, dense wireless mesh networks. Specifically, in a mesh network with 2 to 64 active receivers and one gateway, we show that our system can increase throughput up to 154%, with average gain ranging from 10% to 21%. When there are multiple gateways forming a mesh network, our system gains up to 98%, with average gain ranging from 24% to 46%. These results clearly demonstrate the potential benefits of our system. We also present results from an implementation of superposition coding using GNU Radio.

In third-generation (3G) wireless data networks, providing service to low data-rate users is required for maintaining fairness, but at the cost of reducing the cell's aggregate throughput. In this paper, we propose the unified cellular and ad hoc network (UCAN) architecture for enhancing cell throughput while maintaining fairness. In UCAN, a mobile client has both 3G interface and IEEE 802.11 -based peer-to-peer links. The 3G base station forwards packets for destination clients with poor channel quality to proxy clients with better channel quality. The proxy clients then use an ad hoc network composed of other mobile clients and IEEE 802.11 wireless links to forward the packets to the appropriate destinations, thereby improving cell throughput. We refine the 3G base station scheduling algorithm so that the throughput gains are distributed in proportion to users' average channel rates, thereby maintaining fairness. With the UCAN architecture in place, we propose novel greedy and on-demand protocols for proxy discovery and ad hoc routing that explicitly leverage the existence of the 3G infrastructure to reduce complexity and improve reliability. We further propose secure crediting mechanisms to motivate users that are not actively receiving to participate in relaying packets for others. Through both analysis and extensive simulations with HDR and IEEE 802.11b, we show that the UCAN architecture can increase individual user's throughput by more than 100 percent and the aggregate throughput of the HDR downlink by up to 50 percent.

In 3G data networks, network operators would like to balance system throughput while serving users in a fair manner. This is achieved using the notion of proportional fairness. However, so far, proportional fairness has been applied at each base station independently. Such an approach can result in non-Pareto optimal bandwidth allocation when considering the network as a whole. Therefore, it is important to consider proportional fairness in a network-wide context with user associations to base stations governed by optimizing a generalized proportional fairness objective. In this paper, we take the first step in formulating and studying this problem rigorously. We show that the general problem is NP-hard and it is also hard to obtain a close-to-optimal solution. We then consider a special case where multi-user diversity only depends on the number of users scheduled together. We propose efficient offline optimal algorithms and heuristic-based greedy online algorithms to solve this problem. Using detailed simulations based on the base station layout of a large service provider in the U.S., we show that our simple online algorithm, which assigns a newly arrived user to a base station that improves the generalized proportional fairness objective the most without changing existing users ’ association, is very close to the offline optimal solution. The greedy algorithm can achieve significantly better throughput and fairness in heterogeneous user distributions, when compared to the approach that assigns a user to the base station with the best signal strength.

In third generation (3G) wireless data networks, multicast throughput decreases with the increase in multicast group size, since a conservative strategy for the base station is to use the lowest data rate of all the receivers so that the receiver with the worst downlink channel condition can decode the transmission correctly. This paper proposes ICAM, integrated cellular and ad hoc multicast, to increase 3G multicast throughput through opportunistic use of ad hoc relays. In ICAM, a 3G base station delivers packets to proxy mobile devices with better 3G channel quality. The proxy then forwards the packets to the receivers through an IEEE 802.11-based ad hoc network. In this paper, we first propose a localized greedy algorithm that discovers for each multicast receiver the proxy with the highest 3G downlink channel rate. We discover that due to capacity limitations and interference of the ad hoc relay network, maximizing the 3G downlink data rate of each multicast receiver's proxy does not lead to maximum throughput for the multicast group. We then show that the optimal ICAM problem is NP-hard, and derive a polynomial-time 4-approximation algorithm for the construction of the multicast forest. This bound holds when the underlying wireless MAC supports broadcast or unicast, single rate or multiple rates (4(1 + /spl isin/) approximation scheme for the latter), and even when there are multiple simultaneous multicast sessions. Through both analysis and simulations, we show that our algorithms achieve throughput gains up to 840 percent for 3G downlink multicast with modest overhead on the 3G uplink.

IP-based radio access networks (RAN) are expected to be the next generation access networks in UMTS and CDMA networks. The question of connectivity, i.e., how best to connect base stations to the radio network controllers (RNC) in an IP-based RAN, has not been addressed by researchers. Furthermore, given a connection configuration, an RNC selection algorithm that assigns an incoming call to an RNC is also necessary. This paper examines RAN connectivity and its impact on the performance and resiliency of the wireless network using different RNC selection algorithms. For homogeneous networks, we show that the proposed min-load-1 algorithm, which allows at most one hard handoff in order to accommodate each incoming call request, delivers performance close to the optimal algorithm. We also show that allowing a few base stations to connect to two RNCs (a 10 percent increase in the number of links in our network) results in resiliency to RNC failures that is comparable to the resiliency of RANs with full-mesh connectivity. Finally, for heterogeneous networks, we show that the min-load-k algorithm (with at most k hard handoffs per call) is effective in handling load imbalances. These results provide strong motivation for deploying IP-based RAN, as they suggest that enhancing current point-to-point RAN with few additional links and allowing a few hard handoffs to accommodate incoming calls can result in significant gains in performance and resiliency.

We identify two typical problems in WLAN hotspots that result in unbounded unfairness between upstream and downstream flows. The first unfairness problem arises due to the uniformity of the MAC layer protocol at the access point (AP) and user nodes that result in equal share to the AP and the user nodes but not to the individual flows. The second unfairness problem arises due to the inability of the physical layer to distinguish frame errors due to hidden terminal based collisions and frame errors due to poor signal strength. We present FairMAC, a deployable solution that addresses these unfairness problems without requiring a change to the 802.11 protocol. Thus, our solution is immediately deployable in the millions of currently operational hotspots. We evaluate the performance of our protocol using simulations and a prototype implementation. We show that FairMAC provides fair access to all the flows regardless whether they are originating at the AP or a host.

In third generation (3G) cellular networks, base stations are connected to base station controllers by point-to-point (usually T1/E1) links. However, today's T1/E1 based buck haul network is not a good match for next generation wireless networks because symmetric T1s is not an efficient way to carry bursty and asymmetric data traffic. In this paper, we propose designing an IEEE 802.16-based wireless radio access network to carry the traffic from the base station to the radio network controller. 802.16 has several characteristics that make it a better match for 3G radio access networks including its support for time division duplex mode that supports asymmetry efficiently. In this paper, we tackle the following question; given a layout of base stations and base station controllers, how do we design the topology of the 802.16 radio access network connecting the base stations to the base station controller that minimizes the number of 802.16 links used while meeting the expected demands of traffic from/to the base stations? We make three contributions: we first show that finding the optimal solution to the problem is NP-hard. We then provide heuristics that perform close to the optimal solution. Finally, we address the reliability issue of failure of 802.16 links or nodes by designing algorithms to create topologies that can handle single failures effectively.

The total number of hotspot users around the world is expected to grow from 9.3 million at the end of 2003 to 30 million at the end of 2004 according to researcher Gartner. Given the explosive growth in hotspot wireless usage, enhancing capacity of 802.11-based hot-spot wireless networks is an important problem. In this paper, we make two important contributions. We first present the AP-CST algorithm that dynamically adjusts the carrier sense threshold (CST) in order to allow more flows to coexist in current 802.11 architectures. We then extend the current hotspot engineering paradigm by allowing every cell and AP access to all available channels. These cells are then managed by the RNC-SC algorithm running in a centralized radio network controller. This algorithm assigns mobile stations to appropriate cells/channels and adjusts transmit power values dynamically, thereby exploiting spatial heterogeneity in distribution of users at the hotspots. Through detailed and extensive simulations, we show that the performance of 802.11-based hotspots can be improved by up to 195% per-cell and 70% overall.

Guard channels have been proposed to minimize handoff call dropping when mobile hosts move from one cell to another. Code-division multiple-access (CDMA) systems are power- and interference-limited. Therefore, guard capacity in CDMA networks is soft, that is, a given capacity corresponds to variable number of connections. Thus, it is essential to adjust the guard capacity in response to changes in traffic conditions and user mobility. We propose two schemes for managing downlink CDMA radio resources: guard capacity adaptation based on dropping (GAD), and guard capacity adaptation based on prediction and dropping (GAPD). In both schemes, the guard capacity of a cell is dynamically adjusted so as to maintain the handoff dropping rate at a target level. In the second scheme, there is an additional, frequent adjustment component where guard capacity is adjusted based on soft handoff prediction. We show through extensive simulations that GAD and GAPD control the handoff dropping rate effectively under varying traffic conditions and system parameters. We also find that GAPD is more robust than GAD to temporal traffic variations and changes in control parameters.

As CDMA-based cellular networks mature, the current point-to-point links used in connecting base stations to network controllers evolve to an IP-based radio access network (RAN) for reasons of lower cost due to statistical multiplexing gains, better scalability and reliability, and the projected growth in data applications. In this paper, we study the impact of congestion in a best-effort IP RAN on CDMA cellular voice networks. We propose and evaluate three congestion control mechanisms, admission control, diversity control, and router control, to maximize network capacity while maintaining good voice quality. We first propose two new enhancements to CDMA call admission control that consider a unified view of both IP RAN and air interface resources. Next, we introduce a novel technique called diversity control that exploits the soft-handoff feature of CDMA networks and drops selected frames belonging to multiple soft-handoff legs to gracefully degrade-voice quality during congestion. Finally, we study the impact of router control where an active queue management technique is used to reduce delay and minimize correlated losses. Using simulations of a large mobile network, we show that the three different control mechanisms can help gracefully manage 10-40 percent congestion overload in the IP RAN.

IP-based radio access networks (RAN) are expected to be the next generation access networks in UMTS and CDMA networks. There are several benefits of IP-based RAN including lower costs, flexibility of merging wired and wireless networks, and network scalability and reliability. While quality of service issues in IP-based RAN have been addressed by a number of researchers, the question of connectivity, i.e., how best to connect base stations to the radio network controllers (RNC) in an IP-based RAN, has not been addressed by any research literature. Furthermore, given a connection configuration, an RNC selection algorithm that assigns an incoming call to an RNC is also necessary. This paper examines radio access network (RAN) connectivity and its impact on the performance and resiliency of the wireless network using different RNC selection algorithms. The proposed min-load-1 algorithm, which allows at most one hard hand off in order to accommodate each incoming request, delivers performance close to the standard Min-Load algorithm using a RAN of much higher connectivity and is close to the optimal algorithm using the same RAN. We also find that using min-load-1 algorithm and allowing the base stations to connect to two RNCs result in resiliency to RNC failures that is similar to having full-mesh connectivity between base stations and RNCs

As third generation (3G) wireless networks with high data rate get widely deployed, optimizing TCP performance over these networks would have a broad and significant impact on data application performance. One of the biggest challenges in optimizing TCP performance over the 3G wireless networks is adapting to the significant delay and rate variations over the wireless channel. In this paper, we make two main contributions. First, we present a window regulator algorithm that uses the receiver window field in the acknowledgment packets to convey the instantaneous wireless channel conditions to the TCP source and an ack buffer to absorb the channel variations, thereby maximizing long-lived TCP performance. It improves the performance of TCP sack by up to 100% over a simple drop-tail algorithm for small buffer sizes at the congested router. Second, we present a wireless channel and TCP-aware scheduling and buffer sharing algorithm that reduces the latency of short TCP flows by up to 90% while still exploiting user diversity, thus allowing the wireless channel to be utilized efficiently.

Guard channels have been proposed to minimize handoff call dropping when mobile hosts move from one cell to another. CDMA systems are power- and interference-limited. Therefore, guard capacity in CDMA networks is soft, that is, a given capacity corresponds to variable number of connections. Thus, it is essential to adjust the guard capacity in response to changes in traffic conditions and user mobility. We propose two schemes for managing downlink CDMA radio resources: guard capacity adaptation based on dropping (GAD), and guard capacity adaptation based on prediction and dropping (GAPD). In both schemes, the guard capacity of a cell is dynamically adjusted so as to maintain the handoff dropping rate at a target level. In the second scheme, there is an additional, frequent adjustment component where guard capacity is adjusted based on soft handoff prediction. We show through extensive simulations that GAD and GAPD control the handoff dropping rate effectively under varying traffic conditions and system parameters. We also find that GAPD is more robust than GAD to temporal traffic variations and changes in control parameters.

As CDMA-based cellular networks mature, the current point-to-point links used in connecting base stations to network controllers will evolve to an IP-based radio access network (RAN) for reasons of lower cost due to statistical multiplexing gains, better scalability and reliability, and the projected growth in data applications. In this paper, we study the impact of congestion in a best-effort IP RAN on CDMA cellular voice networks. We propose and evaluate three congestion control mechanisms, admission control, diversity control, and router control, to maximize network capacity while maintaining good voice quality. We first propose two new enhancements to CDMA call admission control that consider a unified view of both IP RAN and air interface resources. Next, we introduce a novel technique called diversity control that exploits the soft-handoff feature of CDMA networks and drops selected frames belonging to multiple soft-handoff legs to gracefully degrade voice quality during congestion. Finally, we study the impact of router control where an active queue management technique is used to reduce delay and minimize correlated losses. Using simulations of a large mobile network, we show that the three different control mechanisms can help gracefully manage 10-40% congestion overload in the IP RAN.

As local area wireless networks based on the IEEE 802.11 standard see increasing public deployment, it is important to ensure that access to the network by different users remains fair. While fairness issues in 802.11 networks have been studied before, this paper is the first to focus on TCP fairness in 802.11 networks in the presence of both mobile senders and receivers. In this paper, we evaluate extensively through analysis, simulation, and experimentation the interaction between the 802.11 MAC protocol and TCP. We identify four different regions of TCP unfairness that depend on the buffer availability at the base station, with some regions exhibiting significant unfairness of over 10 in terms of throughput ratio between upstream and downstream TCP flows. We also propose a simple solution that can be implemented at the base station above the MAC layer that ensures that different TCP flows share the 802.11 bandwidth equitably irrespective of the buffer availability at the base station.

In third-generation (3G) wireless data networks, mobile users experiencing poor channel quality usually have low data-rate connections with the base-station. Providing service to low data-rate users is required for maintaining fairness, but at the cost of reducing the cell's aggregate throughput. In this paper, we propose the Unified Cellular and Ad-Hoc Network (UCAN) architecture for enhancing cell throughput, while maintaining fairness. In UCAN, a mobile client has both 3G cellular link and IEEE 802.11-based peer-to-peer links. The 3G base station forwards packets for destination clients with poor channel quality to proxy clients with better channel quality. The proxy clients then use an ad-hoc network composed of other mobile clients and IEEE 802.11 wireless links to forward the packets to the appropriate destinations, thereby improving cell throughput. We refine the 3G base station scheduling algorithm so that the throughput gains of active clients are distributed proportional to their average channel rate, thereby maintaining fairness. With the UCAN architecture in place, we propose novel greedy and on-demand protocols for proxy discovery and ad-hoc routing that explicitly leverage the existence of the 3G infrastructure to reduce complexity and improve reliability. We further propose a secure crediting mechanism to motivate users to participate in relaying packets for others. Through extensive simulations with HDR and IEEE 802.11b, we show that the UCAN architecture can improve individual user's throughput by up to 310% and the aggregate throughput of the HDR downlink by up to 60%.

Wireless link losses result in poor TCP throughput since losses are perceived as congestion by TCP, resulting in source throttling. In order to mitigate this effect, 3G wireless link designers have augmented their system with extensive local retransmission mechanisms. In addition, in order to increase throughput, intelligent channel state based scheduling have also been introduced. While these mechanisms have reduced the impact of losses on TCP throughput and improved the channel utilization, these gains have come at the expense of increased delay and rate variability. In this paper, we comprehensively evaluate the impact of variable rate and variable delay on long-lived TCP performance. We propose a model to explain and predict TCP's throughput over a link with variable rate and/or delay. We also propose a network-based solution called Ack Regulator that mitigates the effect of variable rate and/or delay without significantly increasing the round trip time, while improving TCP performance by up to 40%.

Mobile IP is the current standard for supporting macromobility of mobile hosts. However, in the case of micromobility support, there are several competing proposals. We present the design, implementation and performance evaluation of HAWAII (handoff-aware wireless access Internet infrastructure), a domain-based approach for supporting mobility. HAWAII uses specialized path setup schemes which install host-based forwarding entries in specific routers to support intra-domain micromobility. These path setup schemes deliver excellent performance by reducing mobility related disruption to user applications. Also, mobile hosts retain their network address while moving within the domain, simplifying quality-of-service (QoS) support. Furthermore, reliability is achieved through maintaining soft-state forwarding entries for the mobile hosts and leveraging fault detection mechanisms built in existing intra-domain routing protocols. HAWAII defaults to using Mobile IP for macromobility, thus providing a comprehensive solution for mobility support in wide-area wireless networks.

In wireless networks, mobile hosts must update the network with their current location in order to get packets delivered. Paging facilitates efficient power management at the mobile host by allowing the host to update the networkless frequently at the cost of providing the network with only approximate location information. The network determines the exact location of a mobile host through paging before delivering packets destined to the mobile host. In this paper, we propose the concept of paging as an IP service. IP paging enables a common infrastructure and protocol to support the different wireless interfaces such as CDMA, GPRS, wireless LAN, avoiding the duplication of several application layer paging implementations and the inter-operability issues that exists today. We present the design, implementation, and detailed qualitative and quantitative evaluation, using measurements and simulation, of three IP-based paging protocols for mobile hosts.

Next generation wireless networks will rely heavily on packet transport for both data and voice services. We describe the Router for Integrated Mobile Access (RIMA) system, which is the core network element of an integrated wireless packet network. RIMA acts as a mobile switching center for standard cellular telephony users, and a mobile router for wireless packet data users. RIMA includes a novel call processing system that supports several types of telephony services, and a new IP mobility protocol, called HAWAII, that efficiently manages the IP mobility of data and packet voice users. We discuss issues with providing wireless packet service, present a network architecture based on RIMA to address those issues, and describe a research prototype of the system.

Wireless networks often employ network-based user agents as proxies for mobile users. In this paper, we consider the fundamental problem of designing migration policies for these user agents. We first introduce a general framework for analyzing user agent migration policies, and then highlight, through analysis and simulation, the numerous parameters and tradeoffs that dictate the design of migration policies. We evaluate these policies in the context of both homogeneous and heterogeneous networks, and in the presence and absence of processing overheads due to migration. Finally, we identify two simple threshold-based policies that deliver very good performance over a wide range of system parameters and configurations. To our knowledge, this is the first paper to propose and evaluate policies for migration of user agents.

Mobile-IP is the current standard for supporting macro-mobility of mobile hosts. However, in the case of micro-mobility support, there are several competing proposals. In this paper we present the design, implementation, and performance evaluation of HAWAII: a domain-based approach for supporting mobility. HAWAII uses specialized path setup schemes which install host-based forwarding entries in specific routers to support intra-domain micro-mobility. These path setup schemes deliver excellent performance by reducing mobility related disruption to user applications. Also, mobile hosts retain their network address while moving within the domain, simplifying QoS support. Furthermore, reliability is achieved through maintaining soft-state forwarding entries for the mobile hosts and leveraging fault detection mechanisms built in existing intra-domain routing protocols. HAWAII defaults to using Mobile IP for macro-mobility, thus providing a comprehensive solution for mobility support in wide-area wireless networks.

Multimedia wireless networks often employ network based user agents as proxies for mobile users. We consider a fundamental question in the design of these networks: should the user agents migrate and if so, what are good user agent migration policies? We first introduce a general framework for analysing user agent migration policies. We then highlight, through analysis and simulation, the numerous parameters and tradeoffs that dictate the design of migration policies. Finally, we identify two simple threshold-based policies that deliver very good performance over a wide range of system parameters and configurations.

In this paper, we present the design and implementation of a software system that performs the control functions of current mobile switching centers (MSCs) and visitor location registers (VLRs), and provides support for third generation services. The novelty of the system design is in its software architecture. To allow flexible deployment of the system as the migration from second generation to third generation systems occurs, the software is modular. To provide scalability in terms of capacity, distributed processing is used. We show that a deployment of this system using three Sun Ultra workstations achieves a call throughput of 300,000 calls/hour with a latency of below 300 milliseconds. This meets the latency requirements of third generation systems.

Supporting mobility in asynchronous transfer mode (ATM)-based broad-band networks with wireless access links poses many technical challenges. One of the most important of these challenges is the need to reroute ongoing connections to/from mobile users as these users move among base stations. Connection rerouting schemes must exhibit low handoff latency, maintain efficient routes, and limit disruption to continuous media traffic while minimizing reroute updates to the network switches. In this paper we propose, describe an implementation for, and experimentally evaluate the performance of five different connection rerouting schemes. We show that one of these schemes, which operates in two phases, executes very fast reroutes (with a measured latency of 6.5 ms) in a real-time phase and, if necessary, reroutes again in a nonreal-time phase to maintain efficient routing. The scheme also results in negligible disruption to both audio (e.g., a 1-in-100 chance of a single packet loss at CD-quality audio rates of 128 kb/s) and low-bit-rate video (e.g., a 2-in-100 chance of a single packet loss for 1-Mb/s video) traffic during connection rerouting. Based on these results, we conclude that simple handoff schemes coupled with a connection management architecture are sufficient for supporting low-bit-rate continuous media applications over ATM-based wireless networks.

Two important quality-of-service (QoS) measures for current cellular networks are the fractions of new and handoff "calls" that are blocked due to unavailability of "channels" (radio and/or computing resources). Based on these QoS measures, we derive optimal admission control policies for three problems: minimizing a linear objective function of the new and handoff call blocking probabilities (MINOBJ), minimizing the new call blocking probability with a hard constraint on the handoff call blocking probability (MINBLOCK) and minimizing the number of channels with hard constraints on both of the blocking probabilities (MINC). We show that the well-known guard channel policy is optimal for the MLNOBJ problem, while a new fractional guard channel policy is optimal for the MINBLOCK and MINC problems. The guard channel policy reserves a set of channels for handoff calls while the fractional guard channel policy effectively reserves a non-integral number of guard channels for handoff calls by rejecting new calls with a probability that depends on the current channel occupancy. It is also shown that the fractional policy results in significant savings (20-50%) in the new call blocking probability for the MINBLOCK problem and provides some, though small, gains over the integral guard channel policy for the MINC problem. Further, we also develop computationally inexpensive algorithms for the determination of the parameters for the optimal policies.

Recent interest in supporting packet-audio applications over wide area networks has been fueled by the availability of low-cost, toll-quality workstation audio and the demonstration that limited amounts of interactive audio can be supported by today's Internet. In such applications, received audio packets are buffered, and their playout delayed at the destination host in order to compensate for the variable network delays. The authors investigate the performance of four different algorithms for adaptively adjusting the playout delay of audio packets in an interactive packet-audio terminal application, in the face of such varying network delays. They evaluate the playout algorithms using experimentally-obtained delay measurements of audio traffic between several different Internet sites. Their results indicate that an adaptive algorithm which explicitly adjusts to the sharp, spike-like increases in packet delay which were observed in the traces can achieve a lower rate of lost packets for both a given average playout delay and a given maximum buffer size.>