Rahul Garg 0001

EDBT 2026 Demo / reviewers in the wild / expert

dblp:55/1248 · DBLP profile ↗

← Back

26ranked-venue papers

12as first author

0since 2021 · last 2019

0000-0003-0244-0037ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Systems, architecture and hardware · 14 · 6 first-authorTheory of computation · 5 · 3 first-authorArtificial intelligence and machine learning · 4 · 2 first-authorGraphics, computer vision, multimedia, augmented reality and games · 3Computer networks · 2 · 2 first-authorApplied, interdisciplinary, general and emerging computing · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science 4 papers		Algorithmic game theory and mechanism design · 58% Mathematical optimization · 26% Information theory · 16%
Computer architecture, parallel and distributed computing, and storage systems 4 papers		High-performance computing · 62% Distributed systems · 17% Interconnection networks and networks-on-chip · 10%
Computer graphics and multimedia 1 paper		Image and video processing · 100%
Computer networks 1 paper		Network optimization and economics · 91% Internet architecture and protocols · 9%

Topics — the 27 heaviest of 29, each with the papers that count most for it

Topic	Weight	Papers	Last	Evidence papers
Algorithmic game theory and mechanism design market equilibrium	0.3	2	2016	A Simple and Efficient Algorithm for Computing Market Equilibria · ACM Trans. Algorithms 2016 Auction algorithms for market equilibrium · STOC 2004
Mathematical optimization › continuous optimization convex optimization	0.2	1	2016	A Simple and Efficient Algorithm for Computing Market Equilibria · ACM Trans. Algorithms 2016
Algorithmic game theory and mechanism design › market equilibrium exchange economy	0.2	1	2016	A Simple and Efficient Algorithm for Computing Market Equilibria · ACM Trans. Algorithms 2016
Distributed systems distributed algorithms	0.1	1	2010	Efficient Algorithms for Global Snapshots in Large Distributed Systems · IEEE Trans. Parallel Distributed Syst. 2010
Information theory › signal processing › compressed sensing restricted isometry property	0.1	1	2009	Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property · ICML 2009
Information theory › signal processing › compressed sensing sparse recovery	0.1	1	2009	Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property · ICML 2009
Image and video processing texture analysis	0.1	1	2007	Locally Invariant Fractal Features for Statistical Texture Classification · ICCV 2007
Image and video processing › texture analysis texture classification	0.1	1	2007	Locally Invariant Fractal Features for Statistical Texture Classification · ICCV 2007
High-performance computing finite element method	0.1	1	2006	Gordon Bell finalists I - Large scale drop impact analysis of mobile phone using ADVC on Blue Gene/L · SC 2006
Interconnection networks and networks-on-chip network bandwidth	0.1	1	2006	MPI and communication - Software routing and aggregation of messages to optimize the performance of HPCC randomaccess benchmark · SC 2006
High-performance computing performance optimization	0.1	1	2006	MPI and communication - Software routing and aggregation of messages to optimize the performance of HPCC randomaccess benchmark · SC 2006
High-performance computing performance optimization at scale	0.1	1	2006	Gordon Bell finalists I - Large scale drop impact analysis of mobile phone using ADVC on Blue Gene/L · SC 2006
High-performance computing scientific computing systems	0.1	1	2006	Gordon Bell finalists I - Large scale drop impact analysis of mobile phone using ADVC on Blue Gene/L · SC 2006
High-performance computing structural analysis	0.1	1	2006	Gordon Bell finalists I - Large scale drop impact analysis of mobile phone using ADVC on Blue Gene/L · SC 2006
Mathematical optimization auction algorithm	0.0	1	2004	Auction algorithms for market equilibrium · STOC 2004
Algorithmic game theory and mechanism design › market equilibrium market clearing	0.0	1	2004	Auction algorithms for market equilibrium · STOC 2004
Algorithmic game theory and mechanism design coalitional game	0.0	1	2003	Coalitional games on graphs: core structure, substitutes and frugality · EC 2003
Algorithmic game theory and mechanism design › cooperative game theory › solution concepts core	0.0	1	2003	Coalitional games on graphs: core structure, substitutes and frugality · EC 2003
High-performance computing › supercomputing bluegene/l	0.0	1	2002	An overview of the BlueGene/L Supercomputer · SC 2002
High-performance computing supercomputing	0.0	1	2002	An overview of the BlueGene/L Supercomputer · SC 2002
Integrated circuit design system-on-chip	0.0	1	2002	An overview of the BlueGene/L Supercomputer · SC 2002
Parallel and multicore computing MPI	0.0	1	2010	Efficient Algorithms for Global Snapshots in Large Distributed Systems · IEEE Trans. Parallel Distributed Syst. 2010
Network optimization and economics admission control	0.0	1	2000	Fair Bandwidth Sharing Among Virtual Networks: A Capacity Resizing Approach · INFOCOM 2000
Network optimization and economics › resource allocation › bandwidth allocation fair bandwidth allocation	0.0	1	2000	Fair Bandwidth Sharing Among Virtual Networks: A Capacity Resizing Approach · INFOCOM 2000
Network optimization and economics resource allocation	0.0	1	2000	Fair Bandwidth Sharing Among Virtual Networks: A Capacity Resizing Approach · INFOCOM 2000
Image and video processing › image statistics statistical image modeling	0.0	1	2007	Locally Invariant Fractal Features for Statistical Texture Classification · ICCV 2007
Internet architecture and protocols › virtual network virtual private network	0.0	1	2000	Fair Bandwidth Sharing Among Virtual Networks: A Capacity Resizing Approach · INFOCOM 2000

