DISTRIBUTED, SCALABLE ROUTING BASED ON VECTORS OF LINK STATES

Link vector algorithms (LVA) are introduced for the distributed mainte nance of routing information in large networks and internets. Accordin g to an LVA, each router maintains a subset of the topology that corre sponds to adjacent links and those links used by its neighbor routers in their preferred paths to known destinations. Based on that subset o f topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbor s. An update message contains a vector of updates; each such update sp ecifies a link and its parameters. LVA's can be used for different typ es of routing. The correctness of LVA's is verified for arbitrary type s of routing when correct and deterministic algorithms are used to sel ect preferred paths at each router and each router is able to differen tiate old updates from new. LVA's are shown to have better performance than the ideal link-state algorithm based on flooding and the distrib uted Bellman-Ford algorithm.