Subhash Suri

Search-quality Tradeoffs for Routing in Non-ideal Wireless Networks (2008)

Modern computer systems are called on to deal with billions of events every second, whether they are instructions executed, memory locations accessed, or packets forwarded. This presents a serious...

Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Typical wireless routing protocols like AODV/DSR are not scalable to very large networks because they employ flooding for route discovery. Geographic routing protocols like GPSR are highly scalable...

Formulating and Implementing Profiling over Adaptive Ranges (2008)

Shashidhar Mysore, Banit Agrawal, Rodolfo Neuber, Timothy Sherwood, Nisheeth Shrivastava, Subhash Suri

Modern computer systems are called on to deal with billions of events every second, whether they are instructions executed, memory locations accessed, or packets forwarded. This presents a serious...

Contour Approximation in Sensor Networks Chiranjeeb Buragohain 1, Sorabh Gandhi 1, (2008)

Abstract. We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose...

Abstract Summarizing Spatial Data Streams Using ClusterHulls ∗ (2008)

Abstract. We propose a distributed scheme called Adaptive-Group-Merge forsensornetworksthat,givenaparameterk, approximates a geometric shape by a k-vertex polygon. The algorithm is well suited to the...

John Hershberger, Nisheeth Shrivastava, Subhash Suri

We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional points, how can we summarize its spatial distribution or shape using a small, bounded amount of...

Abstract (2008)

Subhash Suri, Collaborators Hershberger, Subhash Suri, Uc Santa Barbara

Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful...

Themes (2008)

• A set of distinct items: S = {1, 2,..., m}. • A set of bundle bids: B = {B1, B2,..., Bn}, where Bi ⊂ S. • Each bid has an associated positive price. • Winner determination problem is to...

Contour Approximation in Sensor Networks Chiranjeeb Buragohain 1, Sorabh Gandhi 1, (2008)

Simple Polygon Non−Simple Polygons (2008)

Abstract. We propose a distributed scheme called Adaptive-Group-Merge for sensor networks that, given a parameter k, approximates a geometric shape by a k-vertex polygon. The algorithm is well suited...

Polygon Triangulation, Subhash Suri, Uc Santa Barbara

• A polygonal curve is a finite chain of line segments. • Line segments called edges, their endpoints called vertices. • A simple polygon is a closed polygonal curve without self-intersection.

Profiling over Adaptive Ranges Shashidhar Mysore (2008)

Abstract Collision Detection in Aspect and Scale Bounded Polyhedra (2008)

Modern computer systems are called on to deal with billions of events every second, whether they are instructions executed, memory locations accessed, or packets forwarded. This presents a serious...

Subhash Suri, Philip M. Hubbard, John F. Hughest

Let S be a family of n polyhedral objects in d dimen-sions, with aspect ratio bound CY and scale factor bound (T. Let K,(S) denote the number of object-pairs in S with nonempty intersection, and let...

Abstract Range Counting over Multidimensional Data Streams ∗ (2008)

Subhash Suri

We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is presented in an arbitrary...

, Guru Parulkar ¡ (2008)

Adiseshu Hari, Subhash Suri

Abstract — ¢ Packet filters are rules for classifying packets based on their header fields. Packet classification is essential to routers supporting services such as Quality of Service (QoS),...

Abstract Real-world Environment Models For Mobile Network Evaluation (2008)

Amit P. Jardosh, Kevin C. Almeroth, Subhash Suri

Simulation environments are an important tool for the evaluation of new concepts in networking. The study of mobile ad hoc networks depends on understanding protocols from simulations, before these...

ABSTRACT Towards Realistic Mobility Models For Mobile Ad hoc Networks (2008)

Amit Jardosh, Kevin C. Almeroth, Subhash Suri

One of the most important methods for evaluating the characteristics of ad hoc networking protocols is through the use of simulation. Simulation provides researchers with a number of significant...

A General Framework for Wireless Spectrum (2008)

Sorabh G, Chiranjeeb Buragohain, Lili Cao, Haitao Zheng, Subhash Suri

Abstract — We propose a real-time spectrum auction framework to distribute spectrum among a large number wireless users under interference constraints. Our approach achieves conflictfree spectrum...

ABSTRACT Towards Realistic Mobility Models For Mobile Ad hoc Networks (2008)

Amit Jardosh, Kevin C. Almeroth, Subhash Suri

One of the most important methods for evaluating the characteristics of ad hoc networking protocols is through the use of simulation. Simulation provides researchers with a number of significant...

Tuomas Sandholm, Subhash Suri, Andrew Gilpin, David Levine

Combinatorial auctions where bidders can bid on bundles of items can lead to more economically efficient allocations, but determining the winners is ��-complete and inapproximable. We present...

1 Profile-Based Routing: A New Framework for MPLS Traffic Engineering (2007)

Subhash Suri, Marcel Waldvogel, Priyank Ramesh Warkhede

Abstract---We present a new algorithm and framework for dynamic routing of bandwidth guaranteed flows. The problem is motivated by the need to dynamically set up bandwidth guaranteed paths in carrier...

We prove that a set of n unit balls in R

We prove that a set of n unit balls in R

On-line Scheduling with Hard Deadlines (Extended Abstract) (2007)

Yunhong Zhou, Subhash Suri, In R

We consider the use of bounding boxes to detect collisions among a set of convex objects

Sally A. Goldman, Jyoti Parwatikar, Subhash Suri

) Sally A. Goldman ? and Jyoti Parwatikar ?? and Subhash Suri ??? Dept. of CS, Washington University, St. Louis MO 63130, USA fsg, jp, surig@cs.wustl.edu Abstract. We study non-preemptive, online...

