System and method of a data processing pipeline with policy based routing

A method and apparatus of a network element that processes data by a network element with a data processing pipeline is described. In an exemplary embodiment, the network element receives network data and performs a policy-based routing lookup using one or more characteristics of the network data to retrieve a next hop identifier. In addition, the network element generates a key for the next hop identifier and performs a longest prefix match lookup to retrieve a forwarding result. The network element further determines a next hop interface based on the forwarding result.

FIELD OF INVENTION

This invention relates generally to data networking, and more particularly, to using a data processing pipeline for policy based routing.

BACKGROUND OF THE INVENTION

A network element can use policy-based routing (PBR) to make routing decisions based on policies set by the network administrator. When a network element receives a packet, the network element normally decides where to forward the packet based on the destination address in the packet, which is then used to look up an entry in a routing table. However, in some cases, there may be a need to forward the packet based on other criteria. For example, a network administrator might want to forward a packet based on the source address, the port the packet was received on, type of service and/or some other packet characteristic. Policy-based routing may also be based on the size of the packet, the protocol of the payload, or other information available in a packet header or payload. This permits routing of packets originating from different sources to different networks even when the destinations are the same and can be useful when interconnecting several private networks. Each different type of policy-based routing is mapped to a policy map.

The network element will store routing tables for different policy maps in different tables. Using separate tables for each of the different policy maps can lead to an inefficient use of the network element memory.

SUMMARY OF THE DESCRIPTION

A method and apparatus of a network element that processes data by a network element with a data processing pipeline is described. In an exemplary embodiment, the network element receives network data and performs a policy-based routing lookup using one or more characteristics of the network data to retrieve a next hop identifier. In addition, the network element generates a key for the next hop identifier and performs a longest prefix match lookup to retrieve a forwarding result. The network element further determines a next hop interface based on the forwarding result.

In a further embodiment, a network element that programs a longest prefix match lookup table with a data processing pipeline is described. In one embodiment, the network element receives policy-based routing forwarding information. In addition, the network element stores a policy-based routing entry in a policy-based routing lookup table based on the policy-based routing forwarding information. The network element further generates a key associated with the policy-based routing entry and stores a longest prefix match entry in a longest prefix match based on the key, wherein the longest prefix match entry includes a forwarding result.

Other methods and apparatuses are also described.

DETAILED DESCRIPTION

A method and apparatus of a network element that processes data by a network element with a data processing pipeline is described. In the following description, numerous specific details are set forth to provide thorough explanation of embodiments of the present invention. It will be apparent, however, to one skilled in the art, that embodiments of the present invention may be practiced without these specific details. In other instances, well-known components, structures, and techniques have not been shown in detail in order not to obscure the understanding of this description.

The terms “server,” “client,” and “device” are intended to refer generally to data processing systems rather than specifically to a particular form factor for the server, client, and/or device.

A method and apparatus of a network element that processes data by a network element with a data processing pipeline is described. In one embodiment, instead of using different routing tables for different policy maps for PBR instances, the network element creates special routing entries in the LPM lookup tables for different virtual routing and forwarding instances that used for the different PBR policies. In this embodiment, the network element creates a key for the LPM lookup table based on a PBR policy map identifier and an address indicator. The network element can use this key for a lookup in the LPM lookup table. In one embodiment, the key is formed by prepending an address indicator to the PBR policy map identifier. In one embodiment, the address indicator is value that is used to form a 32-bit IP address that can be used to store in the LPM lookup table. For example and in one embodiment, the address indicator is a 16-bit value of “224.0.”. In this example, the address indicator is prepended onto the PBR policy map identifier, which creates a multicast address. In one embodiment, the last byte of the resulting 32-bit IP address is set to “0” so as to create a /24 prefix. This 32-bit IP address can be added to the LPM lookup table and can subsequently be used to match on a destination IP address. In one embodiment, by prepending a multicast address indicator to the PBR policy map identifier, a multicast address is formed. In one embodiment, the network element uses the key for a lookup in the LPM lookup table. A hit in the lookup leads to a forwarding result that can be used to determine a transmitting interface for the network data.

