With the rapid increase in online interactions, concerns over data privacy and transparency of data processing practices have become more pronounced. While regulations like the GDPR have driven the widespread adoption of cookie banners in the EU, India's Digital Personal Data Protection Act (DPDPA) promises similar changes domestically, aiming to introduce a framework for data protection. However, certain clauses within the DPDPA raise concerns about potential infringements on user privacy, given the exemptions for government accountability and user consent requirements. In this study, for the first time, we explore Indian Internet users' awareness and perceptions of cookie banners, online privacy, and privacy regulations, especially in light of the newly passed DPDPA. We conducted an online anonymous survey with 428 Indian participants, which addressed: (1) users' perspectives on cookie banners, (2) their attitudes towards online privacy and privacy regulations, and (3) their acceptance of 10 contentious DPDPA clauses that favor state authorities and may enable surveillance. Our findings reveal that privacy-conscious users often lack consistent awareness of privacy mechanisms, and their concerns do not always lead to protective actions. Our thematic analysis of 143 open-ended responses shows that users' privacy and data protection concerns are rooted in skepticism towards the government, shaping their perceptions of the DPDPA and fueling demands for policy revisions. Our study highlights the need for clearer communication regarding the DPDPA, user-centric consent mechanisms, and policy refinements to enhance data privacy practices in India.

We present Network Congestion Feedback (NCF), a novel congestion control framework that leverages programmable data planes for generating a rich congestion signal for use in the public Internet. NCF makes several contributions, including isolating ‘mice’ and ‘elephant’ flows using separate queues, detecting congestion in the elephants’ queue and generating a rich sub-RTT signal for the concerned senders, and designing a congestion-control algorithm (CCA) that matches a flow’s demands with supply (i.e., available bandwidth) for maximizing utilization and fairness. It extends two key ingredients from prior work on datacenter CCAs–a short control-loop delay and a precise congestion signal–that are crucial for designing an efficient, fair CCA, by adapting them for the more challenging Internet context. NCF isolates mice and elephant flows so that the former cannot unfairly degrade the throughput of the latter, and it guarantees that mice flows experience minimal round-trip times (RTTs) even when contending with elephant flows. NCF virtually eliminates slow-start spikes and achieves high fairness in both shallow and deep-buffer configurations, and even when the flows experience drastically different RTTs. Lastly, NCF offers low flow completion times (FCTs) to short flows even in challenging multiple-bottleneck scenarios.

Internet censorship is a well-explored area, typically focusing on Web censorship enacted by powerful nation-states like China and Russia. In this paper, we diverge from the norm and study the unexplored VoIP censorship prevalent in the Middle East for over a decade. We present the first research analyzing the VoIP filtering mechanics deployed nationwide. Based on extensive on-the-ground experiments, our investigation reveals novel censorship techniques for distinctly filtering VoIP traffic originating from specific apps.We meticulously analyze the VoIP traffic of nine popular apps and reveal the presence of sophisticated "middleboxes" placed within the local ISPs. These middleboxes possess the unique capability to selectively block the calling facility, leaving the rest of the apps’ features, such as texting and media sharing, completely unhindered. Unlike traditional Web filtering techniques that often require inspecting DNS and HTTP(s) traffic, our research demonstrates that the middlebox scrutinizes the STUN protocol requests and response packets to individually identify the application-specific VoIP call flow. Our analysis of widely used apps such as WhatsApp, Signal, and Facebook Messenger reveals a uniquely characterizable flow of STUN packets. We experimentally confirm that the censor exploits such fingerprints to block VoIP calls made through these apps. Furthermore, our experiments unveil additional nuances in censorship tactics. For apps like LINE, the middlebox searches for the VoIP server IP address in some selective packets. On a successful match, it drops the packets, effectively disrupting the call.In essence, our findings provide valuable insights into the intricate mechanisms of sophisticated VoIP filtering techniques, paving the way for more informed approaches to combating such censorship practices.

Numerous studies have explored SSH attacks, often focusing on specific botnet activities or providing short-term analyses of particular honeynets. In this paper, we present an analysis of data collected from a large-scale honeynet over a three-year period, shedding light on gradual shifts in attacker behavior. Our findings suggest a trend toward more exploratory attacks, with indications that attackers are increasingly moving beyond the blind execution of scripts.

In this paper, we revisit a fundamental discussion in the context of the Internet's future from the past decade: Is IPv6 harmful for DNS or not? As simple as this question may sound, until now, there is no clear recommendation to support DNS for authoritative and recursive name servers. RFC3901 is unchanged since 2004. We revisit the decades long history of this discussion, how it relates to choices regarding fragmentation (end-to-end in IPv6 vs. on-path in IPv4), limitations to Path MTU Discovery (PMTUD), and diverging security policies which suggest dropping IPv6 fragments. To address this question we gather an extensive dataset to capture zones' resolvability (for the top 10 million domains in the Google Chrome User Experience report) over time for different MTU and PMTUD scenarios. To scale our experiments we introduce 'unique name server sets', since fragmentation avoidance (RFC9715) and EDNS0 and TCP fallback capabilities are name server specific. Our results challenge prior work, demonstrating that: i) The negative impact of DNS resolution via IPv6 is negligible, even for DNSSEC enabled zones in a worst-case MTU/PMTUD scenario, ii) NS-Sets supporting DNSSEC are more likely to also support DNS resolution via IPv6, iii) Dropping or not dropping of fragments has negligible impact on IPv6 DNS resolution, and iv) Prior work missed the notable role of a single Tier-1 when determining how wide-spread IPv6 fragment dropping is. From our results, we argue that it is time to recommend that IPv6 SHOULD be used in the DNS.

The DNS, the Internet's address book, traditionally does not guarantee authenticity of data. The DNS Security Extensions (DNSSEC) exist to add cryptographic authenticity checks to the DNS. In spite of DNSSEC being over 30 years old, its widespread deployment has not yet come to fruition. Current work in the IETF tries automating the setup of DNSSEC, in the hopes of furthering its deployment.

Abstract The Domain Name System (DNS) is a cornerstone of the Internet. As such, it is often the subject or the means of network measurement studies. Over the past decades, the Internet measurement community gathered many lessons-learned and captured them in widely available measurement toolchains such as ZDNS and OpenINTEL as well as many papers. However, for feasibility, these tools often restrict DNS tree exploration, use caching, and other intricate methods for reducing query load. This potentially hides many corner cases and unforeseen problems. In this paper, we present a system capable of exploring the full DNS tree. We gather 87 TB of DNS data covering 812M domains with over 85B queries over 40 days. Using this data, we replicate four earlier studies that used feasibility and time-optimized DNS datasets. Our results demonstrate the need for care in selecting which limitations regarding the perspective on DNS can be accepted for a given research question and which may alter findings and conclusions.

In response to the ePrivacy Directive and the consent requirements introduced by the GDPR, websites began deploying consent banners to obtain user permission for data collection and processing. However, due to shared third-party services and technical loopholes, non-consensual cross-site tracking can still occur. In fact, contrary to user expectations of seemingly isolated consent, a user's decision on one website may affect tracking behavior on others. In this study, we investigate the technical and behavioral mechanisms behind these discrepancies. Specifically, we disclose a persistent tracking mechanism exploiting web cookies. These cookies, which we refer to as intractable, are initially set on websites with accepted banners, persist in the browser, and are subsequently sent to trackers before the user provides explicit consent on other websites. To meticulously analyze this covert tracking behavior, we conduct an extensive measurement study performing stateful crawls on over 20k domains from the Tranco top list, strategically accepting banners in the first half of domains and measuring intractable cookies in the second half. Our findings reveal that around 50% of websites send at least one intractable cookie, with the majority set to expire after more than 10 days. In addition, enabling the Global Privacy Control (GPC) signal initially reduces the number of intractable cookies by 30% on average, with a further 32% reduction possible on subsequent visits by rejecting the banners. Moreover, websites with Consent Management Platform (CMP) banners, on average, send 6.9 times more intractable cookies compared to those with native banners. Our research further reveals that even if users reject all other banners, they still receive a large number of intractable cookies set by websites with cookie paywalls. Additionally, our measurement on the partitioned cookies---cookies that are restricted to the top-level site and thus mitigate cross-site tracking---shows that only 1.3% of tracking cookies are marked as such, indicating their minimal impact on cross-site tracking via intractable cookies.

The proliferation of Illegal Movie Streaming Services (IMSS) has posed significant challenges to legitimate streaming services and law enforcement alike, causing financial losses and complicating efforts to combat copyright infringement. Motivated by the absence of a comprehensive list of IMSS, and recognizing that IMSS websites often have short-lived domains, we first introduce a methodology to detect IMSS sites. Our evaluation demonstrates that our method achieves a recall of 84.31% in identifying IMSS. Applying this method on the Tranco Top 1M domains, we find 283 new websites hosting IMSS. When characterizing the IMSS ecosystem, our findings reveal that four specific IMSS sites attract considerable attention, appearing in the Tranco Top 10K domains. Additionally, these sites employ complex redirection patterns, with one site using up to 11 hops to evade detection. Using Google Identifiers, we then uncover 11 cases of co-ownership, where multiple sites share the same identifiers, indicating common operation. Finally, by crawling IMSS sites from seven vantage points (VPs), we investigate online tracking practices on these services — an area that has previously lacked thorough investigation. We find that more than 95% of IMSS include at least one third-party tracker on their websites. Interestingly, tracker presence is lower in the European Union (EU) countries than in other VPs. Furthermore, third-party tracking cookies are not the primary mechanism on IMSS sites; instead, the more invasive and unavoidable fingerprinting techniques are predominantly used for tracking across different VPs.

