DYNAMIC PRIORITIZED CONFLICT-RESOLUTION ON MULTIPLE-ACCESS BROADCAST NETWORKS

In a multiple access broadcast network, all network nodes share a sing le shared communication channel, and there is the possibility of a col lision when two or more nodes transmit at overlapping times. We propos e a dynamic prioritized conflict resolution algorithm in which, when a collision occurs, all colliding messages are retransmitted according to their priority. When a new message arrives, it is allowed to partic ipate in the algorithm as soon as it finds its priority is higher than that of some broadcast message. Using a time-slotted model, for any a rrival pattern and priority distribution, we show that our algorithm r uns in expected linear time, i.e., O(r), where ris the total number of message transmitted. We also show that the expected waiting time for any message x is O((rank(x) + log s), where rank(x) is the expected nu mber of messages with higher priority which transmit while x is waitin g, and s is the minimum of the total number of messages participating in the algorithm and the total number of nodes in the network. The ana lysis presented in this work also includes an improved analysis of our original (static) prioritized conflict resolution algorithm. This wor k is applicable to multimedia communications where different priority values could be assigned to different kinds of traffic, and our algori thm ensures that the high-priority real-time traffic has the minimum d elay.