Abstract Profile-Based Routing and Traffic Engineering ∗ (2007)

Subhash Suri, Marcel Waldvogel, Daniel Bauer, Priyank Ramesh Warkhede

We present a new algorithm and framework for dynamic routing of bandwidth-guaranteed flows. The problem is motivated by the need to set up bandwidth-guaranteed paths in carrier and ISP networks...

Subhash Suri, Tuomas S, Priyank Warkhede

Abstract. We consider an algorithmic problem that arises in the context of routing tables used by Internet routers. The Internet addressing scheme is hierarchical, where a group of hosts are...

$ilo Rinbow, $lble, 1%ult Caching Token: Schemes for Tolerant Stream Caching (2007)

Youngsu Chae, Katherine Guo, Milind M. Buddhikot, Subhash Suri, Ellen W. Zegura

Abstract--In the current Internet, web content is increasingly being cached closer to the end-user to reduce network and web server load and improve performance. Existing web caching systems [1]...

Abstract Finding the k Shortest Simple Paths: A New Algorithm and its Implementation (2007)

John Hershberger, Matthew Maxel, Subhash Suri

We describe a new algorithm to enumerate the k shortest simple (loopless) paths in a directed graph and report on its implementation. Our algorithm is based on a replacement paths algorithm proposed...

References (2007)

Roberto Tamassia, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...

The proposed research will be in the area of applied algorithms in both the sequential and parallel domains. The focus of this work will be on the design and testing of realistic algorithms for...

Cisco Systems (2007)

Subhash Suri, Tuomas Sandholm, Priyank Warkhede

We consider an algorithmic problem that arises in the context of routing tables used by Internet routers. The Internet addressing scheme is hierarchical, where a group of hosts are identied by a...

z (2007)

Subhash Suri, Philip M. Hubbard, John F. Hughes

Heuristics that exploit bounding boxes are common in algorithms for rendering, modeling and animation. While experience has shown that bounding boxes improve the performance of these algorithms in...

On-line Scheduling with Hard Deadlines (Extended Abstract) (2007)

Sally A. Goldman, Jyoti Parwatikar, Subhash Suri

Abstract. We study non-preemptive, online admission control in the hard deadline model: each job must be either serviced prior to its deadline, or be rejected. Our setting consists of a single...

Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations (2007)

Tuomas S, Subhash Suri

Combinatorial auctions can be used to reach efficient resource and task allocations in multiagent systems where the items are complementary. Determining the winners is NP-complete and inapproximable,...

Geometric permutations of balls with bounded size disparity (2007)

Geometric permutations of balls with bounded size disparity (2007)

We study combinatorial bounds for geometric permutations of balls with bounded size disparity in d-space. Our main contribution is the following theorem: given a set S of n disjoint balls in R

Equilibria and Selfish Behavior in Peer Matching (2007)

We study combinatorial bounds for geometric permutations of balls with bounded size disparity in d-space. Our main contribution is the following theorem: given a set S of n disjoint balls in R d, if...

Anshul Kothari, Subhash Suri, Csaba D. Toth

Peer to peer networks are distributed data-sharing systems without a centralized infrastructure.

Abstract (2007)

Approximately-Strategyproof and Tractable (2007)

Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful...

Multi-unit Auctions, Anshul Kothari, David C. Parkes, Subhash Suri

We present an approximately-efficient and approximately-strategyproof auction mechanism for a single-good multi-unit allocation problem. The bidding language allows marginaldecreasing piecewise...

Counting Targets with Mobile Sensors in an Unknown Environment (2007)

Subhash Suri, Beat Gfeller, Elias Vicari, Peter Widmayer

