Patent Description:
<CIT> discloses a method in a service chaining architecture wherein a service function forwarder receives a packet with a header comprising a Service Index field which identifies a location within a service path. Service index may be decremented by Service Function Instances or proxy nodes after performing required services. <CIT> discloses a loop suppression method in transit networks, wherein a provider router evaluates a TTL attribute stored in an MPLS label field for loop detection.

According to a first aspect of the invention there is provided a service function forwarding method according to appended claim <NUM>. According to a second aspect of the invention there is provided a service function forwarder according to appended claim <NUM>.

In a network that implements service function chaining, errors that occur during transmission of service chain packets are typically difficult to detect. For example, when service chain packets repeatedly pass through a Service Function Forwarder (SFF) without the SFF invoking a service function (SF), a loop is created in the transmission of the service chain packet. Service chain packets that are transmitting on a loop may not reach the destination endpoint and may unnecessarily consume network resources.

Disclosed herein are embodiments directed to identifying when service chain packets are transmitting in a loop and identifying when an error occurs during transmission of the service chain packets. In an embodiment, service chain packets include a service header with a loop prevention field. A classifier in the network sets an initial value in the loop prevention field to <NUM> and transmits the service chain packet to an SFF. An SFF is configured to increment the value in the loop prevention field when the value is less than a predefined parameter. The SFF then sends the service chain packet to a service node (SN), which is configured to reset the value in the loop prevention field only after performing a SF on the service chain packet. Each SFF on a service function path (SFP) is configured to compare a value in the loop prevention field with a predefined parameter to determine whether to continue transmission of the service chain packet or discard the service chain packet. Performing such a comparison at each SFF may prevent loops or transmission errors from occurring and unnecessarily clogging network resources within the network.

<FIG> is a schematic diagram of a SFP-enabled network <NUM> that implements service function chaining according to an embodiment of the disclosure. A SFP-enabled network <NUM> that implements service function chaining may generate SFPs for applications sending data packets from a source <NUM> (e.g., source 118A-C) to a destination <NUM> (e.g., destination 124A-C). A SFP is an abstract sequenced set of SFs <NUM> (e.g., SFs 121A-E) that a packet, a frame, and/or a traffic flow may traverse for delivering an end-to-end service. SFs <NUM> refer to any network services, such as, for example, a firewall, an intrusion prevention system (IPS), or a server load-balancer. A SFP may be created according to SF-related information and network topology information. SF-related information may include identifiers that identify SFs <NUM> in the SFP, locators (e.g., network nodes) that identify instances of the SFs <NUM> in SFP-enabled network <NUM>, administrative information (e.g., available memory, available capacity, and central processing unit (CPU) utilization), and capability information. Network topology information may include the arrangement of the network nodes and network links in the SFP-enabled network <NUM>. The SFP may include SFFs <NUM> (e.g., SFFs 112A-C) and SNs <NUM> (e.g., SNs 115A-C). SNs <NUM> are network nodes at which the SFs <NUM> or instances of the SFs <NUM> are located and SFFs <NUM> are network nodes that forward data to the SNs <NUM> so that the SFs <NUM> may process the data.

The SFP-enabled network <NUM> may comprise a Software Defined Network (SDN) controller <NUM> in data communication with a network <NUM>. The underlying physical network of the network <NUM> may be any type of transport network, such as an electrical network and/or an optical network, and may comprise one or more network domains. The network <NUM> may employ any transport protocol, such as an Internet Protocol (IP)/User Datagram Protocol (UDP), suitable for transporting data over the underlying physical network of the network <NUM>. The network <NUM> may employ any type of network virtualization and/or network overlay technologies, such as a virtual extensible local area network (VXLAN). The network <NUM> may comprise a classifier <NUM>, one or more SFFs <NUM>, and one or more SNs <NUM>. In an embodiment, the network <NUM> is an SDN-enabled network, where the network control is decoupled from forwarding and the control plane is programmable through software controlled by a central management entity, such as the SDN controller <NUM>. For example, the SDN controller <NUM> makes routing decisions and communicates the routing decisions to all the network devices, such as the classifier <NUM>, the SFFs <NUM>, the SNs <NUM>, and any other network nodes, in the network <NUM>.

The source <NUM> and destination <NUM> in the SFP-enabled network <NUM> may each be a laptop computer, a tablet computer, a smart phone, a smart television, network site, or a code division multiple access (CDMA) phone configured to request a SFP indicating a sequence of network services or SFs <NUM> for a data flow. The source <NUM> and destination <NUM> may be coupled to the SDN controller <NUM> via a wired or wireless link.

The SDN controller <NUM> may be a virtual machine (VM), a dedicated host, a distributed system comprising a plurality of computing devices, or any other device and/or system configured to manage the network <NUM>. The SDN controller <NUM> performs SDN management and/or control operations, such as determining forwarding paths in the network <NUM> and configuring network nodes, such as the classifier <NUM>, the SFFs <NUM>, and the SNs <NUM>, with the forwarding instructions. In addition, the SDN controller <NUM> may interact with other SFP entities to facilitate the implementations of SFPs. For example, the SDN controller <NUM> may create an SFP to serve an application by determining a series of SFs <NUM>, such as firewall or policy routing, to form a composite service for implementing the application.

The classifier <NUM> may be a VM, dedicated host, a network node, such as a router and/or a switch, or any other device configured to perform classification. For example, a classifier <NUM> may be a component within an SFP ingress node, which is an SFP boundary node that handles traffic entering an SFP-enabled domain or an SFP proxy node in the SFP enabled-domain. In an embodiment, when the classifier <NUM> receives a data packet from a source <NUM> (e.g., source 118A-C), the classifier <NUM> identifies an SFP and a service flow or a SFP for the data packet. To direct the data packet along the identified SFP, the classifier <NUM> generates a service chain packet to carry both the data packet and the SFP information, for example, by encapsulating the data packet with a service header indicating the SFP information. One example of a service header may be a network service header (NSH), as described in the Internet Engineering Task Force (IETF) draft document entitled "<NPL>"), which is hereby incorporated by reference in its entirety. An example of the service header according to embodiments of the present disclosure will be further described in <FIG>. The classifier <NUM> sends the service chain packet to a next SFF 112A in the identified service flow. It should be noted that the classifier <NUM> may perform additional encapsulations over the Service chain packet, for example, according to a transport protocol and/or a network overlay (e.g., IP/UDP, VXLAN) in use.

