Nikhil Gopinath Shetty

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-122

September 19, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-122.pdf

In this paper, we devise a novel method for bottleneck analysis of UDP networks based on the concept of network utility maximization. This method does not rely on time-consuming packet-level simulations, but is instead based on robust mathematical models. For fluid flows, one could solve a fixed point to determine the losses on links and extend this to random rates using a Monte Carlo simulation. However, lack of knowledge of convergence makes it difficult to predict the end of the simulation. Our method is more advantageous as it involves solving an optimization problem, the solution to which can be numerically determined to the desired accuracy. Also, compared to a black and white approach between worst-case analysis and average-case analysis, our method offers network managers the flexibility of choosing the shades of gray in between. To determine the losses on the links in a UDP network, we propose a geometric program formulation for which we find and prove conditions under which it accurately determines the true losses. We further extend this analysis to stochastic rates using stochastic optimization techniques, and show how the desired flexibility is obtained.

Advisors: Jean Walrand

---

BibTeX citation:

@mastersthesis{Shetty:EECS-2008-122,
    Author= {Shetty, Nikhil Gopinath},
    Title= {A Novel Approach to Bottleneck Analysis in Networks},
    School= {EECS Department, University of California, Berkeley},
    Year= {2008},
    Month= {Sep},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-122.html},
    Number= {UCB/EECS-2008-122},
    Abstract= {In this paper, we devise a novel method for bottleneck
analysis of UDP networks based on the concept of
network utility maximization. This method does not rely on
time-consuming packet-level simulations, but is instead based on
robust mathematical models. For fluid flows, one could solve a
fixed point to determine the losses on links and extend this to
random rates using a Monte Carlo simulation. However, lack
of knowledge of convergence makes it difficult to predict the
end of the simulation. Our method is more advantageous as it
involves solving an optimization problem, the solution to which
can be numerically determined to the desired accuracy. Also,
compared to a black and white approach between worst-case
analysis and average-case analysis, our method offers network
managers the flexibility of choosing the shades of gray in between.
To determine the losses on the links in a UDP network, we
propose a geometric program formulation for which we find and
prove conditions under which it accurately determines the true
losses. We further extend this analysis to stochastic rates using
stochastic optimization techniques, and show how the desired
flexibility is obtained.},
}

EndNote citation:

%0 Thesis
%A Shetty, Nikhil Gopinath 
%T A Novel Approach to Bottleneck Analysis in Networks
%I EECS Department, University of California, Berkeley
%D 2008
%8 September 19
%@ UCB/EECS-2008-122
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-122.html
%F Shetty:EECS-2008-122