We consider the problem of counting the number of indistinguishable targets using a simple binary sensing model. Our setting includes an unknown number of point targets in a (simply- or...

P.: Simple robots with minimal sensing: From local visibility to global geometry (2007)

Subhash Suri

We consider problems of geometric exploration and selfdeployment for simple robots that can only sense the combinatorial (non-metric) features of their surroundings. Even with such a limited sensing,...

07151 Abstracts Collection -- Geometry in Sensor Networks (2007)

Suri, Subhash, Wattenhofer, Roger, Widmayer, Peter

From 9.4.2007 to 13.4.07, the Dagstuhl Seminar 07151 ``Geometry in Sensor Networks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several...

Distributed navigation algorithms for sensor networks (2006)

Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Abstract — We propose efficient distributed algorithms to aid navigation of a user through a geographic area covered by sensors. The sensors sense the level of danger at their locations and we use...

Geometric Approaches to Ad Hoc and Sensor Networks: Full Report of the 2006 NSF Workshop (2006)

Subhash Suri, Alon Efrat, Leonidas J. Guibas

Embedded networked sensing devices are becoming ubiquitous across many activities that are important to our economy and life, from manufacturing and industrial sensing, to agriculture and...

Improved throughput bounds for interference-aware routing in wireless networks (2006)

Chiranjeeb Buragohain, Subhash Suri, Csaba D. Tóth, Yunhong Zhou

Abstract. We propose new algorithms and improved bounds for interference-aware routing in wireless networks. First, we prove that n arbitrarily matched source-destinations pairs with average distance...

Distributed navigation algorithms for sensor networks (2006)

Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Abstract — We propose efficient distributed algorithms to aid navigation of a user through a geographic area covered by sensors. The sensors sense the level of danger at their locations and we use...

Paradigms for Summarizing Data in Sensor Networks (2006)

Subhash Suri

Remote monitoring and response are intended to be a major application for sensor networks. The low cost and untethered nature of microsensors makes it possible to deploy them over large geographical...

Improved throughput bounds for interference-aware routing in wireless networks (2006)

Chiranjeeb Buragohain, Subhash Suri, Csaba D. Tóth, Yunhong Zhou

Abstract — We propose new algorithms and improved bounds for interference-aware routing in wireless networks. First, we prove that n arbitrarily matched source-destination pairs with average...

Distributed Navigation Algorithms for Sensor Networks (2005)

Buragohain, Chiranjeeb, Agrawal, Divyakant, Suri, Subhash

We propose efficient distributed algorithms to aid navigation of a user through a geographic area covered by sensors. The sensors sense the level of danger at their locations and we use this...

Interval subset-sum and uniform-price auction clearing (2005)

Anshul Kothari, Subhash Suri, Yunhong Zhou

Abstract. We study the interval subset sum problem (ISSP), a generalization of the classic subset-sum problem, where given a set of intervals, the goal is to choose a set of integers, at most one...

Attribute-based access to distributed data over P2P networks (2005)

Divyakant Agrawal, Amr El Abbadi, Subhash Suri

Abstract. Peer-to-peer (P2P) networks are distributed data sharing systems with no dedicated and centralized infrastructure. These systems are attractive because they deliver on the Internet’s...

Detecting Cuts in Sensor Networks (2005)

Detecting Cuts in Sensor Networks (2005)

Abstract — We propose a low overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An ε-cut,...

Real-world environment models for mobile network evaluation (2005)

Abstract — We propose a low overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An ε-cut,...

Amit P. Jardosh, Kevin C. Almeroth, Subhash Suri

Simulation environments are an important tool for the evaluation of new concepts in networking. The study of mobile ad hoc networks depends on understanding protocols from simulations, before these...

Power aware routing for sensor databases (2005)

Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Abstract — Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensor network databases like TinyDB [1] are the dominant architectures to...

CABOB: A fast optimal algorithm for winner determination in combinatorial auctions (2005)

Tuomas Sandholm, Subhash Suri, Andrew Gilpin, David Levine, Combinenet Inc

Combinatorial auctions where bidders can bid on bundles of items can lead to more economically efficient allocations, but determining the winners is N P-complete and inapproximable. We present CABOB,...

Space Complexity of Hierarchical Heavy Hitters (2005)

John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth

Heavy hitters, which are items occurring with frequency above a given threshold, are an important aggregation and summary tool when processing data streams or data warehouses. Hierarchical heavy...

Power Aware Routing for Sensor Databases (2004)

Buragohain, Chiranjeeb, Agrawal, Divyakant, Suri, Subhash

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensor network databases like TinyDB are the dominant architectures to extract and manage data...

Medians and Beyond: New Aggregation Techniques for Sensor Networks (2004)

Shrivastava, Nisheeth, Buragohain, Chiranjeeb, Agrawal, Divyakant, Suri, Subhash

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very...

Routing Bandwidth-Guaranteed Paths with Restoration in Label-Switched Networks (2004)

Norden, Samphel, Buddhikot, Milind M., Waldvogel, Marcel, Suri, Subhash

A Network Service Provider (NSP) operating a label-switched networks such as ATM or Multi-Protocol Label Switching (MPLS) networks, sets up end-to-end bandwidth-guaranteed Label-Switched Paths (LSPs)...

Uncoordinated load balancing and congestion games in p2p systems (2004)

Congestion games, load balancing, and price of anarchy (2004)

Abstract. In P2P systems, users often have many choices of peers from whom to download their data. Each user cares primarily about its own response time, which depends on how many other users also...

Anshul Kothari, Subhash Suri, Csaba D. Tóth, Yunhong Zhou

Abstract. Imagine a set of self-interested clients, each of whom must choose a server from a permissible set. A server’s latency is inversely proportional to its speed, but it grows linearly with...

Selfish load balancing and atomic congestion games (2004)

Subhash Suri, Csaba D. T'oth, Yunhong Zhou

Abstract We revisit a classical load balancing problem in the modern context of decentralized systems andself-interested clients. In particular, there is a set of clients, each of whom must choose a...

Range counting over multidimensional data streams (2004)

Subhash Suri, Csaba D. T'oth, Yunhong Zhou

\Lambda \Lambda Abstract We consider the problem of approximate range counting over streams of d-dimensional points. In the data stream model, the algorithm makes a single scan of the data, which is...

Medians and Beyond: New Aggregation Techniques for Sensor Networks (2004)

Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very...

Binary space partitions of orthogonal subdivisions (2004)

John Hershberger, Subhash Suri, Csaba D. Tóth

We consider the problem of constructing binary space partitions (BSPs) for orthogonal subdivisions (space filling packings of boxes) in d-space. We show that a subdivision with n boxes can be refined...

Uncoordinated load balancing and congestion games in p2p systems (2004)

A Game Theoretic Framework for Incentives in (2004)

In P2P systems, users often have many choices of peers from whom to download their data. Each user cares primarily about its own response time, which depends on how many other users also choose that...

Systems Chiranjeeb Buragohain, Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri, Advised Jens Graupmann

This paper proposed a di#erential service model based on Game Theory. P2P system that implements this model can eliminate free riding and provide predictable level of service. Such predictable level...

Medians and Beyond: New Aggregation Techniques (2004)

For Sensor Networks, Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very...

Selfish load balancing and atomic congestion games (2004)

Adaptive Spatial Partitioning for Multidimensional Data Streams (2004)

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server...

John Hershberger, Nisheeth Shrivastava, Subhash Suri, Csaba D. Tóth

We propose a space-efficient scheme for summarizing multidimensional data streams. Our sketch can be used to solve spatial versions of several classical data stream queries efficiently. For instance,...

Selfish load balancing and atomic congestion games (2004)

Subhash Suri, Csaba D. Tóth

We revisit a classical load balancing problem in the modern context of decentralized systems and self-interested clients. In particular, there is a set of clients, each of whom must choose a server...

Routing Bandwidth-Guaranteed Paths with Restoration In Label-Switched Networks (2004)

Samphel Norden, Milind Buddhikot, Marcel Waldvogel, Subhash Suri

A Network Service Provider (NSP) operating a label-switched networks such as ATM or Multi-Protocol Label Switching (MPLS) networks, sets up end-to-end bandwidth-guaranteed Label-Switched Paths (LSPs)...

A Game Theoretic Framework for Incentives in P2P Systems (2003)

Buragohain, Chiranjeeb, Agrawal, Divyakant, Suri, Subhash

Peer-To-Peer (P2P) networks are self-organizing, distributed systems, with no centralized authority or infrastructure. Because of the voluntary participation, the availability of resources in a P2P...

Profile-Based Routing : a New Framework for MPLS Traffic Engineering (2003)

Suri, Subhash, Waldvogel, Marcel, Warkhede, Priyank Ramesh

We present a new algorithm and framework for dynamic routing of bandwidth-guaranteed flows. The problem is motivated by the need to set up bandwidth-guaranteed paths in carrier and ISP networks...

Approximately-strategyproof and tractable multi-unit auctions (2003)

Anshul Kothari, David C. Parkes, Subhash Suri

We present an approximately-efficient and approximatelystrategyproof auction mechanism for a single-good multi-unit allocation problem. The bidding language in our auctions allows marginal-decreasing...

A Game Theoretic Framework for Incentives in P2P Systems (2003)

Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri

Peer-To-Peer (P2P) networks are self-organizing, distributed systems, with no centralized authority or infrastructure. Because of the voluntary participation, the availability of resources in a P2P...

Improved Winner Determination in Combinatorial Auctions and Generalizations (2003)

Tuomas Sandholm, Subhash Suri

Combinatorial auctions can be used to reach ecient resource and task allocations in multiagent systems where the items are complementary (or substitutable). Determining the winners is NP-complete and...

On the Difficulty of Some Shortest Path Problems (2003)

John Hershberger, Subhash Suri, Amit Bhosle

We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem:...

On the Difficulty of Some Shortest Path Problems (2003)

John Hershberger, Subhash Suri, Amit Bhosle

We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem:...

Towards Realistic Mobility Models for Mobile Ad hoc Networks (2003)

Amit Jardosh, Kevin C. Almeroth, Subhash Suri

One of the most important methods for evaluating the characteristics of ad hoc networking protocols is through the use of simulation. Simulation provides researchers with a number of significant...

On the Difficulty of Some Shortest Path Problems (2003)

John Hershberger, Subhash Suri, Amit Bhosle

We prove super-linear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem:...

Bandwidth-Constrained Allocation in Grid Computing (2003)

Anshul Kothari, Subhash Suri, Yunhong Zhou

Grid computing systems pool together the resources of many workstations to create a virtual computing reservoir. Users can "draw" resources using a pay-as-you-go model, commonly used for...

Algorithms for a minimum volume enclosing simplex in three dimensions (2002)

Algorithms for a minimum volume enclosing simplex in three dimensions (2002)

We develop a combinatorial algorithm for determining a minimum volume simplex enclosing a set of points in R 3

Approximately-Strategyproof and Tractable Multi-Unit Auctions (2002)

We develop a combinatorial algorithm for determining a minimum volume simplex enclosing a set of points in R

Anshul Kothari, David C. Parkes, Subhash Suri

We present a fully polynomial-time approximation scheme for the single-good multi-unit auction problem. Our scheme is both approximately e#cient and approximately strategyproof. We consider both a...

Winner Determination in Combinatorial Auction Generalizations (2002)

Tuomas Sandholm, Subhash Suri, Andrew Gilpin, David Levine

Combinatorial markets where bids can be submitted on bundles of items can be economically desirable coordination mechanisms in multiagent systems where the items exhibit complementarity and...

Erratum to “Vickrey prices and shortest paths: What is an edge worth (2002)

Routing Bandwidth Guaranteed Paths with Restoration in Label Switched Networks (2001)

the following replacement paths problem: Given a graph � with non-negative edge weights, and a pair of nodes Ü � Ý, let È � � � � ��Ô denote the sequence of edges in a...

Norden, Samphel, Buddhikot, Milind M., Waldvogel, Marcel, Suri, Subhash

Label switched networks have become increasingly attractive to both network providers and customers. By creating aggregate, bandwidth-reserved flows, these networks are known for their routing...

A lower bound for multicast key distribution (2001)

Jack Snoeyink, Subhash Suri, George Varghese

Abstract--With the rapidly growing importance of multicast in the Internet there have been recent proposal, such as RFC 2627, for scalable key distribution such that when the r, th user joins or...

Fast Packet Classification for Two-Dimensional Conflict-Free Filters (2001)

Fast Firewall Implementations for Software and Hardware-based Routers (2001)

Abstract—Routers can use packet classification to support advanced functions such as QoS routing, virtual private networks and access control. Unlike traditional routers, which forward packets...

Lili Qiu, George Varghese, Subhash Suri

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and diffserv. Classification can be based on an arbitrary number of fields in the packet...

Multiway range trees: Scalable ip lookup with fast updates (2001)

Subhash Suri, George Varghese, Priyank Ramesh Warkhede

Abstract—In this paper, we introduce a new IP lookup scheme with worst-case search and update time of O(log n), where n is the number of prefixes in the forwarding table. Our scheme is based on a...

Rcache: Design and analysis of scalable, fault tolerant multimedia stream caching schemes (2001)

Katherine Guo, Milind M. Buddhikot, Lucent Bell Labs, Lucent Bell Labs, Youngsu Chae, Subhash Suri

In the current Internet, web content is increasingly being cached closer to the end-user to reduce network and web server load and therefore improve performance and user perceived quality. Existing...

Market clearability (2001)

Tuomas Sandholm, Subhash Suri

Market mechanisms play a central role in AI as a coordination tool in multiagent systems and as an application area for algorithm design. Mechanisms where buyers are directly cleared with sellers,...

CABOB: A fast optimal algorithm for combinatorial auctions (2001)

Tuomas Sandholm, Subhash Suri, Andrew Gilpin, David Levine

Combinatorial auctions where bidders can bid on bundles of items can lead to more economical allocations, but determining the winners is NP-complete and inapproximable. We present CABOB, a...

Market clearability (2001)

Tuomas Sandholm, Subhash Suri

Market mechanisms play a central role in AI as a coordination tool in multiagent systems and as an application area for algorithm design. Mechanisms where buyers are directly cleared with sellers,...

Profile-Based Routing: A New Framework for MPLS Traffic Engineering (2001)

Subhash Suri, Marcel Waldvogel

Abstract—We present a new algorithm and framework for dynamic routing of bandwidth guaranteed flows. The problem is motivated by the need to dynamically set up bandwidth guaranteed paths in carrier...

Vickrey prices and shortest paths: What is an edge worth (2001)

Fast Packet Classification for Two-Dimensional Conflict-Free Filters (2001)

We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to...

Vickrey Pricing in network routing: Fast payment computation (2001)

Abstract---Routers can use packet classification to support advanced functions such as QoS routing, virtual private networks and access control. Unlike traditional routers, which forward packets...

Fast Packet Classification for Two-Dimensional Conflict-Free Filters (2001)

Eliciting truthful responses from self-interested agents is an important problem in game theory and microeconomics, and it is studied under mechanism design or implementation theory. Truthful...

Fast Packet Classification for Two-Dimensional Conflict-Free Filters (2001)

Abstract—Routers can use packet classification to support advanced functions such as QoS routing, virtual private networks and access control. Unlike traditional routers, which forward packets...

Fast Firewall Implementations for Software and Hardware-based Routers (2001)

Abstract—Routers can use packet classification to support advanced functions such as QoS routing, virtual private networks and access control. Unlike traditional routers, which forward packets...

Lili Qiu, George Varghese, Subhash Suri

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and diffserv. Classification can be based on an arbitrary number of fields in the packet...

Multiway range trees: Scalable ip lookup with fast updates (2001)

Subhash Suri, George Varghese, Priyank Ramesh Warkhede

Abstract—In this paper, we introduce a new IP lookup scheme with worst-case search and update time ofO(logn), wherenis the number of prefixes in the forwarding table. Our scheme is based on a new...

Profile-Based Routing: A New Framework for MPLS Traffic Engineering (2001)

Subhash Suri, Marcel Waldvogel

Abstract—We present a new algorithm and framework for dynamic routing of bandwidth guaranteed flows. The problem is motivated by the need to dynamically set up bandwidth guaranteed paths in carrier...

Routing bandwidth guaranteed paths with restoration in label switched networks (2001)

Samphel Norden, Milind M. Buddhikot, Marcel Waldvogel, Subhash Suri

A Network Service Provider (NSP) operating a label-switched networks such as ATM or Multi-Protocol Label Switching (MPLS) networks, sets up end-to-end bandwidth-guaranteed Label-Switched Paths (LSPs)...

Research problems in combinatorial auctions (2001)

Rakesh V. Vohra, Tuomas S, James Schummer, Subhash Suri

Many auctions involve the sale of a variety of distinct assets. Examples are airport time slots, delivery routes, network routing and furniture. Because of complementarities or substitution effects...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

Curvature-Constrained Shortest Paths in a Convex Polygon (2000)

Agarwal, Pankaj K., Biedl, Thérèse, Lazard, Sylvain, Robbins, Steve, Suri, Subhash, Whitesides, Sue

Let $B$ be a point robot moving in the plane, whose path is constrained to have curvature at most $1$, and let $\poly$ be a convex polygon with $n$ vertices. We study the collision-free, optimal path...

On-line scheduling with hard deadlines (2000)

Sally A. Goldman, Jyoti Parwatikar, Subhash Suri

We study non-preemptive, online admission control in the hard deadline model: each job must be either serviced prior to its deadline, or be rejected. Our setting consists of a single resource that...

Collision detection using bounding boxes: Convexity helps (2000)

Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations (2000)

Abstract. We consider the use of bounding boxes to detect collisions among a set of convex objects in R d. We derive tight bounds on the ratio between the number of box intersections and the number...

Tuomas Sandholm, Tuomas S, Subhash Suri

ffiCombinatorial auctions can be used to reach efficient resource and task allocations in multiagent systems where the items are complementary. Determining the winners is NP-complete and...

Detecting and Resolving Packet Filter Conflicts (2000)

Adiseshu Hari, Subhash Suri, Guru Parulkar

1 Packet filters are rules for classifying packets based on their header fields. Packet classification is essential to routers supporting services such as Quality of Service (QoS), Virtual Private...

Kinetic Connectivity for Unit Disks (2000)

Leonidas Guibas, John Hershberger, Subhash Suri, Li Zhang

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be...

Kinetic connectivity for unit disks (2000)

Leonidas Guibas, John Hershberger, Subhash Suri, Li Zhang

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be...

Space Decomposition Techniques for Fast Layer-4 Switching (1999)

Buddhikot, Milind M., Suri, Subhash, Waldvogel, Marcel

Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the packets. The filters are a powerful and uniform...

Analysis of a bounding box heuristic for object intersection (1999)

Kinetic connectivity of rectangles (1999)

Abstract. Bounding boxes are commonly used in computer graphics and other fields to improve the performance of algorithms that should process only the intersecting objects. A bounding-box-based...

Rectangular tiling in multi-dimensional arrays (1999)

We develop a kinetic data structure (KDS) for maintaining the connectivity of a set of axis-aligned rectangles moving in the plane. In the kinetic framework, each rectangle is assumed to travel along...

Adam Smith, Subhash Suri

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of non-negative numbers and an integer p, partition the array into at most p rectangular subarrays so...

Analysis of a bounding box heuristic for object intersection (1999)

Space decomposition techniques for fast layer-4 switching (1999)

Bounding boxes are commonly used in computer graphics and other fields to improve the performance of algorithms that should process only the intersecting objects. A bounding-box based heuristic...

Milind M. Buddhikot, Subhash Suri

Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the packets. The filters are a powerful and uniform...

Packet Filtering in High Speed Networks (1999)

Subhash Suri, George Varghese

The commercial viability of the future Internet depends on its ability to provide differentiated service to paying customers. The existing Internet delivers only the socalled

Analysis of a bounding box heuristic for object intersection (1999)

Packet Classification using Tuple Space Search (1999)

Bounding boxes are commonly used in computer graphics and other elds to improve the performance of algorithms that should process only the intersecting objects. A bounding box-based heuristic avoids...

V. Srinivasan, Subhash Suri, S. Suri, George Varghese

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and QoS routing. Packet classification requires matching each packet against a database...

Rectangular Tiling in Multi-Dimensional Arrays (1999)

Adam Smith, Subhash Suri

We study the following tiling problem in d dimensions: given a d-dimensional rectangular array of non-negative numbers and an integer p, partition the array into at most p rectangular subarrays so...

Packet Filtering in High Speed Networks (1999)

Subhash Suri, George Varghese

Introduction The commercial viability of the future Internet depends on its ability to provide differentiated service to paying customers. The existing Internet delivers only the so-called best...

Label placement by maximum independent set in rectangles (1998)

Agarwal, Pankaj K., Kreveld, Marc Van, Suri, Subhash

Fast and Scalable Layer Four Switching (1998)

Srinivasan, Venkatachary, Varghese, George, Suri, Subhash, Waldvogel, Marcel

In Layer Four switching, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as source address, TCP and UDP port...

Label placement by maximum independent set in rectangles (1998)

Pankaj K. Agarwal, Marc Van Kreveld, Subhash Suri

Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n)...