Online messaging platforms are key communication tools but are vulnerable to fake news and conspiracy theories. Mainstream platforms such as Facebook are increasing content moderation of harmful and conspiratorial content. In response, users from fringe communities are migrating to alternative platforms like Telegram. These platforms offer more freedom and less intervention. Currently, Telegram is one of the leading messaging platforms hosting fringe communities. Despite the popularity, as a research community, we lack knowledge of how content spreads over this network. Motivated by the importance and impact of messaging platforms on society, we aim to measure the information propagation within fringe communities on the Telegram network, focusing on how public groups and channels exchange messages. We collect and explore about 140 million messages from 9,000 channels and groups on Telegram. We examine message forwarding and the lifetime of the messages from different aspects. Among other things, we find inequality in content creation; 6% of the users are responsible for 90% of forwarded messages. We also discover that while the forwarding feature considerably amplifies the reach of messages, the spread of content within our dataset remains largely localized. Additionally, we find that 5% of the channels are responsible for 40% of the forwarded messages in the entire dataset. Finally, our lifetime analysis shows that messages disseminated in groups with numerous active users exhibit significantly longer lifespans compared to those circulated in channels.

WhatsApp provides a fertile ground for the large-scale dissemination of information, particularly in countries like Brazil and India. Given its increasing popularity and use for political discussions, it is paramount to ensure that WhatsApp groups are adequately protected from attackers who aim to disrupt the activity of WhatsApp groups. Motivated by this, in this work, we characterize two types of attacks that may disrupt WhatsApp groups. We look into the flooding attack, where an attacker shares a large number of usually duplicate messages within a short period, and the hijacking attack, where attackers aim to obtain complete control of the group. We collect a large dataset of 19M messages shared in 1.6K WhatsApp public political groups from Brazil and analyze them to identify and characterize flooding and hijacking attacks. Among other things, we find that approximately 7% of the groups receive flooding attacks, which are usually short-lived (usually less than four minutes), and groups can receive multiple flooding attacks, even within the same day. Also, we find that most flooding attacks are executed using stickers (62% of all flooding attacks) and that, in most cases, attackers use both flooding and hijacking attacks to obtain complete control of the WhatsApp groups. Our work aims to raise user awareness about such attacks on WhatsApp and emphasizes the need to develop effective moderation tools to assist group administrators in preventing or mitigating such attacks.

Malware is recognized as one of the most severe cybersecurity threats today. Although malware attacks are as old as the Internet, our understanding of which part of the Internet infrastructure is used to distribute malware software is still rather limited.

In this study, we measure all root servers over a period of 174 days from 675 vantage points in 523 networks and 62 countries using IPv4 and IPv6. Using this data, we first investigate the co-location between root servers, finding that almost 70% of clients observe co-location of at least two servers. Second, we monitor the integrity of zone transfers, finding rare issues like bitflips or stale zone files. Finally, by enriching our data with passive ISP and IXP data, we quantify the role of IPv6 for performance and behavior under change, finding that even seemingly similar subsets of root servers can differ considerably.

The Internet relies on the Border Gateway Protocol (BGP)—a policy-based routing protocol—to establish routes. Each Autonomous System (AS) uses BGP to realize its routing policies based on the business agreements that they have with its neighboring ASes. ASes typically do not share their business agreements publicly. Another drawback of BGP is that ASes typically do not see the effects of their routing policies as this information is only visible within other ASes. Yet, for an AS to check their BGP configuration they need to see the effect. Thus, ASes collaborate and operate Looking Glasses (LGs) which are publicly accessible. LGs are websites that allow the users to query one or several routers within the ASes for routing information. This information may be restricted to BGP routes (routing prefix plus AS path) only or other BGP attributes as well, e.g., local preference, MED, and BGP communities. Such LG data is required by many BGP topology inference methods either as input or for validation. The dataset that this paper focuses on collects BGP attributes from more than 149 LGs in 154 ASes from 931 routers via scraping the LGs. Hereby, the difficulties relate to the non-uniformity of the LGs—most interfaces differ, the fluctuating accessibility of the LGs, as well as the different output formats. To overcome this we combined manual configuration with an automated scraping process followed by careful post-processing and manual checks. Our current dataset covers one and a half months of continuous data collection every 4 hours. In this paper, we describe both our collection pipeline as well as initial analysis results which focus on route diversity for ASes with multiple LGs. We find that up to 43% of these ASes use diverse routes to at least one of their peers. Routes can differ in local preference 40%, AS paths 37%, or BGP communities 41%. While the former is expected the latter is surprising.

Network operators require real-time traffic monitoring insights to provide high performance and security to their customers. It has been shown that artificial intelligence and machine learning (ML) can improve the visibility of telemetry systems, especially with encrypted traffic. However, current solutions cannot cope with high traffic rates and volumes in large-scale networks. To realize the ML-driven network intelligence paradigm at terabit scale, we design Marina, a system that spreads monitoring over a highly efficient data plane, which can extract traffic statistics at line rate, and a powerful ML server, which can run monitoring inference using complex ML models. We apply temporal microaggregation into sub-second time slots and extract moment-based statistics. These allow to flexibly obtain accurate ML-based monitoring decisions during the next time slot. To demonstrate the scalability of our design, we implement and evaluate a Marina data plane prototype on a Barefoot Wedge 100BF-65X P4 switch, which can monitor more than 520,000 concurrent flows at full switching capacity of 6.4 Tbps. We validate the analytics capabilities enabled by our Marina implementation for four ML-driven real-time monitoring tasks with a broad set of standard ML models, achieving comparable or better than state-of-the-art results.

Honeypots have been used for decades to detect, monitor, and understand attempts of unauthorized use of information systems. Previous studies focused on characterizing the spread of malware, e.g., Mirai and other attacks, or proposed stealthy and interactive architectures to improve honeypot efficiency.

Unsolicited traffic sent to advertised network space that does not host active services provides insights about misconfigurations as well as potentially malicious activities, including the spread of Botnets, DDoS campaigns, and exploitation of vulnerabilities. Network telescopes have been used for many years to monitor such unsolicited traffic. Unfortunately, they are limi the available address space for such tasks and, thus, limited to specific geographic and/or network regions.

Abstract DNS is one of the core building blocks of the Internet. In this paper, we investigate DNS resolution in a strict IPv6-only scenario and find that a substantial fraction of zones cannot be resolved. We point out, that the presence of an resource record for a zone’s nameserver does not necessarily imply that it is resolvable in an IPv6-only environment since the full DNS delegation chain must resolve via IPv6 as well. Hence, in an IPv6-only setting zones may experience an effect similar to what is commonly referred to as lame delegation. Our longitudinal study shows that the continuing centralization of the Internet has a large impact on IPv6 readiness, i.e., a small number of large DNS providers has, and still can, influence IPv6 readiness for a large number of zones. A single operator that enabled IPv6 DNS resolution–by adding IPv6 glue records–was responsible for around 20.3% of all zones in our dataset not resolving over IPv6 until January 2017. Even today, 10% of DNS operators are responsible for more than 97.5% of all zones that do not resolve using IPv6 .

We introduce a runtime verification framework for programmable switches that complements static analysis. To evaluate our approach, we design and developP6, a runtime verification system that automatically detects, localizes, and patches software bugs in P4 programs. Bugs are reported via a violation of pre-specified expected behavior that is captured byP6.P6is based on machine learning-guided fuzzing that tests P4 switch non-intrusively, i.e., without modifying the P4 program for detecting runtime bugs. This enables an automated and real-time localization and patching of bugs. We used aP6prototype to detect and patch existing bugs in various publicly available P4 application programs deployed on two different switch platforms, namely, behavioral model (bmv2) and Tofino. Our evaluation shows thatP6significantly outperforms bug detection baselines while generating fewer packets and patches bugs in large P4 programs, e.g.,switch.p4without triggering any regressions.

Knowing customer's interests, e.g. which Video-On-Demand (VoD) or Social Network services they are using, helps telecommunication companies with better network planning to enhance the performance exactly where the customer's interests lie, and also offer the customers relevant commercial packages. However, with the increasing deployment of CDNs by different services, identification, and attribution of the traffic on network-layer information alone becomes a challenge: If multiple services are using the same CDN provider, they cannot be easily distinguished based on IP prefixes alone. Therefore, it is crucial to go beyond pure network-layer information for traffic attribution.

Internet of Things (IoT) devices are becoming increasingly ubiquitous, e.g., at home, in enterprise environments, and in production lines. To support the advanced functionalities of IoT devices, IoT vendors as well as service and cloud companies operate IoT backends---the focus of this paper. We propose a methodology to identify and locate them by (a) compiling a list of domains used exclusively by major IoT backend providers and (b) then identifying their server IP addresses. We rely on multiple sources, including IoT backend provider documentation, passive DNS data, and active scanning. For analyzing IoT traffic patterns, we rely on passive network flows from a major European ISP.

