Home > Published Issues > 2013 > Volume 8, No. 10, October 2013 >

Understanding the Influence of Network Topology and Network-layer Naming on the Scalability of Routing

Feng Zhao, Baosheng Wang, Xiaofeng Hu, Wei Peng, and Chunqing Wu
College of Computer, National University of Defense Technology, Changsha, P.R. China

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