Abstract

A novel, to our knowledge, type of packet scheduler that could significantly outperform current state-of-the-art schedulers is presented. The operation and the design of such a scheduler are discussed, and a fully operational experimental implementation is described. The scheduler uses a neural network in a winner-take-all strategy to optimize decisions on the throughput of both a crossbar and a banyan switching fabric. The problems of high interconnection density are solved by use of a free-space optical interconnect that exploits diffractive optical techniques to generate the required interconnection patterns and weights.

© 2000 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
    [CrossRef]
  2. R. P. Webb, A. W. O’Neill, “Optoelectronic neural networks,” Br. Telecom Technol. J. 10, 144–154 (1992).
  3. R. P. Webb, “Optoelectronic implementation of neural networks,” Int. J. Neural Syst. 4, 435–444 (1993).
    [CrossRef] [PubMed]
  4. J. J. Hopfield, D. W. Tank, “Neural computation of decisions in optimization problems,” Biolog. Cyber. 52, 141–152 (1985).
  5. T. X. Brown, “Neural networks for switching,” IEEE Commun. Mag. 5(11), 72–81 (1989).
    [CrossRef]
  6. P. W. Protzel, D. L. Palumbo, M. K. Arras, “Performance and fault tolerance of neural networks for optimization,” IEEE Trans. Neural Net. 4, 600–614 (1993).
    [CrossRef]
  7. J. Ghosh, A. Hukkoo, A. Varma, “Neural networks for fast arbitration and switching noise reduction in large crossbars,” IEEE Trans. Circuits Syst. 38, 895–904 (1991).
    [CrossRef]
  8. A. Marrakchi, T. Troudet, “A neural net arbitrator for large crossbar packet switches,” IEEE Trans. Circuits Syst. 36, 1039–1041 (1989).
    [CrossRef]
  9. S. B. Aiyer, M. Niranjan, F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Net. 1, 204–215 (1990).
    [CrossRef]
  10. R. D. Brandt, Y. Wang, A. J. Laub, S. K. Mitra, “Alternative networks for solving the travelling salesman problem,” in Proceedings of the IEEE International Conference on Neural Networks (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 673–681.
  11. T. X. Brown, K. H. Liu, “Neural network design of a banyan network controller,” IEEE J. Select. Areas Commun. 8, 1428–1438 (1990).
    [CrossRef]
  12. R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.
  13. F. Wyrowski, “Iterative quantization of digital amplitude holograms,” Appl. Opt. 28, 3864–3870 (1989).
    [CrossRef] [PubMed]
  14. A. Vasara, M. R. Taghizadeh, J. Turunen, J. Westerholm, E. Noponen, H. Ichikawa, J. M. Miller, T. Jaakkola, S. Kuisma, “Binary surface-relief gratings for array illumination in digital optics,” Appl. Opt. 31, 3320–3336 (1992).
    [CrossRef] [PubMed]
  15. P. Blair, “Diffractive optical elements: design and fabrication issues,” Ph.D. dissertation (Department of Physics, Heriot-Watt University, 1995).
  16. N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
    [CrossRef]
  17. J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
    [CrossRef]
  18. M. P. Y. Desmulliez, B. S. Wherrett, A. J. Waddie, J. F. Snowdon, J. A. B. Dines, “Performance analysis of self-electro-optic effect device-based (SEED-based) smart-pixel arrays used in data sorting,” Appl. Opt. 35, 6397–6416 (1996).
    [CrossRef] [PubMed]

1998 (1)

J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
[CrossRef]

1997 (1)

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

1996 (1)

1993 (3)

T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
[CrossRef]

R. P. Webb, “Optoelectronic implementation of neural networks,” Int. J. Neural Syst. 4, 435–444 (1993).
[CrossRef] [PubMed]

P. W. Protzel, D. L. Palumbo, M. K. Arras, “Performance and fault tolerance of neural networks for optimization,” IEEE Trans. Neural Net. 4, 600–614 (1993).
[CrossRef]

1992 (2)

1991 (1)

J. Ghosh, A. Hukkoo, A. Varma, “Neural networks for fast arbitration and switching noise reduction in large crossbars,” IEEE Trans. Circuits Syst. 38, 895–904 (1991).
[CrossRef]

1990 (2)

S. B. Aiyer, M. Niranjan, F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Net. 1, 204–215 (1990).
[CrossRef]

T. X. Brown, K. H. Liu, “Neural network design of a banyan network controller,” IEEE J. Select. Areas Commun. 8, 1428–1438 (1990).
[CrossRef]

1989 (3)

F. Wyrowski, “Iterative quantization of digital amplitude holograms,” Appl. Opt. 28, 3864–3870 (1989).
[CrossRef] [PubMed]

A. Marrakchi, T. Troudet, “A neural net arbitrator for large crossbar packet switches,” IEEE Trans. Circuits Syst. 36, 1039–1041 (1989).
[CrossRef]

T. X. Brown, “Neural networks for switching,” IEEE Commun. Mag. 5(11), 72–81 (1989).
[CrossRef]

1985 (1)

J. J. Hopfield, D. W. Tank, “Neural computation of decisions in optimization problems,” Biolog. Cyber. 52, 141–152 (1985).

Aiyer, S. B.

S. B. Aiyer, M. Niranjan, F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Net. 1, 204–215 (1990).
[CrossRef]

Anderson, T.

T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
[CrossRef]

Arras, M. K.

P. W. Protzel, D. L. Palumbo, M. K. Arras, “Performance and fault tolerance of neural networks for optimization,” IEEE Trans. Neural Net. 4, 600–614 (1993).
[CrossRef]

Blair, P.

P. Blair, “Diffractive optical elements: design and fabrication issues,” Ph.D. dissertation (Department of Physics, Heriot-Watt University, 1995).

Brandt, R. D.

R. D. Brandt, Y. Wang, A. J. Laub, S. K. Mitra, “Alternative networks for solving the travelling salesman problem,” in Proceedings of the IEEE International Conference on Neural Networks (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 673–681.

Brown, T. X.

T. X. Brown, K. H. Liu, “Neural network design of a banyan network controller,” IEEE J. Select. Areas Commun. 8, 1428–1438 (1990).
[CrossRef]

T. X. Brown, “Neural networks for switching,” IEEE Commun. Mag. 5(11), 72–81 (1989).
[CrossRef]

Desmulliez, M. P. Y.

Dines, J. A. B.

Ellersick, W.

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

Fallside, F.

S. B. Aiyer, M. Niranjan, F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Net. 1, 204–215 (1990).
[CrossRef]

Ghosh, J.

J. Ghosh, A. Hukkoo, A. Varma, “Neural networks for fast arbitration and switching noise reduction in large crossbars,” IEEE Trans. Circuits Syst. 38, 895–904 (1991).
[CrossRef]

Gourlay, J.

J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
[CrossRef]

Hopfield, J. J.

J. J. Hopfield, D. W. Tank, “Neural computation of decisions in optimization problems,” Biolog. Cyber. 52, 141–152 (1985).

Horowitz, M.

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

Hukkoo, A.

J. Ghosh, A. Hukkoo, A. Varma, “Neural networks for fast arbitration and switching noise reduction in large crossbars,” IEEE Trans. Circuits Syst. 38, 895–904 (1991).
[CrossRef]

Ichikawa, H.

Izzard, M.

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

Jaakkola, T.

Kuisma, S.

Laub, A. J.

R. D. Brandt, Y. Wang, A. J. Laub, S. K. Mitra, “Alternative networks for solving the travelling salesman problem,” in Proceedings of the IEEE International Conference on Neural Networks (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 673–681.

Liu, K. H.

T. X. Brown, K. H. Liu, “Neural network design of a banyan network controller,” IEEE J. Select. Areas Commun. 8, 1428–1438 (1990).
[CrossRef]

Marrakchi, A.

A. Marrakchi, T. Troudet, “A neural net arbitrator for large crossbar packet switches,” IEEE Trans. Circuits Syst. 36, 1039–1041 (1989).
[CrossRef]

McKeown, N.

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

Mekkittikul, A.

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

Miller, J. M.

Mitra, S. K.

R. D. Brandt, Y. Wang, A. J. Laub, S. K. Mitra, “Alternative networks for solving the travelling salesman problem,” in Proceedings of the IEEE International Conference on Neural Networks (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 673–681.

Niranjan, M.

S. B. Aiyer, M. Niranjan, F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Net. 1, 204–215 (1990).
[CrossRef]

Noponen, E.

O’Neill, A. W.

R. P. Webb, A. W. O’Neill, “Optoelectronic neural networks,” Br. Telecom Technol. J. 10, 144–154 (1992).

Owicki, S.

T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
[CrossRef]

Palumbo, D. L.

P. W. Protzel, D. L. Palumbo, M. K. Arras, “Performance and fault tolerance of neural networks for optimization,” IEEE Trans. Neural Net. 4, 600–614 (1993).
[CrossRef]

Protzel, P. W.

P. W. Protzel, D. L. Palumbo, M. K. Arras, “Performance and fault tolerance of neural networks for optimization,” IEEE Trans. Neural Net. 4, 600–614 (1993).
[CrossRef]

Saxe, J.

T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
[CrossRef]

Snowdon, J. F.

J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
[CrossRef]

M. P. Y. Desmulliez, B. S. Wherrett, A. J. Waddie, J. F. Snowdon, J. A. B. Dines, “Performance analysis of self-electro-optic effect device-based (SEED-based) smart-pixel arrays used in data sorting,” Appl. Opt. 35, 6397–6416 (1996).
[CrossRef] [PubMed]

R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.

Symington, K. J.

R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.

Taghizadeh, M. R.

A. Vasara, M. R. Taghizadeh, J. Turunen, J. Westerholm, E. Noponen, H. Ichikawa, J. M. Miller, T. Jaakkola, S. Kuisma, “Binary surface-relief gratings for array illumination in digital optics,” Appl. Opt. 31, 3320–3336 (1992).
[CrossRef] [PubMed]

R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.

Tank, D. W.

J. J. Hopfield, D. W. Tank, “Neural computation of decisions in optimization problems,” Biolog. Cyber. 52, 141–152 (1985).

Thacker, C.

T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
[CrossRef]

Troudet, T.

A. Marrakchi, T. Troudet, “A neural net arbitrator for large crossbar packet switches,” IEEE Trans. Circuits Syst. 36, 1039–1041 (1989).
[CrossRef]

Turunen, J.

Varma, A.

J. Ghosh, A. Hukkoo, A. Varma, “Neural networks for fast arbitration and switching noise reduction in large crossbars,” IEEE Trans. Circuits Syst. 38, 895–904 (1991).
[CrossRef]

Vasara, A.

Waddie, A. J.

M. P. Y. Desmulliez, B. S. Wherrett, A. J. Waddie, J. F. Snowdon, J. A. B. Dines, “Performance analysis of self-electro-optic effect device-based (SEED-based) smart-pixel arrays used in data sorting,” Appl. Opt. 35, 6397–6416 (1996).
[CrossRef] [PubMed]

R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.

Walker, A. C.

J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
[CrossRef]

Wang, Y.

R. D. Brandt, Y. Wang, A. J. Laub, S. K. Mitra, “Alternative networks for solving the travelling salesman problem,” in Proceedings of the IEEE International Conference on Neural Networks (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 673–681.

Webb, R. P.

R. P. Webb, “Optoelectronic implementation of neural networks,” Int. J. Neural Syst. 4, 435–444 (1993).
[CrossRef] [PubMed]

R. P. Webb, A. W. O’Neill, “Optoelectronic neural networks,” Br. Telecom Technol. J. 10, 144–154 (1992).

R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.

Westerholm, J.

Wherrett, B. S.

Wyrowski, F.

Yang, T.

J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
[CrossRef]

ACM Trans. Comput. Syst. (1)

T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High speed switch scheduling systems for local area networks,” ACM Trans. Comput. Syst. 11, 319–352 (1993).
[CrossRef]

Appl. Opt. (3)

Biolog. Cyber. (1)

J. J. Hopfield, D. W. Tank, “Neural computation of decisions in optimization problems,” Biolog. Cyber. 52, 141–152 (1985).

Br. Telecom Technol. J. (1)

R. P. Webb, A. W. O’Neill, “Optoelectronic neural networks,” Br. Telecom Technol. J. 10, 144–154 (1992).

Computer (1)

J. Gourlay, T. Yang, J. A. B. Dines, J. F. Snowdon, A. C. Walker, “Development of free-space digital optics in computing,” Computer 31, 38–44 (1998).
[CrossRef]

IEEE Commun. Mag. (1)

T. X. Brown, “Neural networks for switching,” IEEE Commun. Mag. 5(11), 72–81 (1989).
[CrossRef]

IEEE J. Select. Areas Commun. (1)

T. X. Brown, K. H. Liu, “Neural network design of a banyan network controller,” IEEE J. Select. Areas Commun. 8, 1428–1438 (1990).
[CrossRef]

IEEE Micro. (1)

N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The tiny tera: a packet switch core,” IEEE Micro. 17, 26–33 (1997).
[CrossRef]

IEEE Trans. Circuits Syst. (2)

J. Ghosh, A. Hukkoo, A. Varma, “Neural networks for fast arbitration and switching noise reduction in large crossbars,” IEEE Trans. Circuits Syst. 38, 895–904 (1991).
[CrossRef]

A. Marrakchi, T. Troudet, “A neural net arbitrator for large crossbar packet switches,” IEEE Trans. Circuits Syst. 36, 1039–1041 (1989).
[CrossRef]

IEEE Trans. Neural Net. (2)

S. B. Aiyer, M. Niranjan, F. Fallside, “A theoretical investigation into the performance of the Hopfield model,” IEEE Trans. Neural Net. 1, 204–215 (1990).
[CrossRef]

P. W. Protzel, D. L. Palumbo, M. K. Arras, “Performance and fault tolerance of neural networks for optimization,” IEEE Trans. Neural Net. 4, 600–614 (1993).
[CrossRef]

Int. J. Neural Syst. (1)

R. P. Webb, “Optoelectronic implementation of neural networks,” Int. J. Neural Syst. 4, 435–444 (1993).
[CrossRef] [PubMed]

Other (3)

R. D. Brandt, Y. Wang, A. J. Laub, S. K. Mitra, “Alternative networks for solving the travelling salesman problem,” in Proceedings of the IEEE International Conference on Neural Networks (Institute of Electrical and Electronics Engineers, New York, 1998), pp. 673–681.

R. P. Webb, A. J. Waddie, K. J. Symington, M. R. Taghizadeh, J. F. Snowdon, “A neural network scheduler for packet switches,” in Digest of the Topical Meeting on Optics in Computing (Optical Society of America, Washington, D.C., 1999), pp. 422–426.

P. Blair, “Diffractive optical elements: design and fabrication issues,” Ph.D. dissertation (Department of Physics, Heriot-Watt University, 1995).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (11)

Fig. 1
Fig. 1

Schematic of the experimental neural-network crossbar-switch controller. On the basis of the connections requested by the incoming packets the neural network chooses an optimal solution, sets the appropriate crossbar switches (cross points), and then selects the packets chosen to pass through.

Fig. 2
Fig. 2

Schematic of a neural-network controller for a self-routing multistage banyan switch. Here the neural network selects an optimal packet solution and notifies the input buffers: It does not directly control the switching network.

Fig. 3
Fig. 3

(a) Electronic neuron block diagram: Each neuron can be broken down into a series of electronic components. This diagram indicates how a neuron is represented in a modular form. (b) Neural sigmoid response: The slope of a neuron’s activation function is highly dependent on β. This diagram shows how the slope changes by use of three sample values.

Fig. 4
Fig. 4

VCSEL’s that are used are highly sensitive to temperature variations. The VCSEL responses plotted for both high and low ambient temperatures illustrate just how drastic this variance is.

Fig. 5
Fig. 5

Schematic of the experimental optical system setup for the crossbar-switch controller. This diagram shows how the output from a single VCSEL is diffracted by the DOE and imaged onto the detector array.

Fig. 6
Fig. 6

(a) Image of an etched DOE phase profile created from (b) the theoretical phase profile.

Fig. 7
Fig. 7

Both the crossbar and the self-routing switches require different neural-network inhibitory patterns: (a) crossbar switch and (b) self-routing switch.

Fig. 8
Fig. 8

Actual time response of two neurons: One switches itself off, and the other switches itself on.

Fig. 9
Fig. 9

Crossbar-switch network convergence: Random-trial request sequences 1 through 6 were input into the neural network 10,000 times, and the number of neurons in the on state determined. A result with six neurons in the on state indicates an optimal solution; fewer neurons indicate that the network has failed to converge optimally.

Fig. 10
Fig. 10

Self-routing–switch network convergence: Random-trial request sequences 2 through 4 (as used in the crossbar switch) were input into the network 10,000 times, and the output was observed. Again, six neurons in the on state indicate an optimal solution.

Fig. 11
Fig. 11

Comparison of the neural-network controller with a state-of-the-art scheduler, ISLIP4. The advantage of the neural-network controller is clearly indicated at high levels of the offered load. The output-queuing curve indicates a theoretical optimum value.

Tables (1)

Tables Icon

Table 1 Nonuniformity and Efficiency of Crossbar and Self-Routing DOE’s

Equations (2)

Equations on this page are rendered with MathJax. Learn more.

dxidt=Ii-λixi- j=0N-1 wij yj+ti,
y(xi)=omin+omax-omin1+exp(βxi),

Metrics