Home > Articles > Networking

This chapter is from the book

Understanding CEF-Based MLS

The leading-edge Catalyst switches, as listed in Table 9-1, use the CEF-based MLS forwarding model to download the control plane information such as the access lists to the data plane on the supervisor, port, or line card for hardware switching of packets. In the context of this chapter, the control plane represents the Layer 3 engine (route processor), and the data plane represents the hardware components such as ASICs used by the switch for hardware switching.

CEF is a topology-based forwarding model in which all routing information is pre-populated into a forwarding information base (FIB) and Layer 2 rewrite information is dynamically updated in an adjacency table. As a result of the pre-population of routing information, Catalyst switches can quickly look up routing information such as IP adjacencies and next-hop IP and MAC addresses.

The two main components of CEF are as follows:

  • Forwarding information base (FIB)—CEF uses an FIB to make IP destination prefix-based switching decisions. The FIB is conceptually similar to a routing table or information base. It maintains a mirror image of the forwarding information contained in the IP routing table. When routing or topology changes occur in the network, the IP routing table is updated, and those changes are reflected in the FIB. The FIB maintains next-hop address information based on the information in the IP routing table. In the context of CEF-based MLS, both the Layer 3 engine and the hardware-switching components maintain an FIB.
  • Adjacency tables—Network nodes in the network are said to be adjacent if they can reach each other with a single hop across a link layer. In addition to the FIB, CEF uses adjacency tables to store Layer 2 addressing information. The adjacency table maintains Layer 2 addresses for all FIB entries. As with the FIB, in the context of CEF-based MLS, both the Layer 3 engine and the hardware-switching components maintain an adjacency table.

Figure 9-2 depicts CEF-based MLS logically, applied to the Catalyst 6500 family of switches.

Figure 9-2

Figure 9-2 Logical Depiction of CEF-Based MLS on the Catalyst 6500 Family of Switches

CEF-based MLS separates the control plane hardware from the data plane hardware switching. Nevertheless, the control plane is responsible for building the FIB table and adjacency tables in software and then downloading this information to the data plane.

On the Catalyst 6500 family of switches, the control plane hardware is easily distinguishable from the data plane hardware, especially in the case of hybrid software. The Catalyst 6500 MSFC daughter card is responsible for the control plane operations, whereas the Supervisor and PFC module are responsible for the data plane operations. The Catalyst 3550, 3560, 3750, and 4500 families of switches do not have distinguishable control plane and data plane modules or daughter cards.

Catalyst switches do not support routing of all types of frames in hardware. For example, the following list details common frame types that are not supported by hardware switching:

  • Packets with IP header options
  • Packets sourced from or destined to tunnel interfaces
  • Packets using Ethernet encapsulation types other than ARPA
  • Packets that require fragmentation

Upcoming models of Catalyst switches may support these frame types in hardware. In addition, each Catalyst switch family has its own distinct list of frames not supported by hardware switching.

Centralized and Distributed Switching

CEF-based Catalyst switches support one of two methods of hardware switching at Layer 3:

  • Centralized switching—Centralized switching carries out forwarding decisions on a specialized ASIC that is central to all interfaces of a Layer 3 switch. With centralized switching, routing, ACL, QoS, and forwarding decisions are made on the Supervisor Engine in a modular chassis or by Layer 3 engines in fixed port density Layer 3 switches. As a result, all frames to be routed or switched must pass through the centralized engine via a fabric or bus. Furthermore, with centralized switching, the hardware-switching performance of the Catalyst switch is based on the central forwarding engine and the fabric or bus architecture. Figure 9-3 illustrates centralized switching, logically. Note in Figure 9-3 how frames must pass through the centralized switching engine.

    Figure 9-3

    Figure 9-3 Logical Representation of Centralized Switching

    Examples of Catalyst switches that are engineered for centralized switching are the Catalyst 4500 family of switches and the Catalyst 6500 family of switches without the use of Distributed Forwarding Cards (DFC).

  • Distributed switching—With distributed switching, interfaces or line modules on Layer 3 switches handle forwarding decisions independently. With distributed switching, a centralized switching engine synchronizes Layer 3 forwarding, routing, and rewrite tables to local tables on distributed switching–capable modules. As a result, individual line cards or ports make forwarding decisions without the aid of the centralized switching engine; frames pass between ports directly across the fabric. In other words, switches using distributed switching place additional copies of the CEF FIB and adjacency table on line modules or interfaces for routing and switching of frames. System performance with distributed switching is equal to the aggregate of all forwarding engines. Distributed forwarding enables Catalyst switches to achieve rates of over 100 million pps. The Catalyst 6500 supports distributed switching through the use of the Switch Fabric module or with a Supervisor 720 that has an integrated fabric and DFC line modules. The Catalyst 6500 maintains use of a centralized distributing switching engine even when using distributed switching–capable line modules for backward-compatibility. Figure 9-4 illustrates distributed switching logically.
    Figure 9-4

    Figure 9-4 Logical Representation of Distributed Switching

