Teaching assistants (TAs) play a critical role in computing and HCI education, yet little is known about how they perceive and use AI tools or imagine their future pedagogical uses. We report on a series of design workshops with 131 computing (CS) TAs across two U.S. universities. These workshops invited TAs to reflect on current AI use and envision future AI-enhanced tools and practices. Drawing on surveys and design artifacts, we (1) develop a cross-institutional typology of situated TA uses of AI, revealing opportunities and tensions; (2) show how TAs’ visions of AI are shaped by disciplinary norms, institutional structures, and their intermediary position as student-instructors; and (3) reveal ethical dilemmas. Our findings contribute to HCI by positioning TAs as AI-supported knowledge workers in the education domain; illustrating how design and speculation are shaped by people’s situated understandings of AI and their institutional contexts; and identifying a core tension in which TAs simultaneously preserve and erode the human dimensions of their work, with implications for future instructional tools and human–AI collaboration.

Ethics instruction, as required for ABET-accreditation and recommended by the ACM/IEEE-CS/AAAI curricular guidelines, is an important element of the undergraduate computer science (CS) curriculum. Recent papers which analyze the proportion of programs offering CS ethics education focus on specific types of programs, such as top-ranked programs, programs at R1 institutions under the Carnegie Classification, and/or ABET-accredited programs. This leaves out a large portion of CS programs which may fall under none of those categories including many small colleges. In this paper, we analyze a true random sample of all 4-year Bachelor's, Public or Private Not-For-Profit CS programs in the U.S. to assess the extent to which the previous data holds true across the full spectrum of U.S. colleges and universities. Using a systematic approach, we look at which CS programs require CS ethics instruction, whether as a standalone course or integrated into other courses. In addition, we break down the data by categorization to replicate previous studies and place our data in conversation with those. We found 55% of all U.S. CS programs require CS ethics in some capacity. Additionally, we found ABET-accreditation and Carnegie research classification to be a major driver toward programs requiring ethics instruction in the U.S.

Teaching assistants (TAs) play an increasingly vital role in computer science (CS) education, particularly amid rising enrollments, expanding instructional modalities, and the emergence of generative AI tools. In this evolving landscape, CS TAs are taking on greater responsibilities and often serve as the primary point of personal interaction for students, particularly through recitations, lab sessions, and office hours. However, many CS TAs receive limited preparation in inclusive and responsive teaching practices, limiting their ability to effectively support students from diverse cultural and educational backgrounds. To address this gap, we developed and delivered a series of responsive pedagogy workshops at two diverse institutions. These workshops aimed to deepen CS TAs' understanding of inclusive and responsive teaching strategies, support their implementation in practice, and create space for co-design by positioning TAs not only as learners, but as partners in imagining how responsive pedagogy principles could be more effectively integrated into the courses and contexts in which they teach. In this experience report, we describe the design and implementation of these workshops with 117 TA participants, share workshop materials for broader adoption, and reflect on key findings related to integrating responsive pedagogy into CS education through TA training.

Over my 30+ year career, I have dabbled in network measurement and modeling. In this talk I will trace selected efforts over time and connect them to broader lessons I have learned about how to have impact. I will attempt to connect with the larger research and funding ecosystem for networking in general and measurement in particular. I will close with a grand challenge.

Video conferencing applications (VCAs) are a vital tool for business, education, and other important purposes. However, VCAs are vulnerable to network latency, which can cause issues in client interactivity, such as increased overlaps, longer silence durations, and a degradation of the turn-taking structure. In this paper, we propose two systems for improving VCA interactivity in the presence of high network latency: one based on adjustment of the latency between pairs of clients, and the other based on notifying clients of their high latency. Both systems are suitable for deployment within the VCA selective forwarding unit, the central server for the conference. We evaluate the systems using a client behavioral model with accompanying interactivity metrics, and show, among other results, improvements of up to $50 \%$ in the overlap rate and $40 \%$ in useful conversation time, as well as restoration of the turn taking structure to the state with no network latency.

Computing ethics instruction is a vital aspect of the undergraduate computing curriculum. It has received greater focus in recent years driven in part by concerns about the societal impacts of computing technologies such as social media and artificial intelligence. The increased attention provides an opportunity, even an imperative, to examine and rethink common practices. To support our understanding of current practices in computing ethics education, we surveyed 318 computing educators in the United States (U.S.), including 56 who have never taught ethics. The survey included questions about ethics teaching methods and challenges the instructors confronted. We show that ethical frameworks are frequently taught yet teaching them is regarded as one of the least important learning outcomes, and that respondents largely do not consider author demographics when selecting readings for their ethics classes, which could limit the diversity in perspectives present in the course. We conclude with recommendations for improving teaching methods, materials selection, and deployment strategies in computing ethics education, and discuss their implications for promoting more inclusive computing ethics education curricula in the U.S.

Recently, there has been a growing interest in the role of teaching assistants (TAs) in computer science (CS). This interest is due to the vital role CS TAs play in supporting student learning and their expanding responsibilities driven by growing enrollments in CS programs worldwide. While much of this research focuses on the technical and pedagogical aspects of CS TAs' duties, researchers recognize the need to further explore the unique value human CS TAs provide, particularly with the rise of AI tools and assistants. In this paper, we use qualitative methods to analyze 109 survey responses collected across two different institutions in the United States as part of a larger design-based research project to make two contributions. First, we illustrate how CS TAs adopt humanistic stances and demonstrate care in their roles, thereby expanding prevailing understandings of CS TAs. Second, we detail similarities and differences across CS TAs' experiences at each institution that underscore the importance of understanding CS TAs as they are situated in different institutional contexts. We conclude by discussing implications of this work for computing instruction and TA training, emphasizing the importance of foregrounding the roles and values brought by TAs.

Local workers and their knowledge are essential for sustainable and effective conservation efforts. However, many technology-assisted conservation programs are guided by global benchmarks (e.g., forest cover) and industry metrics (e.g., cost per acre), which often devalue local knowledge and fail to consider the economic and conservation goals of local workers. Assets-based design is well-suited to center workers and their strengths, yet it may fail to fully address the complexities of long-term conservation programs by not explicitly emphasizing workers' goals or bolstering their assets. We extend recent approaches in assets-based design literature that address these limitations through our case studies of reforestation, biodiversity monitoring, and carbon sequestration programs in three protected areas in Madagascar. We leverage a mixed-methods approach of direct reactive observations, unstructured interviews, and an informal design workshop, revealing emergent themes surrounding economic sustainability and the value of local ecological knowledge in conservation. Finally, we explore examples, tensions, and design considerations for worker-centered conservation technology to: (1) prioritize local knowledge, (2) foster love of nature, (3) center economic goals, and (4) embrace local autonomy. This work advances the dialogue on assets-based design, promoting the co-creation of equitable and sustainable conservation technologies with workers in Global South settings by centering local economic priorities and enhancing workers' strengths.

Video conferencing applications (VCAs) have become an indispensable tool for business, educational, and personal communications. There is, therefore, considerable interest in understanding and measuring the Quality of Experience (QoE) delivered by VCAs to their users. Video quality, one QoE measure, has received considerable attention in the literature. In this paper, we are concerned with another important aspect of VCA QoE, namely interactivity. We define this informally as the ability of a VCA to facilitate satisfying interaction among its users. Interactivity is primarily impacted by the media transmission latency among users which is, in turn, a function of network and application processing delays. Our goal in this work is to address two challenges in investigating interactivity-related QoE in VCAs. First, we propose a suite of meaningful quantifiable interactivity metrics, such as the proportion of silence time and rate of overlapping speech, that correlate well with conversational impairments and, hence, QoE perceptions. Second, we investigate scalable approaches for measuring these metrics. We develop a validated model for user behavior that enables realistic simulation of interactivity in VCA sessions. We also briefly consider an approach to measure interactivity metrics from packet traces. Through a set of experimental results, we demonstrate how our evaluation methodology provides a way for researchers, VCA service providers and network operators to perform large-scale investigations of how latency can interfere with user interactivity and impact VCA QoE.

Computing Ethics (CE) courses are an increasingly important component of the undergraduate computing curriculum because of the outsized influence of computing on society. CE encompasses topics from multiple disciplines including the humanities; however, it is typically taught by educators within a Computer Science (CS) department in most undergraduate institutions in the United States, potentially leading to a less than comprehensive CE education for students. We surveyed 318 computing educators in US higher education to investigate CS educators' perceptions of how CE topics should ideally be taught. Most of our respondents thought that CE should be taught by a multidisciplinary team of instructors, and further that it should be taught both as a standalone course and embedded in other courses. Our research provides insights into ways to improve CE education that result in a better student experience.

Computing ethics courses are generally considered essential in undergraduate programs, but there is limited research on the importance of their inclusion at the master's level. In this study, we extend research conducted by Dexter et al. in 2013 about the importance of ethics in master's programs. We surveyed Associate Chairs and Associate Deans of Graduate Studies representing 81 different computing programs in the United States. 72% of respondents shared that ethics should be required in master's computing programs. In contrast, only 46% of the 81 programs surveyed require any type of ethics course at the master's level. Our findings also uncover barriers to the inclusion of ethics at the master's level and propose strategies for alleviating these challenges.

In 2011, the United Nations declared Internet access to be a basic human right. Achieving universal Internet access has been a longstanding goal of governments around the world. In the United States (US), provision depends primarily on decisions made by Internet Service Providers (ISPs) driven essentially by commercial market concerns. To encourage deployment in underserved regions, the US federal government has recently allocated unprecedented funding, with distributions guided by the information in broadband maps, spatial representations of current Internet access and quality published by the Federal Communication Commission. Yet, these maps are known to be inaccurate, especially for populations that are marginalized, such as tribal and rural residents. We are interested in the collaborative and contentious efforts to repair the data contained in broadband maps, and particularly by the efforts of citizen groups and local government to counter claims made by ISPs. In this paper, we study these efforts via interviews of 14 individuals involved in various local and regional roles, in policy, IT, advocacy, and research. We draw upon frameworks of repair and of data activism to ask who does this work and why; what tangible and intangible tools are brought to bear; and how the structural context simultaneously empowers and burdens repair workers. In doing so, we make three contributions: (i) we critique the process and system for broadband map repair for the burdens it places on historically marginalized groups to demonstrate how they have been left out of expansion and how their experiences are otherwise silent in official records; (ii) we bring together analytical concepts from repair and data arenas to examine repair work that is substantially shaped by socio, political, and economic context; and (iii) we illustrate how viewing broadband data workers as activists reveals the inadequacy of current tools and the opportunity for better support for their long-term, contextualized, and mediated efforts.

The HCI research community has long centered ethics in HCI research and practice. This interest has persisted as scholars highlight the need for more situated understandings and deeper integration of ethics into HCI. In parallel, HCI scholars and students have become increasingly involved in teaching computing ethics across many different university contexts, bringing in valuable perspectives informed by the connections between HCI and the socio-technical subject matter of computing ethics. Yet explicitly bringing these two threads together – examining the teaching of ethics through an HCI research lens – remains nascent. This paper integrates work in HCI and computing education to focus on the role and experience of computing ethics teaching assistants (CETAs), who are increasingly involved in ethics instruction and whose perspectives are predominantly missing in existing literature spanning HCI and computing education. Drawing on HCI theories and methods, our qualitative study of eleven CETAs at two American universities makes three contributions to the HCI literature. First, we build an understanding of who these TAs are with respect to the unique position of teaching computing ethics. Second, we characterize how CETAs’ teaching and learning is situated and shaped within different communities and institutional contexts. Finally, we suggest several implications for the design of ethics instruction within undergraduate computing programs. More broadly, our work can be viewed as a call to action, encouraging HCI scholars to play a more significant role in studying and designing the teaching and learning of computing ethics.

