  Current directions in network routing research have not kept pace with the
latest developments in network architectures, such as peer-to-peer networks,
sensor networks, ad-hoc wireless networks, and overlay networks. A common
characteristic among all of these new technologies is the presence of highly
dynamic network topologies. Currently deployed single-path routing protocols
cannot adequately cope with this dynamism, and existing multi-path algorithms
make trade-offs which lead to less than optimal performance on these networks.
This drives the need for routing protocols designed with the unique
characteristics of these networks in mind.
  In this paper we propose the notion of reachability routing as a solution to
the challenges posed by routing on such dynamic networks. In particular, our
formulation of reachability routing provides cost-sensitive multi-path
forwarding along with loop avoidance within the confines of the Internet
Protocol (IP) architecture. This is achieved through the application of
reinforcement learning within a probabilistic routing framework. Following an
explanation of our design decisions and a description of the algorithm, we
provide an evaluation of the performance of the algorithm on a variety of
network topologies. The results show consistently superior performance compared
to other reinforcement learning based routing algorithms.
