Sudip Misra
Multihop networks, such as the Internet and the Mobile Ad hoc Networks (MANETs), contain several routers and mobile hosts, which employ different routing protocols. In many of these protocols, each router (or a routing device) computes and stores a shortest path tree from one router to all other routers and hosts in a routing domain.
I will present a new efficient solution to the problem of maintaining shortest path routing trees in networks that undergo stochastic updates in the link costs. In vast, rapidly changing telecommunications (wired or wireless) networks, where links go up and down continuously and rapidly, and where there are simultaneous random updates in link costs, the existing algorithms are either unsuitable in some cases, or are inefficient in others. In such cases, shortest paths need to be computed within a very short time (often in the order of microseconds) by scanning and processing the minimal number of nodes and links. The algorithm that I will present will be very useful in this regard. It uses learning techniques. Indeed, it has the advantage that it can be used to find the shortest path within average network, which converges irrespective of whether there are new changes in link-costs or not. The algorithm has been rigorously evaluated experimentally, and its superiority has been established.