Apparatus and method for processing data frames in an internetworking device

• US 5,796,944 A
• Filed: 07/12/1995
• Issued: 08/18/1998
• Est. Priority Date: 07/12/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Lawler, Christopher P., Hill, Shannon Q.
• Primary Examiner(s): Bowler, Alyssa H.
• Assistant Examiner(s): Nguyen, Dzung C.
• Application Number:
  US08/501,500
• Time in Patent Office: 1,133 Days
• Field of Search: 395/800, 395/200.07, 395/200.15, 395/800.01, 395/200.01, 395/200.08, 395/800.26, 395/800.29, 395/800.27, 395/800.34, 364/DIG. 1
• US Class Current: 709/250
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming

Abstract

An address management circuit and method of operation, for use in a communications internetworking device, includes a search engine having first and second search circuits for concurrently searching a network address table for source and destination addresses of a frame received by the communications internetworking device. Memory read cycles of the source and destination address searches are interleaved to allow a memory access to occur during every system cycle to thereby rapidly complete the searches for both the source and destination addresses.

Claims

1. An internetworking device comprising:

a buffer management circuit for providing addresses;

a memory having a plurality of addresses stored therein; and

an address management circuit, coupled to said buffer management circuit and said memory, said address management circuit for receiving addresses from said buffer management circuit and for searching addresses in said memory, wherein said address management circuit includes;

a search engine having first and second search circuits for simultaneously searching for first and second addresses in said memory; and

a network processor unit coupled to said search engine for accessing said memory and for providing an indication of a last address stored in said memory to said search engine,

wherein each of said first and second search circuits of said search engine comprise;

a comparator having a first input terminal coupled to receive an address from said buffer management circuit and a second input terminal coupled to receive an address retrieved from said memory, wherein said comparator compares a first address received from said buffer management circuit and a second address received from said memory and provides an output indication thereof; and

a math unit, coupled to said comparator, said math unit for searching said memory and for identifying a next address to be provided to the second terminal of said comparator from said memory.

2. The internetworking device of claim 1, further comprising a state machine coupled between said comparator and said math unit, said state machine for receiving said output indication from said comparator and for providing an output signal to said math unit, wherein said output signal indicates to said math unit whether the second address has a value greater than, less than or equal to the first address.

3. The internetworking device of claim 1, wherein said first and second search circuits each perform a binary search.

4. The internetworking device of claim 3, wherein said math unit has stored therein a first value corresponding to a beginning address in said memory, a second value corresponding to an ending address in said memory, and a third value corresponding to an address between the beginning and ending addresses in said memory.

5. The internetworking device of claim 4, wherein the third value corresponding to an address between the beginning and ending addresses corresponds to a midpoint address between the beginning and ending addresses.

6. The internetworking device of claim 1, wherein said network processor unit comprises a register for storing an address that is indicative of a next free address in said memory, wherein the address corresponds to the indication provided from said network processor unit to said search engine.

7. The internetworking device of claim 6, wherein said network processor unit comprises an operations processor for installing addresses in said memory.

8. The internetworking device of claim 6, wherein said network processor unit comprises an operations processor for removing addresses from said memory.

9. The internetworking device of claim 6, further comprising:

a first bounds register; and

a second bounds register, wherein said memory is provided having a first region defined by an address stored in said first bounds register and said memory is provided having a second region defined by an address stored in said second bounds register.

10. The internetworking device of claim 9, wherein said network processor unit further comprises:

a first register for providing a next free address of the first region of said memory; and

a second register for providing a next free address of the second region of said memory.

11. The internetworking device of claim 10, wherein said network processor unit comprises an address multiplexor for indicating whether a first one of an install or a remove operation is being performed in a first one of the first and second regions of said memory.

12. A method for installing an address in a network address table stored in a memory of an internetworking device comprising the steps of:

(a) determining where in a linear list of address entries in the network address table a new address entry belongs;

(b) moving a last address entry in the network address table from its present position in the network address table to a position corresponding to a next free address entry position in the network address table;

(c) moving an address entry located previous to the last address entry in the network address table from its present position in the network address table to a new position in the network address table, wherein the new position is one position closer to the next free address entry position than the present position;

(d) repeating step (c) until all of the address entries above the new address entry in the network address table have been moved to create an available slot in the network address table; and

(e) inserting the new address entry into the available slot in the network address table.

13. The method of claim 12, further comprising the step of informing a network processor unit that the install operation is complete.

14. A method for removing an address in a network address table stored in a memory of an internetworking device comprising the steps of:

(a) determining where in a linear list of address entries in the network address table an old address entry resides;

(b) moving an address entry located subsequent to the old address entry in the network address table from its present position in the network address table to the position of the old address entry in the network address table;

(c) moving an address entry located subsequent to the last moved address entry in the network address table from its present position in the network address table to a new position in the network address table, wherein the new position is the former position of the last moved address entry in the network address table; and

(d) repeating step (c) until all of the address entries above the old address entry in the network address table have been moved to fill in the open slot in the network address table created by the removed old address entry.

15. The method of claim 14, further comprising the step of informing a network processor unit that the remove operation is complete.

16. The method of claim 14, wherein said step of moving an address entry located subsequent to the old address entry in the network address table from its present position in the network address table to the position of the old address entry in the network address table comprises overwriting the old address entry with the address entry located subsequent to the old address entry in the network address table.

17. The method of claim 14, wherein said step of moving an address entry located subsequent to the last moved address entry in the network address table from its present position in the network address table to a new position in the network address table comprises overwriting the last moved address entry with the address entry located subsequent to the last moved address entry in the network address table.

18. An address management circuit having a network address table coupled thereto, said address management circuit comprising:

a search engine for receiving a source address and a destination address and for simultaneously searching the network address table for the source and destination addresses; and

a network processor unit coupled to said search engine for accessing the network address table and for providing a next free address indicator of the network address table to said search engine,

wherein said search engine includes a pair of search circuits, each of said search circuits comprising;

a comparator having a first input terminal coupled to receive a first one of a source address and a destination address and a second terminal adapted to receive an address retrieved from said network address table, wherein said comparator compares the first one of the source address and the destination address and the address retrieved from said network address table; and

a math unit, coupled to said comparator, said math unit for searching said network address table and for identifying a next address to be provided from said network address table to the second terminal of said comparator.

19. The address management circuit of claim 18, wherein said network processor unit comprises:

a comparator for comparing first and second addresses fed thereto and for providing an output indication thereof; and

a state machine, coupled to said comparator, for receiving said output indication from said comparator, wherein said state machine installs and removes addresses from the network address table.

20. A method for searching a memory of an internetworking device to find an active address, said method comprising steps of:

retrieving a first address from a network address table;

comparing a particular source address with the first address retrieved from the network address table; and

retrieving a second address from the network address table while simultaneously performing the step of comparing the particular source address with the first address retrieved from the network address table,

comparing a particular destination address with the second address retrieved from the network address table;

simultaneously retrieving a third address from the network address table; and

performing an age cycle after said particular source address is matched with an address retrieved from the network address table.

21. The method of claim 20, wherein after executing an age cycle no more retrieve steps for said particular source address are performed.

22. The method of claim 20, wherein after a source address compare step indicates that a source address is found, then performing a memory input-output read step in place of a source address retrieve step.