Relay control circuit using hashing function algorithm

Details Relay control circuit using hashing function algorithm Relay control circuit using hashing function algorithm

2000-11-10

2004-11-16

Vu, Huy D. (Department: 2665)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S389000

Reexamination Certificate

active

06819671

ABSTRACT:

CROSS-REFERENCE TO RELATED APPLICATION
This application claims the priority benefit of Taiwan application serial no. 89100598, filed Jan. 15, 2000.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates to an Ethernet switch. More particularly, the present invention relates to the relay control of an Ethernet switch that enlists a hashing function method to increase hit rate and network transmission efficiency.
2. Description of Related Art
Although Ethernet is the most popular local area network, a transmission rate of 10 Mbps (bit per second) is not enough for multimedia communication. Consequently, an improved solution, Fast Ethernet, which has a transmission rate of 100 Mbps, is developed. However, in fast Ethernet an additional convergence sublayer (CS) must be introduced between the media access control (MAC) sublayer and the physical medium dependent (PMD) sublayer. Hence, the network interface card must be updated by a fast Ethernet interface card. However, in the case of increasing the transmission rate without updating the original slow network interface card in each network station, an Ethernet switch structure is preferred.
In the conventional Ethernet, a twisted wires is used as a medium for network connection. It does not matter if the transmission rate is 10 Mbps or 100 Mbps, workstations and server are linked together through an Ethernet hub so that network data are shared. In general, bandwidth of the hub is shared by the linked workstations attached to the network. For example, for a 100 Mbps Ethernet hub with 16 ports, if 4 ports are connected to workstations, network bandwidth is shared by the 4 workstations. If 16 ports are connected to workstations, network bandwidth is shared by the 16 workstations. As the number of network users increases, network collision will become more serious and bandwidth assigned to each user will be narrower as well. Hence, conventional Ethernet hub is no longer capable of satisfying the demands of users.
An Ethernet switch is developed for improving network bandwidth. The Ethernet switch permits the simultaneous data transmission of several connected workstations so that overall performance of the network is increased. To achieve the switching function, the Ethernet switch must know which port a workstation is connected to. In other words, the Ethernet switch must have an address learning function similar to a bridge device. When the switch receives a frame signal, a routing table will be consulted to lookup for the port connected to the destination workstation. If the port is found, a control processor will send out a control signal to a switching element so that the frame signal is output to the port. Conversely, if the port is not found in the routing table, the frame signal will be broadcast to every connected port so that the destination workstation is sure to receive the frame.
Assume that N is the number of connection ports in an Ethernet switch, the switch is capable of transmitting frame signal to a maximum of N/2 workstations. For example, a 16 ports 100 Mbps Ethernet switch can have a maximum network bandwidth of 800 Mbps if collisions are ignored. On the other hand, a 16 ports 100 Mbps Ethernet hub can have a maximum network bandwidth of just 100 Mbps. Hence, there is a tremendous improvement in transmission capability for the Ethernet.
The Ethernet switch device has a relay control circuit. The relay control circuit is connected to an address table of an external memory. When one port of the Ethernet switch picks up a frame signal, the relay control circuit will search the address table for destination port of the frame signal. If a destination port that corresponds to frame's destination medium access control (DMAC) address is found in the address table, the frame is sent to the destination port by the relay control circuit. If a destination port that corresponds to the DMAC address is not found in the address table, the frame is broadcast so that the frame signal is received by the destination port. The destination port that corresponds to the DMAC address is identified and written into the address table. However, this will downgrade the performance of the Ethernet switch. In addition, the relay control circuit of the Ethernet switch also has a frame-filtering function. In general, the address table of an Ethernet switch is stored in a memory. For cost down, the memory is usually a static random access memory (SRAM). Due to the rapid expansion of computer network, the address table within the SRAM can no longer hold all the network addresses of all Ethernet workstations. Hence. it is important to choose a suitable lookup method for obtaining the destination port corresponding to a DMAC address as soon as possible.
At present, performance of an Ethernet switch depends very much on time consumed on finding out the destination port from a frame's DMAC address and transmitting the frame. Currently, various lookup methods capable of shortening lookup time have been implemented in the relay control circuit of the Ethernet switch.
The most common lookup method includes the linear lookup, binary tree lookup and hash function lookup. In the linear lookup method, the DMAC address is compared with the content in an address table one by one from the very beginning to the end. Due to relative inefficiency, linear lookup method is rarely used now. In the binary tree lookup method, checking area is cut in half with each level down the tree. Therefore, the binary tree method converges upon the required address much faster than the linear lookup method. However, the binary lookup method is still not satisfied in Ethernet switch.
In hashing function lookup method, DMAC addresses are sorted on a fix-sized table. A mathematical function h is used to represent the address location of the destination address x in the table. Hence, h(x) represent the address of x in the table. This h(x) is called a hashed address or a home address of x. Assume that the memory addresses for storing a DMAC ADDRESS table are contiguous, the memory addresses form a hash table (ht). The hash table is divided into b buckets from ht[0] to ht[b−1]. Each bucket has s recording stores. In other words, each bucket has s slots, each capable of holding a record. In general, s=1, and hence each bucket contains a record. The hashing function h(x) performs a transformation of the destination medium access control (DMAC) address x so that a group of possible DMAC addresses is assigned to one of the integer between 0 and b−1.
In general, the number of DMAC addresses will be greater than the number of buckets used in the hashing table. Therefore, the hashing function h(x) matchs a few different DMAC addresses to the same bucket. For DMAC addresses I
1
and I
2
with h(I
1
)=h(I
2
), they are referred to as synonyms. As long as there are still vacant slots within a bucket, the synonyms are placed in different slots inside the same bucket. When a bucket is already full, any attempt at putting a new DMAC address into the bucket will result in an overflow. On the other hand, any attempt at forcing two different nonsynonymous address into one bucket will result in a collision.
A conventional relay control circuit of an Ethernet switch usually truncates 48 bits DMAC address into a shorter length such as 11 bits. The 11 bits data are sent to the memory for a table lookup operation. Since no hashing function h(x) or other processing methods are used, hit rate of the table lookup operation is rather low. If there is no hit in a table lookup operation, the relay control circuit has to broadcast the DMAC address again. When a destination port that corresponds to the DMAC address is found, the destination port and the address is written back to the table inside the memory. However, this will degrade the performance of the network.
SUMMARY OF THE INVENTION
Accordingly, one object of the present invention is to provide a relay control circuit and its method of operation that utilizes a hashing function

Affiliated with

Also associated with

Rating

Relay control circuit using hashing function algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Relay control circuit using hashing function algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relay control circuit using hashing function algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3350805