Reference signals from cellular networks present an untapped and abundant signal of opportunity for high quality radio frequency (RF) propagation measurements. Commercial-off-the-shelf mobile phones continuously capture and report Reference Signal Received Power (RSRP) measurements, making them an easily crowdsource-able data source for RF propagation modeling in path geometries and frequencies relevant to cellular communications, broadcast, and short-range outdoor communications systems. However, it remains unclear whether crowdsourced mobile phone RSRP measurements can meet the stringent accuracy requirements of measured propagation data in support of RF propagation model validation and improvement.

In this paper, we conduct a measurement study on operational 5G networks deployed across different frequency bands (mmWave and sub-6GHz) and server locations (mobile edge and Internet cloud). Specifically, we assess 5G performance in both uplink and downlink across multiple operators’ networks. We then carry out extensive comparisons of transport-layer protocols using ten different algorithms in full-fledged 5G networks, including an edge computing environment. Finally, we evaluate representative mobile applications over the 5G network with and without edge servers. Our comprehensive measurements provide several insights that affect the experience of 5G users: (i) With a 5G edge server, existing TCP congestion control algorithms can achieve throughput up to 1.8Gbps with only a single flow. (ii) The maximum TCP receive buffer size, which is set by off-the-shelf 5G phones, can limit the throughput performance of 5G networks, which is not observed in 4G LTE-A networks. (iii) Despite significant latency gains in download-centric applications, the 5G edge service provides limited benefits to CPU-intensive tasks or those that use significant uplink bandwidth. To our knowledge, this is the first measurement-driven understanding of 5G edge computing “in the wild,” which can provide an answer to how edge computing would perform in real 5G networks.

As datacenters become the new computing platform, integrating server-centric distributed systems into modern network hardware is gaining interest under the diminishing Moore's law. Researchers want to build reusable primitives that can take advantage of modern network hardware and offload common system components of a broad range of applications. In this paper, we present Mostly Reliable Totally Ordered Multicast, a reusable network primitive that can embed reliable group communication into the network. MRTOM is a network-centric approach that handles message replication, ordering, and reliable delivery using a network fast path, freeing server CPUs for application logic. MRTOM can be implemented in the programmable switches and edge interfaces (e.g., Smart-NICs), significantly reducing network traffic compared to the existing approaches and improving job finish time amid packet loss. With MRTOM, we were able to accelerate multiple high-performance applications whose fast path can be totally offloaded into the network. For example, a Paxos application, MRTOM-Paxos, achieves > 1,100,000 transactions/secs and$23\mu \mathrm{s}$minimum latency. A replicated key-value store, MRTOM-KV, also shows significant latency reduction with eBPF/XDP in the Linux Kernel, which is further improved by offloading into SmartNICs.

Video conferencing has become a daily necessity, but protocols to support video conferencing have yet to keep pace despite the innovation in next-generation networks. As video resolutions increase and mobile applications using multiple cameras for photos and videos become popular, the need to meet the Quality of Experience (QoE) requirements is growing. Multipath protocols could be a possible solution.

The demand for video conferencing applications has seen explosive growth while users still often face unsatisfactory quality of experience (QoE). Video conferencing applications adopt Forward Error Correction (FEC) as a recovery mechanism to meet tight latency requirements and overcome packet losses prevalent in the network. However, many studies mainly focused on video rate control by neglecting the complex interactions of this video recovery mechanism on the rate control and its impact on the user QoE. Deciding the right amount of FEC for the current video rate under a dynamically changing network environment is not straightforward. For instance, the higher FEC may enhance the tolerance to packet losses, but it may increase latency due to FEC processing overhead and hurt the video quality due to the additional bandwidth used for FEC. To address this issue, we propose R-FEC which is a reinforcement learning (RL) based framework for video and FEC bitrate decisions in video conferencing. R-FEC aims to improve overall QoE by automatically learning through the results of past decisions and adjusting video and FEC bitrates to maximize the user QoE while minimizing the congestion in the network. Our experiments show that R-FEC outperforms the state-of-the-art solutions in video conferencing, with up to 27% improvement in its video rate and 6dB PSNR improvement in video quality over the default WebRTC.

Video conferencing applications have seen explosive growth both in the number of available applications and their use. However, there have been few studies on the detailed analysis of video conferencing applications with respect to network dynamics, yet understanding these dynamics is essential for network design and improving these applications. In this paper, we carry out an in-depth measurement and modeling study on the rate control algorithms used in six popular commercial video conferencing applications. Based on macroscopic behaviors commonly observed across these applications in our extensive measurements, we construct a unified architecture to model the rate control mechanisms of individual applications. We then reconstruct each application's rate control by inferring key parameters that closely follow its rate control and quality adaptation behaviors. To our knowledge, this is the first work that reverse-engineers rate control algorithms of popular video conferencing applications, which are often unknown or hidden as they are proprietary software. We confirm our analysis and models using an end-to-end testbed that can capture the dynamics of each application under a variety of network conditions. We also show how we can use these models to gain insights into the particular behaviors of an application in two practical scenarios.

As video calls and personal broadcasting become popular, the demand for mobile live streaming over cellular uplink channels is growing fast. However, current live streaming solutions are known to suffer from frequent uplink throughput fluctuations causing unnecessary video stalls and quality drops. As a remedy to this problem, we propose PERCEIVE, a deep learning-based uplink throughput prediction framework. PERCEIVE exploits a 2-stage LSTM (Long Short Term Memory) design and makes throughput predictions for the next 100ms. Our extensive evaluations show that PERCEIVE, trained with LTE network traces from three major operators in the U.S., achieves high accuracy in the uplink throughput prediction with only 7.67% mean absolute error and outperforms existing prediction techniques. We integrate PERCEIVE with WebRTC, a popular video streaming platform from Google, as a rate adaptation module. Our implementation on the Android phone demonstrates that it can improve PSNR by up to 6dB (4x) over the default WebRTC while providing less streaming latency.

We investigate solutions to subgraph matching within a temporal stream of data. We present a high-level language for describing temporal subgraphs of interest, the Streaming Analytics Language (SAL). SAL programs are translated into C++ code that is run in parallel on a cluster. We call this implementation of SAL the Streaming Analytics Machine (SAM). SAL programs are succinct, requiring about 20 times fewer lines of code than using the SAM library directly, or writing an implementation using Apache Flink. To benchmark SAM we calculate finding temporal triangles within streaming netflow data. Also, we compare SAM to an implementation written for Flink. We find that SAM is able to scale to 128 nodes or 2560 cores, while Apache Flink has max throughput with 32 nodes and degrades thereafter. Apache Flink has an advantage when triangles are rare, with max aggregate throughput for Flink at 32 nodes greater than the max achievable rate of SAM. In our experiments, when triangle occurrence was faster than five per second per node, SAM performed better. Both frameworks may miss results due to latencies in network communication. SAM consistently reported an average of 93.7% of expected results while Flink decreases from 83.7% to 52.1% as we increase to the maximum size of the cluster. Overall, SAM can obtain rates of 91.8 billion netflows per day.

4G LTE networks across the world (e.g., United States, Europe, and South Korea) use the same mechanism to broadcast emergency alerts. These alerts include AMBER, severe weather alerts, and the (unblockable) Presidential Alert in the US. We demonstrate the ability to spoof these alerts by forcing any 4G phone in the area of our malicious cell tower to receive and display a fabricated message. This demonstration uses a commercially-available software-defined radio, an LTE base station, and our modifications to the open-source NextEPC and srsLTE libraries to send the Presidential Alert to phones volunteered from the audience.

