Holistic Application Analysis for Update-Independence (2009)
Charles Garrod, Todd Mowry, Amit Manjhi, Anthony Tomasic, Bruce Maggs
Current database performance optimizations stop at the border between the database application and the database system, focusing either on improving the performance of just the database system or the...
Holistic Application Analysis for Update-Independence (2009)
Charles Garrod, Todd Mowry, Amit Manjhi, Anthony Tomasic, Bruce Maggs
Current database performance optimizations stop at the border between the database application and the database system, focusing either on improving the performance of just the database system or the...
Beyond Parallel Random-Access Machines (2009)
and then to analyze the complexity of different problems in the model. However, if the model fails to reflect constraints in the real world, these analyses have limited practical importance. The...
On the Performance Benefits of Multihoming Route Control (2009)
Aditya Akella, Bruce Maggs, Srinivasan Seshan, Anees Shaikh, Ramesh Sitaraman
Abstract—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...
Scalable Query Result Caching for Web Applications (2009)
Anastasia Ailamaki, Charles Garrod, Christopher Olston, Bruce Maggs, Amit Manjhi, Anthony Tomasic, ...
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...
Anastasia Ailamaki, Charles Garrod, Christopher Olston, Bruce Maggs, Amit Manjhi, Google Inc, ...
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...
On the Performance Benefits of Multihoming Route Control (2009)
Aditya Akella, Bruce Maggs, Srinivasan Seshan, Shaikh Member Ieee
Abstract—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...
Abstract Empirical Evaluation of Randomly-Wired Multistage Networks (Extended Abstract) (2009)
Tom Leighton, Derek Lisinski, Bruce Maggs
In this paper, we present experimental data indicat-ing that multistage interconnection networks with ran-domly positioned wires are likely to be substantially better for message routing applications...
ABSTRACT A Comparison of Overlay Routing and Multihoming Route Control (2008)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan
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...
Executable files vs. Memory Images (2008)
Dave Eckhardt, Bruce Maggs, Y Bryant
We will ask you to load and run a program released then You need to plan plan how to get there Simple program loader Dummy VM (please write bad code!!) Getting from kernel mode to user mode Getting...
Dave Eckhardt, Bruce Maggs, Y Bryant, Include <stdio. H, Include <stdio. H
Spring break We do not plan for you to work on Project 3 It can be an excellent time for some “light reading” 15-410, S’04
POLYHEDRAL TECHNIQUES FOR GRAPHIC COVERING PROBLEMS (2008)
Abstract The motivation of this thesis is twofold: (i) designing approximation algorithms for NP-hard covering problems in graphs by unearthing polyhedral roots to better understood problems, and...
ABSTRACT A Comparison of Overlay Routing and Multihoming Route Control (2008)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan
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...
On the Performance Benefits of Multihoming Route Control (2008)
Aditya Akella, Bruce Maggs, Srinivasan Seshan, Ramesh Sitaraman
Abstract—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...
Executable files vs. Memory Images (2008)
Dave Eckhardt, Bruce Maggs, Y Bryant
� We will ask you to load and run a program released then You need to plan how to get there � Simple program loader � Dummy VM (please write encapsulated bad code!!) � Getting from kernel...
Paper Code: P2P-2A Interest-Based Content Location in Peer-to-Peer Systems (2008)
Kunwadee Sripanidkulchai, Bruce Maggs, Hui Zhang, Presenter Xuebin Xu
What is Peer-to-Peer distributed system [1]? systems in which all nodes have identical responsibilities and all communication is symmetric, i.e. decentralization; Advantages over traditional...
Data regions (data/bss/heap) (2008)
Dave Eckhardt, Bruce Maggs, Y Bryant, Stack Pointer
Where addresses come from
THESIS PROPOSAL A Theoretical Scheduling Toolbox (2008)
Adam Wierman, John Lafferty, Bruce Maggs, Alan Scheller-wolf, Ward Whitt
Scheduling policies are fundamental components of a majority of modern computer systems. However, despite a vast field of research analyzing the performance of different policies, the task of...
Daniel R. Golovin, Konstantin Andreev, Charles Garrod, Daniel Golovin, Bruce Maggs, Adam Meyerson
RESEARCH INTERESTS Strongly history-independent/uniquely-represented data structures; Approximation & online algorithms; Resource allocation problems; Algorithmic game theory; Provably sound ways...
ABSTRACT A Measurement-Based Analysis of Multihoming (2008)
Aditya Akella, Bruce Maggs, Srinivasan Seshan
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...
ABSTRACT A Comparison of Overlay Routing and Multihoming Route Control (2008)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan
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...
ABSTRACT A Comparison of Overlay Routing and Multihoming Route Control (2008)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan, Anees Shaikh
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...
Tom Leighton, Derek Lisinski, Bruce Maggs
In this paper, we present experimental data indicating that multistage interconnection networks with randomly positioned wires are likely to be substantially better for message routing applications...
Portcullis: Protecting connection setup from denial-of-capability attacks (2007)
Bryan Parno, Adrian Perrig, Dan Wendlandt, Bruce Maggs, Elaine Shi, Yih-chun Hu
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...
Network monitoring and diagnosis based on available bandwidth measurement (2006)
the Korea Information Security Agency in conjunction with CyLab Korea. The views and conclusions contained herein are those of the author and should not be interpreted as representing the official...
FANFARE for the common flow (2005)
Elaine Shi, Bryan Parno, Adrian Perrig, Yih-chun Hu, Bruce Maggs
This paper presents FANFARE 1, a suite of infrastructure-based primitives that empowers routers and receivers to secure and enforce various flow-control mechanisms, such as per-flow admission...
FANFARE for the common flow (2005)
Elaine Shi, Bryan Parno, Adrian Perrig, Yih-chun Hu, Bruce Maggs
This paper presents FANFARE 1, a suite of infrastructure-based primitives that empowers routers and receivers to secure and enforce various flow-control mechanisms, such as per-flow admission...
Methodology for estimating interdomain web traffic demand (2004)
Feldmann, Anja, Maennel, Olaf Manuel, Kammenhuber, Nils, Maggs, Bruce, De Prisco, Roberto, Sundaram, Ravi
Copyright 2004 ACM
Locating Internet Routing Instabilities (2004)
Feldmann, Anja, Maennel, Olaf Manuel, Mao, Z. Morley, Berger, Arthur, Maggs, Bruce
Copyright 2004 ACM
Methodology for estimating interdomain web traffic demand (2004)
Feldmann, Anja, Maennel, Olaf Manuel, Kammenhuber, Nils, Maggs, Bruce, De Prisco, Roberto, Sundaram, Ravi
Copyright 2004 ACM
Locating Internet Routing Instabilities (2004)
Feldmann, Anja, Maennel, Olaf Manuel, Mao, Z. Morley, Berger, Arthur, Maggs, Bruce
Copyright 2004 ACM
An analysis of live streaming workloads on the Internet (2004)
Kunwadee Sripanidkulchai, Bruce Maggs
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...
Simultaneous source location (2004)
Konstantin Andreev, Charles Garrod, Bruce Maggs, Adam Meyerson
Abstract. 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...
Simultaneous source location (2004)
Konstantin Andreev, Charles Garrod, Bruce Maggs
Abstract. 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...
Availability, usage, and deployment characteristics of the domain name system (2004)
Jeffrey Pang, Roberto De Prisco, Hash Tables, James Hendricks, Bruce Maggs
The Domain Name System (DNS) is a critical part of the Internet’s infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few...
Availability, usage, and deployment characteristics of the domain name system (2004)
Jeffrey Pang, Roberto De Prisco, Hash Tables, James Hendricks, Bruce Maggs
The Domain Name System (DNS) is a critical part of the Internet’s infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few...
Locating Internet Routing Instabilities (2004)
Anja Feldmann, Olaf Maennel, Z. Morley Mao, Arthur Berger, Bruce Maggs
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...
An Analysis of Live Streaming Workloads on the Internet (2004)
Kunwadee Sripanidkulchai Bruce, Bruce Maggs
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...
A Methodology for Estimating Interdomain Web Traffic Demand (2004)
Anja Feldmann, Nils Kammenhuber, Olaf Maennel, Bruce Maggs, Roberto De Prisco, Ravi Sundaram
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...
Kunwadee Sripanidkulchai, Aditya Ganjam, Bruce Maggs, Hui Zhang
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...
Availability, Usage, and Deployment Characteristics of the (2004)
Domain Name System, Jeffrey Pang, Roberto De Prisco, Hash Tables, James Hendricks, Bruce Maggs
The Domain Name System (DNS) is a critical part of the Internet's infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few...
Simultaneous Source Location (2004)
Konstantin Andreev Charles, Charles Garrod, Bruce Maggs
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...
Availability, Usage, and Deployment Characteristics of the (2004)
Domain Name System, Jeffrey Pang, Roberto De Prisco, Hash Tables, James Hendricks, Bruce Maggs
The Domain Name System (DNS) is a critical part of the Internet's infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few...
A Comparison of Overlay Routing and Multihoming Route Control (2004)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan, Anees Shaikh
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...
Simultaneous source location (2004)
Konstantin Andreev, Charles Garrod, Bruce Maggs, Adam Meyerson
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...
Availability, usage, and deployment characteristics of the domain name system (2004)
Jeffrey Pang, Roberto De Prisco, Hash Tables, James Hendricks, Bruce Maggs
The Domain Name System (DNS) is a critical part of the Internet’s infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few...
A methodology for estimating interdomain web traffic demand (2004)
Anja Feldmann, Nils Kammenhuber, Olaf Maennel, Bruce Maggs, Roberto De Prisco, Ravi Sundaram, ...
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...
A Comparison of Overlay Routing and Multihoming Route Control (2004)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan
Anees Shaikh 3 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...
Availability, usage, and deployment characteristics of the domain name system (2004)
Jeffrey Pang, Roberto De Prisco, Hash Tables, James Hendricks, Bruce Maggs
The Domain Name System (DNS) is a critical part of the Internet’s infrastructure, and is one of the few examples of a robust, highlyscalable, and operational distributed system. Although a few...
A Comparison of Overlay Routing and Multihoming Route Control (2004)
Aditya Akella, Jeffrey Pang, Bruce Maggs, Srinivasan Seshan, Anees Shaikh
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...
Efficient content location using interest-based locality in peer-to-peer systems (2003)
Kunwadee Sripanidkulchai, Bruce Maggs, Hui Zhang
Abstract--- 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...
Algorithms for Flow Time Scheduling (2003)
Bruce Maggs, Kirk Pruhs, R. Ravi, Nikhil Bansal, Nikhil Bansal
We study scheduling algorithms for problems arising in client-server systems. In the client-server setting, there are multiple clients that submit requests for service to the server(s) over time....
Simultaneous Source Location (2003)
Konstantin Andreev Charles, Charles Garrod, Bruce Maggs, Adam Meyerson
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 satis ed. We give an exact algorithm for trees...
A Measurement-Based Analysis of Multihoming (2003)
Aditya Akella, Bruce Maggs, Srinivasan Seshan, Anees Shaikh, Ramesh Sitaraman
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,...
A Measurement-Based Analysis of Multihoming (2003)
Aditya Akella Bruce, Bruce Maggs, Srinivasan Seshan
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,...
A measurement-based analysis of multihoming (2003)
Aditya Akella, Bruce Maggs, Srinivasan Seshan
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...
A measurement-based analysis of multihoming (2003)
Aditya Akella, Bruce Maggs, Srinivasan Seshan
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...
A Measurement-Based Analysis of Multihoming (2003)
Aditya Akella, Bruce Maggs, Srinivasan Seshan, Ramesh Sitaraman And Anees Shaikh, Anees Shaikh, Ramesh Sitaraman
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,...
Globally Distributed Content Delivery (2002)
John Dilley, Bruce Maggs, Jay Parikh, Harald Prokop, Bill Weihl
Using more than 12,000 servers in over 1,000 networks, Akamai’s distributed content delivery system fights service bottlenecks and shutdowns by delivering content from the Internet’s edge. As Web...
Enabling Efficient Content Location and Retrieval in (2002)
Kunwadee Sripanidkulchai, Bruce Maggs, Hui Zhang
ndomly chosen and pinged on April 23 and May 1, 2001. Figure 1 depicts the measured ping time to a peer with cable modem access. The ping times vary over a wide range from 300 milliseconds to 24...
Globally Distributed Content Delivery (2002)
John Dilley, Bruce Maggs, Jay Parikh, Harald Prokop, Bill Weihl
Using more than 12,000 servers in over 1,000 networks, Akamai’s distributed content delivery system fights service bottlenecks and shutdowns by delivering content from the Internet’s edge. As Web...
Space-Efficient Scheduling for Parallel, Multithreaded Computations (1999)
Girija Narlikar, Thomas Gross, Bruce Maggs
representing the official policies or endorsements, either expressed or implied, of ARPA or the U.S. Government.
Fast algorithms for finding O(congestion + dilation) packet routing schedules (1999)
Tom Leighton, Bruce Maggs, Andréa W. Richa
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...
Universal Packet Routing Algorithms. (1998)
Leighton, Tom, Maggs, Bruce, Rao, Satish
This paper examines the packet routing problem 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...
Work-Preserving Emulations of Fixed-Connection Networks, (1998)
Koch, Richard, Leighton, Tom, Maggs, Bruce, Rao, Satish, Rosenberg, Arnold
In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. Although many isolated emulation results have been proved for specific networks in...
Work-Preserving Emulations of Fixed-Connection Networks, (1998)
Koch, Richard, Leighton, Tom, Maggs, Bruce, Rao, Satish, Rosenberg, Arnold
In this paper the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is O(TGNG/NH)...
Competitive Analysis of Call Admission Algorithms that Allow Delay. (1998)
Feldmann, Anja, Maggs, Bruce, Sgall, Jiri, Sleator, Daniel D., Tomkins, Andrew
This paper presents an analysis of several simple on-line algorithms for processing requests for connections in distributed networks. These algorithms are called call admission algorithms. Each...
A Numerical Optimization Approach to General Graph Drawing. (1998)
Tunkelang, Daniel, Sleator, Daniel, Heckbert, Paul, Maggs, Bruce
Graphs are ubiquitous, finding applications in domains ranging from software engineering to computational biology. While graph theory and graph algorithms are some of the oldest, most studied fields...
Parallel Gaussian Elimination with Linear Work and Fill, (1997)
Bornstein, Claudson, Maggs, Bruce, Miller, Gary, Ravi, R.
This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graphs, the algorithm can be applied directly to interval...
A Parallel Algorithm for Reconfiguring a Multibutterfly Network with Faulty Switches, (1997)
Goldberg, Andrew, Maggs, Bruce, Plotkin, Serge
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...
Parallelizing Elimination Orders with Linear Fill (1997)
Claudson Bornstein, Bruce Maggs, Gary Miller, R. Ravi
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...
Parallel Gaussian Elimination with Linear Work and Fill (1997)
Claudson Bornstein, Bruce Maggs, Gary Miller, R. Ravi
This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval...
Parallel Gaussian Elimination with Linear Work and Fill (1997)
Claudson Bornstein Bruce, Bruce Maggs, Gary Miller, R. Ravi
This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval...
Exploiting Locality for Data Management in Systems of Limited Bandwidth (1997)
Bruce Maggs, Berthold Vocking, Matthias Westermann
This paper deals with data management in computer systems in which the computing nodes are connected by a relatively sparse network. We consider the problem of placing and accessing a set of shared...
Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules (1996)
Tom Leighton, Bruce Maggs, A.W. Richa, Andr'ea W. Richa
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...
Competitive Analysis of Call Admission Algorithms that Allow Delay (1995)
Anja Feldmann, Bruce Maggs, Jiri Sgall, Daniel D. Sleator, Andrew Tomkins
This paper presents an analysis of several on-line algorithms, called call admission algorithms, for processing requests for connections in distributed networks. Each request comes with a source, a...
Approximate Load Balancing on Dynamic and Asynchronous Networks (1993)
William Aiello, Baruch Awerbuch, Bruce Maggs, Satish Rao
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...
On the Fault Tolerance of Some Popular Bounded-Degree Networks (1992)
Tom Leighton, Bruce Maggs, R. Sitaraman
In this paper, we analyze the ability of several bounded-degree networks that are commonly used for parallel computation to tolerate faults. Among other things, we show that an N-node butterfly...
Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (1992)
Bruce Maggs, Ramesh K. Sitaraman
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...