Mobile web usage has significantly increased in last few years. There has been a lot of emphasis on providing good web page performance for mobile devices. Client-side caching can play a significant role in providing good web page performance, but unfortunately, traditional browser caches lack in various aspects leading to sub-optimal performance. More specifically, web applications do not have control on caching, e.g., which resources to cache, how to cache, etc., leading to ineffective cache utilization. Recently, HTML5 has introduced number of persistent storage APIs, that can provide required control for web applications. We evaluate these HTML5 storage options on various devices, and find that they can also meet the performance criteria of caching; in fact, some of the HTML5 storage APIs, e.g., localStorage, can provide even better performance than browser cache. Based on these insights, we make a case for application-managed hierarchical client-side cache, called HCache, that leverages these storage options as backends. We propose a novel API that allows web application developers to intelligently control the caching behavior and the usage of these storage options transparently. Our experiments with a prototype show that HCache can improve web page performance by up to 60%.

Contemporary search engines use a variety of techniques to personalize search results based on users' past queries. While studies have found that users generally prefer personalized search results to non-personalized ones, recent surveys also indicate growing reservations with respect to personalization because of its privacy implications. In this paper, we take a deeper look at privacy considerations of users during web search and explore how users' preferences for privacy and personalization interact when undertaking this activity. We conduct an empirical study over Google search, involving 25 participants in India and their respective web search histories. Our finding is that users exhibit a slight preference for personalization in their search results but are usually willing to "give up" personalization when searching for topics they deem sensitive. We discuss implications of these results for the design of privacy-preserving tools for web search.

In this paper, we present the lessons learned by bringing in content and content-creators from local community media initiatives into the technological fold of the web. Our work focuses on the Community Radio (CR) ecosystem in India, and through extensive field-studies we develop an in-depth understanding of the operations, strengths and challenges of a CR station. Based on this, we outline the design of a system that combines the content creation processes of a CR station with the mobile web. The system was evaluated with the users of a CR station in Bangalore over a month long deployment. Our key take-away is that the incorporation of a mobile web based delivery system can play a critical role in expanding the reach and consumption of community media in the target communities. Conversely, the relevance of CR content and role of radio jockeys (as trusted members of the community) can be a key driver in adoption of the mobile web in these communities. Together, such a hybrid approach points the way forward for more successful deployments of community media systems, and reveals several interesting HCI issues to be studied further.

Recent studies have highlighted user concerns with respect to third-party tracking and online behavioral advertising (OBA) and the need for better consumer choice mechanisms to address these phenomena. We re-investigate the question of perceptions of third-party tracking while situating it in the larger context of how online ads, in general, are perceived by users. Via in-depth interviews with 53 Web users in India, we find that although concerns for third-party tracking and OBA remain noticeable amongst this population, other aspects of online advertising---like the possibility of being shown ads with embarrassing and suggestive content---are voiced as greater concerns than the concern of being tracked. Current-day blocking tools are insufficient to redress the situation: users demand selective filtering of ad content (as opposed to blocking out all ads) and are not satisfied with mechanisms that only control tracking and OBA. We conclude with design recommendations for enduser tools to control online ad consumption keeping in mind the concerns brought forth by our study.

In this paper, we propose a classification scheme that differentiates Ethernet and WLAN TCP flows based on measurements collected passively at the edge of a network. This scheme computes two quantities, the fraction of wireless TCP flows and the degree of belief that a TCP flow traverses a WLAN inside the network, using an iterative Bayesian inference algorithm that we developed. We prove that this iterative Bayesian inference algorithm converges to the unique maximum likelihood estimate (MLE) of these two quantities. Furthermore, it has the advantage that it can handle any general K-classification problem given the marginal distributions of these classes. Numerical and experimental evaluations demonstrate that our classification scheme obtains accurate results. We apply this scheme to two sets of traces collected from two campus networks: one set collected from UMass in mid 2005 and the other collected from UConn in late 2010. Our technique infers that 4%-7% and 52%-55% of incoming TCP flows traverse an IEEE 802.11 wireless link in these two networks, respectively.

