Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-17
2004-10-26
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395200, C370S395310, C370S412000, C709S215000
Reexamination Certificate
active
06810037
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method and apparatus for high performance switching of data packets in local area communications networks such as token ring, ATM, Ethernet, fast Ethernet, and gigabit Ethernet environments, all of which are generally known as LANs. In particular, the invention relates to a new switching architecture in an integrated, modular, single chip solution, which can be implemented on a semiconductor substrate such as a silicon chip.
2. Description of the Related Art
The present invention advances network switching technology in a switch suitable for use in Ethernet, fast Ethernet, gigabit Ethernet, and other types of network environments which require high performance switching of data packets or data cells. A switch utilizing the disclosed elements, and a system performing the disclosed steps, provides cost and operational advantages over the prior art.
SUMMARY OF THE INVENTION
The present invention is related to a method for searching a table in a network switch, wherein the method includes the steps of dividing a primary lookup table into a first sub table and a second sub-table, searching the first sub-table with a first search engine, and simultaneously searching the second sub-table with a second search engine.
The present invention further includes a method for searching a primary address table within a network switch, wherein the method uses the steps of dividing the primary address table into a first and second address sub-tables, storing even numbered memory address locations from the primary address table within the first address sub-table in sorted order, and storing odd numbered memory address locations from the primary address table within the second address sub-table in sorted order. Thereafter the method includes the steps of searching the first address sub-table with a first search engine, and simultaneously searching the second address sub-table with a second search engine.
The present invention also provides a network switch for network communications, wherein the network switch includes a primary lookup table, the primary lookup table being divided into a first lookup sub-table and a second lookup sub-table, each of the first and second lookup sub-tables having a plurality of memory address locations therein for storing entries. A first search engine is provided, wherein the first search engine is communicating with the first and second lookup sub-tables. A second search engine is also provided, and the second search engine is also communicating with the first and second lookup sub-tables. The switch is configured such that the first search engine searches the first lookup sub-table for a first desired entry, and if the first desired entry is not found within the first lookup sub-table, then the first search engine is configured to search within the second lookup table. Further, the second search engine is configured to search the second lookup sub-table for a second desired entry, and if the second desired entry is not found within the second lookup sub-table, then the second search engine is configured to search within the first lookup sub-table.
The present invention additionally provides a network switch for network communications having at least one data port interface operating to transmit data packets through the network switch, wherein the at least one data port interface has at least one address lookup table and at least one address search engine positioned therein. The at least one search engine being in communication with the at least one address lookup table. A CPU interface is provided, and the CPU interface is configured to communicate with a CPU. At least one memory structure is provided, and the at least one memory structure in communication with the at least one data port interface. A communication channel is provided, the communication channel being configured to transmit data and messaging information between the at least one data port interface, the CPU interface, and the at least one memory structure.
REFERENCES:
patent: 5423015 (1995-06-01), Chung
patent: 5473607 (1995-12-01), Hausman et al.
patent: 5787084 (1998-07-01), Hoang et al.
patent: 5993055 (1999-11-01), Williams
patent: 6335935 (2002-01-01), Kadambi et al.
patent: 6453358 (2002-09-01), Micchels et al.
patent: 6553000 (2003-04-01), Ganesh et al.
patent: 6580712 (2003-06-01), Jennings et al.
patent: 6633576 (2003-10-01), Melaragni et al.
patent: WO 99/00938 (1999-01-01), None
patent: WO 99/00939 (1999-01-01), None
patent: WO 99/00944 (1999-01-01), None
patent: WO 99/00945 (1999-01-01), None
patent: WO 99/00949 (1999-01-01), None
patent: WO 99/00950 (1999-01-01), None
Jorda Michael A.
Kalapathy Paul
Broadcom Corporation
Kizou Hassan
Nguyen Hanh
Squire Sanders & Dempsey L.L.P.
LandOfFree
Apparatus and method for sorted table binary search... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for sorted table binary search..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for sorted table binary search... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3267297