Switch with adaptive address lookup hashing scheme

Details Switch with adaptive address lookup hashing scheme Switch with adaptive address lookup hashing scheme

1999-11-30

2004-02-10

Vanderpuye, Kenneth (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395320, C711S216000

Reexamination Certificate

active

06690667

ABSTRACT:

FIELD
The present invention relates to networking technology, and more particularly, to network switches.
BACKGROUND
In a digital communication system, a local area network (LAN) may be connected to another LAN by way of a switch (bridge). LANs are typically packet-based, in which messages are broken into packets (frames). Many LANs are based on IEEE (Institute of Electrical and Electronic Engineers) standard 802.3, commonly called Ethernet.
FIG. 1
illustrates four-port switch
102
connecting four Ethernet segments
104
,
106
,
108
, and
110
. Each Ethernet segment may be operated at different speeds. For example, segment
102
may be a 10 Mbit Ethernet whereas the other segments may be 100 Mbit Ethernets. Connected to each Ethernet segment are various data terminal equipment (DTE), which may be clients, servers, or other users and creators of digital data. Each DTE has one or more media access control (MAC) devices connected to an Ethernet segment, where each MAC has a unique address.
An Ethernet packet (frame) along with some of its fields is illustrated in FIG.
2
. Shown are destination address field
202
, source address field
204
, frame check sequence field
206
, and preamble field
208
. The payload data for the Ethernet packet of
FIG. 2
is indicated by
210
. Not all of the fields are shown. The source address field of an Ethernet packet provides the address of the MAC source of the packet, and the destination address field provides the MAC address of the packet's intended recipient.
Switch
102
forwards or filters a packet based upon the packet's source and destination address fields. For example, if the source of a data packet is DTE
112
and its destination is DTE
114
, then switch
102
filters out the data packet, i.e., it is not forwarded to another Ethernet segment. However, if the source of a data packet is DTE
112
and its destination is DTE
116
, then the packet is forwarded to Ethernet segment
108
.
Usually, a table is accessed by switch
102
to determine whether a packet is forwarded or filtered. Given an address, a table entry provides the segment (or equivalently, the switch port connected to the segment) containing the address, provided the table entry is present in the table. Additional information stored in the table may be the age of the address entry, so that updates based upon age may be performed. The table is built up through a learning process. For example, by observing the source addresses of data packets, switch
102
learns which segments have which MAC addresses. If a data packet is received in which its destination address is not present in a table, switch
102
floods the network with the data packet, i.e., it is forwarded to all segments.
A table may be implemented by a content addressable memory (CAM), whereby an address is matched with stored addresses, and if there is a hit, the appropriate information, such as a switch port, is retrieved. Data structures (or abstract data types) other than tables may be used to associate addresses with segments (switch ports). For example, binary trees, or Patricia trees, may be utilized. However, MAC addresses are 48 bits, and typically a design goal is to provide a capacity of 8 K addresses. Prior techniques of utilizing CAMs and trees may be costly in terms of silicon area or speed. The present invention is motivated to address some or all of these problems.
SUMMARY
In one embodiment of the present invention, a switch comprises a memory unit to store a hash table having entries. Each entry in the hash table is pointed to by a hash table address, and has an address field to indicate an address and a switch port field to indicate a switch port. The hash table address is a portion of the coefficients of a remainder polynomial obtained by dividing the polynomial sum of an address polynomial and a shifted key polynomial by a generator polynomial.


REFERENCES:
patent: 4588985 (1986-05-01), Carter et al.
patent: 4897785 (1990-01-01), Ziiger
patent: 5032987 (1991-07-01), Border et al.
patent: 5083265 (1992-01-01), Valiant
patent: 5406278 (1995-04-01), Graybill et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5623545 (1997-04-01), Childs et al.
patent: 5713001 (1998-01-01), Eberhard et al.
patent: 5920900 (1999-07-01), Poole et al.
patent: 6034958 (2000-03-01), Wicklund
patent: 6134597 (2000-10-01), Rieth et al.
patent: 6226629 (2001-05-01), Cossock
patent: 6246686 (2001-06-01), Ha-Duong et al.
patent: 6424650 (2002-07-01), Yang et al.

Affiliated with

Also associated with

Rating

Switch with adaptive address lookup hashing scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Switch with adaptive address lookup hashing scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switch with adaptive address lookup hashing scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3293312