In this paper, we propose two online algorithms to detect 802.11 traffic from packet-header data collected passively at a monitoring point. These algorithms have a number of applications in real-time wireless LAN management, for instance, in detecting unauthorized access points and detecting/predicting performance degradations. Both algorithms use sequential hypothesis tests and exploit fundamental properties of the 802.11 CSMA/CA MAC protocol and the half-duplex nature of wireless channels. They differ in that one requires training sets, while the other does not. We have built a system for online wireless traffic detection using these algorithms and deployed it at a university gateway router. Extensive experiments have demonstrated the effectiveness of our approach: the algorithm that requires training provides rapid detection and is extremely accurate (the detection is mostly within 10 seconds, with very low false-positive and false-negative ratios), the algorithm that does not require training detects 60 percent to 76 percent of the wireless hosts without any false positives, and both algorithms are lightweight, with computation and storage overhead well within the capability of commodity equipment.

IEEE 802.16e WiMAX is a promising new technology for broadband access networks. Amongst the class of applications that can be supported is real time video services (such as IPTV, broadcast of live events etc.). These applications are bandwidth hungry and have stringent delay constraints. Thus, scalable support for such applications is a challenging problem. To address this challenge, we consider a combination of approaches using multicast, layer encoded video and adaptive modulation of transmissions. Using these, we develop algorithms to ensure efficient, fair and timely delivery of video in WiMAX networks. The corresponding resource allocation problem is challenging because scheduling decisions (within a WiMAX base station) are performed in real-time across two dimensions, time and frequency. Moreover, combining layered video with appropriate modulation calls for novel MAC algorithms. We model the multicast resource allocation problem in WiMAX and demonstrate this problem to be NP-hard. We present a fast greedy algorithm that is (i) provably within a constant approximation of the optimal solution (based on a metric that reflects video quality as perceived by the user), and (ii) performs within 87-95% of the optimal as demonstrated by realistic simulations. We also demonstrate that our algorithm offers a 25% improvement over a naive algorithm. Moreover, in terms of the average rate received by each user, our algorithm out-performs the naive algorithm by more than 50%.

In this paper we present a new channel allocation scheme for IEEE 802.11 based mesh networks with point-to- point links, designed for rural areas. Our channel allocation scheme allows continuous full-duplex data transfer on every link in the network. Moreover, we do not require any synchronization across the links as the channel assignment prevents cross link interference. Our approach is simple. We consider any link in the network as made up of two directed edges. To each directed edge at a node, we assign a non-interfering IEEE 802.11 channel so that the set of channels assigned to the outgoing edges is disjoint from channels assigned to the incoming edges. Evaluation of this scheme in a testbed demonstrate throughput gains of between 50 - 100%, and significantly less end-to-end delays, over existing link scheduling/channel allocation protocols (such as 2P [11]) designed for point-to-point mesh networks. Formally speaking, this channel allocation scheme is equivalent to an edge-coloring problem, that we call the directed edge coloring (DEC) problem. We establish a relationship between this coloring problem and the classical vertex coloring problem, and thus, show that this problem is NP-hard. More precisely, we give an algorithm that, given k vertex coloring of a graph can directed edge color it using xi(k) colors, where xi(k) is the smallest integer n such that (lfloorn/2rfloor/n ) ges k.

IEEE 802.11 WiFi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antennas that can establish long-distance wireless point-to-point links. Some nodes in the network (called gateway nodes) are directly connected to the wired internet, and the remaining nodes connect to the gateway(s) using one or more hops. The dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links and the physical obstructions along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to establish the selected links is minimized. We show that this problem is NP-hard and that a better than O(log n) approximation cannot be expected, where n is the number of vertices in the graph. We then present the first algorithm in the literature, for this problem, with provable performance bounds. More precisely, we present a greedy algorithm that is an O(log n) approximation algorithm for this problem. Finally, through simulations, we compare our approximation algorithm with both the optimal solution, and a naive heuristic.

IEEE 802.11 Wi-Fi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antenna that can establish long-distance point-point links. In recent work, a new MAC protocol named 2P has been proposed that is suited for the interference pattern within such a network. However, the 2P protocol requires the underlying graph (for each 802.11 channel) to be bi-partite. Under the assumption that 2P is the MAC protocol used in the mesh network, we make the following contributions in this paper. GivenKnon-interfering 802.11 channels, we propose a simple cut-based algorithm to computeKbi-partite sub-graphs (on each of which the 2P protocol can be run separately). We establish the class of graphs that can thus be completely covered byKbipartite subgraphs. For the remaining set of graphs, we look into the "price" of routing all end-to-end demands overonlythe bipartite subgraphs. We analytically establish what fraction of the max flow of the original mesh-graph can be routed over the bipartite subgraphs. Finally we look into the problem of mismatch between the load on a link (as computed by max flow) and its effective capacity under a given channel allocation. We propose heuristics to cluster links with similar loads into the same bipartite graphs (channels) and through comprehensive numerical simulations show that our heuristics come very close to the best possible flow.

