Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-01-05
2001-05-22
Bragdon, Reginald G. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S212000
Reexamination Certificate
active
06237061
ABSTRACT:
BACKGROUND
1. Field of Invention
This invention relates generally to Internet Protocol addressing and specifically to using a ternary CAM to implement Classless Inter-Domain Routing functions.
2. Description of Related Art
Packets of data are relayed across the Internet according to an Internet Protocol (IP) addressing scheme. One commonly used IP addressing scheme is known as IPv4. An IPv4 address is a 32-bit binary address represented as a dotted decimal of the form M.N.O.P, where M, N, O and P are decimal values ranging from 0-255. Each 32-bit IPv4 address includes a Network ID field and a Host ID field, where the network ID field contains the address of the destination network, e.g., an Internet Service Provider (ISP) such as, for instance, America Online, and the host ID field contains the address of the destination host, e.g., a corporate network such as, for instance, IBM Corporation. When sending a data packet across the Internet from a source to a destination, the destination address is compared with address routing entries in a content addressable memory (CAM) associated with the source network to determine, for example, the best path over which to send the data packet to the destination network. Here, the network ID field bits of the incoming destination address are compared with corresponding bits of the CAM routing table entries and, if there is a match, the packet is routed to the destination network according to routing data associated with the matching CAM entry. During this CAM search, the host ID field bits of all routing entries in the CAM are masked using a well known global masking function. Typically, after the data packet is received at the destination network, the host ID field bits of the destination address are then compared with the corresponding host ID field bits of CAM routing entries associated with the destination network to determine the best path over which to route the packet to its destination host.
IPv4 addresses are segmented into Classes depending upon the number of bits in the network ID and host ID fields. Referring to
FIG. 1
, Class C IPv4 addresses have an 8-bit network ID field and a 24-bit host ID field, Class B IPv4 addresses have a 16-bit network ID field and a 16-bit host ID field, and Class A IPv4 addresses have a 24-bit network ID field and an 8-bit host ID field. Thus, if a particular company requires less than 2
8
=256 addresses, Class C IPv4 addressing provides the most efficient addressing. Similarly, if a company requires between 2
8
and 2
16
host addresses, Class B IPv4 addressing is used and, if a company requires more than 2
16
host addresses, Class A IPv4 addressing is used. For Class C addressing, the global mask associated with the CAMs is set to mask the right-most 24-bits of the CAM routing table entries corresponding to the host ID field, as shown in FIG.
2
A. For Class B addressing, the global mask associated with the CAMs is set to mask the right-most 16-bits of the CAM routing table entries corresponding to the host ID field, as shown in FIG.
2
B. For Class A addressing, the global mask associated with the CAMs is set to mask the right-most 8-bits of the CAM routing table entries corresponding to the host ID field, as shown in FIG.
2
C.
The rapid growth of the Internet has resulted in an increase in the number of IPv4 addresses which, in turn, has necessitated a more efficient use of IP addressing. For instance, if a company requires 300 host addresses, the company would use a Class B IPv4 address. However, since a Class B IPv4 address includes a 16-bit host address for up to 2
16
=64 k possible host addresses, most of the host addresses are not used, thereby resulting in an inefficient use of IP addresses. In response thereto, a classless IP addressing scheme was developed that allows for a floating boundary between the network ID field and the host ID field. This classless IP addressing scheme, commonly known as Classless Inter-Domain Routing (CIDR), is written as a standard 32-bit IPv4 address followed by a prefix Z, i.e., IPv4/Z, where the prefix Z indicates the number of bits in the network ID field and, thus, indicates the prefix length of the CIDR address. For instance, a CIDR address of 168.69.48.112/12 has a 12-bit network ID field and a 20-bit host ID field.
FIG. 3
shows a CAM routing table having five CIDR address entries each having a different number of bits in its network ID field, where the prefix/Z following each address indicates the number of bits in the network ID field. The CAM entries are ordered such that the CIDR address with the longest prefix, i.e., the greatest number of bits in its network ID field, are located in the lowest numerical address of the CAM, while the CIDR address with the shortest prefix, i.e., the fewest number of bits in its network ID field, are located in the highest numerical address of the CAM. An incoming address of 168.69.43.100 is encoded into the Search Key associated with the CAM. Since only the network ID field bits of each CAM entry (e.g., CDIR address) are compared with the corresponding bits of the search key, and each CAM entry has a different number of bits in its network ID field, each CAM entry may require a different number of its bits to be masked during compare operations in order to determine which CAM entry has the most number of unmasked bits which match corresponding bits of the search key, i.e., which CAM entry has the longest matching prefix (e.g., network ID).
Here, the CAM global mask is initially set to mask none of the CAM entry bits, and then the search key is compared with all CAM entries to determine if there is a match. If there is a match, the index of the matching CAM entry is read from the CAM, as well as any associated routing data, and the data packet is routed accordingly. If there are multiple matches, the matching CAM entry with the lowest numerical CAM address, and thus by definition having the longest matching prefix, is provided. If there is not a match, the CAM global mask is changed so as to mask the least significant bit, i.e., the right-most bit, of all CAM entries, and the search key is again compared with the unmasked bits of all CAM entries. If there is a match, the matching CAM index is output as described above. If there is not a match, the global mask is changed so as to mask the 2 least significant bits of all CAM, and the resulting unmasked bits of all CAM entries are again compared with the corresponding bits of the search key. This process is repeated until either a match is found or a maximum number of mask bits has been exceeded, in which case the routing information with the incoming destination address is not contained in the CAM.
For example, referring again to the example illustrated in
FIG. 3
, the global mask is initially set to have a logic 0 value in each of its left-most 24 bits and a logic 1 in each of its right-most 8 bits, where a logic 1 indicates that corresponding bits of the search key and CAM entries are not compared. Thus, the corresponding left-most 24 bits of the search key are compared to the left-most 24-bits of each CAM entry. Here, since the result is a no match condition, the global mask is changed so as to mask the right-most 12 bits of the CAM entries, whereby the corresponding left-most 20 bits of the search key are compared with corresponding bits of each CAM entry in a subsequent compare operation. Since the result is a no match condition, the global mask is again changed so as to mask the right-most 16 bits of the CAM entries. Here, the compare operation yields a match condition and reads the CAM entry (and any associated information) which corresponds to the CIDR address 168.69.0.0/16.
Note that in the example shown in
FIG. 3
, the global mask is described as being initially set to mask the 8 right-most bits of all CAM entries, and then is incremented by 4 bits on each global mask iteration. This abbreviated global mask iteration, as opposed to mask iterations which initially have no masked bits and are incremented one bit per iteration, is possible onl
Khanna Sandeep
Nataraj Bindiganavale S.
Srinivasan Varadarajan
Bragdon Reginald G.
NetLogic Microsystems, Inc.
Paradice III William L.
Tran Denise
LandOfFree
Method for longest prefix matching in a content addressable... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for longest prefix matching in a content addressable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for longest prefix matching in a content addressable... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2447135