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 AbstractLarge-scale networks such as the Internet has emerged as arguably the most complexdistributed 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.pdf1.28 Mb 00:05:56 00:03:03 00:02:40 00:01:20 00:00:06

Browse All Available ETDs by
( Author |
Department )

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