This paper presents a fully distributed scheduling framework called CASTLE (Client-side Adaptive Scheduler That minimizes Load and Energy), which jointly optimizes the spectral efficiency of cellular networks and battery consumption of smart devices. To do so, we focus on scenarios when many smart devices compete for cellular resources in the same base station: spreading out transmissions over time so that only a few devices transmit at once improves both spectral efficiency and battery consumption. To this end, we devise two novel features in CASTLE. First, we explicitly consider inter-cell interference for accurate cellular load estimation. Based on our observations, we exploit the RSRQ (Reference Signal Received Quality) and SINR as features in a machine learning algorithm to accurately estimate the cellular load. Second, we propose a fully distributed scheduling algorithm that coordinates transmissions between clients based on the locally estimated load level at each client. Our formulation for minimizing battery consumption at each device leads to an optimized backoff-based algorithm that fits practical environments. To evaluate these features, we prototype a complete LTE system testbed consisting of mobile devices, eNodeBs, EPC (Evolved Packet Core) and application servers. Our comprehensive experimental results show that CASTLE's load estimation is up to 91% accurate, and that CASTLE achieves higher spectral efficiency with less battery consumption, compared to existing centralized scheduling algorithms as well as a distributed CSMA-like protocol. Furthermore, we develop a light-weight SDK that can expedite the deployment of CASTLE into smart devices and evaluate it in a commercial LTE network.

Modern cell phones are required to receive and display alerts via the Wireless Emergency Alert (WEA) program, under the mandate of the Warning, Alert, and Response Act of 2006. These alerts include AMBER alerts, severe weather alerts, and (unblockable) Presidential Alerts, intended to inform the public of imminent threats. Recently, a test Presidential Alert was sent to all capable phones in the United States, prompting concerns about how the underlying WEA protocol could be misused or attacked. In this paper, we investigate the details of this system, and develop and demonstrate the first practical spoofing attack on Presidential Alerts, using both commercially available hardware as well as modified open source software. Our attack can be performed using a commercially-available software defined radio, and our modifications to the open source NextEPC and srsLTE software libraries. We find that with only four malicious portable base stations of a single Watt of transmit power each, almost all of a 50,000-seat stadium can be attacked with a 90% success rate. The true impact of such an attack would of course depend on the density of cell phones in range; fake alerts in crowded cities or stadiums could potentially result in cascades of panic. Fixing this problem will require a large collaborative effort between carriers, government stakeholders, and cell phone manufacturers. To seed this effort, we also discuss several defenses to address this threat in both the short and long term.

We present the demonstration of a fully distributed scheduling framework called CASTLE (Client-side Adaptive Scheduler That minimizes Load and Energy) that jointly optimizes the spectral efficiency of cellular networks and battery consumption of smart devices. To do so, we focus on scenarios when many smart devices compete for cellular resources in the same base station: spreading out transmissions over time so that only a few devices transmit at once and improves both spectral efficiency and battery consumption. To this end, we devise two novel features in CASTLE. First, we explicitly consider inter-cell interference for accurate cellular load estimation in our machine learning algorithm. Second, we propose a fully distributed scheduling algorithm that coordinates transmissions between clients based on the locally estimated load level at each client. Our formulation for minimizing battery consumption at each device leads to an optimized back off-based algorithm that fits practical environments. Our comprehensive experimental results show that CASTLE's load estimation is up to 91 % accurate, and that CASTLE achieves higher spectral efficiency with less battery consumption, compared to existing centralized scheduling algorithms as well as a distributed CSMA-like protocol. Furthermore,we develop a light-weight SDK that can expedite the deployment of CASTLE into smart devices and evaluate it in a commercial LTE network.

The storage and management of secrets (encryption keys, passwords, etc) are significant open problems in the age of ephemeral, cloud-based computing infrastructure. How do we store and control access to the secrets necessary to configure and operate a range of modern technologies without sacrificing security and privacy requirements or significantly curtailing the desirable capabilities of our systems? To answer this question, we propose Tutamen: a next-generation secret-storage service. Tutamen offers a number of desirable properties not present in existing secret-storage solutions. These include the ability to operate across administrative domain boundaries and atop minimally trusted infrastructure. Tutamen also supports access control based on contextual, multi-factor, and alternate-band authentication parameters. These properties have allowed us to leverage Tutamen to support a variety of use cases not easily realizable using existing systems, including supporting full-disk encryption on headless servers and providing fully-featured client-side encryption for cloud-based file-storage services. In this paper, we present an overview of the secret-storage challenge, Tutamen's design and architecture, the implementation of our Tutamen prototype, and several of the applications we have built atop Tutamen. We conclude that Tutamen effectively eases the secret-storage burden and allows developers and systems administrators to achieve previously unattainable security-oriented goals while still supporting a wide range of feature-oriented requirements.

In this paper we use anomaly scores derived from a technique for bipartite graphs as features for a supervised machine learning algorithm for two cyber security problems: classifying Short Message Service (SMS) text messages as either spam or non-spam and detecting malicious lateral movement within a network. While disparate problems, both spam and lateral movement detection can be viewed as bipartite graphs and we can compute bipartite anomaly scores for each situation. The bipartite anomaly scores by themselves are not very predictive, but used as auxiliary features can boost the receiver operating characteristic (ROC) curve of a supervised classifier. We examine the UCI SMS Spam Collection Data Set for the SPAM problem and use an authentication graph from Los Alamos National Laboratory. We create features by dimensionality reduction through principal component analysis (PCA) on the message-term or user-computer matrix, and then augment those features with anomaly scores. By using the anomaly scores we are able to improve the area under the curve (AUC) for the receiver operating characteristic (ROC) up to 27.5% for the spam data and 21.4% for the authentication data.

Fostering an effective learning environment in large classes is a challenge: instructors and teaching assistants are stretched thin across many students, students often lack opportunities for personal interaction with course staff, and the size of the classes makes them seem impersonal. Furthermore, students in large classes can often find solutions to their labs and assignments online or copy them from other students, diminishing their impetus to learn and raising plagiarism concerns.

Recent work has examined techniques to estimate the “best” modulation rate for data networks such as 802.11a/g. While accurate rate estimation yields better rate-selection decisions and increased throughput, those methods must still choose between a handful of modulation rates. Each modulation rate is effective in a range of actual signal-to-noise ratios (SNRs) but the limited number of practical rates means that transmitters are often forced to “step down” to a lower data rate despite having a higher SNR than the minimum required for that lower rate. In this paper we describe, evaluate and implement a practical multiuser communication scheme that exploits these discrete “steps” in modulation rates to transmit two packets in the time normally needed to transmit a single packet, increasing aggregate throughput precisely when it is most needed—when the network is busy and suffers from rate unfairness. Because the method transmits a group of packets simultaneously, we call this scheme Group Rate Transmission with Intertwined Symbols, or GRaTIS. In addition to up to 120% improvement in network throughput achieved by GRaTIS, the technique is backward compatible with 802.11 and doesn’t require complex DSP algorithms as required by competing methods.

Big data problems are often more akin to sparse graphs rather than relational tables. As such we argue that graph-based physical representations provide advantages in terms of both size and speed for executing queries. Drawing from research in sparse matrices, we use a compressed sparse row (CSR) format to model graph-oriented data. We also present two novel mechanisms for exploiting the CSR format that both find optimal join strategies and also prune variable bindings before expensive join operations occur. The first tactic we call Sprinkle SPARQL, which takes triple patterns of SPARQL queries and performs low-cost, linear-time set intersections to produce a constrained list of variable bindings for each variable in a query. Besides constrained lists of variable bindings, Sprinkle SPARQL also produces metrics that are consumed by the join algorithm to select an optimal execution path. The second tactic, graph joins, utilizes the CSR data structure as an index to efficiently join two variables expressed in a triple pattern together. We evaluate our approach on two data sets with over a billion edges: LUBM(8000) and an R-MAT graph generated with Graph5001parameters and extended to have edge labels.

