| |
Researchers: Hong Li, Ph.D. student, Prof. Lorne Mason & Prof. Michael Rabbat
Description:
Problem: The project studies the problem of identifying
minimum delay paths in a service overlay network. Low end-to-end delay is one of the most important
quality of service requirements for real-time applications.
For example, VoIP requires the mouth-to-ear delay
to be less than 150ms. In many cases, the minimum
delay path provides the best quality for VoIP and other
real time streaming applications. However, the minimum
hop path, as determined by the underlying network
routing protocols, does not guarantee minimum delay.
In previous works, minimum delay paths are learned based on endto-
end delay estimation. In our work, no delay estimation
is involved.
Approach: We propose, analyze and simulate
an active probing and learning algorithm using distributed
learning automata to find the minimum mean
delay paths in service overlay networks.
We adopt a reinforcement learning technique: the crosscorrelation
learning algorithm. The basic idea is that,
at each probing epoch, the path probed is chosen randomly
according to a distribution over a set of possible
paths between a given source and destination. The observed
delay for this probe is then used to reinforce this
path by increasing the probability of probing it again,
and simultaneously decreasing the probability of probing
the other paths.
Simulation Results:
The convergence of mean delay for all source destination pairs is shown below.
Fig: Mean delays on the learned
paths versus the mean delays on the optimal paths and
those on the minimum hop paths.
We also simulated the hop-by-hop learning method
for larger overlay network. The figure below shows the learning
speed for hop-by-hop learning with uniform initialization
in 10, 15, 20, 25 node overlay network.
Fig: Learning result in a
10 (top left),15 (top right), 20 (bottom left)
and 25 (bottom right) node overlay network,
gain=0.01.
Publications:
H. Li, L. Mason and M. Rabbat, "Learning minimum delay paths for VoIP in Service Overlay Networks", in Proc. IEEE NCA, July 2008, Cambridge, MA, USA.[pdf]
|
Return to QoS Routing for VoIP Projects