Methods — techniques the papers use, named apart from their topics

weak gross substitutes · 0.2tâtonnement price adjustment · 0.2tree-based algorithm · 0.1grid-based algorithm · 0.1centralized algorithm · 0.1sparsification · 0.1restricted isometry property · 0.1gradient descent · 0.1joint PDF modeling · 0.1fractal dimension · 0.1bi-lipschitz invariance · 0.1software routing · 0.1parallel structural analysis · 0.1message aggregation · 0.1linear programming · 0.0complementary slackness · 0.0auction mechanism · 0.0system architecture design · 0.0

Year	Publication	Venue	Position
2019	Acceleration of Sparse Vector Autoregressive Modeling Using GPUs abstract Autoregressive modeling is a standard approach to mathematically describe the behavior of a time series. The vector autoregressive model (VAR) describes the behavior of multiple time series. The VAR modeling is a fundamental approach which has applications in multiple domains such as time series forecasting, Granger causality, system identification and stochastic control. Solving high dimensional VAR model requires the use of sparse regression techniques from machine learning. Efficient algorithms to solve the sparse regression problems are too slow to be useful in solving large high dimensional sparse VAR modeling problems. Earlier application of sparse VAR modeling in the neuroimaging domain required the use of the IBMs Blue Gene supercomputers. In this paper we describe an approach to accelerate large scale sparse VAR problems when solved using the lasso regression algorithm on state-of-the-art GPUs. Our accelerated implementation on NVIDIA GTX 1080 GPU takes a few seconds to solve the problem, reaching up to 4 TFLOPs of single-precision performance which is close to 55% of its peak matrix-multiply (GEMM) performance. Shreenivas Bharadwaj Venkataramanan, Rahul Garg 0001, Yogish Sabharwal	HiPC	2
2018	SandhiKosh: A Benchmark Corpus for Evaluating Sanskrit Sandhi Tools Shubham Bhardwaj, Neelamadhav Gantayat, Nikhil Chaturvedi, Rahul Garg 0001, Sumeet Agarwal	LREC	4
2016	A Simple and Efficient Algorithm for Computing Market Equilibria abstract We give a new mathematical formulation of market equilibria in exchange economies using an indirect utility function : the function of prices and income that gives the maximum utility achievable. The formulation is a convex program and can be solved when the indirect utility function is convex in prices. We illustrate that many economies, including: —Homogeneous utilities of degree α ∈ [0, 1] in Fisher economies—this includes Linear, Leontief, Cobb-Douglas — Resource allocation utilities like multi-commodity flows satisfy this condition and can be efficiently solved. Further, we give a natural tâtonnement type price-adjusting algorithm in these economies. Our algorithm, which is applicable to a larger class of utility functions than previously known weak gross substitutes , mimics the natural dynamics for the markets as suggested by Walras: it iteratively adjusts a good’s price upward when the demand for that good under current prices exceeds its supply; and downward when its supply exceeds its demand. The algorithm computes an approximate equilibrium in a number of iterations that is independent of the number of traders and is almost linear in the number of goods. Lisa Fleischer, Rahul Garg 0001, Sanjiv Kapoor, Rohit Khandekar, Amin Saberi	ACM Trans. Algorithms	2
2010	Balanced stream assignment for service facility abstract Shared data centers and clouds are gaining popularity because of their ability to reduce costs by increasing the utilization of server farms. In a shared server environment, a careful assignment of workload streams (all work-requests from a customer may constitute a stream) to servers is necessary to ensure good “end user” performance. In this work, we investigate the assignment of streams to servers in order to minimize an objective function, while ensuring that load is balanced across all the servers. The objective functions we optimize in this work include the overall expected waiting-time, overall probability of the wait exceeding a given value, and weighted versions of these measures. We obtain the optimal algorithm for a farm with 2 servers, if sharing of streams among servers is allowed. Based on the insights obtained, we design an efficient algorithm for the multiserver case. By rounding off this solution, we obtain a solution to the case where sharing of streams is not allowed. Our trace-driven evaluation study shows that our algorithms significantly outperform baseline methods. Our work enables high performance for web hosting services as well as emerging Application as a Service (AaaS) clouds. We also show that solutions in areas such as task-level scheduling and file assignment fall within our framework. Rahul Garg 0001, Perwez Shahabuddin, Akshat Verma	HiPC	1
2010	Efficient Algorithms for Global Snapshots in Large Distributed Systems abstract Existing algorithms for global snapshots in distributed systems are not scalable when the underlying topology is complete. There are primarily two classes of existing algorithms for computing a global snapshot. Algorithms in the first class use control messages of size 0(1) but require O(N) space and O(N) messages per processor in a network with JV processors. Algorithms in the second class use control messages (such as rotating tokens with vector counter method) of size O(N), use multiple control messages per channel, or require recording of message history. As a result, algorithms in both of these classes are not efficient in large systems when the logical topology of the communication layer such as MPI is complete. In this paper, we propose three scalable algorithms for global snapshots: a grid-based, a tree-based, and a centralized algorithm. The grid-based algorithm uses O(N) space but only O(¿(N)) messages per processor each of size O(¿(N)). The tree-based and centralized algorithms use only O(1) size messages. The tree-based algorithm requires O(1) space and O(log N log(W/N)) messages per processor where W is the total number of messages in transit. The centralized algorithm requires O(1) space and O(log(W/N)) messages per processor. We also have a matching lower bound for this problem. We also present hybrid of centralized and tree-based algorithms that allow trade-off between the decentralization and the message complexity. Our algorithms have applications in checkpointing, detecting stable predicates, and implementing synchronizers. Rahul Garg 0001, Vijay K. Garg, Yogish Sabharwal	IEEE Trans. Parallel Distributed Syst.	1
2009	Gradient descent with sparsification: an iterative algorithm for sparse recovery with restricted isometry property abstract We present an algorithm for finding an s-sparse vector x that minimizes the square-error ∥y -- Φx∥2 where Φ satisfies the restricted isometry property (RIP), with isometric constant δ2s < 1/3. Our algorithm, called GraDeS (Gradient Descent with Sparsification) iteratively updates x as: [EQUATION] Rahul Garg 0001, Rohit Khandekar	ICML	1
2009	HPCC Random Access benchmark for next generation supercomputers abstract In this paper we examine the key elements determining the performance of the HPC Challenge RandomAccess benchmark on next generation supercomputers. We find that the performance of this benchmark is closely related to the bisection bandwidth of the underlying communication network, performance of integer divide operation and details of benchmark specifications such as error tolerance and permissible multi-core mapping strategies. We demonstrate that seemingly small and innocuous changes in the benchmark can lead to significantly different system performance. We also present an algorithm to optimize RandomAccess benchmark for multi-core systems. Our algorithm uses aggregation and software routing and balances the load on the cores by specializing each of the cores for one specific routing or update function. This algorithm gives approximately a factor of 3 speedup on the Blue Gene/P system which is based on quad-core nodes. Vikas Aggarwal, Yogish Sabharwal, Rahul Garg 0001, Philip Heidelberger	IPDPS	3
2009	A Cluster Overlap Measure for Comparison of Activations in fMRI Studies Guillermo A. Cecchi, Rahul Garg 0001, A. Ravishankar Rao	MICCAI (1)	2
2008	Optimization of Fast Fourier Transforms on the Blue Gene/L Supercomputer Yogish Sabharwal, Saurabh Kumar Garg 0001, Rahul Garg 0001, John A. Gunnels, Ramendra K. Sahoo	HiPC	3
2008	Optimization of All-to-All Communication on the Blue Gene/L Supercomputer abstract All-to-all communication is a well known performance bottleneck for many applications, such as the ones that use the Fast-Fourier-transform (FFT) algorithm. We analyze the performance of all-to-all communication on the BlueGene/L torus interconnect that has link contention even for all-to-all operations with short messages. We observed that the performance of all-to-all depends on the shape of the processor partition. We present a performance analysis of all-to-all on partitions of various shapes. We then present optimization schemes that substantially improve the performance of all-to-all with short and large messages.In particular, throughput improved from 64% to over 99% of peak on the 65,536 (64 times 32 times 32) node Blue Gene/L machine at the Lawrence Livermore National Lab. We show the impact of the all-to-all performance optimizations in 1-D and 3-D FFT benchmarks. We achieved a performance of over 2.8 TF for the HPC Challenge 1D FFT benchmark with our optimized all-to-all. Sameer Kumar 0001, Yogish Sabharwal, Rahul Garg 0001, Philip Heidelberger	ICPP	3
2007	Locally Invariant Fractal Features for Statistical Texture Classification abstract We address the problem of developing discriminative, yet invariant, features for texture classification. Texture variations due to changes in scale are amongst the hardest to handle. One of the most successful methods of dealing with such variations is based on choosing interest points and selecting their characteristic scales [Lazebnik et al. PAMI 2005]. However, selecting a characteristic scale can be unstable for many textures. Furthermore, the reliance on an interest point detector and the inability to evaluate features densely can be serious limitations. Fractals present a mathematically well founded alternative to dealing with the problem of scale. However, they have not become popular as texture features due to their lack of discriminative power. This is primarily because: (a) fractal based classification methods have avoided statistical characterisations of textures (which is essential for accurate analysis) by using global features; and (b) fractal dimension features are unable to distinguish between key texture primitives such as edges, corners and uniform regions. In this paper, we overcome these drawbacks and develop local fractal features that are evaluated densely. The features are robust as they do not depend on choosing interest points or characteristic scales. Furthermore, it is shown that the local fractal dimension is invariant to local bi-Lipschitz transformations whereas its extension is able to correctly distinguish between fundamental texture primitives. Textures are characterised statistically by modelling the full joint PDF of these features. This allows us to develop a texture classification framework which is discriminative, robust and achieves state-of-the-art performance as compared to affine invariant and fractal based methods. Manik Varma, Rahul Garg 0001	ICCV	2
2006	Impact of Noise on Scaling of Collectives: An Empirical Evaluation Rahul Garg 0001, Pradipta De	HiPC	1
2006	Scalable algorithms for global snapshots in distributed systems abstract Existing algorithms for global snapshots in distributed systems are not scalable when the underlying topology is complete. In a network with N processors, these algorithms require O(N) space and O(N) messages per processor. As a result, these algorithms are not efficient in large systems when the logical topology of the communication layer such as MPI is complete. In this paper, we propose three algorithms for global snapshot: a grid-based, a tree-based and a centralized algorithm. The grid-based algorithm uses O(N) space but only O(√N) messages per processor. The tree-based algorithm requires only O(1) space and O(logNlog w) messages per processor where w is the average number of messages in transit per processor. The centralized algorithm requires only O(1) space and O(log w) messages per processor. We also have a matching lower bound for this problem. Our algorithms have applications in checkpointing, detecting stable predicates and implementing synchronizers. We have implemented our algorithms on top of the MPI library on the Blue Gene/L supercomputer. Our experiments confirm that the proposed algorithms significantly reduce the message and space complexity of a global snapshot. Rahul Garg 0001, Vijay K. Garg, Yogish Sabharwal	ICS	1
2006	Gordon Bell finalists I - Large scale drop impact analysis of mobile phone using ADVC on Blue Gene/L abstract Existing commercial finite element analysis (FEA) codes do not exhibit the performance necessary for large scale analysis on parallel computer systems. In this paper, we demonstrate the performance characteristics of a commercial parallel structural analysis code, ADVC, on Blue Gene/L (BG/L). The numerical algorithm of ADVC is described, tuned, and optimized on BG/L, and then a large scale drop impact analysis of a mobile phone is performed. The model of the mobile phone is a nearly-full assembly that includes inner structures. The size of the model we have analyzed has 47 million nodal points and 142 million DOFs. This does not seem exceptionally large, but the dynamic impact analysis of a product model, with the contact condition on the entire surface of the outer case under this size, cannot be handled by other CAE systems. Our analysis is an unprecedented attempt in the electronics industry. It took only half a day, 12.1 hours, for the analysis of about 2.4 milliseconds. The floating point operation performance obtained has been 538 GFLOPS on 4096 node of BG/L. Hiroshi Akiba, Tomonobu Ohyama, Yoshinoir Shibata, Kiyoshi Yuyama, Yoshikazu Katai, Ryuichi Takeuchi, Takeshi Hoshino, Shinobu Yoshimura, Hirohisa Noguchi, Manish Gupta 0002, John A. Gunnels, Vernon Austel, Yogish Sabharwal, Rahul Garg 0001, Shoji Kato, Takashi Kawakami, Satoru Todokoro, Junko Ikeda	SC	14
2006	MPI and communication - Software routing and aggregation of messages to optimize the performance of HPCC randomaccess benchmark abstract The HPC Challenge(HPCC) benchmark suite is increasingly being used to evaluate the performance of supercomputers. It augments the traditional LINPACK benchmark by adding six more benchmarks, each designed to measure a specific aspect of the system performance.In this paper, we analyze the HPCC Randomaccess benchmark which is designed to measure the performance of random memory updates. We show that, on many systems, the bisection bandwidth of the network may be the performance bottleneck of this benchmark. We suggest an aggregation and software routing based technique that may be used to optimize this benchmark. We report the performance results obtained using this technique on the Blue Gene/L supercomputer. Rahul Garg 0001, Yogish Sabharwal	SC	1
2005	The Impact of Noise on the Scaling of Collectives: A Theoretical Approach Rahul Garg 0001, Nisheeth K. Vishnoi	HiPC	2
2004	An Auction-Based Market Equilibrium Algorithm for the Separable Gross Substitutability Case Rahul Garg 0001, Sanjiv Kapoor, Vijay V. Vazirani	APPROX-RANDOM	1
2004	Adaptive incremental checkpointing for massively parallel systems abstract Given the scale of massively parallel systems, occurrence of faults is no longer an exception but a regular event. Periodic checkpointing is becoming increasingly important in these systems. However, huge memory footprints of parallel applications place severe limitations on scalability of normal checkpointing techniques. Incremental checkpointing is a well researched technique that addresses scalability concerns, but most of the implementations require paging support from hardware and the underlying operating system, which may not be always available. In this paper, we propose a software based adaptive incremental checkpoint technique which uses a secure hash function to uniquely identify changed blocks in memory. Our algorithm is the first self-optimizing algorithm that dynamically computes the optimal block boundaries, based on the history of changed blocks. This provides better opportunities for minimizing checkpoint file size. Since the hash is computed in software, we do not need any system support for this. We have implemented and tested this mechanism on the BlueGene/L system. Our results on several well-known benchmarks are encouraging, both in terms of reduction in average checkpoint file size and adaptivity towards application’s memory access patterns. Rahul Garg 0001, Meeta Sharma Gupta, José E. Moreira	ICS	2
2004	Auction algorithms for market equilibrium abstract In this paper we study algorithms for computing market equilibrium in markets with linear utility functions. The buyers in the market have an initial endowment given by a portfolio of items. The market equilibrium problem is to compute a price vector which ensures market clearing, i. e. the demand of a good equals its supply, and given the prices, each buyer maximizes its utility. The problem is of considerable interest in Economics. This paper presents a formulation of the market equilibrium problem as a parameterized linear program. We construct the dual of these parametrized linear programs. We show that finding the market equilibrium is the same as finding a linear-program from the family of programs where the optimal dual solution satisfies certain properties. The market clearing conditions arise naturally from complementary slackness conditions.We then define an auction mechanism which computes prices such that approximate market clearing is achieved. The algorithm we obtain outperforms previously known methods. Rahul Garg 0001, Sanjiv Kapoor	STOC	1
2003	Coalitional games on graphs: core structure, substitutes and frugality abstract No abstract available. Rahul Garg 0001, Atri Rudra, Akshat Verma	EC	1
2002	An overview of the BlueGene/L Supercomputer abstract This paper gives an overview of the BlueGene/L Supercomputer. This is a jointly funded research partnership between IBM and the Lawrence Livermore National Laboratory as part of the United States Department of Energy ASCI Advanced Architecture Research Program. Application performance and scaling studies have recently been initiated with partners at a number of academic and government institutions,including the San Diego Supercomputer Center and the California Institute of Technology. This massively parallel system of 65,536 nodes is based on a new architecture that exploits system-on-a-chip technology to deliver target peak processing power of 360 teraFLOPS (trillion floating-point operations per second). The machine is scheduled to be operational in the 2004-2005 time frame, at price/performance and power consumption/performance targets unobtainable with conventional architectures. Narasimha R. Adiga, Gheorghe Almási 0001, George S. Almási, Yariv Aridor, Rajkishore Barik, Daniel K. Beece, Ralph Bellofatto, Gyan Bhanot, Randy Bickford, Matthias A. Blumrich, Arthur A. Bright, José R. Brunheroto, Calin Cascaval, José G. Castaños, Waiman Chan, Luis Ceze, Paul Coteus, Siddhartha Chatterjee, Dong Chen 0005, George L.-T. Chiu, Thomas M. Cipolla, Paul Crumley, K. M. Desai, Alina Deutsch, Tamar Domany, Marc Boris Dombrowa, Wilm E. Donath, Maria Eleftheriou, C. Christopher Erway, J. Esch, Blake G. Fitch, Joseph Gagliano, Alan Gara, Rahul Garg 0001, Robert S. Germain, Mark Giampapa, Balaji Gopalsamy, John A. Gunnels, Manish Gupta 0002, Fred G. Gustavson, Shawn Hall, Ruud A. Haring, David F. Heidel, Philip Heidelberger, Lorraine M. Herger, Dirk Hoenicke, R. D. Jackson, T. Jamal-Eddine, Gerard V. Kopcsay, Elie Krevat, Manish P. Kurhekar, Alphonso P. Lanzetta, Derek Lieber, L. K. Liu, M. Lu, Mark P. Mendell, A. Misra, Yosef Moatti, Lawrence S. Mok, José E. Moreira, Ben J. Nathanson, Matthew Newton, Martin Ohmacht, Adam J. Oliner, Vinayaka Pandit, R. B. Pudota, Rick A. Rand, Richard D. Regan, Bradley Rubin, Albert E. Ruehli, Silvius Vasile Rus, Ramendra K. Sahoo, Alda Sanomiya, Eugen Schenfeld, M. Sharma, Edi Shmueli, Sarabjeet Singh, Peilin Song, Vijay Srinivasan, Burkhard D. Steinmacher-Burow, Karin Strauss, Christopher W. Surovic, Richard A. Swetz, Todd Takken, R. Brett Tremaine, Mickey Tsao, Arun R. Umamaheshwaran, P. Verma, Pavlos Vranas, T. J. Christopher Ward, Michael E. Wazlowski, W. Barrett, C. Engel, B. Drehmel, B. Hilgart, D. Hill, F. Kasemkhani, David J. Krolak, Chun-Tao Li 0001, Thomas A. Liebsch, James A. Marcella, A. Muff, A. Okomo, M. Rouse, A. Schram, M. Tubbs, G. Ulsh, Charles D. Wait, J. Wittrup, Myung Bae, Kenneth A. Dockser, Lynn Kissel, Mark K. Seager, Jeffrey S. Vetter, K. Yates	SC	34
2001	An Architecture for Secure Generation and Verification of Electronic Coupons Rahul Garg 0001, Parul A. Mittal, Vikas Agarwal, Natwar Modani	USENIX ATC, General Track	1
2001	Seller-Focused Algorithms for Online Auctioning Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg 0001, Michael T. Goodrich	WADS	3
2000	Fair Bandwidth Sharing Among Virtual Networks: A Capacity Resizing Approach abstract Virtual private networks (VPN) and link sharing are cost-effective ways of realizing corporate intranets. Corporate intranets will increasingly have to provide integrated services for voice and multimedia traffic. Although packet scheduling algorithms can be used to implement integrated services in link sharing and virtual private networks, their statistical multiplexing gains are limited. We propose a new scheme called stochastic fair sharing (SFS) to carry out fair link sharing and fair sharing among virtual leased links (VLL). In the link sharing environment, capacities allocated to different classes are adjusted dynamically as sessions arrive (or depart). The SFS admission control algorithm decides which sessions to accept and which to reject depending upon the current utilizations and provisioned capacities of the classes. SFS gives protection to classes with low session arrival rate against classes with high session arrival rates by ensuring them a low blocking probability. In the case of multi-hop VLL, capacity resizing requests are sent in the service providers's network which are admission-controlled using SFS. Our simulations indicate that using SFS, the equivalent capacity of virtual links converge to their max-min fair capacity, with a fairness index of 0.97 in extreme situations. The average signaling load of the protocol was found to be reasonable. The scheme is simple to implement, efficient, and robust. The potential applications of SFS are fair and efficient resource sharing in telecommunication networks, ATM networks, virtual private networks (VPN) and integrated services or differentiated services-based IP networks. Rahul Garg 0001, Huzur Saran	INFOCOM	1
1999	RRR: recursive round robin scheduler Rahul Garg 0001	Comput. Networks	1
1995	Methods for matching compressed video to ATM networks abstract Over the last few years three technologies have reached the stage of maturation where then can become synergistic. These are wideband, high speed networking, high quality video compression (MPEG-I and II), and high capacity affordable digital storage media. This paper addresses the interaction of these three technologies. In particular, it examines the problem of taking a compressed video data stream that is stored on a server, and transmitting it over an ATM channel which has a capacity smaller than that required by the data stream. The conventional approach to this problem would be to transcode by decoding the video data, and then re-encoding so as to meet the channel constraints. Currently this is not a cost effective solution since, while MPEG decoders are relatively inexpensive, encoders are not. Our approach to this problem is to partially decompress the video bitstream. Then, perform the transcoding in the quantized data domain. Finally, a valid bitstream is reassembled and transmitted. This approach has the advantage of providing nearly identical quality as the traditional transcoding approach, at a fraction of the hardware cost. Robert J. Safranek, Charles R. Kalmanek Jr., Rahul Garg 0001	ICIP	3