Enhancing the performance of a dynamically partitionable bus network using a graph coloring algorithm

摘要

An efficient dynamic graph traversal algorithm is used to identify non-conflicting requests and to allocate network resources in a dynamically partitionable bus network (DPBN). A special processor receives from the control computer of a partitionable bus network an adjacency matrix which indicates conflicts among requests. It applies the dynamic graph traversal algorithm and returns the identified non-conflicting requests to the control computer. The control computer then physically partitions the network into a number of subnetworks for processing non-conflicting requests in parallel. The results of performance evaluation show a forty percent decrease of network delay as compared with a fully utilized, but unpartitioned local area network.