Big data analytics platforms have played a critical role in the unprecedented success of data-driven applications. However, real-time and streaming data applications, and recent legislation, e.g., GDPR in Europe, have posed constraints on exchanging and analyzing data, especially personal data, across geographic regions. To address such constraints data has to be processed and analyzed in-situ and aggregated results have to be exchanged among the different sites for further processing. This introduces additional network delays due to the geographic distribution of the sites and potentially affecting the performance of analytics platforms that are designed to operate in datacenters with low network delays. In this paper, we show that the three most popular big data analytics systems (Apache Storm, Apache Spark, and Apache Flink) fail to tolerate round-trip times more than 30 milliseconds even when the input data rate is low. The execution time of distributed big data analytics tasks degrades substantially after this threshold, and some of the systems are more sensitive than others. A closer examination and understanding of the design of these systems show that there is no winner in all wide-area settings. However, we show that it is possible to improve the performance of all these popular big data analytics systems significantly amid even transcontinental delays (where inter-node delay is more than 30 milliseconds) and achieve performance comparable to this within a datacenter for the same load.

Amplification Distributed Denial of Service (DDoS) attacks' traffic and harm are at an all-time high. To defend against such attacks, distributed attack mitigation platforms, such as traffic scrubbing centers that operate in peering locations, e.g., Internet Exchange Points (IXP), have been deployed in the Internet over the years. These attack mitigation platforms apply sophisticated techniques to detect attacks and drop attack traffic locally, thus, act as sensors of attacks. However, it has not yet been systematically evaluated and reported to what extent coordination of these views by different platforms can lead to more effective mitigation of amplification DDoS attacks. In this paper, we ask the question: "Is it possible to mitigate more amplification attacks and drop more attack traffic when distributed attack mitigation platforms collaborate?"

Delivering videos under less-than-ideal network conditions without compromising end-users' quality of experiences is a hard problem. Virtually all prior work follow a piecemeal approach---either "tweaking" the fully reliable transport layer or making the client "smarter." We propose VOXEL, a cross-layer optimization system for video streaming. We use VOXEL to demonstrate how to combine application-provided "insights" with a partially reliable protocol for optimizing video streaming. To this end, we present a novel ABR algorithm that explicitly trades off losses for improving end-users' video-watching experiences.

The business relationships between Autonomous Systems (ASes) can provide fundamental insights into the Internet's routing ecosystem. Throughout the last two decades, many works focused on how to improve the inference of those relationships. Yet, it has proven difficult to assemble extensive ground-truth data sets for validation. Therefore, more recent works rely entirely on relationships extracted from BGP communities to serve as "best-effort" ground-truth. In this paper, we highlight the shortcomings of this trend. We show that the best-effort validation data does not cover relationships between ASes within the Latin American (LACNIC) service region even though ~14% of all inferred relationships are from that region. We further show that the overall precision of 96-98 % for peering relationships achieved by three of the most prominent algorithms can drop by 14-25 % when considering only peering relationships between Tier-1 and other transit providers. Finally, we discuss potential ways to overcome the presented challenges in the future.

We design, develop, and evaluate P6, an automated approach to (a) detect, (b) localize, and (c) patch software bugs in P4 programs. Bugs are reported via a violation of pre-specified expected behavior that is captured by P6. P6 is based on machine learning-guided fuzzing that tests P4 switch non-intrusively, i.e., without modifying the P4 program for detecting runtime bugs. This enables an automated and real-time localization and patching of bugs. We used a P6 prototype to detect and patch existing bugs in various publicly available P4 application programs deployed on two different switch platforms: behavioral model (bmv2) and Tofino. Our evaluation shows that P6 significantly outperforms bug detection baselines while generating fewer packets and patches bugs in large P4 programs such as switch.p4 without triggering any regressions.

In this talk, I will use multiple internet measurement studies as examples to outline the challenges that we face when performing internet-scale traffic analysis, including implications of the COVID-19 pandemic on internet traffic as well as detecting IoT devices through the lens of an ISP. Using this as motivation, I will discuss the challenges of working with network-wide flow data and correlating such data with other datasets.

With the recent IPv4 address exhaustion, many networks can no longer rely on requesting additional IPv4 addresses space. They resort to new ways to obtain addresses: buying and leasing. In this paper, we first shed light on the recent economic trends of the IPv4 buying market by augmenting transfer statistics with public and private pricing information from four large IPv4 brokers. We infer the size of the IPv4 leasing market through two different data sources: routing information observed from BGP collectors and RDAP databases operated by the Regional Internet Registries. We find that neither of those sources alone is capable of estimating the full market size. We relate our findings to discussions with 13 IPv4 brokers and summarize how networks handle their demand for obtaining IPv4 addresses in 2020.

There is a rich body of literature on measuring and optimizing nearly every aspect of the web, including characterizing the structure and content of web pages, devising new techniques to load pages quickly, and evaluating such techniques. Virtually all of this prior work used a single page, namely the landing page (i.e., root document, "/"), of each web site as the representative of all pages on that site. In this paper, we characterize the differences between landing and internal (i.e., non-root) pages of 1000 web sites to demonstrate that the structure and content of internal pages differ substantially from those of landing pages, as well as from one another. We review more than a hundred studies published at top-tier networking conferences between 2015 and 2019, and highlight how, in light of these differences, the insights and claims of nearly two-thirds of the relevant studies would need to be revised for them to apply to internal pages.

Due to the COVID-19 pandemic, many governments imposed lock-downs that forced hundreds of millions of citizens to stay at home. The implementation of confinement measures increased Internet traffic demands of residential users, in particular, for remote working, entertainment, commerce, and education, which, as a result, caused traffic shifts in the Internet core.

Online messaging platforms such as WhatsApp, Telegram, and Discord, each with hundreds of millions of users, are one of the dominant modes of communicating or interacting with one another. Despite the widespread use of public group chats, there exists no systematic or detailed characterization of these group chats. There is, more importantly, lack of a general understanding of how these (public) groups differ in characteristics and use across the different platforms. We also do not know whether the messaging platforms expose personally identifiable information, and we lack a comprehensive view of the privacy implications of leaks for the users.

Inbound traffic engineering (ITE)---the process of announcing routes to, e.g., maximize revenue or minimize congestion---is an essential task for Autonomous Systems (ASes). AS Path Prepending (ASPP) is an easy to use and well-known ITE technique that routing manuals show as one of the first alternatives to influence other ASes' routing decisions. We observe that origin ASes currently prepend more than 25% of all IPv4 prefixes.

Consumer Internet of Things (IoT) devices are extremely popular, providing users with rich and diverse functionalities, from voice assistants to home appliances. These functionalities often come with significant privacy and security risks, with notable recent large-scale coordinated global attacks disrupting large service providers. Thus, an important first step to address these risks is to know what IoT devices are where in a network. While some limited solutions exist, a key question is whether device discovery can be done by Internet service providers that only see sampled flow statistics. In particular, it is challenging for an ISP to efficiently and effectively track and trace activity from IoT devices deployed by its millions of subscribers---all with sampled network data.

As end-user devices often have multiple access networks available, choosing the most suitable network can help to improve application performance and user experience. However, selecting the best access network for HTTP Adaptive Streaming (HAS) is non-trivial, e.g., due to complex interactions between network conditions and the Adaptive Bit-Rate algorithm (ABR), which adapts to network conditions by selecting which video representation to load. In this paper, we propose to use an application-informed approach, Informed Access Network Selection (IANS), to select the most suitable access network for each video segment. We evaluate the impact of IANS on HAS performance in a testbed under a variety of network conditions and using different workloads. We find that IANS improves HAS performance substantially, in particular in cases where the available downstream capacity is low. In the Capacity Decrease scenario, where capacity decreases drastically during the video load, IANS can improve the estimated Mean Opinion Score (MOS) compared to using a single network from 2.1 to 2.8. We compare IANS to MPTCP using the Lowest-RTT-first scheduler, which continues to use a low downstream capacity network, resulting in lower performance. This confirms that IANS can improve video streaming performance.

Many network operations, ranging from attack investigation and mitigation to traffic management, require answering network-wide flow queries in seconds. Although flow records are collected at each router, using available traffic capture utilities, querying the resulting datasets from hundreds of routers across sites and over time, remains a significant challenge due to the sheer traffic volume and distributed nature of flow records. In this article, we investigate how to improve the response time for a priori unknown network-wide queries. We present Flowyager, a system that is built on top of existing traffic capture utilities. Flowyager generates and analyzes tree data structures, that we call Flowtrees, which are succinct summaries of the raw flow data available by capture utilities. Flowtrees are self-adjusted data structures that drastically reduce space and transfer requirements, by 75% to 95%, compared to raw flow records. Flowyager manages the storage and transfers of Flowtrees, supports Flowtree operators, and provides a structured query language for answering flow queries across sites and time periods. By deploying a Flowyager prototype at both a large Internet Exchange Point and a Tier-1 Internet Service Provider, we showcase its capabilities for networks with hundreds of router interfaces. Our results show that the query response time can be reduced by an order of magnitude when compared with alternative data analytics platforms. Thus, Flowyager enables interactive network-wide queries and offers unprecedented drill-down capabilities to, e.g., identify DDoS culprits, pinpoint the involved sites, and determine the length of the attack.

The conventional wisdom is that a software-defined network (SDN) operates under the premise that the logically centralized control plane has an accurate representation of the actual data plane state. Unfortunately, bugs, misconfigurations, faults or attacks can introduce inconsistencies that undermine correct operation. Previous work in this area, however, lacks a holistic methodology to tackle this problem and thus, addresses only certain parts of the problem. Yet, the consistency of the overall system is only as good as its least consistent part. Motivated by an analogy of network consistency checking with program testing, we propose to add active probe-based network state fuzzing to our consistency check repertoire. Hereby, our system, Pazz, combines production traffic with active probes to periodically test if the actual forwarding path and decision elements (on the data plane) correspond to the expected ones (on the control plane). Our insight is that active traffic covers the inconsistency cases beyond the ones identified by passive traffic. Pazz prototype was built and evaluated on topologies of varying scale and complexity. Our results show that Pazz requires minimal network resources to detect persistent data plane faults through fuzzing and localize them quickly while outperforming baseline approaches.