The SFFs <NUM> are any network nodes or devices, such as router, switches, and/or bridges, configured to forward packets and/or frames received from the network <NUM> to one or more SNs <NUM> associated with the SFFs <NUM> according to information carried in the service header. When an SFF <NUM> receives a packet carrying a service header from the network <NUM>, the SFF <NUM> performs decapsulation (e.g., removal of transport header) to obtain the service chain packet. In an embodiment, the SFF <NUM> obtains a value in a loop prevention field of the service chain packet to determine whether a forwarding error has occurred during transmission of the service chain packet, as will be discussed more fully below. If a forwarding error has not occurred during transmission of the service chain packet, the SFF <NUM> determines the appropriate SFs <NUM> for processing the packet. The SFF <NUM> determines the SNs <NUM> that provide the SFs <NUM> or instances of the SFs <NUM>, for example, according to SF-to-locator mappings received from the SDN controller <NUM>. The SFF <NUM> forwards the service chain packet to the SNs <NUM> in an order (e.g., SF 121A-E). In an embodiment, when the SNs <NUM> return the SF-processed data in the service chain packet, the SFF <NUM> is configured to increment the value in the loop prevention field, as will be discussed more fully below. The SFF <NUM> may then forward the SF-processed data to another SN <NUM> or to a next SFF <NUM>. When the SFF <NUM> is a last SFF (e.g., SFF 112C) in the SFP, the SFF <NUM> may deliver the data processed by a last SF (e.g., SF 121E) to a destination <NUM> (e.g., destination 124A-C).

The SNs <NUM> may be VMs, hypervisors, or any other devices configured to process packets and/or frames according to SF <NUM> types. In one embodiment, an SN <NUM> may implement one or more SFs <NUM> which are logical entities or software components. In another embodiment, multiple occurrences of an SF <NUM> may be located in several SNs <NUM> in the same SFP-enabled domain. In some embodiments, an SN <NUM> may be the same node as the classifier <NUM>, where the SN <NUM> implements one or more SFs <NUM> and classification. Some example SFs <NUM> provided by the SNs <NUM> may include firewalls, WAN and application acceleration, server load balancing, lawful intercept, NAT, such as NAT-type <NUM> (NAT44) for Internet Protocol version <NUM> (IPv4) address translation or NAT-type <NUM> (NAT64) for IP version <NUM> (IPv6) address translation, network prefix translation (NPT), hypertext transfer protocol (HTTP) header enrichment function, and/or transport control protocol (TCP) optimizer. When an SN <NUM> receives a service chain packet from the SFF <NUM>, the SF <NUM> located at the SN <NUM> processes the data packet carried in the received service chain packet. In some embodiments, the SN <NUM> is configured to set the value in the loop prevention field of the service chain packet to <NUM> after processing the data packet, as will be discussed more fully below.

<FIG> is a schematic diagram of SFP-enabled network <NUM> implementing a loop prevention mechanism while transmitting packets along a SFP <NUM> according to an embodiment of the disclosure. <FIG> shows an example of a method of loop prevention while successfully transmitting a packet from a source 118A to a destination 124A. For example, source 118A sends a request to the SDN controller <NUM> indicating a sequence of network services or SFs <NUM> for a data flow. The SDN controller <NUM> may compute a shortest path through network <NUM> traversing a subset of the available SFs <NUM> to determine the SFP <NUM> based on the request. For the example shown in <FIG>, the subset of available SFs <NUM> included in SFP <NUM> include SF 121B, SF 121C, and SF 121D. The SFFs <NUM> corresponding to the available SFs 121B, SF 121C, and SF 121D include SFF 112A, SFF 112B, and SFF 112C, respectively. The SDN controller <NUM> may assign SF 121B, SF 121C, and SF 121D according to the request to create SFP <NUM>.

The SDN controller <NUM> may transmit the SFs <NUM> and SFFs <NUM> that are included in SFP <NUM> to classifier <NUM> such that the classifier <NUM> is configured to encapsulate a service header <NUM> onto data packets <NUM> received from an application executed at source <NUM> to be transmitted to destination <NUM> via network <NUM>. For example, an application executed at source 118A generates a data packet <NUM> comprising a payload. Source 118A may transmit the data packet <NUM> to the classifier <NUM>. The classifier <NUM> may determine the SFP <NUM> and a service flow or SFP for the data packet <NUM> based on information received from the SDN controller <NUM>. In an embodiment, the classifier <NUM> may encapsulate the data packet <NUM> with a service header <NUM> to create a service chain packet <NUM>. The service chain packet <NUM> may comprise a service header <NUM>, as the NSH. The service header <NUM> may carry SFP traffic steering information (e.g., service path information) and SFP metadata information. For example, the service header <NUM> may carry a service path identifier <NUM>, which may be defined by the classifier <NUM> or the SDN controller <NUM> to uniquely identify SFP <NUM>.

According to some embodiments, the service header <NUM> may further include a loop prevention field <NUM>. The loop prevention field <NUM> may be configured to indicate whether an error has occurred during transmission of the data packet <NUM> across network <NUM>. For example, the loop prevention field <NUM> may be created by using a number (n) of reserved bits that are available in a service header <NUM>. In an embodiment, the classifier <NUM> sets a value in the loop prevention field <NUM> to <NUM> after encapsulating the service header <NUM> onto the data packet <NUM>. For example, the value in the loop prevention field <NUM> may be set to <NUM> when the loop prevention field <NUM> includes <NUM> bits.

After the classifier <NUM> encapsulates the data packet <NUM> to create the service chain packet <NUM>, the classifier <NUM> may transmit the service chain packet <NUM> to the SFF 112A according to the service path identifier <NUM>. In an embodiment, the SFF 112A is configured to first obtain the value in the loop prevention field <NUM> and compare the value in the loop prevention field <NUM> to a predefined parameter. In an embodiment, the SFF 112A is configured to determine to continue transmission of the service chain packet <NUM> when the value in the loop prevention field <NUM> is less than the predefined parameter. In an embodiment, the SFF 112A is configured to discard the service chain packet <NUM>, or discontinue transmission of the service chain packet <NUM>, when the value in the loop prevention field <NUM> is greater than or equal to the predefined parameter.

