skip to main content
article

Minimizing internal speedup for performance guaranteed switches with optical fabrics

Published: 01 April 2009 Publication History

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 N2 - 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 (N2 - 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]
B. Towles and W. J. Dally, "Guaranteed scheduling for switches with configuration overhead," IEEE/ACM Trans. Networking, vol. 11, no. 5, pp. 835-847, Oct. 2003.
[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]
E. Altman, Z. Liu, and R. Righter, "Scheduling of an input-queued switch to achieve maximal throughput," Probabil. Eng. Inform. Sci., vol. 14, pp. 327-334, 2000.
[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.

Cited By

View all
  • (2018)A Parallel Complex Coloring Algorithm for Scheduling of Input-Queued SwitchesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.280252329:7(1456-1468)Online publication date: 1-Jul-2018
  • (2016)Resource Management for Optical Interconnects in Data Centre Networks2016 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2016.7842226(1-7)Online publication date: 4-Dec-2016
  • (2015)Switch cost and packet delay tradeoff in data center networks with switch reconfiguration overheadComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.05.01087:C(33-43)Online publication date: 20-Jul-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 17, Issue 2
April 2009
319 pages

Publisher

IEEE Press

Publication History

Published: 01 April 2009
Revised: 10 August 2007
Received: 07 November 2006
Published in TON Volume 17, Issue 2

Author Tags

  1. optical switch fabric
  2. performance guaranteed switching
  3. reconfiguration overhead
  4. scheduling
  5. speedup

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2018)A Parallel Complex Coloring Algorithm for Scheduling of Input-Queued SwitchesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.280252329:7(1456-1468)Online publication date: 1-Jul-2018
  • (2016)Resource Management for Optical Interconnects in Data Centre Networks2016 IEEE Global Communications Conference (GLOBECOM)10.1109/GLOCOM.2016.7842226(1-7)Online publication date: 4-Dec-2016
  • (2015)Switch cost and packet delay tradeoff in data center networks with switch reconfiguration overheadComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.05.01087:C(33-43)Online publication date: 20-Jul-2015
  • (2011)An analytical model for input-buffered optical packet switches with reconfiguration overheadPhotonic Network Communications10.1007/s11107-011-0320-422:3(209-220)Online publication date: 1-Dec-2011
  • (2010)Feedback-based scheduling for load-balanced two-stage switchesIEEE/ACM Transactions on Networking10.1109/TNET.2009.203731818:4(1077-1090)Online publication date: 1-Aug-2010

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media