INFOCOM 2015 Papers

Monitoring delays in the Internet is essential to understand the network condition and ensure the good functioning of time-sensitive applications. Large-scale measurements of round-trip time (RTT) are promising data sources to gain better insights into Internet-wide delays. However, the lack of efficient methodology to model RTTs prevents researchers from leveraging the value of these datasets. In this work, we propose a log-normal mixture model to identify, characterize, and monitor spatial and temporal dynamics of RTTs. This data-driven approach provides a coarse grained view of numerous RTTs in the form of a graph, thus, it enables efficient and systematic analysis of Internet-wide measurements. Using this model, we analyze more than 13 years of RTTs from about 12 millions unique IP addresses in passively measured backbone traffic traces. We evaluate the proposed method by comparison with external data sets, and present examples where the proposed model highlights interesting delay fluctuations due to route changes or congestion. We also introduce an application based on the proposed model to identify hosts deviating from their typical RTTs fluctuations, and we envision various applications for this empirical model.

End-to-end network monitoring is essential to ensure transmission quality for Internet applications. However, in large-scale networks, full-mesh measurement of network performance between all transmission pairs is infeasible. As a newly emerging sparsity representation technique, matrix completion allows the recovery of a low-rank matrix using only a small number of random samples. Existing schemes often fix the number of samples assuming the rank of the matrix is known, while the data features thus the matrix rank vary over time. In this paper, we propose to exploit the matrix completion techniques to derive the end-to-end network performance among all node pairs by only measuring a small subset of end-to-end paths. To address the challenge of rank change in the practical system, we propose a sequential and information-based adaptive sampling scheme, along with a novel sampling stopping condition. Our scheme is based only on the data observed without relying on the reconstruction method or the knowledge on the sparsity of unknown data. We have performed extensive simulations based on real-world trace data, and the results demonstrate that our scheme can significantly reduce the measurement cost while ensuring high accuracy in obtaining the whole network performance data.