For decades, determining how to teach computing ethics effectively to undergraduate students has been a major concern. As more universities integrate computing ethics into their curriculum, or seek to further refine existing content, who is involved in teaching computing ethics has come to include both graduate and undergraduate teaching assistants (TAs). However, the role of TAs in ethics education is not well-understood, nor are the responsibilities, challenges, and support needs that might distinguish Computing Ethics TAs (CETAs) from their peers in technical computing courses. This paper addresses this gap in two ways, drawing on qualitative and design research methods. First, by interviewing CETAs and their supervising faculty at two universities, we identified common motivations, struggles, and goals among CETAs. Second, drawing on this data, we developed and piloted a cross-institutional support network for CETAs on the messaging platform Discord. Despite challenges in the deployment of the server, our results indicate that cross-institutional online communities have the potential to assist CETAs in professional development, in expanding perspectives, and in strategies for dealing with difficult topics. Furthermore, our platform can be retooled for future use within and between computing ethics courses. We hope that our research will contribute to fostering community and support for CETAs as part of improving computing ethics curriculum writ large.

Disruption to routines is an increasingly common part of everyday life. With the roots of some disruptions in the interconnectedness of the world and environmental and socio-political instability, there is good reason to believe that conditions that cause widespread disruption will persist. Individuals, communities, and systems are thus challenged to engage in resilience practices to deal with both acute and chronic disruption. Our interest is in chronic, everyday resilience, and the role of both technology and non-technical adaptation practices engaged by individuals and communities, with a specific focus on practices centered in nature. Foregrounding nature's role allows close examination of environmental adversity and nature as part of adaptivity. We add to the CSCW and HCI literature on resilience by examining long-distance hikers, for whom both the sources of adversity and the mitigating resilience processes cut across the social, the technical, and the environmental. In interviews with 12 long-distance hikers we find resilience practices that draw upon technology, writ large, and nature in novel assemblages, and leverage fluid configurations of the individual and the community. We place our findings in the context of a definition for resilience that emphasizes a systems view at multiple scales of social organization. We make three primary contributions: (1) we contribute an empirical account of resilience in a contextual setting that complements prior CSCW resilience studies, (2) we add nuance to existing models for resilience to reflect the role of technology as both a resilience tool and a source of adversity, and (3) we identify the need for new designs that integrate nature into systems as a way to foster collaborative resilience. This nuanced understanding of the role of technology in individual and community resilience in and with nature provides direction for technology design that may be useful for everyday disrupted life.

The Federal Communications Commission (FCC) has recently released official technical requirements for its Broadband Data Collection (BDC) processes, with the purpose of improving the accuracy of broadband coverage data in the United States. A key process in the BDC establishes the opportunity for communities to crowdsource Internet measurements that may dispute coverage data maintained by Internet service providers. This process outlines complex requirements that may provide a substantial barrier to community participation. In this poster we share the design of a network measurement tool suite and the requirements for a community coordination tool to support community-led efforts to challenge official reports. Our design is based on “counter-data action” principles, which call unethical and authoritative uses of data into question.

Globally, 43% of households lack Internet access, primarily in regions where deployment and/or service costs are prohibitive, including in the least developed countries, rural locations, and regions with high concentrations of ethnic minorities and low-income populations. Unfortunately, this lack of Internet access increasingly equates to a lack of access to essential services, such as healthcare, education, and economic opportunities. In an environment of marginal economics, creative and varied approaches to obtaining access have flourished, including Internet kiosks long popular in the Global South, libraries as public access in the Global North, parking lot use of open WiFi access points, and spectrum-based solutions such as TV whitespace links and citizen band radio. In the near future, local 5G and the deployment of satellite constellations promise yet additional options in the price/performance space for access. In this context we are interested in the following research question: How can the presence of multiple networks, with different price, performance, and geographic reach profiles, be best used in concert to improve access to critical services? We propose that a robust answer to this question bears a holistic, cross-layer examination of new communication paradigms, network architecture innovation, and application design. We make this concrete by running to ground a specific case study of two networks, one high performance yet limited in geographic scope and the other low performance yet pervasive. Specifically our LoRaX (LoRa eXtends the Internet) system combines high bandwidth but non-pervasive Internet access with a low data rate, low power, yet ubiquitious network made possible by IoT developments. By focusing on two networks with extreme differences, we explore a design space that offers users new opportunities for participating in Internet-based services–even when high speed Internet connectivity is intermittent. We also reflect on the generality of the environment and our solution approach for future multi-network settings.

The 2020 election was fraught with allegations of fraud. To respond to a lack of a robust method to investigate these allegations, we propose a multi-step clustering based approach. We first solve a regression problem to find a group of influential variables, then cluster on these variables to get a set of precincts that should have similar election results. Re-clustering each cluster shows us the outliers. We then apply the approach to Fulton County, Georgia’s largest county and an epicenter of allegations of corruption and fraud. We show that the level of fraud detected is not significant and would not be enough to change the election results in Georgia. In fact, the majority of the precincts that showed to be anomalous were ones where Trump received more votes than was expected. We also validate our analysis through application to the 2015 Argentina National Election.

Cellular network performance does not cleanly generalize. A variety of factors, such as location, terrain, signal quality and network load, affect the performance of services delivered over LTE networks. As a result, the presence of LTE coverage does not always equate to usable service; coverage can be of poor quality, or it can be congested and difficult to access. Given that reliance on LTE networks for Internet connectivity has exploded, it is critical to understand the quality of experience for applications delivered over these networks in a variety of scenarios. To this end, we develop a robust measurement suite that we use to conduct a unique measurement campaign in tribal, rural, congested urban and uncongested urban regions, representing a variety of under-provisioned, congested, and well-provisioned operational LTE networks run by four major providers. Our analysis confirms that the performance of LTE networks in tribal and rural areas is typically worse than even heavily congested urban networks. More specifically, in the regions that we study, LTE networks in under-provisioned (tribal/rural) areas have $ 9\times$ poorer video streaming quality, $ 10\times$ higher video start-up delay, undergo more than $ 10\times$ the number of resolution switches, and lead to more than $ 2\times$ slower Web browsing experience as compared to urban deployments. We show that throughput and latency are $ 11\times$ and $ 3\times$ worse in tribal and rural locations, despite identical LTE carrier subscription plans.

In response to widespread calls for computer scientists to better engage with the ethical dimensions of their work, there has been a surge of interest to embed ethics across the computer science (CS) curriculum. Yet one key set of barriers to doing so can be broadly described as scaling challenges -- in the number and breadth of courses in a curriculum and in the number of students in the CS major. Our paper describes and makes available a novel activity for teaching ethics using role-play that has advantages for scaling across different courses and in different delivery modes, including synchronous and asynchronous online course offerings. We describe our design process and early findings from developing the activity in a large first year seminar course, a senior-level computing and society class, and three different online graduate level courses. Further, we describe an evaluation survey that instructors can use to assess the short-term impact of the activity. We analyze survey results and our direct observations to reflect on the strengths and challenges of the activity. Our experiences suggest that role-play as a pedagogical tool can be particularly useful to broaden student perspectives and meaningfully incorporate ethics into CS courses.

Researching and designing Internet infrastructure solutions in rural and tribal contexts requires reciprocal relationships between researchers and community partners. Methodologies must be meaningful amid local social textures of life. Achieving transdisciplinarity while relating research impacts to partner communities takes care work, particularly where technical capacity is scarce. The Full Circle Framework is an action research full stack development methodology that foregrounds reciprocity among researchers, communities, and sovereign Native nations as the axis for research purpose and progress. Applying the framework to deploy television white space infrastructure in sovereign Native nations in northern New Mexico reveals challenges for rural computing, including the need to design projects according to the pace of rural and tribal government workflows, cultivate care as a resource for overworked researchers and community partners, and co-create a demand for accurate government data around Internet infrastructures in Indian Country and through rural counties.

Understanding end-user video Quality of Experience (QoE) is important for Internet Service Providers (ISPs). Existing work presents mechanisms that use network measurement data to estimate video QoE. Most of these mechanisms assume access to packet-level traces, the most-detailed data available from the network. However, collecting packet-level traces can be challenging at a network-wide scale. Therefore, we ask:"Is it feasible to estimate video QoE with lightweight, readily-available, but coarse-grained network data?" We specifically consider data in the form of Transport Layer Security (TLS) transactions that can be collected using a standard proxy and present a machine learning-based methodology to estimate QoE. Our evaluation with three popular streaming services shows that the estimation accuracy using TLS transactions is high (up to 72%) with up to 85% recall in detecting low QoE (low video quality or high re-buffering) instances. Compared to packet traces, the estimation accuracy (recall) is 7% (9%) lower but has up to 60 times lower computation overhead.

With over 6 million articles and 38 million editors, English Wikipedia is one of the largest peer produced and edited encyclopedias on the Internet. Some attribute this success to the peer production process which allows many to contribute. However, not all articles are created equally, or evolve similarly, in terms of quality and amount of attention they receive from the editing community. We examine pages with geotagged content in English Wikipedia in four categories, places with Indigenous majorities (of any size), Rural places, Urban Clusters, and Urban areas. We find significant differences in quality and editor attention for articles about places with Native American majorities, as compared to other places.

Cloud services are deployed in datacenters connected though high-bandwidth Wide Area Networks (WANs). We find that WAN traffic negatively impacts the performance of datacenter traffic, increasing tail latency by 2.5x, despite its small bandwidth demand. This behavior is caused by the long round-trip time (RTT) for WAN traffic, combined with limited buffering in datacenter switches. The long WAN RTT forces datacenter traffic to take the full burden of reacting to congestion. Furthermore, datacenter traffic changes on a faster time-scale than the WAN RTT, making it difficult for WAN congestion control to estimate available bandwidth accurately.

Modern end-host network stacks have to handle traffic from tens of thousands of flows and hundreds of virtual machines per single host, to keep up with the scale of modern clouds. This can cause congestion for traffic egressing from the end host. The effects of this congestion have received little attention. Currently, an overflowing queue, like a kernel queuing discipline, will drop incoming packets. Packet drops lead to worse network and CPU performance by inflating the time to transmit the packet as well as spending extra effort on retansmissions. In this paper, we show that current end-host mechanisms can lead to high CPU utilization, high tail latency, and low throughput in cases of congestion of egress traffic within the end host. We present zD, a framework for applying backpressure from a congested queue to traffic sources at end hosts that can scale to thousands of flows. We implement zD to apply backpressure in two settings: i) between TCP sources and kernel queuing discipline, and ii) between VMs as traffic sources and kernel queuing discipline in the hypervisor. zD improves throughput by up to 60%, and improves tail RTT by at least 10x at high loads, compared to standard kernel implementation.

