Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-12-02
2002-10-29
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000, C370S412000, C370S418000, C709S241000, C709S241000, C709S241000
Reexamination Certificate
active
06473424
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to computer networking. More specifically, the present invention relates to methods and apparatuses for distributing frame transmissions as evenly as possible across a group of ports which are logically grouped into a single port.
A common computer network implementation includes a plurality of clients, such as personal computers or work stations, connected to each other and one or more servers via a switch or router by network cable. In the present application, the term “switch” is intended to mean any network device that forwards packets from a source to a destination, rather than broadcasting them (i.e., includes router, but excludes repeater). The network is configured to operate at one or more data transmission rates, typically 10 Mbit/sec (e.g., 10Base-T Ethernet), or 100 Mbit/sec (e.g., 100Base-T Fast Ethernet). More recently, Gigabit data transmission rates have become attainable. Data is forwarded on the network in packets which are typically received by a switch from a source network device and then directed to the appropriate destination device. The receipt and transmission of data packets by a switch occurs via ports on the switch. Packets travelling from the same source to the same destination are defined as members of the same stream.
Since network switches typically receive data from and transmit data to several network devices, and the cable connections between the various network devices typically transmit data at the same rate, a bottle-neck may be created when, for example, several devices (e.g., clients) are simultaneously attempting to send data to a single other device (e.g., a server). In this situation, the data packets must sit in a queue at the port for the server and wait for their turn to be forwarded from the switch to the server.
One way to relieve this bottle-neck is to provide a logical grouping of multiple ports into a single port. The bandwidth of the new port is increased since it has multiple lines (cables) connecting a switch and another network device, each line capable of carrying data at the same rate as the line connecting data sources to the switch. This grouping of ports is sometimes referred to as a port aggregation or port group. One example of such a port aggregation implementation is Cisco Technology, Inc.'s Fast EtherChannel™ port group in a Fast Ethernet network. Further information regarding Fast EtherChannel™ may be found on Cisco Technology, Inc.'s World Wide Web site www.cisco.com. This information is incorporated by reference herein for all purposes.
In order for networking equipment to make optimal utilization of the increased bandwidth provided by a port group, packet transmissions must be distributed as evenly as possible across the ports of the group. In addition, a suitable distribution system will ensure that packets in the same stream are not forwarded out of order.
Traffic distribution for ports grouped in port groups has conventionally been accomplished by static distribution of addresses across the ports of a group. In one example of such a static distribution of network traffic, as a packet of data to be forwarded is received by a switch, its destination address is determined, and it is assigned to the port group connecting with its destination. Assignment to a port within the port group may be done in a number of ways. For example, each packet assigned to the port group may be assigned to the next port in a cycle through the ports, or the assignment may be based on the packet's source address. However it is done, this assignment is permanent, so that if a second packet with the same address is subsequently received by the switch, it is assigned to the same port assigned to the previous packet with that address. The one exception to this permanent assignment in conventional systems may be the removal of an address due to aging, that is, if a long enough period of time (e.g., 10 to 1,000,000 seconds, typically 300 seconds) passes between the receipt of two packets of data having the same address, the second packet may be assigned to a different port. Another static address distribution system performs a simple logical operation on a packet's source and destination addresses (exclusive OR of the two least significant bits of the addresses) in order to identify the port within a group to be used to transmit a packet.
Static address distribution systems ensure that packets from a given stream are not forwarded out of order by permanently assigning the stream to a particular port. In this way, packets in a stream can never be forwarded to their destination by the switch out of order. For example, an earlier packet in the stream may not be forwarded by the switch before a later one via a different less-busy port in the group since all packets from that stream will always be forwarded on the same port in the group.
While static address distribution improves the efficiency of data transmission over a port group by distributing packet streams among the various ports of a port group, it does not account for the amount of traffic volume of different streams. Accordingly, static address distribution evenly (and thus most efficiently) distributes traffic over the ports of a port group of a switch only if there is the same amount of data being forwarded in each stream. If a given stream is transmitting much more than the average amount of data for streams being forwarded through the port group, then there may be inefficiencies in the data transmission in a static address distribution system. For example, this situation may result in there being a long queue for the port to which the heavily loaded stream is assigned, while other ports in the group, which are assigned to more lightly loaded streams, are available to transmit data.
Accordingly, what is needed is an improved distribution system for network port groups that satisfies the port groups' distribution and packet ordering requirements, while taking into consideration the amount of data being forwarded in a given stream.
SUMMARY OF THE INVENTION
The present invention meets this need by providing methods, apparatuses and systems for balancing the load of data transmissions through a port aggregation. The methods, apparatuses and systems of the present invention allocate port assignments based on load, that is, the amount of data being forwarded through each port in the group. The load balancing of the present invention is preferably dynamic, that is, packets from a given stream may be forwarded on different ports depending upon each port's current utilization. When a new port is selected to transmit a particular packet stream, it is done so that the packets cannot be forwarded out of order. This is preferably accomplished by ensuring passage of a period of time sufficient to allow all packets of a given stream to be forwarded by a port before a different port is allocated to transmit packets of the same stream. The invention may be used in a variety of different network environments and speeds, including 10Base-T, 100Base-T, and Gigabit Ethernet, and other network environments.
In one aspect, the present invention provides a method of distributing traffic over a network port group. The method involves receiving a packet of data to be forwarded, determining a stream ID for the packet, and determining whether a prior packet having that stream ID has been distributed to a queue on a port in the group during a predetermined time interval. Where a prior packet having that stream ID has not been distributed to a queue on a port of the group during the predetermined time interval, the method involves allocating the packet to a queue of a port having a lesser load in its queue than a queue of any other port of the group. The method may also involve, where a prior packet having that stream ID has been distributed to a queue on a port of the group during the predetermined time interval, allocating the packet to that queue. In addition, the method may involve monitoring the port group
DeJager Gregory L.
Emery Scott A.
Findlater Stewart
Rivers James R.
Yen David H.
Austin James E.
Beyer,Weaver & Thomas, LLP
Cisco Technology Inc.
Hsu Alpus H.
Qureshi Afsar M.
LandOfFree
Port aggregation 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 Port aggregation load balancing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Port aggregation load balancing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3000117