Higher education is facing a paradigm shift in the ownership and use of computer hardware. The school computer lab is no longer the primary place of student computer use. Instead, students increasingly expect to use their own hardware to complete their school assignments. This creates a challenge for computer science educators: we must now support a wide range of heterogeneous hardware without the benefits of tight control over its use. To address this ``Bring-Your-Own-Device'' (BYOD) challenge, we leverage virtualization and software packaging systems to gracefully deploy and support a standardized development environment for all core CS courses across a range of both school-owned and student-owned computing devices. We have deployed and evaluated our system for the previous two years at scale and continue to actively use and develop it. It has effectively helped us support multiple classes comprising hundreds of students with very limited IT staffing. We describe the design and management of our system, present our experience using our system, and discuss the lessons we've learned. We also provide data reflecting current student user experience with our system. Our system has proven very effective in addressing the student BYOD challenge in a manageable, cost-efficient, and easy-to-use manner.

Who gets to use radio spectrum, and when, where, and how? Scheduling (who, where, when) and system configuration (how) are fundamental problems in radio communication and wireless networking. Optimization decomposition based on Lagrangian relaxation of signal quality requirements provides a mathematical framework for solving this type of combined problem. This paper demonstrates the technique as a solution to spatial reuse time-division multiple access (STDMA) scheduling with reconfigurable antennas. The joint beam steering and scheduling (JBSS) problem offers both a challenging mathematical structure and significant practical value. We present algorithms for JBSS and describe an implemented system based on these algorithms. We achieve up to 600% of the throughput of TDMA with a mean of 234% in our experiments. The decomposition approach leads to a working distributed protocol producing optimal solutions in an amount of time that is at worst linear in the size of the input. This is, to the best of our knowledge, the first actually implemented wireless scheduling system based on dual decomposition. We identify and briefly address some of the challenges that arise in taking such a system from theory to reality.

Online social networks (OSNs) such as Twitter provide a good platform for event discussions. Recent research [26][25] as shown that event discussions in OSNs are diverse and innovative and encourage public engagement in events. Although much research has been conducted in OSNs to track and detect events, there has been limited research on detecting or understanding the event context. Event context helps to better predict users' participation in events, identify relations among events, and recommend friends who share similar event context.

School districts across the country are embracing 21st century skills, and grappling with how to teach these to their K-12 students. At the same time, computer science educators are grappling with how to broaden participation. These two dilemmas are related, in that computer science can be used to teach many of the 21st century skills, and bringing computer science to all K-12 students can help broaden participation.

Engaging Computer Science in Traditional Education (ECSITE, pronounced "excite") is a 5-year program that began in 2009 to bring computer science into traditional K-12 classrooms. Rather than seeking to draw students into computing courses, we bring computing into the courses that students are already taking. To date, these have included art, biology, health education, mathematics, and social studies courses as well as a Native American focus program. Middle school and high school students are introduced to computational thinking and computer science concepts including algorithms, graph theory, and simulations in interdisciplinary contexts, mirroring the ways in which computing technologies are utilized in research and industry. Teachers report that students increase their understanding and perception of computer science, and that participating K-12 teachers increase their knowledge about computing and will continue to include the computational curriculum after their involvement with ECSITE.

Location information is becoming prevalent in today's online social networks (OSNs), which raises special privacy concerns with regard to both location sharing and its applications. Even when no explicit location is disclosed by a user, it is possible to geolocate the user through his/her social context, e.g., status updates and social relationships in OSNs. To demonstrate this, we propose GeoFind, which accurately identifies users' geographic regions through effective fusion (re-ranking) of (1) text-based ranking using geo-sensitive textual features and (2) structure-based ranking using maximum likelihood estimation (MLE) of geotagged friends. Evaluation results using 0.8 million geotagged Twitter users over a 3-month period demonstrate that GeoFind outperforms state-of-the-art techniques, with significant reduction of estimation error (25% of average error, 66% of median error). The potential of improving location accuracy through the fusion of multiple data types calls for a re-examination of existing privacy protection policies and mechanisms.

As we move forward towards the next generation of wireless protocols, the push for a better radio physical layer is ever increasing. Conventional radio architectures are limited to narrow operating regions and fails to adapt with changing technology. This is further strengthened with the advent of cognitive radio, which needs a more versatile and flexible framework that is programmable within the timing constraints of a protocol. In this paper we present an architecture for Software Defined Cognitive Radio that caters to the specific baseband processing requirements in a changing environment. We aim to provide more flexibility by de-constructing the radio pipeline into a framework of user controlled kernels that can be reconfigured at run-time. This architecture provides the bare-bones of a OFDM based radio physical layer that can adapt to perform a varied number of tasks in different radio networks. We also present a novel message based real-time reconfiguration method to transmit and receive a wide range of waveforms used in concurrent wireless protocols.

Vehicular safety systems for collisions or sensing rapid changes in traffic typically use two methods to communicate and disseminate traffic hazards. Many current systems use RADAR systems that transmit a radio wave and sense the reflective waves for angle-of-arrival or time-of-arrival information. Several proposed systems use vehicular networks to disseminate information about braking, emergencies or road conditions; when coupled with accelerometer or GPS information, these radio systems may also offer information on speed, traffic density or distance. In-vehicle RADAR systems are relatively expensive; vehicular radio based systems are less expensive. In this paper, we present a cooperative technology that combines these two techniques, seeking to adopt characteristics of both systems by employing a software defined radio for “cooperative RADAR” and vehicular networking. Our method uses multicarrier wireless communication to detect and disseminate. Using precise timing and synchronization, we can detect the distance of each of the vehicles, their current velocity and current acceleration or deceleration conditions. Using simultaneous, multi-party acknowledgments, we can rapidly disseminate or determine information about a number of vehicles in an efficient manner.

With advances in hardware, instruction set architectures are undergoing continual evolution. As a result, compilers are under constant pressure to adapt and take full advantage of available features. However, current techniques for evaluating relative compiler performance only compare profiles at the application level, ignoring relative performance differences at finer granularities. To ensure that new features are put to good use, a more rigorous approach is necessary. A fundamental step in tuning compiler performance is identifying the specific examples that can be improved. To solve this problem, we present a compiler-independent binary matching technique to compare executions of differently compiled programs and identify intervals where the behavior can be meaningfully compared. Matched intervals can be automatically analyzed to identify anomalous segments of execution where one version performs significantly differently versus another. We present case studies using Chainsaw to identify significant performance anomalies between differently compiled codes.

Computer systems are resource constrained. Application adaptation is a useful way to optimize system resource usage while satisfying the application performance constraints. Previous application adaptation efforts, however, were ad-hoc, time-consuming, and highly application-specific with limited portability between computer systems. In this work, our goal is to provide a development platform to systematically explore and rigorously apply portable application-specific runtime optimization. We present OCCAM, a software platform for developing multicore adaptive applications. OCCAM's design-time platform consists of APIs and data structures that allow application developers to specify the performance constraints and application-specific optimization techniques. OCCAM's run-time system dynamically manages the application behavior and optimizes system resource usage. OCCAM targets emerging Recognition, Mining, and Synthesis Applications (RMS). Using a set of RMS benchmarks, the experimental study demonstrates that OCCAM can successfully optimize resource usage under application performance constraints across a wide range of computer platforms, with an average of 38% energy savings on an Intel Atom-based, energy-constrained portable system, and an average of 24% energy savings on a high-performance, dual-core computer platform. These savings are accomplished with low overhead. We have also successfully extended OCCAM applications to run on a 16-core setup.

Compilers employ many aggressive code transformations to achieve highly optimized code. However, because of complex target architectures and unpredictable optimization interactions, these transformations may not always be beneficial. Current analysis methods measure performance at the application level and ignore optimization effects at the function and loop level. To better measure and understand these effects, we present OptiScope, a compiler independent tool to identify performance opportunities by comparing programs built with different compilers or optimization flags. The analysis includes hundreds of different metrics and uses a novel loop correlation technique for binary programs (produced from the same source by different compilers) to isolate measurements to specific regions. We present several case studies using OptiScope to identify key differences between different compiler suites, versions, and target architectures. The examples demonstrate performance improvement opportunities between 32.5% to 893% on select regions of SPEC 2006 benchmarks.

