Patent Description:
The disclosure relates to computer networks and, more specifically, to applying network services to data traffic traversing computer networks.

A computer network is composed of a set of nodes (e.g., computing devices) and a set of links that connect one node to another. For instance, a computer network may be composed of a set of routers while the set of links may be paths between the routers. When a first node in the network sends data traffic to a second node in the network, the message may pass through many links and many nodes. The set of links and nodes that the message passes through while traveling from the first node to the second node is referred to as a path through the network.

A network operator may deploy one or more computing devices to apply, to data traffic traversing a computer network, network services such as firewall, carrier grade network address translation (CG-NAT), performance enhancement proxies for video, transport control protocol (TCP) optimization and header enrichment, caching, and load balancing. Each of these network services may be referred to as a service function and is implemented by one or more service function instances. In addition, the network operator may configure service function chains that each identify a set of the service functions to be applied to packet flows mapped to the respective service function chains. A service function chain, in other words, defines one or more service functions to be applied in a particular order to provide a composite service for application to packet flows bound to the service function chain for processing. In this way, a service function chain is a sequence of service functions through which packet flows satisfying specified criteria will pass. An example service function chain architecture is described in <NPL>.

<CIT> provides network service header (NSH) relaying of serviceability of a service function. <CIT> provides a method and system of performing service function chaining.

The details of one or more example of this disclosure are set forth in the accompanying drawings and the description below.

Like reference characters denote like elements throughout the description and figures.

<FIG> illustrates an example network system providing backup service function notification and synchronization, in accordance with techniques described herein. The example network system of <FIG> includes a service provider network <NUM> to provide packet-based network services to subscriber devices <NUM> (collectively, "subscriber devices <NUM>"). That is, service provider network <NUM> provides authentication and establishment of network access for subscriber devices <NUM> such that the subscriber devices may begin exchanging data packets with public network <NUM> (also referred to herein as a "packet data network"), which may be an internal or external packet-based network such as the Internet.

In the example of <FIG>, service provider network <NUM> comprises access network <NUM> ("access network <NUM>") that provides connectivity to public network <NUM> via service provider core network <NUM> (referred to herein as "core network <NUM>") and gateway <NUM>. Service provider core network <NUM> and public network <NUM> provide packet-based services that are available for request and use by subscriber devices <NUM>. As examples, core network <NUM> and/or public network <NUM> may provide, for example, bulk data delivery, voice over Internet protocol (VoIP), Internet Protocol television (IPTV), Short Messaging Service (SMS), Wireless Application Protocol (WAP) service, or customer-specific application services. Public network <NUM> may comprise, for instance, a local area network (LAN), a wide area network (WAN), the Internet, a virtual LAN (VLAN), an enterprise LAN, a layer <NUM> virtual private network (VPN), an Internet Protocol (IP) intranet operated by the service provider that operates access network <NUM>, an enterprise IP network, or some combination thereof. In various examples, public network <NUM> is connected to a public WAN, the Internet, or to other networks. Public network <NUM> executes one or more packet data protocols (PDPs), such as IP (IPv4 and/or IPv6), X. <NUM> or Point-to-Point Protocol (PPP), to enable packet-based transport of public network <NUM> services.

Subscriber devices <NUM> connect to gateway <NUM> via access network <NUM> to receive connectivity to subscriber services for applications hosted by subscriber devices <NUM>. A subscriber may represent, for instance, an enterprise, a residential subscriber, or a mobile subscriber. Subscriber devices <NUM> may be, for example, personal computers, laptop computers or other types of computing device associated with subscribers. In addition, subscriber devices <NUM> may comprise mobile devices that access the data services of service provider network <NUM> via radio access network (RAN) <NUM>. Example mobile subscriber devices include mobile telephones, laptop or desktop computers having, e.g., a wireless card, wireless-capable netbooks, video game devices, pagers, smart phones, personal data assistants (PDAs) or the like. Each of subscriber devices <NUM> may run a variety of software applications, such as word processing and other office support software, web browsing software, software to support voice calls, video games, videoconferencing, and email, among others. Subscriber devices <NUM> connect to access network <NUM> via access links <NUM> that comprise wired and/or wireless communication link. The term "communication link," as used herein, comprises any form of transport medium, wired or wireless, and can include intermediate nodes such as network devices. Each of access links <NUM> may comprise, for instance, aspects of an asymmetric DSL network, WiMAX, a T-<NUM> line, an Integrated Service Digital Network (ISDN), wired Ethernet, or a cellular radio link.

A network service provider operates, or in some cases leases, elements of access network <NUM> to provide packet transport between subscriber devices <NUM> and gateway <NUM>. Access network <NUM> represents a network that aggregates data traffic from one or more subscribers for transport to/from service provider core network <NUM> of the service provider. Access network <NUM> includes network nodes that execute communication protocols to transport control and user data to facilitate communication between subscriber devices <NUM> and gateway <NUM>. Access network <NUM> may include a broadband access network, network, a wireless LAN, a public switched telephone network (PSTN), or other type of access network, and may include or otherwise provide connectivity for cellular access networks, such as radio access network (RAN) <NUM> of <FIG>. Examples include networks conforming to a Universal Mobile Telecommunications System (UMTS) architecture, <NUM>th Generation of Mobile Technologies (<NUM>), an evolution of UMTS referred to as Long Term Evolution (LTE), mobile IP standardized by the Internet Engineering Task Force (IETF), as well as other standards proposed by the <NUM>rd Generation Partnership Project (3GPP), <NUM>rd Generation Partnership Project <NUM> (3GGP/<NUM>) and the Worldwide Interoperability for Microwave Access (WiMAX) forum.

Service provider core network <NUM> offers packet-based connectivity to subscriber devices <NUM> attached to access network <NUM> for accessing public network <NUM>. Core network <NUM> may represent a network that is owned and operated by a service provider to interconnect a plurality of networks, which may include access network <NUM>. Core network <NUM> may implement Multi-Protocol Label Switching (MPLS) forwarding and in such instances may be referred to as an MPLS network or MPLS backbone. In some instances, core network <NUM> represents a plurality of interconnected autonomous systems, such as the Internet, that offers services from one or more service providers. Public network <NUM> may represent an edge network coupled to core network <NUM>, e.g., by a customer edge device such as customer edge switch or router (not shown in <FIG>). Public network <NUM> may include a data center.

In examples of service provider network <NUM> that include a wireline/broadband access network, gateway <NUM> may represent a Broadband Network Gateway (BNG), a Broadband Remote Access Server (BRAS), MPLS Provider Edge (PE) router, core router or gateway, or a Cable Modem Termination System (CMTS), for instance. In examples of service provider network <NUM> that include a cellular access network as access network <NUM>, gateway <NUM> may represent a mobile gateway, for example, a Gateway General Packet Radio Service (GPRS) Serving Node (GGSN), an Access Gateway (aGW), or a Packet Data Network (PDN) Gateway (PGW). In other examples, the functionality described with respect to gateway <NUM> may be implemented in a switch, service card or other network element or component.

A network service provider that administers at least parts of service provider network <NUM> typically offers services to subscribers associated with devices, e.g., subscriber devices <NUM>, that access the service provider network. Services offered may include, for example, traditional Internet access, Voice-over-Internet Protocol (VoIP), video and multimedia services, and security services. As described above with respect to access network <NUM>, core network <NUM> may support multiple types of access network infrastructures that connect to service provider network access gateways to provide access to the offered services. In some instances, network system may include subscriber devices <NUM> that attach to multiple different access networks <NUM> having varying architectures.

In general, any one or more of subscriber devices <NUM> may request authorization and data services by sending a session request to gateway <NUM>. In turn, gateway <NUM> typically accesses Authentication, Authorization and Accounting (AAA) server <NUM> to authenticate the subscriber device requesting network access. Once authenticated, any of subscriber devices <NUM> may send subscriber data traffic toward service provider core network <NUM> in order to access and receive services provided by public network <NUM>, and such packets traverse gateway <NUM> as part of at least one packet flow. Flows 26A illustrated in <FIG> represent one or more upstream packet flows from any one or more subscriber devices <NUM> and directed to public network <NUM>. Flows 26B represent one or more downstream packet flows from public network <NUM> and directed to any one or more subscriber devices <NUM>.

