Relay control circuit using hashing function algorithm

• US 6,819,671 B1
• Filed: 11/10/2000
• Issued: 11/16/2004
• Est. Priority Date: 01/15/2000
• Status: Active Grant

• Current Assignee: VIA Technologies Incorporated (VIA Technologies)
• Original Assignee: VIA Technologies Incorporated (VIA Technologies)
• Inventors: Wu, Hsiao-Lung, Chen, Wei-Pin
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): MATTIS, JASON E
• Application Number:
  US09/710,704
• Time in Patent Office: 1,467 Days
• Field of Search: 370/351, 370/389, 370/392, 370/400, 370/395.31, 370/395.32, 370/401, 370/412, 370/445, 370/475
• US Class Current: 370/392
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A relay control circuit that uses a hashing algorithm for increasing the hit rate in a table lookup operation. Destination medium access control (DMAC) address is extracted from a network frame. The DMAC address is scrambled to put the frequently changing bytes in a position closer to each other. The scrambled address is sent to a cyclic redundancy checking circuit, where a cyclic redundancy checking operation with hashing function capability is carried out to produce a remainder. The remainder is sent to a memory unit for a table lookup operation. Hence, the relay control circuit is capable of finding a destination port that corresponds to a given DMAC address in a very short time, thereby boosting network efficiency.

Claims

1. A relay control circuit inside a switch device, the switch device having an address/port table and receiving a frame signal with a destination medium access control (DMAC) address, comprising:

an address scrambling circuit for changing a byte sequence of at least part of a plurality of bytes in the DMAC address of the frame signal to generate a scrambled DMAC address; and

a transformation circuit coupled to the address scrambling circuit, for generating an index address according to the scrambled DMAC address including all bytes in the DMAC address, wherein the switch device sends out the frame signal according to the index address and the address/port table.

2. The circuit of claim 1, wherein the transformation circuit includes a cyclic redundancy checking circuit.

3. The circuit of claim 2, wherein the cyclic redundancy checking circuit includes a CRC-11 circuit.

8. The circuit of claim 1, said address scrambling circuit putting the frequently changing bytes in a position closer to each other.

9. The circuit of claim 1, said address scrambling circuit putting the frequently changing bytes in the end of said DMAC address.

10. The circuit of claim 1, said address scrambling circuit putting the bytes including more information contents in a position closer to each other.

11. The circuit of claim 1, said address scrambling circuit putting the bytes including more information contents in the end of said DMAC address.

12. The circuit of claim 1, said address scrambling circuit scrambling said bytes such that a byte having the most frequent variation switches position with a byte having the highest information content.

4. A relay control method for sending out a frame signal in a switch network with an address/port table, the frame signal having a DMAC address, the relay control method comprising the steps of:

changing a byte sequence of at least part of a plurality of bytes in the DMAC address of the frame signal to generate a scrambled DMAC address;

transforming the scrambled DMAC address including all bytes in the DMAC address into an index with hash function;

sending out the frame signal according to the index and the address/port table.

5. The relay control method of claim 4, wherein the step of transforming includes performing a CRC operation on the scrambled DMAC address.

7. The relay control method of claim 4, wherein the DMAC address includes six bytes, and the step of scrambling the bytes in the DMAC address changes fourth byte of the DMAC address to a position neighboring to sixth byte.

13. The relay control method of claim 4, said scrambling step putting the frequently changing bytes in a position closer to each other.

14. The relay control method of claim 4, said scrambling step putting the frequently changing bytes in the end of said DMAC address.

15. The relay control method of claim 4, said scrambling step putting the bytes including more information contents in a position closer to each other.

16. The relay control method of claim 4, said scrambling step putting the bytes including more information contents in the end of said DMAC address.

17. The relay control method of claim 4, said scrambling step scrambling said bytes such that a byte having the most frequent variation switches position with a byte having the highest information content.

6. A switch device for receiving and sending out a frame, comprising:

an address acquisition circuit for obtaining a destination medium access control (DMAC) address from the received frame;

a memory unit for storing an address table; and

a relay control circuit coupled to the address acquisition circuit and the memory unit for sending out the frame, the relay control circuit changing the byte sequence of at least part of a plurality of bytes in the DMAC address to generate a scrambled DMAC address and transforming the scrambled DMAC address including all bytes in the DMAC address into an index address, the frame being sent out according to the index address and the address table.

18. The switch device of claim 6, said scrambling step putting the frequently changing bytes in a position closer to each other.

19. The switch device of claim 6, said scrambling step putting the frequently changing bytes in the end of said DMAC address.

20. The switch device of claim 6, said scrambling step putting the bytes including more information contents in a position closer to each other.

21. The switch device of claim 6, said scrambling step putting the bytes including more information contents in the end of said DMAC address.

22. The switch device of claim 6, said address scrambling circuit scrambling said bytes such that a byte having the most frequent variation switches position with a byte having the highest information content.