With the continuing growth and dynamicism of large scale networks, alternative evaluation criteria for routing algorithms are becoming increasingly important. The emergence of low-bandwidth ad-hoc mobile networks requires routing algorithms that can distribute data traffic across multiple paths and quickly adapt to changing conditions. Multi-path routing offers several advantages, including better bandwidth utilization, bounding delay variation, minimizing delay, and improved fault tolerance. Furthermore, current single path routing algorithms face route oscillations (or flap), since they switch routes as a step function. The solution has been to choose low variance routing metrics that are not amenable to route flap, which incidentally are also metrics that don't represent the true state of the network. Good multi-path routing involves gradual changes to routes and should work well even with high variance routing metrics.
While multi-path routing is a desirable goal, the current Internet routing framework cannot be easily extended to support it. One solution is to develop a new multi-path routing framework, which necessitates changes to the Internet's networking protocol (IP). The main problem here stems from deployability concerns. Our approach is to study multipath routing within the confines of the current Internet protocol, which leads to interesting design decisions.
In this work, we approach multi-path routing from the limiting perspective of reachability routing, where the routing algorithm attempts to determine all paths between a sender and a receiver. This is particularly important in highly dynamic environments resource-constrained such as overlay networks and wireless networks. In this research we use reinforcement learning to realize reachability routing, within the confines of the current Internet backbone infrastructure. The setting of the reinforcement learning problem offers several advantages, including loop resolution, multi-path forwarding capability, cost-sensitive routing, and minimizing state overhead, while maintaining the incremental spirit of the current backbone routing algorithms.
In the current design, we use a model-based approach to achieve cost-sensitive multi-path forwarding. Performance assessment of the algorithm in various troublesome topologies shows consistently superior performance over classical reinforcement learning algorithms. We are extending this work to improve the sophistication of the model-based algorithm, with a view to developing a complete routing protocol implementation.