BGP was initially created assuming by default that all ASes are equal. Its policies and protocols, namely BGP, evolved to accommodate a hierarchical Internet, allowing an autonomous system more control over outgoing traffic than incoming traffic. However, the modern Internet is flat, making BGP asymmetrical. In particular, routing decisions are mostly in the hands of traffic sources (i.e., content providers). This leads to suboptimal routing decisions as traffic sources can only estimate route capacity at the destination (i.e., ISP). In this paper, we present the design of Unison, a system that allows an ISP to jointly optimize its intra-domain routes and inter-domain routes, in collaboration with content providers. Unison provides the ISP operator and the neighbors of the ISP with an abstraction ISP network in the form of a virtual switch. This abstraction allows the content providers to program the virtual switch with their requirements. It also allows the ISP to use that information to optimize the overall performance of its network. We show through extensive simulations that Unison can improve ISP throughput by up to 30% through cooperation with content providers. We also show that cooperation of content providers only improves performance, even for non-cooperating content providers (e.g., a single cooperating neighbour can improve ISP throughput by up to 6%).

We investigate Internet traffic logs on rural Native American reservations in California served by a tribally-owned Internet provider. The anonymous user browsing traffic and device preferences create unique failure patterns that reveal where connectivity is not well-served by standard networking technology. Geographical and cultural marginalization has lead to distinctive Internet usage when connectivity is available. For instance, residents commonly visit websites that are not as popular in the wider United States; and mobile devices dominate web request traffic, often with content-heavy video and media downloads, despite sustaining a higher rate of failure than desktop devices. This statistical analysis of passive measurements avoids institutional and cultural biases and ensures continuing research will contribute to a decolonizing narrative of Native American informational practices and values. Based on our analysis, we propose follow-up research angles to better understand the technological and social drivers behind these findings in order to improve user experience in this, and similar, networks.

Over 87% of US mobile wireless subscriptions are currently held by LTE-capable devices [34]. However, prior work has demonstrated that connectivity may not equate to usable service. Even in well-provisioned urban networks, unusually high usage (such as during a public event or after a natural disaster) can lead to overload that makes the LTE service difficult, if not impossible to use, even if the user is solidly within the coverage area. A typical approach to detect and quantify overload on LTE networks is to secure the cooperation of the network provider for access to internal metrics. An alternative approach is to deploy multiple mobile devices with active subscriptions to each mobile network operator (MNO). Both approaches are resource and time intensive. In this work, we propose a novel method to estimate overload in LTE networks using only passive measurements, and without requiring provider cooperation. We use this method to analyze packet-level traces for three commercial LTE service providers, T-Mobile, Verizon and AT&T, from several locations during both typical levels of usage and during public events that yield large, dense crowds. This study presents the first look at overload estimation through the analysis of unencrypted broadcast messages. We show that an upsurge in broadcast reject and cell barring messages can accurately detect an increase in network overload.

Despite widespread LTE adoption and dependence, rural areas lag behind in coverage availability and quality. In the United States, while the Federal Communications Commission (FCC), which regulates mobile broadband, reports increases in LTE availability, the most recent FCC Broadband Report was criticized for overstating coverage. Physical assessments of cellular coverage and quality are essential for evaluating actual user experience. However, measurement campaigns can be resource, time, and labor intensive; more scalable measurement strategies are urgently needed. In this work, we first present several measurement solutions to capture LTE signal strength measurements, and we compare their accuracy. Our findings reveal that simple, lightweight spectrum sensing devices have comparable accuracy to expensive solutions and can estimate quality within one gradation of accuracy when compared to user equipment. We then show that these devices can be mounted on Unmanned Aircraft Systems (UAS) to more rapidly and easily measure coverage across wider geographic regions. Our results show that the low-cost aerial measurement techniques have 72% accuracy relative to the ground readings of user equipment, and fall within one quality gradation 98% of the time.

Researchers in human-centered computing have surfaced a feminist ethic of care in interaction with technologies, in data collection, and in data work. Drawing on two years of ethnographic fieldwork, we consider how democratic caring might be enacted and sustained through collaborative data work. We employ philosopher Joan Tronto's theory of caring democracy to structure our analysis of a resident-led initiative that uses data to organize and address issues of neglect and abandonment in their neighborhood. Adding to the CSCW literature on sociotechnical systems of care, we look particularly at Tronto's concept of caring democracy where caring needs and the ways in which they are met are an ongoing and inclusive process of assigning and reassigning caring responsibilities, characterized by both equality of voice and freedom from domination. This work develops grounded insight into the practice of democratic caring and how collaborative data work is relevant to this caring practice. We discuss opportunities and challenges for a data-supported caring democracy and address how caring democracy technologies are different from other modern civic technology practices. We conclude with a call to researchers to identify and enact democratic caring experiments in the small.

Understanding the user-perceived quality of experience (QoE) of HTTP-based video has become critical for content providers, distributors, and network operators. For network operators, monitoring QoE is challenging due to lack of access to video streaming applications, user devices, or servers. Thus, network operators need to rely on the network traffic to infer key metrics that influence video QoE. Furthermore, with content providers increasingly encrypting the network traffic, the task of QoE inference from passive measurements has become even more challenging. In this paper, we present a methodology called eMIMIC that uses passive network measurements to estimate key video QoE metrics for encrypted HTTP-based adaptive streaming (HAS) sessions. eMIMIC uses packet headers from network traffic to model an HAS session and estimate video QoE metrics, such as average bitrate and re-buffering ratio. We evaluate our methodology using network traces from a variety of realistic conditions and ground truth collected using a lab testbed for video sessions from three popular services, two video on demand (VoD) and one Live. eMIMIC estimates re-buffering ratio within 1% point of ground truth for up to 75% sessions in VoD (80% in Live) and average bitrate with error under 100 Kb/s for up to 80% sessions in VoD (70% in Live). We also compare eMIMIC with recently proposed machine learning-based QoE estimation methodology. We show that eMIMIC can predict average bitrate with 2.8%-3.2% higher accuracy and re-buffering ratio with 9.8%-24.8% higher accuracy without requiring any training on ground truth QoE metrics. Finally, we show that eMIMIC can estimate real-time QoE metrics with at least 89.6% accuracy in identifying buffer occupancy state and at least 85.7% accuracy in identifying average bitrate class of recently downloaded chunks.

Data science is an interdisciplinary field that extracts insights from data through a multi-stage process of data collection, analysis and use. When data science is applied for social good, a variety of stakeholders are introduced to the process with an intention to inform policies or programs to improve well-being. Our goal in this paper is to propose an orientation to care in the practice of data science for social good. When applied to data science, a logic of care can improve the data science process and reveal outcomes of "good" throughout. Consideration of care in practice has its origins in Science and Technology Studies (STS) and has recently been applied by Human Computer Interaction (HCI) researchers to understand technology repair and use in under-served environments as well as care in remote health monitoring. We bring care to the practice of data science through a detailed examination of our engaged research with a community group that uses data as a strategy to advocate for permanently affordable housing. We identify opportunities and experiences of care throughout the stages of the data science process. We bring greater detail to the notion of human-centered systems for data science and begin to describe what these look like.

The basic MAC mechanisms in IEEE 802.11 (WiFi) have remained largely unchanged for over 20 years. In this paper, we argue that the prevalence of WiFi makes it almost impossible to improve its performance through changes that require modifying hardware, firmware, or drivers. New applications, however, continue to exert novel performance demands. We suggest that changes should be developed as augmentation-only solutions through above-driver, kernel-level software modifications. An augmentation-only solution needs to maintain inter-operability and afford transparency in performance to existing WiFi devices, as well as enable minimum overhead upgradability. Our goal is to demonstrate the feasibility of MAC augmentation according to these principles. To this end, we leverage soft scheduling, where nodes are asked for a best-effort attempt to adhere to a given schedule. We allow the soft scheduler to coexist with and work at a different time scale from WiFi's Distributed Coordination Function (DCF); allowing it to reduce the time nodes spend contending for the medium while allowing DCF to handle only missed schedule slots and schedule divergence. We present a new Soft Token Passing Protocol (STPP) as an instance of this family of Soft Scheduling Protocols. We then show how STPP can be made part of a MAC protocol with specific performance improvement goals by developing the Wireless Low-Latency Local Links (WL4) system. We evaluate WL4 on a five node microbenchmark and quantify the system's overhead on network throughput and latency. We show that soft scheduling, via STPP, enables WL4 to adhere to our augmentation principles while improving the latency within the system.

Video streaming traffic is rapidly growing in mobile networks. Mobile Network Operators (MNOs) are expected to keep up with this growing demand, while maintaining a high video Quality of Experience (QoE). This makes it critical for MNOs to have a solid understanding of users' video QoE with a goal to help with network planning, provisioning and traffic management. However, designing a system to measure video QoE has several challenges: i) large scale of video traffic data and diversity of video streaming services, ii) cross-layer constraints due to complex cellular network architecture, and iii) extracting QoE metrics from network traffic. In this paper, we present VideoNOC, a prototype of a flexible and scalable platform to infer objective video QoE metrics (e.g., bitrate, rebuffering) for MNOs. We describe the design and architecture of VideoNOC, and outline the methodology to generate a novel data source for fine-grained video QoE monitoring. We then demonstrate some of the use cases of such a monitoring system. VideoNOC reveals video demand across the entire network, provides valuable insights on a number of design choices by content providers (e.g., OS-dependent performance, video player parameters like buffer size, range of encoding bitrates, etc.) and helps analyze the impact of network conditions on video QoE (e.g., mobility and high demand).

White spaces are portions of the TV spectrum that are allocated but not used locally. Ifaccurately detected, white spaces offer a valuable new opportunity for highspeed wireless communications. We propose a new method for white space detection that allows a node to actlocally, based on a centrally constructed model, and at low cost, whiledetecting more spectrum opportunities than best known approaches. Weleverage two ideas. First, we demonstrate that low-cost spectrum monitoringhardware can offer "good enough" detection capabilities. Second, we develop amodel that combines locally-measured signal features and location to more efficiently detect white space availability. We incorporate these ideas into the design,implementation, and evaluation of a complete system we call Waldo. We deployWaldo on a laptop in the Atlanta metropolitan area in the US covering 700 km2. Our results show that usingsignal features, in addition to location, can improve detection accuracy by up to10x for some channels. We also deploy Waldo on an Android smartphone,demonstrating the feasibility of real-time white space detection with efficientuse of smartphone resources.

It has become increasingly important for content providers (CPs) to reach consumers with low latency. Peering links that connect CPs directly to access Internet service providers (access ISPs) have been used for this purpose thus providing one-hop AS paths from CPs to users. While providing improved latency, these peering links still do not give CPs control over the entire end-to-end path to their users. This has made it difficult for CPs to completely manage user experience. Motivated by this, we propose the deployment of Zero-Hop Networks (ZeN), where a CP's entire end-to-end path to users is under its control. We believe it is important to respond to the compelling demand for ZeN and enable its provision over the shared Internet infrastructure so that all may continue to reap its benefits. In this paper we lay out the vision for ZeN, describing its goals and challenges. We propose to deploy ZeN by allowing CPs to extend their network's control over the access ISP substrate in a way that allows the CP to control the entire end-to-end path. We develop two strawman architectures based on Software-Defined Networking ideas: one based on resource reservation and the other based on network virtualization. We also discuss some elements of a research agenda that is needed to bring ZeN deployments to realization.

