2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Journal of Lightwave Technology
Volume 18 Number 4, April 2000

Table of Contents for this issue

Complete paper in PDF format

Packet Scheduling Algorithms and Performance of a Buffered Shufflenet with Deflection Routing

S.-H. Gary Chan, Member, IEEE and Hisashi Kobayashi Fellow, IEEE

Page 490.

Abstract:

In a multihop network, packets go through a number of hops before they are absorbed at their destinations. In routing to its destination using minimum path, a packet at a node may have a preferential output link (the so-called"care"packet) or may not (the so-called"don't care"packet). Since each node in an optical multihop network may have limited buffer, when such buffer runs out, contention among packets for the same output link can be resolved by deflection. In this paper, we study packet scheduling algorithms and their performance in a buffered regular network with deflection routing. Using shufflenet as an example, we show that high performance (in terms of throughput and delay) can be achieved if"care"packets can be scheduled with higher priority than"don't care"packets.We then analyze the performance of a shufflenet with this priority scheduling given the buffer size per node. Traditionally, the deflection probability of a packet at a node is solved from a transcendental equation by numerical methods which quickly becomes very cumbersome when the buffer size is greater than one packet per node. By exploiting the special topological properties of the shufflenet, we are able to simplify the analysis greatly and obtain a simple closed-form approximation of the deflection probability. The expression allows us to extract analytically the performance trend of the shufflenet with respect to its buffer and network sizes. We show that a shufflenet indeed performs very well with only one buffer, and can achieve performance close to the store-and-forward case using a buffer size as small as four packets per node.

