Abstract

Monarchic Reconfiguration protocol (MRP) is the self- governing, independent and autonomous system to resolve the deadlocking problem during reconfiguration in interconnection networks. Deadlock is the cyclic dependency between the old and new routing functions. Our aim is to protect the routing path with deadlocking freedom and improve the performance drastically. Our proposed method will increase the availability and dependability of the network and reduce 100 % pocket drops ratio with deadlock freedom.

References

• K. Malavalli, et al. Fibre Channel Switch Fabric-2 (FC-SW-2). NCITS 321- 200x T11/Project 1305-D/Rev 4. 3 Specification, pages 57_74, March 2000.
• F. Petrini, W. C. Feng, A. Hoisie, S. Coll, and E. Frachtenberg. The Quadrics Network: High-Performance Clustering Technology. IEEE Micro, 22(1):2_ 13, January-February 2002.
• T. M. Pinkston, A. F. Benner, M. Krause, I. M. Robinson, and T. Sterling. Infini Band: The "De Facto" Future Standard for System and Local Area Networks or Just a Scalable Replacement for PCI Buses? Cluster Computing, 6(2):95_104, April 2003.
• W. Dally and B. Towles. Route Packets, NotWires: On-Chip Interconnection Networks. In Proceedings of the Design Automation Conference (DAC), pages 684_689. ACM, June 2001.
• M. B. Taylor, W. Lee, S. Amarasinghe, and A. Agarwal. Scalar Operand Networks: On-Chip Interconnect for ILP in Partitioned Architectures. In Proceedings of the 9th International Symposium on High-Performance Computer Architecture, pages 341_353. IEEE Computer Society Press, February 2003.
• W. H. Ho and T. M. Pinkston. A Methodology for Designing Efficient On-Chip Interconnects on Well-Behaved Communication Patterns. In Proceedings of the 9th International Symposium on High-Performance Computer Architecture, pages 377_388. IEEE Computer Society Press, February 2003.
• E. Baydal, P. Lopez, and J. Duato. A Simple and Efficient Mechanism to Prevent Saturation in Wormhole Networks. In Proceedings of the 14th International Parallel and Distributed Processing Symposium, pages 617_622, 2000.
• M. Thottethodi, A. R. Lebeck, and S. S. Mukherjee. Self-Tuned Congestion Control for Multiprocessor Networks. In Proceedings of the 7th International Symposium on High Performance Computer Architecture, January 2001.
• L. -S. Peh and W. Dally. Flit-Reservation Flow Control. In Proceedings of the 6th International Symposium on High Performance Computer Architecture, pages 73_84. IEEE Computer Society Press, January 2000.
• J. Duato. A New Theory of Deadlock-free Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems, 4(12):1320_1331, December 1993.
• J. Duato. A Necessary and Sufficient Condition for Deadlock-free Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems, 6(10):1055_1067, October 1995.
• J. Duato and T. M. Pinkston. A General Theory for Deadlock-Free Adaptive Routing Using a Mixed Set of Resources. IEEE Transactions on Parallel and Distributed Systems, 12(12):1219_1235, December 2001.
• S. Warnakulasuriya and T. M. Pinkston. A Formal Model of Message Blocking and Deadlock Resolution in Interconnection Networks. IEEE Transactions on Parallel and Distributed Systems, 11(2):212_229, March 2000.
• S. Warnakulasuriya and T. M. Pinkston. Characterization of Deadlocks in k-ary n-cube Networks. IEEE Transactions on Parallel and Distributed Systems, 10(9):904_921, September 1999.
• S. Warnakulasuriya and T. M. Pinkston. Characterization of Deadlocks in Irregular networks. Journal of Parallel and Distributed Computing, 62(1):61_ 84, January 2002.
• T. M. Pinkston, R. Pang, and J. Duato. Deadlock-Free Dynamic Reconfiguration Schemes for Increased Network Dependability. IEEE Transactions on Parallel and Distributed Systems, 14(8):780_794, August 2003.
• V. Puente, R. Beivide, J. A. Gregorio, J. M. Prellezo, J. Duato, and C. Izu. Adaptive bubble router: A design to improve performance in torus networks. In Proceedings of the 28th International Conference on Parallel Process- ing (28th ICPP'99), Aizu-Wakamatsu, Fukushima, Japan, September 1999. University of Aizu.
• J. M. Martinez, P. Lopez, and J. Duato. FC3D: Flow Control Based Distributed Deadlock Detection Mechanism for True Fully Adaptive Routing in Wormhole Networks. IEEE Transactions on Parallel and Distributed Systems, 14(8):765_779, August 2003.
• S. S. Mukherjee, P. Bannon, S. Lang, A. Spink, and D. Webb. The Alpha 21364 Network Architecture. In Symposium on High Performance Interconnects (HOT Interconnects 9), pages 113_117. IEEE Computer Society Press, August 2001.
• W. Barrett et al. An Overview of the Blue-Gene/L Supercomputer. In Proceedings of the 2002 ACM/IEEE Conference on Supercomputing, CD ROM, November 2002.
• J. Flich, P. Lopez, M. P. Malumbres, and J. Duato. Boosting the Performance of Myrinet Networks. IEEE Transactions on Parallel and Distributed Systems, 13(7):693_709, July 2002.
• Y. H. Song and T. M. Pinkston. A New Mechanism for Congestion and Deadlock Resolution. In The 2002 International Conference on Parallel Processing, pages 81_90. IEEE Computer Society, August 2002.
• C. B. Stunkel et al. The SP2 high-performance switch. IBM Systems Journal, 34(2):185_204, 1995.
• J. F. Martinez, J. Torrellas, and J. Duato. Improving the Performance of Bristled CC-NUMA Systems Using Virtual Channels and Adaptivity. In Proceedings of 13th International Conference on Supercomputing, June 1999.
• Y. H. Song and T. M. Pinkston. A Progressive Approach to Handling Message-Dependent Deadlock in Parallel Computer Systems. IEEE Transactions on Parallel and Distributed Systems, 14(3):259_275, March 2003.
• Infini Band TM Architecture Specification Volume 1. Infini Band Trade Association, October 24, 2000.
• O. Lysne and J. Duato. Fast Dynamic Reconfiguration in Irregular Networks. In The 2000 International Conference on Parallel Processing, pages 449_458. IEEE Computer Society, August 2000.
• F. J. Quiles, J. L. Sanchez, R. Casado, A. Bermudez and J. Duato. A protocol for deadlock-free dynamic reconfiguration in high-speed local area networks. Special Issue on Dependable Network Computing. IEEE Transactions on Parallel and Distributed Systems, 12(2):115_132, February 2001.
• R. Pang, T. M. Pinkston and J. Duato. Dynamic Reconfiguration of Networks with Distributed Routing: The Single Scheme. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), pages 2042_2048, June 2001.
• Antonio Robles-Gomez, Aurelio Bermudez, and Rafael Casado, A deadlock-free dynamic reconfiguration scheme for source routing networks using close up*/down* graphs , IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 10, October 2011.
• Olav Lysne, Jose Miguel Montanana, Jose Flich, Jose Duato, Timothy Mark Pinkston and Tor Skeie, "An Efficient and Deadlock Free Network Reconfiguration Protocol", IEEE Transactions on Computers, vol. 57, No. 6, June 2008.
• Dong Xiang, Yueli Zhang and Yi Pan, "Practical Deadlock Free Fault Tolerant Routing in Meshes Based on the Planar Network Fault Model", IEEE Transactions on Computers, vol. 58, No. 6, May 2008.
• Jian Qiu, Mohan Gurusamy,, Kee Chaing Chua, and Yong Liu," Local Restoration with Multiple Spanning Trees in Metro Ethernet Networks", IEEE/ACM Transaction on networking,vol. 19,No. 2, April 2011.