802.11 localization algorithms provide the ability to accurately position and track wireless clients thereby enabling location-based services and applications. However, we show that these localization techniques are vulnerable to non-cryptographic attacks where an adversary uses a low-cost directional antenna to appear from the localization algorithm's perspective to be in another arbitrary location of their choosing. The attacker's ability to actively influence where they are positioned is a key distinguishing feature of the directional attack relative to prior localization attacks that use transmit power control to introduce localization errors. We implement a representative set of received signal strength-based localization algorithms and evaluate the attack in a real office building environment. To mitigate the attack's effectiveness, we develop and evaluate an attack detection scheme that offers a high detection rate with few false positives.

Network protocols have traditionally been designed using a layered method in part because it is easier to implement some portions of network protocols in software and other portions must be implemented in hardware for performance reasons. These different implementation techniques enforce layer boundaries. In this paper, we show that with the advent of software defined radios, it becomes possible to blur those layer boundaries and produce higher performance network protocols as a result. In this paper we exploit a programmable physical layer and simultaneous transmission to have clients signal whether they have packets to send. By detecting the high energy at the simultaneous transmission, the AP gets the following information: a) which stations have packets to send and b) whether the traffic load is high, medium or low. Again, using the programmable physical layer, the AP schedules clients efficiently while wasting little of the spectrum on signaling overhead. The proposed protocol is a) fast, since no packet transmission is required for polling responses and all clients respond concurrently; b) reliable, as the poll response is contention free and c) scalable. We demonstrate the feasibility of implementing such a system using a FPGA based prototype software defined radio platform. We then show how the MAC protocol can scale using the QualNet network simulator and compare the performance to a contention based protocol.

Tor is currently the most popular low latency anonymizing overlay network for TCP-based applications. However, it is well understood that Tor's path selection algorithm is vulnerable to end-to-end traffic correlation attacks since it chooses Tor routers in proportion to their perceived bandwidth capabilities. Prior work has shown that the fraction of malicious routers and the amount of adversary-controlled bandwidth are significant factors for predicting the number of paths that an adversary can compromise. We extend this prior work by identifying that the application-layer protocol being transported is also a significant factor in predicting path compromise. Through a simulation study driven by data obtained from the real Tor network, we show that ports commonly associated with peer-to-peer file sharing protocols and the simple mail transport protocol (SMTP) are significantly more vulnerable to this attack than other ports.

Network protocol designers, both at the physical and network level, have long considered interference and simultaneous transmission in wireless protocols as a problem to be avoided. This, coupled with a tendency to emulate wired network protocols in the wireless domain, has led to artificial limitations in wireless networks.

Realistic radio modeling is crucial for accurate simulation of wireless networks. This paper examines the effect of using directional antennas in real environments with non-trivial multipath effects. We find that the actual variation in signal strength as a function of antenna direction differs appreciably - sometimes dramatically - from what the antenna power (gain) pattern alone would suggest. We quantify and analyze this difference across several antenna types and environments, and provide a generalizable parametric model to support more realistic planning, simulation and analysis.

Increasingly, directional antennas are being used in wireless networks. Such antennas can improve the quality of individual links and decrease overall interference. However, the interaction of environmental effects with signal directionality is not well understood. We observe that state of the art simulators make simplifying assumptions which are often unrealistic and can give a misleading picture of application layer performance. Because simulators are often used for prototyping and validating new ideas, their realism and accuracy are of primary importance. In this paper, we apply a new empirical simulation method for directional antennas and study how well this models reality. We show that not only is our model easy to implement, but is also more accurate and thus better able to predict the performance of propagation-sensitive applications.

In the design of wireless networking protocols and systems, simulation has become the primary form of initial validation and performance evaluation. Hence, ensuring the realism of simulators and simulation methods is fundamental for simulated results to be interpretable. In this paper, we provide a simulation framework for infrastructure wireless network traffic that allows researchers to use publicly available captured traces as a primary or background traffic source. We investigate the question of trace classification as a necessary task for these traces to be useful and apply our framework to a well-known power-saving application, showing that the use of real traffic provides substantially different results as compared to traffic generated from an application-specific fitted model or contrived source. Additionally, we show how trace classification provides unique insights into application behavior in both typical and extreme scenarios.

The network on chip will become a future general purpose interconnect for FPGAs much like todaypsilas standard OPB or PLB bus architectures. However, performance characteristics and reconfigurable logic resource utilization of different network on chip architectures vary greatly relative to bus architectures. Current mainstream FPGA parts only support very small network on chip topologies, due to the high resource utilization of virtual channel based implementations. This observation is reflected in related research where only modest 2times2 or 2times3 networks are demonstrated on FPGAs. Naively it would be assumed that these complex network on chip architectures would perform better than simplified implementations. We show this assumption to be incorrect under light network loading conditions across 3 separate application domains. Using statistical based network loading, a synthetic benchmarking application, a cryptographic accelerator, and a 802.11 transmitter are each demonstrated across network on chip architectures. From these experiments, it can be seen that network on chips with complex routing and switching functionality are still useful under high network loading conditions. Additionally, it is also shown for our network on chip implementations, a simple solution that uses 4-5times less logic resources can provide better network performance under certain conditions.

In recent years, a variety of algorithms for cognitive radio networks have been proposed. Many of these algorithms rely on the exchange of control information among the cognitive radio nodes and often require the presence of a globally available control channel. This requirement however poses a problem in a practical deployment: First, due to spectrum fluctuations such common control channel may be unknown at deployment stage. Second, when designating a fixed, dedicated control channel (for example in licensed spectrum), this will increase costs and expose vulnerability to the operation of the cognitive radio network. Thus, to overcome this difficulty, control channels should be dynamically assigned and managed in cognitive radio networks. In this paper, we propose the use of swarm intelligence as a way to dynamically find and manage such control channels in cognitive radio networks. The system we describe is able to independently identify viable control channels and adapt in presence of changing spectrum. We formalize the problem of control channel assignments to the multi-commodity flow problem, measure the performance of our approach in a hardware implementation and software simulation and compare the results against the theoretically optimal solution.

In this paper we use a large dataset of wireless user activity traces to test the various dynamic power management schemes. We also present and test our own empirically-driven dynamic power-saving algorithms, which are based on prior observations of user activity patterns. We believe that this sort of analysis can guide adoption of a user-behavior driven approach to radio and communications power management, and, in networking-centric devices, power management for the entire device. Additionally, understanding the characteristics of user-activity and efficient mechanisms to predict this activity can help inform the design of power-saving schemes for future networking protocols.

We present BitBlender, an efficient protocol that provides an anonymity layer for BitTorrent traffic. BitBlender works by creating an ad-hoc multi-hop network consisting of special peers called "relay peers" that proxy requests and replies on behalf of other peers. To understand the effect of introducing relay peers into the BitTorrent system architecture, we provide an analysis of the expected path lengths as the ratio of relay peers to normal peers varies. A prototype is implemented and experiments are conducted on Planetlab to quantify the performance overhead associated with the protocol. We also propose protocol extensions to add confidentiality and access control mechanisms, countermeasures against traffic analysis attacks, and selective caching policies that simultaneously increase both anonymity and performance. We finally discuss the potential legal obstacles to deploying an anonymous file sharing protocol. This work is among the first to propose a privacy enhancing system that is designed specifically for a particular class of peer-to-peer traffic.

The physical-layer models commonly used in current networking research only minimally address the interaction of directional antennas and radio propagation. This paper compares the models found in popular simulation tools with measurements taken across a variety of links in multiple environments. We find that the effects of antenna direction are significantly different from the models used by the common wireless network simulators. We propose a parametric model which better captures the effects of different propagation environments on directional antenna systems. We believe that adopting this model will allow more realistic simulation of protocols relying on directional antennas, supporting better design and more valid assessment of those protocols.

