UMass Machine Learning and Friends Lunch | Main / Robust Routing In Dynamic Networks

Wireless networks, and mobile ad-hoc networks (MANETs) in particular, are characterized by time-varying link characteristics and network topology. In such an environment, the network must accommodate the changes, providing end-end packet delivery while at the same time incurring low control overhead. This work proposes a routing algorithm for MANETs with the primary goal of maximizing connectivity while limiting overhead. Rather than using one or more disjoint paths between a source and destination, a set of non-disjoint paths, or braid, is selected. To adapt to link changes, local rerouting is performed within the braid, thus avoiding network-wide recalculations. We analytically characterize the source-destination connectivity of the braid. Through simulation, we compare the reliability of braided routing and various other MANET routing protocols, including Ad-hoc On-Demand Distance Vector (AODV) routing, and quantify the relative amounts of control overhead incurred by braided routing and AODV.