Address Resolution Protocol Throttling

An important feature of CEF-based Catalyst switches is Address Resolution Protocol (ARP) throttling; this feature requires explanation before CEF-based MLS is explored further. Make note that the ARP table builds the CEF adjacency table. This concept is explored in more detail throughout this chapter; however, it is important to consider when reading this section.

When a router is directly connected to a segment shared by multiple hosts such as Ethernet interfaces, the router maintains an additional prefix for the subnet. This subnet prefix points to a glean adjacency. When a router receives packets that need to be forwarded to a specific host, the adjacency database is gleaned for the specific prefix. If the prefix does not exist, the subnet prefix is consulted, and the glean adjacency indicates that any addresses within this range should be forwarded to the Layer 3 engine ARP processing.

One example where glean adjacencies are used is where a Catalyst switch receives a packet for which no rewrite information exists. In order to obtain rewrite information, the Layer 3 engine sends ARP requests to obtain the rewrite information. Catalyst switches using CEF-based MLS forward only the first several packets to the Layer 3 engine for new destinations without rewrite information. The switch installs a throttling adjacency such that the switch drops subsequent packets to the specific destination address in hardware until an ARP response is received. The switch removes the throttling adjacency when an ARP reply is received from the Layer 3 engine (and a complete rewrite adjacency is installed for the host). The switch removes the throttling adjacency if no ARP reply is seen within 2 seconds (to allow more packets through to the Layer 3 engine to reinitiate ARP). This relieves the Layer 3 engine from excessive ARP processing (or ARP-based denial-of-service [DoS] attacks).

Figure 9-5 shows an example of ARP throttling; an explanation of its stepwise behavior follows. Figure 9-5 depicts the Layer 3 forwarding engine and hardware switching forwarding engine as two separate hardware components for illustrative purposes.

Figure 9-5

Figure 9-5 ARP Throttling Example

ARP throttling consists of the following steps:

Step 1

Host A sends a packet to host B.

Step 2

The switch forwards the packet to the Layer 3 engine based on the "glean" entry in the FIB.

Step 3

The Layer 3 engine sends an ARP request for host B and installs the drop adjacency for host B in hardware.

Step 4

Host B responds to the ARP request.

Step 5

The Layer 3 engine installs adjacency for host B and removes the drop adjacency.

Figure 9-9, later in this chapter, builds on Figure 9-5 to show CEF-based MLS in a larger context.

Switching Table Architectures

Multilayer switches build routing (CEF FIB and adjacency), bridging, QoS, and ACL tables for centralized or distributed switching in hardware using high-speed memory tables. Switches perform lookups in these tables for result information, such as to determine whether a packet with a specific destination IP address is supposed to be dropped according to an ACL. These tables support high-performance lookups and search algorithms such that multilayer switches maintain line-rate performance.

Multilayer switches deploy these memory tables using specialized memory architectures, referred to as content addressable memory (CAM) and ternary content addressable memory (TCAM). CAM tables provide only two results: 0 (true) or 1 (false). CAM is most useful for building tables that search on exact matches such as MAC address tables. TCAM provides three results: 0, 1, and "don't care." TCAM is most useful for building tables for searching on longest matches such as IP routing tables organized by IP prefixes.

In addition, Catalyst switch architecture supports the ability to perform multiple lookups into multiple distinct CAM and TCAM regions in parallel. As a result of this ability to perform multiple lookups simultaneously, Catalyst switches do not suffer any performance degradation by enabling additional hardware-switching features such as QoS and IP ACL processing.

CAM