Massive, Open, Online Courses (MOOCs) have been promoted as a means to revolutionize access to education. In this paper, we describe experiences with MOOCs for Liberian students who are connected to the iLab technology hub. We describe their motivations for participating as well as the challenges they encountered. We also describe the importance of the face-to-face learning environment provided by the iLab as a source of community support.

Since 2011, our research group, along with numerous local partners, has been building a platform and methodology for monitoring elections using social media. Historically, election monitoring has traditionally been the domain of trained monitors provided by international monitoring groups. But monitoring by domestic groups with fewer resources has been a growing phenomenon, supported in part by the availability of inexpensive digital technologies such as SMS. Social media represents a further, exciting step in this trend. We describe our five years of experience in this endeavor and report a series of key lessons learned. These lessons touch on issues such as source types and curation, collaboration with other election-related groups, human vs. automated analysis, varying stakeholder needs, and the value of falsification. We also share our vision for the next five years of this research.

Traditional election monitoring involves trained observers recruited and deployed by neutral organizations to complete structured reports based on their first-hand observations. In contrast, social media-based election monitoring takes as input the high volume, noisy data produced by individuals posting on social media outlets, with limited constraints and structure. Trained volunteers process this data in an effort to extract meaningful information. Both methods have been used successfully to support free and fair elections. In this work we begin to explore a middle ground, namely reports by untrained individuals, but mediated through a mobile phone application that provides structure for the responses. In collaboration with Pol-IT, a Buenos Aires based organization focused on politics and ICTs, we report on a first study of users of the Ojo con el Voto (Eyes on the Vote) application deployed during the Argentina presidential run-off election in November 2015. We expect that citizen apps for election monitoring will become increasingly popular, hence this early look at their use offers an opportunity to establish an initial baseline and to potentially influence subsequent development.

Multimedia streaming is a major mobile application, accounting for more than half of total mobile traffic. Streaming applications usually have a static buffering strategy. For example, buffer size is limited to x minutes of the stream, where x is optimized to provide the best trade-off between minimizing stalls and limiting waste of user's bandwidth and energy resulting from user abandonment. We show that such strategies based on information available on the mobile device alone do not work well when network conditions change dynamically, e.g., connectivity degrades due to congestion. We propose an alternative strategy using the framework called TANGO, based on a novel idea of cooperation between cellular network and mobile devices. By monitoring real-time network conditions and continuously predicting user location, our system is able to predict connectivity degradation in the near term. In such events, a notification is sent to the mobile device so that the streaming application can initiate a mitigation action, such as to pre-cache more content. In simulations based on real user traces, we found that TANGO reduces pause time by 13-72%, significantly outperforming DASH, which is the current state of the art.

Mobile devices are becoming increasingly capable computing platforms with significant processor power and memory. However, mobile compute capabilities are often underutilized. In this paper we consider how a collection of co-located devices can be orchestrated to provide a cloud service at the edge. Scenarios with co-located devices include, but are not limited to, passengers with mobile devices using public transit services, students in classrooms and groups of people sitting in a coffee shop. To this end, we propose the femtocloud system which provides a dynamic, self-configuring and multi-device mobile cloud out of a cluster of mobile devices. We present the femtocloud system architecture designed to enable multiple mobile devices to be configured into a coordinated cloud computing service despite churn in mobile device participation. We develop a prototype of our femtocloud system and use it in addition to simulations to evaluate the performance of the system showing its efficiency and ability to leverage the available devices' compute capacity. We contribute to a line of research on small, local and possibly private clouds.

With the advent of wearable computing and the resulting growth in mobile application market, we investigate mobile opportunistic cloud computing where mobile devices leverage nearby computational resources in order to save execution time and consumed energy. Our goal is to enable generic computation offloading to heterogeneous devices that include Cloud, mobile devices, and cloudlets. We propose a generic and flexible architecture that maximizes the computation gain with respect to various objective functions such as, minimizing the response time, reducing the overall energy consumption, and increasing the network lifetime. This novel architecture is designed to automate computation offloading to numerous compute resources over disrupted network connections.

Working with the Carter Center, we have developed and sustained software and training to enable data reporting at the patient level by mental health clinicians in Liberia. Over a four year time period, more than 140 clinicians have been trained in the use of the data reporting software, and more than 3000 valid reports have uploaded to the cloud. This participation has persisted despite significant technology challenges and little data feedback to clinicians. Because so many ICTD interventions fail, we were interested in the factors that contributed to sustaining the human and technology infrastructure to enable data reporting over this fairly long time period. We focus on motivations to participate and find support for positive motivations such as clinician pride. We find that being seen to do health work, not just doing the work, plays a critical role in motivation. We describe and critically analyze a novel approach to sustaining the technology, using student teams in a class. We assess project success through two lenses provided by the literature, first on characterization of project success and failure factors, and then on project champions.

While Information and Communication Technology (ICT) access in Liberia is still low, use of PCs, mobile phones and the Internet is rising. A relatively recent option for learning ICT skills is Liberia's iLab technology hub founded in 2011 to encourage and support a local technology community. We have partnered with the iLab since its founding to offer summer courses taught by a student instructor. In this paper, we describe how the iLab's community-based learning approach has advanced from the coalescing stage, identified in earlier research, towards the maturing stage, despite obstacles. We use Lave and Wenger's Community of Practice (CoP) framework as the analytic structure to present results from our data consisting primarily of interviews with course participants. We contribute to research on technology hubs in Africa and highlight the role of community-based learning for technical skill acquisition even in resource challenged settings.

DDoS attacks have been a persistent threat to network availability for many years. Most of the existing mitigation techniques attempt to protect against DDoS by filtering out attack traffic. However, as critical network resources are usually static, adversaries are able to bypass filtering by sending stealthy low traffic from large number of bots that mimic benign traffic behavior. Sophisticated stealthy attacks on critical links can cause a devastating effect such as partitioning domains and networks. In this paper, we propose to defend against DDoS attacks by proactively changing the footprint of critical resources in an unpredictable fashion to invalidate an adversary's knowledge and plan of attack against critical network resources. Our present approach employs virtual networks (VNs) to dynamically reallocate network resources using VN placement and offers constant VN migration to new resources. Our approach has two components: (1) a correct-by-construction VN migration planning that significantly increases the uncertainty about critical links of multiple VNs while preserving the VN placement properties, and (2) an efficient VN migration mechanism that identifies the appropriate configuration sequence to enable node migration while maintaining the network integrity (e.g., avoiding session disconnection). We formulate and implement this framework using SMT logic. We also demonstrate the effectiveness of our implemented framework on both PlanetLab and Mininet-based experimentations.

Mobile devices are often expected to perform computational tasks that may be beyond their processing or battery capability. Cloud computing techniques have been proposed as a means to offload a mobile device's computation to more powerful resources. In this paper, we consider the case where powerful computing resources are employed on a vehicle, thus they can be re-positioned in real time. User-carried devices with no Internet connectivity wish to initiate computing tasks to be run on a remote computer. This scenario finds application in challenged environments and may be used in a military or disaster relief setting. It is further enabled by increasing feasibility of constructing a Mobile High Performance Computer (MHPC) using rugged computer hardware with form factors that can be deployed in vehicles. By analogy to prior work on message ferries and data mules, one can refer to the use of MHPCs as computational ferrying. After illustrating and motivating the computational ferrying concept, we turn our attention into the challenges facing such a deployment. These include the well-known challenges of operating an opportunistic and intermittently connected network using message ferries - such as devising an efficient mobility plan for MHPCs and developing techniques for proximity awareness. In addition such a system must include computation offloading decision making mechanisms to be deployed by mobile users, techniques for scheduling computation on MHPCs, and for handling possible mobility of the users. In this paper, first we propose an architecture for the system components to be deployed on the mobile users and the MHPCs. We then provide solutions to the MHPC movement scheduling problem with sufficient generality to describe a number of plausible deployment scenarios. Finally, we report and discuss some preliminary results.

There is great potential for boosting the performance of mobile devices by offloading computation-intensive parts of mobile applications to the cloud. The full realization of this potential is hindered by a mismatch between how individual mobile devices demand computing resources and how cloud providers offer them: offloading requests from a mobile device usually require quick response, may be infrequent, and are subject to variable network connectivity, whereas cloud resources incur relatively long setup times, are leased for long time quanta, and are indifferent to network connectivity. In this paper, we present the design and implementation of the COSMOS system, which bridges this gap by providing computation offloading as a service to mobile devices. COSMOS efficiently manages cloud resources for offloading requests to both improve offloading performance seen by mobile devices and reduce the monetary cost per request to the provider. COSMOS also effectively allocates and schedules offloading requests to resolve the contention for cloud resources. Moreover, COSMOS makes offloading decisions in a risk-controlled manner to overcome the uncertainties caused by variable network connectivity and program execution. We have implemented COSMOS for Android and explored its design space through computation offloading experiments to Amazon EC2 across different applications and in various settings. We find that COSMOS, configured with the right design choices, has significant potential in reducing the cost of providing cloud resources to mobile devices while at the same time enabling mobile computation speedup.

The explosive growth of mobile data traffic poses severe pressure on cellular providers to better manage their finite spectrum. Proposed solutions such as congestion-pricing exist, but they degrade users' ability to use the network when they want. In this paper, we propose a fundamentally different approach - rather than reducing the aggregate busy hour traffic, we seek to smooth the peaks that cause congestion. Our approach is based on two key insights obtained from traffic traces of a large cellular provider. First, mobile traffic demonstrates high short-term variation so that delaying traffic for very short periods of time can significantly reduce peaks. Second, by making collaborative decisions on which traffic gets delayed and by how much across all users of a cell, the delays need not result in any degradation of user experience. We design a system, CoAST, to implement this approach using three key mechanisms: a protocol to allow mobile applications and providers to exchange traffic information, an incentive mechanism to incentivize mobile applications to collaboratively delay traffic at the right time, and mechanisms to delay application traffic. We provide extensive evaluations that show that CoAST reduces traffic peaks by up to 50% even for applications that are not thought to be delay-tolerant, e.g., streaming and web browsing, but which together account for 70% of all cellular traffic.

Network virtualization enables the deployment of novel network architectures and services on existing Internet infrastructure. In addition, virtual networks (VNs) can share the resources in the physical substrate. To enable efficient resource reallocation and network agility, VNs must sometimes migrate, i.e., change their placements on a substrate network. While VN placement, and to a lesser extent migration, has been studied in the past, little attention has been devoted to deploying and evaluating these functions over a real infrastructure. In this paper, we study the VN migration problem based on network virtualization in PlanetLab. We create a tool, PL-VNM, that orchestrates the VN migration on PlanetLab for a given new VN placement. The design and deployment of the tool reveal challenges and constraints. Some are particular to PlanetLab while others apply more generally to any virtualized infrastructure. Most significantly, we find that while in principle one can specify a migration schedule (sequence of migration steps) as an input to our tool, certain PlanetLab features make VN migration scheduling very difficult if not infeasible. Our work leads to recommendations about the features of a general virtualization environment and specific recommendations for PlanetLab that enable VN migration and migration scheduling. We believe that the recommended features make long-term experiments and application deployments on PlanetLab and other realistic virtualized infrastructures possible.

