Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-07-23
2002-12-03
Marcelo, Melvin (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S475000, C711S216000
Reexamination Certificate
active
06490279
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the system architecture and data management techniques to configure and design a database searching and learning apparatus. More particularly, this invention relates to an improved database searching and learning system to speed up the database searching and learning processes for implementation in single chip Ethernet frame switching system. The database searching and learning processes can be completed within one or two clock cycles. Improved searching and learning process speed also enables a pipelined architecture for constructing systems to carry out database searching and learning processes.
2. Description of the Prior Art
As the Ethernet packet switch fabrics are now required to process gigabit per second, conventional technology is faced with a difficult challenge. The challenge is to perform an address resolution task at a rate of gigabits per second in order to be in synch with such a high data-rate in switching and transmission operation. Limited by the techniques available for address resolution, conventional methods are either too slow or too expensive. Practical application of Ethernet packet switch of higher data-rate is therefore hindered by this difficulty. In order to have better understanding of the technical background, the basic structure of the database entry items and the techniques employed for conducting an address resolution is explained first.
Database search logic is a technique applied to map the key of the searched item with the keys of all the items contained in a database. When a match is identified, the associated data in the database is retrieved as output. For a database employed for storing addresses for packet or cell switch, the database search logic is commonly referred to as lookup engine or address resolution logic. The database is generally referred to as an address table.
FIG. 1
shows the structure of a database entry item, which typically comprises three parts. The first part is the key for identifying the item, e.g., an address. The second part is a status data for providing a state of this database entry item. The state of the item may be the data related to information such as validity, age and other control information. The third part is the data item itself. For an address table, the data item is the data associated with the address. For an Ethernet packet switching system, the data may be used as the value of a port number. Details for application of this data item in an Ethernet switching system will be further discussed below.
FIG. 2
shows the format of an Ethernet packet processed by an Ethernet switching system. The destination address (DA), is applied to identify the node to which the packet should be forwarded. The source address (SA) is included to indicate the address of the node from which the packed is sent out The lookup engine, i.e., an address resolution logic, for a switching fabric uses the DA as a key to find the destination port and the associated information related to the destination address if applicable. The source address (SA) is used by the automatic learning logic to establish the address table.
A typical Ethernet packet switch system is illustrated in
FIG. 3. A
data packet received from the media is converted into digital format by the physical layer device (PHY). A media access control (MAC) logic is responsible to retrieve the destination address (DA) data embedded in the packet and to pass the DA data as a key. The DA is used by the address resolution logic (ARL) as a key to search of the associated data item in the database. The database is an address table for this application. The ARL searches the address table to find the matched DA to retrieve a data item for providing an address of the destination port The destination port address is returned to the MAC. A request is then sent by the source MAC to the switch fabric to send the packet to the destination MAC. After receiving the packet, the destination MAC will forward the packet to the PHY for further transmission. For a gigabit Ethernet system, the rate for data transmission can be as high as
10
9
bits per second. For an Ethernet packet switching system with one ARL shared by 16 MAC ports, there can be as high as 23.8-million address resolution requests per second. Under a worst-scenario assumption, the frequency of lookup request for address resolution can reach as high as the calculated value of:
16* 10
9
bits/ [(512+64+96) bits]=23.8 *10
6
Where 512 bits is the minimum packet length with a 64-bit preamble and 96 inter-packet gap. As will be further discussed below, in order to satisfy such a high-speed processing requirement, very expensive ARL system has to be implemented when conventional techniques are applied.
FIG. 4
is a functional block diagram of a conventional address resolution logic system. There are two basic modules, i.e., a lookup logic module and a learning logic module, for an ARL system. Upon receiving a lookup request, a database search is performed to locate a database entry item matched the destination address contained in the received packet Conventional database search techniques such as link list search and content addressable memory (CAM) search are further discussed below.
The structure of a traditional address table is a link-list type table. The keys are hashed into different “buckets”. In each bucket, entries of the data items are chained together through a link list The link lists can be sorted or unsorted lists.
FIG. 5
shows the linking configurations of the data entries in each bucket for a link list based address table.
FIG. 6
is a flow chart showing the processing steps of an ARL system in conducting a database search on a link-list based address table. After a lookup request is received, the key is first hashed into a bucket number. The search begins by pointing to the first entry of the bucket and then comparing the key with that of the first entry of the bucket. A check is made to find out if the key matches with the data in the first entry. If the key matches, then the data is retrieved, if not, another check is made to determine if this is the last entry in a specific bucket If not, then the process is pointed to a next entry in the bucket and another attempt is performed to match the key with the data. If this data entry is the last entry is the last entry in the bucket, then a “result unknown” is returned. In performing this search, for a sorted link list, a binary search algorithm can take up to log
2
N cycles where N is the length of the link list. For an unsorted link list, the search can take up N cycles. Similar to the lookup logic, the learning logic of the ARL system will also search if there is a match in the entry matched up with the key. As that shown in
FIG. 7
, the learning logic will also check if the data is changed when a matched key is identified. The data item in the database will be updated when there is a change in the data. If the key is not found in a bucket, the key and the data are added to the bucket in the learning process by the learning logic. Again, to update or insert a new database item, for a sorted link list, the learning process may take up log
2
N cycles, and for an unsorted link list, it may take up N-cycles. Due to these time-cycle requirement, the link-list based methodology as discussed above is obviously too slow when a system is implemented with high transmission data rate.
Another conventional method for establishing and searching a database is by employing a content address memory (CAM) technique.
FIG. 8
is an organizational configuration of a content addressable memory based address table. The CAM based ARL system includes a comparand register for receiving and temporarily storing the key. The ARL system further includes n-comparators. The data stored in the comparand register is compared to the address entry in each of these n-comparators. A matched address is identified and retrieved from the memory as the output data of the s
Chen Honglu
Tsui Tak-Lap
Wang Ying
Advanced Communication Device, Inc.
Lin Bo-In
Marcelo Melvin
Mehra Inder Pal
LandOfFree
Fast data base research and learning apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast data base research and learning apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast data base research and learning apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2995316