ABSTRACT:
The heterogeneous postal delivery model assumes that each intermediate node in the multicasting tree incurs a constant switching time for each message that is sent. We have proposed a new model where we assume a more generalized switching time at intermediate nodes. In our model, a child node v of a parent u has a switching delay vector, where the ith element of the vector indicates the switching delay incurred by u for sending the message to v after sending the message to i − 1 other children of u. Given a multicast tree and switching delay vectors at each non-root node in the tree, we provide an O(n5 over 2) optimal algorithm that will decide the order in which the internal (non-leaf) nodes have to send the multicast message to its children in order to minimize the maximum end-to-end delay due to multicasting. We also show an important lower bound result that optimal multicast switching delay problem is as hard as min-max matching problem on weighted bipartite graphs and hence O(n5 over 2) running time is tight.
Did you like this research project?
To get this research project Guidelines, Training and Code... Click Here