Technology hubs---labs committed to fostering local technology and entrepreneurship communities---are newcomers in local African ICT ecosystems. While research has focused on the organizational structure of labs, the degree to which they fuel start ups, and surrounding institutional contexts in which they operate, less is understood about how each operates as a Community of Practice (CoP) from social learning theory. And yet, the creation of such a community of practice seems central to building local ICT capacity. Drawing on data from Liberia's iLab, we describe how it functions as a CoP and identify some next steps for supporting its community.

Mobile devices are increasingly being relied on for services that go beyond simple connectivity and require more complex processing. Fortunately, a mobile device encounters, possibly intermittently, many entities capable of lending it computational resources. At one extreme is the traditional cloud-computing context where a mobile device is connected to remote cloud resources maintained by a service provider with which it has an established relationship. In this paper we consider the other extreme, where a mobile device's contacts are only with other mobile devices, where both the computation initiator and the remote computational resources are mobile, and where intermittent connectivity among these entities is the norm. We present the design and implementation of a system, Serendipity, that enables a mobile computation initiator to use remote computational resources available in other mobile systems in its environment to speedup computing and conserve energy. We propose a simple but powerful job structure that is suitable for such a system. Serendipity relies on the collaboration among mobile devices for task allocation and task progress monitoring functions. We develop algorithms that are designed to disseminate tasks among mobile devices by accounting for the specific properties of the available connectivity. We also undertake an extensive evaluation of our system, including experience with a prototype, that demonstrates Serendipity's performance.

Message Ferrying is a mobility assisted scheme in which a special node, called a message ferry, is tasked with delivering data among a set of disconnected wireless nodes. One key challenge for such scheme is to design the ferry route in a way that improves certain network characteristics such as average data delivery delay or data loss ratio. Previous work has optimized ferry travel time, rather than directly optimizing message delivery performance metrics. In this paper, we revisit the basic ferry route design problem for stationary nodes with the goal of providing a framework for optimizing delay performance. We start with a Markovian Decision Problem (MDP) formulation which produces the optimal ferry route that minimizes the average data delivery delay. While this formulation, in principle, enables optimal ferry route design, it is numerically intractable for moderate to large size problems. Solutions to small problems, however, yield insight into the properties of optimal ferry routes. These insights, in turn, lead us to propose a ferry route design algorithm that takes advantage of the similarity between our problem and the link scheduling problem in traditional networks. Our algorithm is inspired by the Deficit Round Robin (DRR) algorithm which has provable properties for delay optimization when applied to link scheduling. Using simulations we show that our DRR-based algorithm produces ferry routes that are close to optimal when compared to the MDP-derived solutions for small problems. Our results also show that our algorithm produces ferry routes for moderate to large problems that significantly outperform existing solutions.

As the dominant Internet application, peer-to-peer (P2P) file sharing systems account for the major portion of Internet traffic, posing significant burden on ISPs. Many ISPs have attempted to discriminate against P2P traffic, making it important to alleviate such severe conflict. In this paper, we propose a novel architecture called iDTT that aims to use the underutilized off-peak time network capacity to transfer data for P2P file sharing systems. The rationale is that file sharing, especially for large files, is not real-time and able to tolerate some delay. iDTT is able to reduce network usage at peak time by storing data at overlay nodes and transferring it at off-peak times. This reduces ISP cost for transit traffic and the pressure on their infrastructure. Two representative P2P systems, eMule and BitTorrent, are adapted to use iDTT as their data plane. Our experiments on Emulab show that iDTT significantly reduces the network traffic at peak times while only slightly increasing the downloading time for these applications.

Cellular data links are an effective outdoor Internet access solution in urban environments. In this paper, we evaluate cellular data service as a potential data communication solution for oil field crews operating at remote areas in the United States. In our study, we first record the performance of cellular data service at twelve oil field locations. Measurement results show extensive availability of cellular service at those locations making it potentially a data communication solution at field locations. Spatial diversity from multiple antennas is shown to improve the cellular data link's speed but quality of the link varies significantly due to attenuated/faded cellular signal. We then design a measurement framework and deploy measurement units to five oil field crews and carry out a side-by-side comparison of two different satellite links and cellular links from two service providers. Analysis of data sets consisting of more than 300 days' measurement shows that the cellular link has comparable or even higher availability than conventional satellite link at many field operations. However, the quality of its coverage is location dependent. This indicates that both cellular and satellite links should be used to provide highly available and cost-effective data communication for such operations.

In this paper we consider how vehicular networking technology can be used to support roadside-to-roadside (r2r) communications. In this form of communication vehicles traveling along a road or highway are used to transport data between two fixed roadside locations that are too far apart to be connected. The basic idea is to have a roadside station give data to a moving vehicle as it gets close and then have the vehicle carry and then deliver the data to the other roadside station. In previous work we first considered the feasibility of such a service. In this paper we aim to take concrete steps towards making the deployment of such a service real and useable. We, therefore, focus on two main aspects of such a service: 1) The design of the data transfer mechanisms between the roadside stations and the vehicles assuming a standard 802.11 MAC protocol is in use, and 2) The design of schemes to insure reliable data transfer between the two roadside stations over the particularly challenging channel provided by the moving vehicles. We describe and evaluate several schemes to achieve data transfer reliability. We find that a rateless coding scheme is best for the transfer of small to moderate files, while a hybrid ARQ/data replication scheme performs well for larger file transfers.

Abstract — Intelligent Route Control (IRC) systems are increasingly deployed in multihomed networks. IRC systems aim to optimize the cost and performance of outgoing traffic, based on measurement-driven dynamic path switching techniques. In this paper, we first show that IRC systems can introduce sustained traffic oscillations, causing significant performance degradation instead of improvement. This happens, first, when IRC systems do not take into account the self-load effect, i.e., when they ignore that the performance of a path can change after additional traffic is switched to that path. Second, oscillations can take place when different IRC systems get synchronized due to significant overlap of their measurement time windows. We then propose measurement methodologies and path switching algorithms that can effectively deal with the previous two issues. The proposed IRC techniques use available bandwidth estimation to avoid the self-load effect, and they introduce a random component in the path switching decision or time scale. We evaluate the proposed techniques under diverse traffic conditions. When the background traffic is stationary, IRC systems should switch paths conservatively, only upon major traffic fluctuations. With nonstationary background traffic and congestion periods that last for a time scale ¢¡, IRC systems improve performance only if they can detect congestion and switch paths much faster than ¡; otherwise, they cause oscillations and hurt performance. We also show that the gradual deployment of randomized IRC systems, in the presence of traffic from deterministic IRC systems, can play a stabilizing role and benefits early adopters.

Disruption tolerant networks (DTNs) are designed to overcome limitations in connectivity due to conditions such as mobility, poor infrastructure, and short range radios. DTNs rely on the inherent mobility in the network to deliver packets around frequent and extended network partitions using a store-carry-and-forward paradigm. However, missed contact opportunities decrease throughput and increase delay in the network. We propose the use of throwboxes in mobile DTNs to create a greater number of contact opportunities, consequently improving the performance of the network. Throwboxes are wireless nodes that act as relays, creating additional contact opportunities in the DTN. We propose algorithms to deploy stationary throwboxes in the network that simultaneously consider routing as well as placement. We also present placement algorithms that use more limited knowledge about the network structure. We perform an extensive evaluation of our algorithms by varying both the underlying routing and mobility models. Our results suggest several findings to guide the design and operation of throwbox-augmented DTNs

Message ferrying is a networking paradigm where a special node, called a message ferry, facilitates the connectivity in a mobile ad hoc network where the nodes are sparsely deployed. One of the key challenges under this paradigm is the design of ferry routes to achieve certain properties of end-to-end connectivity, such as, delay and message loss among the nodes in the ad hoc network. This is a difficult problem when the nodes in the network move arbitrarily. As we cannot be certain of the location of the nodes, we cannot design a route where the ferry can contact the nodes with certainty. Due to this difficulty, prior work has either considered ferry route design for ad hoc networks where the nodes are stationary, or where the nodes and the ferry move pro-actively in order to meet at certain locations. Such systems either require long-range radio or disrupt nodes' mobility patterns which can be dictated by non-communication tasks. We present a message ferry route design algorithm that we call the Optimized Way-points, or OPWP, that generates a ferry route which assures good performance without requiring any online collaboration between the nodes and the ferry. The OPWP ferry route comprises a set of way-points and waiting times at these way-points, that are chosen carefully based on the node mobility model. Each time that the ferry traverses this route, it contacts each mobile node with a certain minimum probability. The node-ferry contact probability in turn determines the frequency of node-ferry contacts and the properties of end-to-end delay. We show that OPWP consistently outperforms other naive ferry routing approaches.

Multicast is an essential service in mobile ad hoc networks (MANETs). Numerous protocols have been proposed but none of them is directly applicable in sparse MANETs, which are a form of disruption/delay tolerant networks (DTNs). In this paper, we consider multicasting in sparse MANETs with focus on two data dissemination schemes, epidemic routing (ER) and message ferrying (MF). With necessary group management schemes, both schemes can be extended for multicast. However, their performance is scenario-dependent. With this observation, a set of multicast protocols combining the essentials of MF and ER are proposed. In particular, we propose adaptive protocols targeting a balance between transmission efficiency and timely delivery in different scenarios. With simulations, we evaluate the performance of these protocols

Searching for content in peer-to-peer networks is an interesting and challenging problem. Queries in Gnutella-like unstructured systems that use flooding or random walk to search must visit O(n) nodes in a network of size n, thus consuming significant amounts of bandwidth. In this paper, we propose a query routing protocol that allows low bandwidth consumption during query forwarding using a low cost mechanism to create and maintain information about nearby objects. To achieve this, our protocol maintains a lightweight probabilistic routing table at each node that suggests the location of each object in the network. Following the corresponding routing table entries, a query can reach the destination in a small number of hops with high probability. However, maintaining routing tables in a large and highly dynamic network requires non-traditional mechanisms. We design a novel data structure called an exponentially decaying bloom filter (EDBF) that encodes such probabilistic routing tables in a highly compressed manner, and allows for efficient aggregation and propagation. The search primitives provided by our system can be used to search for single keys or multiple keywords with equal ease. Analytical modeling of our design predicts significant improvements in search efficiency, verified through extensive simulations in which we observed an order of magnitude reduction in query path length over previous proposals.

As technology rapidly progresses, more devices will combine both communication and mobility capabilities. With mobility in devices, we envision a new class of proactive networks that are able to adapt themselves, via physical movement, to meet the needs of applications. To fully realize these opportunities, effective control of device mobility and the interaction between devices is needed. In this paper, we consider the message ferrying (MF) scheme which exploits controlled mobility to transport data in delay-tolerant networks, where end-to-end paths may not exist between nodes. In the MF scheme, a set of special mobile nodes called message ferries are responsible for carrying data for nodes in the network. We study the use of multiple ferries in such networks, which may be necessary to address performance and robustness concerns. We focus on the design of ferry routes. With the possibilities of interaction between ferries, the route design problem is challenging. We present algorithms to calculate routes such that the traffic demand is met and the data delivery delay is minimized. We evaluate these algorithms under a variety of network conditions via simulations. Our goal is to guide the design of MF systems and understand the tradeoff between the incurred cost of multiple ferries and the improved performance. We show that the performance scales well with the number of ferries in terms of throughput, delay and resource requirements in both ferries and nodes.