Today's end-user devices have multiple access networks available and can achieve better application performance by distributing traffic across access networks. However, matching application traffic to the most suitable access network or bundling them is non-trivial, given varying application needs and network performance characteristics. Therefore, we propose an application-informed approach for access network selection (IANS). Based on the size of a Web resource, we select the better access network in terms of latency and available downstream capacity. We implement IANS within our Socket Intents prototype and evaluate its benefits for Web page loads under a variety of network conditions and for various Web pages. IANS provides the highest speedups for scenarios with asymmetric network conditions and for scenarios with low downstream capacity. Here, IANS improves relevant Web metrics by between 500 and 1000 ms in the median, compared to using the better of the two access networks, and may also outperform MPTCP. This confirms that IANS improves application performance over using a single network and, in several scenarios, even using MPTCP.

Large content providers, known as hyper-giants, are responsible for sending the majority of the content traffic to consumers. These hyper-giants operate highly distributed infrastructures to cope with the ever-increasing demand for online content. To achieve commercial-grade performance of Web applications, enhanced end-user experience, improved reliability, and scaled network capacity, hyper-giants are increasingly interconnecting with eyeball networks at multiple locations. This poses new challenges for both (1) the eyeball networks having to perform complex inbound traffic engineering, and (2) hyper-giants having to map end-user requests to appropriate servers.

With the ongoing digitalization, an increasing number of sensors is becoming part of our digital infrastructure. These sensors produce highly, even globally, distributed data streams. The aggregate data rate of these streams far exceeds local storage and computing capabilities. Yet, for radical new services (e.g., predictive maintenance and autonomous driving), which depend on various control loops, this data needs to be analyzed in a timely fashion. In this position paper, we outline a system architecture that can effectively handle distributed mega-datasets using data aggregation. Hereby, we point out two research challenges: The need for (1) novel computing primitives that allow us to aggregate data at scale across multiple hierarchies (i.e., time and location) while answering a multitude of a priori unknown queries, and (2) transfer optimizations that enable rapid local and global decision making.

Network attacks, including Distributed Denial-of-Service (DDoS), continuously increase in terms of bandwidth along with damage (recent attacks exceed 1.7 Tbps) and have a devastating impact on the targeted companies/governments. Over the years, mitigation techniques, ranging from blackholing to policy-based filtering at routers, and on to traffic scrubbing, have been added to the network operator's toolbox. Even though these mitigation techniques provide some protection, they either yield severe collateral damage, e.g., dropping legitimate traffic (blackholing), are cost-intensive, or do not scale well for Tbps level attacks (ACL filtering, traffic scrubbing), or require cooperation and sharing of resources (Flowspec).

Life without the Internet is no longer possible nor thinkable. Consider the effects of a prolonged Internet outage: In the least impactful way, most of our kids and peers just would no longer be able to interact with their peers. They might severely miss out on the quality of their leisure time activities which increasingly relies on social networks, online games, YouTube, and other online entertainment offers. This may be a nuisance but still is tolerable. More seriously and economically relevant, manufacturing and trade would no longer work as all interactions inside and among companies rely on a working Internet. Indeed, just-in-time ordering mechanisms and Internet of Things-enhanced production chains within the Industry 4.0 framework would no longer be operational as old-style communication means such as phone and faxes have completely been replaced. Indeed, neither of these alternative mechanisms-faxes, phone, and also messaging-would be available either as they also rely on Internet technology. Even worse, the control of critical infrastructures would also be affected severely as they increasingly rely on the Internet for gathering input data and propagating control information. Moreover, all big data analytic applications, including financial transactions, would fail as they can no longer gather and process their input data. Even worse, the fact that there is “no communication without energy” nowadays also means that the reciprocal statement applies that there is no “energy without communication”.

The Border Gateway Protocol (BGP) has been used for decades as the de facto protocol to exchange reachability information among networks in the Internet. However, little is known about how this protocol is used to restrict reachability to selected destinations, e.g., that are under attack. While such a feature, BGP blackholing, has been available for some time, we lack a systematic study of its Internet-wide adoption, practices, and network efficacy, as well as the profile of blackholed destinations.

IP traffic with forged source addresses (i.e., spoofed traffic) enables a series of threats ranging from the impersonation of remote hosts to massive denial-of-service attacks. Consequently, IP address spoofing received considerable attention with efforts to either suppress spoofing, to mitigate its consequences, or to actively measure the ability to spoof in individual networks. However, as of today, we still lack a comprehensive understanding both of the prevalence and the characteristics of spoofed traffic "in the wild" as well as of the networks that inject spoofed traffic into the Internet.

Peering infrastructures, namely, colocation facilities and Internet exchange points, are located in every major city, have hundreds of network members, and support hundreds of thousands of interconnections around the globe. These infrastructures are well provisioned and managed, but outages have to be expected, e.g., due to power failures, human errors, attacks, and natural disasters. However, little is known about the frequency and impact of outages at these critical infrastructures with high peering concentration.

The quickly growing demand for wireless networks and the numerous application-specific requirements stand in stark contrast to today's inflexible management and operation of wireless networks. While most research focuses on mobile networks, WiFi is often left out of the purview. In this paper, we present and evaluate OpenSDWN, a novel WiFi architecture based on a joint software-defined network and network functions virtualization approach. OpenSDWN exploits virtualization across the wired and wireless network and introduces datapath programmability to enable service differentiation and fine-grained transmission control, facilitating the prioritization of critical applications. OpenSDWN implements per-client virtual access points and per-client virtual middleboxes, to render network functions more flexible and support mobility and seamless migration. Moreover, OpenSDWN also increases the security of upcoming WiFi HotSpot architectures by following a functional split approach. Finally, OpenSDWN can also be used to out-source the control over the home network to a participatory interface or to an Internet service provider.

Software-Defined Networks (SDNs) promise to overcome the often complex and error-prone operation of tradi- tional computer networks, by enabling programmabil- ity, automation and verifiability. Yet, SDNs also in- troduce new challenges, for example due to the asyn- chronous communication channel between the logically centralized control platform and the switches in the data plane. In particular, the asynchronous commu- nication of network update commands (e.g., OpenFlow FlowMod messages) may lead to transient inconsisten- cies, such as loops or bypassed waypoints (e.g., fire- walls). One approach to ensure transient consistency even in asynchronous environments is to employ smart scheduling algorithms: algorithms which update subsets of switches in each communication round only, where each subset in itself guarantees consistency. In this demo, we show how to change routing policies in a transiently consistent manner. We demonstrate two al- gorithms, namely, Wayup [5] and Peacock [4], which partition the network updates sent from SDN controller towards OpenFlow software switches into multiple rounds as per respective algorithms. Later, the barrier mes- sages are utilized to ensure reliable network updates.

Content and services which are offered for free on the Internet are primarily monetized through online advertisement. This business model relies on the implicit agreement between content providers and users where viewing ads is the price for the "free" content. This status quo is not acceptable to all users, however, as manifested by the rise of ad-blocking plugins which are available for all popular Web browsers. Indeed, ad-blockers have the potential to substantially disrupt the widely established business model of "free" content, currently one of the core elements on which the Web is built.

The quickly growing demand for wireless networks and the numerous application-specific requirements stand in stark contrast to today's inflexible management and operation of WiFi networks. In this paper, we present and evaluate OpenSDWN, a novel WiFi architecture based on an SDN/NFV approach. OpenSDWN exploits datapath programmability to enable service differentiation and fine-grained transmission control, facilitating the prioritization of critical applications. OpenSDWN implements per-client virtual access points and per-client virtual middleboxes, to render network functions more flexible and support mobility and seamless migration. OpenSDWN can also be used to out-source the control over the home network to a participatory interface or to an Internet Service Provider.

Despite decades of operational experience and focused research efforts, standards for sizing and configuring buffers in network systems remain controversial. An extreme example of this is the recent claim that excessive buffering (i.e., bufferbloat) can severely impact Internet services. In this paper, we systematically examine the implications of buffer sizing choices from the perspective of factors impacting end user experience. To assess user perception of application quality under various buffer sizing schemes we employ Quality of Experience (QoE) metrics. We evaluate these metrics over a wide range of end-user applications (e.g., web browsing, VoIP, and RTP video streaming) and workloads in two realistic testbeds emulating access and backbone networks. The main finding of our extensive evaluations is that network workload, rather than buffer size, is the primary determinant of end user QoE. Our results also highlight the relatively narrow conditions under which bufferbloat seriously degrades QoE, i.e., when buffers are oversized and sustainably filled.

Although traffic between Web servers and Web browsers is readily apparent to many knowledgeable end users, fewer are aware of the extent of server-to-server Web traffic carried over the public Internet. We refer to the former class of traffic as front-office Internet Web traffic and the latter as back-office Internet Web traffic (or just front-office and back-office traffic, for short). Back-office traffic, which may or may not be triggered by end-user activity, is essential for today's Web as it supports a number of popular but complex Web services including large-scale content delivery, social networking, indexing, searching, advertising, and proxy services. This paper takes a first look at back-office traffic, measuring it from various vantage points, including from within ISPs, IXPs, and CDNs. We describe techniques for identifying back-office traffic based on the roles that this traffic plays in the Web ecosystem. Our measurements show that back-office traffic accounts for a significant fraction not only of core Internet traffic, but also of Web transactions in the terms of requests and responses. Finally, we discuss the implications and opportunities that the presence of back-office traffic presents for the evolution of the Internet ecosystem.

