Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-10-08
2001-09-11
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S117000, C711S202000, C712S224000
Reexamination Certificate
active
06289414
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to digital hierarchical address filtering and more specifically to methods for increasing the rate at which hierarchical address filtering, such as the network address contained in a packet, can be performed.
BACKGROUND OF THE INVENTION
Address translation is the process of mapping an address, such as the network address contained in a packet, to some desired information. Examples of desired information include determining the output port of a switch to which a packet should be sent, or determining the address of the next-hop router for the routing of IP (Internet Protocol) datagrams. Address filtering is similar to address translation, except that instead of finding the data associated with some address, it is only important to determine whether a given address exists in a table of addresses. Throughout this disclosure, the phrase “address translation” encompasses both address translation and address filtering.
Addresses can be placed into two categories with regard to processing: flat and hierarchical. Flat addresses are those addresses that have no internal structure that is useful from a processing aspect. Ethernet addresses are an example of a flat address. Although Ethernet addresses have some structure to them (e.g., one part of the Ethernet address denotes the manufacturer of the equipment using the given Ethernet address), the structure is not relevant to protocol processing operations, such as routing. Many techniques have been developed for accelerating flat address translation.
Hierarchical addresses are those addresses that have an internal structure that is useful for protocol processing. Examples of hierarchical addresses include IPv4 addresses, IPv6 addresses, E.164 addresses (used in ATM-asynchronous transfer mode), and telephone numbers. To better illustrate the internal structure of a hierarchical address, a telephone number is used . Consider a telephone number: (908) 979-1010. The highest level of the hierarchy is denoted by the “area code” 908. The next level of the hierarchy is the “central office code” 979. The lowest level of the hierarchy is the “station number” 1010. The hierarchical structure of the telephone number is used to determine how to route a call through the telephone network. For example, if a call both originates and terminates in the
979
central office, then the phone call passes only through the
979
central office. If a call both originates and terminates in the
908
area, then no long-distance carrier is used to carry the call. Note that a flat address is a hierarchical address with a single level of hierarchy. Thus, any address translation techniques that operate on hierarchical address can be applied to flat addresses as well.
The main importance of the structure of hierarchical addresses is that there is no need to store information about every single address in order to be able to process all addresses. Information about entire classes of addresses can be stored in a single entry. For example, for a call that originates from area code 908 and terminates in some other area code, the correct action is to forward the call to a long distance carrier, regardless of the specific terminating area code.
The tables used for hierarchical address translation can be thought of as a sieve. Consider the following example, as shown in
FIG. 1
, of a translation table that might exist in the
979
central office switch (X's represent “wildcard” or “don't care” values that match all digits). Telephone numbers are compared with table entries in order from top to bottom looking for a matching entry. The telephone number 908 979 1035 would match entry A in the table, and the call would be routed to the station number 1035. The telephone number 201 829 5136 matches entry D of the table and would be routed to a long distance carrier for transport. Note that any telephone number that matches an entry also may match some of the entries that follow. The fact that entries are examined in order assures that routine is done correctly.
Other methods can be used to search the table that will provide the same result as if the table were searched serially. One technique is to use a tree structure, such as a PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric) tree.
The Art of Computer Programming
(Knuth),
Introduction to Algorithms
(Cormen, Leiserson, and Rivest). The search begins at the root of the tree, which corresponds to the top of the hierarchy.
FIG. 2
depicts such a search method and comprises the table of
FIG. 1
re-arranged as shown in FIG.
2
. The first comparison would be against just the area code 908. If 908 were found, then the entries indented under 908 would be searched. Otherwise, the call will match the last line and be routed to a long distance Point-of-Presence.
Another alternative would be to search all entries in parallel. As shown in
FIG. 3
, the table can be augmented with explicit hierarchical levels assigned to each table entry. The telephone number 908 979 1035 matches table entries A, C and D. The desired match is entry A, which has the highest level number (3 in this case, i.e., only two entries need to be delineated A & B. The word “address” as used above may actually be a combination of data fields from a packet header that is treated as a single address for purposes of address translation. For example, the address may be a combination of source address, destination address and priority fields. It should be noted that any combination of different header elements forms a single hierarchical address, in which the different elements form part of the structure of the hierarchical address.
However, these approaches are limited by the constraints of software processing speeds and comparisons with table entries are typically performed in sequential order. Thus, as network communication speeds increase, it becomes necessary to find high-speed translation techniques to operate at wirespeed.
One way to achieve wirespeed is to utilize a content-addressable memory (CAM). CAMs differ from conventional RAM (random access memory), SRAM (static RAM) and DRAM (dynamic RAM) in that they are organized differently. In a CAM, data is stored in locations in an arbitrary fashion. The locations can be selected by an address bus, or the data can be written directly into the first empty location because every location has a special status bit that keeps track of whether the location has valid information in it or is empty and available for overwriting. Once information is stored in a memory location, it is found by comparing every bit in memory with data placed in a special Comparand register. CAMs also comprise a mask register which allows selection of which bits will participate in the comparison. If there is a match for every bit in a location with every corresponding bit in the Comparand register, a Match Flag is asserted to the user know that the data in the Comparand register was found in memory. A priority encoder sorts out which matching location has the top priority, if there is more than one, and makes the address of the matching location available to the user. Thus, a CAM is a memory device that allows retrieval of information by specifying part of the stored information, rather than by specifying a storage address. For example, using masking, if the entries hex “abcd,” “abde” and “accd” were stored in a CAM, the CAM could be instructed to return the complete contents of the entries of all locations beginning “ab.” In this example, the CAM would return entries “abcd” and “abde.”
CAMs are generally classified as either binary or ternary CAMs. Binary CAMs store binary entries, while ternary CAMs store ternary entries (see PCT Application No. PCT/US97/13216, WO98/07160). Binary entries are entries that contain only 0 or 1 values, while ternary entries are entries that contain 0, 1, or X (i.e., “don't care”) values. Note that a single ternary entry can be expressed as two or more binary entries. In other words, a single ternary entry “1X0” can be repre
Arnold Tyler
Feldmeier David
Anderson Matthew D.
Caesar Rivise Bernstein Cohen & Pokotilow Ltd.
Kim Matthew
Music Semiconductors, Inc.
LandOfFree
Partially ordered cams used in ternary hierarchical address... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Partially ordered cams used in ternary hierarchical address..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Partially ordered cams used in ternary hierarchical address... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2449340