In some embodiments, the loop prevention field <NUM> comprises at least <NUM> bits. In some embodiments, the predefined parameter is based on the number of bits (n) in the loop prevention field <NUM> such that the predefined parameter is in the range from <NUM>n-<NUM> to <NUM>n-<NUM>. For example, when the loop prevention field <NUM> has <NUM> bits, the predefined parameter is equal to <NUM> or <NUM> depending on the embodiment. In this case, each of the SFFs <NUM> along an SFP <NUM> is configured to compare the value in the loop prevention field <NUM> to the predefined parameter such as <NUM>. The predefined parameter according to embodiments of the disclosure will be more fully described below.

Continuing the example, SFF 112A obtains the service chain packet <NUM> from the classifier <NUM> with the value of the loop prevention field <NUM> being <NUM>. SFF 112A may determine that the value of the loop prevention field <NUM>, which is <NUM>, is less than the predefined parameter, such as <NUM>. In this case, SFF 112A continues to transmit the service chain packet <NUM> to SN 115A, which runs the SF 121B on the service chain packet <NUM>. For example, the SF 121B is performed on the data packet <NUM> within the service chain packet <NUM>. When SN 115A successfully performs SF 121B on the data packet <NUM>, SN 115A may be configured to reset the value in the loop prevention field <NUM> to <NUM>. When SN 115A is unable to successfully perform SF 121B on the data packet <NUM> or SF 121B is unavailable at SN 115A, the SN 115A does not change the value in the loop prevention field <NUM>.

As shown in <FIG>, SN 115A is configured to transmit the service chain packet <NUM> back to SFF 112A, where the value in the loop prevention field <NUM> is <NUM> because SN 115A successfully performed SF 121B on data packet <NUM>. Similar to when SFF 112A received the service chain packet <NUM> from the classifier <NUM>, SFF 112A may again increment the value in the loop prevention field <NUM> to <NUM>. After incrementing, SFF 112A forwards the service chain packet <NUM> to SFF 112B based on the service path identifier <NUM> in the service header <NUM>.

SFF 112B receives the service chain packet <NUM> and determines whether the value in the loop prevention field <NUM> received from SFF 112A is less than the predefined parameter. For example, SFF 112B determines that the value in the loop prevention field <NUM>, which is <NUM>, is less than the predefined parameter, such as <NUM>. In this case, SFF 112B again increments the value in the loop prevention field <NUM> to <NUM> and then continues to transmit the service chain packet <NUM> to SN 115B. SN 115B may be configured to execute SF 121C on the service chain packet <NUM>. After SN 115B successfully performs SF 121C on the service chain packet <NUM>, SN 115B may be configured to reset the value in the loop prevention field <NUM> to <NUM> and then transmit the service chain packet <NUM> back to SFF 112B. Upon receiving the service chain packet <NUM> where the value in the loop prevention field <NUM> is <NUM>, SFF 112B may again increment the value in the loop prevention field <NUM>. For example, SFF 112B increments the value in the loop prevention field <NUM> to <NUM> and forwards the service chain packet <NUM> to SFF 112C based on the service path identifier <NUM> in the service header <NUM>.

SFF 112C receives the service chain packet <NUM> and determines whether the value in the loop prevention field <NUM> is less than the predefined parameter. For example, SFF 112C determines that the value in the loop prevention field <NUM>, which is <NUM>, is still less than the predefined parameter, such as <NUM>. In this case, SFF 112C may increment the value in the loop prevention field <NUM> to <NUM> and then transmit the service chain packet <NUM> to SN 115C. SN 115C may be configured to execute SF 121D on the service chain packet <NUM>. After SN 115C successfully performs SF 121D on the data packet <NUM>, SN 115C may be configured to reset the value in the loop prevention field <NUM> to <NUM> and then transmit the service chain packet <NUM> back to SFF 112C. Upon receiving the service chain packet <NUM> where the value in the loop prevention field <NUM> is <NUM>, SFF 112C may again increment the value in the loop prevention field <NUM>. In an embodiment in which SFF 112C determines that SFF 112C is the last SFF <NUM> before the data packet <NUM> is sent to the destination 124A, SFF 112C may decapsulate the service chain packet <NUM> and send the data packet <NUM> to destination 124A.

As shown in <FIG>, the value in the loop prevention field <NUM> is incremented each time the service chain packet <NUM> reaches a SFF <NUM> and resets to <NUM> each time the service chain packet <NUM> leaves an SN <NUM> after successfully performing a service on the service chain packet <NUM>. Each time a SFF <NUM> receives the service chain packet <NUM>, the SFF <NUM> determines whether the value in the loop prevention field <NUM> is less than a predetermined parameter. When the value in the loop prevention field <NUM> is less than a predetermined parameter, SFF <NUM> determines that an error has not occurred during transmission of the service chain packet <NUM>, as shown in <FIG>.

According to the claimed invention a service function forwarding method comprises: receiving, by a service function forwarder, SFF, a first service packet, wherein the first service packet is a service chain packet comprising a service path identifier used to identify a service chain and a loop prevention field comprising a plurality of bits indicating whether an error has occurred during packet transmission; and; obtaining, by the SFF, a second service packet when the loop prevention field meets a preset condition, wherein the obtaining, by the SFF, a second service packet comprises: obtaining, by the SFF, the second service packet based on the first service packet, wherein the second service packet comprises an incremented loop prevention field; and; sending, by the SFF, the second service packet based on the service path identifier.

<FIG> is a schematic diagram of SFP-enabled network <NUM> implementing a loop prevention mechanism while transmitting packets along a SFP <NUM> according to an embodiment of the disclosure. <FIG> shows an example of a method <NUM> of loop prevention when a failure occurs during transmission of a packet from a source 118A to a destination 124A. Source 118A, destination 124A, SDN controller <NUM>, classifier <NUM>, SFFs 112A-C, SNs 115A-C, and SFs 121A-E in method <NUM> operate similar to how they did in method <NUM>, except that SFF 112C determines that an error occurs during transmission of service chain packet <NUM> and discards the service chain packet <NUM>.