The term "packet flow," "traffic flow," or simply "flow" refers to a set of packets originating from a particular source device and sent to a particular destination device. A single flow of packets, in either the upstream (sourced by one of subscriber devices <NUM>) or downstream (destined for one of subscriber devices <NUM>) direction, may be identified by values used in a header of a packet, such as the network "<NUM>-tuple," i.e., a source network address (IP address), destination network address, source port, destination port, and protocol, for example. This <NUM>-tuple generally identifies a packet flow to which a received packet corresponds. An n-tuple refers to any n items drawn from the <NUM>-tuple. For example, a <NUM>-tuple for a packet may refer to the combination of <source network address, destination network address> or <source network address, source port> for the packet. Moreover, a subscriber device may originate multiple packet flows upon authenticating to service provider network <NUM> and establishing a communication session for receiving data services. The techniques described in this disclosure may apply to packet flows between any two computing devices and are not limited to application to flows <NUM> depicted in <FIG>.

As described herein, service provider network <NUM> includes a services complex <NUM> having service function instances 10A-10N that provide an execution environment for the network services. That is, each of service function instances <NUM> apply one or more service functions. A service function is applied to received packets of packet flows and can act at various layers of a protocol stack (e.g., network layer, application layer).

As examples, service functions applied by service function instances <NUM> may include firewall and security services, carrier grade network address translation (CG-NAT), media optimization (voice/video), WAN optimization, NAT44, NAT64, HTTP header enrichment functions, TCP optimizers, IPSec/VPN services, deep packet inspection (DPI), HTTP filtering, counting, accounting, charging, and load balancing of packet flows or other types of services applied to network traffic. Service functions may be alternately referred to as virtualized network functions (VNFs), although service functions need not be virtual. Each of service function instances <NUM> in this way represents an instance of a service function. Each of service function instances <NUM> represents a component that may be realized as a virtual element of a computing device (e.g., a real server) and/or embedded in a physical network element (e.g., a firewall or NAT appliance). Multiple service function instances <NUM> may be executed in a single computing device or physical network element computing device. A computing device that hosts one or more service function instances <NUM> may refer to a real server or a physical network element.

Although illustrated as part of a services complex <NUM>, which may represent a data center, service function instances <NUM> may, for instance, be located within core network and be interconnected by one or more switches or virtual switches of core network <NUM>. Service function instances <NUM> may in some instances be located in multiple different data centers. One or more service function instances <NUM> may be located within an enterprise / customer site attached to service provider core <NUM>. In some examples, each of service function instances <NUM> may be executed by a virtual machine in virtual compute environment. Moreover, the compute environment may comprise a scalable cluster of general computing devices, such as x86 processor-based servers. As another example, service function instances <NUM> may be executed by a combination of general purpose computing devices and special purpose appliances. As virtualized, individual network services provided by service function instances <NUM> can scale just as in a modern data center, through the allocation of virtualized memory, processor utilization, storage and network policies, as well as horizontally by adding additional load-balanced virtual machines. Services complex <NUM> may represent or otherwise be implemented using a public cloud, private cloud, hybrid cloud, or combination thereof. Other network architectures for delivering network traffic to services complex <NUM> are contemplated, and the techniques are not limited to network service provider architectures as illustrated in <FIG>.

In example of <FIG>, gateway <NUM> steers individual packet flows <NUM> through a defined set of service functions provided by service function instances <NUM>. That is, each packet flow may be forwarded through a particular ordered combination of service functions, each ordered combination providing an overall "network service" or "composite service" and being referred to herein as a "service function chain" or, more simply, a "service chain. " A service function chain may include a particular service function instance <NUM> that provides the service function or may indicate that the service function may be applied by any service function instance <NUM> that provides the service function. In this way, packet flows <NUM> may be processed by service function instances <NUM> as the packets flow between access network <NUM> and public network <NUM> according to service function chains configured by the service provider. A particular service function instance <NUM> may support multiple service function chains. An example service chain <NUM> is depicted in <FIG> and includes, in order, service function instance 10A, service function instance 10B, and service function instance 10N.

Whereas a "service function chain" defines one or more services to be applied in a particular order to provide a composite service for application to packet flows bound to the service function chain, a "service tunnel" or "service path" refers to a logical and/or physical path taken by packet flows processed by a service function chain along with the forwarding state for forwarding packet flows according to the service function chain ordering. Each service function chain may be associated with a respective service path.

Gateway <NUM> or one or more computing devices hosting service function instances <NUM> may classify packet flows <NUM> to service function chains. Classification granularity may vary based on device capabilities, customer requirements, service provider network policies, and services offered. Initial classification determines the service function chain with which to process a packet flow. Subsequent classification may occur within a service function chain to alter the sequence of service functions applied.

Service function instances <NUM> may implement each service function chain using internally configured forwarding state that directs packets of the packet flow along a service function chain for processing according to the identified set of service function instances <NUM>. Such forwarding state may specify tunnel interfaces for tunneling between service function instances <NUM> using network tunnels such as Internet Protocol (IP) or Generic Route Encapsulation (GRE) tunnels, or by using Virtual Local Area Networks (VLANs), Multiprotocol Label Switching (MPLS) techniques, and so forth. Tunnel encapsulation for service function chaining may be referred to as service function chain encapsulation, which enables the creation of the service function chain in the data plane of service provider network <NUM>. In some instances, real or virtual switches, routers or other network elements that interconnect service function instances <NUM> may be configured to direct packet flows to the service function instances <NUM> according to service function chains.

Service function chain encapsulation enables forwarding between service function instances <NUM> that provide a service function overlay network over a physical underlay network, the physical underlay network made up of an existing layer <NUM> network topology of computing devices, such as real servers, interconnected by routing and switching equipment for exchanging packetized data between the computing devices. The service function overlay network may enable the network service provider to create paths between service function instances <NUM> and to locate service functions in service provider network <NUM> in a network topology-independent manner, e.g., without requiring changes to the underlay network topology.

Computing devices that implement service function instances <NUM> may distribute service function data that describes service function instances <NUM>. As one example, computing devices may leverage a layer <NUM> routing protocol, such as a Border Gateway Protocol (BGP) message (e.g., BGP UPDATE message) to distribute service function data. More particularly, a computing device that hosts at least one service function instance <NUM> may output a service function instance route <NUM>. In general, a service function instance route (SFIR) describes a particular service function instance of a particular service function and the way to forward a packet to the service function instance through the underlay network. For example, service function instance route <NUM> may include a network address for the computing device and service function instance data that specifies, for one or more service function instances <NUM> hosted by the computing device, a service function type for the service function and a service identifier (e.g., as defined by IANA (Internet Assigned Numbers Authority)), where the combination of the service function type and the service identifier identify the service function instance <NUM> in the service provider network <NUM>. The service function instance routes <NUM> may in some instances specify an address family for the service function instance data that varies from the address family of the underlay computer network and, in this way, the service function instance routes <NUM> distribute service function data for an overlay network of service function instances <NUM> overlaying the computer network made up of computing devices.

In some cases, a service function instance route <NUM> may be originated by the computing device that hosts the described service function instance <NUM>. However, service function instance routes <NUM> may be originated by controller <NUM> or other another device. A service function instance route <NUM> includes a network address, such as an IPv4 or IPv6 address, for the computing device that hosts the service function instances <NUM> being described. In some example, the service function instance route <NUM> may further include encapsulation data that describes the tunnel encapsulation for packets to be received by the computing device in order to reach the service function instances <NUM>.

In <FIG>, controller <NUM> may manage deployment of service function instances within the operating environment of services complex <NUM>. For example, controller <NUM> may orchestrate a service function and deploy the service function as a service function instance, e.g., any of service function instances <NUM>. In some examples, controller <NUM> may orchestrate a virtual machine, container, or other operating environment to host the orchestrated service function. Controller <NUM> may orchestrate service functions in response to requests from applications or network service provider operators.

In some examples, controller <NUM> may distribute service function chain data that describes overlay topologies for service function chains each made up of one or more service function instances <NUM> described by the service function chain data. As one example, controller <NUM> may leverage a layer <NUM> routing protocol to output, to service provider network <NUM>, a service function chain route <NUM> that includes an ordered set of one or more service function instances <NUM> to define a service chain with which to process at least one packet flow <NUM>. Controller <NUM> may inject the service function chain route <NUM> into service provider network <NUM> by sending the service function chain route <NUM> to any of service function instances <NUM>, a route reflector, or another routing device of service provider network <NUM>, for advertisements by the routing device in the network. Controller <NUM> may be a layer <NUM> routing protocol speaker and advertise service function chain route <NUM> directly. Controller <NUM> may output multiple service function chain routes, service function chain route <NUM> being only one example. In general, controller <NUM> originates one service function chain route per service function chain, and each service function chain route may include a service path identifier for the service function chain described, a sequence of service function types and/or service function instances of which the chain consists, and for each such service function type and/or service function instance, a service index that represents it in the service function chain described.