Fast and Scalable Layer Four Switching (1998)

V Srinivasan, George Varghese, Subhash Suri, S. Suri, Marcel Waldvogel

In Layer Four switching, the route and resources allocated to a packet are determined by the destination address as well as other header fields of the packet such as source address, TCP and UDP port...

Curvature-Constrained Shortest Paths in a Convex Polygon (Extended Abstract) (1998)

Pankaj K. Argarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, Sue Whitesides

) Pankaj K. Agarwal Therese Biedl y Sylvain Lazard z Steve Robbins x Subhash Suri -- Sue Whitesides k Abstract Let B be a point robot moving in the plane, whose path is constrained to have curvature...

Packet Filter Management for Layer 4 Switching (1998)

Hari Adiseshu, Subhash Suri, Guru Parulkar

Packet filters are rules for classifying packets based on their header fields. A filter specifies a pattern for each of the key header fields, and an action that is applied to the packet matching...

Surface Approximation and Geometric Partitions (1998)

Pankaj K. Agarwal, Subhash Suri

.<F3.842e+05> Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: given a...

Analyzing Bounding Boxes for Object Intersection (1998)

Subhash Suri, Philip M. Hubbard, John F. Hughes

Heuristics that exploit bounding boxes are common in algorithms for rendering, modeling and animation. While experience has shown that bounding boxes improve the performance of these algorithms in...