Similar to method <NUM>, in method <NUM> the classifier <NUM> encapsulates the data packet <NUM> to include a service header <NUM>, creating the service chain packet <NUM>. The classifier <NUM> is configured to set the value in the loop prevention field <NUM> of the service header <NUM> to <NUM>. The classifier <NUM> transmits the service chain packet <NUM> to SFF 112A. SFF 112A first obtains the value in the loop prevention field <NUM> and compares the value with the predefined parameter, such as, in this example, <NUM>. Since the value in the loop prevention field <NUM> is <NUM> after being received from the classifier <NUM>, the value in the loop prevention field <NUM> is less than the predefined parameter. SFF 112A transmits the service chain packet <NUM> to SN 115A, which performs SF 121B on the data packet <NUM>. SN 115A resets the value in the loop prevention field <NUM> to <NUM> after successfully performing SF 121B on the service chain packet <NUM> and then forwards the service chain packet <NUM> back to SFF 112A. SFF 112A again increments the value in the loop prevention field <NUM> to <NUM> and then forwards the service chain packet <NUM> to SFF 112B.

As shown in <FIG>, SFF 112B receives the service chain packet <NUM> from SFF 112A but does not transmit the service chain packet <NUM> to SN 115B to invoke SF 121C. There may be many reasons why SFF 112B receives the service chain packet <NUM> but does not invoke a SF <NUM>. For example, SFF 112B may not actually be connected to a SN <NUM> that has a SF <NUM> which is to be performed on a data packet <NUM>. In this case, SFF 112B has received the service chain packet <NUM> by mistake, and has thus created an error in transmitting the packet from the source 118A to the destination 124A. In another case, SF 121C may be experiencing a failure such that SF <NUM> cannot transmit the service chain packet <NUM> to SN 115B to execute SF 121C. In this case, SN 115B merely receives the service chain packet <NUM> without performing a SF <NUM> on the packet and then forwards the service chain packet <NUM> to another SFF 112C, thereby causing a loop to occur within network <NUM>. An error occurs among SFFs <NUM> when one SFF <NUM> receives a service chain packet <NUM> and forwards the service chain packet <NUM> to another SFF <NUM> without performing a SF <NUM> on the service chain packet <NUM>. Such errors may result in loops occurring while transmitting the data packet <NUM> from the source <NUM> to the destination <NUM>.

When SFF 112B receives the service chain packet <NUM>, the SFF 112B first determines whether the value in the loop prevention field <NUM> is less than the predefined parameter. Since the value in the loop prevention field <NUM> is <NUM>, which is still less than <NUM>, the SFF 112B determines that the service chain packet <NUM> may continue to be transmitted. The SFF 112B is configured to increment the value in the loop prevention field <NUM> to <NUM> even though the SFF 112B does not transmit the service chain packet <NUM> to SN <NUM>. After incrementing the value in the loop prevention field <NUM>, SFF 112B transmits the service chain packet <NUM> to SFF 112C.

Upon receiving the service chain packet <NUM>, SFF 112C determines whether the value in the loop prevention field <NUM> is less than the predefined parameter. The SFF 112B incremented the value in the loop prevention field <NUM> to <NUM>, such that when SFF 112C receives the service chain packet <NUM>, the value in the loop prevention field <NUM> is no longer less than the predefined parameter, which is also <NUM>. The SFF 112C may be configured to discard the service chain packet <NUM> when the value in the loop prevention field <NUM> is greater than or equal to the predefined parameter. For example, SFF 112C may discontinue transmission of the service chain packet <NUM> when the value in the loop prevention field <NUM> is greater than or equal to the predefined parameter.

Similar to method <NUM>, the value in the loop prevention field <NUM> is incremented each time the service chain packet <NUM> reaches a SFF <NUM> and reset to <NUM> each time the service chain packet <NUM> leaves an SN <NUM> after successfully performing a service on the service chain packet <NUM>. When an SFF <NUM> forwards a service chain packet <NUM> without invoking a SF <NUM>, SFF <NUM> still increments the value in the loop prevention field <NUM>. Each time a SFF <NUM> receives the service chain packet <NUM>, the SFF <NUM> determines whether the value in the loop prevention field <NUM> is less than a predetermined parameter. When the value in the loop prevention field <NUM> is greater or equal to the predetermined parameter, SFF <NUM> determines that an error has occurred during transmission of the service chain packet <NUM>, as shown in <FIG>. In such a case, the SFF <NUM> discards the service chain packet <NUM>.

<FIG> is a schematic diagram of an embodiment of a network element (NE) <NUM> in a SFP-enabled network <NUM>. For instance, the NE <NUM> may be a classifier <NUM>, SFF <NUM>, SN <NUM>, source <NUM>, destination <NUM>, or SDN controller <NUM>. The NE <NUM> may be configured to implement and/or support the loop prevention mechanisms described herein. The NE <NUM> may be implemented in a single node or the functionality of NE <NUM> may be implemented in a plurality of nodes. One skilled in the art will recognize that the term NE encompasses a broad range of devices of which NE <NUM> is merely an example. The NE <NUM> is included for purposes of clarity of discussion, but is in no way meant to limit the application of the present disclosure to a particular NE embodiment or class of NE embodiments. At least some of the features and/or methods described in the disclosure may be implemented in a network apparatus or module such as an NE <NUM>. For instance, the features and/or methods in the disclosure may be implemented using hardware, firmware, and/or software installed to run on hardware. As shown in <FIG>, the NE <NUM> comprises one or more ingress ports <NUM> and a receiver unit (Rx) <NUM> for receiving data, at least one processor, logic unit, or CPU430 to process the data, a transmitter unit (Tx) <NUM> and one or more egress ports <NUM> for transmitting the data, and a memory <NUM> for storing the data.

The processor <NUM> may comprise one or more multi-core processors and be coupled to a memory <NUM>, which may function as data stores, buffers, etc. The processor <NUM> may be implemented as a general processor or may be part of one or more application specific integrated circuits (ASICs) and/or digital signal processors (DSPs). The processor <NUM> may comprises a loop prevention module <NUM>, which may perform processing functions of classifier <NUM>, SFF <NUM>, SN <NUM>, source <NUM>, destination <NUM>, or SDN controller <NUM> and implement methods <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, as discussed more fully below, and/or any other method discussed herein. As such, the inclusion of the loop prevention module <NUM> and associated methods and systems provide improvements to the functionality of the NE <NUM>. Further, the loop prevention module <NUM> effects a transformation of a particular article (e.g., the network) to a different state. In an alternative embodiment, the loop prevention module <NUM> may be implemented as instructions stored in the memory <NUM>, which may be executed by the processor <NUM>.

