Home Problem Statement
Recently we have seen an emergent trend of self adaptive routing in both Internet and wireless ad hoc networks. Although there is previous work on studying the traffic equilibria of self adaptive routing (e.g., selfish routing), the previous methods use computationally demanding algorithms and require that a precise analytical model of the network be given. Also, it remains an open question how to design an adaptive scheme that ensures convergence to a traffic equilibrium in practice.
Adaptive Routing: a learning-based approach
We propose a simple, distributed, probabilistic routing scheme for scalable, efficient, self adaptive routing in dynamic, realistic environments. Using both analysis and extensive simulations, we show that our scheme can converge to the desired traffic equilibrium (either user-optimal or network-optimal) very quickly.
Interesting results
We find that user-optimal routing can achieve very close to optimal average latency in dynamic environments, but such performance often comes at the cost of seriously overloading certain links. To avoid link overloads, we improve adaptive routing by optimizing average user latency and link utilization simultaneously. Our evaluation shows that there is a trade-off between optimizing dual objectives, but the degradation in average latency is only marginal for typical link utilization requirements.
Paper Toys
- On Self Adaptive Routing in Dynamic Environments -- An Evaluation and Design Using a Simple, Probabilistic Scheme, Haiyong Xie, Lili Qiu, Yang Richard Yang, and Yin Zhang. In Proceedings of 12th International Conference on Network Protocols (ICNP 2004), Berlin, Germany, October 2004. (PDF)
- On Self Adaptive Routing in Dynamic Environments -- An Evaluation and Design Using a Simple, Probabilistic Scheme, Haiyong Xie, Lili Qiu, Yang Richard Yang, and Yin Zhang, Yale Computer Science Technical Report YALEU/DCS/TR-1289, May 2004. (PDF)