Delay tolerant networks (DTNs) are mobile wireless networks that are characterized by frequent partitions and potentially long message delivery delays. Such networks have the potential for use in important application environments where energy sources are limited. Therefore, efficient power management mechanisms are necessary to allow these networks to operate over a long period of time. In this paper, we leverage the observation that many DTNs are characterized by sparse connectivity, providing the opportunity to save energy by aggressively disabling node radios (sleeping). The major challenge is to balance sleeping periods with wake-up periods so that valuable and infrequent communication opportunities between nodes are not missed. We develop a power management framework that allows a node to save energy while missing few communication opportunities. The framework is tailored to the available knowledge about network connectivity over time. Further, the framework supports an explicit tradeoff between energy savings and connectivity, so that network operators can choose, for example, to conserve energy at the cost of reduced message delivery performance. We evaluate our mechanisms using ns-2 simulations. Our results show that our power management mechanisms consume from 10 % to 50 % of the energy expended when the network operates without power management. These energy savings come at the cost of some performance degradation when available knowledge is incomplete, though our tuning parameter allows a rich set of tradeoffs between energy consumption and performance.

Statistical information about the flow sizes in the traffic passing through a network link helps a network operator to characterize network resource usage, infer traffic demands, detect traffic anomalies, and improve network performance through traffic engineering. Previous work on estimating the flow size distribution for the complete population of flows has produced techniques that either make inferences from sampled network traffic, or use data streaming approaches. In this work, we identify and solve a more challenging problem of estimating the size distribution and other statistical information about arbitrary subpopulations of flows. Inferring subpopulation flow statistics is more challenging than the complete population counterpart, since subpopulations of interest are often specified a posteriori (i.e., after the data collection is done), making it impossible for the data collection module to "plan in advance".Our solution consists of a novel mechanism that combines data streaming with traditional packet sampling to provide highly accurate estimates of subpopulation flow statistics. The algorithm employs two data collection modules operating in parallel --- a NetFlow-like packet sampler and a streaming data structure made up of an array of counters. Combining the data collected by these two modules, our estimation algorithm uses a statistical estimation procedure that correlates and decodes the outputs (observations) from both data collection modules to obtain flow statistics for any arbitrary subpopulation. Evaluations of this algorithm on real-world Internet traffic traces demonstrate its high measurement accuracy.

We propose a cooperative patching architecture to achieve continuous live video streaming to a set of cooperative but unreliable end hosts. In this design, each end host caches an initial portion of the video content before playback. It then keeps the video that has been played out for a certain time before discarding it. An end host maintains a list of patching parents, and retrieves lost data from one of its patching parents. Any end host that has the requested video content can be a patching parent. Several parent selection algorithms are proposed and evaluated in this paper. This architecture relieves server load by completely shifting video patching responsibility to the client side. Video content is replicated in multiple locations across the overlay network to provide fast and timely data recovery. Cooperative patching is especially advantageous for legacy video systems, since it does not require modification of the video server. Simulation experiments demonstrate that our design can achieve continuous video streaming with moderate cost.

Many applications can benefit from knowledge of latency between hosts. Recently, there have been proposals such as global network positioning (GNP) (T. S. E. Ng et al., 2002) and Internet coordinate system (ICS) (H. Lim et al., 2003) that attempt to provide this for hosts on the Internet. The schemes work by using a small set of nodes called "landmarks" to compute the coordinates of other hosts. We investigate the effect of placement of landmarks on the performance of these proposals. We show that with random placement, the estimation error of these schemes varies widely. We propose heuristics for placing landmarks that show good performance. We also investigate the behaviour of these schemes with measurement errors and show that GNP is less affected by measurement errors than ICS.

Mobile Ad Hoc Networks (MANETs) provide rapidly deployable and self-configuring network capacity required in many critical applications, e.g., battlefields, disaster relief and wide area sensing. In this paper we study the problem of efficient data delivery in sparse MANETs where network partitions can last for a significant period. Previous approaches rely on the use of either long range communication which leads to rapid draining of nodes' limited batteries, or existing node mobility which results in low data delivery rates and large delays. In this paper, we describe a Message Ferrying (MF) approach to address the problem. MF is a mobility-assisted approach which utilizes a set of special mobile nodes called message ferries (or ferries for short) to provide communication service for nodes in the deployment area. The main idea behind the MF approach is to introduce non-randomness in the movement of nodes and exploit such non-randomness to help deliver data. We study two variations of MF, depending on whether ferries or nodes initiate proactive movement. The MF design exploits mobility to improve data delivery performance and reduce energy consumption in nodes. We evaluate the performance of MF via extensive ns simulations which confirm the MF approach is efficient in both data delivery and energy consumption under a variety of network conditions.

The performance of large-scale wireless ad hoc networks is often limited by the broadcasting nature of the wireless medium and the inherent node energy constraints. While the impact of the former on network capacity extensively studied extensively in the literature, the impact of energy constraints has not received much attention. In this paper, we study the capacity limitations resulting from the energy supplies in wireless nodes. We define the energy-limited capacity of a wireless network as the maximum amount of data the network can deliver before the nodes run out of energy. This energy-limited capacity is an important parameter in networks where operating lifetime is critical, such as ad hoc networks deployed in hazardous environments and sensor networks. We study two types of static networks, networks without any infrastructure support and networks where base stations with unlimited energy are deployed to support data forwarding. We consider two kinds of traffic models motivated by ad hoc networks and sensor networks. We derive upper and lower bounds on the energy-limited capacity of these networks. While throughput has been shown to not scale with node density in static networks by previous studies, our results show that, depending on the energy consumption characteristics of wireless communication, the energy-limited capacity can scale well under both traffic models. In addition, we show that the deployment of base stations can improve the energy-limited capacity of the network, especially for networks with sensor traffic.

Models for network topology form a crucial component in the analysis of protocols. This paper systematically investigates a variety of evolutionary models for autonomous system (AS) level Internet topology. Evolution-based models produce a topology incrementally, attempting to reflect the growth patterns of the actual topology. While evolutionary models are appealing, they have generally not agreed as closely with measurements of real data as non-evolutionary models. We attempt to understand what factor contributes to a "good" evolutionary model. Our systematic study consists of a relatively generic evolutionary model framework, which we populate with different choices for the components. This allows us to compare a variety of instances of models to measurements from real data sets. We study issues such as the initial topology, the type of preferential connectivity used when adding edges, and the role of "growth" edges added between existing nodes. We find that appropriate instantiation of the framework can provide topologies that agree closely with real data. We also use our work to highlight several crucial open problems in topology modeling.

Spectral analysis of the Internet topology at the autonomous system (AS) level, by adapting the standard spectral filtering method of examining the eigenvectors corresponding to the largest eigenvalues of matrices related to the adjacency matrix of the topology is performed. We observe that the method suggests clusters of ASs with natural semantic proximity, such as geography or business interests. We examine how these clustering properties vary in the core and in the edge of the network, as well as across geographic areas, over time, and between real and synthetic data. We observe that these clustering properties may be suggestive of traffic patterns and thus have direct impact on the link stress of the network. Finally, we use the weights of the eigenvector corresponding to the first eigenvalue to obtain an alternative hierarchical ranking of the ASs.

In the current Internet, many applications start sessions with multiple connections to multiple servers in order to expedite the reception of data. One may argue that such aggressive behavior leads to unfair sharing of bandwidth using the current per-connection rate allocation methods. Sessions with more connections get a higher total rate than competing sessions with fewer connections. In this paper, we explore the issue of fairness of rate allocation from a session point of view. We define a multipoint-to-point session as a set of point-to-point connections started from multiple servers to a client in order to transfer an application-level object. We present session fairness definitions, propose algorithms to achieve these definitions, and compare the resulting allocations with the traditional connection fair algorithm. It is clear from our evaluations that the session fair algorithms proposed achieve a more fair distribution of session rates than the connection fair algorithm, by redistributing the rates claimed by sessions with more connections. We present some initial thoughts on the challenges involved in implementing the session fair algorithms proposed.

Quality-of-service (QoS) techniques and server replication are two complementary approaches that can improve the performance observed by users. QoS techniques provide differentiated service to meet the diverse needs of applications; server replication enables load balancing across a set of servers. To combine the two approaches, we need to address one important question: how to select a server among a replicated set that satisfies the user QoS requirement. We propose a probing-based protocol to discover network resources and make reservations for requests in differentiated service networks. This approach optimizes network resource utilization with reasonable signaling overhead. Furthermore, we compare five heuristics that can be used for server selection. We also investigate two methods that can reduce probing overhead, namely caching and the technique of probing from a subset of servers.

In this paper we examine a high speed wireless access network and present traffic patterns and on-line behavior for wireless users. To date, wireless network studies have largely focused on cellular voice technologies and architectures. Here we present an analysis of data collected from an authenticated campus area access network providing both wireless 802.11b and walk-up Ethernet capabilities through an authenticated access network service. We present an analysis of session data, transport layer flow data, and movement data taken from 109 wireless access points spread across 18 buildings. Local area wireless network (LAWN) wireless services support about 444 wireless hosts, 765 current users, and have sustained more than a million TCP flows over the nearly two month collection period.

DNS is a critical component of the operation of Internet applications. However, DNS performance in the wide-area is not well understood. A number of studies present DNS performance measurements [1], [2], [3], [4], but the measurements are out of date, are not collected at client locations (e.g., they are taken at root servers), or are collected at very few client locations.In this paper we present the largest known study of wide-area DNS performance at clients. We use data obtained under a variety of network environments such as location in the Internet topology, connection technology and client ISP. We identify DNS system performance measures and investigate the degree to which they vary from site to site. We report on measures that are relatively consistent throughout the system such as the fraction of names whose lookups succeed, and those that vary widely, such as overall response times and response times from root and gTLD servers. We also discuss the impact of some of these measures on DNS performance for non-cached domain names, confirming some current notions about DNS operation while challenging others.

A Video-on-Demand (VoD) service offers a large selection of videos from which customers can choose. Designers of VoD systems strive to achieve low access latency for customers. One approach that has been investigated by several researchers allows the server to batch clients requesting the same video and to serve clients in the same batch with one multicast video stream. This approach has the advantage that it can save server resources as well as server access and network bandwidth, thus allowing the server to handle a large number of customers without sacrificing access latency. VoD server replication is another approach that can allow a VoD service to handle a large number of clients, albeit at the additional cost of providing more servers. While replication is an effective way to increase the service capacity, it needs to be coupled with appropriate selection techniques in order to make efficient use of the increased capacity. In this paper, we investigate the design of server selection techniques for a system of replicated batching VoD servers. We design and evaluate a range of selection algorithms as they would be applied to three batching approaches: Batching with Persistent Channel Allocation, Patching, and Hierarchical Multicast Stream Merging (HMSM). We demonstrate that server replication combined with appropriate server selection scheme can indeed be used to increase the capacity of the service leading to improved performance.

