Reinforcing Reachable Routes

Reachability routing is a newly emerging paradigm in networking, where the goal is to determine all paths between a sender and a receiver. It is becoming relevant with the changing dynamics of the Internet and the emergence of low-bandwidth wireless/ad hoc networks. This thesis presents the case for reinforcement learning (RL) as the framework of choice 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. We present the design and implementation of a new reachability algorithm that uses 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. Evaluations of the algorithm based on different criteria on many types of randomly generated networks as well as realistic topologies are presented.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2004

Author dc:creator

• Thirunavukkarasu, Muthukumar

Chairs dc:contributor.committeechair

• Varadarajan, Srinidhi
• Ramakrishnan, Naren

Committee member dc:contributor.committeemember

• Ribbens, Calvin J.

• Multipath routing
• Probabilistic algorithms
• Reachability
• Reinforcement learning

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-05102004-130036

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/9904