Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
1999-11-03
2004-10-12
Nguyen, Steven (Department: 2665)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S389000, C370S428000, C707S793000
Reexamination Certificate
active
06804230
ABSTRACT:
BACKGROUND TO THE INVENTION
This invention relates to communication devices for packet-based communication systems, and in particular to multi-port communication devices which receive addressed data packets at any of a multiplicity of ports and which can forward packets to one or more ports after recourse to a forwarding database which includes entries identifiable from a destination address and including associated data such as, for example, a port mask.
Background to the Invention
Multi-port communication devices for packet-based communication systems, such as ‘layer
3
’ switches and routers, usually include a forwarding database by means of which a received packet is directed, after appropriate processing and temporary storage as necessary or appropriate, to one or more ports of the device. The forwarding database may be established from information obtained from routing and address resolution protocols.
When a packet is received and is therefore to be forwarded by the device, the destination address may be looked up in the forwarding database. There is a variety of ways of organising such a database in the look up process, in order to economize on the fast random access memory that is required and to reduce the searching time or both. For example, one method of retrieval includes the hashing of an address to provide access to a table of hashed addresses, this table having entries constituting pointers to a data table including address data and associated data. It is known to organise these databases such that the entries in the data table which share a common hashed address are linked, it being necessary to verify the entries in the data table in turn against the key, or address for which the search is made, and to proceed along the chain of linked addresses until a verified match is found. A database organised on these lines is disclosed in U.S. patent application Ser. No. 09/286,469 filed 6 Apr. 1999 in the name Anne G O'Connell and incorporated by reference herein.
There are circumstances in which despite such space saving schemes as hashing, a forwarding database is liable to contain a very large number of addresses and consequently would require a very large memory. One example is if a switch is used as a ‘layer
3
’ device, namely it is required to look up addresses which pertain to layer
3
(logical link control) of the OSI model, these addresses are otherwise known as ‘network’ addresses.
It is known to employ a ‘trie’ system for the forwarding database. The purpose of a ‘trie’ scheme is to determine the ‘next hop’ for a packet on a route to its final destination. It will be understood that a router which operates on network addresses is indirectly connected (by way of other routers) to a large number of end stations and, in the absence of some more efficient scheme for storing addresses, would need to store the MAC addresses of all that large number of end stations (in addition to the MAC addresses of the end stations to which it may be directly connected). However, many packets having different network addresses will require to be sent to the same router and therefore, as far as the search is concerned may be treated as having the same address (whether this be expressed as a port number or as the MAC address of the next router). The address data for forwarding packets to the next (intermediate) destination can be collapsed into a single entry in a routing table.
It is therefore convenient to divide a forwarding database, particularly for a router or other layer
3
switch, into generally two parts. One part comprises a set of blocks each of which contains a plurality of storage locations each including (in the simplest case) a pointer ‘result’ field. The rest of the database comprises ‘associated data’ entries, such as a port number and/or a MAC address. If the ‘result’
0
field of a pointer is not set, the pointer will identify another trie block. If it is set it will point to an entry in the associated data table part of the database. Many packets may have the same ‘next hop’ and accordingly the information for the address data of these packets can be collapsed into a single entry in the routing table. The address look up is performed using a key comprising the layer
3
address information. The key may be used to search a trie data structure until a leaf node, namely an associated data block is found. Each level in the trie employs a successive group of bits from the key. The benefit of such a searching scheme is that many addresses with a common prefix can refer to the same target address
When a trie structure is established, the amount of memory allotted to it in the database is divided into blocks. The number of blocks determines the number of routes which may be stored. If only a small number of blocks is available, then the number of routes that can be stored is also small. It is possible to increase the number of routes stored by sub-dividing the same memory space into smaller trie blocks. Using smaller blocks in the trie system has the disadvantage that the search time may be increased, thereby reducing the performance of the look up process. Maximum versatility can be achieved by supporting blocks of different sizes. Initially, the tables can then be built using larger trie blocks, maximizing look up performance. If the memory configuration does not allow sufficient routes to be stored, the tables can be configured to use smaller trie blocks with some loss of look up performance.
However, if blocks of different sizes are to be used, a problem arises over the selection of the correct number of address bits for use in each stage of the trie search. The multiplexing required to select different numbers of address bits at each stage would become very complex, the complexity increasing as the number of block sizes increases.
SUMMARY OF THE INVENTION
The invention has as its main object the provision of a device with a trie search facility that is provided in hardware and which accommodates a multiplicity of block sizes for the trie search.
The invention is based on the use of a shift register to hold the key for the trie search, and at each stage of the search to shift the content of the register by the number of bits employed for accessing a location within a block. The result of each stage of a search is a pointer to a block, the pointer identifying the block and also including an indication, which denotes the size of the block to which the pointer refers. This indication in the pointer can be used to control the shift register. Preferably the indication is a coded indication, i.e. it merely distinguishes between the possible sizes of blocks. Thus it may be constituted by a one-bit field if there are only two possible sizes and a two-bit field if there are four possible sizes. Herein ‘size’ refers to the number of different pointers that can be accessed and not necessarily the number of locations, since each location may be used for storing a plurality of pointers.
Reference will hereinafter be made to the accompanying drawings, which illustrate schematically one embodiment of the invention.
REFERENCES:
patent: 5787430 (1998-07-01), Doeringer et al.
patent: 5790979 (1998-08-01), Liedtke
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 5983320 (1999-11-01), Farmwald et al.
patent: 6014659 (2000-01-01), Wilkinson, III et al.
patent: 6430527 (2002-08-01), Waters et al.
patent: 6493347 (2002-12-01), Sindhu et al.
patent: 0551243 (1993-01-01), None
patent: WO 95/34155 (1995-12-01), None
patent: WO 99/13619 (1999-03-01), None
Jennings Kevin
Loughran Kevin
O'Callaghan Sorcha
O'Malley Edele
3Com Corporation
Nguyen Steven
Nixon & Vanderhye PC
Stevens Roberta
LandOfFree
Communication device with forwarding database having a trie... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communication device with forwarding database having a trie..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication device with forwarding database having a trie... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3323121