The memory <NUM> may comprise a cache for temporarily storing content, e.g., a random-access memory (RAM). Additionally, the memory <NUM> may comprise a long-term storage for storing content relatively longer, e.g., a read-only memory (ROM). For instance, the cache and the long-term storage may include dynamic RAMs (DRAMs), solid-state drives (SSDs), hard disks, or combinations thereof. The memory <NUM> may be configured to store identified misconfigurations <NUM>, which may include, for example, the service path identifiers <NUM> of SFPs that have been identified as resulting in an error during transmission of packets. The memory <NUM> may also be configured to store the predefined parameter <NUM>, which is limited by the number of bits (n) in the loop prevention field <NUM>.

It is understood that by programming and/or loading executable instructions onto the NE <NUM>, at least one of the processor <NUM> and/or memory <NUM> are changed, transforming the NE <NUM> in part into a particular machine or apparatus, e.g., a multi-core forwarding architecture, having the novel functionality taught by the present disclosure. It is fundamental to the electrical engineering and software engineering arts that functionality that can be implemented by loading executable software into a computer can be converted to a hardware implementation by well-known design rules. Decisions between implementing a concept in software versus hardware typically hinge on considerations of stability of the design and numbers of units to be produced rather than any issues involved in translating from the software domain to the hardware domain. Generally, a design that is still subject to frequent change may be preferred to be implemented in software, because re-spinning a hardware implementation is more expensive than re-spinning a software design. Generally, a design that is stable that will be produced in large volume may be preferred to be implemented in hardware, for example in an ASIC, because for large production runs the hardware implementation may be less expensive than the software implementation. Often a design may be developed and tested in a software form and later transformed, by well-known design rules, to an equivalent hardware implementation in an ASIC that hardwires the instructions of the software. In the same manner as a machine controlled by a new ASIC is a particular machine or apparatus, likewise a computer that has been programmed and/or loaded with executable instructions may be viewed as a particular machine or apparatus.

<FIG> is a protocol diagram of a method <NUM> for performing loop prevention in a network implementing service function chaining, such as SFP-enabled network <NUM>. The method <NUM> is implemented by a source <NUM>, classifier <NUM>, SFF 112A, SN 115A, SFF 112B, and SFF 112C. The method <NUM> is initiated when a source <NUM> transmits a request to a SDN controller <NUM> for the SDN controller <NUM> to determine a SFP <NUM> for data packets <NUM> transmitted from the source <NUM> to a destination <NUM>. At step <NUM>, the source <NUM> transmits a data packet <NUM> to a classifier <NUM>. For example, the Tx <NUM> of the source <NUM> transmits the data packet <NUM> to the classifier <NUM>. A Rx <NUM> of the classifier <NUM> may receive the data packet <NUM>.

At step <NUM>, the classifier <NUM> may identify a SFP <NUM> for the data packet <NUM> based on information received from the SDN controller <NUM>. In some embodiments, the classifier <NUM> may encapsulate the data packet <NUM> to include a service header <NUM>, thereby creating the service chain packet <NUM>. In some embodiments, the service header <NUM> includes a loop prevention field <NUM> that indicates whether an error has occurred during transmission of the data packet <NUM>. In an embodiment, the loop prevention field <NUM> comprises at least <NUM> bits. The classifier <NUM> may be configured to set the value in the loop prevention field <NUM> to <NUM>.

At step <NUM>, the classifier <NUM> may transmit the service chain packet <NUM> to SFF 112A based on the SFP <NUM> for the data packet <NUM>. For example, the Tx <NUM> of the classifier <NUM> transmits the service chain packet <NUM> with the value in the loop prevention field <NUM> being set to <NUM>. The Rx <NUM> of the SFF 112A may receive the service chain packet <NUM> from the classifier <NUM>. At step <NUM>, the SFF 112A determines whether the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. For example, the loop prevention module <NUM> executed by the processor <NUM> is configured to determine whether the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. As shown in <FIG>, the predefined parameter <NUM>, which is limited by the number of bits (n) in the loop prevention field <NUM>, may be equal to <NUM>n-<NUM>. The loop prevention field <NUM> used in the example shown in <FIG> includes <NUM> bits, and the predefined parameter <NUM> in the example above is equal to <NUM>. Since the value in the loop prevention field <NUM> is <NUM> when the SFF 112A receives the service chain packet <NUM> from the classifier <NUM>, the SFF 112A may determine that an error has not occurred during transmission of the service chain packet <NUM> and continue transmission. At step <NUM>, the SFF 112A also increments the value in the loop prevention field <NUM> to <NUM> when the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. For example, the loop prevention module <NUM> executed by the processor <NUM> is configured to increment the value in the loop prevention field <NUM> when the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>.

At step <NUM>, the SFF 112A transmits the service chain packet <NUM> to the SN 115A to invoke an SF <NUM> at the SN 115A. For example, the Tx <NUM> of the SFF 112A transmits the service chain packet <NUM> to the SN 115A. At step <NUM>, SN 115A invokes SF <NUM> to perform a network function on the data packet <NUM> within the service chain packet <NUM>. For example, the processor <NUM> of the SN 115A invokes SF <NUM> to perform the network function on the data packet <NUM>. At step <NUM>, the SF <NUM> successfully performs the network function on the data packet <NUM> and then resets the value in the loop prevention field <NUM> to <NUM>. For example, the processor <NUM> of the SN 115A resets the value in the loop prevention field <NUM> to <NUM>. In the case where the network function cannot be performed on the data packet <NUM> by SF <NUM> at SN 115A, the value in the loop prevention field <NUM> may remain the same and is not reset.