Abstract — Verifying the accuracy of a passive measurementsbased inference technique under all possible network scenarios is a difficult challenge- the measurement point has limited observability of events along the path, and monitored paths can exhibit a wide range of network properties (packet loss, reordering, end-end delay, route changes). In this paper, we propose and apply formal verification techniques to exhaustively verify the correctness of an inference technique. We apply this approach to the problem of inferring packet retransmissions and reorderings from passively observed packets at a single measurement point. We define classification rules for this inference problem and, through a combination of model-checking and formal reasoning, uncover all possible events in the network for which the rules produce incorrect inferences. Our work is novel in its use of formal verification tools for evaluating inference techniques in network measurements. I.

2443-2454

In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS graph with that of graphs produced by topology generators that match the power-law degree distribution of the AS graph. We are guided by the existing notion that nodes in the AS graph can be placed in tiers with the resulting graph having an hierarchical structure. Our techniques are based on identifying graph nodes at each tier, decomposing the graph by removing such nodes and their incident edges, and thus explicitly revealing the interconnection structure of the graph. We define quantitative metrics to analyze and compare the decomposition of synthetic power-law graphs with the Internet-AS graph. Through experiments, we observe qualitative similarities in the decomposition structure of the different families of power-law graphs and explain any quantitative differences based on their generative models. We believe our approach provides insight into the interconnection structure of the AS graph and finds continuing applications in evaluating the representativeness of synthetic topology generators.

We propose a passive measurement methodology to infer and keep track of the values of two important variables associated with a TCP connection: the sender's congestion window (cwnd) and the connection round trip time (RTT). Together, these variables provide a valuable diagnostic of end-user-perceived network performance. Our methodology is validated via both simulation and concurrent active measurements, and is shown to be able to handle various flavors of TCP. Given our passive approach and measurement points within a Tier-1 network provider, we are able to analyze more than 10 million connections, with senders located in more than 45% of the autonomous systems in today's Internet. Our results indicate that sender throughput is frequently limited by a lack of data to send, that the TCP congestion control flavor often has minimal impact on throughput, and that the vast majority of connections do not experience significant variations in RTT during their lifetime

Peer-peer networking has recently emerged as a new paradigm for building distributed networked applications. We develop simple mathematical models to explore and illustrate fundamental performance issues of peer-peer file sharing systems. The modeling framework introduced and the corresponding solution methods are flexible enough to accommodate different characteristics of such systems. Through the specification of model parameters, we apply our framework to three different peer-peer architectures: centralized indexing, distributed indexing with flooded queries, and distributed indexing with hashing directed queries. Using our model, we investigate the effects of system scaling, freeloaders, file popularity and availability on system performance. In particular, we observe that a system with distributed indexing and flooded queries cannot exploit the full capacity of peer-peer systems. We further show that peer-peer file sharing systems can tolerate a significant number of freeloaders without suffering much performance degradation. In many cases, freeloaders can benefit from the available spare capacity of peer-peer systems and increase overall system throughput. Our work shows that simple models coupled with efficient solution methods can be used to understand and answer questions related to the performance of peer-peer file sharing systems.

We present a measurement study and classification methodology for out-of-sequence packets in TCP connections observed within the Sprint IP backbone. Such out-of-sequence packets can result from many causes including loss, looping, reordering, or duplication in the network. It is important to quantify and understand the causes of such out-of-sequence packets since they are one indication of the "health" of an end-end TCP connection. Our first contribution is methodological. Because we measure out-of-sequence packets at a single point in the backbone (rather than by sending and measuring end-end probe traffic at the sender or receiver), a new methodology is required to infer the causes of a connection's out-of-sequence packets based only on measurements taken in the "middle" of the connection. We thus describe techniques that classify the causes of observed out-of-sequence behavior based only on the previously- and subsequently-observed packets within a connection and knowledge of how TCP behaves. We show that using these simple techniques, it is possible to classify almost all out-of-sequence packets in our traces and that we can quantify the uncertainty in our classification. Our second contribution is the characterization of the out-of-sequence behavior itself. We analyze numerous several-hour packet-level traces from a set of OC-3 and OC-12 links for several million connections generated in nearly 4,300 unique ASs. Our measurements show a relatively consistent amount of out-of-sequence packets of approximately 5%. We find that few out-of-sequence packets result from pathological problems such as routing loops or in network duplication/reordering.

No abstract available.