In the current Internet, Web content is increasingly being cached closer to the end user to reduce network and Web server load and improve performance. Existing Web caching systems typically cache entire Web documents and attempt to keep them consistent with the origin server. This approach works well for text and images; for bandwidth intensive multimedia data such as audio and video, caching entire documents is not cost effective and does not scale. An alternative approach is to cache parts of the multimedia stream on different caches in the network and coordinate stream playback from these independent caches. From the perspective of the clients, the collection of cooperating distributed caches acts as a single fault tolerant, scalable cache. In this paper, we focus on data placement and replacement techniques for such co-operating distributed caches. Specifically, we propose the following new schemes that work together. 1) A family of distributed layouts, consisting of two layouts, namely RCache and Silo. The RCache layout is a simple, randomized, easy-to-implement layout that distributes constant length segments of a clip among caches and provides modest storage efficiency. The Silo scheme improves upon RCache; it accounts for long term clip popularity and intraclip segment popularity metrics and provides parameters to tune storage efficiency, server load, and playback switch-overs. 2) Rainbow, a local data replacement scheme based on the concept of segment access potential that accurately captures the popularity metrics. 3) Caching Token, a dynamic global data replacement or redistribution scheme that exploits existing data in distributed caches to minimize data distribution overhead. Our schemes optimize storage space, startup latency, server load, network bandwidth usage, and overhead from playback switch-overs. Our analytical and simulation results show that the silo scheme provides three to eight times higher cache hit ratio than a comparable traditional Web caching system that has the same amount of storage space.

We formulate and investigate fundamental problems that arise when multicast servers, that deliver content to multiple clients simultaneously, are replicated to enhance scalability and performance. Our study consists of two parts. First, we consider the problem under the assumption that the multicast clients are static for the duration of the multicast content distribution session. In this context, we examine two models for server behavior: fixed-rate servers, which transmit at a constant rate, and rate-adaptive servers, which adapt their transmission rate based on network conditions and/or feedback from clients. In both cases, we show that general versions of the client assignment problems are NP-hard. We then develop and evaluate efficient algorithms for interesting special cases, as well as heuristics for general cases. Second, we consider the case in which the set of clients changes dynamically during the multicast content distribution session. We again consider both fixed-rate and rate-adaptive servers. We formulate the problem as a Markov decision process, capturing the costs associated with trees, as well as the transition costs to dynamically change the trees. We use the properties of optimal solutions for small examples to develop a set of dynamic server selection heuristics.

Multicast communication enables a server to send content to multiple clients at the same time through a multicast tree. To deal with the heterogeneity of client capacities, multiple multicast groups can be used to allocate clients with similar capacity to the same group, so that the performance perceived by clients can be improved. We investigate the problem of allocating clients to constrained multicast servers, which, similar to clients, have different capacities. We explore some interesting issues raised by the constraints and propose an optimal solution to the allocation problem. We evaluate the solution and show substantial performance gain for our algorithm over those considering the server constraints separately.

Understanding network traffic from operational networks is critical to the design and evaluation of network protocols. We present analysis of a data set comprised of eight months of RADIUS authentication data taken from a large national dial-up Internet Service Provider (ISP). We present basic statistics, including session counts based on time-of-day, session length distribution, session inter-arrival times, and growth in the customer base over the measurement period. We investigate more deeply several properties of the data. We use area code information to correlate account location with basic statistics. For example, we find that United States west coast accounts tend to have earlier-than-average mean session start time. We find that 40% of sampled accounts exhibit concurrent sessions (two or more sessions active at the same time), while 20% show multiple originating phone numbers. Both phenomenon are likely to increase as users become more mobile and sophisticated. Finally, we offer evidence of significant session activity due to hypothesized automated processes, characterized by periodic interarrival times and/or constant session durations. Our results provide important data for the simulation and modeling of access network protocols and applications. They may also form the basis for creating a workload model of access networks.

As the Internet has grown in size and diversity of applications, two trends have emerged to provide good end-user perceived performance. First, servers are often replicated for better scalability of the service. Second, QoS approaches, such as the differentiated services framework, have been proposed as enhancement to the best-effort IP service. We are interested in the combination of these two trends; that is, replicated servers in QoS-based networks. We focus on the problem of selecting amongst replicated servers in the context of differentiated service networks. Our contributions are twofold. First, we design a QoS-based server-selection architecture. The architecture is scalable in the sense that server selection and resource reservation are done in an aggregated fashion and operate in the background, rather than being driven by individual client demand. At the same time, the architecture offers a fast response time to client requests for server selection. Second, we explore the design space implied by the architecture and evaluate various design options including signalling protocols, server selection/sorting algorithms and resource reservation granularity.

One way to attack the problem of growing routing tables in networks is hierarchical addressing. When addresses are distributed manually by the network administrator, maintaining a good hierarchical address allocation can be difficult, especially if the domain is large. This paper presents a protocol to self-organize a routing domain with hierarchical addresses that are closely matched to the underlying network topology. Once the protocol assigns addresses, we examine the shortest-path routing tables for every router. Our studies indicate that 95% of the routing tables calculated are within one entry of optimal, where an optimal routing table is defined as one entry per next-hop router. In addition, these results are robust across networks of various sizes and in networks with various numbers of cycles. The protocol's address allocation is efficient, with minimal waste of address space. Furthermore, our experiments indicate that the choice of which router initiates the protocol does not significantly affect the quality of the resulting routing tables nor the efficiency of the address allocation.

Load balancing is a key technique for improving Internet performance. Effective use of load balancing requires good traffic distribution schemes. We study the performance of several hashing schemes for distributing traffic over multiple links while preserving the order of packets within a flow. Although hashing-based load balancing schemes have been proposed in the past, this is the first comprehensive study of their performance using real traffic traces. We evaluate five direct hashing methods and one table-based hashing method. We find that hashing using a 16-bit CRC over the five-tuple gives excellent load balancing performance. Further, load-adaptive table-based hashing using the exclusive OR of the source and destination IP addresses achieves comparable performance to the 16-bit CRC. Table-based hashing can also distribute traffic load according to unequal weights. We also report on four other schemes with poor to moderate performance.

Fair bandwidth sharing at routers has several advantages, including protection of well-behaved flows and possible simplification of end-to-end congestion control mechanisms. Traditional mechanisms to achieve fair sharing (e.g., weighted fair queueing, flow random early discard) require per-flow state to determine which packets to drop under congestion, and therefore are complex to implement at the interior of a high-speed network. In recent work, Stoica et al., (1998), have proposed core-stateless fair queueing (CSFQ), a scheme to approximate fair bandwidth sharing without per-flow state in the interior routers. In this paper, we also achieve approximate fair sharing without per-flow state, however our mechanism differs from CSFQ. Specifically, we divide each flow into a set of layers, based on rate. The packets in a flow are marked at an edge router with a layer label (or "color"). A core router maintains a color threshold and drops layers whose color exceeds the threshold. Using simulations, we show that the performance of our rainbow fair queueing (RFQ) scheme is comparable to CSFQ when the application data does not contain any preferential structure. RFQ outperforms CSFQ in goodput when the application takes advantage of the coloring to encode preferences.

A number of important questions remain concerning the scalability of networks with quality of service guarantees. We consider one of these questions: can QoS routing protocols scale to large networks? To address this question, we evaluate the performance of techniques that can reduce the QoS routing protocol overhead. We specifically focus on topology aggregation, which can reduce overhead by orders of magnitude. We also investigate the interaction of topology aggregation with other important factors that contribute to performance, such as routing update frequency, routing algorithms, and network configuration. Our experiments are based on simulations of relatively large, structured networks. Among our observations, we find-contrary to intuition-that topology aggregation does not always have a negative impact on routing performance. Aggregation can reduce the routing information fluctuation, increase stability, and thus benefit routing performance. We also propose two new methods of aggregating routing information. Our hybrid aggregation method performs much better than conventional star aggregation and approaches unaggregated performance. Our weighted aggregation method, while intuitively appealing, offers mixed performance across topologies.

Multicast applications can involve a large number of receivers with heterogeneous data reception capabilities. In a traditional single-rate multicast session, the transmission rate at the source is chosen to match the lowest capacity path to a receiver in the session. This can cause an under-utilization of higher capacity paths to other receivers. We have previously defined an inter-receiver fairness measure in order to quantify the effect of this underutilization. We also developed protocols that use this measure to guide the choice of the source rate for a single-rate session. In this paper we design and develop a multi-rate protocol in the context of an ATM ABR service to achieve better inter-receiver fairness for a multicast session. The multi-rate protocol we investigate is based on the use of destination set grouping (DSG) where the set of receivers in a multicast session is partitioned into disjoint subgroups. The transmitter carries a separate conversation with each subgroup. Based on a number of grouping heuristics, the DSG protocol attempts to find the partitioning of the receivers that maximizes the inter-receiver fairness of the session. The DSG protocol can result in a session receiving a higher bandwidth allocation when it is split into multiple connections. We address this issue by proposing a mechanism in which the connections split from a single multicast session are treated as a single aggregated-allocation connection (AAC). A set of examples demonstrate the effectiveness of the DSG scheme incorporating the AAC technique on improving inter-receiver fairness for multicast ABR sessions.

Bowman is an extensible platform for active networking: it layers active networking functionality in user space software over variants of the System V UNIX operating system. The packet processing path implemented in Bowman incorporates an efficient and flexible packet classification algorithm, supports multi-threaded per-flow processing, and utilizes real time processor scheduling to achieve deterministic performance in the user-space. In this paper we describe the design and implementation of Bowman; discuss the support that Bowman provides for implementing execution environments for active networking; discuss the network-level architecture of Bowman that can be used to implement virtual networks; and present performance data showing that Bowman is able to sustain 100 Mbps throughput while forwarding IP packets over fast Ethernets.

Server replication improves the ability of a service to handle a large number of clients. One of the important factors in the efficient utilization of replicated servers is the ability to direct client requests to the "best" server, according to some optimality criteria. In the anycasting communication paradigm, a sender communicates with a receiver chosen from an anycast group of equivalent receivers. As such, anycasting is well suited to the problem of directing clients to replicated servers. This paper examines the definition and support of the anycasting paradigm at the application-layer, providing a service that uses an anycast resolver to map an anycast domain name and a selection criteria into an IP address. By realizing anycasting in the application-layer, we achieve flexibility in the optimization criteria and ease the deployment of the service. As a case study, we examine the performance of our system for a key service: replicated Web servers. To this end, we develop an approach for estimating the response time that a client will experience when accessing given servers. Such information is maintained in the anycast resolver that clients query to obtain the identity of the server with the best estimated response time. Our performance collection technique combines server push with resolver probes to estimate the expected response time without undue overhead. Our experiments show that selecting a server using our architecture and estimation technique can improve the client response time by a factor of two over nearest server selection and by a factor of four over random server selection.

In this paper we investigate multicast server selection problems. First we give a definition of the static multicast server selection problem, in which we assume a set of static clients and multicast servers and consider how one might produce an optimal allocation of the clients to the servers. We use a transformation method for deriving multicast server selection algorithms from traditional multicast routing algorithms. To investigate the dynamic behavior of client join and leave and the cost incurred during the process, we next define the dynamic multicast server selection problem, in which the clients join and leave the multicast session dynamically. The goal is to produce an optimal allocation of clients to servers with an emphasis on how this allocation behaves over time. We formulate the problem as a Markovian decision process (MDP). Our analysis of the problem leads to two heuristics which we use to propose a simple selection algorithm. Our simulation compares the performance of our proposed algorithm with other multicast server selection algorithms.

