Information exchange for routing protocols

Distance vector routing is a classic distributed algorithm for obtaining routing tables in a communication network. The algorithm relies on message exchange between neighbor routers. This paper studies the amount of routing data that needs to be stored and exchanged. On a static network, a variation of the algorithm that exchanges routing trees or pseudotrees is slightly more information theoretically efficient than a traditional implementation that exchanges tables. Knowledge of an underlying graph model and proper estimation of parameters allow more efficient coding schemes, including schemes related to Slepian-Wolf coding. Further improvements can be obtained on a dynamic network.