© The Institution of Engineering and Technology
A ‘fibre-switch block’ is a switch with delay lines that feedback from some outputs to inputs. In every unit time, it receives and transmits a packet concurrently. A ‘fibre memory’ means a multi-block serial connection. Its performance of time-multiplexed operation is often said to ‘emulate’ a multistage interconnection network. This study formulates this concept of emulation. The formalised concept is useful in the design and validation of various switching functionalities, including timeslot interchanging, sorting, merging and concentration. For illustration, ‘banyan-type networks’, ‘Clos network’ and several familiar multi-stage sorting networks are all efficiently emulated.
References
-
-
1)
-
21. Wu, C.-L., Feng, T.-Y.: ‘On a class of multistage interconnection networks’, IEEE Trans. Comput., 1980, C-29, (8), pp. 694–702 (doi: 10.1109/TC.1980.1675651).
-
2)
-
1. Clos, C.: ‘A study of nonblocking switching networks’, Bell Syst. Tech. J., 1953, 32, pp. 406–424 (doi: 10.1002/j.1538-7305.1953.tb01433.x).
-
3)
-
19. Goke, L.R., Lipovski, G.J.: ‘Banyan networks for partitioning multi-processing systems’. Proc. First Annual Computer Architecture Conf., New York, USA, December 1973, pp. 21–28.
-
4)
-
22. Parker, D.S.: ‘Note on shuffle/exchange-type switching networks’, IEEE Trans. Comput., 1980, C-29, (3), pp. 213–222 (doi: 10.1109/TC.1980.1675553).
-
5)
-
20. Lawrie, D.H.: ‘Access and alignment of data in an array processor’, IEEE Trans. Comput., 1975, C-24, (12), pp. 1145–1155 (doi: 10.1109/T-C.1975.224157).
-
6)
-
16. Benes, V.E.: ‘Mathematical theory of connecting network and telephone traffic’ (Academic press, 1965).
-
7)
-
18. Robert Li, S.-Y., Tan, X.J.: ‘Recursive construction of parallel distributed networks’, J. Parallel Distrib. Comput., 2007, 67, (6), pp. 617–634 (doi: 10.1016/j.jpdc.2007.01.004).
-
8)
-
3. Chou, C.-C., Chang, C.-S., Lee, D.-S., et al: ‘A necessary and sufficient condition for the construction of 2-to-1 optical FIFO multiplexers by a single crossbar switch and fiber delay lines’, IEEE Trans. Inf. Theory, 2006, 52, (10), pp. 4519–4531 (doi: 10.1109/TIT.2006.881712).
-
9)
-
7. Chiu, H.-C., Chang, C.-S., Cheng, J., et al: ‘A simple proof for the constructions of optical priority queues’, Queueing Syst. Theory Appl., 2007, 56, (2), pp. 73–77 (doi: 10.1007/s11134-007-9033-x).
-
10)
-
2. Chang, C.-S., Lee, D.-S., Tu, C.-K.: ‘Recursive construction of FIFO optical multiplexers with switched delay lines’, IEEE Tran. Inf. Theory, 2004, 50, (12), pp. 3221–3233 (doi: 10.1109/TIT.2004.838092).
-
11)
-
12. Batcher, K.E.: ‘Sorting networks and their applications’. Proc. AFIP Spring Joint Computer Conf., New York, USA, April–May 1968, pp. 307–314.
-
12)
-
1. Pippenger, N.: ‘Juggling networks’. Proc. Canada–France Conf. on Parallel and Distributed Computing, Montréal, Canada, May 1994, pp. 1–12.
-
13)
-
9. Chang, C.-S., Chen, Y.-T., Cheng, J., et al: ‘Multistage constructions of linear compressors, non-overtaking delay lines, and flexible delay lines’. Proc. IEEE INFOCOM, Barcelona, Spain, April 2006, pp. 1–11.
-
14)
-
10. Knuth, D.E.: ‘The art of computer programming, Volume 3: sorting and searching’ (Addison-Wesley, 1973).
-
15)
-
14. Pratt, V.R.: ‘Shell sort and sorting networks’ (Garland Pub., New York, 1979).
-
16)
-
13. Shell, D.L.: ‘A high-speed sorting procedure’, Commun. ACM, 1959, 2, (7), pp. 30–32 (doi: 10.1145/368370.368387).
-
17)
-
5. Li, S.-Y.R., Tan, X.J.: ‘Mux/demux queues, FIFO queues, and their construction by fiber memories’, IEEE Trans. Inf. Theory, 2011, 57, (3), pp. 1328–1343 (doi: 10.1109/TIT.2011.2104552).
-
18)
-
4. Chang, C.-S., Chen, Y.-T., Lee, D.-S.: ‘Construction of optical FIFO queues’, IEEE Tran. Inf. Theory, 2006, 52, (6), pp. 2838–2843 (doi: 10.1109/TIT.2006.874538).
-
19)
-
11. Robert Li, S.-Y.: ‘Algebraic switching theory and broadband applications’ (Academic Press, 2001).
-
20)
-
23. Li, S.-Y.R., Tan, X.J.: ‘Analog memory by recursive 2-stage switching’. Proc. IEEE ISIT, Seattle, USA, July 2006, pp. 2779–2883.
-
21)
-
24. Ho, S.: ‘Applications of Algebra in Communication Engineering’, , The Chinese University of Hong Kong, 2010.
-
22)
-
17. Robert Li, S.-Y., Tan, X.J.: ‘Preservation of conditionally non-blocking switches under 2-stage interconnection’, IEEE Trans. Commun., 2007, 55, (5), pp. 973–980 (doi: 10.1109/TCOMM.2007.896062).
-
23)
-
6. Sarwate, D., Anantharam, V.: ‘Exact emulation of a priority queue with a switch and delay lines’, Queueing Syst. Theory Appl., 2006, 53, (3), pp. 115–125 (doi: 10.1007/s11134-006-6669-x).
-
24)
-
8. Huang, P.-K., Chang, C.-S., Cheng, J., et al: ‘Recursive constructions of parallel FIFO and LIFO queues with switched delay lines’, IEEE Trans. Inf. Theory, 2007, 53, (5), pp. 1778–1798 (doi: 10.1109/TIT.2007.894666).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2013.1122
Related content
content/journals/10.1049/iet-com.2013.1122
pub_keyword,iet_inspecKeyword,pub_concept
6
6