We consider the use of an application-layer performance measure-the utility-in the context of bandwidth allocation for an available bit rate service. This bandwidth allocation scheme can be viewed as a generalization of traditional available bit rate service; the scheme is equivalent to bandwidth max-min allocation when the utility of all applications are equal. The goal of the allocation scheme is to provide a good application-layer service to a wide diversity of applications sharing available bandwidth. We achieve this goal while also supporting changes in utility over time, tolerating some inaccuracy in utility function specification, and addressing the issue of circumvention through pricing.

A key technique for allowing servers to handle a large volume of requests for file transfers is to multicast the data to the set of requesting clients. Typically the paths from the server to the clients will be heterogeneous in bandwidth availability. Multiple-channel multicast (MCM) is an approach that can be used to handle this heterogeneity. In this approach the data is multicast over multiple channels, each addressed as a separate multicast group. Each receiver subscribes to a set of channels (i.e., joins the corresponding multicast groups) commensurate with its own rate capabilities. Of particular interest in the design of MCM schemes is the scheduling of data transmission across the multiple channels to accommodate asynchronous requests from clients. In this paper we present and analyze a new multiple-channel multicast approach called partition organization scheduling. The scheme is designed to result in good reception efficiency when compared to existing proposals while improving on their performance when other measures of interest are considered.

We present a technique to enable the efficient simulation of large scale ATM networks, while preserving the accuracy of the end-to-end delay statistics. Our approach uses on-the-fly aggregation by observing traffic at monitoring points, then substituting an aggregate model, when appropriate. We focus in particular on the end-to-end delay distribution, given the importance of this distribution for continuous media. We find that our methods are able to achieve speedup of one order of magnitude, while maintaining accuracy within 5% of the unaggregated simulation. These results are observed in both a series of multiplexers and a 100-switch wide-area ATM topology.

A wide variety of applications, including traditional data transfer and adaptive real-time multimedia, can potentially use the ATM available bit rate service. While these applications all share the ability to adapt their rate, they otherwise may have very different characteristics. The goal of this paper is to examine routing algorithms in the context of two different classes of best-effort applications: data-driven and real-time. We propose three new routing algorithms and compare them to algorithms from the literature using global and per-connection metrics. We demonstrate that the performance of a given routing algorithm is quite sensitive to the class of application. For real-time connections, routing algorithms that prefer shorter routes show better results. For data-driven applications, routing algorithms that try to balance allocated bandwidth and length of routes perform better. We further show that our new subgraphing algorithm consistently performs best for real-time applications on nearly all metrics.

Hierarchical addresses are fundamental to the scalability of Internet routing. The explosive of the Internet has strained the initial two-level hierarchy and led to the development of more flexible divisions between levels (CIDR) and larger addresses (IPv6). Equally, important are algorithms and protocols to systematically assign addresses with appropriate hierarchical structure to allow route aggregation. This paper describes and analyzes two algorithms for clustering network nodes into a multi-level address hierarchy. We evaluate the resulting address assignment with respect to routing table size, path length and concentration of traffic. We also explicitly recognize the need for "robustness" or "slack" the assignment to accommodate future changes in topology. Our evaluation includes both single- and multi-domain topologies.

Active networks allow users to "program" the network infrastructure, by injecting information that describes or controls a distributed algorithm to be executed for the user by the network infrastructure. The nature of the services that can be implemented with such a facility is determined by the programming interface to the active network, i.e. the set of abstractions it exposes to users. The complexity of this interface may range from a few simple parameters to a completely general programming language. We present a model that supports reasoning independently about the correctness of both the underlying active network platform and the algorithms injected into it, in a manner that admits the full range of possible programming interfaces. The model is described without relying on any particular formalism. The interaction between the underlying platform and the user injected program is captured in a specialized form of program composition that allows properties of each to be preserved. The use of the model is illustrated via an example dealing with mobility. For the example, we use the UNITY formalism to be more precise about the programs and properties that are preserved.

A substantial fraction of all network traffic today comes from applications in which clients retrieve objects from servers. The caching of objects in locations "close" to clients is an important technique for reducing both network traffic and response time for such applications. In this paper we consider the benefits of associating caches with switching nodes throughout the network, rather than in a few locations. We also consider the use of various self-organizing or active cache management strategies for organizing cache content. We evaluate caching techniques using both simulation and a general analytic model for network caching. Our results indicate that in-network caching can make effective use of cache space, and in many cases self-organizing caching schemes yield better average round-trip latencies than traditional approaches, using much smaller per-node caches.

Server replication is an approach often used to improve the ability of a service to handle a large number of clients. One of the important factors in the efficient utilization of replicated servers is the ability to direct client requests to the best server, according to some optimality criteria. In this paper we target an environment in which servers are distributed across the Internet, and clients identify servers using our application-layer any-casting service. Our goal is to allocate servers to clients in a way that minimizes a client's response time. To that end, we develop an approach for estimating the performance that a client would experience when accessing particular servers. Such information is maintained in a resolver that clients can query to obtain the identity of the server with the best response time. Our performance collection technique combines server push with client probes to estimate the expected response time. A set of experiments is used to demonstrate the properties of our performance determination approach and to show its advantages when used within the application-layer anycasting architecture.

In a multicast ABR service, a connection is typically restricted to the rate allowed on the bottleneck link in the distribution tree from the source to the set of receivers. Because of this, receivers in the connection can experience inter-receiver unfairness, when the preferred operating rates of the receivers are different. In this paper we explore the issue of improving the inter-receiver fairness in a multicast ABR connection by allowing the connection to operate at a rate higher than what is allowed by the multicast tree's bottleneck link. Since this can result in cell loss to some receivers, we operate with the knowledge of each receiver's application-specific loss tolerance. The multicast connection rate is not allowed to increase beyond the point where the cell loss on a path to a receiver exceeds this receiver's loss tolerance. Based on these ideas we develop an inter-receiver fairness measure and a technique for determining the rate that maximizes this measure. We show possible switch algorithms that can be used to convey the parameters needed to compute the function to the connection's source. In addition we develop a global network measure that helps us assess the effect of increasing inter-receiver fairness on the total network delivered throughput. We also briefly explore improving inter-receiver fairness through the use of multiple virtual circuits to carry traffic for a single multicast session. A set of examples demonstrate the use of the inter-receiver fairness concept in various network scenarios.

Active networking is the placement of user-controllable computing functionality in the switching nodes of a network. The end-to-end argument states that functions should be placed "in" the network only if they can be cost-effectively implemented there. We argue that active networking is a natural consequence of the end-to-end argument, because certain functions can be most effectively implemented with information that is only available inside the network. We propose a performance model for quantifying the benefit of implementing a particular functionality solely in the end system versus implementing it through a combination of end system and network support. We show how the model applies to specific services, including congestion control and reliable multicast.

An available bit rate (ABR) service allows applications to access a time-varying network capacity. In a basic ABR service the available network capacity is divided "fairly" amongst active connections, without regard to the utility that each application derives from the bandwidth allocation. The goal of this paper is to improve both the global and individual utility obtained by applications using ABR, as compared to standard max-min bandwidth allocation. The key to our novel ABR algorithm is to relax the requirement for short-term fair bandwidth allocation, allowing an allocation that trades bandwidth between applications to increase the overall utility. To increase the utility of each individual application, we also re-allocate the bandwidth on the usual ABR time interval. This re-allocation increases the long-term average utility obtained by each individual application; it also ensures that the longer term average bandwidth allocated to each application is equal to the max-min allocation.

The anycasting communication paradigm is designed to support server replication by allowing applications to easily select and communicate with the "best" server, according to some performance or policy criteria, in a group of content-equivalent servers. We examine the definition and support of the anycasting paradigm at the application layer, providing a service that maps anycast domain names into one or more IP addresses using anycast resolvers. In addition to being independent from network-layer support, our definition includes the notion of filters, functions that are applied to groups of addresses to affect the selection process. We consider both metric-based filters (e.g., server response time) and policy-based filters.

Graphs are commonly used to model the topological structure of internetworks in order to study problems ranging from routing to resource reservation. A variety of graphs are found in the literature, including fixed topologies such as rings or stars, "well-known" topologies such as the ARPAnet, and randomly generated topologies. While many researchers rely upon graphs for analytic and simulation studies, there has been little analysis of the implications of using a particular model or how the graph generation method may affect the results of such studies. Further, the selection of one generation method over another is often arbitrary, since the differences and similarities between methods are not well understood. This paper considers the problem of generating and selecting graphs that reflect the properties of real internetworks. We review generation methods in common use and also propose several new methods. We consider a set of metrics that characterize the graphs produced by a method, and we quantify similarities and differences among several generation methods with respect to these metrics. We also consider the effect of the graph model in the context of a specific problem, namely multicast routing.

Graphs are commonly used to model the structure of internetworks, for the study of problems ranging from routing to resource reservation. A variety of graph models are found in the literature, including regular topologies such as rings or stars, "well-known" topologies such as the original ARPAnet, and randomly generated topologies. Less common is any discussion of how closely these models correlate with real network topologies. We consider the problem of efficiently generating graph models that accurately reflect the topological properties of real internetworks. We compare the properties of graphs generated using various methods with those of real internets. We also propose efficient methods for generating topologies with particular properties, including a transit-stub model that correlates well with the internet structure. Improved models for the internetwork structure have the potential to impact the significance of simulation studies of internetworking solutions, providing a basis for the validity of the conclusions.

Multicast routing is an important topic of both theoretical and practical interest. Several proposed multicast routing algorithms involve the designation of one or more network nodes as the "center" of the routing tree for each multicast group. The choice of this designated router (which we refer to as the "core") influences the shape of the multicast routing tree, and thus influences the performance of the routing scheme. We investigate the relationship between the choice of core and three performance measures. Specifically, we compare various methods of selecting a core with respect to their effect on the bandwidth, delay, and traffic concentration. We conclude that simple methods are adequate for widely distributed groups, but that the addition of group information can be leveraged to improve performance especially when the group is small or exhibits a high degree of locality. We also conclude that core choice can be used to control traffic concentration, in fact traffic concentration effects can be ameliorated by appropriate core choice policies.

Generalized connectors provide the capability to connect a single input to one or more outputs. Such networks play an important role in supporting any application that involves the distribution of information from one source to many destinations or many sources to many destinations. The authors present the first analytic model for evaluating blocking probability in generalized connectors. The model allows flexibility in specifying traffic fanout characteristics and network routing algorithms. Equations are derived for computing blocking probability for the important class of series-parallel networks. The authors investigate the accuracy of the equations by comparing the blocking probability computed using the equations to results from simulation.>

The authors present an improved model for evaluating blocking probability in generalized connectors. The new model extends an earlier result to allow more flexibility in specifying traffic fanout characteristics and network routing algorithms. Included as special cases are both the previous model and Pippenger's (1975) exact model for blocking in connectors. Equations are derived for computing the blocking probability for the class of series-parallel networks. They investigate the accuracy of the approximation by comparing the blocking probability computed using the equations with measured simulation data.>

A model for evaluating blocking probability in distribution networks is presented, and equations for computing blocking probability for the class of series-parallel networks are derived. The quotations are exact for pure series networks and approximate for parallel networks. The accuracy of the approximation is investigated by comparing the blocking probability computed using the equations to measured simulation data. The results indicate that for higher loads and larger switches the approximation is generally within 10% of the simulation results.>