COMPUTER NETWORKS RESEARCH LAB

TSP Lab

Department of Electrical and Computer Engineering, McGill University

  NAVIGATION

Home
People
Photos
 

  RESEARCH

Projects
Publications
 

  LINKS

AAPN
MITACS
McGill TSP
McGill ECE
 

  LOCAL ACCESS
Local Info
 
 

Project Descriptions Return to Network Monitoring Projects

Efficient Network-wide Available Bandwidth Estimation through Active Learning and Belief Propagation
 

Researchers: Frederic Thouin Ph.D. student, Prof. Mark Coates and Prof. Mike Rabbat.

Description:

Measurement Model: One of the techniques to estimate the available bandwidth on one path is to use trains of packets. It consists of sending packets of data at a known and constant rate on the path we are interested in, and then, by observing various metrics, determine if this rate is greater or not than the actual capacity. This process is repeated iteratively until some convergence criterion is met. In this section, we present the two metrics we have paid more attention to; one-way delays (OWDs) and the receiving rate.

Belief Propagation: One way of representing the relations between all the paths and links we are interested in is factor graphs; a bipartite graph that expresses which variables are arguments of which local functions. Each variable has an associated node in the graph that represents the probability distribution of either one of the single link or path in the network. After each iteration (measurement), rather than updating lower and upper bounds of the confidence interval, we update these PDFs that give us the probability of all possible values (in the allowed range) for the available bandwidth.

The way information is shared amongst nodes in a factor graph is by using message passing, or belief propagation. The algorithm called the sum-product obeys the following update rule: the message sent from a node $v$ on an egde $e$ is the product of the local function at $v$ with all messages received at $v$ on edges other than $e$, summarized for the variable associated with $e$.

Active Learning Algorithm: Most previous approaches use lower and upper bounds to determine the interval within which the available bandwidth lies. To decide on the probing rate, they use a binary search approach and choose the mean of the bounds. We adopt a similar approach by using the marginal of the path we have chosen and probe at the median rate (Figure~\ref{fig:median}). By probing at the median, there is equal probability that the available capacity is smaller or greater than the probing rate, and therefore we maximize the expected information gain from our measurement.

A well-known passive path selection method is round robin (RR). This consists of probing consecutively all the paths in order until the stopping criterion is met. This means that even if we have a estimate of the available capacity with high probability of one path, we still make a measurement on it. Which could be considered wasteful since we are trying to minimize the number of measurements we make. We use active path selection to reduce the number of measurements by using information from prior measurements to choose the path that will maximize the expected information gain. More precisely, we use the entropy of the paths (calculated from the marginals) to make the selection; paths with high entropy have more uncertainty and therefore there is more information to gain. In this first technique, called weighted entropy (WE), to avoid choosing the same path over and over we assign each path a probing probability proportional to its entropy. Another technique is to simulate measurements on every single path and take the expected value of both possible outcomes of a given metric. In Active Learning Path (ALP), we choose the path that will minimize the sum of the entropy of all paths. The obvious issue with this type of techniques is the lack of scalability. The large delays in between each measurements make it hard to implement it in practice.

Simulation and Experimental Results: