Interconnection Network Routing and Graph Symmetry

点击翻译按钮获取中文摘要

Efficient routing schemes are of fundamental importance to both traditional and optical interconnection networks. To achieve high performance it is recommended that the graph modelling the network be vertex-transitive, meaning that it looks the same viewed from any vertex. In this project we will conduct a systematic study of the routing problem for such networks. We will focus on the effect of vertex-transitivity and some other symmetry properties on the efficiency of routing schemes measured by the vertex- and edge-congestions, and the minimum number of wavelengths needed in optical networks.