Catalyst switches use CAM tables to house, for example, Layer 2 switching tables. Switches match results in CAM tables in binary (0 or 1 operations). With CAM tables, switches must find exact matches or use a default behavior. For example, in the case of Layer 2 switching tables, the switch must find an exact match to a destination MAC address or flood the packet out all ports in the VLAN.

The information that a switch uses to perform a lookup in a CAM table is called a key. For example, a Layer 2 lookup would use a destination MAC address and a VLAN ID as a key. Figure 9-6 depicts the use of keys in determining results using CAM.

Figure 9-6

Figure 9-6 Content Addressable Memory

The following steps detail the process of determining a result based on a key:

Step 1

The switch feeds the key into a hashing algorithm for searching the CAM for a matching key.

Step 2

The hashing algorithm returns a pointer into the CAM table for the matched entry.

Step 3

The switch accesses the pointer and finds the result without searching the entire table sequentially.

In the case of Layer 2 tables, CAM tables contain information such as destination VLAN, destination MAC address, and destination ports.

Switches do not always search for an exact match in memory tables. For example, a switch that is looking up an IP route destination subnet with a 24-bit mask is concerned only with the first 24 bits of an IP address (i.e., the prefix). In this case, the switch is not looking for an exact match in CAM but rather a match on the first 24 bits of the IP address.

TCAM

TCAM is a specialized CAM designed for rapid table lookups. For example, the Catalyst 2950, 3550, 3560, 3750, 4500, and 6500 families of switches use TCAM to handle ACL lookups at line rate. As a result of using TCAM, applying ACLs does not affect the performance of the switch.

TCAM populates a limited number of entries, which varies per platform, with pattern values and mask values, each with an associated result. These are known as value, mask, and result (VMR) entries, respectively. The term VMR simply refers to the format of entries in TCAM.

The "value" in VMR refers to the pattern that is to be matched; examples include IP addresses, protocol ports, DSCP values, and so on. The "mask" refers to the mask bits associated with the pattern and determines the prefix. The "result" refers to the result or action that occurs in the case where a lookup returns a hit for the pattern and mask. This result might be a "permit" or "deny" in the case of a TCAM for ACLs. Another example of a result is a pointer to an entry in the hardware adjacency table that contains the next-hop MAC rewrite information in the case of a TCAM used for IP routing.

The TCAM structure is broken into a series of patterns and masks. Masks are shared among a specific number of patterns by using wildcard-specific content fields. To perform a lookup in a TCAM table, the switch checks all entries in parallel. The performance is independent of the number of entries. This allows a switch to use the longest match lookup when needed, and it provides fixed latency to unused fields.

Figure 9-7 illustrates a sample logical depiction of TCAM used for access lists in hardware. This figure represents the access list shown in Example 9-1.

Figure 9-7

Figure 9-7 Sample TCAM Illustration

Example 9-1. Sample ACL for Figure 9-7

access-list 101 permit ip host 10.1.1.1 any

access-list 101 deny ip 10.1.1.0 0.0.0.255 any log

Moreover, TCAM defines three different match options that correlate to specific match regions. These match regions are as follows:

  • Exact-match region—Consists of Layer 3 entries for regions such as IP adjacencies. IP adjacencies are the next-hop information (MAC address) for an IP address. Other examples of exact-match regions are Layer 2 switching tables and UDP flooding tables.
  • Longest-match region—Consists of multiple "buckets" or groups of Layer 3 address entries organized in decreasing order by mask length. All entries within a bucket share the same mask value and key size. The buckets change their size dynamically by borrowing address entries from neighboring buckets. Although the size of the whole protocol region is fixed, several platforms support configuration of the region size. For most platforms, the reconfigured size of the protocol region is effective only after the next system reboot.
  • First-match region—Consists of regions that stop lookups after the first match of the entry. An example of when a first-match region is used is for ACL entries.

Table 9-2 illustrates the common protocol regions, lookup type, and key size found on Catalyst switches. The size of the regions and the ability to configure the region varies on each Catalyst switch family.

Table 9-2. Common TCAM Protocol Regions

Region Name

Cisco IOS Region Name

Lookup Type

Key Size

Sample Result

IP adjacency

ip-adjacency

Exact-match

32 bits

MAC address rewrite info

IP prefix

ip-prefix

Longest-match

32 bits

Next-hop routing information

IP multicast

ip-mcast

Longest-match

64 bits

Next-hop routing information

