Type of Document	Dissertation
Author	Srinivasagopalan, Srivathsan
URN	etd-04202011-092524
Title	Oblivious Buy-at-Bulk Network Design Algorithms
Degree	Doctor of Philosophy (Ph.D.)
Department	Computer Science
Advisory Committee	Advisor Name Title Busch, Konstantin (Costas) Committee Co-Chair Iyengar, S.S. Committee Co-Chair Mukhopadhyay, Supratik Committee Member Park, Seung-Jong Committee Member Sarker, Bhaba Dean's Representative
Keywords	Spanning Tree Network Design Doubling-Dimension Sparse Covers Algorithms Approximation Graph Theory Buy-at-Bulk
Date of Defense	2011-04-13
Availability	unrestricted
Abstract Large-scale networks such as the Internet has emerged as arguably the most complex distributed communication network system. The mere size of such networks and all the various applications that run on it brings a large variety of challenging problems. Similar problems lie in any network - transportation, logistics, oil/gas pipeline etc where efficient paths are needed to route the flow of demands. This dissertation studies the computation of efficient paths from the demand sources to their respective destination(s). We consider the buy-at-bulk network design problem in which we wish to compute efficient paths for carrying demands from a set of source nodes to a set of destination nodes. In designing networks, it is important to realize economies of scale. This is can be achieved by aggregating the flow of demands. We want the routing to be oblivious: no matter how many source nodes are there and no matter where they are in the network, the demands from the sources has to be routed in a near-optimal fashion. Moreover, we want the aggregation function f to be unknown, assuming that it is a concave function of the total flow on the edge. The total cost of a solution is determined by the amount of demand routed through each edge. We address questions such as how we can (obliviously) route flows and get competitive algorithms for this problem. We study the approximability of the resulting buy-at-bulk network design problem. Our aim is to find minimum-cost paths for all the demands to the sink(s) under two assumptions: (1) The demand set is unknown, that is, the number of source nodes that has demand to send is unknown. (2) The aggregation cost function at intermediate edges is also unknown. We consider different types of graphs (doubling-dimension, planar and minor-free) and provide approximate solutions for each of them. For the case of doubling graphs and minor-free graphs, we construct a single spanning tree for the single-source buy-at-bulk network design problem. For the case of planar graphs, we have built a set of paths with an asymptotically tight competitive ratio.
Files	Filename       Size       Approximate Download Time (Hours:Minutes:Seconds)     28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access    Dissertation.pdf 1.28 Mb 00:05:56 00:03:03 00:02:40 00:01:20 00:00:06

If you have questions or technical problems, please Contact LSU-ETD Support.