Parallel implementation issues of the textured algorithm for optimal routing in data networks

Parallel implementation issues of the textured algorithm to solve the optimal routing problem (ORP) in data networks is investigated. The textured model decomposes a large data network into a multi-level structure, each level contains a few subnetworks and each subnetwork is controlled by a local processor (e.g. an internet gateway). Subnetworks of the same level are not overlapped with each other, subnetworks on different levels overlap partially. Compared with solving the ORP globally, the textured algorithm clearly saves computation time and has better precision since parallel computation is applied to smaller scale subproblems at each level. On the other hand, synchronization overhead among local processors needs to be addressed. It is shown that due to the characteristics of the textured algorithm, its synchronization overhead can be managed to remain a constant as the size of network increases since one only needs to exchange data among neighboring processors