Duplicating delays in network multicasting: Model, algorithm and validation

A multicast tree is used to send the same message from the root (source) of the multicast tree to the leaves (destinations) of the tree. Each interior (non-leaf) node of the multicast tree, duplicates the message (or executes several send statements) sent by its parent and delivers them to its children. We consider a multicast model in which there is an additional delay involved in this duplication and transmission process. In this model, we assume (later experimentally verified) that the delay experienced by a child node in receiving the message depends on the order in which the parent selects the children to send the message. For each child node a duplicating vector of size equal to the number of siblings is used to represent the delays. The delay information in the i^th position of the vector indicates the additional delay experienced by the child node, if its parent sends the message to it after it has sent the messages to the other i-1 children first. The main contribution of this work is that given a multicast tree and delay vectors at each non-leaf node in the tree, we provide an O(n^5/2) optimal algorithm that will decide the order in which each internal node would have to send the multicast message to its children so as to minimize the maximum delay experienced by the root. We describe an experimental setup that validates the model.