Load balancing for packet switching nodes

• US 4,621,359 A
• Filed: 10/18/1984
• Issued: 11/04/1986
• Est. Priority Date: 10/18/1984
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Original Assignee: Hughes Aircraft Company (Rtx Corporation)
• Inventors: McMillen, Robert J.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US06/661,995
• Time in Patent Office: 747 Days
• Field of Search: 370/60, 370/58, 370/94, 370/61, 340/825.5, 340/825.51
• US Class Current: 370/235
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane

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.

Claims

1. A load balancing circuit arrangement for use with a packet switching node that processes applied data packets that contain routing tag signals indicative of the output port destinations to which said data packets are addressed, wherein said load balancing arrangement comprises:

load balancing means coupled to said packet switching node for monitoring the output port addresses of said applied data packets and the number of data packets addressed to each of said output ports, and for generating new routing tag signals identifying output port addresses which are adapted to redistribute the output port load; and

tag selection means coupled to said load balancing means and said packet switching node for selectively replacing the routing tag signals of said applied data packets with said new routing tag signals in order to redistribute and balance the output port load.

2. The load balancing circuit arrangement of claim 1 wherein:

said load balancing means comprises a logic circuit which monitors the output port addresses of said applied data packets and the number of data packets addressed to each of said output ports, and generates said new routing tag signals; and

said tag selection means comprises a logic circuit for selectively applying said new routing tag signals to said switching node in response to enabling signals applied thereto.

3. The load balancing circuit arrangement of claim 2 wherein said load balancing means comprises:

a minimum index circuit for generating said new routing tag signals; and

an adder circuit coupled to said minimum index circuit for combining said new routing tag signals with offset signals which modify said new routing tag signals in order to implement a predetermined output port priority scheme.

4. A load balancing circuit arrangement for use with a switching node that processes applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are addressed, and wherein said switching node comprises a multiport memory and control logic coupled thereto for routing applied data packets in accordance with the output port destination thereof, wherein said load balancing circuit arrangement comprises:

load balancing means coupled to said control logic for monitoring the output port addresses of said applied data packets and the number of data packets addressed to each of said output ports, and for generating new routing tag signals identifying output port addresses which are adapted to redistribute the output port load; and

tag selection means coupled to said load balancing means and said control logic for selectively replacing the routing tag signals of said applied data packets with said new routing tag signals in order to redistribute and balance the output port load.

5. The load balancing circuit arrangement of claim 4 wherein:

said load balancing means comprises a logic circuit which monitors the output port addresses of said applied data packets and the number of data packets addressed to each of said output ports, and generates said new routing tag signals; and

said tag selection means comprises a logic circuit for selectively applying said new routing tag signals to said switching node in response to enabling signals applied thereto.

6. The load balancing arrangement of claim 5 wherein said load balancing means comprises:

a minimum index circuit for generating said new routing tag signals; and

an adder circuit coupled to said mimimum index circuit for combining said new routing tag signals with offset signals which modify said new routing tag signals in order to implement a predetermined output port priority scheme.

7. A load balancing circuit arrangement for use with a packet switching node that processes applied data packets containing routing tag signals indicative of the output port destinations to which said data packets are addressed, and wherein said switching node comprises queue selection logic coupled to a plurality of queues for routing applied data packets in accordance with the output port destination thereof, wherein said load balancing circuit arrangement comprises:

load balancing means coupled to said plurality of queues for monitoring the number of data packets addressed to each of said output ports, and for generating new routing tag signals identifying output port addresses which are adapted to redistribute the output port load; and

tag selection means coupled to said load balancing means and said queue selection logic for selectively replacing the routing tag signals of said applied data packets with said new routing tag signals in order to redistribute and balance the output port load.

8. The load balancing circuit arrangement of claim 7 wherein:

said load balancing means comprises a logic circuit which monitors the output port addresses of said applied data packets and the number of data packets addressed to each of said output ports, and generates said new routing tag signals; and

said tag selection means comprises a logic circuit for selectively applying said new routing tag signals to said switching node in response to enabling signals applied thereto.

9. The load balancing circuit arrangement of claim 8 wherein said load balancing means comprises:

a minimum index circuit for generating said new routing tag signals; and

an adder circuit coupled to said minimum index circuit for combining said new routing tag signals with offset signals which modify said new routing tag signals in order to implement a predetermined output port priority scheme.