Packet Filter Management for Layer 4 Switching (1998)

Hari Adiseshu, Subhash Suri, Guru Parulkar

The Internet is being pushed to the limit by the increased demand for bandwidth and functionality. The increased demand for bandwidth is fueled by the explosive growth in the number of users and...

Efficient breakout routing in printed circuit boards (1997)

Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness (1997)

Abstract. Breakout routing is a single-layer wire-routing problem in which each of a set of pins must be connected to one of a set of vias, but no matching is prespecified. We propose a network-flow...

Subhash Suri, George Varghese, Girish Chandranmenon

Fair queuing is the mechanism by which routers schedule packets on output links in order to guarantee fairness and latency bounds. Fair queuing, along with with address lookup and switching, is one...

An Optimal Algorithm for Euclidean Shortest Paths in the Plane (1997)

A New Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness (1997)

We propose an optimal-time algorithm for a classical problem in plane computational geometry: computing a shortest path between two points in the presence of polygonal obstacles. Our algorithm runs...

Subhash Suri, George Varghese, Girish Chandranmenon

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds similar to WFQ, along with throughput fairness. Our scheme can be implemented with a...

Leap Forward Virtual Clock: A New Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness (1997)

Subhash Suri, George Varghese, Girish Chandranmenon

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds similar to WFQ, along with throughput fairness. Our scheme can be implemented with a...