During the last few years, more and more of the medium-to-large Internet eXchange Points (IXP) around the world have started to operate a route server and offer its use as a free value-added service to their members. This service has greatly simplified inter-domain routing for those members and has made it easy for them to peer with possibly hundreds of networks at those IXPs from the get-go.

Distributed applications often require high-performance networks with strict connectivity guarantees. For instance, many cloud applications suffer from today's variations of the intra-cloud bandwidth, which leads to poor and unpredictable application performance. Accordingly, we witness a trend towards virtual networks (VNets) which can provide resource isolation. Interestingly, while the problem of where to embed a VNet is fairly well-understood today, much less is known about when to optimally allocate a VNet. This however is important, as the requirements specified for a VNet do not have to be static, but can vary over time and even include certain temporal flexibilities. This paper initiates the study of the temporal VNet embedding problem (TVNEP). We propose a continuous-time mathematical programming approach to solve the TVNEP, and present and compare different algorithms. Based on these insights, we present the CSM-Model which incorporates both symmetry and state-space reductions to significantly speed up the process of computing exact solutions to the TVNEP. Based on the CSM-Model, we derive a greedy algorithm OGA to compute fast approximate solutions. In an extensive computational evaluation, we show that despite the hardness of the TVNEP, the CSM-Model is sufficiently powerful to solve moderately sized instances to optimality within one hour and under different objective functions (such as maximizing the number of embeddable VNets). We also show that the greedy algorithm exploits flexibilities well and yields good solutions. More generally, our results suggest that already little time flexibilities can improve the overall system performance significantly.

Recent Internet studies have reported on continued traffic growth, changes in applications usage, and a proliferation in the adoption of high-speed access links. Any adverse impact that these observed trends may have on Internet traffic flows can result in sub par performance, which in turn results in unsatisfactory user experience. To study such adverse impacts, we examine in this paper the flow-level performance of popular applications across a range of size-based flow-classes and applications. We use out-of-sequence packets, retransmissions, throughput, and RTTs as key flow performance metrics. Leveraging data sets collected from two complementary network environments, we compare these metrics for popular applications and for the up/downstream directions. We show that irrespective of the direction, flows are severely impacted by the specifics of the network, e.g., DSL or CDN and application behavior. We also find that, in general, this impact differs markedly across the different flow-classes. In particular, contrary to popular belief, the small flows from all applications, which make up the majority of flows, experience significant retransmissions, while the very large flows, although small in number, experience very limited retransmissions. In terms of application-related performance, we observe that especially when compared to HTTP, apart from large flows, P2P flows suffer from continuously high retransmissions and low throughput. As for the root cause of these retransmissions, we identify the access part of the network as the main culprit and not the network core.

Today, most devices have multiple network interfaces. Coupled with wide-spread replication of popular content at multiple locations, this provides substantial path diversity in the Internet. We propose Multi-source Multipath HTTP, mHTTP, which takes advantage of all existing types of path diversity in the Internet. mHTTP needs only client-side but not server-side or network modifications as it is a receiver-oriented mechanism. Moreover, the modifications are restricted to the socket interface. Thus, no changes are needed to the applications or to the kernel.

Today's trend toward network virtualization and software-defined networking enables flexible new distributed systems where resources can be dynamically allocated and migrated to locations where they are most useful. This paper proposes a competitive analysis approach to design and reason about online algorithms that find a good tradeoff between the benefits and costs of a migratable service. A competitive online algorithm provides worst-case performance guarantees under any demand dynamics, and without any information or statistical assumptions on the demand in the future. This is attractive especially in scenarios where the demand is hard to predict and can be subject to unexpected events. As a case study, we describe a service (e.g., an SAP server or a gaming application) that uses network virtualization to improve the quality of service (QoS) experienced by thin client applications running on mobile devices. By decoupling the service from the underlying resource infrastructure, it can be migrated closer to the current client locations while taking into account migration costs. We identify the major cost factors in such a system and formalize the wide-area service migration problem. Our main contributions are a randomized and a deterministic online algorithm that achieve a competitive ratio of O(logn) in a simplified scenario, where n is the size of the substrate network. This is almost optimal. We complement our worst-case analysis with simulations in different specific scenarios and also sketch a migration demonstrator.

In today's Internet, almost all end devices have multiple interfaces built in. This enables users to seamlessly switch between different access networks or even use them simultaneously; to better use the resources available to them and to better satisfy their needs. This is referred to as mobile data offloading and has received lots of attention recently in both the research community and in the industry. However, all the proposed data solutions either rely on static configuration policies or are reactive rather than proactive with regards to the application needs.

Recent Internet studies have reported on continued traffic growth and popularity of web-based applications. Any adverse impact that these observed trends may have on Internet traffic flows can result in sub par performance, which in turn results in unsatisfactory user experience. Leveraging data collected at a major content distribution network (CDN), we investigate flow-level performance in the wild. We observe that packet losses differ widely across flows of different sizes, and even for flows of similar size. To shed light on these observations, we rely on a controlled testbed setup with advanced instrumentation via NetFPGA cards. We highlight the key factors which can degrade flow-performance across different network loads and flow-size distributions. We find that packet losses do not affect all flows similarly. Depending on the network load, some flows either suffer from significantly more drops (unhappy flows) or significantly less drops than the average loss rate (happy flows). Very few flows actually observe a loss rate similar to the average loss rate. Therefore, any single flow is very unlikely to observe the global packet loss process. Furthermore, we find that some flows are burstier than others as indicated by their average congestion window.

In the context of measuring the Internet, a long-standing question has been whether there exist well-localized physical entities in today's network where traffic from a representative cross-section of the constituents of the Internet can be observed at a fine-enough granularity to paint an accurate and informative picture of how these constituents shape and impact much of the structure and evolution of today's Internet and the actual traffic it carries. In this paper, we first answer this question in the affirmative by mining 17 weeks of continuous sFlow data from one of the largest European IXPs. Examining these weekly snapshots, we discover a vantage point with excellent visibility into the Internet, seeing week-in and week-out traffic from all 42K+ routed ASes, almost all 450K+ routed prefixes, from close to 1.5M servers, and around a quarter billion IPs from all around the globe. Second, to show the potential of such vantage points, we analyze the server-related portion of the traffic at this IXP, identify the server IPs and cluster them according to the organizations responsible for delivering the content. In the process, we observe a clear trend among many of the critical Internet players towards network heterogenization; that is, either hosting servers of third-party networks in their own infrastructures or pursuing massive deployments of their own servers in strategically chosen third-party networks. While the latter is a well-known business strategy of companies such as Akamai, Google, and Netflix, we show in this paper the extent of network heterogenization in today's Internet and illustrate how it enriches the traditional, largely traffic-agnostic AS-level view of the Internet.

The recently proposed DNS extension, EDNS-Client-Subnet (ECS), has been quickly adopted by major Internet companies such as Google to better assign user requests to their servers and improve end-user experience. In this paper, we show that the adoption of ECS also offers unique, but likely unintended, opportunities to uncover details about these companies' operational practices at almost no cost. A key observation is that ECS allows to resolve domain names of ECS adopters on behalf of any arbitrary IP/prefix in the Internet. In fact, by utilizing only a single residential vantage point and relying solely on publicly available information, we are able to (i) uncover the global footprint of ECS adopters with very little effort, (ii) infer the DNS response cacheability and end-user clustering of ECS adopters for an arbitrary network in the Internet, and (iii) capture snapshots of user to server mappings as practiced by major ECS adopters. While pointing out such new measurement opportunities, our work is also intended to make current and future ECS adopters aware of which operational information gets exposed when utilizing this recent DNS extension.

No abstract available.

The concept of CloudNets, virtual networks connecting cloud resources, has recently attracted much interest from both academic as well as business sides. CloudNets can realize the vision of affordable customized infrastructures. In particular, such networks are expected to be offered even in federated environments with multiple providers. Inter-provider communication about requirements or provisioning of truly customized virtual environments however require a powerful flexible resource description language (RDL). While extensibility and expressiveness seem to be natural requirements for such a language, we identify another less intuitive requirement affecting all actors (or stakeholders) in their economic benefits: the possibility to omit arbitrary specification details and to remainvaguewhile at the same time describing real world scenarios. Not only may a description language ignoring this constraint easily become too bulky to use, it is also likely to force players to focus on details they are not interested in or lack the knowledge to map their actual requirements to. This paper identifies detailed requirements for an RDL to allow for topology and requirement communication in business scenarios. Furthermore, we present the FleRD flexible resource description language for multi-provider virtual network architectures. FleRD is fully incorporated in our own CloudNet prototype architecture.

The largest IXPs carry on a daily basis traffic volumes in the petabyte range, similar to what some of the largest global ISPs reportedly handle. This little-known fact is due to a few hundreds of member ASes exchanging traffic with one another over the IXP's infrastructure. This paper reports on a first-of-its-kind and in-depth analysis of one of the largest IXPs worldwide based on nine months' worth of sFlow records collected at that IXP in 2011.

