字典乘积图的点转发指数

路由选择的优劣直接影响网络通信性能的有效性.在大规模超级计算机系统中,某些元件和连线发生故障是不可避免的,故障的出现势必会对路由的选择产生影响.由于路由选择的点转发指数是用来度量网络节点的负载情况,因而它是衡量路由选择优劣的一个重要参数.本文利用图的字典乘积方法,用若干已有的小网络来构造规模较大的网络,通过分析这些小网络与所得大网络拓扑参数之间的联系,首次得到字典乘积网络点转发指数的一个紧的上界和紧的下界.

Vertex forwarding indices of the lexicographic product of graphs

With the rapid development of computer and communication networks, many theoretical problems have come into focus, one of which is the reliability design of a network. The main aim is to design an optimal system for the network. This type of question is of great interest in mathematics and has applications in many fields, e.g., supercomputer systems, multiple processor systems, communication systems and local area networks. Forwarding indices of a routing can be used to deterministically measure its efficiency. If some nodes or links fail, it is important to know which paths of the supercomputer system are malfunctioning, and, quite naturally, good routing should not overload any vertex by sending too many routing paths through it. The original study of forwarding indices was motivated by the problem of maximizing network capacity, which is achieved by minimizing the forwarding indices of a routing. Thus, determining the vertex forwarding indices of a given graph becomes very significant. In this study, we investigated the routing forwarding indices of the lexicographic product of graphs. Some large networks are composed from existing smaller networks, using, in terms of graph theory, the lexicographic product of graphs. Some properties of such large networks are associated strongly with those of the corresponding smaller networks. By using the topological structure and analysis of interconnection networks, and the theory of algebra, we characterize the closed lower and upper bounds on the vertex forwarding indices of the lexicographic product of graphs. The formula for the forwarding indices depends only on the distance, the number of vertices and vertex forwarding indices of the factor graphs.