Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-03-12
2001-03-27
Pham, Chi H. (Department: 2731)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S400000, C370S422000
Reexamination Certificate
active
06208644
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a network switch for routing network data transmissions between network stations, and in particular to a switch including a system for dynamically balancing loads over multiple output ports servicing the same set of network stations.
2. Description of Related Art
Networks transfer data between computers or other types of network stations. For example 10BASE-T Ethernet systems use sets of twisted pair conductors to connect network stations to a central hub or switch. A network switch includes input ports for receiving data packets from various network sources, output ports for forwarding packets to various network destinations and a switching mechanism such as a crosspoint switch for selectively routing each incoming packet from an input port to the appropriate output port. The network switch also includes an address translation system which relates a network destination address included in each incoming packet to an output port that can forward the packet to that network address. When an input port receives an incoming packet it stores the packet, reads its network destination address, consults the address translation system to determine which output port is to forward the packet, and then sends a routing request to the switch's arbitration system. When the arbitration system determines that the requested output port is idle it establishes a connection through the crosspoint switch between the requesting input port and the requested output port and then notifies the input port that it may begin sending the packet to the output port via the crosspoint switch.
A typical large network is often organized into clusters of stations with network stations of each cluster being linked to ports of a common network switch. Other ports of network switches serving the various clusters are then linked to one another. In such a network, a packet originating at a network station connected to one network switch may travel through that switch and possibly several others before reaching its destination station.
When there is a relatively large volume of traffic between two network switches, it is helpful to link several ports of the two switches to provide more than one path between them. Multiple links can be provided by separate transmission lines, each connecting an output port of one switch to an input port of another. Such links could also be provided by a high speed multiplexer/demultiplexer system connected to several input/output ports of each switch. A multiplexer at one end of a transmission line receives data packet transmissions concurrently from several output ports of one switch and multiplexes them onto the high speed transmission line. A demultiplexer at the opposite end of the transmission line separates the packets and routes them concurrently into separate input ports of another switch. The two switches, however, simply view the multiplexer/demultiplexer system as several separate paths.
In order to make efficient use of multiple paths between network switches we would like to distribute the transmission load evenly over those multiple paths. But load balancing has been problematic. Recall that a switch input port receiving a packet consults an address translation system to find out which switch output port is to receive the packet. Although the address translation system may assign many different network destination addresses to the same switch output port, it can assign each network address to one and only one output port. Thus, for example, when 10 output ports of a first switch are connected to 10 input ports of a second switch by 10 transmission lines, the first switch can forward an incoming data packet addressed to a network station connected to the second switch via only one of the 10 output ports. If that particular output port is busy, packet transmission is blocked and the input port has to store the packet until the particular output port is available, even if the other nine output ports linked to the second switch are idle.
In order to better distribute the loads on the 10 output ports, some prior art address translation system assigns an equal number of network addresses to each of the 10 output ports. But if the traffic to some network addresses is much higher than the traffic to others, the load will riot be balanced and system throughput will not be optimal. A network manager could manually adjust the manner in which the address translation system allocates network addresses to output ports to account for differences in traffic levels. However such manual load balancing is labor intensive and often ineffective when good traffic data is not available or when there are frequent changes in the amount of traffic to particular network addresses.
What is needed is a load balancing system for a network switch that is automatic, simple, inexpensive and effective.
SUMMARY OF THE INVENTION
A network switch in accordance with the present invention routes data transmission “packets” between network stations, each data packet including a network address of a source station sending the data transmission and the network address of a destination station to receive the data packet. The network switch includes a set of input/output ports for receiving the data packet from source stations and for selectively forwarding the data packets to destination stations. A crosspoint switch selectively routes data packets between the I/O ports.
In accordance with one aspect of the invention, each I/O port of the network switch is assigned both a “physical” port ID and a “logical” port ID. While each I/O port's physical port ID is unique, all I/O ports that communicate with the same set of network stations share the same logical port ID. When an I/O port receives an incoming packet it stores the packet and sends the network destination address to an address translation system. The address translation system then ascertains the logical port ID assigned to the set of I/O ports that can communicate with the destination station at that destination address. A switch arbitration system then looks for an idle I/O port having that logical port address that is not currently busy forwarding a data packet. On finding an idle I/O port, the switch arbitration system sends a switch controller the physical port ID of the port that received the packet from the source station and the physical port ID of the idle port that is to forward the packet to the destination station. The switch controller then establishes a data path through the crosspoint switch between the two I/O ports. Once the data path is established, the I/O port that received the packet sends the packet through the crosspoint switch to the I/O port that forwards the packet to the destination station.
Since the address translation system relates each network address to a logical output port ID rather than to a physical output port ID, a busy output port will not block packet transmission when there is an idle output port having the same logical ID, and traffic loads are dynamically balanced for optimum throughput.
It is accordingly an object of the present invention to provide a switch which automatically balances traffic though output ports connected to the same network destination.
The concluding portion of this specification particularly points out and distinctly claims the subject matter of the present invention. However those skilled in the art will best understand both the organization and method of operation of the invention, together with further advantages and objects thereof, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.
REFERENCES:
patent: 5412648 (1995-05-01), Fan
patent: 5689644 (1997-11-01), Chou et al.
patent: 5754791 (1998-05-01), Dahlgren et al.
Hemming Robert Donald
Pannell Donald Robert
Bedell Daniel J.
I-Cube, Inc.
Pham Chi H.
Smith-Hill and Bedell
Tran Maikhanh
LandOfFree
Network switch providing dynamic load balancing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network switch providing dynamic load balancing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switch providing dynamic load balancing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453446