Constructing the Upper Envelope of Line Segments in Parallel
Mentors: Dr. Neelima Gupta and Prof. Sandeep SenOptimal Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel
Proceedings of Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore India, December 2001.Output-Sensitive Algorithms for Optimally Constructing Upper Envelope of Straight Line Segments in Parallel
Journal of Parallel and Distributed Computing (2007)Upper envelope of a set of n line segments in a plane is an important concept in the problems involving visibility and motion planning. The line segments are regarded as opaque obstacles, and their upper envelope consists of the portion of the segments visible from the point infinity. The complexity of upper envelope is the number of distinct pieces of segments that appear on it. In the general case of intersecting segments the worst case complexity of their upper envelope is O(n \alpha(n)), where \alpha(n) is the inverse of Akermann's function. However the complexity could be as small as a constant - when for example a single line segment covers all the rest which lie below it. Thus one can hope to obtain a very fast algorithm in terms of output size.
During this project we proposed
two randomized and one deterministic parallel algorithms
for the problem, which were output size sensitive. Our
algorithms are superior in the sense that they speed-up
optimally (i.e., the processor time product matches the
lower bound) with the output size in the sub logarithmic
time domain. Our randomized results hold with high
probability.
K-Splittable Traffic Assignment on Identical Servers
Mentors: Prof. Berthold Voking and Piotr KrystaCollaborators: Tarun Agarwal, Amit Agarwal
An Experimental Study of Different Strategies for DNS-Based Load Balancing
Proceedings of Euro-Par, Klagenfurt Austria, August 2003.The Internet domain name system uses rotation of address lists to perform load distribution among replicated servers. We model this kind of load balancing mechanism in form of a set of request streams with different rates that should be mapped to a set of servers. Rotating a list of length k corresponds to breaking streams into k equally sized pieces. We compare this and other strategies of how to break the streams into a bounded number of pieces and how to map these pieces to the server.
One of the strategies that we study computes an optimal k-splittable allocation using a scheduling algorithm that breaks streams into at most k >= 2 pieces of possibly different size and maps these pieces to the servers in such a way that the maximum load over all servers is minimized. Our experimental study was done using the network simulator SSFNet. We study the average and maximum delay experienced by HTTP requests for various traffic allocation policies and traffic patterns. Our simulations show that splitting data streams can reduce the maximum as well as the average latency of HTTP requests significantly. This improvement can be observed even if the streams are simply broken into k equally sized pieces that are mapped randomly to the servers. Using allocations computed by machine scheduling algorithms, we observe further significant improvements.
Channel Assignment in Optical Networks Supporting DWDM
Mentors: Dr. Neelima Gupta and Prof. S. N. Maheshwari3/2 Approximation Algorithm for Channel Assignment Problem in All Optical Networks Supporting DWDM
Optical fiber is rapidly becoming the standard transmission medium for backbone networks, since it can provide the required data rate, error rate and delay performance for the high speed networks of next generation. Networks using optical transmission and maintaining optical data paths through the nodes are called "all-optical networks". In an "all-optical network", once the data stream has has been transmitted in the form of light it continues without conversion to electronic form until it reaches its destination. Optical bandwidth is defined as the number of available wavelengths for transmit such a signal. An important engineering problem is to establish communication between pairs of nodes so that the data stream travels on the same wavelength on all the links and the total number of wavelengths used is minimized; this is known as the wavelength routing problem.
In this work we model the
underlying fiber network as a directed graph, where the
vertices are the nodes of the network and the links are the
optical fibers connecting the nodes. Communication requests
are ordered pairs of nodes, which are thought of as
transmitter receiver pairs. We study the bidirected binary
tree topology for the network. We assume that the pattern
of communication requests is such that all the requests are
from leaf-to-leaf and each directed edge of the tree is
fully loaded. For this specific instance of requests, we
give a deterministic greedy algorithm that guarantees a 3/2
approximation and improves upon the previously known bound
of 5/3 on the approximation factor.