Source: http://www.google.com/patents/US7327727?dq=6272333
Timestamp: 2016-07-01 10:37:36
Document Index: 422911175

Matched Legal Cases: ['art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500', 'art 500']

Patent US7327727 - Atomic lookup rule set transition - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsPerforming atomic lookup rule set transitions. A method involves performing lookups using a first set of rules, flagging a subset of the first set of rules as old rules, adding a second set of rules while continuing to perform lookups using the first set of rules, and atomically transitioning to perform...http://www.google.com/patents/US7327727?utm_source=gb-gplus-sharePatent US7327727 - Atomic lookup rule set transitionAdvanced Patent SearchPublication numberUS7327727 B2Publication typeGrantApplication numberUS 10/449,628Publication dateFeb 5, 2008Filing dateMay 30, 2003Priority dateJun 4, 2002Fee statusPaidAlso published asUS20030223421Publication number10449628, 449628, US 7327727 B2, US 7327727B2, US-B2-7327727, US7327727 B2, US7327727B2InventorsScott Rich, Sandeep Lodha, Ram Krishnan, Robert PfileOriginal AssigneeLucent Technologies Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (3), Referenced by (16), Classifications (17), Legal Events (6) External Links: USPTO, USPTO Assignment, EspacenetAtomic lookup rule set transition
US 7327727 B2Abstract
Performing atomic lookup rule set transitions. A method involves performing lookups using a first set of rules, flagging a subset of the first set of rules as old rules, adding a second set of rules while continuing to perform lookups using the first set of rules, and atomically transitioning to perform lookups using the first set of rules plus the second set of rules minus the old rules. A system implementing the method includes a lookup table and a lookup table management module that is configured to make atomic lookup rule set transitions in the lookup table.
This application is entitled to the benefit of provisional Patent Application Ser. No. 60/385,918, filed 4 Jun. 2002.
The invention relates to performing lookups at network nodes, and more particularly to transitioning between lookup rule sets used for lookups.
Internet protocol (IP) routing involves transmitting packets from a source to a destination through a series of hops. Lookups are performed frequently in the process of handling network traffic. For example, lookups may be used to implement an access control list (ACL), policy routing, rate shaping, and quality of service (QoS). Determining the next hop of a packet involves, for example, looking up the destination address of the packet in a route lookup table. When performing a lookup, information from incoming packets, such as header information, is used to compare against information stored in a lookup table to determine how the packet should be handled. In the process of handling network traffic, multiple hookups may be performed using information from different protocol layers, such as layer three (3) and layer four (4), where the layers are defined by the International Standards Organization (ISO) in the Open System Interconnection (OSI) model. As defined in the OSI model, layer 3 (L3) (also referred to as the network layer) is used to route data to different routers based on destination IP addresses. Layer 4 (L4) (also referred to as the transport layer) can be used to ensure delivery of an entire file or message. L3 lookups are commonly performed in order to determine a next hop for a packet. L4 lookups are commonly performed to implement a traffic distribution policy or for access control.
CAM arrays are now being used as a way to speed route table lookups. “Ternary” or “tertiary” CAMs are being used to perform route table lookups in networks that require longest prefix matching, such as networks that utilize Classless Inter Domain Routing (CIDR). Ternary CAMs can perform compare operations on bits that are “0”, “1”, or “X”, where “X” is a wildcard or “don't care” value. In order to accomplish compare operations on bits that are “0”, “1”, or “X”, ternary CAMs store a prefix mask word in addition to a CAM entry word. The prefix mask word associated with each CAM entry indicates the number of significant bits that must be matched in each CAM entry. That is, the prefix mask word identifies the bits that fall into the “X” category.
A method for performing atomic lookup rule set transitions involves performing lookups using a first set of rules, flagging a subset of the first set of rules as old rules, adding a second set of rules while continuing to perform lookups using the first set of rules, and atomically transitioning to perform lookups using the first set of rules plus the second set of rules minus the old rules. The atomic transition is accomplished by ignoring rules that have been flagged (e.g., the old rules). The above-described method can also be implemented in a system.
FIG. 1 depicts relevant functional blocks of a network node that forwards packets within a network.
FIG. 1 depicts relevant functional blocks of a network node 100, such as a switch or a router, that forwards packets within a network. The network node 100 includes a PHY 102, a MAC 104, a packet processor module 106, a switch fabric 116, and a lookup engine 120. The lookup engine 120 includes a CPU 108, memory 110, a CAM module 12, and an associated data memory 14. In an embodiment, the network node is an Ethernet-based switch/router.
The CAM module 212 includes a CAM 220, a comparand unit 222, and a priority arbiter 224. In an embodiment, the CAM 220 includes a lookup table. In this embodiment, the lookup table stores CAM entries in CAM locations. The CAM locations are typically organized in rows of individual CAM memory cells. A CAM location includes a series of CAM memory cells that store a CAM entry word, a CAM prefix mask word, and a CAM entry result. The CAM entry word, the CAM prefix mask word associated with the CAM entry word, and the CAM entry result together define a ternary CAM entry. The CAM entry is ternary because each bit of the CAM entry word and a corresponding bit of the CAM prefix mask word together define a ternary bit that is configured to have a value of “0”, “1”, or “X” (i.e., “wildcard”). The value “0” may be referred to as “off” and the value “1” may be referred to as “on” or vice versa. Each CAM location is assigned a CAM index that identifies the CAM entry. In an embodiment, a CAM array has 64K CAM locations that are indexed from 0 to 65,535.
The comparand structure is a comparand register (not shown) of the comparand unit. The comparand unit applies a comparand to the CAM 220. The comparand is compared with each ternary CAM entry. Each bit of a ternary CAM entry matches a corresponding bit of the comparand when the bit of the ternary CAM entry either has the same value as the corresponding bit of the comparand or has a value of “X” (“wildcard”). Since the comparand is compared with each ternary CAM entry, the ternary CAM entries may be referred to more generally as comparand keys. Accordingly, henceforth, the more general term comparand key is used when referring to lookup table entries.
FIG. 3 depicts an expanded view of the lookup engine 120 (FIG. 1). The lookup engine 300 includes a CAM module 312 and an associated data memory 314. The CAM module includes a lookup table 320 and a priority arbiter 324. The lookup table is populated with exemplary lookup table entries that are used below to describe an example lookup operation. Each location in the lookup table has an associated index. In the embodiment of FIG. 3, the lookup table includes 64K entries and the index values range from 0 to 65,535, with index 0 being at the “top” of the lookup table and index 65,535 being at the “bottom” of the lookup table. The lookup table is populated with lookup table entries, with each lookup table entry having an associated prefix length (i.e., 180.11.2.1/32). The lookup table entries and related prefix lengths are presented in the well-known convention of entry/prefix length. The lookup table entries are grouped by prefix length into prefix levels within the lookup table and lexicographically ordered according to prefix level. The prefix lengths of the lookup table entries define the prefix levels within the lookup table. In the embodiment of FIG. 3, the entries at prefix level thirty-two (/32) are followed by the entries at prefix level thirty-one (/31) and so on. The longest prefix length is considered to have the highest priority and the priority of the lookup table entries decreases as the prefix lengths decrease. In the embodiment of FIG. 3, the lookup table locations are indexed from the longest prefix length (lowest index number) to the shortest prefix length (highest index numbers) although in other embodiments the indexing can be reversed. Although thirty-two prefix levels (plus the default prefix level) are available, every prefix level may not be represented by a lookup table entry.
In accordance with an embodiment of the invention, the comparand and CAM entries use the atomic bit to achieve atomic rules set transition. In general, this is achieved by setting the comparand atomic bit to an operational value. In an embodiment, the operational value of the comparand atomic bit is off (e.g., “0”). The atomic bits of the CAM entries are also set to operational values. In an embodiment, the operational value of a CAM entry is unflagged (e.g., “X”). (It should be noted that CAM entries with either the values “0” or “1” may be referred to as flagged.) Accordingly, since an atomic bit that is off (e.g., “0”) always matches an atomic bit that is unflagged (e.g., “X”), during normal operation the atomic bit of the comparand and the atomic bits of the CAM entries match. When a new rule configuration is desired, the CAM entries that are associated with old rules (e.g., rules that were used under the old rule configuration, but are not used under the new rule configuration) are flagged by turning off their atomic bits (e.g., by changing the CAM entry atomic bits from “X” to “0”) and the CAM entries that are new (e.g., rules that were not used under the old rule configuration, but are used under the new rule configuration) are added and flagged by turning on their atomic bits (e.g., by setting the CAM entry atomic bits to “1”). Flagging the rules does not change the rule configuration since the atomic bit of the comparand continues to match the atomic bit of the old rules, but not the atomic bit of the new rules. After the rules are flagged, the atomic transition is accomplished by turning on the atomic bit of the comparand (e.g., by changing the atomic bit of the comparand from “0” to “1”). Then, the old rules (e.g., rules flagged with a “0”) are deleted and the new rules (e.g., rules flagged with a “1”) are unflagged (e.g., the CAM entries associated with the new rules have their atomic bits changed from “1” to “X”). Finally, the atomic bit of the comparand is changed back to its operational value (e.g., changed from “1” to “0”).
FIGS. 4A to 4C depict an exemplary atomic rule set transition procedure. FIG. 4A depicts three stages of preparation for an atomic rule set transition from a first configuration. At stage 1, the comparand atomic bit is off (e.g., “0”). The rule configuration includes the set of rules {A, B, C, D, F} that are respectively associated with CAM entries A-D and F. At stage 2, old rules are flagged by turning off (e.g., changing from “X” to “0”) the atomic bit of the CAM entry with which they are associated. The rule configuration is unchanged because the atomic bit of the comparand continues to match every rule illustrated in FIG. 4A. The set of old rules is {B, F}. At stage 3, new rules are added with atomic bits that are on (e.g., “1”). Again, the rule configuration is unchanged. The set of new rules is {E, G}. In an alternative, new rules are added before old rules are flagged. In yet another alternative, the new rules are added in parallel with flagging the old rules.
FIG. 4B depicts an atomic rule set transition. The CAM entries remain the same as in Stage 3 (FIG. 4A), but the atomic bit of the comparand is turned on (e.g., changed from “0” to “1”). Since the atomic bits of the old rules no longer match the atomic bit of the comparand, the configuration has been changed from the first rule configuration to a second configuration. The second configuration includes the set of rules {A, C, D, E, G}. Notably, none of the old rules are included in the configuration once a new rule is included in the configuration. Similarly, none of the new rules are included in the configuration while an old rule is included in the configuration. Therefore, the transition is atomic.
FIG. 4C depicts three stages following an atomic rule set transition to a second configuration. Stage 4 illustrates the state of the comparand and CAM entries immediately following the atomic transition of FIG. 4B. At stage 5, the CAM entries with atomic bits that are off (e.g., “0”) are deleted and CAM entries with atomic bits that are on (e.g., “1”) are unflagged (e.g., the atomic bits are changed from “1” to “X”). At stage 6, the atomic bit of the comparand is turned off (e.g., changed from “1” to “0”). Since the operational value of the comparand is off and the operational values of the CAM entries are unflagged, stage 6 illustrates the state of the CAM entries and comparand when set back to their operational values.
Referring once again to FIG. 3, it should be apparent from the discussion of FIG. 4A, above, that the CAM 320 is in stage 3 (FIG. 4A), prior to an atomic rule set transition. In other words, some of the atomic bits of the CAM entries have operational values (e.g., “X”), while others are flagged (e.g., have values of “0” or “1”). FIG. 3 depicts a lookup that has returned three CAM entries that match the comparand, including the atomic bit of the comparand, and a default match. The lookup criteria at lookup table location 2 (index 2) matches the lookup criteria of the comparand, but the atomic bit at lookup table location 2 is on (e.g., “1”) while the atomic bit of the comparand is off (e.g., “0”). Accordingly, no match is made with the lookup criteria at lookup table location 2. The exemplary lookup table entry matches are at index numbers 2501, 15500, and 15505, and the default index 65535. In the embodiment of FIG. 3, the match at lookup table location 2501 has the lowest index and therefore is identified by the priority arbiter as the highest priority match. CAM results (e.g., a pointer) from the highest priority match are then used to locate associated routing information that is stored in the associated data memory 314. The routing information is provided to a packet processor module, such as packet processor module 106, which uses the routing information to forward the associated packet.
FIG. 5A depicts a flowchart 500A of a method for performing atomic lookup table updates. It is assumed that a rule configuration is in a first (current) rule configuration when the flowchart 500A begins and in a second (new) rule configuration when the flowchart 500A ends. The flowchart 500A begins at step 502 with creating a rule set for a lookup table. In an embodiment, a user or administrator creates the rule set. Alternatively, the rule set could be learned through the implementation of a protocol (e.g., a routing protocol). At decision point 506, it is determined whether an old rule remains in the first rule configuration. If an old rule remains in the first rule configuration, the old rule is flagged at step 508 and the flowchart returns to decision point 506. Steps 506 and 508 repeat until all old rules are flagged. At decision point 510 it is determined whether a new rule has not yet been added. If a new rule has not yet been added, then it is added at step 512 and the flowchart 500A returns to decision point 510. Steps 510 and 512 are repeated until all of the new rules have been added. The order in which old rules are flagged and new rules are added is not critical, but the ability to flag old rules and add new rules in any order is an advantage of this method. For the purposes of flowchart 500A, the flagging and adding are assumed to occur in parallel. When all of the old rules have been flagged and all of the new rules have been added, an atomic transition from the first rule configuration to the second rule configuration occurs at step 514 and the flowchart 500A ends. The atomic transition occurs when the flagged (old) rules cease to be used and the new rules begin to be used. This may be accomplished using the atomic bit of each rule as the flag and setting the atomic bit of a comparand to an unflagged, non-wildcard value. For example, if the flag is off (e.g., “0”), then the atomic bit of the comparand is turned on (e.g., changed from “0” to “1”) to accomplish the atomic transition. Note that in this example the new rules should have atomic bit turned on (e.g., “1”) when added so that the new rules are not used prior to the atomic transition, but are used after the atomic transition.
FIG. 5B depicts a method of performing atomic lookup table updates in an alternate embodiment. It is assumed that a rule configuration is in a first (current) rule configuration when the flowchart 500B begins and in a second (new) rule configuration when the flowchart 500B ends. When performing lookups with the lookup table, a comparand is compared to lookup table entries. The atomic bit of the comparand matches the atomic bit of lookup table entries if the lookup table entries have atomic bits set to wildcard or the same value as the atomic bit of the comparand. It should be noted that the comparand lookup criteria must still match lookup criteria of the lookup table entries in order to establish a best match. In other words, just because the atomic bits match does not necessarily mean that the lookup criteria match. In an embodiment, the atomic bit of the comparand is off (e.g., “0”) in normal operation and the atomic bits of the lookup table entries are unflagged (e.g., “X”). Accordingly, in normal operation, the atomic bit of the comparand and the atomic bits of the lookup table entries match. The actual bit values of the atomic bits are not critical, but should be consistent.
The flowchart 500B begins at step 522 with receiving a set of new rules. Using the set of new rules, new lookup table entries are determined at step 524 and old lookup table entries are determined at step 530. The determinations at steps 524 and 530 may also include determinations of unchanged lookup table entries (not shown). No action need be taken with respect to unchanged lookup table entries as long as the unchanged lookup table entries have atomic bits that are unflagged (e.g., “X”). This is necessary because old and new rules are flagged by setting the atomic bit to different values and, in an embodiment, the atomic bit is ternary (i.e., it has only three values). After step 524, new table entries with atomic bits on (e.g., “1”) are provided at step 526 and added to the lookup table at step 528. It should be noted that, just as with every other step, steps 526 and 528 could occur simultaneously or in reverse order. After step 530, the atomic bits of old lookup table entries are off (e.g., “0”). Steps 524 to 528 and 530 to 532 may be performed serially or in parallel. After step 528 and 532, it is determined at decision point 534 whether an update has been completed. An update is completed when all new table entries have been added to the lookup table and all old table entries have been flagged in the lookup table. If the update is not complete, then the flowchart 500B waits at step 536 for the update to become complete.
Once the update is complete, the atomic bit of a comparand is turned on (e.g., changed from “0” to “1”) at step 538. This is different from the normal operation value of the comparand atomic bit. When the atomic bit is turned on, an atomic transition from the first configuration using the old rules to the second configuration using the new and unchanged rules occurs. Thus, there are no transient state rules (i.e., one or more old rules applied while one or more new rules are also being applied). In other words, every rule associated with an atomic bit that matches the atomic bit of the comparand is a non-transient rule. Since the old rules are no longer needed following the transition to the second configuration, the old lookup table entries are deleted at step 540. The old lookup table entries are identifiable because they were flagged (e.g., set to “0”) at step 532. At step 542, the atomic bits of the new entries are unflagged (e.g., changed from “1” to “X”). This makes the atomic bits of the new entries the same as the atomic bits of old unchanged rules. At step 544, the atomic bit of the comparand is turned off (e.g., changed from “1” to “0”). Since all of the rules of the second configuration have unflagged (e.g., “X”) atomic bits, turning off the atomic bit of the comparand has no effect on the application of rules. At this point, normal operation resumes with the atomic bit of the comparand off (e.g., “0”). At step 546, an associated data database related to the rules may (optionally) be cleaned up, and then the flowchart 500B ends. Cleaning up the database entails removing associated data for lookup table entries that have been deleted. If necessary, new database entries would typically be added before the atomic transition (not shown).
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6882999 *Jul 22, 2003Apr 19, 2005Microsoft CorporationURL mapping methods and systemsUS7054993 *Jan 22, 2002May 30, 2006Netlogic Microsystems, Inc.Ternary content addressable memory deviceUS20040054671 *Jul 22, 2003Mar 18, 2004Cohen Ariye M.URL mapping methods and systems* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7613167 *Nov 3, 2009Broadcom CorporationMethod and system for upstream priority lookup at physical interfaceUS7773590 *Apr 26, 2005Aug 10, 2010Cisco Technology, Inc.Combined interface and non-interface specific associative memory lookup operations for processing of packetsUS7774496 *Jun 21, 2007Aug 10, 2010International Business Machines CorporationSystem and program product for facilitating forwarding of data packets through a node of a data transfer network using multiple types of forwarding tablesUS7898985 *Apr 23, 2008Mar 1, 2011Juniper Networks, Inc.Composite next hops for forwarding data in a network switching deviceUS7987149 *Mar 12, 2007Jul 26, 2011Trilogy Intellectual Property Holdings, Inc.Configuration mapping using a multi-dimensional rule space and rule consolidationUS7990952Aug 17, 2007Aug 2, 2011Broadcom CorporationMethod for upstream priority lookup at physical interface within a wireless deviceUS8117335 *Jan 30, 2007Feb 14, 2012Oracle International CorporationService or application driven processing of network traffic using a smart routerUS8364628Jul 5, 2011Jan 29, 2013Trilogy Intellectual Property Holdings, Inc.Configuration mapping using a multi-dimensional rule space and rule consolidationUS8599721Jan 19, 2011Dec 3, 2013Juniper Networks, Inc.Composite next hops for forwarding data in a network switching deviceUS20030058837 *Sep 27, 2001Mar 27, 2003Lisa DenneyMethod and system for upstream priority lookup at physical interfaceUS20060239258 *Apr 26, 2005Oct 26, 2006Cisco Technology, Inc., A California CorporationCombined interface and non-interface specific associative memory lookup operations for processing of packetsUS20070233630 *Mar 12, 2007Oct 4, 2007Kulkarni Aditya PConfiguration mapping using a multi-dimensional rule space and rule consolidationUS20070248096 *Jun 21, 2007Oct 25, 2007International Business Machines CorporationSystem and program product for facilitating forwarding of data packets through a node of a data transfer network using multiple types of forwarding tablesUS20080037556 *Aug 17, 2007Feb 14, 2008Broadcom CorporationMethod for upstream priority lookup at physical interface within a wireless deviceUS20080181208 *Jan 30, 2007Jul 31, 2008Oracle International CorporationService Driven Smart RouterUS20110110373 *May 12, 2011Juniper Networks, Inc.Composite next hops for forwarding data in a network switching device* Cited by examinerClassifications U.S. Classification370/389, 370/392, 711/108, 709/238, 711/216, 709/204, 370/382International ClassificationH04L12/28, H04L12/56Cooperative ClassificationH04L45/00, H04L45/54, H04L49/3009, H04L45/7453European ClassificationH04L45/54, H04L45/7453, H04L49/30A, H04L45/00Legal EventsDateCodeEventDescriptionJun 25, 2003ASAssignmentOwner name: RIVERSTONE NETWORKS, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:RICH, SCOTT;LODHA, SANDEEP;KRISHNAN, RAM;AND OTHERS;REEL/FRAME:014207/0964Effective date: 20030529Dec 5, 2007ASAssignmentOwner name: LUCENT TECHNOLOGIES INC., NEW JERSEYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:RIVERSTONE NETWORKS, INC.;REEL/FRAME:020213/0306Effective date: 20060427Aug 2, 2011FPAYFee paymentYear of fee payment: 4Mar 7, 2013ASAssignmentOwner name: CREDIT SUISSE AG, NEW YORKFree format text: SECURITY INTEREST;ASSIGNOR:ALCATEL-LUCENT USA INC.;REEL/FRAME:030510/0627Effective date: 20130130Oct 9, 2014ASAssignmentOwner name: ALCATEL-LUCENT USA INC., NEW JERSEYFree format text: RELEASE BY SECURED PARTY;ASSIGNOR:CREDIT SUISSE AG;REEL/FRAME:033950/0261Effective date: 20140819Jul 27, 2015FPAYFee paymentYear of fee payment: 8RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services