This chapter is from the book
This chapter is from the book
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 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 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 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 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 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 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 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 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.