In recent years, cognitive radios that follow dynamic spectrum access policies have been proposed to overcome spectrum scarcity and to make better use of spectrum opportunities while avoiding interference to other users. The central component of such a cognitive radio is the control algorithm driving its sensing, learning and adaptation process. These three tasks however are both computationally expensive and resource intensive and it is therefore in the cognitive radio's best interest to minimize the time spent to sense, learn and adapt to its surroundings while still meeting its operational targets. In this paper, we present the rapid adaptation architecture, a statistical system that can be used in conjunction with existing cognitive radio control algorithms to speed up the learning and adaptation process without loosing significant accuracy. Through this system, control algorithms can be made more efficient by a factor of 2 or more, thus providing the cognitive radio with faster, more resource saving adaptations without major changes to the algorithm's inner workings or the overall cognitive radio.

This paper presents a method for improving the performance of Wireless Mesh Networks (WMN) through the use of multichannel wormhole switching. Current WMNs based on contention-based medium access control (MAC) such as ";WiFi"; suffer from high latency and low resource utilization because of competition for the shared single-channel medium. Through simulation we compare WMNs using contention-based wireless nodes versus WMNs using contention-free ";flit-relay"; wireless nodes. We demonstrate our ";flit-relay"; design as a promising low latency alternative to CSMA/CA for providing WMNs. The approximate 800-fold improvement in latency over WMNs using wireless nodes with a contention-based MAC and competitive setup times for VoIP support the argument for more development on pursuing this technology.

In profiling, a tradeoff exists between information and overhead. For example, hardware-sampling profilers incur negligible overhead, but the information they collect is consequently very coarse. Other profilers use instrumentation tools to gather temporal traces such as path profiles and hot memory streams, but they have high overhead. Runtime and feedback-directed compilation systems need detailed information to aggressively optimize, but the cost of gathering profiles can outweigh the benefits. Shadow profiling is a novel method for sampling long traces of instrumented code in parallel with normal execution, taking advantage of the trend of increasing numbers of cores. Each instrumented sample can be many millions of instructions in length. The primary goal is to incur negligible overhead, yet attain profile information that is nearly as accurate as a perfect profile. The profiler requires no modifications to the operating system or hardware, and is tunable to allow for greater coverage or lower overhead. We evaluate the performance and accuracy of this new profiling technique for two common types of instrumentation-based profiles: interprocedural path profiling and value profiling. Overall, profiles collected using the shadow profiling framework are 94% accurate versus perfect value profiles, while incurring less than 1% overhead. Consequently, this technique increases the viability of dynamic and continuous optimization systems by hiding the high overhead of instrumentation and enabling the online collection of many types of profiles that were previously too costly

Mainstream processor architectures and field programmable custom computing machines (FCCMs) are colliding towards a heterogeneous system on chip architecture. This is apparent from Intel and AMD efforts to create new chip architectures with various processing cores focusing on DSP, networking, and graphics. From the embedded processor research, system-on-chips connected by network on chips have allowed scalable architectures with a variety of processing cores connected by an onchip network. In this paper we examine several scheduling and allocation policies that can be utilized across network on chip architectures regardless of the processing cores onchip. By abstracting characteristics of the processing cores with various scheduling data structures, any heterogeneous system on a chip can be allocated and scheduled dynamically.

Network on Chips are becoming a common onchip interconnect for both FPGA and mainstream processor designs. At the same time, software defined radios (SDR) are a new application field that is gaining much attention. As SDR tasks are mapped onto Network on Chip architectures, the typically streaming nature of samples will stress the NoC itself and possibly hurt the performance of other applications using that NoC. In this paper, we present the results of our partitioning and placement of a SDR transmitter onto a NoC architecture using an FPGA. We use a 802.11a transmitter example partitioned across a NoC and compare it to a handcrafted design. Additionally, various placement schemes, runtime architecture loads and NoC access methods are examined to determine the feasibility of this application and architecture combination.

In recent years, several algorithms for controlling cognitive radio platforms have been proposed. In this paper, we review the existing approaches that have been developed for cognitive radio control algorithms and extract the common sensing and control requirements for those algorithms. We also briefly discuss the challenges of defining representative testing scenarios. We then synthesize our experience implementing cognitive radio control algorithms and extract a set of pragmatic issues challenging researchers in cognitive radios. We conclude with a set of open questions and problems and discuss implications for future research.

Multimedia requirements of the 1990's drove wired and optical network architects to reconsider the inefficiencies of packet switching and consider long proven methods such as circuit-switching to implement traffic engineering in order to reduce end-to-end delay. This resulted in the development of asynchronous transfer mode (ATM) and multi-protocol label switching (MPLS) technologies. Because both are mature and proven technologies for wired and optical network architectures, much research has been done to apply these methods to wireless mesh networks. But optimal performance improvement eludes wireless mesh network designers because of differences between the wired/optical and wireless environments in the provision of non-interfering unidirectional internodal links and lack of a wireless circuit switch. We propose a wireless mesh networking architecture that will provide low-latency and potentially higher throughput, based upon the availability of multiple channels, a circuit-switch implemented at the physical layer, and a reservation protocol that will assign channels to provide non-interfering unidirectional internodal links.

This work was motivated by a discussion that two of the coauthors (computer science professors) had with the other coauthor (a law professor and a former computer crime Trial Attorney at the U.S. Department of Justice), in which it was pointed out that some of the network measurements that the computer scientists were thinking of making might potentially violate Federal laws.

Deployments of wireless LANs consisting of hundreds of 802.11 access points with a large number of users have been reported in enterprises as well as college campuses. However, due to the unreliable nature of wireless links, users frequently encounter degraded performance and lack of coverage. This problem is even worse in unplanned networks, such as the numerous access points deployed by homeowners. Existing approaches that aim to diagnose these problems are inefficient because they troubleshoot at too high a level, and are unable to distinguish among the root causes of degradation. This paper designs, implements, and tests fine-grained detection algorithms that are capable of distinguishing between root causes of wireless anomalies at the depth of the physical layer. An important property that emerges from our system is that diagnostic observations are combined from multiple sources over multiple time instances for improved accuracy and efficiency.

For several years now, modern FPGAs have included onchip network related hard cores. These cores include Xilinx's RocketIO and Altera's RapidIO serial transceivers. However, to use these cores in a complete networking application may be a daunting task to a non-networking expert. In addition to the complicated use of these components, the high performance needs of modern networking applications require designs that are optimized for low latency and a moderately high clock rate. Therefore to meet these challenges, we present CUSP (Click Utilizing Speculation and Parallelism)for reconfigurable hardware platforms.Click is an accepted software network router framework that is similar to CUSP, but specifically built for a Linux platform and software network routers. CUSP, while also having a modular design of reusable components, additionally provides automated speculation and parallelism to gain better performance on FPGAs. An accompanying scripting language allows quick creation of these routers from a body of existing components. We have implemented an example network application through the CUSP design flow and its performance will be compared against alternative network design methods.

Simultaneous multithreading (SMT) seeks to improve the computation throughput of a processor core by sharing primary resources such as functional units, issue bandwidth, and caches. SMT designs increase utilization and generally improve overall throughput, but the amount of improvement is highly dependent on competition for shared resources between the scheduled threads. This variability has implications that relate to operating system scheduling, simulation techniques, and fairness. Although these techniques recognize the implications of thread interaction, they do little to profile and predict this interaction. The modeling approach presented in this paper uses data collected from performance counters on two different hardware implementations of Pentium-4 hyper-threading processors to demonstrate the effects of thread interaction. Techniques are described for fitting linear regression models and recursive partitioning to use the counters to make online predictions of performance (expressed as instructions per cycle); these predictions can be used by the operating system to guide scheduling decisions. A detailed analysis of the effectiveness of each of these techniques is presented.

Many companies, organizations and communities are providing wireless hotspots that provide networking access using 802.11b wireless networks. Since wireless networks are more sensitive to variations in bandwidth and environmental interference than wired networks, most networks support a number of transmission rates that have different error and bandwidth properties. Access points can communicate with multiple clients running at different rates, but this leads to unfair bandwidth allocation. If an access point communicates with a mix of clients using both 1 mb/s and 11 mb/s transmission rates, the faster clients are effectively throttled to 1 mb/s as well. This happens because the 802.11 MAC protocol approximate "station fairness", with each station given an equal chance to access the media. We provide a solution to provide "rate proportional fairness", where the 11 mb/s stations receive more bandwidth than the 1 mb/s stations. Unlike previous solutions to this problem, our mechanism is easy to implement, works with common operating systems and requires no change to the MAC protocol or the stations.