We address the problem of network-side localization where cellular operators are interested in localizing cellular devices by means of signal strength measurements alone. While fingerprinting-based approaches have been used recently to address this problem, they require significant amount of geo-tagged (`labeled') measurement data that is expensive for the operator to collect. Our goal is to use semi-supervised and unsupervised machine learning techniques to reduce or eliminate this effort without compromising the accuracy of localization. Our experimental results in a university campus (6 sq. km) demonstrate that sub-100m median localization accuracy is achievable with very little or no labeled data so long as enough training is possible with `unlabeled' measurements. This provides an opportunity for the operator to improve the model with time. We present extensive analysis of the error characteristics to gain insight and improve performance, including understanding spatial properties and developing confidence measures.

Full-duplex radio technology is becoming mature and holds potential to boost the spectrum efficiency of a point-to-point wireless link. However, a fundamental understanding is still lacking, with respect to its advantage over half-duplex in multi-cell wireless networks with contending links. In this paper, we establish a spatial stochastic framework to analyze the mean network throughput gain from full-duplex, and pinpoint the key factors that determine the gain. Our framework extends classical stochastic geometry analysis with a new tool-set, which allows us to model a trade-off between the benefit from concurrent full-duplex transmissions and the loss of spatial reuse, particularly for CSMA-based transmitters with random backoff. The analysis derives closed-form expressions for the full-duplex gain as a function of link distance, interference range, network density, and carrier sensing schemes. It can be easily applied to guide the deployment choices during the early stage of network planning.

Cloud storage has gained a remarkable success in recent years with an increasing number of consumers and enterprises outsourcing their data to the cloud. To assure the availability and integrity of the outsourced data, several protocols have been proposed to audit cloud storage. Despite the formally guaranteed security, the constructions employed heavy cryptographic operations as well as advanced concepts (e.g., bilinear maps over elliptic curves and digital signatures), and thus are inefficient to admit wide applicability in practice. In this paper, we design a novel secure cloud storage protocol, which is conceptually and technically simpler and significantly more efficient than previous constructions. Inspired by a classic string equality checking protocol in distributed computing, our protocol uses only basic integer arithmetic (without advanced techniques and concepts). As simple as the protocol is, it supports both randomized and deterministic auditing to fit different applications. We further extend the proposed protocol to support data dynamics, i.e., adding, deleting and modifying data, using a novel technique. As a further contribution, we find a systematic way to design secure cloud storage protocols based on verifiable computation protocols. Theoretical and experimental analyses validate the efficacy of our protocol.

The landscape of cyber security has been reformed dramatically by the recently emerging Advanced Persistent Threat (APT). It is uniquely featured by the stealthy, continuous, sophisticated and well-funded attack process for long-term malicious gain, which render the current defense mechanisms inapplicable. A novel design of defense strategy, continuously combating APT in a long time-span with imperfect/incomplete information on attacker's actions, is urgently needed. The challenge is even more escalated when APT is coupled with the insider threat (a major threat in cyber-security), where insiders could trade valuable information to APT attacker for monetary gains. The interplay among the defender, APT attacker and insiders should be judiciously studied to shed insights on a more secure defense system. In this paper, we consider the joint threats from APT attacker and the insiders, and characterize the fore-mentioned interplay as a two-layer game model, i.e., a defense/attack game between defender and APT attacker and an information-trading game among insiders. Through rigorous analysis, we identify the best response strategies for each player and prove the existence of Nash Equilibrium for both games. Extensive numerical study further verifies our analytic results and examines the impact of different system configurations on the achievable security level.

In this paper, we propose a system called R# to estimate the number of human objects using passive RFID tags but without attaching anything to human objects. The idea is based on our observation that the more human objects are present, the higher the variance in the RSS values of the tag backscattered RF signal. Thus, based on the received RF signal, the reader can estimate the number of human objects. R# includes an RFID reader and some (say 20) passive tags, which are deployed in the region that we want to monitor the number of human objects, such as the region in front of a painting. The RFID reader periodically emits RF signal to identify all tags and the tags simply respond with their IDs via C1G2 standard protocols. We implemented R# using commercial Impinj H47 passive RFID tags and Impinj reader model R420. We conducted experiments in a simulated picking aisle area of the supermarket environment. The experimental results show that R# can achieve high estimation accuracy (more than 90%).

We study optimal radio resource allocation across multiple tiers of a heterogeneous wireless network in order to maximize the downlink sum throughput. Different from prior works, we consider both the randomness of base stations in space and dynamic user traffic session arrivals in time, accounting for both elastic and inelastic user traffic. A new stochastic analysis framework, which accommodates both spatial and temporal dimensions, is proposed to quantify the throughput objective. The derived throughput function is not in closed form and is non-concave in terms of the radio resource allocation factors to be optimized, hindering the search for an efficient optimization solution. Therefore, we further develop closed-form concave bounds that envelop the throughput function, to form convex approximations of the original optimization problem that can be solved efficiently. We characterize the performance gap when these bounds are used instead of the original objective. Both analytical bounding and simulation experiments demonstrate that the proposed solution is nearly optimal.

Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguñá, Vahdat (INFOCOM, pp. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs G and present new results on the expected number of k-cliques E[Kk] and the size of the largest clique ω(G). We observe that there is a phase transition at power-law exponent γ = 3. More precisely, for γ ε (2,3) we prove E[Kk] = nk(3-γ)/2Θ(k)-kand ω(G) = Θ(n(3-γ)/2) while for γ ≥ 3 we prove E[Kk] = nΘ(k)-kand ω(G) = Θ(log(n)/log log n). We empirically compare the ω(G) value of several scale-free random graph models with real-world networks. Our experiments show that the ω(G)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.

Cloud-assisted e-healthcare systems significantly facilitate the patients to outsource their personal health information (PHI) for medical treatment of high quality and efficiency. Unfortunately, a series of unaddressed security and privacy issues dramatically impede its practicability and popularity. In e-healthcare systems, it is expected that only the primary physicians responsible for the patients treatment can not only access the PHI content but verify the real identity of the patient. Secondary physicians participating in medical consultation and/or research tasks, however, are only permitted to view or use the content of the protected PHI, while unauthorized entities cannot obtain anything. Existing work mainly focuses on patients conditional identity privacy by exploiting group signatures, which are very computationally costly. In this paper, we propose a white-box traceable and revocable multi-authority attribute-based encryption named TR-MABE to efficiently achieve multilevel privacy preservation without introducing additional special signatures. It can efficiently prevent secondary physicians from knowing the patients identity. Also, it can efficiently track the physicians who leak secret keys used to protect patients identity and PHI. Finally, formal security proof and extensive simulations demonstrate the effectiveness and practicability of our proposed TR-MABE in e-healthcare cloud computing systems.

With increasing popularity of location-based services (LBSs), there have been growing concerns for location privacy. To protect location privacy in a LBS, mobile users in physical proximity can work in concert to collectively change their pseudonyms, in order to hide spatial-temporal correlation in their location traces. In this study, we leverage the social tie structure among mobile users to motivate them to participate in pseudonym change. Drawing on a social group utility maximization (SGUM) framework, we cast users' decision making of whether to change pseudonyms as a socially-aware pseudonym change game (PCG). The PCG further assumes a general anonymity model that allows a user to have its specific anonymity set for personalized location privacy. For the SGUM-based PCG, we show that there exists a socially-aware Nash equilibrium (SNE), and quantify the system efficiency of the SNE with respect to the optimal social welfare. Then we develop a greedy algorithm that myopically determines users' strategies, based on the social group utility derived from only the users whose strategies have already been determined. It turns out that this algorithm can efficiently find a Pareto-optimal SNE with social welfare higher than that for the socially-oblivious PCG, pointing out the impact of exploiting social tie structure. We further show that the Pareto-optimal SNE can be achieved in a distributed manner.

To stay competitive, plenty of data mining techniques have been introduced to help stores better understand consumers' behaviors. However, these studies are generally confined within the customer transaction data. Actually, another kind of `deep shopping data', e.g. which and why goods receiving much attention are not purchased, offers much more valuable information to boost the product design. Unfortunately, these data are totally ignored in legacy systems. This paper introduces an innovative system, called TagBooth, to detect commodities' motion and further discover customers' behaviors, using COTS RFID devices. We first exploit the motion of tagged commodities by leveraging physical-layer information, like phase and RSS, and then design a comprehensive solution to recognize customers' actions. The system has been tested extensively in the lab environment and used for half a year in real retail store. As a result, TagBooth generally performs well to acquire deep shopping data with high accuracy.

In wireless networks, broadcasting is a fundamental communication primitive for network management and information sharing. However, in multi-channel networks, the broadcast efficiency is very poor as devices are distributed across various channels. Thus, a sender tries all channels for broadcasting a single message, which causes large overhead. In this paper, we propose a novel scheme for efficient broadcast in multichannel networks. Our scheme leverages the overlapped band, which is the frequency range that partially overlapped channels (i.e., adjacent channels) share within their channel boundaries. Specifically, a sender advertises the rendezvous channel through the overlapped band of adjacent channels; the message sharing via broadcast is done on the rendezvous channel. Our scheme employs Signaling via Overlapped Band (SOB), which defines a new signal processing mechanism for communication via the overlapped band. SOB is integrated with MAC layer mechanisms: 1) Reserve Idle Spectrum Fragment (RISF) to reduce waiting time, 2) Reinforce Switch Notification (RSN) to reduce the residing time at a wrong channel, and 3) Multi-sender Agreement on Rendezvous CHannel (MARCH) to support multisender broadcasts. We implemented our scheme on the SORA platform. Experiment results validated communication through the overlapped band. Intensive simulation studies showed that our scheme drastically outperformed previous approach.

