Article Preview
Top1. Introduction
Information is transmitted in the network in form of packets. Routing is the process of transmitting these packets from one network to another. While transmitting the packets from source to the destination, a number of intermediate hops came in picture. Various performance parameters (Sivakumar, 2011) are used to judge the quality of routing such as delay, packet delivery ratio, control overhead, throughput, jitter etc. Some of the most important parameter used for judging the quality is the delay and packet delivery ratio. Different routing algorithms such as shortest path routing, bellman ford algorithms are used. The simplest and effective policy used is the shortest path routing. In shortest path routing the path with minimum number of hops is selected to deliver the packet from source to the destination. In shortest path routing, cost table and neighbor tables are present to store the appropriate information and tables are exchanged frequently for adaptation purpose.
The shortest path routing policy is good and found effective for less number of nodes and when less traffic present on the network. But this policy is not always good as there are some intermediate nodes present in the network that are always get flooded with huge number of packets. Such routes are referred as popular routes. In such cases, it is always better to select the alternate path for transmitting the packets. This path may not be shortest in terms of number of hops, but this path definitely results in minimum delivery time to reach the packets to the destination because of less traffic on those routes. Such routes are dynamically selected in real time based on the actual traffic present on the network. Hence when the more traffic is present on some popular routes, some un-popular routes must be selected for delivering the packets. This is the main motivating factor for designing and implementing various adaptive routing algorithms on a network.
Learning such effective policy for deciding routes online is major challenge, as the decision of selecting routes must be taken in real time and packets are diverted on some unpopular routes. The main goal is to optimize the delivery time for the packets to reach to the destination and preventing the network to go into the congestion. There is no training signal available for deciding optimum policy at run time, instead decision must be taken when the packets are routed and packets reaches to the destination on popular routes.
DSDV (Toteja Asma, Gujral Toteja, Thalia Sunil, 2011) is one of the proactive routing protocol developed for an ad hoc network. This is based on distance vector routing protocol and uses destination sequence numbers to avoid count to infinity problem. Second type of routing protocol on an ad hoc network is on demand routing protocols which are also known as reactive routing protocols. These routing protocols maintain routes whenever required.
The Dynamic Source Routing Protocol (DSR) (Kulla et.al., 2011) is one of the on demand routing protocol which is characterized by the use of source routing. That is, the sender knows the complete hop-by-hop route to the destination. These routes are stored in a route cache. Ad Hoc on Demand Distance Vector Routing (AODV) is also on-demand routing protocol. AODV uses traditional routing tables, one entry per destination. This is in contrast to DSR, where DSR maintains multiple route cache entries for each destination. Being a single path protocol, it had to invoke a new route discovery process whenever this single path fails. To overcome this limitation, another Multipath extension to AODV called Ad Hoc On-Demand Multipath Distance Vector (AOMDV) is used.
The paper is organized as follows. Section 2 introduces the literature survey of various reinforcement learning algorithms. Section 3 evaluates various algorithms using Network simulator NS2.34. Section 4 concludes with main results.