Strategic Directions in Computational Geometry (1996)

Roberto Tamassia, Roberto Tamassia (editor, Pankaj K. Agarwal, Nancy Amato, Danny Z. Chen, David Dobkin, ...

ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...

Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (1996)

Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki

this paper. First, we give an algorithm to learn C

Designing Minimum Cost Nonblocking Communication Networks (1996)

J. Andrew, Subhash Suri, J. Andrew, J. Andrew Fingerhut, Fingerhut Subhash, Suri Jonathan, ...

This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network designs that, subject to...

Surface Approximation and Geometric Partitions (1996)

Pankaj K. Agarwal, Subhash Suri

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a...

Leap Forward Virtual Clock: An O(log log N) Fair Queuing Scheme with Guaranteed Delays and Throughput Fairness (1996)

Subhash Suri, Subhash Suri, George Varghese, George Varghese, Girish P. Chandranmenon, Girish P. Chandranmenon

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock , that provides endto -end delay bounds almost identical to that of PGPS fair queuing, along with throughput fairness. Our...

Design Of Nonblocking Atm Networks (1996)

J. Andrew Fingerhut, J. Andrew Fingerhut, Rob Jackson, Rob Jackson, Subhash Suri, Subhash Suri, ...

This paper considers the problem of designing ATM networks that are nonblocking with respect to virtual circuit requests, subject to specified constraints on the traffic. In this paper, we focus on...

Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (1996)

Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ! d for fixed d. More specifically, let T be any set of s halfspaces. Let x = (x1 ; : : : ; xd) be...

Leap Forward Virtual Clock: (1996)

Log Log, Subhash Suri, Subhash Suri, George Varghese, George Varghese, Girish P. Chandranmenon, ...

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds similar to PGPS, along with throughput fairness. Our scheme can be implemented with a...

Designing Minimum Cost Nonblocking Communication Networks (1996)

J. Andrew, Subhash Suri, J. Andrew, Andrew Fingerhut, Fingerhut Subhash, Suri Jonathan, ...

This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network designs that, subject to...

Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (1996)

Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ! for fixed d. More specifically, let T be a set of s halfspaces. Let x = (x 1 ; : : : ; x d ) be an...

The centroid of points with approximate weights (1995)

Marshall Bern, Leonidas Guibas, John Hershberger, Subhash Suri

3

Practical Methods for Approximating Shortest Paths on a Convex Polytope in R^3 (1995)

Morphing Binary Trees (1995)

We propose an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p; q...

Surface approximation and geometric partitions (1994)

We investigate the problem of transforming one binary tree into another by rotations, subject to certain weight constraints on the nodes of the trees. These constraints arise in the problem of...

Pankaj K. Agarwal, Subhash Suri

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a...

Surface Approximation and Geometric Partitions (1994)

Pankaj K. Agarwal, Pankaj K. Agarwal, Subhash Suri, Subhash Suri

Motivated by applications in computer graphics, visualization, and scientific computation, we study the computational complexity of the following problem: Given a set S of n points sampled from a...

Query-Sensitive Ray Shooting (1994)

Joseph Mitchell David, David M. Mount, Subhash Suri

Ray (segment) shooting is the problem of determining the first intersection between a ray (directed line segment) and a collection of polygonal or polyhedral obstacles. In order to process queries...

Data Structures for Two-Edge Connectivity in Planar Graphs (1994)

John Hershberger, Monika Rauch, Subhash Suri

We present a data structure for maintaining 2-edge connectivity information dynamically in an embedded planar graph. The data structure requires linear storage and preprocessing time for its...

Separating Bi-Chromatic Points by Parallel Lines (1994)

Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri

Given a 2-coloring of the vertices of a regular n-gon P , how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that bn=2c is a tight upper bound, and also...

Can Visibility Graphs Be Represented Compactly? (1993)

Pankaj K. Agarwal, Pankaj K. Agarwal, Noga Alon, Noga Alon, Boris Aronov, Boris Aronov, ...

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G = fG 1 ; G 2 ; : : : ; G k g is called a clique...

Matrix Searching with the Shortest Path Metric (1993)

Line Stabbing Bounds in Three Dimensions (1993)

We present an O(n) time algorithm for computing row-wise maxima or minima of an implicit, totally-monotone n \Theta n matrix whose entries represent shortest-path distances between pairs of vertices...

Pankaj K. Agarwal, Boris Aronov, Subhash Suri

Let S be a set of (possibly degenerate) triangles in ! 3 whose interiors are disjoint. A triangulation of ! 3 with respect to S, denoted by T (S), is a simplicial complex in which the interior of no...

Computing the Intersection-Depth of Polyhedra (1993)

David Dobkin, John Hershberger, David Kirkpatrick, Subhash Suri

Given two intersecting polyhedra P , Q and a direction d, find the smallest translation of Q along d that renders the interiors of P and Q disjoint. The same problem can also be posed without...

Finding a shortest diagonal of a simple polygon in linear time (1993)