We explore the use of TV White Space (TVWS) wireless networks for providing robust and long range connectivity to vehicles. A key distinctive requirement of TVWS networks is the power asymmetry - the static APs are allowed to transmit at up to 4 W, while the mobile clients in vehicles are limited to only 100 mW. Our measurements reveal that the power asymmetry not only causes severe uplink blackouts but also poses significant coexistence problems, as high-power fixed nodes can easily starve the low-power mobile ones due to carrier sensing loss. To tackle these unique challenges, we propose a cross-layer design of a Direct-Sequence Spread Spectrum (DSSS) based system. We employ an adaptive DSSS mechanism that strategically configures the spreading code, so as to boost uplink coverage while maximizing throughput. We further design a traffic-aware code assignment algorithm for uplink packets to balance the requirement of throughput-intensive and latency-sensitive flows. We have implemented the design on a TVWS software-radio platform on a moving vehicle in an urban environment, and demonstrated that link asymmetry can be completely removed to support realistic application traffic, while the carrier sense loss rate at fixed nodes can be reduced by around 85%.

Named Data Networking (NDN) as an instantiation of the Content-Centric Networking (CCN) approach, embraces the major shift of the network function - from host-to-host conversation to content dissemination. The NDN forwarding architecture consists of three tables - Content Store (CS), Pending Interest Table (PIT) and Forwarding Information Base (FIB), as well as two lookup rules - Longest Prefix Match (LPM) and Exact Match (EM). A software-based implementation for this forwarding architecture would be low-cost, flexible and have rich memory resource, but may also make the pipelining technique not readily applicable to table lookups. Therefore, forwarding a packet would go through multiple tables sequentially without pipelining, leading to high latency and low throughput. In order to take advantage of the software-based implementation and overcome its shortcoming, we find that, a single unified index that supports all the three tables and both LPM and EM lookup rules would benefit the forwarding performance. In this paper, we present such an index data structure called BFAST (Bloom Filter-Aided haSh Table). BFAST employs a Counting Bloom Filter to balance the load among hash table buckets, making the number of prefixes in each non-empty bucket close to 1, and thus enabling high lookup throughput and low latency. Evaluation results show that, for solely LMP lookup, BFAST can arrive at 36.41 million lookups per second (M/s) using 24 threads, and the latency is around 0.46 μs. When utilized to build the NDN forwarding architecture, BFAST obtains remarkable performance promotion under various request composition, e.g., BFAST achieves a lookup speed of 81.32 M/s with a synthetic request trace where 30% of the requests hit CS, another 30% hit PIT and the rest 40% hit FIB, while the lookup latency is only 0.29 μs