Inexpensive analog phase array antennas are on the verge of becoming widely available. These versatile antennas are capable of very rapidly altering their gain pattern to form complex patterns. However, it is not immediately obvious how to best exploit their capabilities. Previous research has shown that problems arise when using the stock 802.11 MAC protocol with directional antennas, and new MAC protocols have been designed to address these issues as well as exploit some of their new capabilities. Unfortunately moving to a new MAC layer means abandoning a wealth of inexpensive 802.11 wireless equipment since these cards are not very amenable to such extensive modification. In this work, we propose, implement, and evaluate a scheme which uses the flexible gain pattern formation ability of a phase array antenna to exploit the enhanced spatial diversity potential of directional transmission in a community networking environment while still functioning with the existing 802.11 MAC.

Article Share on Anonymous Usage of Location-Based Services Through Spatial and Temporal Cloaking Authors: Marco Gruteser View Profile , Dirk Grunwald View Profile Authors Info & Claims MobiSys '03: Proceedings of the 1st international conference on Mobile systems, applications and servicesMay 2003Pages 31–42https://doi.org/10.1145/1066116.1189037Published:05 May 2003Publication History 1,618citation6,645DownloadsMetricsTotal Citations1,618Total Downloads6,645Last 12 Months247Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Although central processor speeds continues to improve, improvements in overall system performance are increasingly hampered by memory latency, especially for pointer-intensive applications. To counter this loss of performance, numerous data and instruction prefetch mechanisms have been proposed. Recently, several proposals have posited a memory-side prefetcher; typically, these prefetchers involve a distinct processor that executes a program slice that would effectively prefetch data needed by the primary program. Alternative designs embody large state tables that learn the miss reference behavior of the processor and attempt to prefetch likely misses.This paper proposes Content-Directed Data Prefetching, a data prefetching architecture that exploits the memory allocation used by operating systems and runtime systems to improve the performance of pointer-intensive applications constructed using modern language systems. This technique is modeled after conservative garbage collection, and prefetches "likely" virtual addresses observed in memory references. This prefetching mechanism uses the underlying data of the application, and provides an 11.3% speedup using no additional processor state. By adding less than ½% space overhead to the second level cache, performance can be further increased to 12.6% across a range of "real world" applications.

Simultaneous multithreading seeks to improve the aggregate computation bandwidth of a processor core by sharing resources such as functional units, caches, TLB and so on. To date, most research investigating the scheduling of these shared resources has focused on enhancing computational bandwidth. In this paper, we examine scheduling fairness. First, we show that a thread running on an implementation of a SMT processor can suffer from "denial of service" by a malicious thread, slowing down the original thread by a factor of 10-20. Using performance counter hardware, we show that the slowdown occurs because of deliberate misuse of shared resources and design decisions that are necessary for high speed implementation. We then propose and evaluate a number of mechanisms to counter such malicious behavior: some affect the core scheduling algorithm and others simply attempt to identify activity that would affect threads sharing the same processor core. We find that harmful activity based mechanisms outperform core scheduling mechanisms. In addition, we show that they can be designed so that they can differentiate between malicious attacks and legitimate activities that may also make use of the same harmful activities.

Ad hoc network protocols are often developed, tested and evaluated using simulators. However, when the time comes to deploy those protocols for use or testing on real systems the protocol must be reimplemented for the target platform. This usually results in two, completely separate code-bases that must be maintained. Bugs which are found and fixed under simulated conditions must also be fixed separately in the deployed implementation, and vice versa. There is ample opportunity for the two implementations to drift apart, possibly to the point where the deployed and simulated version have little actual resemblance to each other. Testing the deployed version may also require construction of a testbed, a potentially time-consuming and expensive endeavor. Even if constructing an actual testbed is feasible, simulators are very useful for running large, repeatable scenarios for tasks such as protocol evaluation and regression testing. Furthermore, since the implementation may require modification of the kernel network stack, there's a good chance that a particular implementation may only run on specific versions of specific operating systems. To address these issues, we constructed the nsclick simulation environment by embedding the Click Modular Router inside of the popular \ns~network simulator. Routing protocols may be implemented as Click graphs and easily moved between simulation and any operating system supported by Click. This paper describes the design, use, validation and performance of nsclick.

The declining costs of commodity disk drives is rapidly changing the economics of deploying large amounts of online or near-line storage. Conventional mass storage systems use either high performance RAID clusters, automated tape libraries or a combination of tape and disk. In this paper, we analyze an alternative design using massive arrays of idle disks, or MAID. We argue that this storage organization provides storage densities matching or exceeding those of tape libraries with performance similar to disk arrays. Moreover, we show that with effective power management of individual drives, this performance can be achieved using a very small power budget. In particular, we show that our power management strategy can result in the performance comparable to an always-on RAID system while using 1/15th the power of such a RAID system.

In this paper, we examine the energy consumption of a state-of-the-art pocket computer. Using a data acquisition system, we measure the energy consumption of the Itsy Pocket Computer, developed by Compaq Computer Corporation's Palo Alto Research Labs. We begin by showing that the energy usage characteristics of the Itsy differ markedly from that of a notebook computer. Then, since we expect that flexible software environments will become increasingly prevalent on pocket computers, we consider applications running in a Java environment. In particular, we explain some of the Java design tradeoffs applicable to pocket computers, and quantify their energy costs. For the design options we considered and the three workloads we studied, we find a maximum change in energy use of 25%.

Branch mispredictions can have a major performance impact on high-performance processors. Multipath execution has recently been introduced to help limit the misprediction penalties incurred by branches that are difficult to predict. This paper presents efficient instruction fetch architecture designs for these multipath processor execution cores. We evaluate a number of design trade-offs for the first-level instruction cache and the multipath PC fetch arbiter. Furthermore we evaluate the effect of additional bandwidth limitations imposed by the processor frontend pipeline. Our results show that instruction fetch support for efficient multipath execution can be achieved with realizable hardware implementations. In addition, we show that the best performing instruction fetch designs for multipath execution and multithreaded processors are likely to differ, since both designs optimize the processor for different performance goals (minimal execution time vs maximal throughput).

Prefetching is one approach to reducing the latency of memory operations in modern computer systems. In this paper, we describe the Markov prefetcher. This prefetcher acts as an interface between the on-chip and off-chip cache and can be added to existing computer designs. The Markov prefetcher is distinguished by prefetching multiple reference predictions from the memory subsystem, and then prioritizing the delivery of those references to the processor. This design results in a prefetching system that provides good coverage, is accurate, and produces timely results that can be effectively used by the processor. We also explored a range of techniques that can be used to reduce the bandwidth demands of prefetching, leading to improved memory system performance. In our cycle-level simulations, the Markov Prefetcher reduces the overall execution stalls due to instruction and data memory operations by an average of 54 percent for various commercial benchmarks while only using two-thirds the memory of a demand-fetch cache organization.

Abstract Barrier synchronizations can be very expensive on multiprogramming environment because no process can go past a barrier until all the processes have arrived. If a process participating at a barrier is swapped out by the operating system, the rest of participating processes end up waiting for the swapped-out process. This paper presents a compile-time/run-time system that uses a dependence-driven execution to overlap the execution of computations separated by barriers so that the processes do not spend most of the time idling at the synchronization point. Keywords: Run-time systems, multiprogramming, loop scheduling, dependence-driven execution, barrier synchronization, coarse-grain dataflow. The parallel execution of a sequence of loop nests is typically broken into phases, each phase consisting of a simple loop separated by a barrier synchronization to ensure that the execution respects

