| Structured P2P | Stanford Univ, '03 |
| We summarize the overall design philosophy behind a novel DHT routing layer. As of now, the design provides a conceptual framework for approaching the routing problem. An implementation is underway. We also list a set of research problems that we believe merit attention, outlining a possible line of attack. |
| Structured P2P: Hash Tables and Probably More G S Manku, Submitted to HotNets-II |
| ID Selection for DHTs | Stanford Univ, '03 |
|
We propose a simple, low-cost and decentralized ID selection scheme
for Distributed Hash Tables. Our scheme guarantees that \sigma, the
ratio of the largest partition to the smallest, is 4 w.h.p.
Insertions and deletions cost on average O(R) messages where R is the
average number of hops required to lookup a hash value. Typical
routing networks offer R = O(log n) or R = O(log n / log log n) where
n is the total number of nodes. Our scheme is better than existing
schemes which suffer from one or more of the following drawbacks:
they work for specific routing topologies or require O(R log n)
messages or do not handle deletions. We also show how \sigma can be reduced to values less than 2 at the cost of changing the IDs of a few existing nodes upon arrival/departure. The ID selection scheme also provides a low-cost algorithm for estimating n, the size of the network. It also simplifies the emulation of arbitrary parallel and randomized inter-connection network topologies. |
| ID Selection for Distributed Hash Tables G S Manku, Submitted to ICDCS 2004 |
| DHT Design: A Modular Approach | Stanford Univ, '03 |
|
We present a modular approach for designing Distributed Hash Tables
(DHTs). First, we propose a novel, low-cost ID selection algorithm
that ensures partition balance while being simple and
decentralized. A consequence is that nodes can be divided into almost
equi-sized groups that we call blobs. We demonstrate how
blobs may be used to separately solve different design problems such
as network-proximity awareness, replication for fault tolerance, and
resilience to network partitions, in a fashion that is independent of
routing topology. This clean separation of concerns underlies our
design template which can be used to create a variety of DHTs by
emulating arbitrary families of deterministic and randomized
interconnection networks (ICNs). We also provide new insights into the algorithmic and structural similarities of different families of deterministic and randomized ICNs. In doing so, we develop improved routing algorithms on some ICNs and suggest new variants of known ICNs. We experimentally validate our design on multiple ICNs. Finally, we present guidelines for choosing the right ICN. |
| DHT Design: A Modular Approach G S Manku and P Ganesan, Submitted to INFOCOM 2004. |
| Analysis of Routing Protocols for Symphony | Stanford Univ, '03 |
| We show that Symphony, a randomized routing topology for distributed hash tables, offers average latency Theta (log n / log log n) when the out-degree of each of n nodes is Theta (log n). The result is surprising because other known results pertaining to related topologies do not suggest this behavior. We also show how Symphony works in a dynamic environment when nodes arrive and depart. We analyze its performance when different nodes have different estimates of n at run-time. |
| Analysis of Routing Protocols for Symphony G S Manku, Submitted SODA 2004. |
| Analysis of Routing Protocols for Chord | Stanford Univ, '03 |
| Consider an undirected graph on 2^b nodes arranged in a circle, with an edge connecting every pair of nodes that are 2^k positions apart for any k >= 0. This graph, often called Chord, is popularly used for routing in peer-to-peer networks. The standard Chord routing protocol is non-optimal as it uses edges in only one direction for routing. We propose new routing protocols that exploit the bidirectionality of edges. Two of our protocols are optimal as they identify the shortest paths between pairs of nodes. Given that the Chord topology is a variant of the hypercube, the shortest paths have a surprising combinatorial structure. |
| Analysis of Routing Protocols for Chord P Ganesan and G S Manku, Submitted SODA 2004. |
| Routing Networks for DHTs | Stanford Univ, '02-'03 |
| Routing topologies for distributed hashing in peer-to-peer networks are classified into two categories: deterministic and randomized. A general technique for constructing deterministic routing topologies is presented. Using this technique, classical parallel interconnection networks can be adapted to handle the dynamic nature of participants in peer-to-peer networks. A unified picture of randomized routing topologies is also presented. Two new protocols are described which improve average latency as a function of out-degree. One of the protocols can be shown to be optimal with high probability. Finally, routing networks for distributed hashing are revisited from a systems perspective and several open design problems are listed. |
| Routing Networks for Distributed Hash Tables G S Manku, Proc. 22nd ACM Symposium on Principles of Distributed Computing, PODC 2003, p. 133-142, June 2003. |
| Symphony | Stanford Univ, '02-'03 |
| Symphony is a protocol for maintaining distributed hash tables in a wide area network. The key idea is to arrange all participants along a ring and equip them with long distance contacts drawn from a family of harmonic distributions. Symphony is inspired by Kleinberg's Small World construction. We extend Kleinberg's theoretical result by showing that with k links per node, greedy routing can achieve an average latency of O((log^2 n) / k) hops. The paper builds upon this basic idea to engineer a practical protocol that is scalable, flexible, stable in the presence of frequent updates and offers small average latency with only a handful of long distance links per node. The cost of updates when hosts join and leave is small. |
| Symphony: Distributed Hashing in a Small World G S Manku, M Bawa and P Raghavan, Proc. 4th USENIX Symposium on Internet Technologies and Systems, USITS 2003, p 127-140, 2003. |
| SETS | Stanford Univ, '01-'03 |
| We present SETS, an architecture for efficient search in peer-to-peer networks, building upon ideas drawn from machine learning and social network theory. The key idea is to arrange participating sites in a topic-segmented overlay topology in which most connections are short-distance, connecting pairs of sites with similar content. Topically focused sets of sites are then joined together into a single network by long-distance links. Queries are matched and routed to only the topically closest regions. We discuss a variety of design issues and tradeoffs that an implementor of SETS would face. We show that SETS is efficient in network traffic and query processing load. |
| SETS: Search Enhanced by Topic Segmentation M Bawa, G S Manku, and P Raghavan, Proc. 26th Intl. ACM SIGIR 2003. |
| Gnutella and Icecast/Shoutcast Crawlers | Gigabeat Inc., Summer '00 |
|
Implemented a robust Gnutella crawler that periodically discovered
its network topology and maintained statistics of participating
hosts. Also implemented Icecast/Shoutcast crawlers to frequently
log the title and artists of songs being broadcasted by various
Icecast/Shoutcast servers. Gigabeat was acquired by Napster in April 2001. |
| Data Stream Management System | Stanford Univ, '01-'03 |
| This paper describes ongoing work developing the Stanford Stream Data Manager (STREAM), a system for executing continuous queries over multiple continuous data streams. The STREAM system supports a declarative query language and it copes with high data rates and query workloads by providing approximate answers when resources are limited. This paper describes specific contributions made so far and enumerates our next steps in developing a general Data Stream Management System. |
| Query Processing, Resource Management and Approximation in a Data Stream Management System R Motwani, J Widom, A Arasu, B Babcock, S Babu, M Datar, G S Manku, C Olston, J Rosenstein and R Varma, Proc. 1st Biennial Conf. On Innovative Data Systems Research, CIDR 2003, p 245-254, Jan 2003. |
| Approximate Frequency Counts | Stanford Univ, '01-'02 |
| Consider a stream of elements. This paper proposes two simple algorithms for identifying all elements whose relative frequency (in the portion of the stream seen so far) exceeds a certain threshold (say, 0.01%). Both algorithms require provably small memory footprints. Although the output is approximate, the error is guaranteed not to exceed a user-specified parameter. The algorithms can easily be deployed for streams of singleton items like those found in IP network monitoring. The latter half of the paper considers streams of variable-sized sets of items, e.g., sequence of market-basket transactions at a retail store. One of the above algorithms is adapted to compute frequent itemsets for such streams in a single pass. The implementation is currently the fastest program for computing frequent itemsets and association rules. |
| Approximate Frequency Counts over Data Streams G S Manku and R Motwani, Proc 28th VLDB, p 346-357, August 2002. |
| Quantiles and Equi-depth Histograms | IBM Almaden, '97-'99 |
|
In the SIGMOD-98 paper, we present new algorithms for computing approximate quantiles of large datasets in a single pass. The approximation guarantees are explicit and apply without regard to the value distribution or the arrival distributions of the dataset. The main memory requirements are smaller than those reported earlier by an order of magnitude. We also discuss methods that couple the approximation algorithms with random sampling to further reduce memory requirements. With sampling, the approximation guarantees are explicit but probabilistic, i.e., they apply with respect to a (user controlled) confidence parameter. We present the algorithms, their theoretical analysis and simulation results. In a followup paper in SIGMOD-99, we address two issues left open in our earlier paper. First, all known and space efficient algorithms for approximate quantile finding require advance knowledge of the length of the input sequence. Many important database applications employing quantiles cannot provide this information. In this paper, we present a novel non-uniform random sampling scheme and an extension of our framework. Together, they form the basis of a new algorithm which computes approximate quantiles without knowing the input sequence length. Second, if the desired quantile is an extreme value (e.g., within the top 1% of the elements), the space requirements of currently known algorithms are overly pessimistic. We provide a simple algorithm which estimates extreme values using less space than required by the earlier more general technique for computing all quantiles. Our principal observation here is that random sampling is quantifiably better when estimating extreme values than is the case with the median. |
| Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets G S Manku, S Rajagopalan and B G Lindsay, Proc. 1999 ACM SIGMOD, Vol 28, No 2, p 251-62, June 1999. Approximate Medians and other Quantiles in One Pass and with Limited Memory G S Manku, S Rajagopalan and B G Lindsay, Proc. 1998 ACM SIGMOD, Vol 27, No 2, p 426-35, June 1998. |
| Symmetries in Model Checking | UC Berkeley, '96-'97 |
| We present a fully automatic framework for identifying symmetries in structural descriptions of digital circuits and CTL* formulas and using them in a model checker. The set of sub-formulas of a formula is partitioned into equivalence classes so that truth values for only one sub-formula in any class need be evaluated for model checking. Structural symmetries in net-list descriptions of digital circuits and CTL* formulas are formally defined and their relationship with Kripke structures is described. A technique for automatic identification of structural symmetries is described that requires computation of the automorphism group of a suitable directed labeled graph. A novel fast algorithm for this problem is presented. Finally, experimental results are reported for BLIF-MV net-lists derived from Verilog. |
| Structural Symmetry and Model Checking G S Manku, R Hojati and R K Brayton, Proc. 10th Intl Conf on Computer-Aided Verification, CAV 98, Vancouver, Canada, LCNS 1427, p 159-171, July 1998. (Source code for VIS symmetry module). |
| Self-Similarity in File Systems | UC Berkeley, '95-'97 |
| We demonstrate that high-level file system events exhibit self-similar behaviour, but only for short-term time scales of under a day. We do so through the analysis of four sets of traces that span time scales of milliseconds through months, and that differ in the trace collection method, the filesystems being traced, and the chronological times of the tracing. Two sets of detailed, short-term file system trace data are analyzed; both are shown to have self-similar like behaviour, with consistent Hurst parameters (a measure of self-similarity) for all file system traffic as well as individual classes of file system events. Long-term file system trace data is then analyzed, and we discover that the traces' high variability and self-similar behaviour does not persist across time scales of days, weeks, and months. Using the short-term trace data, we show that sources of file system traffic exhibit ON/OFF source behaviour, which is characterized by highly variably lengthed bursts of activity, followed by similarly variably lengthed periods of inactivity. This ON/OFF behaviour is used to motivate a simple technique for synthesizing a stream of events that exhibit the same self-similar short-term behaviour as was observed in the file-system traces. |
| Self-Similarity in File-System Traffic S D Gribble, G S Manku, D Roselli, E A Brewer, T J Gibson and E L Miller, Proc. ACM SIGMETRICS '98/PERFORMANCE '98, Madison, Wisconsin, p 141-150, June 24-26, 1998 |
| Circuit Partioning | Intel Corp., Summer '96 |
| Yet to write. |
| Data Prefetching Hardware | UC Berkeley, '96-'97 |
| The dramatic increase in the processor-memory gap in recent years has led to the development of techniques like data prefetching that hide the latency of cache misses. Two such hardware techniques are the stream buffer and the stride predictor. These two have dissimilar architectures, are effective for different kinds of memory access patterns and require different amounts of extra memory bandwidth. We compare the performance of these two techniques and propose a scheme that unifies them. Simulation studies on six benchmark programs confirms that the combined scheme is more effective in reducing the average memory access time (AMAT) than either of the two individually. |
| A New Voting Based Hardware Data Prefetch Scheme G S Manku, M R Prasad and D A Patterson, Proc. Fourth Intl. Conf. on High Performance Computing, HiPC 97, Bangalore, India, p 100-105, December 18-21, 1997. |
| Object Tracking | IIT Delhi, '95-'96 |
| A new object tracking algorithm based on affine structure has been developed and it is shown that the performance is better than that of a Kalman filter based correlation tracker. The algorithm is fast, reliable, viewpoint invariant, and insensitiver to occlusion and/or individual corner disappearance or reappearance. Detailed experimental analysis on a long real image sequence is also presented. |
| Object Tracking using Affine Structure for Point Correspondences G S Manku, P Jain, A Aggarwal, L Kumar and S Banerjee, Proc. IEEE Conf. for Computer Vision and Pattern Recognition, CVPR 97, Puerto Rico, p704-9, June 17-19, 1997. |
| Theory | IIT Delhi, '94-'95 |
| A linear time algorithm for the Bottleneck Biconnected Spanning Subgraph problem is presented. This improves the hitherto best-known solution, which has a running time of O(m + n log n), where m and n are the number of edges and vertices of the graph. Linear time is acheived by first mapping the problem onto a special kind of graphs (that we call B_Graphs), which are shown to have nice structural properties. Then, a binary search on the weights of edges is done. The main idea is to use the properties of the B_Graph to shrink it by removing redundant edges and vertices in each iteration, thereby reducing the size of the graph by at least a factor of two. |
| A Linear Time Algorithm for the Bottleneck Biconnected Spanning Subgraph Problem G S Manku, Information Processing Letters, Vol 59, Number 1, 8 July 1996, p 1-7. |
| Circuit Partitioning | IIT Delhi, '94-'95 |
| A low-cost hybrid simulator for VLSI circuits has been under development at IIT Delhi. The simulator uses a Reconfigurable System (RS) consisting of a limited number of FPGAs for hardware emulation and blends the ideas of hardware emulation with conventional software simulation. A crucial preparatory step is to partition a given circuit into as few parts as possible. The parts are then downloaded onto the RS one by one and emulated in stand alone mode or in conjunction with software simulator. The hybrid simulation environment poses some unique requirements on the partitioner. This paper presents an efficient partitioning algorithm for this purpose. A study of performance of the algorithm on 32 benchmark circuits for various I/O and size constraints of FPGAs has been carried out and good results have been obtained. |
| Circuit Partitioning with Partial Order for Mixed Simulation Emulation Environment G S Manku, A Kumar and S Kumar, Proc. Sixth Intl. Conf. on Rapid System Prototyping, RSP '95, Chapel Hill, North Carolina, USA, p201-7, 7-9 June, 1995. |