We present a novel technique for estimating the round trip time network latency between two off-path end hosts. That is, given two arbitrary machines, A and B, on the Internet, our technique measures the round trip time from A to B. We take advantage of information side-channels that are present in the TCP/IP network stack of modern Linux kernels to infer information about off-path routes. Compared to previous tools, ours does not require additional resources, machines, or require additional protocols beyond TCP. The only requirements are that one end host have an open port and be running a modern Linux kernel and that the other end host responds to unsolicited SYN-ACK packets with a RST packet. We evaluate our technique “in the wild” and compare our off-path estimates to on-path measurements. Our experiments show that our technique provides accurate, real-time estimates of off-path network latency. In over 80% of measurements our technique provides off-path round trip time measurements within 20% of the actual round trip time. We also discuss possible causes of errors that impact the accuracy of our measurements.

There are network management, traffic engineering, and security practices adopted in today's networking that rely on the knowledge about what applications' traffic is passing through the networks. These practices might fail with mobile apps whose identity remains hidden in generic HTTP traffic. The main reason is that unlike traditional applications, most mobile apps do not use specific protocols or IP ports with distinctive features. Many enterprises and service providers are in a great need of regaining control over their networks that increasingly carry mobile traffic. In this paper we propose FLOWR, a system that automatically identifies mobile apps by continually learning the apps' distinguishing features via traffic analysis. FLOWR focuses solely on key-value pairs in HTTP headers and intelligently identifies the pairs suitable for app signatures. Our system employs a custom supervised learning approach that leverages a very limited knowledge of app-signature seeds and autonomously grows its capacity for app identification. The approach is motivated by a simple but effective hypothesis that unknown app-identifying features should co-occur with the known signatures. Our experimental results show a significant growth in flow identification coverage provided by FLOWR. Specifically, we show that FLOWR can achieve identification of 86-95% of flows related to their generating apps.

Web page classification is useful in many domains- including ad targeting, traffic modeling, and intrusion detection. In this paper, we investigate whether learning-based techniques can be used to classify web pages based only on anonymized TCP/IP headers of traffic generated when a web page is visited. We do this in three steps. First, we select informative TCP/IP features for a given downloaded web page, and study which of these remain stable over time and are also consistent across client browser platforms. Second, we use the selected features to evaluate four different labeling schemes and learning-based classification methods for web page classification. Lastly, we empirically study the effectiveness of the classification methods for real-world applications.

With recent standardization and deployment of LTE eMBMS, cellular multicast is gaining traction as a method of efficiently using wireless spectrum to deliver large amounts of multimedia data to multiple cell sites. Cellular operators still seek methods of performing optimal resource allocation in eMBMS based on a complete understanding of the complex interactions among a number of mechanisms: the multicast coding scheme, the resources allocated to unicast users and their scheduling at the base stations, the resources allocated to a multicast group to satisfy the user experience of its members, and the number of groups and their membership, all of which we consider in this work. We determine the optimal allocation of wireless resources for users to maximize proportional fair utility. To handle the heterogeneity of user channel conditions, we efficiently and optimally partition multicast users into groups so that users with good signal strength do not suffer by being grouped together with users of poor signal strength. Numerical simulations are performed to compare our scheme to practical heuristics and state-of-the-art schemes. We demonstrate the tradeoff between improving unicast user rates and improving spectrum efficiency through multicast. Finally, we analyze the interaction between the globally fair solution and individual user's desire to maximize its rate. We show that even if the user deviates from the global solution in a number of scenarios, we can bound the number of selfish users that will choose to deviate.