We present a demo of Odin, an SDN framework to program enterprise wireless local area networks (WLANs). Enterprise WLANs need to support a wide range of services and functionalities. This includes authentication, authorization and accounting, policy, mobility and interference management, and load balancing. WLANs also exhibit unique challenges. In particular, access point (AP) association decisions are not made by the infrastructure, but by clients. In addition, the association state machine combined with the broadcast nature of the wireless medium requires keeping track of a large amount of state changes. To this end, Odin builds on a light virtual AP abstraction that greatly simplifies client management. Odin does not require any client side modifications and its design supports WPA2 Enterprise. With Odin, a network operator can implement enterprise WLAN services as network applications.

Recent studies show that a large fraction of Internet traffic is originated by Content Providers (CPs) such as content distribution networks and hyper-giants. To cope with the increasing demand for content, CPs deploy massively distributed server infrastructures. Thus, content is available in many network locations and can be downloaded by traversing different paths in a network. Despite the prominent server location and path diversity, the decisions on how to map users to servers by CPs and how to perform traffic engineering by ISPs, are independent. This leads to a lose-lose situation as CPs are not aware about the network bottlenecks nor the location of end-users, and the ISPs struggle to cope with rapid traffic shifts caused by the dynamic CP server selection process.

The evolution of wireless network standards, e.g., GSM/GPRS, UMTS, WiFi, WiMAX, and end-user devices has paved the way towards Next Generation Mobile Networks (NGMN), where users are always connected through multiple radio access networks. NGMN technologies target to improve the user experience especially for mobile data and multimedia services, which are in line with user expectations evident from, for instance, the increasingly popular mobile HTTP video streaming. To understand the quality that can be offered to the user in NGMNs, we compare the Quality of Experience (QoE) for HTTP streaming in a prototype NGMN testbed with WiFi and 3G UMTS/HSDPA support. We use CUBIC TCP as the transport layer protocol as it is typically the default TCP variant, e.g., in Android phones. We complement the QoE estimations with network QoS parameters such as throughput and delay, and transport layer statistics. The results of our evaluation show that (i) video QoE remains stable in WiFi even for high packet losses compared to UMTS, (ii) QoE in UMTS is sensitive to packet loss even for low loss rates due to high variations in the network QoS, namely, throughput and delay, (iii) the decrease in QoE and QoS in HSDPA is due to its negative interactions with the aggressive congestion control of CUBIC TCP, and (iv) handover from WiFi to HSDPA degrades QoE.

Speech quality in Next Generation Mobile Networks (NGMN) is critical. Accordingly, we analyze in this paper, how the quality estimation provided by wideband PESQ, a signal-based speech quality prediction model, differs from the user perception. We find that the model underestimates the auditory quality in certain NGMN conditions: 1) wideband-narrowband speech codec switching, 2) speech signal fading during codec switching, and 3) talk-spurt internal time-shifting due to jitter buffer instability. By pointing out the impact of these degradations on the speech signal, this paper contributes to potential improvements and adaptation of the wideband PESQ model for NGMNs.

This paper explores the effect of varying peers' local cache sizes on user perceived video quality in Video-on-Demand p2p streaming. First, we ascertain the relationship between the average video distortion on peers and peer cache size. Second, we analyze the aggregate access network usage of uplink bandwidth for different peer cache sizes. Finally, we measure the p2p server bandwidth usage as the peer cache size is changed. After finding analytical fits to these three functions we compute the optimal peer cache size that minimizes the total cost of p2p VoD video streaming. Our extensive simulations highlight the key role peer cache sizes play in the interplay between the video quality delivered to users and the amounts of p2p server and peer bandwidth usage. Subsequent data analysis provided in this work presents a framework for computing an optimum operating point for p2p VoD systems in terms of server and peer bandwidth required.

Content delivery systems constitute a major portion of today’s In-ternet traffic. While they are a good source of revenue for Internet Service Providers (ISPs), the huge volume of content delivery traf-fic also poses a significant burden and traffic engineering challenge for the ISP. The difficulty is due to the immense volume of trans-fers, while the traffic engineering challenge stems from the fact that most content delivery systems themselves utilize a distributed infrastructure. They perform their own traffic flow optimization and realize this using the DNS system. While content delivery sys-tems may, to some extent, consider the user’s performance within their optimization criteria, they currently have no incentive to con-sider any of the ISP’s constraints. As a consequence, the ISP has “lost control ” over a major part of its traffic. To overcome this im-pairment, we propose a solution where the ISP offers a Provider-aided Distance Information System (PaDIS). PaDIS uses informa-tion available only to the ISP to rank any client-host pair based on distance information, such as delay, bandwidth or number of hops. In this paper we show that the applicability of the system is sig-nificant. More than 70 % of the HTTP traffic of a major European ISP can be accessed via multiple different locations. Moreover, we show that deploying PaDIS is not only beneficial to ISPs, but also to users. Experiments with different content providers show that improvements in download times of up to a factor of four are possible. Furthermore, we describe a high performance implemen-tation of PaDIS and show how it can be deployed within an ISP.

While residential broadband Internet access is popular in many parts of the world, only a few studies have examined the characteristics of such traffic. In this paper we describe observations from monitoring the network activity for more than 20,000 residential DSL customers in an urban area. To ensure privacy, all data is immediately anonymized. We augment the anonymized packet traces with information about DSL-level sessions, IP (re-)assignments, and DSL link bandwidth.

Online Social Networks (OSNs) have already attracted more than half a billion users. However, our understanding of which OSN features attract and keep the attention of these users is poor. Studies thus far have relied on surveys or interviews of OSN users or focused on static properties, e. g., the friendship graph, gathered via sampled crawls. In this paper, we study how users actually interact with OSNs by extracting clickstreams from passively monitored network traffic. Our characterization of user interactions within the OSN for four different OSNs (Facebook, LinkedIn, Hi5, and StudiVZ) focuses on feature popularity, session characteristics, and the dynamics within OSN sessions. We find, for example, that users commonly spend more than half an hour interacting with the OSNs while the byte contributions per OSN session are relatively small.

Peer-to-peer (P2P) systems offer astounding possibilities to their users. As such P2P users are a good source of revenue for the Internet service providers (ISPs). But the immense volume of P2P traffic also poses a significant challenges to the ISPs. P2P systems have to either build their overlay topologies agnostic of the underlay topology or measure the path performance themselves. Accordingly, routing in P2P systems is often suboptimal and largely independent of the Internet routing. In addition, the ISP looses control of its traffic. This situation is disadvantageous for both: the ISPs and the P2P users.To overcome this, we suggest that ISPs and P2P systems collaborate. We propose and evaluate the feasibility of a solution where the ISP offers an ldquooraclerdquo to the P2P users. When the P2P user supplies the oracle with a list of possible P2P nodes, the oracle ranks them according to certain criteria, like their proximity to the user or higher bandwidth links. This can be used by the P2P user to choose appropriate neighbors, and therefore improve its performance. The ISP can use this mechanism to better manage the immense P2P traffic, e.g., to keep it inside its network, or to direct it along a desired path.

Mobility is a requirement not appropriately addressed by the original design of the Internet since an IP address has two fundamentally different tasks. It specifies a network location (for routing) and serves as an application identifier. A plethora of suggestions have been made to overcome this, e.g., Mobile IP and HIP. Yet, each of the proposed solutions has drawbacks such as requiring fundamental changes to the Internet architecture or relying on triangular routing.

In this paper, we detail our experiences with the implementation of a popular P2P file sharing system in a simulation framework. We discuss some of the salient features of our implementation, and compare packet level with application level simulators. We then explain how we reflect user behaviour models in our simulation framework. After describing the use of visualization as an important analysis tool, we finally make some observations from our experiences with P2P simulations.

In many situations it can be enormously helpful to archive the raw contents of a network traffic stream to disk, to enable later inspection of activity that becomes interesting only in retrospect. We present a Time Machine (TM) for network traffic that provides such a capability. The TM leverages the heavy-tailed nature of network flows to capture nearly all of the likely-interesting traffic while storing only a small fraction of the total volume. An initial proof-of-principle prototype established the forensic value of such an approach, contributing to the investigation of numerous attacks at a site with thousands of users. Based on these experiences, a rearchitected implementation of the system provides flexible, highperformance traffic stream capture, indexing and retrieval, including an interface between the TM and a real-time network intrusion detection system (NIDS). The NIDS controls the TM by dynamically adjusting recording parameters, instructing it to permanently store suspicious activity for offline forensics, and fetching traffic from the past for retrospective analysis. We present a detailed performance evaluation of both stand-alone and joint setups, and report on experiences with running the system live in high-volume environments.

When installing network intrusion detection systems (NIDSs), operators are faced with a large number of parameters and analysis options for tuning trade-offs between detection accuracy versus resource requirements. In this work we set out to assist this process by understanding and predicting the CPU and memory consumption of such systems.

Mobility is a requirement not appropriately addressed by the original design of the Internet. A plethora of suggestions have been made to overcome this.

So far virtual machine (VM) migration has focused on transferring the run-time memory state of the VMs in local area networks (LAN). However, for wide-area network (WAN) migration it is crucial to not just transfer the VMs image but also transfer its local persistent state (its file system) and its on-going network connections. In this paper we address both: by combining a block-level solution with pre-copying and write throttling we show that we can transfer an entire running web server, including its local persistent state, with minimal disruption --- three seconds in the LAN and 68 seconds in the WAN); by combining dynDNS with tunneling, existing connections can continue transparently while new ones are redirected to the new network location. Thus we show experimentally that by combining well-known techniques in a novel manner we can provide system support for migrating virtual execution environments in the wide area.

