  This paper studies the evaluation of routing algorithms from the perspective
of reachability routing, where the goal is to determine all paths between a
sender and a receiver. Reachability routing is becoming relevant with the
changing dynamics of the Internet and the emergence of low-bandwidth
wireless/ad-hoc networks. We make the case for reinforcement learning as the
framework of choice to realize reachability routing, within the confines of the
current Internet 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 current backbone routing
algorithms. We identify research issues in reinforcement learning applied to
the reachability routing problem to achieve a fluid and robust backbone routing
framework. The paper is targeted toward practitioners seeking to implement a
reachability routing algorithm.