In addition, and in another embodiment, the network element can program entries in the PBR and the LPM lookup tables. In this embodiment, the network element receives PBR forwarding information, creates a PBR entry, and stores this entry in the PBR lookup table. The PBR entry includes a policy map identifier for the PBR entry. In addition, the network element uses this policy map identifier to create an entry for the LPM lookup table. In one embodiment, the network element creates a key for the LPM lookup table based on a PBR policy map identifier and an address indicator as described above.

FIG. 1is a block diagram of one embodiment of a network element100that includes a control plane104and a data plane102. In one embodiment, the data plane102receives, processes, and forwards network data using various configuration data (e.g. packet forwarding (routing, switching, or another type of packet forwarding), security, quality of service (QoS), and other network traffic processing information). For example, for each received packet of the network traffic, the data plane determines a destination address of that packet, looks up the requisite information for that destination in one or more memories120A-C of data plane, and forwards the packet out the proper outgoing interface. The data plane102includes multiple switches106A-C that can each receive, process, and/or forward network traffic. In one embodiment, each switch106A-C includes a hardware forwarding engine112A-C and ports110A-C, respectively. In one embodiment, the network element100can be a switch, router, hub, bridge, gateway, etc., or any type of device that can communicate data packets with a network. In one embodiment, the network elements100can be a virtual machine.

In one embodiment, the control plane104includes central processing unit (CPU)108. As discussed herein, CPU108is interchangeably referred to as a control plane processor of network element100. The CPU108is used to process information for the control plane104and write configuration data for hardware forwarding engines112A-C in the switches106A-C. The information processed by CPU108includes, for example, control plane data corresponding to a plurality of different classes of control plane traffic, such as routing protocol messages, routing table messages, routing decisions messages, route update messages, unresolved traffic messages, L2 protocol messages, link aggregation control protocol messages, link layer state updates messages (e.g., spanning tree messages), link state update messages (e.g., link aggregation control protocol messages for a link aggregation group, bidirectional forwarding detection messages, etc.), exception packets that cannot be dealt with in hardware (e.g., router alerts, transmission time interval messages, maximum transmission size exceeded messages, etc.), program messages (e.g., packets from a controller instructing the programming of a network element), messages for routing table misses, time control messages (e.g., precision time protocol messages), messages for packets marked as being of interest for snooping (e.g., access control list logging and port mirroring messages), messages used to collect traffic diagnostics, address resolution messages (ARP) requests and replies, neighbor solicitation requests and replies, general communication to the control plane of the networking device, etc. CPU108processes the control plane network data to perform control management updates and/or respond with control message responses (e.g., routing decisions, protocol updates, traffic resolutions, etc.).

In one embodiment, the control plane108further includes memory114that includes operating system118that is executing various processes. In this embodiment, the processes are processes that execute the functionality of the control plane104. In one embodiment, there can be processes for quality of service, access control lists management (or other types of security), policy service, fan agent, light emitting diode agent, temperature sensor agent, database service, management service(s), processes to support networking protocols (e.g. spanning tree protocol (STP), routing protocols (e.g. such as routing information protocol (RIP), border gateway protocol (BGP), open shortest path first (OSPF), intermediate system-intermediate system (IS-IS), interior gateway routing protocol (IGRP), enhanced IGRP (EIGRP), protocol independent multicast (PIM), distance vector multicast routing protocol (DVMRP), and any/or other type or unicast or multicast routing protocol), Multiprotocol Label Switching (MPLS), and/or other types of networking protocols), network flow management applications (e.g., openflow, directflow), process manager, and/or other types of processes for other types of functionality of the network element100. In one embodiment, the operating system includes a data processing pipeline module116that controls the re-programming of the data processing pipeline described below. In one embodiment, the data processing pipeline module116can re-program the data processing pipeline by putting the data processing pipeline in a non-forwarding mode, using a standby memory, and/or using a standby data processing pipeline.

