Title page for ETD etd-04202011-092524


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 di fferent 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

Browse All Available ETDs by ( Author | Department )

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