Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1998-12-09
2003-01-28
Nguyen, Steven (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S389000, C711S216000, C711S220000, C711S221000
Reexamination Certificate
active
06512742
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to a method and system for improved transmission of data and in particular to an improved method and system for balanced data transmission across a link aggregation. Still more particularly, the present invention relates to an improved method and system for balanced distribution of the data for tranmission across k links of a link aggregation where k is not a power of 2.
2. Description of the Related Art
In a networking environment, it is typical that a plurality of devices will be linked together for the purpose of transmitting data from one device to another in the network. In a large network, it would be uneconomical to provide a specific data link connecting each device to each of the other devices in the network. In order to provide connectivity from each device to each of the other devices in the network in an efficient and economical manner, a plurality of methods have been developed.
One well known method of distributing data between devices within a network is through switches. Switches may be utilized within the network to receive data from a plurality of devices and distribute the data to a plurality of devices to reduce the amount of data lines required to distribute data. To utilize switches to communicate between devices, each device has a specific address. Specifically in an ethernet switching environment, each device in the network has a media access control (MAC) address, which uniquely identifies the device in the network. Frames of data are delivered to a MAC destination address (DA) and senders are recognized by a MAC source address (SA). Each switch, and each port on a switch supports a finite number of MAC addresses. Ideally, the overall number of MAC addresses distributed by a switch should be large, so the switch can support a large number of devices.
In addition to supporting a large number of devices, a switch should comprise the ability to handle transfer of large amounts of data through a network. For a switch to handle quick transfer of large amounts of data, often link aggregation is utilized in order to allow a switch to support a higher bandwidth interface to increase the rate of data transfer. Link aggregation is a technique that allows parallel physical links between switches or between a switch and a server to be used simultaneously, multiplying the bandwidth between the devices. Link aggregation may be further defined as a method of grouping physical link segments of the same media type and speed, and treating them as if they were part of a single, logical link segment. For example, two 100 Mbps links between switches may be grouped into a link aggregation and treated as a single 200 Mbps link to create a higher bandwidth interface between the two switches.
In order to optimize data transmission across a link aggregation, a load balancing scheme is preferably implemented. Load balancing schemes attempt to distribute data in a balanced manner across the links of the link aggregation in order to optimize the available bandwidth. One load balancing techniques may measure the bandwidth through each link and adjust data to move through underutilized links to reduce traffic through overutilized links. Other load balancing techniques may utilize less hardware through a table with a hashing scheme to distribute data for transmission across the link aggregation.
FIG. 1
depicts a prior art pictorial illustration of a table
10
which may be utilized to implement a hashing scheme. Table
10
contains 2
N
entry positions where 2
N
is the number of links in the link aggregation. In the example shown, N=2 such that there are four links the link aggregation and four entry positions in table
10
. Each of the four entry positions has an assigned index number
0
-
3
as depicted at reference numeral
12
. Following, each of the four links is assigned to one entry position of the table
10
as depicted at reference numeral
14
. To distribute the data across the links, each of the data frames with identical MAC addresses as other data frames are grouped into a flow. N=2 bits of the SA of each flow are XORed with N=2 bits of the DA of each flow to create a two bit table address. The link which is addressed for a selected flow is selected from table
10
utilizing the table address described above and the flow is sent across the particular link. By the hashing scheme described above, each link should be assigned to onefourth of the flows. However, in order to implement this technique, the link aggregation must have k links where k is a power of two. Thus, table
10
, utilized to implement the depicted hashing scheme, limits the link aggregation design.
As networking technologies require larger bandwidths for data transmission, users demand that networks scale flexibility to fit their needs. It would be desirable in the development of link aggregation to provide a table and a method of assigning links to that table which may be utilized with a hashing scheme which would support link aggregations of an arbitrary size, with balanced distribution of data transmission across the k links. Such a table and hashing scheme would not be limited to 2
N
links, thus allowing flexibility in the number of links included in a link aggregation for expansion of the uses of a link aggregation.
SUMMARY OF THE INVENTION
It is therefore one object of the present invention to provide a method and system for improved data transmission.
It is another object of the present invention to provide an improved method and system for balanced data transmission across a link aggregation.
It is yet another object of the present invention to provide an improved method and system for balanced distribution of the data for transmission across k links of the link aggregation where k is not a power of 2.
The foregoing objects are achieved as is now described. A method and system are disclosed for balanced transmission of data across a link aggregation of k links in a network, where k is not a power of 2, where data is specified by frames each having a source address and a destination address. N bits of the source address and N bits of the destination address are selected to be XORed together, where N is greater than 2, where N is chosen to provide an equal distribution of data across each link within a desired percent. An index table with 2
N
entry positions is created where each of the entry positions is assigned an index number between 0 and 2
N
−1. The entry positions within the index table are then filled with one link of the k links in each entry position until all of the entry positions are filled where the k links may fill the entry positions in a repetitive sequence. The frames of data with identical source addresses and destination addresses with other frames of data are grouped into a flow. N bits of the source address are XORed together with N bits of the destination address for each of flow to obtain an N bit index number for each of flow. The index table is then accessed with the N bit index number to identify a particular link within the index table. The flow is transmitted across the particular link.
The above as well as additional objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4032719 (1977-06-01), Blasbalg
patent: 5163156 (1992-11-01), Leung et al.
patent: 5430729 (1995-07-01), Rahnema
patent: 5524111 (1996-06-01), Le Pennec et al.
patent: 5687168 (1997-11-01), Iwata
IBM Technical Disclosure Bulletin, vol. 38, no. 9, Sep. 1995, “Load Balancing for Multiple Interfaces for Transmission Control Protocol/Internet Protocol for VM/MVS.”
IBM Technical Disclosure Bulletin, vol. 35, no. 5, Oct. 1992, “Guideline for Flow Window Configuration in Data Redistribution.”
Alexander, Jr. Cedell Adam
Kumar Arush
Larsen Loren Douglas
Bracewell & Patterson L.L.P.
Duong Duc
International Business Machines - Corporation
Nguyen Steven
Woods Gerald R.
LandOfFree
System for data transmission across a link aggregation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for data transmission across a link aggregation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for data transmission across a link aggregation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3040777