BOUNDS ON THE PERFORMANCE OF MESSAGE ROUTING HEURISTICS

Let S be a set of messages to be routed on an N x N omega network. In addition, suppose that S contains communication conflicts. One strateg y to deal with such conflicts is to partition S into some number of su bsets, called rounds, such that each subset is conflict-free. The mess ages are then routed through the network by successively routing the m essages in each subset. The minimum round partitioning problem is the problem of partitioning a given message set into a minimum number of r ounds. We establish upper and lower bounds on the performance ratio fo r two heuristics for partitioning message patterns into rounds. For bo th of these heuristics we give upper and lower bounds of 0 (log N) and OMEGA (log N), respectively.