ConferenceHotNets 2023 - Proceedings of the 22nd ACM Workshop on Hot Topics in Networks · November 28, 2023
When a root certificate authority (CA) in the Web PKI misbehaves, primary root-store operators such as Mozilla and Google respond by distrusting that CA. However, full distrust is often too broad, so root stores often implement partial distrust of roots, s ...
Full textCite
ConferenceACM Transactions on Algorithms · March 9, 2023
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ...
Full textCite
Journal ArticleACM Transactions on Algorithms · March 9, 2023
This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 7, 2022
This paper proposes using a logic programming language to disentangle X.509 certificate validation policy from mechanism. Expressing validation policies in a logic programming language provides multiple benefits. First, policy and mechanism can be more ind ...
Full textCite
Journal ArticleJournal of the ACM · August 26, 2022
It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Altho ...
Full textCite
ConferenceSIGCOMM 2021 - Proceedings of the ACM SIGCOMM 2021 Conference · August 9, 2021
The key to optimizing the performance of an anycast-based system (e.g., the root DNS or a CDN) is choosing the right set of sites to announce the anycast prefix. One challenge here is predicting catchments. A naïve approach is to advertise the prefix from ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2021
Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrie ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 27, 2020
Low latency is of interest for a variety of applications. The most stringent latency requirements arise in financial trading, where sub-microsecond differences matter. As a result, firms in the financial technology sector are pushing networking technology ...
Full textCite
OtherLeibniz International Proceedings in Informatics, LIPIcs · June 1, 2020
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020
Header bidding (HB) is a relatively new online advertising technology that allows a content publisher to conduct a client-side (i.e., from within the end-user’s browser), real-time auction for selling ad slots on a web page. We developed a new browser exte ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 21, 2019
Despite its critical role in Internet connectivity, the Border Gateway Protocol (BGP) remains highly vulnerable to attacks such as prefix hijacking, where an Autonomous System (AS) announces routes for IP space it does not control. To address this issue, t ...
Full textCite
Journal ArticleIEEE/ACM Transactions on Networking · October 1, 2019
Internet interconnections are the means by which networks exchange traffic between one another. These interconnections are typically established in facilities that have known geographic locations, and are owned and operated by so-called colocation and inte ...
Full textCite
ConferenceProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019
It is well-known that a program’s memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Altho ...
Full textCite
ConferenceHotNets 2018 - Proceedings of the 2018 ACM Workshop on Hot Topics in Networks · November 15, 2018
A new space race is imminent, with several industry players working towards satellite-based Internet connectivity. While satellite networks are not themselves new, these recent proposals are aimed at orders of magnitude higher bandwidth and much lower late ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 31, 2018
TLS, the de facto standard protocol for securing communications over the Internet, relies on a hierarchy of certificates that bind names to public keys. Naturally, ensuring that the communicating parties are using only valid certificates is a necessary fir ...
Full textCite
ConferenceCoNEXT 2017 - Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies · November 28, 2017
Various trends are reshaping Internet video delivery: exponential growth in video traffic, rising expectations of high video quality of experience (QoE), and the proliferation of varied content delivery network (CDN) deployments (e.g., cloud computing-base ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 1, 2017
The Domain Name System (DNS) provides a scalable, flexible name resolution service. Unfortunately, its unauthenticated architecture has become the basis for many security attacks. To address this, DNS Security Extensions (DNSSEC) were introduced in 1997. D ...
Full textCite
ConferenceHotNets 2023 - Proceedings of the 22nd ACM Workshop on Hot Topics in Networks · November 28, 2023
When a root certificate authority (CA) in the Web PKI misbehaves, primary root-store operators such as Mozilla and Google respond by distrusting that CA. However, full distrust is often too broad, so root stores often implement partial distrust of roots, s ...
Full textCite
ConferenceACM Transactions on Algorithms · March 9, 2023
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ...
Full textCite
Journal ArticleACM Transactions on Algorithms · March 9, 2023
This article presents universal algorithms for clustering problems, including the widely studied k-median, k-means, and k-center objectives. The input is a metric space containing all potential client locations. The algorithm must select k cluster centers ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · November 7, 2022
This paper proposes using a logic programming language to disentangle X.509 certificate validation policy from mechanism. Expressing validation policies in a logic programming language provides multiple benefits. First, policy and mechanism can be more ind ...
Full textCite
Journal ArticleJournal of the ACM · August 26, 2022
It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Altho ...
Full textCite
ConferenceSIGCOMM 2021 - Proceedings of the ACM SIGCOMM 2021 Conference · August 9, 2021
The key to optimizing the performance of an anycast-based system (e.g., the root DNS or a CDN) is choosing the right set of sites to announce the anycast prefix. One challenge here is predicting catchments. A naïve approach is to advertise the prefix from ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2021
Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrie ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 27, 2020
Low latency is of interest for a variety of applications. The most stringent latency requirements arise in financial trading, where sub-microsecond differences matter. As a result, firms in the financial technology sector are pushing networking technology ...
Full textCite
OtherLeibniz International Proceedings in Informatics, LIPIcs · June 1, 2020
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defin ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2020
Header bidding (HB) is a relatively new online advertising technology that allows a content publisher to conduct a client-side (i.e., from within the end-user’s browser), real-time auction for selling ad slots on a web page. We developed a new browser exte ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 21, 2019
Despite its critical role in Internet connectivity, the Border Gateway Protocol (BGP) remains highly vulnerable to attacks such as prefix hijacking, where an Autonomous System (AS) announces routes for IP space it does not control. To address this issue, t ...
Full textCite
Journal ArticleIEEE/ACM Transactions on Networking · October 1, 2019
Internet interconnections are the means by which networks exchange traffic between one another. These interconnections are typically established in facilities that have known geographic locations, and are owned and operated by so-called colocation and inte ...
Full textCite
ConferenceProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2019
It is well-known that a program’s memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Altho ...
Full textCite
ConferenceHotNets 2018 - Proceedings of the 2018 ACM Workshop on Hot Topics in Networks · November 15, 2018
A new space race is imminent, with several industry players working towards satellite-based Internet connectivity. While satellite networks are not themselves new, these recent proposals are aimed at orders of magnitude higher bandwidth and much lower late ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 31, 2018
TLS, the de facto standard protocol for securing communications over the Internet, relies on a hierarchy of certificates that bind names to public keys. Naturally, ensuring that the communicating parties are using only valid certificates is a necessary fir ...
Full textCite
ConferenceCoNEXT 2017 - Proceedings of the 2017 13th International Conference on emerging Networking EXperiments and Technologies · November 28, 2017
Various trends are reshaping Internet video delivery: exponential growth in video traffic, rising expectations of high video quality of experience (QoE), and the proliferation of varied content delivery network (CDN) deployments (e.g., cloud computing-base ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 1, 2017
The Domain Name System (DNS) provides a scalable, flexible name resolution service. Unfortunately, its unauthenticated architecture has become the basis for many security attacks. To address this, DNS Security Extensions (DNSSEC) were introduced in 1997. D ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · August 1, 2017
Motivated by denial-of-service network attacks, we introduce the symmetric interdiction model, where both the interdictor and the optimizer are subject to the same constraints of the underlying optimization problem. We give a general framework that relates ...
Full textCite
ConferenceProceedings - IEEE Symposium on Security and Privacy · June 23, 2017
Currently, no major browser fully checks for TLS/SSL certificate revocations. This is largely due to the fact that the deployed mechanisms for disseminating revocations (CRLs, OCSP, OCSP Stapling, CRLSet, and OneCRL) are each either incomplete, insecure, i ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2017
In principle, a network can transfer data at nearly the speed of light. Today’s Internet, however, is much slower: our measurements show that latencies are typically more than one, and often more than two orders of magnitude larger than the lower bound imp ...
Full textCite
ConferenceProceedings of the 26th USENIX Security Symposium · January 1, 2017
The Domain Name System’s Security Extensions (DNSSEC) allow clients and resolvers to verify that DNS responses have not been forged or modified inflight. DNSSEC uses a public key infrastructure (PKI) to achieve this integrity, without which users can be su ...
Cite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 14, 2016
SSL and TLS are used to secure the most commonly-used Internet protocols. As a result, the ecosystem of SSL certificates has been thoroughly studied, leading to a broad understanding of the strengths and weak-nesses of the certificates accepted by most web ...
Full textCite
ConferenceProceedings of the ACM Conference on Computer and Communications Security · October 24, 2016
The semantics of online authentication in the web are rather straightforward: if Alice has a certificate binding Bob's name to a public key, and if a remote entity can prove knowledge of Bob's private key, then (barring key compromise) that remote entity m ...
Full textCite
Journal ArticleACM Transactions on Algorithms · August 1, 2016
We study the problem of routing in doubling metrics and show how to perform hierarchical routing in such metrics with small stretch and compact routing tables (i.e., with a small amount of routing information stored at each vertex). We say that a metric (X ...
Full textCite
ConferencePerformance Evaluation Review · June 1, 2016
As popular web sites turn to content delivery networks (CDNs) for full-site delivery, there is an opportunity to improve the end-user experience by optimizing the delivery of entire web pages, rather than just individual objects. In particular, this paper ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · October 28, 2015
Critical to the security of any public key infrastructure (PKI) is the ability to revoke previously issued certificates. While the overall SSL ecosystem is well-studied, the frequency with which certificates are revoked and the circumstances under which cl ...
Full textCite
Journal ArticleJournal of Interconnection Networks · October 1, 2015
This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs G1=(V1, E1) and G2=(V2,E2) is an identification of the vertices of V1 and V2, i.e., a bijection :V1aV 2, together with an embedding of G ...
Full textCite
ConferenceComputer Communication Review · July 1, 2015
This paper "peeks under the covers" at the subsystems that provide the basic functionality of a leading content delivery network. Based on our experiences in building one of the largest distributed systems in the world, we illustrate how sophisticated algo ...
Full textCite
Journal ArticleComputer · April 1, 2015
Secure delivery networks can help prevent or mitigate the most common attacks against mission-critical websites. A case study from a leading provider of content delivery services illustrates one such network's operation and effectiveness. ...
Full textCite
ConferenceACM International Conference Proceeding Series · January 4, 2015
This paper proposes an approach to the design of large-scale general-purpose data center networks based on the notions of volume and area universality introduced by Leiserson in the 1980's in the context of VLSI design. In particular, we suggest that the p ...
Full textCite
ConferenceProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · November 5, 2014
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-offi ...
Full textCite
ConferenceProceedings of the 13th ACM Workshop on Hot Topics in Networks, HotNets 2014 · October 27, 2014
For many Internet services, reducing latency improves the user experience and increases revenue for the service provider. While in principle latencies could nearly match the speed of light, we find that infrastructural inefficiencies and protocol overheads ...
Full textCite
Journal ArticleProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · December 16, 2013
Content distribution systems have traditionally adopted one of two architectures: infrastructure-based content delivery networks (CDNs), in which clients download content from dedicated, centrally managed servers, and peer-to-peer CDNs, in which clients do ...
Full textCite
Journal ArticleComputer Communication Review · December 1, 2013
Information-Centric Networking (ICN) has seen a significant resurgence in recent years. ICN promises benefits to users and service providers along several dimensions (e.g., performance, security, and mobility). These benefits, however, come at a non-trivia ...
Full textCite
Journal ArticleSIGCOMM 2013 - Proceedings of the ACM SIGCOMM 2013 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication · September 5, 2013
Information-Centric Networking (ICN) has seen a significant resurgence in recent years. ICN promises benefits to users and service providers along several dimensions (e.g., performance, security, and mobility). These benefits, however, come at a non-trivia ...
Full textCite
Journal ArticleComputer Communication Review · October 1, 2012
Today, a large fraction of Internet traffic is originated by Content Delivery Networks (CDNs). To cope with increasing demand for content, CDNs have deployed massively distributed infrastructures. These deployments pose challenges for CDNs as they have to ...
Full textCite
ConferenceProceedings of NSDI 2012: 9th USENIX Symposium on Networked Systems Design and Implementation · January 1, 2012
Content distribution networks (CDNs) have started to adopt hybrid designs, which employ both dedicated edge servers and resources contributed by clients. Hybrid designs combine many of the advantages of infrastructure-based and peer-to-peer systems, but th ...
Cite
Journal ArticleACM Transactions on Algorithms · December 1, 2009
We consider the problem of simultaneous source location: selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied simultaneously, with the goal of minimizing the number of locations chosen. For general direct ...
Full textCite
Journal ArticleComputer Communication Review · November 30, 2009
Energy expenses are becoming an increasingly important fraction of data center operating costs. At the same time, the energy expense per unit of computation can vary significantly between two difierent locations. In this paper, we characterize the variatio ...
Full textCite
Journal ArticleProceedings - International Conference on Data Engineering · July 8, 2009
A promising approach to scaling Web applications is to distribute the server infrastructure on which they run. This approach, unfortunately, can introduce latency between the application and database servers, which in turn increases the network latency of ...
Full textCite
Journal ArticleIEEE/ACM Transactions on Networking · February 1, 2008
Multihoming is increasingly being employed by large enterprises and data centers to extract good performance and reliability from their ISP connections. Multihomed end networks today can employ a variety of route control products to optimize their Internet ...
Full textCite
Journal ArticleProceedings of the VLDB Endowment · January 1, 2008
The backend database system is often the performance bottleneck when running web applications. A common approach to scale the database component is query result caching, but it faces the challenge of maintaining a high cache hit rate while effciently ensur ...
Full textCite
Journal ArticleACM SIGCOMM 2007: Conference on Computer Communications · December 17, 2007
Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Cap ...
Full textCite
Journal ArticleProceedings of the ACM SIGCOMM Internet Measurement Conference, IMC · December 1, 2007
Several route monitoring systems have been set up to help understand the Internet routing system. They operate by gathering realtime BGP updates from different networks. Many studies have relied on such data sources by assuming reasonably good coverage and ...
Full textCite
Journal ArticleComputer Communication Review · October 1, 2007
Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Cap ...
Full textCite
Journal ArticleProceedings - International Conference on Data Engineering · September 24, 2007
For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications' query results and answers queries on their behalf. One way for applications to address their security/privacy concerns wh ...
Full textCite
Conference4th Symposium on Networked Systems Design and Implementation, NSDI 2007 · January 1, 2007
Many studies show that, when Internet links go up or down, the dynamics of BGP may cause several minutes of packet loss. The loss occurs even when multiple paths between the sender and receiver domains exist, and is unwarranted given the high connectivity ...
Cite
Journal ArticleProceedings of the ACM SIGMOD International Conference on Management of Data · December 1, 2006
For Web applications in which the database component is the bottleneck, scalability can be provided by a third-party Database Scalability Service Provider (DSSP) that caches application data and supplies query answers on behalf of the application. Cost-eff ...
Full textCite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · September 21, 2006
A quorum system over a universe of logical elements is a collection of subsets (quorums) of elements, any two of which intersect. In numerous distributed algorithms, the elements of the universe reside on the nodes of a physical network and the participati ...
Cite
Journal Article2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings · January 1, 2006
This paper surveys a collection of theoretical results that relate the congestion and dilation of the paths taken by a set of packets in a network to the time required for their delivery, or to the rate at which they can be delivered, where the congestion ...
Full textCite
Journal ArticleAnnual ACM Symposium on Parallelism in Algorithms and Architectures · December 1, 2005
In 1995, Gremban, Miller, and Zagha introduced support-tree preconditioners and a parallel algorithm called supporttree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where A is an n × n Laplacian matrix. A Laplacian is a symmetri ...
Full textCite
Journal Article2nd Biennial Conference on Innovative Data Systems Research, CIDR 2005 · December 1, 2005
Providers of dynamicWeb applications are currently unable to accommodate heavy usage without significant investment in infrastructure and in-house management capability. Our goal is to develop technology to enable a third party to offer scalability as a su ...
Cite
ConferenceProceedings of the Annual ACM Symposium on Principles of Distributed Computing · January 1, 2005
A quorum system is a family of sets (themselves called quorums), each pair of which intersect. In many distributed algorithms, the basic unit accessed by a client is a quorum of nodes. Such algorithms are used for applications such as mutual exclusion, dat ...
Full textCite
Journal ArticleComputer Communication Review · December 1, 2004
While application end-point architectures have proven to be viable solutions for large-scale distributed applications such as distributed computing and file-sharing, there is little known about its feasibility for more bandwidth-demanding applications such ...
Full textCite
Journal ArticleComputer Communication Review · December 1, 2004
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 ...
Full textCite
Journal ArticleComputer Communication Review · December 1, 2004
The limitations of BGP routing in the Internet are often blamed for poor end-to-end performance and prolonged connectivity interruptions. Recent work advocates using overlays to effectively bypass BGP's path selection in order to improve performance and fa ...
Full textCite
Chapter · January 1, 2004
The subject of this chapter is the design and analysis of parallel algorithms. Most of today’s computer algorithms are sequential, that is, they specify a sequence of steps in which each step consists of a single operation. As it has become more difficult ...
Cite
Journal ArticleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2004
We consider the problem of Simultaneous Source Location -selecting locations for sources in a capacitated graph such that a given set of demands can be satisfied. We give an exact algorithm for trees and show how this can be combined with a result of Räcke ...
Full textCite
Journal ArticleProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004 · January 1, 2004
In this paper, we study the live streaming workload from a large content delivery network. Our data, collected over a 3 month period, contains over 70 million requests for 5,000 distinct URLs from clients in over 200 countries. To our knowledge, this is th ...
Full textCite
Journal ArticleProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004 · January 1, 2004
The Domain Name System (DNS) is a critical part of the Internet's infrastructure, and is one of the few examples of a robust, highly-scalable, and operational distributed system. Although a few studies have been devoted to characterizing its properties, su ...
Full textCite
Journal ArticleProceedings of the 2004 ACM SIGCOMM Internet Measurement Conference, IMC 2004 · January 1, 2004
This paper introduces a methodology for estimating interdomain Web traffic flows between all clients worldwide and the servers belonging to over one thousand content providers. The idea is to use the server logs from a large Content Delivery Network (CDN) ...
Full textCite
Journal ArticleProceedings - IEEE INFOCOM · December 1, 2003
Locating content in decentralized peer-to-peer systems is a challenging problem. Gnutella, a popular file-sharing application, relies on flooding queries to all peers. Although flooding is simple and robust, it is not scalable. We explore how to retain the ...
Full textCite
Journal ArticleComputer Communication Review · January 1, 2003
Multihoming has traditionally been employed by stub networks to enhance the reliability of their network connectivity. With the advent of commercial "intelligent route control" products, stubs now leverage multihoming to improve performance. Although multi ...
Full textCite
Journal ArticleProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2003
We show how to support the finger search operation on degree-balanced search trees in a space-efficient, manner that retains a worst-case time bound of O(logd), where d is the difference in rank between successive search targets. While most existing tree-b ...
Cite
Journal ArticleAnnual ACM Symposium on Parallel Algorithms and Architectures · January 1, 2003
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to within a constant factor of optimal, and cost to within a lo ...
Full textCite
Journal ArticleAlgorithmica (New York) · January 1, 2003
This paper introduces a model for parallel computation, called the distributed random-assess machine (DRAM), inwhich the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory acc ...
Cite
Journal ArticleIEEE Internet Computing · September 1, 2002
A company, Akamai Technologies, evolved out of an MIT research effort aimed at solving a flash crowd problem. An approach based on the observation that serving Web content from a single location can present serious problems for site scalability, reliabilit ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2002Cite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 2001Cite
Journal ArticleTheory of Computing Systems · January 1, 2001
This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an n-input butterfly network is 2(√2 -1)n + o(n) ≈ 0.82n without wraparound, and n with wraparound. T ...
Full textCite
Journal ArticleJournal of Computer and System Sciences · January 1, 2001
In this paper we examine the problem of sending an n-bit data item from a client to a server across an asymmetric communication channel. We demonstrate that there are scenarios in which a high-speed link from the server to the client can be used to greatly ...
Full textCite
Journal ArticleJournal of Computer and System Sciences · January 1, 2001
This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link, can support up to B virtual channels. We show that it is po ...
Full textCite
Journal ArticleAlgorithmica (New York) · December 1, 2000
This paper shows that an N-node AKS network 0as described by Paterson) can be embedded in a (3N/2)-node twinbutterfly network (i.e., a multibutterfly constructed by superimposing two butterfly networks) with load 1, congestion 1, and dilation 2. The result ...
Full textCite
Journal ArticleAlgorithmica (New York) · January 1, 2000
This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap, as well as on various sorting al ...
Full textCite
Journal ArticleSIAM Journal on Computing · January 1, 1999
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximu ...
Full textCite
Journal ArticleAnnual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1999
In this paper we demonstrate that parallelism and fill can be traded off in orders for Gaussian elimination. While the well-known nested dissection algorithm produces very parallel elimination orders, we show that by reducing the parallelism it is possible ...
Full textCite
Journal ArticleSIAM Journal on Computing · January 1, 1999
This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any greedy queuing protocol, a routing problem in which each of the N inputs sends a packet to a randomly chosen output requires O ...
Full textCite
Journal ArticleCombinatorica · January 1, 1999
In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to their destinations in O(c+d) steps using constant-size queues ...
Full textCite
Journal ArticleAnnual Symposium on Foundations of Computer Science - Proceedings · December 1, 1998
The problem of sending an n-bit data item from a client to a server across a asymmetric communication channel is investigated. The scenarios in which a high-speed link from the server to the client can be used to greatly reduce the number of bits sent from ...
Cite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1998
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and ...
Full textCite
Journal ArticleTheory of Computing Systems · January 1, 1998
We have developed a methodology for predicting the performance of parallel algorithms on real parallel machines. The methodology consists of two steps. First, we characterize a machine by enumerating the primitive operations that it is capable of performin ...
Full textCite
Journal ArticleProceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998 · January 1, 1998
The paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. Previously it was known that the bisection width of an n-input butterfly with wraparound is n. We show that without wraparound, the bisect ...
Full textCite
Journal ArticleConference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1998
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for the messages with small congestion, dilation, and setup tim ...
Full textCite
Journal ArticleAnnual Symposium on Foundations of Computer Science - Proceedings · December 1, 1997
The static and dynamic data management are investigated in computer systems where the computing nodes are connected by a relatively sparse network. In the static model, it is assume that the given application for which the rates of read and write accesses ...
Cite
Journal ArticleAnnual Symposium on Foundations of Computer Science - Proceedings · December 1, 1997
This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can ...
Cite
Journal ArticleSIAM Journal on Computing · January 1, 1997
In this paper we study the ability of array-based networks to tolerate worst-case faults. We show that an N × N two-dimensional array can sustain N1-∈ worst-case faults for any fixed ∈ > 0, and still emulate T steps of a fully functioning N × N array in O( ...
Full textCite
Journal ArticleConference Proceedings of the Annual ACM Symposium on Theory of Computing · January 1, 1997
This paper shows that an N-node AKS network (as described by Paterson) can be embedded in a 3N/2-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorith ...
Full textCite
Journal ArticleJournal of the ACM · January 1, 1997
In this paper, we study the problem of emulating TG steps of an NG-node guest network, G, on an NH-node host network, H. We call an emulation work-preserving if the time required by the host, TH, is O(TGNG/NH), because then both the guest and host networks ...
Full textCite
Journal ArticleComputer Vision and Image Understanding · January 1, 1996
A stereo algorithm is presented that optimizes a maximum likelihood cost function. The maximum likelihood cost function assumes that corresponding features in the left and right images are normally distributed about a common true value and consists of a we ...
Full textCite
Journal ArticleSIAM Journal on Computing · January 1, 1996
This paper presents the first optimal-time algorithms for path selection in an optimalsize nonblocking network. In particular, we describe an N-input, N-output, nonblocking network with O(N log N) bounded-degree nodes, and an algorithm that can satisfy any ...
Full textCite
Journal ArticleAnnual ACM Symposium on Parallel Algorithms and Architectures · January 1, 1996
This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We show that in any network in which each physical channel can emulate up to Q virtual channels, it is possible to route any set of L-bit messages whose p ...
Full textCite
Journal ArticleProceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN · January 1, 1996
This paper takes a critical look at the following three maxims. 1. Parallel architecture is converging on a design based on commodity microprocessor chips. 2. Wormhole routing is decidedly more efficient than store-and-forward routing. 3. The PRAM is an un ...
Cite
Journal ArticleAnnual Symposium on Foundations of Computer Science - Proceedings · December 1, 1995
In this paper we show that even if every node or edge in an N-node butterfly network fails independently with some constant probability, p, it is still possible to identify a set of Θ(N) nodes between which packets can be routed in any permutation in O(log ...
Cite
ConferenceProceedings of the Annual Hawaii International Conference on System Sciences · January 1, 1995
In the realm of sequential computing, the random access machine has successfully provided an underlying model of computation that has promoted consistency and coordination among algorithm developers, computer architects and language experts. In the realm o ...
Full textCite
ConferenceProceedings of the Annual Hawaii International Conference on System Sciences · January 1, 1995
In 1988, Leighton, Maggs and Rao (1988) showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to their destinations in O(c+d) steps using constant-size ...
Full textCite
Journal ArticleCombinatorica · June 1, 1994
In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, in O(c+d) steps, where c is the congestion of the paths in the network, and d is the length of the longest path. The result has appl ...
Full textCite
Journal ArticleJournal of Algorithms · January 1, 1994
This paper presents a general paradigm for the design of packet routing algorithms for fixed-connection networks. Its basis is a randomized on-line algorithm for scheduling any set of N packets whose paths have congestion c on any bounded-degree leveled ne ...
Full textCite
Journal ArticleIEEE Transactions on Computers · January 1, 1994
This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the network, without the aid of any off-line computation, eve ...
Full textCite
Journal ArticleProceedings of the Annual ACM Symposium on Theory of Computing · June 1, 1993
In this paper we study the ability of array-based networks to tolerate faults. We show that an N x N two- dimensional array can sustain N1-ϵ worst-case faults, for any fixed e > 0, and still emulate a fully functioning N x N array with only constant slowdo ...
Full textCite
Journal ArticleProceedings of the Annual ACM Symposium on Theory of Computing · June 1, 1993
This paper presents a simple local algorithm for load balancing in a distributed network. The algorithm makes no assumption about the structure of the network. It can be executed on a synchronous networic with fixed topology, a synchronous network with dyn ...
Full textCite
Journal ArticleStatistical Science · January 1, 1993
Randomly wired multistage networks have recently been shown to outperform traditional multistage networks in three respects. First, they have fast deterministic packet-switching and circuit-switching algorithms for routing permutations. Second, they are no ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1993
This paper presents a data structure that supports the operations of inserting and deleting elements drawn from a universe U={0⋯u-1} into a set S, and for finding the predecessors of elements of U in S. We consider both random inputs and worst-case inputs. ...
Full textCite
ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) · January 1, 1993
It has recently been discovered that randomly-wired interconnection networks outperform traditional well-structured networks in several notable respects. Among other things, randomly-wired networks have been found to be exceptionally fault-tolerant and wel ...
Full textCite
ConferenceProceedings of 7th International Parallel Processing Symposium, IPPS 1993 · January 1, 1993
This paper presents several deterministic algorithms for selecting the kth largest record from a set of n records on any n-node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap (1985), as well as on various sor ...
Full textCite
Journal ArticleProceedings of the Annual ACM Symposium on Theory of Computing · July 1, 1992
This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any pure queuing protocol, a routing problem in which each of the N inputs sends a packet to a randomly chosen output requires O(l ...
Full textCite
Journal ArticleIEEE Transactions on Computers · January 1, 1992
This paper describes simple deterministic O(log N) step algorithms for routing permutations of packets in multibutterflies and randomly-wired splitter networks. The algorithms are robust against faults (even in the worst case), and are efficient from a pra ...
Full textCite
ConferenceProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS · January 1, 1992
The authors analyze the fault-tolerance properties of several bounded-degree networks that are commonly used for parallel computation. Among other things, they show that an N-node butterfly containing N/sup 1- epsilon / worst-case faults (for any constant ...
Full textCite
Journal ArticleMathematical Systems Theory · December 1, 1991
In this paper we describe an O(log N)-bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves ...
Full textCite
ConferenceProceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1991 · June 1, 1991
We have implemented three parallel sorting algorithms on the Connection Machine Supercomputer model CM-2: Batcher's bitonic sort, a parallel radix sort, and a sample sort similar to Reif and Valiant's flashsort. We have also evaluated the implementation of ...
Full textCite
Journal ArticleProceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors · September 1, 1990
Experimental data are presented indicating that multistage interconnection networks with randomly positioned wires are likely to be substantially better for message routing applications than traditional multistage networks, such as the butterfly. The data ...
Cite
Journal ArticleAlgorithms and Architectures · January 1, 1990
In this paper, we describe an O(log N) bit-step randomized algorithm for bit-serial message routing on a hypercube. The result is asymptotically optimal, and improves upon the best previously known algorithms by a logarithmic factor. The result also solves ...
Full textCite
Journal ArticleAnnual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1989
Simple deterministic O(log N)-step algorithms for routing packets on a multibutterfly are described. The algorithms are shown to be robust against faults, even in the worst case, and to be efficient from a practical point of view. As a consequence, the mul ...
Full textCite
Journal ArticleAlgorithmica · March 1, 1988
This paper introduces a model for parallel computation, called the distributed randomaccess machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory acc ...
Full textCite
Journal ArticleInformation Processing Letters · January 25, 1988
In this paper we show that the minimum-cost spanning tree is a special case of the closed semiring path-finding problem. This observation gives us a nonrecursive algorithm for finding minimum-cost spanning trees on mesh-connected computers which has the sa ...
Full textCite
Journal ArticleAnnual Symposium on Foundations of Computer Science (Proceedings) · January 1, 1988
The packet-routing problem is examined in a network-independent context. The goal is to devise a strategy for routing that works well for a wide variety of networks. To achieve this goal, the routing problem is partitioned into two stages: a path-selection ...
Full textCite
Journal ArticleProceedings of the International Conference on Parallel Processing · December 1, 1986
Communication bandwidth is a resource ignored by most parallel random-access machine (PRAM) models. It is shown that many graph problems can be solved in parallel, not only with polylogarithmic performance, but with efficient communication at each step of ...
Cite