At step <NUM>, the SN 115A transmits the service chain packet <NUM> back to SFF 112A. For example, the Tx <NUM> of the SN 115A transmits the service chain packet <NUM> back to SFF <NUM>. When the SN 115A successfully performed SF <NUM> on the service chain packet <NUM>, the value in the loop prevention field <NUM> is <NUM>, and at step <NUM>, the SFF 112A increments the value in the loop prevention field <NUM> to <NUM>. In the case where the SN 115A is unable to perform SF <NUM> on the service chain packet <NUM>, the SFF 112A may still increment the value in the loop prevention field <NUM>. For example, the loop prevention module <NUM> executed by the processor <NUM> is configured to increment the value in the loop prevention field <NUM>.

At step <NUM>, the SFF 112A transmits the service chain packet <NUM> to SFF 112B where the loop prevention field <NUM> includes the value of <NUM>. For example, the Tx <NUM> transmits the service chain packet <NUM> to SFF 112B. At step <NUM>, the SFF <NUM> determines whether the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. For example, the loop prevention module <NUM> executed by the processor <NUM> is configured to determine whether the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. The predefined parameter <NUM> in the example shown in <FIG> is <NUM>. Since the value in the loop prevention field <NUM> is <NUM> when the service chain packet <NUM> is received from SFF 112A, the SFF 112B may determine that an error has not occurred during transmission of the service chain packet <NUM> and continue transmission. At step <NUM>, the SFF 112B does not perform a SF <NUM> on the data packet <NUM> of the service chain packet <NUM> for one of the various reasons discussed above with reference to <FIG>. However, even though a SF <NUM> is performed on the service chain packet <NUM>, the SFF 112B is still configured to increment the value in the loop prevention field <NUM> to <NUM>. For example, the processor <NUM> increments the value in the loop prevention field <NUM>.

At step <NUM>, the SFF 112B transmits the service chain packet <NUM> to SFF 112C. For example, Tx <NUM> of SFF 112B transmits the service chain packet <NUM> to SFF 112C. A Rx <NUM> of SFF 112C receives the service chain packet <NUM> where the value in the loop prevention field <NUM> is <NUM>. At step <NUM>, SFF 112C determines whether the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. For example, the loop prevention module <NUM> executed by the processor <NUM> is configured to determine whether the value in the loop prevention field <NUM> is less than the predefined parameter <NUM>. Here, the value in the loop prevention field <NUM> is <NUM> when the service chain packet <NUM> is received from SFF 112B. SFF 112C may determine that the value in the loop prevention field <NUM> is greater than or equal to the predefined parameter <NUM> and discard, or discontinue transmission of, the service chain packet <NUM>.

<FIG> is a diagram of a service header <NUM> according to an embodiment of the disclosure. For example, the service header <NUM> is a NSH as described in the IETF Draft Document for NSH, which is already incorporated by reference above in the description for <FIG>. The service header <NUM> includes service path information and optionally metadata that are added to a data packet <NUM> and used to create a service plane. Subsequently, an outer transport encapsulation is imposed on the service header <NUM>, which is used for network forwarding. The classifier <NUM> adds the service header <NUM> onto the data packet <NUM>, and the last SFF 112C in the SFP <NUM> removes the service header <NUM>.

As shown in <FIG>, the service header <NUM> comprises a version field <NUM>, an operations, administration, and maintenance (OAM) field <NUM>, a loop prevention field <NUM>, a length field <NUM>, a metadata (MD) type field <NUM>, a next protocol field <NUM>, a service path identifier field <NUM>, a service index field <NUM>, and reserved bits <NUM>. As should be appreciated, the service header <NUM> may not include all of these fields and/or may include additional fields. The version field <NUM> indicates a version and is used to ensure backward compatibility going forward with future service header <NUM> specification updates. The OAM field <NUM> indicates whether the data packet <NUM> is an OAM packet.

The MD type field <NUM> indicates a format of the metadata being carried in the service chain packet <NUM>. The next protocol field <NUM> indicates the protocol type of the encapsulated data. The service path identifier field <NUM> includes a service path identifier that uniquely identifies a SFP <NUM>. SFFs <NUM> and SNs <NUM> use this service path identifier to select the SF <NUM> to perform on the service chain packet <NUM>. The service index field <NUM> includes the service index that provides a location within the SFP <NUM>. The service index is used in conjunction with the service path identifier for SFP selection for determining the next SFF <NUM>, SN <NUM>, and/or SF <NUM> in the path. The reserved bits <NUM> may be extra bits that do currently not carry information.

As shown in <FIG>, the loop prevention field <NUM> occupies two or more reserved bits that are available in the service header <NUM>. Although only <NUM> bits are shown in the loop prevention field <NUM> of <FIG>, there may be any number of bits used for the loop prevention field <NUM>. In some embodiments, the number of bits (n) used for the loop prevention field <NUM> corresponds to the predefined parameter <NUM>. If n bits are used in a loop prevention field <NUM>, then <NUM>n-<NUM> is a maximum number of consecutive SFFs <NUM> permitted for an SFP <NUM>. In an embodiment, the predefined parameter <NUM> is <NUM>n-<NUM> such that the value in the loop prevention field <NUM> is compared to <NUM>n-<NUM>. For the examples shown in <FIG> and <FIG>, the predefined parameter <NUM> is <NUM> because n = <NUM>. In some embodiments, SFP resilience to SF <NUM> failures is considered by using more than <NUM> bits in the loop prevention field <NUM>. For example, when a SF <NUM> fails, service chain packets <NUM> may pass through more than two SFFs <NUM>, or middle relay components, without reaching an SF <NUM>. To allow for the service chain packets <NUM> to pass through more than two SFFs <NUM> to find a working SF <NUM>, the loop prevention field <NUM> may include more than <NUM> bits. In this embodiment, each of the SFFs <NUM> are configured to determine the number of bits (n) in the loop prevention field <NUM> when a service chain packet <NUM> is received. The SFFs <NUM> may then be configured with the predefined parameter <NUM> based on the number of bits (n) in the range <NUM>n-<NUM> to <NUM>n-<NUM>. Each of the SFFs <NUM> are configured to increment the value in the loop prevention field <NUM> based on whether the value currently in the loop prevention field <NUM> is less than the computed predefined parameter <NUM>.

