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
- Sparse Covers
- Graph Theory
Date of Defense 2011-04-13 Availability unrestricted AbstractLarge-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.
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.