In one embodiment, the data plane102receives, processes, and forwards network data, including control plane network data, using various configuration data (e.g., forwarding, security, quality of service (QoS), and other network traffic processing information). The data plane102includes multiple switches106A-C that can each receive, process, and/or forward network traffic. Each of the switches106A-C includes multiple ports110A-C that are used to receive and transmit network data.

In one embodiment, for each received unit of network data (e.g., a packet), the data plane102determines a destination address for the network data, looks up the requisite information for that destination in one or more tables stored in the data plane, and forwards the data out the proper outgoing interface, for example, one of the interface devices106A-C. In one embodiment, each switch106A-C includes one or more hardware forwarding engines (HWFE(s))112A-C and ports110A-C, respectively. Each hardware forwarding engine112A-C forwards data for the network element100, such as performing routing, switching, or other types of network forwarding or processing.

FIG. 2is a block diagram of one embodiment of a hardware forwarding engine200that includes a data processing pipeline202and memory208. In one embodiment, the hardware forwarding engine200receives incoming network data204, processes the incoming network data204using data processing pipeline202, and outputs the processed network data206. In this embodiment, the data processing pipeline202processes the incoming network data using one or more functionalities of the pipeline. In one embodiment, each of the functionalities can provide a different functionality, such as packet forwarding functionality (routing, switching, PBR, or another type of packet forwarding), security functionality (e.g., firewall, network address translation, access control lists, and/or other types of functionalities), QoS, traffic policing, network data re-write, and/or other network traffic processing functionalities. In one embodiment, the data processing pipeline is part of hardware and, in one embodiment, it is part of an Application-Specific Integrated Circuit (ASIC).

As described above, a problem with having a policy-based routing functionality is that each separate policy map corresponds to a separate table. This is because the traditional routing table, such as a longest prefix match (LPM) lookup table, is based on making routing decisions based on the destination IP address of the incoming network data. With PBR, the routing decisions can be made based on different network data characteristics, such as source IP address, the port the network data was received on, type of service, and/or some other network data characteristic. Using separate tables for each of the policy maps can lead to an inefficient use of the network element memory.

In one embodiment, instead of using separate tables for different policy maps, the network element uses a longest prefix match lookup table to store routing entries for PBR routed entries. In this embodiment, special entries are created and stored in the LPM lookup table for PBR routed entries, where these special entries do not overlap with the traditional destination IP based routing entries (e.g., destination IP based unicast routing entries).

FIG. 3is a block diagram of one embodiment of a data processing pipeline200with policy-based routing functionality. InFIG. 3, the data processing pipeline200includes several lookup and decision engines302A-G. In one embodiment, each of the LDE302A-G performs a function on the incoming network data. For example and in one embodiment, LDE302B performs PBR. In one embodiment, PBR is forwarding mechanism to make routing decisions based on policies set by the network administrator. For example, and in one embodiment, a network administrator can setup for certain class of packets, such that these packets are forwarded using the source IP address or some other criteria of packet characteristics. In addition, the network element performs PBR lookups to determine a policy map for the network data. Furthermore, LDE302C performs bridging, LDE302D&E each perform routing, LDE302F performs QoS and packet data protocol (PDP), and LDE302G is used for ACL functionality. While in one embodiment, each LDE302A-G is illustrated as a single LDE, in alternate embodiments, each of the LDE302A-G may be one or more LDEs.

In one embodiment, the PBR entries are stored in a ternary content addressable memory (TCAM) for LDE302B. In this embodiment, the network element issues a lookup in the LDE302B to match on PBR TCAM entries. PBR TCAM entries are grouped together using a policy map identifier, which identifies a policy map for that TCAM entry. In one embodiment, the policy map identifier serves as a shared identifier for interfaces using the same policy-map.