<FIG> illustrates a method <NUM> of loop prevention according to an embodiment of the disclosure. <FIG> shows examples of values <NUM> (e.g., values <NUM> A-E) in the loop prevention field <NUM> when the loop prevention field <NUM> includes <NUM> bits. When the loop prevention field <NUM> includes <NUM> bits, the predefined parameter <NUM> may be <NUM> (<NUM><NUM>-<NUM>). In such a case, each SFF 112A-C determines whether the value <NUM> in the loop prevention field <NUM> is less than <NUM>. As shown in <FIG>, the value <NUM> may be a binary value.

As shown in <FIG>, when the classifier <NUM> encapsulates the data packet <NUM> to include the service header <NUM> and creates the service chain packet <NUM>, the classifier <NUM> sets the value 710A in the loop prevention field <NUM> to <NUM> (shown as the binary value <NUM> in <FIG>) and transmits the service chain packet <NUM> to SFF 112A. SFF 112A first determines that the value 710A (<NUM>) is less than <NUM>, increments the value 710A to be <NUM> (shown as the binary value <NUM> in <FIG>), then transmits the service chain packet <NUM> to SN 115A to perform a SF <NUM> on the service chain packet <NUM>. SN <NUM> resets the value <NUM> back to <NUM>, and sends the service chain packet <NUM> back to SFF 112A. SFF 112A again increments the value 710B to <NUM> (shown as the binary value <NUM> in <FIG>) and transmits the service chain packet <NUM> to SFF 112B.

SFF 112B also determines that the value 710B (<NUM>) is less than <NUM>, but SFF 112B does not transmit the service chain packet <NUM> to a SN <NUM> to invoke an SF <NUM>. Instead, SFF 112B increments the value 710C to <NUM> (shown as the binary value <NUM> in <FIG>) and transmits the service chain packet <NUM> to SFF 112C. SFF 112C also determines that the value 710C (<NUM>) is less than <NUM> and does not transmit the service chain packet <NUM> a SN <NUM> to invoke an SF <NUM>. SFF 112C instead increments the value 710D to <NUM> (shown as the binary value <NUM> in <FIG>) and transmits the service chain packet <NUM> back to SFF 112B. SFF 112B determines that the value <NUM> (<NUM>) is less than <NUM> and again does not transmit the service chain packet <NUM> to a SN <NUM>. SFF 112B increments the value 710E to <NUM> (shown as the binary value <NUM> in <FIG>) and transmits the service chain packet <NUM> to SFF 112C.

In traditional SFP-enabled networks, the loop occurring between SFF 112B and SFF112C during the transmission of the service chain packet <NUM> may not be detected because a loop prevention field <NUM> is typically not included in a service header <NUM>. Embodiments of the disclosure herein prevent the loop between SFF 112B and SFF 112C from continuously occurring because SFF 112C is configured to discard the service chain packet <NUM> after determining that the value 710E (<NUM>) is greater than or equal to the predefined parameter <NUM> of <NUM>. As shown in <FIG>, the <NUM> bit loop prevention field <NUM> permits the service chain packet <NUM> to account for some SF <NUM> failures while still maintaining the ability to discard packets once an error in packet transmission is detected.

In an embodiment, the service chain packet <NUM> may be additionally encapsulated with an overlay header to be transmitted across overlay nodes in an overlay network. In an embodiment, the overlay header may include a Time-to-Live (TTL) field that may be more than <NUM> bits. For example, a TTL field may be <NUM> bits in length. The TTL field may be set by an ingress node on an overlay path to include a value indicating a maximum number of hops for an overlap path that may be used for loop detection. The initial value in the TTL field may be configurable or specific to one or more overlay paths. If no initial value in the TTL field is provided, a default initial TTL value may be used. Each overlay node on an overlay path may be configured to decrement a value in the TTL field by <NUM> prior to forwarding the overlay packet to another overlay node. When an overlay node receives an overlay packet, the overlay node may first determine whether the value in the TTL field is <NUM>. The overlay node may be configured to discard the overlay packet when the value in the TTL field is <NUM>. The overlay node may be configured to continue transmission of the overlay packet along the overlay path when the value in the TTL field is greater than <NUM>.

In an embodiment, the TTL field may be included in the overlay header when an inner header with a TTL value is not used in the service chain packet <NUM>. In an embodiment, the TTL field may be included in the overlay header when an inner header with a TTL value does not exist in the service chain packet <NUM>. In an embodiment, the TTL field may be included in the overlay header when an inner header with a TTL field includes a large value, for example, to cover delivery after a final overlay hop. In this embodiment, the maximum number of hops for an overlay path may be smaller than the large value.

In an embodiment, a service header <NUM> used for service function chaining may include a TTL field, for example, in some of the reserved bits <NUM> of the service header <NUM>. For example, the TTL field in the service header <NUM> may include a value for a maximum number of SFF <NUM> hops for an SFP. The TTL field here may also be used for service plane loop detection similar to the loop prevention field <NUM>. The initial TTL value in the TTL field may be set by the classifier <NUM> or the SDN controller <NUM>. The initial TTL value may be configurable or set specifically for one of the SFPs <NUM>. If an initial value for the TTL field is not explicitly provided, the default initial TTL value of <NUM> may be used. Each SFF <NUM> involved in forwarding a service chain packet <NUM> must decrement the value in the TTL field by <NUM> prior to forwarding lookup and transmitting the service chain packet <NUM> to another SFF <NUM>. In one embodiment, the SFF <NUM> is configured to discard the service chain packet <NUM>, or discontinue forwarding the service chain packet <NUM>, if the value in the TTL field is <NUM> upon receiving the service chain packet <NUM> from another SFF <NUM>. In one embodiment, the SFF <NUM> is configured to discard the service chain packet <NUM> if the value in the TTL field is <NUM> after decrementing is <NUM>.

<FIG> is a method <NUM> of loop prevention according to an embodiment of the disclosure. The method <NUM> may be implemented by the SFF <NUM>. The method <NUM> may be implemented when, for example, a classifier <NUM> transmits a service chain packet <NUM> to the SFF <NUM> after encapsulating the data packet <NUM> to include the service header <NUM>. At step <NUM>, the SFF <NUM> receives the service chain packet <NUM> comprising a loop prevention field <NUM>. For example, Rx <NUM> of SFF <NUM> receives the service chain packet <NUM>. The loop prevention field <NUM> comprises a plurality of bits indicating whether an error has occurred during transmission of the service chain packet <NUM>. In an embodiment where the SFF <NUM> receives the service chain packet <NUM> from the classifier <NUM>, the value <NUM> in the loop prevention field <NUM> is <NUM>. In an embodiment where the SFF <NUM> receives the service chain packet <NUM> from another SFF, the value <NUM> in the loop prevention field <NUM> may be greater than <NUM>.

