Abstract

A load balancing circuit arrangement for use with a packet switching node. The packet switching node processes applied data packets containing routing tag signals indicative of the output port destinations to which the data packets are addressed, and routes these packets to the identified output ports. The present invention a load balancing circuit coupled to the packet switching node which monitors the output port addresses of the applied data packets and monitors the number of data packets addressed to each of the output ports. The load balancing circuit is adapted to generate new routing tag signals identifying output port addresses which redistribute the output port load. The load balancing circuit arrangement includes a tag selection circuit coupled to the load balancing circuit and the packet switching node which selectively replaces the routing tag signals of the applied data packets with the new routing tage signals in order to redistribute and balance the output port load. The load balancing circuit comprises a minimum index circuit for generating the new routing tag signals and an adder circuit coupled thereto. The minimum index circuit combines the new routing tag signals with offset signals that modify the new routing tag signals in order to implement a predetermined output port priority scheme. The load balancing circuit arrangement may be employed in both multiple queue and multiport memory packet switching nodes employed in computer or telephone communications applications.

Other References

• Herzog: Message-Switching Networks with Alternate Routing, Jun. 13-20, 1973, pp. 415/1-415/8, Proceedings of the International Teletraffic Congress, Stockholm, Proc. 7, Part 2, Swedish Communications 1973 (Stockholm, Sweden)
• Parker et al: The Gamma Network: A Multiprocessor Interconnection Network with Redundant Paths, pp. 73-80, Conference Proceedings: the 9th Annual Symposium on Computer Architecture, Apr. 26-29, 1982, Austin, Texas
• Switching Strategies in a Class of Packet Switching Networks, M. Kumar et al; The 10th Annual International Symposium on Computer Architecture 1983, Stockholm, Sweden; pp. 284-300
• The Hybrid Cube Network, R. J. McMillen et al; Distributed Data Acquisition, Computing & Control Symposium; Dec. 1980; pp. 11-22
• P. N. Jean, S. C. Crist, M. Arozullah, "Multi-Microprocessor Based Architecture for a Space Borne Packet Switch", pp. 139-141; COMCON 80, Feb. 25-28, 1980, 20th Computer Society International Conference (San Francisco, Calif.)
• L. Ciminiera and A. Serra, "LSI Implementation of Modular Interconnection Networks for MIMD Machines", 1980 Int'l. Conf. Parallel Processing, Aug. 1980, pp. 161-162
• D. M. Dias and J. R. Jump, "Analysis and Simulation of Buffered Delta Networks", IEEE Trans. Computers, vol. C-30, pp. 273-282, Apr. 1981
• A. C. Hung and M. Malek, "A 4×4 Modular Crossbar Design for the Multistage Interconnection Networks", Real-Time Systems Symp., Dec. 1981, pp. 3-12
• J. H. Patel, "Processor-Memory Interconnections for Multiprocessors", 6th Annual Int'l. Symp. Computer Architecture, Apr. 1979, pp. 168-177
• U. V. Premkumar, R. Kapur, M. Malek, G. J. Lipovski and P. Horne, "Design and Implementation of the Banyan Interconnection Network in TRAC", AFIPS 1980 Nat'l. Computer Conf., Jun. 1980, pp. 643-653
• H. J. Siegel and R. J. McMillen, "The Multistage Cube: A Versatile Interconnection Network", Computer, vol 14, pp. 65-76, Dec. 1981
• R. J. McMillen, G. B. Adams III, and H. J. Siegel, "Performance and Implementation of 4×4 Switching Nodes in an Interconnection Network for PASM", 1981 Int'l Conf. on Parallel Processing, Aug. 1981, pp. 229-233
• R. J. McMillen and H. J. Siegel, "The Hybrid Cube Network", Distributed Data Acquisition, Computing and Control Symp., Dec. 1980, pp. 11-22, (FIG. VI.2, p. 19)
• "B. J. Smith, "Architecture and Applications of the HEP Multiprocessor Computer System", SPIE, vol. 298, Section on Real-Time Signal Processing IV, Aug. 1981, pp. 241, 248