Controller <NUM> may receive service function instance routes <NUM> via the layer <NUM> protocol. Controller <NUM> may use service function instance data included in service function instance routes <NUM> to generate a service function chain and the service function chain route <NUM> for the service function chain. For example, controller <NUM> may receive a request from an operator to create a service function chain that has a series of service functions (each with a different service function type) for application to a packet flow. Controller <NUM> may identify service function instances that match the service function types for the service functions, as indicated in the service function instance routes <NUM>. Additional examples of the service function instance route and service function chain route are described in <CIT>. The use of layer <NUM> routing protocols to distribute service function chain data is merely one example and controller <NUM> may use any protocol to distribute service function data and/or service function chain data, such as Network Configuration protocol (NETCONF).

In the example of <FIG>, service function instance 10A may operate as an ingress service function instance for the service function overlay network to apply a classification service function to packet flows. In such cases, service function instance 10A may be referred to as a "classifier," which is a special service function located at an ingress point to a service function overlay network. In such instances, service function instance 10A operating as a classifier assigns the packets of a given packet flow to a specific service function chain. To classify a packet flow for processing using a service function chain, service function instance 10A may apply policies to packet header fields (e.g., <NUM>-tuple values such as source/destination address, source/destination port, protocol) of the packet flow packets to determine the service chain for the packet. Policies may be specific to a subscriber of a subscriber device <NUM>, specific to a network, or specific to an application service transported using the packet flow, for instance. A policy may specify a service path identifier that identifies the service function chain for processing packets that match the policy. In some cases, service function instance 10A operating as a classifier selects a service function chain for a packet flow, sets the service path identifier for the service function chain, sets the service index for the first hop in the selected service function chain, and adds to packets of the packet flow a network service header (NSH) indicating the service path identifier and the service index. Additional examples of the network service header are described in <NPL>.

In the example of <FIG>, service function instance 10A may classify one or more of packet flows <NUM> to service function chain <NUM>. Although service function instance 10A is the first service function instance in service function chain <NUM>, service function instance 10A may classify some packets flows <NUM> to service function chains that do not have service function instance 10A as the first service function instance. In addition, a computing device other than one of service function instances <NUM> may classify packet flows to service function chains and direct the packet flows to first service function instances <NUM> in the service function chains.

To apply the service functions indicated by a service function chain, service function instances <NUM> forward a packet through an ordered combination of service function instances <NUM> for application of corresponding service functions. A service function instance <NUM> that applies a service function to a packet determines a next service function instance <NUM> in a service function chain and forwards the packet to a next service function instance <NUM> (referred to herein as a "service function next hop"). In some examples, the service function next hop may be determined based on next hop information for the service chain, such as a service path identifier and service function type that in combination identify a service function instance as a next service function instance in the service chain. For example, service function instance 10A may add a network service header (NSH) to the packet, the NSH including at least one of the service path identifier and the service index.

The packet with the NSH may be further encapsulated in a tunnel encapsulation header including an IP address in the underlay network for the computing device that hosts the service function next hop, e.g., service function instance 10B. As one example, the tunnel encapsulation header may be based on encapsulation data included in a service function instance route <NUM> for service function instance 10B. If more than one service function instance <NUM> may be used as the next service function instance for a service function in a service function chain, then an anycast address in the underlay network or direct knowledge of the underlay network topology may be used to select the next service function instance <NUM> to apply the indicated service function.

Service function instance 10B receives the packet and applies its corresponding service function to the packet to further realize service function chain <NUM>. The computing device that hosts service function instance 10B uses the NSH included with the packet to determine a next service function instance <NUM> in the service chain and, in some cases, a next service index. For example, the combination of the service path identifier and the service index provides the identification of a service function and its order within the service function chain. In this example, the computing device that hosts service function instance 10B determines the next service function instance is service function instance 10N and forwards the packet to the computing device that hosts service function instance 10N.

Service function instance 10N receives the packet and applies its corresponding service function to the packet to further realize service function chain <NUM>. The computing device that hosts service function instance 10N uses the NSH included with the packet to determine a next service function instance <NUM> in the service chain. In this case, service function instance 10N is a terminal service function instance in service chain <NUM>. The computing device that hosts service function instance 10N may therefore output the packet to the IP next hop for the packet in the underlay network.

To provide a high availability of service functions, service functions may be deployed in a cluster as part of the same service function chain or across multiple service function chains. Service functions in the cluster may be configured as active service functions and/or backup service functions for a given service function chain. For example, service function chain <NUM> may include a first service function (e.g., firewall) provided by service function instance 10A, a second service function (e.g., Network Address Translation) provided by service function instance 10B, and a third service function (e.g., WAN optimization) provided by service function instance 10N. In the example of <FIG>, service function instance 10C may also provide a Network Address Translation and may operate as a backup service function in the event service function instance 10B fails or is otherwise unavailable. Typically, a controller statically configures the active service function and backup service function. For example, a network operator may pre-configure, for a given service function chain, the active service function and one or more backup service functions for the active service function. However, service function instances in the cluster may change and the controller may be unable to dynamically update the backup service functions in such topological changes.

In accordance with the techniques described in this disclosure, service provider network <NUM> provides backup service function notification and synchronization. In the example of <FIG>, when service function instance 10A, operating as the classifier, receives a packet and classifies the packet to service function chain <NUM>, service function instance 10A determines whether there are any backup service functions for the active service functions in service function chain <NUM>. For example, service function instance 10A may store a table, e.g., table <NUM>, that includes backup service function information. In the example of <FIG>, table <NUM> includes network addresses of computing devices that host backup service functions for active service functions of a given service path. In this example, service chain <NUM> may be identified by a service path identifier (SPI) "<NUM>". The location of the network service for which backup service function information is being provided is indicated by the service index (SI) "<NUM>". The backup service function information specifies a network address of an active service function next hop and one or more network addresses of backup service function next hops for the active service function of the given service function chain. In this example, the backup service function information for service chain <NUM> at the location indicated by service index <NUM> includes an active service function next hop located at <NUM>. <NUM> and its backup service function next hop located at <NUM>. In this example, the backup service function information for service chain <NUM> at the location indicated by service index <NUM> includes another active service function next hop located at <NUM>. <NUM> and its backup service function next hop located at <NUM>. Traffic may be load balanced among active service functions.

In some examples, the backup service function information specifies network addresses of a plurality of backup service function next hops for an active service function. In this example, backup service function information for service chain <NUM> at the location indicated by service index <NUM> includes another active service function next hop located at <NUM>. <NUM> and a first backup service function next hop located at <NUM>. <NUM> and a second backup service function next hop located at <NUM>. Table <NUM> is only one example of a data structure storing backup service function information and may include additional information, such as metric information. In some examples, controller <NUM> may push active and backup service functions stored in table <NUM>. In other examples, table <NUM> may be generated based on the service function instance data such as data distributed with service function instance routes <NUM> and/or service function chain information included in service function chain route <NUM>.

When the classifier, e.g., service function instance 10A, receives a packet and has classified the packet to service function chain <NUM> with service path identifier of <NUM> in this example, service function instance 10A performs a lookup of table <NUM> to determine whether there are any backup service functions for the active service function instances in service function chain <NUM>. Service function instance 10A may include backup service function information (e.g., a network address of the computing device hosting a backup service function instance) in the network service header. For example, service function instance 10A encapsulates the packet with a network service header including the service path identifier "<NUM>," the service index "<NUM>," and an address of the computing device hosting backup service function instance 10C (e.g., <NUM>. <NUM>) and sends the packet encapsulated with the network service header to the service function next hop, e.g., service function instance 10B that is an active service function. In some examples, the classifier may include the backup service function information in the network service header during initialization or when the backup service function information is updated or changed.