One major challenge in communication networks is the problem of dynamically distributing load in the presence of bursty and hard to predict changes in traffic demands. Current traffic engineering operates on time scales of several hours which is too slow to react to phenomena like flash crowds or BGP reroutes. One possible solution is to use load sensitive routing. Yet, interacting routing decisions at short time scales can lead to oscillations, which has prevented load sensitive routing from being deployed since the early experiences in Arpanet.

Search engines are a vital part of the Web and thus the Internet infrastructure. Therefore understanding the behavior of users searching the Web gives insights into trends, and enables enhancements of future search capabilities. Possible data sources for studying Web search behavior are either server-side logs or client-side logs. Unfortunately, current server-side logs are hard to obtain as they are considered proprietary by the search engine operators. Therefore we in this paper present a methodology for extracting client-side logs from the traffic exchanged between a large user group and the Internet. The added benefit of our methodology is that we do not only extract the search terms, the query sequences, and search results of each individual user but also the full clickstream, i.e., the result pages users view and the subsequently visited hyperlinked pages. We propose a finite-state Markov model that captures the user web searching and browsing behavior and allows us to deduce users' prevalent search patterns. To our knowledge, this is the first such detailed client-side analysis of clickstreams.

More and more traffic management techniques, including accounting and load adaptive routing, try to take advantage of the fact that traffic demands are consistent with Zipf's law. By treating a few large volume demands differently they try to capture most of the traffic. This relies on the implicit assumption that traffic demands are persistent in volume over time; meaning that their volume does not change drastically over time. As this assumption has been shown to be incorrect we in this paper focus on how Internet flows behave over time. Accordingly, this paper examines the characteristics of volatility in a qualitative way by characterizing the components that are responsible for changes in the cast of heavy hitters over time.

An understanding of the topological structure of the Internet is needed for quite a number of networking tasks, e. g., making decisions about peering relationships, choice of upstream providers, inter-domain traffic engineering. One essential component of these tasks is the ability to predict routes in the Internet. However, the Internet is composed of a large number of independent autonomous systems (ASes) resulting in complex interactions, and until now no model of the Internet has succeeded in producing predictions of acceptable accuracy.We demonstrate that there are two limitations of prior models: (i) they have all assumed that an Autonomous System (AS) is an atomic structure - it is not, and (ii) models have tended to oversimplify the relationships between ASes. Our approach uses multiple quasi-routers to capture route diversity within the ASes, and is deliberately agnostic regarding the types of relationships between ASes. The resulting model ensures that its routing is consistent with the observed routes. Exploiting a large number of observation points, we show that our model provides accurate predictions for unobserved routes, a first step towards developing structural mod-els of the Internet that enable real applications.

... (NIDSs) face extreme challenges with respect to traffic volume, traffic diversity, and resource management. While crucial for acceptance and operational deployment, the research literature mainly omits such practical difficulties. In this paper, we offer an evaluation based on extensive operational experience. More specifically, we identify and explore key factors with respect to resource management and efficient packet processing and highlight their impact using a set of real-world traces. On the one hand, these insights help us gauge the trade-offs of tuning a NIDS. On the other hand, they motivate us to explore several novel ways of reducing resource requirements. These enable us to improve the state management considerably as well as balance the processing load dynamically. Overall this enables us to operate a NIDS successfully in our highvolume network environments.

This paper introduces a methodology for estimating interdomain Web traffic lows between all clients worldwide and the ervers belonging to over one housand content providers. The idea is to use the server logs from a large ontent Delivery Network (CDN) to identify client downloads of content provider (i.e., publisher) Web pages. For each of these Web pages, a client typically downloads some objects from the content provider, some from the CDN, and perhaps some from third parties such as banner advertisement agencies. The sizes and sources of the non-CDN downloads associated with each CDN download are estimated separately by examining Web accesses in packet traces collected at several universities.

Evaluating network components such as network intrusion detection systems, firewalls, routers, or switches suffers from the lack of available network traffic traces that on the one hand are appropriate for a specific test environment but on the other hand have the same characteristics as actual traffic. Instead of just capturing traffic and replaying the trace, we identify a set of packet trace manipulation operations that enable us to generate a trace bottom-up: our trace primitives can be traces from different environments or artificially generated ones; our basic operations include merging of two traces, moving a flow across time, duplicating a flow, and stretching a flow's time-scale. After discussing the potential as ell as the dangers of each operation with respect to analysis at different protocol layers, we present a framework within which these operations can be realized and show an example configuration for our prototype.

This paper presents a methodology for identifying the autonomous system (or systems) responsible when a routing change is observed and propagated by BGP. The origin of such a routing instability is deduced by examining and correlating BGP updates for many prefixes gathered at many observation points. Although interpreting BGP updates can be perplexing, we find that we can pinpoint the origin to either a single AS or a session between two ASes in most cases. We verify our methodology in two phases. First, we perform simulations on an AS topology derived from actual BGP updates using routing policies that are compatible with inferred peering/customer/provider relationships. In these simulations, in which network and router behavior are "ideal", we inject inter-AS link failures and demonstrate that our methodology can effectively identify most origins of instability. We then develop several heuristics to cope with the limitations of the actual BGP update propagation process and monitoring infrastructure, and apply our methodology and evaluation techniques to actual BGP updates gathered at hundreds of observation points. This approach of relying on data from BGP simulations as well as from measurements enables us to evaluate the inference quality achieved by our approach under ideal situations and how it is correlated with the actual quality and the number of observation points.

In our quest to better understand network tra#c dynamics, we examine Internet chat systems. Although chat as an application does not contribute huge amounts of tra#c, chat systems are known to be habit-forming. This implies that catering to such users can be a promising way of attracting them, especially in low bandwidth environments such as wireless networks.

No abstract available.

This paper examines the possibility of generating realistic routing tables of arbitrary size along with realistic BGP updates of arbitrary frequencies via an automated tool deployable in a small-scale test lab. Such a tool provides the necessary foundations to study such questions as: the limits of BGP scalability, the reasons behind routing instability, and the extent to which routing instability influences the forwarding performance of a router.We find that the answer is affirmative. In this paper we identify important characteristics/metrics of routing tables and updates which provide the foundation of the proposed BGP workload model. Based on the insights of an extensive characterization of BGP traffic according to such metrics as prefix length distributions, fanout, amount of nesting of routing table prefixes, AS path length, number and times between BGP update bursts and number and times between BGP session resets, etc., we introduce our prototype tool, rtg. rtg realizes the workload model and is capable of generating realistic BGP traffic. Through its flexibility and parameterization rtg enables us to study the sensibilities of test systems in a repeatable and consistent manner while still providing the possibility of capturing the different characteristics from different vantage points in the network.

Engineering a large IP backbone network without an accurate network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctuations in load. We present a model of traffic demands to support traffic engineering and performance debugging of large Internet service provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability information about all egress links. We discuss how to cope with situations where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdomain traffic demands using measurements collected at a smaller number of edge links-the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic demands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering.

We present an algorithmic framework for solving the packet classification problem that allows various access time versus memory tradeoffs. It reduces the multidimensional packet classification problem to solving a few instances of the one-dimensional IP lookup problem. It gives the best known lookup performance with moderately large memory space. Furthermore, it efficiently supports a reasonable number of additions and deletions to the rulesets without degrading the lookup performance. We perform a thorough experimental study of the tradeoffs for the two-dimensional packet classification problem on rulesets derived from datasets collected from AT&T WorldNet, an Internet service provider.

Engineering a large IP backbone network without an accurate, network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctuations in load. In this paper, we present a model of traffic demands to support traffic engineering and performance debugging of large Internet Service Provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability information about all egress links. We discuss how to cope with situations where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdomain traffic demands using measurements collected at a smaller number of edge links --- the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic demands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering.

Much work on the performance of Web proxy caching has focused on high-level metrics such as hit rates, but has ignored low level details such as "cookies", aborted connections, and persistent connections between clients and proxies as well as between proxies and servers. These details have a strong impact on performance, particularly in heterogeneous bandwidth environments where network speeds between clients and proxies are significantly different than speeds between proxies and servers. We evaluate through detailed simulations the latency and bandwidth effects of Web proxy caching in such environments. We drive our simulations with packet traces from two scenarios: clients connected through slow dialup modems to a commercial ISP, and clients on a fast LAN in an industrial research lab. We present three main results. First, caching persistent connections at the proxy can improve latency much more than simply caching Web data. Second, aborted connections can waste more bandwidth than that saved by caching data. Third, cookies can dramatically reduce hit rates by making many documents effectively uncacheable.

Using the ns-2-simulator to experiment with different aspects of user- or session-behaviors and network configurations and focusing on the qualitative aspects of a wavelet-based scaling analysis, we present a systematic investigation into how and why variability and feedback-control contribute to the intriguing scaling properties observed in actual Internet traces (as our benchmark data, we use measured Internet traffic from an ISP). We illustrate how variability of both user aspects and network environments (i) causes self-similar scaling behavior over large time scales, (ii) determines a more or less pronounced change in scaling behavior around a specific time scale, and (iii) sets the stage for the emergence of surprisingly rich scaling dynamics over small time scales; i.e., multifractal scaling. Moreover, our scaling analyses indicate whether or not open-loop controls such as UDP or closed-loop controls such as TCP impact the local or small-scale behavior of the traffic and how they contribute to the observed multifractal nature of measured Internet traffic. In fact, our findings suggest an initial physical explanation for why measured Internet traffic over small time scales is highly complex and suggest novel ways for detecting and identifying, for example, performance bottlenecks.This paper focuses on the qualitative aspects of a wavelet-based scaling analysis rather than on the quantitative use for which it was originally designed. We demonstrate how the presented techniques can be used for analyzing a wide range of different kinds of network-related measurements in ways that were not previously feasible. We show that scaling analysis has the ability to extract relevant information about the time-scale dynamics of Internet traffic, thereby, we hope, making these techniques available to a larger segment of the networking research community.