At step <NUM>, the SFF <NUM> determines whether to forward the service chain packet <NUM> based on a value <NUM> in the loop prevention field <NUM> being less than a predefined parameter <NUM>. For example, the loop prevention module <NUM> in the processor <NUM> determines whether to forward the service chain packet <NUM>. In an embodiment, SFF <NUM> is configured to increment a value <NUM> in the loop prevention field <NUM> when the value <NUM> in the loop prevention field <NUM> is less than the predefined parameter <NUM>. In an embodiment, the SFF <NUM> is configured to discard the service chain packet <NUM> when the value <NUM> in the loop prevention field <NUM> is greater than or equal to the predefined parameter <NUM>.

<FIG> is a method <NUM> of loop prevention according to an embodiment of the disclosure. The method <NUM> may be implemented by SN <NUM>. The method <NUM> may be implemented when, for example, an SFF <NUM> transmits a service chain packet <NUM> to the SN <NUM>. At step <NUM>, the SN <NUM> receives the service chain packet <NUM> comprising the loop prevention field <NUM> from an SFF <NUM>. For example, the Rx <NUM> receives the service chain packet <NUM>. The loop prevention field <NUM> comprises a plurality of bits indicating whether an error has occurred during transmission of the service chain packet <NUM>. At step <NUM>, the SN <NUM> executes an SF <NUM> on the service chain packet <NUM>. For example, the loop prevention module <NUM> in the processor <NUM> of SN <NUM> executes an SF <NUM> on the data packet <NUM> in the service chain packet <NUM>. At step <NUM>, SN <NUM> sets a value <NUM> in the loop prevention field <NUM> to <NUM> after executing the SF <NUM> on the service chain packet <NUM>. For example, the loop prevention module <NUM> in the processor <NUM> of SN <NUM> sets a value <NUM> in the loop prevention field <NUM> to <NUM> after executing the SF <NUM> on the service chain packet <NUM>. In an embodiment, if the SF <NUM> is unavailable or fails to execute a network service on the service chain packet <NUM>, the value <NUM> in the loop prevention field <NUM> remains unchanged. At step <NUM>, the SN <NUM> transmits the service chain packet <NUM> back to the SFF <NUM>. For example, the Tx <NUM> transmits the service chain packet <NUM> back to the SFF <NUM>.

<FIG> is a method <NUM> of loop prevention according to an embodiment of the disclosure. The method <NUM> may be implemented by a classifier <NUM>. The method <NUM> may be implemented when, for example, the classifier <NUM> receives a data packet <NUM> from a source <NUM>. At step <NUM>, the classifier <NUM> receives a data packet <NUM> from a source <NUM>. For example, the Rx <NUM> receives the data packet <NUM> from a source <NUM>. At step <NUM>, the classifier <NUM> encapsulates the data packet <NUM> to comprise the service header <NUM> and create a service chain packet <NUM>. For example, the loop prevention module <NUM> in the processor <NUM> encapsulates the data packet <NUM> to comprise the service header <NUM> and create a service chain packet <NUM>. The service header <NUM> comprises the loop prevention field <NUM>, where the loop prevention field <NUM> comprises a plurality of bits to indicate whether an error has occurred during transmission of the service chain packet <NUM>. At step <NUM>, the classifier <NUM> sets a value <NUM> of the loop prevention field <NUM> to <NUM>. For example, the loop prevention module <NUM> in the processor <NUM> sets the value <NUM> of the loop prevention field <NUM> to <NUM>. At step <NUM>, the classifier <NUM> transmits the service chain packet <NUM> to a SFF <NUM> after setting the value <NUM> in the loop prevention field <NUM> to <NUM>.

In an embodiment, the disclosure includes a means for receiving a service chain packet comprising a loop prevention field, the loop prevention field comprising a plurality of bits indicating whether an error has occurred during packet transmission, and determining whether to forward the service chain packet based on a value in the loop prevention field being less than a predefined parameter, the predefined parameter based on a number of bits (n) in the loop prevention field.

In an embodiment, the disclosure includes a means for receiving a service chain packet comprising a loop prevention field, the loop prevention field comprising a plurality of bits indicating whether an error has occurred during packet transmission, a means for incrementing a value in the loop prevention field when the value in the loop prevention field is less than a predefined parameter, the predefined parameter being based on a number of bits (n) in the loop prevention field, and a means for transmitting the service chain packet after incrementing the value in the loop prevention field.

In an embodiment, the disclosure includes a means for receiving a service chain packet comprising a loop prevention field, the loop prevention field comprising a plurality of bits indicating whether an error has occurred during packet transmission, and a means for discarding the service chain packet when a value in the loop prevention field is greater than or equal to a predefined parameter, the predefined parameter corresponding to a number of bits (n) in the loop prevention field.

In an embodiment, the disclosure includes a means for receiving a service chain packet comprising a loop prevention field from a SFF, the loop prevention field comprising a plurality of bits indicating whether an error has occurred during transmission of the service chain packet, a means for executing a service function on the service chain packet, a means for setting a value in the loop prevention field to <NUM> after executing the service function on the service chain packet, and a means for transmitting the service chain packet to the SFF.

Claim 1:
A service function forwarding method, wherein the method is characterized by:
receiving, by a service function forwarder, SFF (<NUM>), a first service packet, wherein the first service packet is a service chain packet (<NUM>) comprising a service path identifier used to identify a service chain and a loop prevention field (<NUM>) comprising a plurality of bits indicating whether an error has occurred during packet transmission; and;
obtaining, by the SFF (<NUM>), a second service packet (<NUM>) when the loop prevention field (<NUM>) meets a preset condition, wherein the obtaining, by the SFF (<NUM>), a second service packet comprises:
obtaining, by the SFF (<NUM>), the second service packet based on the first service packet, wherein the second service packet comprises an incremented loop prevention field (<NUM>); and;
sending, by the SFF (<NUM>), the second service packet based on the service path identifier.