In response to receiving the packet, the service function next hop may use the backup service function information in the network service header to identify the backup service functions with which to synchronize its session (e.g., flow state). For example, in response to receiving the network service header including the backup service function information, service function instance 10B may synchronize a NAT session with service function instance 10C identified by the backup service function information. As one example, a computing device that hosts the active service function may establish a communication session (e.g., TCP or UDP session) with the computing device that hosts the backup service function such that the active service function may synchronize state information with the backup service function. In this way, by sending the packet with the network service header including the backup service function information, the classifier may leverage a packet in the data plane to provide stateful synchronization between an active service function and a backup service function without the backup service function information needing to be statically configured by a controller, e.g., in the computing device hosting the classifier or the prior service function in the service function chain. By synchronizing the service function state data for packet flows, the active service function and backup service function may enable low-latency switchover to the backup service function because the backup service function has similar state as the active service function and can assume stateful processing of flows previously being processed by the active service function.

In some examples, a backup service function may change for a given service function chain. For example, the backup service function for active service function 10B of service function chain <NUM> may change from service function instance 10C to service function 10D (not shown in <FIG>). In this example, service function instance 10A, operating as the classifier, may add a network service header including updated backup service function information that identifies service function 10D such that the service function next hop (e.g., service function instance 10B) may use the updated backup service function information included in the network service header to perform stateful synchronization.

<FIG> is a block diagram illustrating an example computing device that provides one or more service function instances according to techniques described in this disclosure. Computing device <NUM> may represent a real or virtual server and includes in this example, a system bus <NUM> coupling hardware components of a computing device <NUM> hardware environment. System bus <NUM> couples memory <NUM>, network interface card (NIC) <NUM>, storage disk <NUM>, and microprocessor <NUM>. Network interface card <NUM> includes one or more interfaces configured to exchange packets using links of an underlying physical network. Microprocessor <NUM> may include one or more processors each including an independent execution unit to perform instructions that conform to an instruction set architecture. Execution units may be implemented as separate integrated circuits (ICs) or may be combined within one or more multicore processors (or "many-core" processors) that are each implemented using a single IC (i.e., a chip multiprocessor).