Modern processors improve instruction level parallelism by speculation. The outcome of data and control decisions is predicted, and the operations are speculatively executed and only committed if the original predictions were correct. There are a number of other ways that processor resources could be used, such as threading or eager execution. As the use of speculation increases, we believe more processors will need some form of speculation control to balance the benefits of speculation against other possible activities. Confidence estimation is one technique that can be exploited by architects for speculation control. In this paper, we introduce performance metrics to compare confidence estimation mechanisms, and argue that these metrics are appropriate for speculation control. We compare a number of confidence estimation mechanisms, focusing on mechanisms that have a small implementation cost and gain benefit by exploiting characteristics of branch predictors, such as clustering of mispredicted branches. We compare the performance of the different confidence estimation methods using detailed pipeline simulations. Using these simulations, we show how to improve some confidence estimators, providing better insight for future investigations comparing and applying confidence estimators.

Control-flow misprediction penalties are a major impediment to high performance in wide-issue superscalar processors. In this paper we present Selective Eager Execution (SEE), an execution model to overcome mis-speculation penalties by executing both paths after diffident branches. We present the micro-architecture of the PolyPath processor which is an extension of an aggressive superscalar out-of-order architecture. The PolyPath architecture uses a novel instruction tagging and register renaming mechanism to execute instructions from multiple paths simultaneously in the same processor pipeline, while retaining maximum resource availability for single-path code sequences. Results of our execution-driven, pipeline-level simulations show that SEE can improve performance by as much as 36% for the go benchmark, and an average of 14% on SPECint95, when compared to a normal superscalar, out-of-order speculative execution, monopath processor. Moreover our architectural model is both elegant and practical to implement, using a small amount of additional state and control logic.

Branch prediction has enabled microprocessors to increase instruction level parallelism (ILP) by allowing programs to speculatively execute beyond control boundaries. Although speculative execution is essential for increasing the instructions per cycle (IPC), it does come at a cost. A large amount of unnecessary work results from wrong-path instructions entering the pipeline due to branch misprediction. Results generated with the SimpleScalar tool set using a 4-way issue pipeline and various branch predictors show an instruction overhead of 16% to 105% for event instruction committed. The instruction overhead will increase in the future as processors use more aggressive speculation and wider issue widths. In this paper we present an innovative method for power reduction ,which, unlike previous work that sacrificed flexibility or performance reduces power in high-performance microprocessors without impacting performance. In particular we introduce a hardware mechanism called pipeline gating to control rampant speculation in the pipeline. We present inexpensive mechanisms for determining when a branch is likely to mispredict, and for stopping wrong-path instructions from entering the pipeline. Results show up to a 38% reduction in wrong-path instructions with a negligible performance loss (/spl ap/1%). Best of all, even in programs with a high branch prediction accuracy, performance does not noticeable degrade. Our analysis indicates that there is little risk in implementing this method in existing processors since it does not impact performance and can benefit energy reduction.

Binary Decision Diagrams (BDDs) are efficient at manipulating large sets in a compact manner. BDDs, however, are inefficient at utilizing the memory hierarchy ofthe computer. Recent work addresses this problem by manipulating the BDDsin breath-first manner (BFS). BFS processing is quite successful at reducing the number of page faults when the BDDs do not fit in the available physical memory. When pagingdoes not take place, it is much less clear which paradigmleads to the better performance. In this paper, we perform adetailed analysis of BFS and DFS packages using simulationand direct performance monitoring ofthe memory hierarchy.We show that there is very little difference in TLB and cachemiss rates for DFS and BFS paradigms. We also show thatdifferences in execution time between carefully tuned BFSand DFS implementations are primarily a function of thelossless computed table used in BFS implementations, andnot a function of memory locality. Furthermore, we presentimplementation changes to the the Cudd package that canimprove execution times by asmuch as 26% when the problem fits in main memory, and a factor of six when paging is involved.

Prefetching is one approach to reducing the latency of memory operations in modern computer systems. In this paper, we describe the Markov prefetcher. This prefetcher acts as an interface between the on-chip and off-chip cache, and can be added to existing computer designs. The Markov prefetcher is distinguished by prefetching multiple reference predictions from the memory subsystem, and then prioritizing the delivery of those references to the processor.This design results in a prefetching system that provides good coverage, is accurate and produces timely results that can be effectively used by the processor. In our cycle-level simulations, the Markov Prefetcher reduces the overall execution stalls due to instruction and data memory operations by an average of 54% for various commercial benchmarks while only using two thirds the memory of a demand-fetch cache organization.

The order in which loop iterations are executed can have a large impact on the number of cache misses that an applications takes. A new loop order that preserves the semantics of the old order but has a better cache data re-use, improves the performance of that application. Several compiler techniques exist to transform loops such that the order of iterations reduces cache misses. This paper introduces a run-time method to determine the order based on a dependence-driven execution. In a dependence-driven execution, an execution traverses the iteration space by following the dependence arcs between the iterations.

Enterprise level web proxies relay world-wide web traffic between private networks and the Internet. They improve security, save network bandwidth, and reduce network latency. While the performance of web proxies has been analyzed based on synthetic workloads, little is known about their performance on real workloads. In this paper we present a study of two web proxies (CERN and Squid) executing real workloads on Digital's Palo Alto Gateway. We demonstrate that the simple CERN proxy architecture outperforms all but the latest version of Squid and continues to outperform cacheless configurations. For the measured load levels the Squid proxy used at least as many CPU, memory, and disk resources as CERN, in some configurations significantly more resources. At higher load levels the resource utilization requirements will cross and Squid will be the one using fewer resources. Lastly we found that cache hit rates of around 30% had very little effect on the requests service time.

Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this article, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch prediction evidence-based static prediction , or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this article, we use neural networks and decision trees to map static features associated with each branch to a prediction that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique; it is effective across a range of programming languages and programming styles; and it does not rely on the use of expert-defined heuristics. In this article, we describe the application of ESP to the problem of static branch prediction and compare our results to existing program-based branch predictors. We also investigate the applicability of ESP across computer architectures, programming languages, compilers, and run-time systems. We provide results showing how sensitive ESP is to the number and type of static features and programs included in the ESP training sets, and we compare the efficacy of static branch prediction for subroutine libraries. Averaging over a body of 43 C and Fortran programs, ESP branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.

Modern languages and operating systems often encourage programmers to use threads, or independent control streams, to mask the overhead of some operations and simplify program structure. Multitasking operating systems use threads to mask communication latency, either with hardwares devices or users. Client-server applications typically use threads to simplify the complex control-flow that arises when multiple clients are used. Recently, the scientific computing community has started using threads to mask network communication latency in massively parallel architectures, allowing computation and communication to be overlapped. Lastly, some architectures implement threads in hardware, using those threads to tolerate memory latency.In general, it would be desirable if threaded programs could be written to expose the largest degree of parallelism possible, or to simplify the program design. However, threads incur time and space overheads, and programmers often compromise simple designs for performance. In this paper, we show how to reduce time and space thread overhead using control flow and register liveness information inferred after compilation. Our techniques work on binaries, are not specific to a particular compiler or thread library and reduce the the overall execution time of fine-grain threaded programs by ≈ 15-30%. We use execution-driven analysis and an instrumented operating system to show why the execution time is reduced and to indicate areas for future work.

In this paper we propose a cache design that provides the same miss rate as a two-way set associative cache, but with an access time closer to a direct-mapped cache. As with other designs, a traditional direct-mapped cache is conceptually partitioned into multiple banks, and the blocks in each set are probed, or examined, sequentially. Other designs either probe the set in a fixed order or add extra delay in the access path for all accesses. We use prediction sources to guide the cache examination, reducing the amount of searching and thus the average access latency. A variety of accurate prediction sources are considered, with some being available in early pipeline stages. We feel that our design offers the same or better performance and is easier to implement than previous designs.