References

  1. B. Y. Yu, I. Glesk and P. R. Prucnal, "Analysis of a dual-receiver node with high fault tolerance for ultrafast OTDM packet-switched shuffle networks", J. Lightwave Technol., vol. 16, pp.  736-744, May  1998.
  2. I. Chlamtac, A. Fumagalli and C.-J. Suh, "Switching multi-buffer delay lines for contention resolution in all-optical deflection networks", in Proc. 1996 GLOBECOM, London, U.K.,Nov. 1996, pp.  1624-1628. 
  3. I. Chlamtac and A. Fumagalli, "Quadro-star: A high performance optical WDM star network", IEEE Trans. Commun., vol. 42, pp.  2582-2591, Aug.  1994.
  4. A. Acampora, "A multichannel multihop local lightwave networks", in Proc. 1987 IEEE GLOBECOM, Nov. 1987, pp.  1459-1467. 
  5. M. Karol and R. Gitlin, "High-performance optical local and metropolitan area networks: Enhancement of FDDI and IEEE 802.6 DQDB", IEEE J. Select. Areas Commun., vol. 8, pp.  1439-1448, Oct.  1990.
  6. A. Acampora and M. Karol, "An overview of lightwave packet networks", IEEE Network, vol. 3, pp.  29-41, Jan.  1989.
  7. R. D. Gitlin and T. B. London, "Broadband Gigabit research and the LuckyNet testbed", J. High Speed Networks, vol. 1, no. 1, pp.  1-47, 1992.
  8. J. J. Yoo, J. E. Leight, C. Kim, G. Giaretta, W. Yuen, A. E. Willner and C. J. Chang-Hasnain, "Experimental demonstration of a multihop shuffle network using WDM multiple-plane optical interconnection with VCSEL and MQW/DBR detector arrays", IEEE Photon. Technol. Lett., vol. 10, pp.  1507-1509, Oct.  1998.
  9. F. Forghieri, A. Bononi and P. Prucnal, "Analysis and comparison of hot-potato and single-buffer deflection routing in very high bit rate optical mesh network", IEEE Trans. Commun., vol. 43, pp.  88-98, Jan.  1995.
  10. A. Bononi, G. A. Castañòn and O. K. Tonguz, "Analysis of hot-potato optical networks with wavelength conversion", J. Lightwave Technol., vol. 17, pp.  525-534, April  1999 .
  11. A. Bononi and P. R. Prucnal, "Analytical evaluation of improved access techniques in deflection routing networks", IEEE/ACM Trans. Networking, vol. 4, pp.  726-730, Oct.  1996.
  12. A. Acampora and S. Shah, "Multihop lightwave networks: A comparison of store-and-forward and hot-potato routing", IEEE Trans. Commun., vol. 40, pp.  1082-1090, June  1992.
  13. S.-H. G. Chan and H. Kobayashi, "Performance analysis of shufflenet with deflection routing", in Proc. 1993 IEEE GLOBECOM, TX, Dec. 1993, pp.  854-859. 
  14. A. Choudhury and V. Li, "An approximate analysis of the performance of deflection routing in regular networks", IEEE Journal on Selected Areas in Communications , vol. 11, pp.  1302-1316, October  1993.
  15. S.-H. G. Chan and H. Kobayashi, "Buffer architectures and routing algorithms in the performance of shufflenet", in Proc. 1993 IEEE SICON/ICIE, Singapore, Sept. 1993, pp.  34-38. 
  16. Z. Zhang and A. Acampora, "Performance analysis of multihop lightwave networks with hot potato routing and distance-age priorities", in Proc.IEEE INFOCOM, FL, April 1991, pp.  1012-1021. 
  17. L. Wang and K.-W. Hung, "Contention resolution in the loop-augmented shufflenet multihop lightwave network", in Proc. 1994 IEEE GLOBECOM, CA, Dec. 1994, pp.  186-190. 
  18. S. P. Monacos and A. A. Sawchuk, "A scalable recirculating shuffle network with deflection routing", in Proc.3rd Int. Conf. Massively Parallel Processing Using Optical Interconnections, HI, Oct. 1996, pp.  122-129. 
  19. S.-W. Seo, P. R. Prucnal and H. Kobayashi, "Generalized multihop shuffle networks", IEEE Trans. Commun., vol. 44, pp.  1205-1211, Sept.  1996.
  20. C.-L. Ng, S.-W. Seo and H. Kobayashi, "Performance analysis of generalized multihop shuffle networks", in Proc. INFOCOM'97, Kobe, Japan,April 1997, pp.  824-829. 
  21. P. Palnati, E. Leonardi and M. Gerla, "Bidirectional shufflenet: A multihop topology for backpressure flow control", in Proc. 4th Int. Conf. Comput. Commun. Networks, NV, Sept. 1995, pp.  74-81. 
  22. M. Gerla, E. Leonardi, F. Neri and P. Palnati, "Minimum distance routing in the bidirectional shufflenet", in Proc. IEEE INFOCOM'98, CA, Mar. 1998, pp.  102-109. 
  23. N. F. Maxemchuk, "Routing in the Manhattan street network", IEEE Trans. Commun., vol. 35, pp.  503-512, May  1987.
  24. N. F. Maxemchuk and R. Krishnam, "A comparison of linear and mesh topologies-DQDB and the Manhattan street network", IEEE J. Select. Areas Commun., vol. 11, pp.  1278-1289, Oct.  1993.
  25. A. G. Greenberg and J. Goodman, "Sharp approximation models of deflection routing in mesh networks", IEEE Trans. Commun., vol. 41, pp.  210-223, Jan.  1993.
  26. K. L. Yeung and T.-S. P. Yum, "Node placement optimization in shufflenets", IEEE/ACM Trans. Networking, vol. 6, pp.  319 -324, June  1998.
  27. S. Banerjee and B. Mukherjee, "Algorithms for optimized node arrangements in shufflenet based multihop lightwave networks", in Proc. IEEE INFOCOM'93 , CA, USA,Mar. 1993, pp.  557-564. 
  28. P. To, T.-S. P. Yum and Y.-W. Leung, "Multistar implementation of expandable shufflenets", IEEE/ACM Trans. Networking, vol. 2, pp.  345 -351, Aug.  1994.
  29. J. Iness, S. Banerjee and B. Mukherjee, "GEMNET: A generalized, shuffle-exchange-based, regular, scalable, modular, multihop, WDM lightwave network", IEEE/ACM Trans. Networking, vol. 3, pp.  470-476, Aug.  1995.
  30. G. B. Brewster and M. S. Borella, "Multicast routing algorithms for the WDM shufflenet local optical network", in Proc. IEEE ICC, P.Q., Canada,June 1997, pp.  111- 115. 
  31. S.-H. G. Chan and H. Kobayashi, "Asymptotic performance of a buffered shufflenet with deflection routing", in Proc. 1994 IEEE GLOBECOM, CA, Dec. 1994, pp.  1935-1942.