Resource allocation in a dynamically partitionable bus network using a graph coloring algorithm

An efficient dynamic graph traversal algorithm is used to identify nonconflicting requests and to allocate network resources in a dynamically partitionable bus network (DPBN). In centralized network control 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 nonconflicting requests to the control computer. The control computer then physically partitions the network into a number of subnetworks for processing the nonconflicting requests in parallel. In distributed control, each station determines conflicts and sets the switches. The results of performance evaluation show a 40% decrease of network delay as compared with a fully utilized, but unpartitioned local area network