Minimizing internal speedup for performance guaranteed switches with optical fabrics

ABSTRACT

We consider traffic scheduling in an N × N packet switch with an optical switch fabric, where the fabric requires a reconfiguration overhead to change its switch configurations. To provide 100% throughput with bounded packet delay, a speedup in the switch fabric is necessary to compensate for both the reconfiguration overhead and the inefficiency of the scheduling algorithm. In order to reduce the implementation cost of the switch, we aim at minimizing the required speedup for a given packet delay bound. Conventional Birkhoff-von Neumann traffic matrix decomposition requires N² - 2N + 2 configurations in the schedule, which lead to a very large packet delay bound. The existing DOUBLE algorithm requires a fixed number of only 2N configurations, but it cannot adjust its schedule according to different switch parameters. In this paper, we first design a generic approach to decompose a traffic matrix into an arbitrary number of Ns (N² - 2N + 2 > Ns > N configurations. Then, by taking the reconfiguration overhead into account, we formulate a speedup function. Minimizing the speedup function results in an efficient scheduling algorithm ADAPT. We further observe that the algorithmic efficiency of ADAPT can be improved by better utilizing the switch bandwidth. This leads to a more efficient algorithm SRF (Scheduling Residue First). ADAPT and SRF can automatically adjust the number of configurations in a schedule according to different switch parameters. We show that both algorithms outperform the existing DOUBLE algorithm.

REFERENCES

• 1: J. E. Fouquet et al., "A compact, scalable cross-connect switch using total internal reflection due to thermally-generated bubbles," in IEEE LEOS Annual Meeting, Dec. 1998, pp. 169-170.
• 2: L. Y. Lin, "Micromachined free-space matrix switches with sub-millisecond switching time for large-scale optical crossconnect," in OFC'98 Tech. Dig., Feb. 1998, pp. 147-148.
• 3: O. B. Spahn, C. Sullivan, J. Burkhart, C. Tigges, and E. Garcia, "GaAs-based microelectromechanical waveguide switch," in Proc. 2000 IEEE/ LEOS Intl. Conf. Optical MEMS, Aug. 2000, pp. 41-42.
• 4: A. J. Agranat, "Electroholographic wavelength selective crossconnect," in 1999 Dig. LEOS Summer Topical Meetings, Jul. 1999, pp. 61-62.
• 5: K. Kar, D. Stiliadis, T. V. Lakshman, and L. Tassiulas, "Scheduling algorithms for optical packet fabrics," IEEE J. Sel. Areas Commun., vol. 21, no. 7, pp. 1143-1155, Sep. 2003.
• 6: Brian Towles , William J. Dally, Guaranteed scheduling for switches with configuration overhead, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.835-847, October 2003 [doi>10.1109/TNET.2003.818190]
• 7: X. Li and M. Hamdi, "On scheduling optical packet switches with reconfiguration delay," IEEE Journal on Selected Areas in Communications , vol. 21, no. 7, pp. 1156-1164, Sept. 2003.
• 8: B. Wu and K. L. Yeung, "Traffic scheduling in non-blocking optical packet switches with minimum delay," in Proc. IEEE GLOBECOM'05, Dec. 2005, vol. 4, pp. 2041-2045.
• 9: B. Wu and K. L. Yeung, "Minimum delay scheduling in scalable hybrid electronic/optical packet switches," in Proc. IEEE GLOBECOM'06, Dec. 2006.
• 10: B. Wu, X. Wang, and K. L. Yeung, "Can we schedule traffic more efficiently in optical packet switches?," in Proc. IEEE HPSR'06, Jun. 2006, pp. 181-186.
• 11: S. T. Chuang, A. Goel, N. McKeown, and B. Prabhakar, "Matching output queuing with a combined input output queued switch," in Proc. IEEE INFOCOM'99, Mar. 1999, vol. 3, pp. 1169-1178.
• 12: G. Birkhoff, "Tres observaciones sobre el algebra lineal," Univ. Nac. Tucumán Rev. Ser. A, vol. 5, pp. 147-151, 1946.
• 13: J. von Neumann, "A certain zero-sum two-person game equivalent to the optimal assignment problem," in Contributions to the Theory of Games. Princeton, NJ: Princeton Univ. Press, 1953, vol. 2, pp. 5-12.
• 14: C. S. Chang, W. J. Chen, and H. Y. Huang, "Birkhoff-von Neumann input buffered crossbar switches," in Proc. IEEE INFOCOM'00, Mar. 2000, vol. 3, pp. 1614-1623.
• 15: J. Li and N. Ansari, "Enhanced Birkhoff-von Neumann decomposition algorithm for input queued switches," IEE Proc.-Commun., vol. 148, no. 6, pp. 339-342, Dec. 2001.
• 16: T. Inukai, "An efficient SS/TDMA time slot assignment algorithm," IEEE Trans. Commun., vol. COM-27, no. 10, pp. 1449-1455, 1979.
• 17: Y. Ito, Y. Urano, T. Muratani, and M. Yamaguchi, "Analysis of a switch matrix for an SS/TDMA system," Proc. IEEE, vol. 65, no. 3, pp. 411-419, Mar. 1977.
• 18: K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, "Scheduling bursts in time-domain wavelength interleaved networks," IEEE J. Sel. Areas Commun., vol. 21, no. 9, pp. 1441-1451, Nov. 2003.
• 19: H. Liu, P. Wan, C.-W. Yi, X. H. Jia, S. Makki, and N. Pissinou, "Maximal lifetime scheduling in sensor surveillance networks," in Proc. IEEE INFOCOM'05, Mar. 2005, vol. 4, pp. 2482-2491.
• 20: R. Cole and J. Hopcroft, "On edge coloring bipartite graphs," SIAM J. Comput., vol. 11, pp. 540-546, Aug. 1982.
• 21: R. Diestel, Graph Theory, 2nd ed. New York: Springer-Verlag, 2000.
• 22: S. Gopal and C. K. Wong, "Minimizing the number of switchings in a SS/TDMA system," IEEE Trans. Commun., vol. COM-33, pp. 497-501, Jun. 1985.
• 23: R. L. Graham, "Bounds on multiprocessing timing anomalies," SIAM J. Appl. Mathemat., vol. 17, no. 2, pp. 416-429, Mar. 1969.
• 24: Eitan Altman , Zhen Liu , Rhonda Righter, SCHEDULING OF AN INPUT-QUEUED SWITCH TO ACHIEVE MAXIMAL THROUGHPUT, Probability in the Engineering and Informational Sciences, v.14 n.3, p.327-334, July 2000 [doi>10.1017/S0269964800143049]
• 25: J. E. Hopcroft and R. M. Karp, "An n^5/2 algorithm for maximum matching in bipartite graphs," Soc. Ind. Appl. Math. J. Comput., vol. 2, pp. 225-231, 1973.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM); Access schemes
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Design, Performance

Keywords:
optical switch fabric, performance guaranteed switching, reconfiguration overhead, scheduling, speedup