Accurate instruction fetch and branch prediction is increasingly important on today's wide-issue architectures. Fetch prediction is the process of determining the next instruction to request from the memory subsystem. Branch prediction is the process of predicting the likely out-come of branch instructions. Several researchers have proposed very effective fetch and branch prediction mechanisms including branch target buffers (BTB) that store the target addresses of taken branches. An alternative approach fetches the instruction following a branch by using an index into the cache instead of a branch target address. We call such an index a next cache line and set (NLS) predictor. A NLS predictor is a pointer into the instruction cache, indicating the target instruction of a branch.In this paper we examine the use of NLS predictors for efficient and accurate fetch and branch prediction. Previous studies associated each NLS predictor with a cache line and provided only one-bit conditional branch predictors. Our study examines the use of NLS predictors with highly accurate two-level correlated conditional branch architectures. We examine the performance of decoupling the NLS predictors from the cache line and storing them in a separate tag-less memory buffer. Our results show that the decoupled architecture performs better than associating the NLS predictors with the cache line, that the NLS architecture benefits from reduced cache miss rates, and it is particularly effective for programs containing many branches. We also provide an in-depth comparison between the NLS and BTB architectures, showing that the NLS architecture is a competitive alternative to the BTB design.

Current trends in processor design are pointing to deeper and wider pipelines and superscalar architectures. The efficient use of these resources requires speculative execution, a technique whereby the processor continues executing the predicted path of a branch before the branch condition is resolved.In this paper, we investigate the implications of speculative execution on instruction cache performance. We explore policies for managing instruction cache misses ranging from aggressive policies (always fetch on the speculative path) to conservative ones (wait until branches are resolved). We test these policies and their interaction with next-line prefetching by simulating the effects on instruction caches with varying architectural parameters. Our results suggest that an aggressive policy combined with next-line prefetching is best for small latencies while more conservative policies are preferable for large latencies.

Accurate instruction fetch and branch prediction is increasingly important on today's wide-issue architectures. Fetch prediction is the process of determining the next instruction to request from the memory subsystem. Branch prediction is the process of predicting the likely outcome of branch instructions. Many branch and fetch prediction architectures have been proposed, from simple static techniques to more sophisticated hardware designs. All these previous studies compare differing branch prediction architectures in terms of misprediction rates, branch penalties, or an idealized cycles per instruction. This paper provides a system-level performance comparison of several branch architectures using a full pipeline-level architectural simulator. The performance of various branch architectures is reported using execution time and cycles-per-instruction. For the programs we measured, our simulations show that having no branch prediction increases the execution time by 27%. By comparison, a highly accurate 512 entry branch target buffer architecture has an increased execution time of 1.5% when compared to an architecture with perfect branch prediction. We also show that the most commonly used branch performance metrics, branch misprediction rates and the branch execution penalty are highly correlated with program performance and are suitable metrics for architectural studies.

Profile-based optimizations are being used with increasing frequency. Profile information can be used to improve instruction scheduling, code layout, and to increase instruction level parallelism. These optimizations have been shown to be effective when they are applied to the same program from which the profile was gathered. However it is an open question how profile-based optimizations should be applied to library subroutines. If many programs use libraries in the same way, it may be possible to "preoptimize" a library or to use an optimized shared library. This study examines the use of commonly used libraries among 43 C and FORTRAN programs to see if the libraries have common behavior across different programs. We examine the behavior of the most commonly used Unix libraries on Digital Unix. We found that libraries have very predictable behavior between applications. This implies that profile-based compiler optimizations may be effective far libraries across different applications. Therefore, one can use profile optimizations on shared and non-shared libraries before they are shipped, allowing a program using those libraries to take advantage of profile-based optimizations without having to gather any profiles. All results in this study are shown using branch misprediction rates. We feel this metric indicates the likelihood that programs have similar behavior and allows comparison to earlier branch prediction studies.

Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this paper, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch prediction, evidence-based static prediction, or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this paper, we use a neural network to map static features associated with each branch to the probability that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique, it is effective across a range of programming languages and programming styles, and it does not rely on the use of expert-defined heuristics.

Several researchers have proposed algorithms for basic block reordering. We call these branch alignment algorithms. The primary emphasis of these algorithms has been on improving instruction cache locality, and the few studies concerned with branch prediction reported small or minimal improvements. As wide-issue architectures become increasingly popular the importance of reducing branch costs will increase, and branch alignment is one mechanism which can effectively reduce these costs.

Accurate branch prediction is critical to performance; mispredicted branches mean that ten's of cycles may be wasted in superscalar architectures. Architectures combining very effective branch prediction mechanisms coupled with modified branch target buffers (BTB's) have been proposed for wide-issue processors. These mechanisms require considerable processor resources. Concurrently, the larger address space of 64-bit architectures introduce new obstacles and opportunities. A larger address space means branch target buffers become more expensive. The authors show how a combination of less expensive mechanisms can achieve better performance than BTB's. This combination relies on a number of design choices described in the paper. They used trace-driven simulation to show that their proposed design, which uses fewer resources, offers better performance than previously proposed alternatives for most programs, and indicate how to further improve this design.>

Modern computer architectures increasingly depend on mechanisms that estimate future control flow decisions to increase performance. Mechanisms such as speculative execution and prefetching are becoming standard architectural mechanisms that rely on control flow prediction to prefetch and speculatively execute future instructions. At the same time, computer programmers are increasingly turning to object-oriented languages to increase their productivity. These languages commonly use run time dispatching to implement object polymorphism. Dispatching is usually implemented using an indirect function call, which presents challenges to existing control flow prediction techniques.

The allocation and disposal of memory is a ubiquitous operation in most programs. Rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. This paper presents a performance evaluation of the reference locality of dynamic storage allocation algorithms based on trace-driven simualtion of five large allocation-intensive C programs. In this paper, we show how the design of a memory allocator can significantly affect the reference locality for various applications. Our measurements show that poor locality in sequential-fit allocation algorithms reduces program performance, both by increasing paging and cache miss rates. While increased paging can be debilitating on any architecture, cache misses rates are also important for modern computer architectures. We show that algorithms attempting to be space-efficient by coalescing adjacent free objects show poor reference locality, possibly negating the benefits of space efficiency. At the other extreme, algorithms can expend considerable effort to increase reference locality yet gain little in total execution performance. Our measurements suggest an allocator design that is both very fast and has good locality of reference.

We present a solution to the reaching definitions problem for programs with explicit lexically specified parallel constructs, such as cobegin/coend or parallel_sections, both with and without explicit synchronization operations, such as Post, Wait or Advance. The reaching definitions information for sequential programs is used to solve many standard optimization problems. In parallel programs, this information can also be used to explicitly direct communication and data ownership. Although work has been done on analyzing parallel programs to detect data races, little work has been done on optimizing such programs.

Abstract The allocation and disposal of memory is a ubiquitous operation in most programs. Rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. Yet, in some applications, programmers use domain‐specific knowledge in an attempt to improve the speed or memory utilization of memory allocators. In this paper, we describe a program (CustoMalloc) that synthesizes a memory allocator customized for a specific application. Our experiments show that the synthesized allocators are uniformly faster and more space efficient than the Berkeley UNIX allocator. Constructing a custom allocator requires little programmer effort, usually taking only a few minutes. Experience has shown that the synthesized allocators are not overly sensitive to properties of input sets and the resulting allocators are superior even to domain‐specific allocators designed by programmers. Measurements show that synthesized allocators are from two to ten times faster than widely‐used allocators.

A method is presented that realizes a kind of interconnection network, called a hyperswitch network, that is achieved using a mixture of static and dynamic topologies. Available of fault-free paths need not be specified by a source because the routing header can be modified in response to congestion or faults encountered as a path is established. This method can be accomplished in a static topology such as the hypercube network if the nodes have switching elements which are capable of dynamically performing the necessary routing header revisions. Detailed simulation results show that the hyperswitch network is consistently more efficient than fixed-path routing for large message traffic conditions. The simulation results also show that the hyperswitch network has equivalent latency overhead for messages with localized and antilocal destinations (i.e., less than a 25% difference between diameter 1 and 5).>