In a further embodiment, once a PBR TCAM entry is hit, the network element reads the resulting next hop identifier associated with the PBR TCAM entry. The network element, in one embodiment, carries both the PBR Match flag (where this flag indicates whether any PBR TCAM entry is hit or not) and next hop identifier from LDE302B to the routing LDEs, LDE302D & E. In one embodiment, LDE302D&E perform normal routing lookup in LPM and Host tables. In this embodiment, the routing LDEs302D&E use destination IP address as a key for lookup in LPM and Host tables. Furthermore, the network element can re-use the routing functionality in LDE302D&E for PBR. If PBR Match flag is set, the network element transforms the next hop identifier from the PBR lookup to a mapped address and uses this mapped address as a key to perform a lookup in LPM table in default virtual routing and forwarding (VRF) instance. In one embodiment, the mapped address is chosen such that the address does not overlap with any unicast IPv4 route.

In one embodiment, the network element programs the route in LPM table so that the network element can perform a route lookup in Host Table with the destination IP address. The result from Host Table lookup will be used in case the result from the LPM lookup table indicates that the Host Table result should be used (e.g. the LPM<lookup table results points to a ReceiveRoute (Self-IP)). Basically, network data sent to Self-IP address are sent to CPU even if the network element has a PBR rule to redirect it somewhere.

In order to have a hit in LPM lookup table, the network element programs route entries in LPM lookup table. The inserted entry has the mapped address as a key and configured PBR Nexthop address(es) as a result. In one embodiment, if there is a hit in the routing table, the remaining path for the network data in the data processing pipeline200uses the routing functionality of choosing the right egress virtual interface and rewrite information. In this embodiment, if the network data needs to be bridged, LDE302C (bridging LDE) overrides the PBR routing decision. Furthermore, if there is a QoS ACL configured, corresponding actions (policing, marking, and/or other QoS actions) are performed by LDE302F on the PBR routed network data. Similarly, ingress ACL and egress ACL actions are done in LDE302G onwards on PBR routed network data. In either case, the network element still use the original destination IP for any lookups as destination IP field is not overwritten by PBR.

FIG. 4is a block diagram of one embodiment of a policy based lookup and decision engine (LDE) and a longest prefix match LDE. InFIG. 4, the PBR LDE402receives network data. In one embodiment, for each unit of network data, the PBR LDE402retrieves one or more characteristics of the network data that is used to perform a PBR lookup in the PBR LDE402. In one embodiment, the PBR LDE402can use packet characteristics such as received port number, source IP address, destination IP address, type of service bit, Internet Protocol, Layer4port, application identifier, packet attribute, another packet characteristic, and/or a combination therein. In one embodiment, the PBR entries are stored in PBR TCAM. The network element issues a lookup in LDE1 to match on PBR TCAM entries. PBR TCAM entries are grouped together using a policy map identifier, where the policy map identifier identifies a policy-map. In one embodiment, the policy map identifier serves as a shared identifier for the interfaces that are using the same policy-map. In one embodiment, PBR LDE402applies to unicast routed packets.

With the resulting PBR entry in the PBR LDE402, the network element reads the resulting next hop identifier from the PBR entry. This next hop identifier and the policy map identifier flags are forwarded to the LPM LDE416. In one embodiment, the LPM LDE416includes an LPM LUT404, NH Index406, and ECMP NH408. In this embodiment, the LPM LUT404is a lookup table (e.g., TCAM) that is used for longest prefix match lookups. In one embodiment, each entry in the LPM LUT404can include the pbdAclID, BD, IPv4 destination IP address, IPv4 source IP address, IP protocol, fragmented bit, source port, destination port, and type of service designation. In addition, this entry can further include Next hop identifier, pbrNoAction, and counterID. In one embodiment, the network element shares TCAM entries belonging to a policy-map if the same policy-map is applied on multiple routed interfaces or Switched Virtual Interfaces (SVI). The network element uses policy map identifier as sharing identifier and is part of the TCAM lookup key. In one embodiment, a policy map identifier is 6-bits. Hence, the network element can configure up to a maximum of 64 policy-maps. A policy map identifier is made part of PortVlanIvifTable and is derived in LDE0 and carried from LDE0 to LDE1 on scratchpad.

