A Coding-Based Approach to Robust Shortest-Path Routing

Robust and distributed creation of routing tables is essential for the functioning of a modern communication network. One of the two main types of routing algorithms in use in today's Internet is made up of variations of the so-called distance-vector or Bellman-Ford algorithm (Bellman, Quart Appl Math 16: 87-90, 1958; Ford (1956) Network flow theory paper P-923. RAND Corporation, Santa Monica; Moore (1959) The shortest path through a maze. In: Proceedings of an international symposium on the theory of switching 1957, Cambridge. Part II. Harvard University Press, pp 285-292). These algorithms suffer from two main deficiencies: (i) The amount of data exchanged for the algorithms to function is considered excessive for some applications, and (ii) the algorithms respond slowly to "bad news" in the network. This is known as the count-to-infinity (c2 infinity) problem. In order to address (ii), protocol designers (RFC1058 - routing information protocol (1988) Internet Engineering Task Force) have introduced heuristics such as the "split horizon" and the "route poisoning" techniques. It can be shown by simple examples that these heuristics do not solve the c2 infinity problem completely. In this paper we describe a simple routing algorithm, the Tree Routing algorithm, that exchanges no more data than existing algorithms, and that at the same time provides routing agents with no less (and often more) insight into the topology of the network. The Tree Routing algorithm is inspired by techniques used in information theory and coding theory. We explain why the Tree Routing algorithm will never respond slower, and will often respond faster, than existing algorithms.