Previous studies have demonstrated that measured wide-area network traffic such as Internet traffic exhibits locally complex irregularities, consistent with multifractal behavior. It has also been shown that the observed multifractal structure becomes most apparent when analyzing measured network traffic at a particular layer in the well-defined protocol hierarchy that characterizes modern data networks, namely the transport or transmission control protocol (TCP) layer. To investigate this new scaling phenomenon associated with the dynamics of measured network traffic over small time scales, we consider a class of multiplicative processes, the so-called conservative cascades, that serves as a cascade paradigm for and is motivated by the networking application. We present a wavelet-based time/scale analysis of these cascades to determine rigorously their global and local-scaling behavior. In particular, we prove that for the class of multifractals generated by these conservative cascades the multifractal formalism applies and is valid, and we illustrate some of the wavelet-based techniques for inferring multifractal scaling behavior by applying them to a set of wide-area traffic traces.

To efficiently transfer large amounts of diverse traffic over high-speed links, modern integrated networks require more efficient packet-switching techniques that can capitalize on advances in switch hardware. Several promising approaches attempt to improve performance by creating dedicated "shortcut" connections for long-lived traffic flows, at the expense of the network overhead for establishing and maintaining these shortcuts. The network can balance these cost-performance tradeoffs through three tunable parameters: the granularity of flow end-point addresses, the timeout for grouping related packets into flows, and the trigger for migrating a long-lived flow to a shortcut connection. Drawing on a continuous one-week trace of Internet traffic, we evaluate the processor and switch overheads for transferring HTTP server traffic through a flow-switched network. In contrast to previous work, we focus on the full probability distributions of flow sizes and cost-performance metrics to highlight the subtle influence of the HTTP protocol and user behavior on the performance of flow switching. We find that moderate levels of aggregation and triggering yield significant reductions in overhead with a negligible reduction in performance. The traffic characterization results further suggest schemes for limiting the shortcut setup rate and the number of simultaneous shortcuts by temporarily delaying the creation of shortcuts during peak load, and by aggregating related packets that share a portion of their routes through the network.

In apparent contrast to the well-documented self-similar (i.e., monofractal) scaling behavior of measured LAN traffic, recent studies have suggested that measured TCP/IP and ATM WAN traffic exhibits more complex scaling behavior, consistent with multifractals. To bring multifractals into the realm of networking, this paper provides a simple construction based on cascades (also known as multiplicative processes) that is motivated by the protocol hierarchy of IP data networks. The cascade framework allows for a plausible physical explanation of the observed multifractal scaling behavior of data traffic and suggests that the underlying multiplicative structure is a traffic invariant for WAN traffic that co-exists with self-similarity. In particular, cascades allow us to refine the previously observed self-similar nature of data traffic to account for local irregularities in WAN traffic that are typically associated with networking mechanisms operating on small time scales, such as TCP flow control.To validate our approach, we show that recent measurements of Internet WAN traffic from both an ISP and a corporate environment are consistent with the proposed cascade paradigm and hence with multifractality. We rely on wavelet-based time-scale analysis techniques to visualize and to infer the scaling behavior of the traces, both globally and locally. We also discuss and illustrate with some examples how this cascade-based approach to describing data network traffic suggests novel ways for dealing with networking problems and helps in building intuition and physical understanding about the possible implications of multifractality on issues related to network performance analysis.

To efficiently transfer diverse traffic over high-speed links, modern integrated networks require more efficient packet-switching techniques that can capitalize on the advances in switch hardware. Several promising approaches attempt to improve the performance by creating dedicated "shortcut" connections for long-lived traffic flows, at the expense of the network overhead for establishing and maintaining these shortcuts. The network can balance these cost-performance tradeoffs through three tunable parameters: the granularity of flow end-point addresses, the timeout for grouping related packets into flows, and the trigger for migrating a long-lived flow to a shortcut connection. Drawing on a continuous one-week trace of Internet traffic, we evaluate the processor and switch overheads for transferring HTTP server traffic through a flow-switched network. In contrast to previous work, we focus on the full probability distributions of flow sizes and cost-performance metrics to highlight the subtle influence of the HTTP protocol and user behavior on the performance of flow switching. We find that moderate levels of aggregation and triggering yield significant reductions in overhead with a negligible reduction in performance. The traffic characterization results further suggest schemes for limiting shortcut overhead by temporarily delaying the creation of shortcuts during peak load and by aggregating related packets that share a portion of their routes through the network.

Traffic measurements from communication networks have shown that many quantities characterizing network performance have long-tail probability distributions, i.e., with tails that decay more slowly than exponentially. Long-tail distributions can have a dramatic effect upon performance, but it is often difficult to describe this effect in detail, because performance models with component long-tail distributions tend to be difficult to analyze. We address this problem by developing an algorithm for approximating a long-tail distribution by a finite mixture of exponentials. The fitting algorithm is recursive over time scales. At each stage, an exponential component is fit in the largest remaining time scale and then the fitted exponential component is subtracted from the distribution. Even though a mixture of exponentials has an exponential tail, it can match a long-tail distribution in the regions of primary interest when there are enough exponential components.

Caching in the World Wide Web currently follows a naive model, which assumes that resources are referenced many times between changes. The model also provides no way to update a cache entry if a resource does change, except by transferring the resource's entire new value. Several previous papers have proposed updating cache entries by transferring only the differences, or "delta," between the cached entry and the current value.In this paper, we make use of dynamic traces of the full contents of HTTP messages to quantify the potential benefits of delta-encoded responses. We show that delta encoding can provide remarkable improvements in response size and response delay for an important subset of HTTP content types. We also show the added benefit of data compression, and that the combination of delta encoding and data compression yields the best results.We propose specific extensions to the HTTP protocol for delta encoding and data compression. These extensions are compatible with existing implementations and specifications, yet allow efficient use of a variety of encoding techniques.

In this paper we introduce the ConSet communication model for distributed memory parallel computers. The communication needs of an application program can be satisfied by some arbitrary set of connections which are partitioned into discrete phases. A communication context switch is used to select the active phase. We present an implementation of the ConSet model on the iWarp and describe its performance characteristics, contrasting it to a message passing implementation on the same machine. Our implementation demonstrates how one existing parallel computer can function as a “reconfigurable network ” without needing a new processor interconnect technology. The ConSet model works best when communication patterns can be optimized at compile time. We examine the interactions of the target architecture with the algorithmic problems encountered designing a communication compiler to effectively partition, route, and schedule connections. We built a prototype communication compiler for our iWarp implementation, and are using it to generate iWarp code. Looking at basic communication patterns as well as patterns generated by an iterative finite element PDE solver, we compare ConSet’s performance (using the compiler’s schedules) to that of message passing. Our experiments suggestthat ConSet communication offers a performance advantage over messagepassing in applications where the communication pattern is known at compile time. 1

We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific communication configuration, but its running time is not known until it is completed. We present optimal online algorithms for PRAMs, hypercubes and one-dimensional meshes, and obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested...

The authors point out that, in order to perform the design of printed circuit boards as time- and cost-efficiently as possible, electromagnetic compatability (EMC) phenomena have to be taken into account during layout synthesis. The EMC router HERO offers a robust framework for incorporating EMC constraints and cost criteria into routing. Using HERO, it will not be possible to obtain a completely failsafe layout, in general. However, experimental results for typical boards prove that a great number of EMC problems can be avoided during layout synthesis and that the effects of EMC phenomena can be reduced substantially. Detailed reports of EMC design rule violations provide effective input to the succeeding EMC verification phase. Violations of EMC design rules are mainly caused by an inappropriate placement. Therefore, it seems to be of great promise to combine hierarchical placement methods with this approach for hierarchical routing.>

A global barrier synchronizes all processors in a parallel system.This paper investigates algorithms that allow disjoint subsets of processors to synchronize independently and in parallel.The user model of a subset barrier is straight forward; a processor that participates in a subset barrier needs to know only the name of the barrier and the number of participating processors.This paper identifies two general communication models for private-memory parallel systems: the bounded buffer broadcast model and the anonymous destination messagepassing model and presents algorithms fior barrier synchronization in the terms of these models.The models are detailed enough to allow meaningful cost estimates for their primitives, yet independent of a specific architecture and ~canbe supported efficiently by a modem private-memory parallel system.The anonymous destination message passing model is the most attractive.The time complexity to synchronize over a uni-directional ring of N processors is O(log N) for common cases, and 0( m) in the worst case.The algorithms have been implemented on iWarp, a private-memory parallel system and are now in daily use.The paper concludes with timing measurements obtained on a 64-node system. 1 Introduction Barrier synchronization is a useful technique for organizing 'the execution of a parallel program into a sequence of loosely coordinated phases.For example, a phase of a data-parallel program running on a private memory system might consist of a communication step,

The problem of online job scheduling on various parallel architectures is studied. An O((log log n)/sup 1/2/)-competitive algorithm for online dynamic scheduling on an n*n mesh is given. It is proved that this algorithm is optimal up to a constant factor. The algorithm is not greedy, and the lower bound proof shows that no greedy-like algorithm can be very good. The upper bound result can be generalized to any fixed-dimensional meshes. Competitive scheduling algorithms for other architectures are given.>