In one embodiment, with the next hop identifier from the PBR lookup, the Next hop identifier is used as a key to search in LPM table. Here are some of the points about Next hop identifier:A single Next hop identifier is used for each ACL rule. Hence, multiple TCAM entries (or subrules) created for each rule use the same Next hop identifier. However, if multiple classes use the same nexthop(s), they use different Ids.A next hop identifier is 16 bits long. The network element forms 32-bit IP address from this 16-bit value by pre-pending 224 to this id. Since 224* is a multicast address and the network element do not perform any search with the multicast address, a resulting LPM entry should not overlap with other LPM entries in the LPM table. When a PBR rule is programmed as NoAction, the network element programs a single bit in data portion of TCAM indicating it is a pbrNoAction. In this case, the network element increments the counter but set pbrMatchHit flag to ‘false’ in LDE1. Due to this, packet takes normal routing path in LDE1. In a further embodiment, the last byte of the address is set to 0 so as to create a /24 route and would be automatically added to LPM table. In one embodiment, the network element adds the route to LPM table so that the network element can perform a parallel host table lookup with the destination IP.

In one embodiment, the LPM lookup result is a forwarding indication that can be used to determine the interface used to transmit the network data. In one embodiment, the forwarding indication in an index into a NextHop Index406. In one embodiment, the Nexthop Index406is an index between the result of the LPM lookup and interfaces or multilink groups (e.g. ECMP or LAG multi-link groups). If the LPM lookup result indicates that a multilink group is used, the network element uses the ECMP nexthop408functionality to determine which interface of the multilink group is to be used for transmitting the network data.

FIG. 5is flow diagram of one embodiment of a process500to determine an interface for a packet using policy-based routing In one embodiment, process500is performed by a data processing pipeline module to determine an interface for network data, such as the data processing pipeline module116. InFIG. 5, process500begins by receiving the network data at block502. In one embodiment, the network data is a packet. At block504, process500performs a PBR lookup using one or more of the network data characteristics to determine if the network data should be processed using policy-based routing. In one embodiment, the network data characteristics can be port number, source IP address, destination IP address, type of service bit, another packet characteristic, and/or a combination therein. Process500determines if there is an entry in the PBR lookup that is a match for the network data characteristics at block506. In one embodiment, there is a match if the one or more network data characteristics of the network data match an entry in the PBR lookup table. If there not a match, process500proceeds to block508for alternative processing. If there is a match, process500proceeds to block510, where process500creates a key for the longest prefix match lookup. In one embodiment, the process500creates the key from the results of the PBR lookup (e.g., the next hop identifier as described inFIG. 3above) and an address indicator. In one embodiment, the address indicator is value that is used to form a 32-bit IP address that can be used to store in the LPM lookup table. For example and in one embodiment, the address indicator is a 16-bit value of “224.0.”. In this example, the address indicator is prepended onto the Next hop identifier, which creates a multicast address. In one embodiment, the last byte of the resulting 32-bit IP address is set to “0” so as to create a /24 route. This 32-bit IP address can be added to the LPM lookup table and can subsequently be used to match on a destination IP address. In one embodiment, by prepending a multicast address indicator to the Next hop identifier, a multicast address is formed. This can be stored in the LPM lookup table as the LPM lookup table as LPM will usually store unicast routes. Furthermore, the resulting 32-bit address is formed so that the resulting address does not overlap with one of the routes stored in the LPM lookup table. In one embodiment, by avoiding

At block512, process500performs an LPM lookup using the key. Process500determines the transmitting interface using the LPM result at block514. In one embodiment, the LPM result is an index into a nexthop table that can be used to determine an ECMP interface as described inFIG. 3above.

