Measurement-based Optimal Routing Strategies on Overlay Architectures

In this thesis, we seek optimal, yet practical, multipath routing algorithms that can minimize the network congestion by exploiting the locally collected measurement data. We first develop a distributed measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple unicast sources. Multiple paths are established using overlay nodes. The algorithm is derived from simultaneous perturbation stochastic approximation (SPSA) and does not assume that the gradient of an analytical cost function is known…

Contents

1 Introduction
2 Measurement Based Optimal Multipath Routing for Unicast Sessions
2.1 Model
2.2 Stochastic Approximation
2.3 Optimal Routing Using SPSA
2.3.1 An Optimal Routing Algorithm – Decreasing Step Size
2.3.2 The Optimal Routing Algorithm – Constant Step Size
2.3.3 Measurement Process
2.4 Implementation Issues
2.4.1 Path Establishment
2.4.2 Traffic Monitoring
2.5 Experimental Setup and Simulation Results
2.6 Conclusion
2.7 Proof of Theorem 2.3.1
2.8 Proof of Theorem 2.3.2
3 A Unified Framework for Multipath Routing for Unicast and Mul-ticast Traffic
3.1 Background & Set-up
3.1.1 Digital Fountain codes
3.2 Network models
3.2.1 Network Model-I
3.2.2 Network Model-II
3.2.3 Network Model-III
3.3 Optimization Framework and the Proposed Algorithm
3.3.1 Proposed routing algorithm
3.4 Convergence of the Proposed Algorithm
3.4.1 Decreasing step size case
3.4.2 Constant step size case
3.5 Simulation Results
3.5.1 First topology
3.5.2 Second topology
3.6 Conclusion
3.7 Proof of Theorem 3.4.2
3.8 Proof of Theorem 3.4.4
3.9 Proof of Lemma 3.7.1
4 Obtaining Better Paths through Overlay Node Selection
4.1 Introduction
4.2 Model
4.3 Stochastic Comparison Algorithm
4.4 A suboptimal heuristic
4.5 Simulation Results
4.5.1 Unicast traffic sessions under first network topology
4.5.2 Unicast traffic sessions under second topology
4.5.3 Unicast traffic sessions with a non-uniform traffic matrix
4.5.4 Multicast traffic sessions
5 Conclusion
Bibliography

Author: Guven, Tuna

Source: University of Maryland

Download URL 2: Visit Now