Prefix Routing Schemes in Dynamic Networks

摘要

A routing scheme on dynamic networks called a prefix routing scheme is studied.The scheme is an abstraction of source routing. It assigns fixed addresses to the nodes and one address per link. Routing of messages is done by sending the messages out via the link with maximum common prefix with the destination node. Arbitrary insertions of links and nodes are feasible with constant adaptation cost. It is shown that any dynamic growing network can be assigned such a scheme. The type of fixed networks with dynamic links (i.e., the cost of the links can vary over time) and dynamic networks with arbitrary insertion and deletion of nodes and links (without disconnecting the network) that allow optimum routing in this scheme are characterized completely. A hierarchical routing scheme where each link may carry more than one address is introduced and the connections between prefix routine and static interval routing are presented.