From switching theory to "queueing" theory

ABSTRACT

Queueing theory is generally known as the theory to study the performance of queues. In this extended abstract, we are interested in another aspect of queueing theory, the theory to construct queues. Our interest in constructing queues originates from optical packet switching. Traditionally, queues are relatively cheap to build via electronic memory. However, it is very costly to convert optical packets into electronic packets. As such, building optical queues with minimum complexity has become an important research topic.

REFERENCES

• 1: C.-S. Chang, Y.-T. Chen, and D.-S. Lee, "Construction of optical FIFO queues and nonovertaking delay lines," submitted to IEEE Transactions on Information Theory.
• 2: C.-S. Chang, Y.-T. Chen, J. Cheng, and D.-S. Lee, "Multistage constructions of linear compressors, nonovertaking delay lines, and flexible delay lines," submitted to IEEE INFOCOM 2006.
• 3: C.-S. Chang, D.-S. Lee, and C.-K. Tu, "Using switched delay lines for exact emulation of FIFO multiplexers with variable length bursts," accepted by IEEE Journal on Selected Areas in Communications. Conference version in Proceedings of IEEE INFOCOM, 2003.
• 4: C.-S. Chang, D.-S. Lee, and C.-K. Tu, "Recursive construction of FIFO optical multiplexers with switched delay lines," IEEE Transactions on Information Theory, Vol. 50, pp. 3221--3233, 2004.
• 5: C.-C. Chou, C.-S. Chang, D.-S. Lee, and J. Cheng, "A construction of 2-to-1 optical FIFO multiplexers by a single crossbar switch and fiber delay lines," submitted to IEEE INFOCOM 2006.
• 6: Joseph Yu Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, Norwell, MA, 1990
• 7: Harry F. Jordan , Daeshik Lee , Kyungsook Y. Lee , Srinivasan V. Ramanan, Serial Array Time Slot Interchangers and Optical Implementations, IEEE Transactions on Computers, v.43 n.11, p.1309-1318, November 1994 [doi>10.1109/12.324563 ]
• 8: M. J. Karol, "Shared-memory optical packet (ATM) switch," SPIE Vol. 2024: Multigigabit Fiber Communication Systems(1993), pp. 212--222, 1993.
• 9: Shuo-Yen Robert Li, Algebraic switching theory and broadband applications, Academic Press, Inc., Orlando, FL, 2000
• 10: M. J. Marcus, "Designs for time slot interchangers," Proc. National Electronics Conf., Vol. 26, pp. 812--817, 1970.
• 11: Nicholas Pippenger, Juggling networks, Proceedings of the first Canada-France conference on Parallel and distributed computing, p.1-12, June 1994, Montreal, Canada
• 12: S. V. Ramanan, H. F. Jordan, and J. R. A. Sauer, "A new time domain, multistage permutation algorithm," IEEE Transactions on Information Theory, Vol. 36, No. 1, pp. 171--173, 1990.
• 13: A. D. Sarwate , V. Anantharam, Exact emulation of a priority queue with a switch and delay lines, Queueing Systems: Theory and Applications, v.53 n.3, p.115-125, July 2006 [doi>10.1007/s11134-006-6669-x]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory