Abstract—The naming and routing play a very important role for network communications. To characterize the influence of network topology characteristics, network mobility features, network layer naming schemes on the routing scalability, we introduce a new concept called partial transparent graph. We show that a partial transparent graph can better characterize the topological properties of a layered computer network by introducing different kinds of nodes. And we present a routing analysis model to formalize topologies of layered computer networks, network-layer naming, and routing. Then we analyze the routing scalability of two special kinds of naming and routing schemes. We prove that in a static topology with a structured naming, the routing table size can be very small and does not depend on the network size. In a dynamic topology, in which a node can move randomly, the routing table size for name-independent routing with some constraints is linear with the network size.

Index Terms—network architecture, topology, mobility, network naming, name-independent, routing

Cite: Feng Zhao, Baosheng Wang, Xiaofeng Hu, Wei Peng, and Chunqing Wu, "Understanding the Influence of Network Topology and Network-layer Naming on the Scalability of Routing," Journal of Communications, vol. 8, no. 10, pp. 672-680, 2013. doi: 10.12720/jcm.8.10.672-680