© The Institution of Engineering and Technology
The input-queued (IQ) switch architecture is favoured for designing multicast high-speed switches because of its scalability and low implementation complexity. However, using the first-in-first-out (FIFO) queueing discipline at each input of the switch may cause the head-of-line (HOL) blocking problem. Using a separate queue for each output port at an input to reduce the HOL blocking, that is, the virtual output queuing discipline, increases the implementation complexity, which limits the scalability. Given the increasing link speed and network capacity, a low-complexity yet efficient multicast scheduling algorithm is required for next generation high-speed networks. This study proposes the novel efficient round-robin multicast scheduling algorithm for IQ architectures and demonstrates how this algorithm can be implemented as a hardware solution, which alleviates the multicast HOL blocking issue by means of queue look-ahead. Simulation results demonstrate that this FIFO-based IQ multicast architecture is able to achieve significant improvements in terms of multicast latency requirements by searching through a small number of cells beyond the HOL cells in the input queues. Furthermore, hardware synthesis results show that the proposed algorithm can be very efficiently implemented in hardware to perform multicast scheduling at very high speeds with only modest resource requirements.
References
-
-
1)
-
16. Ugurdag, H.F., Baskirt, O.: ‘Fast parallel prefix logic circuits for n2n round-robin arbitration’, Microelectron. J., 2012, 43, pp. 573–581 (doi: 10.1016/j.mejo.2012.04.005).
-
2)
-
D. Pan ,
Y. Yang
.
FIFO-based multicast scheduling algorithm for virtual output queued packet switches.
IEEE Trans. Comput.
,
10 ,
1283 -
1297
-
3)
-
6. Yu, H., Ruepp, S., Berger, M.S.: ‘A novel round-robin based multicast scheduling algorithm for 100 Gigabit Ethernet switches’. Proc. IEEE INFOCOM WS, April 2010, pp. 2707–2711.
-
4)
-
H. Yu ,
S. Ruepp ,
M.S. Berger
.
Enhanced first-in-first-out-based round-robin multicast scheduling algorithm for input-queued switches.
IET Commun.
,
8 ,
1163 -
1171
-
5)
-
13. Shin, E.S., Mooney, V.J.III, Riley, G.F.: ‘Round-robin arbiter design and generation’, 15th Int. Symp. on System Synthesis, 2002. 2002, pp. 243–248 (doi: 10.1145/581199.581253).
-
6)
-
D. Pan ,
Y. Yang
.
Bandwidth guaranteed multicast scheduling for virtual output queued packet switches.
J. Parallel Distrib. Comput.
,
12 ,
939 -
949
-
7)
-
4. Bianco, A., Giaccone, P., Piglione, C., Sessa, S.: ‘Practical algorithms for multicast support in input queued switches’. Proc. High Performance Switching and Routing, October 2006.
-
8)
-
9. Yu, H., Ruepp, S., Berger, M.S., ‘Multi-level round-robin multicast scheduling with look-ahead mechanism’. Proc. IEEE Int. Conf. Communications, June 2011.
-
9)
-
10)
-
3. Bianco, A., Giaccone, P., Leonardi, E., Neri, F., Piglione, C.: ‘On the number of input queues to efficiently support multicast traffic in input queued switches’. Proc. High Performance Switching and Routing, June 2003.
-
11)
-
B. Prabhakar ,
N. McKeown ,
R. Ahuja
.
Multicast scheduling for input-queued switches.
IEEE J. Selected Area Commun.
,
5 ,
855 -
866
-
12)
-
M.J. Karol ,
M.G. Hluchyj ,
S.P. Morgan
.
Input versus output queueing on a space-division packet switch.
IEEE Trans. Commun.
,
12 ,
1347 -
1356
-
13)
-
5. Shoaib, M.: ‘Selectively weighted multicast scheduling designs for input-queued switches’. Proc. IEEE Int. Symp. Signal Processing and Information Technology, December 2007, pp. 92–97.
-
14)
-
J.F. Hayes ,
R. Breault ,
M. Mehmet-Ali
.
Performance analysis of a multicast switch.
IEEE Trans. Commun.
,
581 -
587
-
15)
-
16)
-
7. Hu, B., He, C., Yeung, K.L.: ‘Achieving 100% throughput for multicast traffic in input-queued switches’. Proc. IEEE Global Telecommunications Conf., December 2011, p. 1.
-
17)
-
P. Gupta ,
N. McKeown
.
Designing and implementing a fast crossbar scheduler.
IEEE Micro
,
20 -
28
-
18)
-
15. Jou, J.-M., Lee, Y.-L.: ‘An optimal round-robin arbiter design’, J. Inf. Sci. Eng., 2010, 26, pp. 2047–2058.
-
19)
-
1. McKeown, N., Prabhakar, B.: ‘Scheduling multicast cells in an input-queued switch’. Proc. IEEE Fifteenth Annual Joint Conf. IEEE Computer Societies (INFOCOM), March 1996, pp. 271–278.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-net.2012.0172
Related content
content/journals/10.1049/iet-net.2012.0172
pub_keyword,iet_inspecKeyword,pub_concept
6
6