Disk <NUM> represents computer readable storage media that includes volatile and/or non-volatile, removable and/or non-removable media implemented in any method or technology for storage of information such as processor-readable instructions, data structures, program modules, or other data. Computer readable storage media includes, but is not limited to, random access memory (RAM), read-only memory (ROM), EEPROM, flash memory, CD-ROM, digital versatile discs (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information and that can be accessed by microprocessor <NUM>.

Memory <NUM> includes one or more computer-readable storage media, which may include random-access memory (RAM) such as various forms of dynamic RAM (DRAM), e.g., DDR2/DDR3 SDRAM, or static RAM (SRAM), flash memory, or any other form of fixed or removable storage medium that can be used to carry or store desired program code and program data in the form of instructions or data structures and that can be accessed by a computer. Memory <NUM> provides a physical address space composed of addressable memory locations.

Memory <NUM>, NIC <NUM>, storage disk <NUM>, and microprocessor <NUM> provide an operating environment for a software stack that executes a hypervisor <NUM> and one or more virtual machines 216A-<NUM> (collectively, "virtual machines <NUM>"). While illustrated and described with respect to virtual machines, service function instances 203A-<NUM> (collectively, "service function instances <NUM>") may be executed by other operating environments, such as containers (e.g., a DOCKER container). An operating system kernel (not shown in <FIG>) may execute in kernel space and may include, for example, a Linux, Berkeley Software Distribution (BSD), another Unix-variant kernel, or a Windows server operating system kernel, available from Microsoft Corp.

Computing device <NUM> executes a hypervisor <NUM> to manage virtual machines <NUM>. Example hypervisors include Kernel-based Virtual Machine (KVM) for the Linux kernel, Xen, ESXi available from VMware, Windows Hyper-V available from Microsoft, and other open-source and proprietary hypervisors.

Virtual machines <NUM> host corresponding service function instances <NUM>. Each of service function instances <NUM> may represent an example instance of a service function instance <NUM> of <FIG>. In some examples, a virtual machine <NUM> may host one or more service function instances <NUM>. Service function instances <NUM> are described hereinafter with respect to service function instance 203A. Service function instance <NUM> includes service function 220A for application to packet flows. Some examples of computing device <NUM> host only one service function instance <NUM>.

Service function 220A represents software that may apply any one of the aforementioned service functions described above with respect to service function instances <NUM>. Service function instance 203A may be orchestrated by a controller, such as controller <NUM>, to be executed by virtual machine 216A to apply service function 220A. Service function instance configuration data <NUM> includes data describing service function instance 203A. Service function instance configuration data <NUM> may specify the service function type of service function 220A and a service identifier for service function instance 203A, for example. Service function instance configuration data <NUM> may further describe a virtual machine tap or other identifier for virtual machine 216A that enables virtual router <NUM> to direct received packets to virtual machine 216A for processing using service function instance 203A.

Hypervisor <NUM> in the example computing device <NUM> provides an operating environment for a routing protocol module <NUM>, which may represent a process that executes various protocols at different layers of a network stack. In the example of <FIG>, network protocols include the Border Gateway Protocol (BGP) <NUM>, which is a layer <NUM> routing protocol. BGP <NUM> may include Multiprotocol BGP (MP-BGP). Routing protocol module <NUM> may execute other protocols not shown in <FIG>, such as an MPLS label distribution protocol and/or other MPLS protocols. Routing protocol module <NUM> is responsible for the maintenance of routing information <NUM> to reflect the current topology of a network to which computing device <NUM> is connected via NIC <NUM>. In particular, BGP <NUM> updates routing information <NUM> to accurately reflect the topology of the network and other entities based on routing protocol messages received by computing device <NUM>.

Routing protocol module <NUM> uses BGP to send and receive service function routes that distribute service function instance data and service function chain data for describing service function overlay network nodes and topology. Routing protocol module <NUM> may receive one or more service function instance (SFI) routes <NUM> and one or more service function chain routes <NUM> and store the service function routes to routing information <NUM>. Service function instance routes <NUM> and service function chain routes <NUM> may represent instances of service function instance routes <NUM> and service function chain route <NUM>, respectively, of <FIG>.

Routing protocol module <NUM> may generate and output service function instance routes <NUM> to advertise service function instances <NUM> of computing device <NUM>. That is, routing protocol module <NUM> may originate such service function instance routes <NUM>. For example, routing protocol module <NUM> may obtain, for service function instance 203A, the service function type of service function 220A and the service identifier for service function instance 203A from service function instance configuration data <NUM>. Routing protocol module <NUM> may generate a service function instance route from the service function type and service identifier and output the service function instance route via network interface card <NUM>.

Virtual router <NUM> of hypervisor <NUM> may manage one or more virtual networks configured for computing device <NUM>, such as an overlay network for service function instances <NUM>. Additional description of a virtual router is found in <CIT>. Packets received by the network interface card <NUM>, for instance, from an underlying physical network may include an outer header to allow the physical network to tunnel the payload or "inner packet" to a physical network address for NIC <NUM> of computing device <NUM> that executes the virtual router <NUM>. The outer header may include not only a physical network address of NIC <NUM> of the computing device but also a network service header. Aspects of virtual router <NUM> may be executed in user space rather than in hypervisor <NUM>. For instances, aspects of virtual router <NUM> including aspects of service function forwarder <NUM> may be executed by virtual machines <NUM>.

Service function forwarder <NUM> provides a service function data plane and determines forwarding of packets according to service function chains. In some examples, computing device <NUM> may include a separate instance of service function forwarder <NUM> for each service function instance <NUM>. Service function forwarder <NUM> may be executed in part, in some examples, by specialized hardware designed to support virtual networking. Service function forwarder <NUM> may be executed by an application in user space rather than in hypervisor <NUM>.

Service function forwarder <NUM> may be conceptualized as a portal in the underlay network through which service function instances <NUM> may be reached. Note that while service function forwarder <NUM> and routing protocol module <NUM> are illustrated and described as separate modules, operations of routing protocol module <NUM> to import and export and process routes, e.g., may be considered control plane operations of service function forwarder <NUM>. In addition, as used herein, the term "service function forwarder" may refer to computing device <NUM> as a whole as such operations relate to service function route import/export/selection, packet forwarding in the service overlay network, and so forth, but excluding the operations of service function instances <NUM>.

When service function forwarder <NUM> receives a service function chain route, service function forwarder <NUM> may determine whether to import the service function chain route based on the route target. If the service function forwarder <NUM> imports the route, the service function forwarder <NUM> may determine whether it is on the described service function chain by determining whether a route distinguisher for computing device <NUM> is specified for any of the service indices / hops of the service function chain. If so, the service function forwarder <NUM> may create forwarding state for incoming packets and forwarding state for outgoing packets that have been processed by one of service function instances <NUM>.

The service function forwarder <NUM> may create local forwarding state making the association between the service path identifier / service index and a specific service function instance as identified by the route distinguisher for the service function instance route and service type combination. The service function forwarder <NUM> may also create next hop forwarding state for packets received back from the local service function instance <NUM> that need to be forwarded to the next hop in the service function chain. There may be a choice of next hops. The service function forwarder <NUM> may install forwarding state for all potential next hops, or may make choices and only install forwarding state to a subset of the potential next hops. The installed forwarding state may change over time reacting to changes in the underlay network and the availability of particular service function instances <NUM>. Note that service function forwarder <NUM> may only create and store forwarding state for the service function chain on which it is included, in some cases. That is, service function forwarder <NUM> may not maintain state for all service function chains advertised.

This selection of forwarding state includes determining from the service function chain route the service index to put in the network service header of the outbound packet. This selection may be conditional on information returned from the local service function instance <NUM>. A service function forwarder <NUM> may also install forwarding state to support looping, jumping, and branching.

Network interface card <NUM> receives packets of packet flows. The packet flows may be classified to a service function chain that includes service function instance 203A. A packet received by network interface card <NUM> may include a tunnel encapsulation header that identifies the packet for processing by service function forwarder <NUM>. Service function forwarder <NUM> may remove the tunnel encapsulation header. A packet to be processed by service function forwarder <NUM> and received from a previous service function instance (executed by computing device <NUM> or another computing device) may include a network service header having a service path identifier and a service index.

The service function forwarder <NUM> may determine service function instance 203A is to apply service function 220A to the packet, based on the network service header. For example, the service function forwarder <NUM> may determine the service function chain route <NUM> having a matching service path identifier and key the service index from the network service header to determine service function instance 203A is indicated for the service index. The service function instance 203A may be indicated for the service index in the matching service function chain route <NUM> using a combination of service function type and service identifier that identify the service function instance 203A. The service function instance in some cases may be indicated by the service function type only, the service function type corresponding to at least one of service functions <NUM>. For instance, the service function instance may be indicated by the service function type only if the service identifier indicates that any service function instance that supports the service function type may apply the service function. In example instances of computing device <NUM> in which there is an instance of a service function forwarder <NUM> per service function instance <NUM> (e.g., only one service function forwarder <NUM> and one service function instance <NUM>), the service function forwarder <NUM> may direct its corresponding service function instance <NUM> to apply a service function to a received packet without first having to determine the particular service function instance <NUM> to apply the service function.

Service function forwarder <NUM> may direct service function instance 203A to process the packet based in part on the network service header. Service function instance 203A processes the packet by applying service function 220A. In addition to or as part of processing the packet by applying the service function 220A, service function instance 203A may determine a new network service header for the packet. That is, service function instance 203A may select the next service function instance along the service chain (or another service chain) that is to process the packet. Service function 203A may select between multiple service function instances (in some cases of different service function types). The service index and service path identifier in the new network service header may indicate the next service function in the service chain, a previous service function in the chain (known as "looping"), or a service function further down the chain (known as "jumping"). The service index and service path identifier in the new network service header may alternatively indicate a service function on a different service function chain (known as "branching").

Service function forwarder <NUM> subsequently selects a service function instance that provides the service function denoted by the service path identifier and service index in the next network service header, and service function forwarder <NUM> forwards the packet to the service function forwarder that supports the selected service function instance.

The service index in the new network service header received from service function instance 203A may leave the service function forwarder <NUM> with a choice of next hop service function types, and service function instances for each service function types. That is, the service index indicates a set of one or more entries in the service function chain route <NUM> for the service path identifier, each of which corresponds to a service function type and the service identifier (e.g., route distinguisher) of a service function instance route <NUM> that advertised a specific service function instance. The service function forwarder <NUM> selects one of these service function instances, identifies the service function forwarder that supports the chosen service function instance, and sends the packet to that next hop service function forwarder. Additional examples of computing device <NUM> processing the packet for a service function next hop is described in <CIT>.

In accordance with the techniques described in this disclosure, a service function instance <NUM> operating as a classifier may add a network service header including backup service function information. In this example, service function instance 203A may operate as a service function classifier. Service function instance 203A may classify a packet to a service function chain. To notify active service functions in the service function chain of their backup service functions, service function instance 203A encapsulates a network service header including backup service function information.

For example, service function instance 203A may determine, from backup service function information <NUM>, one or more backup service functions for the active service functions of the service function chain. Backup service function information <NUM> may represent a table (e.g., table <NUM> of <FIG>) including backup service function information. Computing device <NUM> may perform a lookup of backup service function information <NUM> to identify one or more backup service functions for an active service function of a given service chain.

In response to determining one or more backup service functions for the active service functions of the service function chain, service function instance 203A encapsulates the received packet with a network service header including the location of one or more backup service functions determined from backup service function information <NUM>, and forwards the packet to a service function next hop to enable the service function next hop synchronize its state information with its backup service functions.

For example, assume network interface card <NUM> of computing device <NUM> receives a packet from a previous service function instance (e.g., the classifier executed by another computing device <NUM>) that is encapsulated with a network service header including backup service function information. Service function forwarder <NUM> processes the packet and may determine that a service function instance hosted by another computing device may apply a service function as a backup for service function instance 203A. In this example, service function instance 203A may send state information 250A to the other computing device that hosts the backup service function to synchronize its state with the backup service function. If the network service header includes a plurality of backup service functions, the service function instance 203A may send state information 250A to each of the computing devices that host the backup service functions to synchronize its forwarding state with each of the backup service functions.

<FIG> illustrate an example tunnel packet and a network service header, respectively, in accordance with techniques of this disclosure. <FIG> illustrates an example tunnel packet to steer an inner packet along a service function chain, in accordance with techniques of this disclosure. In the example of <FIG>, an original inner packet <NUM> having header <NUM> and payload <NUM> is encapsulated with a network service header <NUM> and encapsulated as payload <NUM> using outer (or encapsulation) header <NUM> to form tunnel packet <NUM>.

Outer header <NUM> may include tunnel encapsulation data advertised in encapsulation attributes <NUM> or otherwise included in service function instance routes. Outer header <NUM> enables the underlay network to forward tunnel packet <NUM> to a computing device that hosts a service function instance identified in network service header <NUM>. As further described in <FIG>, network service header <NUM> may include a base header <NUM> including information to realize a service function path. For example, network service header <NUM> may include a service path identifier and a service index.

In accordance with the techniques described in this disclosure, network service header <NUM> may further include backup service function information <NUM>. A service function classifier that receives a packet classified to a service function chain may add network service header <NUM> including a service path identifier, a service index, and backup service function information.

A computing device that receives tunnel packet <NUM> may determine a service function instance hosted by the computing device to process the inner packet <NUM>, based on a service function instance route stored by the computing device that describes the service function chain identified by the network service header <NUM>. The computing device may also determine from the backup service function information <NUM> included in the network service header <NUM> one or more computing devices that host one or more backup service functions for the service function instance hosted by the computing device.

<FIG> is an example of the network service header <NUM> in greater detail. For example, network service header <NUM> includes a base header <NUM> (otherwise referred to as "NSH Service Path Header") to realize a service path and backup service function information <NUM>. Base header <NUM> includes at least a service path identifier that identifies a service function chain. In some examples, network service header <NUM> may include a service path identifier and another service function chain identifier that in combination identify a service function chain. Network service header <NUM> may further include a service index that identifies a next service function in the service function chain to be applied. Base header <NUM> may also include other information, such as a metadata type (illustrated as "MD TYPE" in <FIG>) to indicate that network service header <NUM> includes one or more variable-length context headers that, in accordance with the techniques described in this disclosure, include backup service function information, such as one or more network addresses of computing devices that host backup service functions, e.g., service function backup nodes 314A-314N (collectively, "backup service function nodes <NUM>").

As one example, the variable-length context header may include fields such as a metadata class, type, an unassigned bit, the length of the variable-length metadata, and the variable-length metadata that specify the one or more network addresses of computing devices that host backup service functions. The metadata class may define the scope of the type field. The type field may specify the type of metadata being carried. The length field may specify the length of the variable-length metadata. As one particular example, the variable-length context header may specify a metadata class of 0x0000, which is a type that may be assigned by the Internet Assigned Numbers Authority (IANA) to specify the base NSH metadata class, and a value for the metadata type that indicates the network service header includes backup service function information.

A service function instance operating as a classifier (e.g., service function instance 10A of <FIG>) may add a packet including network service header <NUM> including backup service function information <NUM>, and forward the encapsulated packet to a service function next hop such that the service function next hop may perform stateful synchronization with the computing devices identified by service function backup nodes <NUM>.

<FIG> is a block diagram illustrating further details of one example of a computing device that operates in accordance with one or more techniques of the present disclosure. <FIG> may illustrate a particular example of a server or other computing device <NUM> that includes one or more processor(s) <NUM> for executing any one or more of controller <NUM>, service function instances <NUM>, or any other computing device described herein. Other examples of computing device <NUM> may be used in other instances. Although shown in <FIG> as a stand-alone computing device <NUM> for purposes of example, a computing device may be any component or system that includes one or more processors or other suitable computing environment for executing software instructions and, for example, need not necessarily include one or more elements shown in <FIG> (e.g., communication units <NUM>; and in some examples components such as storage device(s) <NUM> may not be co-located or in the same chassis as other components).

As shown in the specific example of <FIG> computing device <NUM> includes one or more processors <NUM>, one or more input devices <NUM>, one or more communication units <NUM>, one or more output devices <NUM>, one or more storage devices <NUM>, and user interface (UI) device <NUM>, and communication unit <NUM>. Computing device <NUM>, in one example, further includes one or more applications <NUM>, orchestration module <NUM>, routing protocol module <NUM>, operating system <NUM> that are executable by computing device <NUM>. Computing device <NUM> further includes routing information <NUM>. Each of components <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> are coupled (physically, communicatively, and/or operatively) for inter-component communications. In some examples, communication channels <NUM> may include a system bus, a network connection, an inter-process communication data structure, or any other method for communicating data. As one example, components <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> may be coupled by one or more communication channels <NUM>.

Processors <NUM>, in one example, are configured to implement functionality and/or process instructions for execution within computing device <NUM>. For example, processors <NUM> may be capable of processing instructions stored in storage device <NUM>. Examples of processors <NUM> may include, any one or more of a microprocessor, a controller, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or equivalent discrete or integrated logic circuitry.

One or more storage devices <NUM> may be configured to store information within computing device <NUM> during operation. Storage device <NUM>, in some examples, is described as a computer-readable storage medium. In some examples, storage device <NUM> is a temporary memory, meaning that a primary purpose of storage device <NUM> is not long-term storage. Storage device <NUM>, in some examples, is described as a volatile memory, meaning that storage device <NUM> does not maintain stored contents when the computer is turned off. Examples of volatile memories include random access memories (RAM), dynamic random access memories (DRAM), static random access memories (SRAM), and other forms of volatile memories known in the art. In some examples, storage device <NUM> is used to store program instructions for execution by processors <NUM>. Storage device <NUM>, in one example, is used by software or applications running on computing device <NUM> to temporarily store information during program execution.

Storage devices <NUM>, in some examples, also include one or more computer-readable storage media. Storage devices <NUM> may be configured to store larger amounts of information than volatile memory. Storage devices <NUM> may further be configured for long-term storage of information. In some examples, storage devices <NUM> include non-volatile storage elements. Examples of such non-volatile storage elements include magnetic hard discs, optical discs, floppy discs, flash memories, or forms of electrically programmable memories (EPROM) or electrically erasable and programmable (EEPROM) memories.

Computing device <NUM>, in some examples, also includes one or more communication units <NUM>. Computing device <NUM>, in one example, utilizes communication units <NUM> to communicate with external devices via one or more networks, such as one or more wired/wireless/mobile networks. Communication units <NUM> may include a network interface card, such as an Ethernet card, an optical transceiver, a radio frequency transceiver, or any other type of device that can send and receive information. Other examples of such network interfaces may include wireless mobile network technology (e.g., <NUM>, LTE, <NUM>) and WiFi radios. In some examples, computing device <NUM> uses communication unit <NUM> to communicate with an external device.

Computing device <NUM>, in one example, also includes one or more user interface devices <NUM>. User interface devices <NUM>, in some examples, are configured to receive input from a user through tactile, audio, or video feedback. Examples of user interface devices(s) <NUM> include a presence-sensitive display, a mouse, a keyboard, a voice responsive system, video camera, microphone or any other type of device for detecting a command from a user. In some examples, a presence-sensitive display includes a touch-sensitive screen.

One or more output devices <NUM> may also be included in computing device <NUM>. Output device <NUM>, in some examples, is configured to provide output to a user using tactile, audio, or video stimuli. Output device <NUM>, in one example, includes a presence-sensitive display, a sound card, a video graphics adapter card, or any other type of device for converting a signal into an appropriate form understandable to humans or machines. Additional examples of output device <NUM> include a speaker, a cathode ray tube (CRT) monitor, a liquid crystal display (LCD), or any other type of device that can generate intelligible output to a user.

Computing device <NUM> may include operating system <NUM>. Operating system <NUM>, in some examples, controls the operation of components of computing device <NUM>. For example, operating system <NUM>, in one example, facilitates the communication of one or more applications with processors <NUM>, communication unit <NUM>, storage device <NUM>, input device <NUM>, user interface devices <NUM>, and output device <NUM>.

Orchestration module <NUM> may orchestrate service function instances in a service function overlay network and generate service function chains. A network service provider operator may configure the service function chains using user interface devices <NUM> and/or input devices <NUM>.

Routing protocol module <NUM> may represent a process that executes various protocols at different layers of a network stack. In the example of <FIG>, network protocols include the Border Gateway Protocol (BGP) <NUM>, which is a layer <NUM> routing protocol. BGP <NUM> may include Multiprotocol BGP (MP-BGP). Routing protocol module <NUM> may execute other protocols not shown in <FIG>, such as an MPLS label distribution protocol and/or other MPLS protocols. Routing protocol module <NUM> is responsible for the maintenance of routing information <NUM> to reflect the current topology of a network to which computing device <NUM> is connected via one of communication units <NUM>. In particular, BGP <NUM> updates routing information <NUM> to accurately reflect the topology of the network and other entities based on routing protocol messages received by computing device <NUM>.

Routing protocol module <NUM> uses BGP to send receive service function routes that distribute service function instance data and service function chain data for describing service function overlay network nodes and topology. Routing protocol module <NUM> may receive one or more service function instance routes <NUM> and may receive one or more service function chain routes <NUM> and store the service function routes to routing information <NUM>. Service function instance routes <NUM> and service function chain routes <NUM> may represent instances of service function instance routes <NUM> and service function chain route <NUM> of <FIG>.

Using service function instance routes <NUM> received or generated by computing device <NUM>, routing protocol module <NUM> may generate and output service function chain routes <NUM> to advertise service function chains configured for a service function overlay network controlled at least in part by computing device <NUM>. That is, routing protocol module <NUM> may originate such service function chain routes <NUM> and inject the routes into the service function overlay network.

In accordance with the techniques described herein, computing device <NUM> includes a network service header module <NUM> to provide backup service function notification and synchronization. In an example in which processor(s) <NUM> of computing device <NUM> execute a service function instance operating as a service function classifier (e.g., an ingress to the service function overlay network such as service function instance 10A of <FIG>), network service header module <NUM> may store backup service function information <NUM> (e.g., in routing information <NUM>). In some examples, network service header module <NUM> may generate backup service function information based on service function instance routes <NUM> and service function chain routes <NUM>. In other examples, network service header module <NUM> may receive backup service function information from a controller. As described above, backup service function information <NUM> may include network addresses of computing devices that host backup service functions.

Network service header module <NUM> may determine one or more backup service functions for an active service function of a service chain. For example, in response to receiving a packet and classifying the packet to a service chain, network service header module <NUM> may determine one or more backup service functions resulting from a lookup of backup service function information <NUM>. Network service header module <NUM> may encapsulate the packet with a network service header including backup service function information <NUM>. For example, the network service header may include a service path identifier, a service index, and one or more network addresses (e.g., IP addresses) of computing devices that host one or more backup service functions, such as the network service header illustrated in <FIG>.

In the example in which processor(s) <NUM> of computing device <NUM> execute a service function instance that receives a packet encapsulated with a network service header including backup service function information (e.g., service function instance 10B of <FIG>), the network service module <NUM> may identify the one or more computing devices that host one or more backup service functions from the network service header information and send state information of computing device <NUM> to the computing devices identified from the backup service function information included in the network service header.

<FIG> is a block diagram illustrating an example service function chaining architecture reference model, according to techniques described herein. In this example, service function overlay network <NUM> operates over a physical underlay network of interconnected computing devices each providing an operating environment for one or more service function forwarders 504A-504D. Each of service function forwarders <NUM> may represent an example instance of service function forwarder <NUM> or any service function forwarder described herein. Tunnels <NUM> connect pairs of service function forwarders <NUM> over the underlay network.

Service function overlay network <NUM> includes service function instances 506A-506D (collectively, "service function instances <NUM>") and classifier <NUM>, which may also represent a service function instance. Each of service function instances <NUM> and classifier <NUM> is hosted or otherwise local to one of service function forwarders <NUM>. For example, service function instances 506A, 506B are local to service function forwarder 504B and service function instance 506D is local to service function forwarder 504D. Service function instances <NUM> may have a different service function type <NUM>. For example, service function instances 506A, 506B, and 506C all have service function type 508A, while service function instance 506D has a different service function type 508B.

Service function overlay network <NUM> is merely one example. Examples of service function overlay network <NUM> may have any number of service function forwarders <NUM>, service function instances <NUM>, and may be arranged in various overlay topologies as determined by the configuration of tunnel interfaces for tunnels <NUM>.

Packets <NUM> ingress at classifier <NUM>, which classifies each packet to a service function chain of one or more service function instances <NUM>. Service function forwarders <NUM> exchange service function chain routes and service function instance routes as described elsewhere herein. Service function forwarders <NUM> select a next service function instance <NUM> and forward each classified packet along its service function chain via tunnels <NUM> to the next hop service function forwarder <NUM> that is local for the next service function instance <NUM>, via tunnels <NUM>. Once the last service function instance 506D in the service function chain processes the packets, the last service function forwarder 504D may egress the processed packets <NUM> from the service function overlay network <NUM> to their respective destinations.

In the example of <FIG>, a service function chain may include service function instance 506A and a next hop of service function instance 506D. That is, service function instance 506A and service function instance 506D are active service functions of the service function chain. Service function instance 506C may operate as a backup service function for service function instance 506A of the service function chain.

Classifier <NUM> receives packets <NUM> and classifies the packet to a service function chain. Classifier <NUM> may determine one or more backup service functions for active service functions of the service function chain. For example, classifier <NUM> may determine that service function instance 506C may operate as a backup service function for service function instance 506A. Classifier <NUM> encapsulates packets <NUM> with a network service header including a service path identifier, a service index, and backup service function information. As described in this disclosure, the backup service function information <NUM> (e.g., backup service information stored in table <NUM> of <FIG>) may include, for example, one or more network addresses of computing devices that host the backup service functions. In this example, the network service header includes a network address of service function forwarder 504C that hosts backup service function instance 506C and forwards the packet to service function forwarder 504B, which will forward the packet to the service function next hop, e.g., service function instance 506A. In response to receiving the packet, service function forwarder 504B may decapsulate the network service header from the packet and sends the packet to service function instance 506A. Service function forwarder 504B may also identify, based on the backup service function information included in the network service header, that service function forwarder 504C hosts backup service function instance 506C. Service function forwarder 504B may inform service function instance 506A that service function forwarder 504C hosts backup service function instance 506C. In response, service function instance 506A may send the state information to service function forwarder 504C that hosts service function instance 506C to synchronize its state information with backup service function instance 506C.

<FIG> is a block diagram illustrating an example service function overlay network, according to techniques described herein. Service function overlay network <NUM> may be an example instance of service function overlay network <NUM>. In this example, service function overlay network <NUM> includes service function forwarders <NUM>, service function instances <NUM>, classifier <NUM>, and is managed by controller <NUM>. Tunnels are not shown for ease of illustration. Each service function instance <NUM> has a corresponding service function type <NUM> value that is illustrated in <FIG>. For example, the service function type 608A value is <NUM> and is shared by service function instances 606A, 606C, the service function type 608B value is <NUM> and is provided by service function instance 606E, the service function type 608C value is <NUM> and is shared by service function instances 606D, <NUM>, and the service function type 608D value is <NUM> and is shared by service function instances 606B, 606F, and <NUM>.

Each of service function forwarders 604A-604D has a corresponding network address illustrated in <FIG>. Although illustrated and described with respect to an IPv4 address, other types of network addresses are contemplated, e.g., IPv6. For instance, service function forwarder 604A has IP address <NUM>. <NUM>, service function forwarder 604B has IP address <NUM>. <NUM>, service function forwarder 604C has IP address <NUM>. <NUM>, and service function forwarder has IP address <NUM>. Service function forwarder 604A provides access to service function instances 606A, 606B. Service function forwarder 604B provides access to service function instances 606C, 606D. Service function forwarder 604C provides access to service function instances 606E, 606F. Service function forwarder 604D provides access to service function instances <NUM>, <NUM>. Service function forwarder 604E provides access to classifier <NUM>. Controller <NUM> has IP address <NUM>.

Each of service function forwarders <NUM> advertise routes to the service function instances <NUM> it provides access to. The following are example service function instance routes for service function instances <NUM>:.

Route distinguisher (RD) is an example of a service distinguisher and includes the IP address of the advertising host and another value, and SFT is the service function type for the service function instance being advertised. Addressing used for communicating between service function forwarders <NUM> is taken from the Tunnel Encapsulation attribute of the service function instance route and not from the RDs of the route.

A service function chain route may define an explicit service function chain (i.e., defines a specific service function next hop), a service function chain that provides a choice of service function instances (i.e., defines a choice of next hop service function forwarder to execute the next hop in the chain), a service function chain with an open choice of service function instances (e.g., defines a choice of next hop service function forwarder that support service functions of a particular service function type), a service function chain with a choice of service function types, correlated bidirectional service function chains, correlated bidirectional and asymmetrical service function chains, asymmetric bidirectional service function chains, a service chain to provide looping, jumping, or branching.

The following is an example of a service function chain. Consider the following service function chain route:.

The service function chain for SFC1 consists of a service function of type <NUM> located at service function forwarder 604A followed by a service function of type <NUM> located at service function forwarder 604B. In one example, classifier <NUM> may receive a packet of packets <NUM> that is classified to SFC1. Classifier <NUM> determines backup service function information for the active service functions of SFC1. For example, service function instance 606C may operate as a backup service function for service function instance 606A of type 608A having value <NUM>. In this example, backup service function information <NUM> may specify an active service function next hop with a network address of service function forwarder 604A (e.g., RD = <NUM>. <NUM>,<NUM>) and a backup service function next hop with a network address of service function forwarder 604B (e.g., RD = <NUM>. <NUM>,<NUM>) that hosts backup service function instance 606C.

Classifier <NUM> sends the packet on the chain to service function forwarder 604A, the packet including a network service header specifying a service path identifier (SPI) (value = <NUM>), a service index of <NUM>, and the backup service function information, as provided below:.

Service function forwarder 604A may receive the packet encapsulated with the network service header including the backup service function information and identifies the service function chain from the SPI and service index. Service function forwarder 604A determines that for initial service index <NUM>, service function forwarder 604A is to deliver the packet to the service function instance 606A having service function type 608A with value <NUM>. Service function forwarder 604A also determines that for initial service index <NUM>, service function forwarder 604B provides access to the backup service function instance 606C. Service function forwarder 604A delivers the packet to the service function instance 606A having service function type 608A with value <NUM>. Service function forwarder 604A may also inform service function instance 606A the location of its backup service function instance. Service function instance 606A may send its state information (illustrated in <FIG> as <NUM>) to service function forwarder 604B that hosts service function instance 606C to synchronize state information with service function instance 606C.

When the packets are returned to service function forwarder 604A by the service function instance 606A, the service index will be decreased to <NUM> for the next hop. Service function forwarder 604A forwards the packet to service function forwarder 604B, which will send the packets to the service function instance 606D having service function type 608C with value <NUM> before forwarding the packets to their destinations. Service function forwarder 604B determines that for service index <NUM>, service function forwarder 604B is to deliver the packet to the service function instance 606D having service function type 608C with value <NUM>.

In some examples, an active service function may have a plurality of backup service functions. Consider the following example service function chain route:.

The service function chain for SFC2 consists of a service function of type <NUM> located at service function forwarder 604A followed by a service function of type <NUM> located at service function forwarder 604C. In one example, classifier <NUM> may receive a packet of packets <NUM> that is classified to SFC2. Classifier <NUM> determines backup service function information for the active service functions of SFC2. For example, service function instance 606B and service function instance <NUM> may each operate as a backup service function for service function instance 606F of type 608B having value <NUM>. In this example, backup service function information <NUM> may specify an active service function next hop with a network address of service function forwarder 604C (e.g., RD = <NUM>. <NUM>,<NUM>) and a first backup service function next hop with a network address of service function forwarder 604A (e.g., RD = <NUM>. <NUM>,<NUM>) and a second backup service function next hop with a network address of service function forwarder 604D (e.g., RD = <NUM>. <NUM>,<NUM>).

Service function forwarder 604A may receive the packet encapsulated with the network service header including the backup service function information and identifies the service function chain from the SPI and service index. Service function forwarder 604A determines that for initial service index <NUM>, service function forwarder 604A is to deliver the packet to the service function instance 606A having service function type 608A with value <NUM>. When the packets are returned to service function forwarder 604A by the service function instance 606A the service index will be decreased to <NUM> for the next hop. Service function forwarder 604A forwards the packet to service function forwarder 604C, which will send the packets to the service function instance 606F having service function type 608D with value <NUM> before forwarding the packets to their destinations. Service function forwarder 604C may also inform service function instance 606F the location of its backup service function instances, e.g., service function forwarder 604A (e.g., <NUM>. <NUM>,<NUM>) and service function forwarder 604D (e.g., <NUM>. <NUM>,<NUM>). Service function instance 606F may send its state information (illustrated in <FIG> as 612A) to service function forwarder 604A that hosts service function instance 606B to synchronize state information with service function instance 606B. Similarly, service function instance 606F may send its state information (illustrated in <FIG> as 612B) to service function forwarder 604D that hosts service function instance <NUM> to synchronize state information with service function instance <NUM>.

<FIG> is a flowchart illustrating an example mode of operation, in according to techniques of this disclosure. Operation <NUM> is described with respect to <FIG>. Operation <NUM> is also described with respect to computing device <NUM> of <FIG> but may be performed by any computing or network device.

Classifier <NUM> may receive a packet (e.g., of packets <NUM>) and classifies the packet to a service function chain (<NUM>). For example, computer device <NUM>, operating as classifier <NUM>, may match the packet to policies that each specifies a service path identifier that identifies a given service function chain. As one example, classifier <NUM> receives a service function chain route for SFC1 of <FIG>. In response to receiving a packet, classifier <NUM> may apply the policies to packet header fields (e.g., <NUM>-tuple values) of the packet to determine a service function chain (e.g., SFC1 of <FIG>) is applied to the packet. As described above, SFC1 may identify a service function chain including service function instance 606A followed by service function instance 606D.

Classifier <NUM> determines one or more backup service functions for an active service function of the service function chain (<NUM>). For example, classifier <NUM> may perform a lookup of a table including backup service function information (e.g., backup service function information <NUM> of <FIG>) and determine the location of backup service functions for service function instance 606A and service function instance 606D. In this example, backup service function information <NUM> may specify an active service function next hop with a network address of service function forwarder 604A (e.g., RD = <NUM>. <NUM>,<NUM>) and a backup service function next hop with a network address of service function forwarder 604B (e.g., RD = <NUM>. <NUM>,<NUM>). Backup service function information <NUM> may also specify an active service function next hop with a network address of service function forwarder 604B (e.g., RD = <NUM>. <NUM>,<NUM>) and a backup service function next hop with a network address of service function forwarder 604D (e.g., RD = <NUM>. <NUM>,<NUM>).

To realize the service path, classifier <NUM> encapsulates the packet with a network service header including a service path identifier for the service function chain (e.g., SPI = <NUM>) and a service index (SI = <NUM>) for the first hop in the selected service function chain. In accordance with the techniques described in this disclosure, classifier <NUM> further includes backup service function information in the network service header (<NUM>). For example, classifier <NUM> includes a network address of computing devices that host the backup service function instances. For instance, a packet classified to SFC1 is encapsulated with a network service header including a service path identifier of <NUM>, a service index of <NUM>, and a network address of service function forwarder 604B to indicate the location of the backup service function instance 606D for active service function instance 606A.

Classifier <NUM> sends the packet encapsulated with the network service header including the backup service function information to the first service function instance (e.g., service function instance 606A) in the service chain (<NUM>). For example, classifier <NUM> sends the packet to service function forwarder 604A, which will deliver the packet to service function instance 606A in the service chain.

Service function instance 606A may receive the packet encapsulated with the network service header including the backup service function information (<NUM>) and sends, based at least on the backup service function information included in the network service header, state information for the active service function to the computing devices that host the one or more backup service functions (<NUM>). For example, service function instance 606A may identify the service chain from service path identifier of <NUM>, and the one or more computing devices that host the one or more backup service functions specified in variable-length context headers of the network service header.

Service function instance 606A may send state information to the one or more computing devices that host the one or more backup service functions (<NUM>). In this example, service function instance 606A (e.g., the active service function) may send state information to service function instance 606D (e.g., the backup service function).

Although not illustrated in <FIG>, each service function next hop may receive the packet encapsulated with the network service header including the backup service function information, and synchronize its session state with computing devices identified from the backup service function information. For example, classifier <NUM> may send another packet encapsulated with a network service header including a service path identifier for the service function chain (e.g., SPI = <NUM>) and a service index (SI = <NUM>) for the second service function instance in the selected service chain, and backup service information to enable the computing device that hosts the second service function instance in the service chain to synchronize, based at least on the backup service function information, state information with the one or more backup service functions identified from the backup service function information.

According to the claimed invention there is defined a method comprising: receiving, from a service function classifier and by a computing device that hosts an active service function of a service function chain, a packet classified to the service function chain, wherein the packet is encapsulated with a network service header that includes backup service function information for the active service function of the service function chain; and sending, by the computing device and based at least on the backup service function information included in the network service header, state information for the active service function to one or more computing devices that host one or more backup service functions identified by the backup service function information.

Furthermore, according to the claimed invention there is also defined a method comprising: classifying, by a service function classifier, a packet to a service function chain; determining, by the service function classifier, one or more backup service functions for an active service function of the service function chain; encapsulating, by the classifier, the packet with a network service header, wherein the network service header includes backup service function information identifying one or more computing devices that host the one or more backup service functions; and sending, by the classifier, the packet encapsulated with the network service header to a computing device that hosts the active service function in the service function chain to enable the computing device that hosts the active service function to send, based at least on the backup service function information, state information for the active service function with the one or more backup service functions.

If implemented in hardware, this disclosure may be directed to an apparatus such as a processor or an integrated circuit device, such as an integrated circuit chip or chipset. Alternatively, or additionally, if implemented in software or firmware, the techniques may be realized at least in part by a computer-readable data storage medium comprising instructions that, when executed, cause a processor to perform one or more of the methods described above. For example, the computer-readable data storage medium may store such instructions for execution by a processor.

A computer-readable medium may form part of a computer program product, which may include packaging materials. A computer-readable medium may comprise a computer data storage medium such as random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), Flash memory, magnetic or optical data storage media, and the like. In some examples, an article of manufacture may comprise one or more computer-readable storage media.

In some examples, the computer-readable media may be a storage medium comprising non-transitory media. The term "non-transitory" may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in RAM or cache). In other examples, the computer-readable medium may be a transitory medium such as a carrier signal or transmission medium.

The code or instructions may be software and/or firmware executed by processing circuitry including one or more processors, such as one or more digital signal processors (DSPs), general purpose microprocessors, application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs), or other equivalent integrated or discrete logic circuitry. In addition, in some aspects, functionality described in this disclosure may be provided within software modules or hardware modules.

Claim 1:
A method comprising:
receiving, from a service function classifier and by a computing device (<NUM>, <NUM>) that hosts an active service function of a service function chain, a packet (<NUM>) classified to the service function chain,
wherein the packet is encapsulated with a network service header (<NUM>) that includes backup service function information (<NUM>) for the active service function of the service function chain; and
sending, by the computing device and based at least on the backup service function information included in the network service header, state information (250A) for the active service function to one or more computing devices that host one or more backup service functions identified by the backup service function information.