Layer 2 switching

l2-switching

Exact-match

64 bits

Destination interface and VLAN

UDP flooding

udp-flooding

Exact-match

64 bits

Next-hop routing or MAC address rewrite info

Access lists

access-list

First-match

128 bits

Permit, deny, or wildcard

CEF-Based MLS Operation and Use of TCAM

The following list details the characteristics of CEF-based MLS operation and its use of the TCAM:

  • Longest-match lookups in the FIB table are done for the Layer 3 destination address prefixes.
  • CEF uses the IP routing table on the Layer 3 forwarding engine to build the FIB. Arrangement of the FIB is for maximum lookup throughput.
  • CEF builds the adjacency table from the ARP table. The adjacency table contains Layer 2 rewrite (MAC) information for the next hop.
  • FIB entries in the TCAM table are populated from the most specific to the least specific entry.
  • Adjacency (rewrite) information and statistics are maintained by specialized components.
  • CEF maintains one-to-one CEF-to-adjacency mappings for accurate statistics tracking.
  • When the FIB table in TCAM is full, a wildcard entry redirects unmatched entries to the software switching Layer 3 forwarding engine.
  • When the adjacency table in TCAM is full, an entry in the FIB table points to the Layer 3 forwarding engine to redirect the adjacency lookup.
  • FIB and adjacency tables are dynamically updated when an ARP entry for a destination next hop changes, ages out, or is removed; the routing table changes; or next-hop rewrite information changes.

Sample CEF-Based MLS Operation

Figure 9-8 provides an example of CEF-based MLS operation.

Figure 9-8

Figure 9-8 Sample of CEF-Based MLS Operation

Before a multilayer switch can route frames in the hardware, it sets up the necessary routing information in the hardware. After the switch has set up the necessary routing information in the hardware, frame routing in the hardware can start. The following steps illustrate an example of frame routing via hardware switching based on Figure 9-8. Figure 9-9 illustrates the steps. These steps assume the switch does not initially have rewrite information for the destination:

Step 1

Host A sends a packet to host B. The switch recognizes the frame as a Layer 3 packet because the destination MAC (0000.000c.0001) matches the Layer 3 engine MAC.

Step 2

The switch performs a CEF lookup based on the destination IP address (10.20.10.2) in the hardware. The packet hits the CEF FIB entry for the connected (VLAN 20) network and is redirected to the Layer 3 engine using a "glean" adjacency. The hardware-switching CEF table cannot forward this packet because it does not have rewrite information.

Step 3

The Layer 3 engine installs an ARP throttling adjacency in the switch for host B's IP address, because an ARP entry does not exist for host B since host A and B have not previously communicated.

Step 4

The Layer 3 engine sends an ARP request for host B on VLAN 20.

Step 5

Host B sends an ARP response to the Layer 3 engine.

Step 6

The Layer 3 engine installs the resolved adjacency in its local adjacency table and the hardware-switching components install the adjacency as well (removing the ARP throttling adjacency).

Step 7

The switch receives another packet for host B (10.20.10.2).

Step 8

The switch performs a Layer 3 lookup and finds a CEF entry for host B. The entry points to the adjacency with rewrite information for host B.

Step 9

The switch rewrites packets per the adjacency information (source and destination MAC address) and forwards the packet to host B on VLAN 20.

Figure 9-9

Figure 9-9 Stepwise Example of CEF-Based MLS Operation

CEF-Based MLS Load Sharing

CEF-based MLS does support load sharing (equal-cost or nonequal-cost). However, CEF-based MLS does not support all the load-sharing features found in software-based CEF. With the current version of software on a Catalyst 6500 switch, a single FIB entry may have up to six adjacencies for load sharing per destination.

To achieve evenly distributed load balancing across multiple interfaces, CEF-based MLS selects a particular adjacency based on the hash (mathematical equivalent) of the following packet characteristics:

  • Source IP address
  • Destination IP address
  • Source and destination IP Layer 4 ports

The load-sharing method and hashing algorithms vary slightly per Catalyst switch family. Consult the product documentation for specifics about load-sharing support on each Catalyst switch.

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

Overview


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information


To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

Newsletters

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information


Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.

Security


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

Children


This site is not directed to children under the age of 13.

Marketing


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information


If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

Choice/Opt-out


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information


Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents


California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure


Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

Links


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020