InFIG. 5and in one embodiment, process500uses the PBR and LPM lookup tables to determine an LPM result, which can then be used to determine a transmitting interface.FIG. 6is flow diagram of one embodiment of a process to program entries in the PBR and LPM lookup tables. In one embodiment, process600is performed by a data processing pipeline module to program entries in the PBR and LPM lookup tables, such as the data processing pipeline module116as described inFIG. 1above. InFIG. 6, process600beings by receiving a PBR routing entry at block602. In one embodiment, the PBR routing entry is that maps one or more network characteristics to a PBR policy map. At block604, process600programs the PBR routing entry in the PBR lookup table. In one embodiment, the PBR lookup table is a TCAM and the PBR entry is an entry in the TCAM. Process600generates a key for the PBR entry at block606. In one embodiment, process600generates the key by combining the policy-map identifier with an address indicator (e.g., a multicast address indicator as described above inFIG. 3). For example and in one embodiment, the address indicator is “224.0”, which when combined with the policy-map identifier, creates a multicast address of the form “224.0.<policy-map-ID>.0/24”. At block608, process600programs the LPM entry using generated key. In one embodiment, process600programs a TCAM entry for the LPM lookup table using the generated key and an associated nexthop index. In this embodiment, the generated key is a type of address that does not overlap with other unicast routes that could be programmed into the LPM lookup table (e.g., the LPM stores unicast routes and the key is a multicast based address as described above).

FIG. 7is a block diagram of one embodiment of a data processing pipeline module116that determines an interface for a packet using policy-based routing and programs entries in the PBR and LPM lookup tables. In one embodiment, the data processing pipeline module116includes a processing module702and a loading module704. In one embodiment, the processing module702includes PBR Lookup module706, Create Key module708, LPM lookup module710, and a Determine Interface module712. In one embodiment, the loading module704includes PBR Entry module714, Generate Table Key module716, and LPM Entry module718.

As shown inFIG. 8, the computer system800, which is a form of a data processing system, includes a bus803which is coupled to a microprocessor(s)805and a ROM (Read Only Memory)807and volatile RAM809and a non-volatile memory811. The microprocessor805may retrieve the instructions from the memories807,809,811and execute the instructions to perform operations described above. The bus803interconnects these various components together and also interconnects these components805,807,809, and811to a display controller and display device817and to peripheral devices such as input/output (I/O) devices which may be mice, keyboards, modems, network interfaces, printers and other devices which are well known in the art. In one embodiment, the system800includes a plurality of network interfaces of the same or different type (e.g., Ethernet copper interface, Ethernet fiber interfaces, wireless, and/or other types of network interfaces). In this embodiment, the system800can include a forwarding engine to forward network date received on one interface out another interface.

Typically, the input/output devices815are coupled to the system through input/output controllers813. The volatile RAM (Random Access Memory)809is typically implemented as dynamic RAM (DRAM), which requires power continually in order to refresh or maintain the data in the memory.

The mass storage811is typically a magnetic hard drive or a magnetic optical drive or an optical drive or a DVD ROM/RAM or a flash memory or other types of memory systems, which maintains data (e.g. large amounts of data) even after power is removed from the system. Typically, the mass storage811will also be a random-access memory although this is not required. WhileFIG. 8shows that the mass storage811is a local device coupled directly to the rest of the components in the data processing system, it will be appreciated that the present invention may utilize a non-volatile memory which is remote from the system, such as a network storage device which is coupled to the data processing system through a network interface such as a modem, an Ethernet interface or a wireless network. The bus803may include one or more buses connected to each other through various bridges, controllers and/or adapters as is well known in the art.

A machine readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine readable medium includes read only memory (“ROM”); random access memory (“RAM”); magnetic disk storage media; optical storage media; flash memory devices; etc.

FIG. 9is a block diagram of one embodiment of an exemplary network element900that determines an interface for a packet using policy-based routing. InFIG. 9, the midplane906couples to the line cards902A-N and controller cards904A-B. While in one embodiment, the controller cards904A-B control the processing of the traffic by the line cards902A-N, in alternate embodiments, the controller cards904A-B, perform the same and/or different functions (e.g., determines an interface for a packet using policy-based routing as described inFIGS. 3-6above). In one embodiment, the line cards902A-N processes network data. It should be understood that the architecture of the network element900illustrated inFIG. 9is exemplary, and different combinations of cards may be used in other embodiments of the invention.