TY - GEN
T1 - A random graph approach for multicast scheduling and performance analysis
AU - Han, Guowen
AU - Yang, Yuanyuan
N1 - Publisher Copyright:
© 2003 IEEE.
PY - 2003
Y1 - 2003
N2 - In this paper, we consider scheduling in multicast switching networks, which aims to minimize the multicast latency for a set of multicast requests. Such a problem has been proved to be NP-complete. We propose a simple, fast greedy multicast scheduling algorithm and derive a lower bound and an upper bound on the performance of the algorithm. As can be seen, while a lower bound is fairly straightforward, the upper bound is much more difficult to obtain. By translating the multicast scheduling problem into a graph theory problem and employing a random graph approach, we are able to obtain a probabilistic upper bound on the performance of the multicast scheduling algorithm. Our analytical and simulation results show that the performance of the proposed multicast scheduling algorithm is quite close to the lower bound and is statistically guaranteed by the probabilistic upper bound.
AB - In this paper, we consider scheduling in multicast switching networks, which aims to minimize the multicast latency for a set of multicast requests. Such a problem has been proved to be NP-complete. We propose a simple, fast greedy multicast scheduling algorithm and derive a lower bound and an upper bound on the performance of the algorithm. As can be seen, while a lower bound is fairly straightforward, the upper bound is much more difficult to obtain. By translating the multicast scheduling problem into a graph theory problem and employing a random graph approach, we are able to obtain a probabilistic upper bound on the performance of the multicast scheduling algorithm. Our analytical and simulation results show that the performance of the proposed multicast scheduling algorithm is quite close to the lower bound and is statistically guaranteed by the probabilistic upper bound.
KW - Bandwidth
KW - Communication switching
KW - Computer networks
KW - Delay
KW - Multicast communication
KW - Performance analysis
KW - Processor scheduling
KW - Scheduling algorithm
KW - Upper bound
KW - Wavelength division multiplexing
UR - https://www.scopus.com/pages/publications/10044230223
U2 - 10.1109/ICCCN.2003.1284181
DO - 10.1109/ICCCN.2003.1284181
M3 - Conference contribution
AN - SCOPUS:10044230223
T3 - Proceedings - International Conference on Computer Communications and Networks, ICCCN
SP - 270
EP - 275
BT - Proceedings - 12th International Conference on Computer Communications and Networks, ICCCN 2003
A2 - Luijten, Ronald P.
A2 - Park, E.K.
A2 - DaSilva, Luiz
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 12th IEEE International Conference on Computer Communications and Networks, ICCCN 2003
Y2 - 20 October 2003 through 22 October 2003
ER -