Patent Description:
A computer network is a collection of interconnected computing devices that can exchange data and share resources. In a packet-based network, the computing devices communicate data by dividing the data into small blocks called packets, which are individually routed across the network from a source device to a destination device. The destination device extracts the data from the packets and assembles the data into its original form. Dividing the data into packets enables the source device to resend only those individual packets that may be lost during transmission.

Network service providers provide services such as security, tunneling, virtual private networks, filtering, load-balancing, VoIP/Multimedia processing, proxies, and other types of services to incoming packets. Service providers also provide content-specific services designed to improve the quality of a user's experience, for example, video streaming and caching. To provide these new services, a network service provider may direct packets along a "service chain," where the service chain represents a set of functions that are applied to the packet virtual or physical compute nodes. <NPL>, discloses 'this document defines Subscriber and Performance Policy Identifiers Network Service Header Variable-Length Context Headers'. <CIT> relates to `Service function path performance monitoring'.

Any embodiments or examples of the following description which are not within the scope of the appended claims are provided for illustrative purposes. This disclosure describes techniques that include adding information to a network service header for packets being processed by a set of compute nodes in a network service chain. The information added to the network service header can be used during selection of the next hop in a service chain, and may be used to help ensure that service level agreements (SLA) or other constraints are met with respect to one or more metrics. In some examples, techniques described herein may involve including SLA information in a network service header, and enabling each of the nodes in a service chain to dynamically update the information as the packet is processed in the service chain. For instance, in some examples, service nodes each maintain a table of information about round-trip times (RTT) between adjacent nodes in a service chain. As each node processes a packet in a service chain, each node includes, within the network service header, information about the current metrics relative to the SLA requirements. For instance, as each node in a service chain processes a network packet, each node may update the network packet to include information about how much RTT remains relative to an SLA requirement for the overall RTT to be consumed by the service chain. Accordingly, the information stored within the network services header for the packet may change dynamically as that packet is processed in the service chain. Such metrics that may be reflected in a network services header may include RTT, as wells as other metrics, including as jitter and packet loss tolerances. Accordingly, this disclosure describes techniques that include embedding, within a network packet, information about one or more metrics (e.g., those subject to an SLA requirement) and updating such information as that packet is processed in a service chain. Techniques described herein may be implemented as an extension of the network service header metadata described in RFC <NUM>.

The techniques described herein may provide one or more technical advantages. For instance, by including information about SLA requirements within a network packet, appropriate selections of network service function routes or paths can be more effectively made in light of SLA requirements. Including information about SLA requirements, and dynamically updating such information through the service chain is an easier, more efficient, and more accurate way to help ensure that network service function nodes are properly selected to satisfy SLA requirements. Maintaining such information within the network service header is, compared to prior techniques for helping to ensure compliance with SLAs, easier, more efficient, and more accurate. Further, including dynamically-updated SLA information within each packet also helps ensure that up-to-date information about progress in satisfying SLA requirements for a given packet is available.

In some examples, this disclosure describes operations performed by a network services complex, compute node, or other system in accordance with one or more aspects of this disclosure. In one specific example, this disclosure describes a method according to independent claim <NUM>.

In another example, this disclosure describes a service complex according to independent claim <NUM>.

In another example, this disclosure describes a computer-readable storage medium comprising instructions that, when executed, configure processing circuitry of a computing system to perform any of the method claims.

<FIG> illustrates an example network system for processing a packet in a service chain, in accordance with one or more aspects of the present disclosure. The example network system of <FIG> includes a service provider network <NUM> that operates as a private network to provide packet-based network services to computing devices 116A to 116N (collectively, "computing devices <NUM>," and representing any number of computing devices). That is, service provider network <NUM> may provide authentication and establishment of network access for computing devices <NUM> such that each of computing devices <NUM> may begin exchanging data packets with public network <NUM>, 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> that provides connectivity to public network <NUM> via service provider core network <NUM> and gateway <NUM>. Gateway <NUM> may apply various network service functions through services complex <NUM> applying functions pursuant to one or more service chains <NUM>. Service provider core network <NUM> (hereinafter "core network <NUM>"), gateway <NUM>, services complex <NUM>, and/or public network <NUM> may provide packet-based services that are available for request and use by computing devices <NUM>. As examples, core network <NUM>, gateway <NUM>, services complex <NUM>, and/or public network <NUM> may provide, for example, bulk data delivery, voice over Internet protocol (VoIP), 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.

Computing devices <NUM> connect to gateway <NUM> via access network <NUM> to receive connectivity to services for applications executing on or hosted by computing devices <NUM>. Each of computing devices <NUM> may be, for example, any appropriate mobile or non-mobile computing device, typically operated by a user. Each of computing devices <NUM> may run a variety of software applications, such as productivity or office support software, web browsing software, software to support voice calls, video games, videoconferencing, and email, among others. Computing devices <NUM> connect to access network <NUM> via access links <NUM> that comprise wired and/or wireless communication links. The term "communication link," as used herein, may comprise any form of transport medium, wired or wireless, and can include intermediate nodes such as network devices.

A network service provider may operate, or in some cases lease, elements of access network <NUM> to provide packet transport between computing devices <NUM> and gateway <NUM>. Access network <NUM> represents a network that aggregates data traffic from one or more user devices (e.g., computing devices <NUM>) for transport to/from 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 computing 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 or mobile access networks.

Core network <NUM> offers packet-based connectivity to computing devices <NUM> attached to access network <NUM> for accessing public network <NUM>. Core network <NUM> may represent a public 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. Public network <NUM> may include a data center.

A network service provider that administers at least parts of service provider network <NUM> typically offers services to computing devices <NUM>, such as, 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 computing devices <NUM> that attach to multiple different access networks <NUM> having varying architectures.

In general, any one or more of computing devices <NUM> may request authorization and data services by sending a session request to gateway <NUM>. In turn, gateway <NUM> typically authenticates such computing devices <NUM>. Once authenticated, each such computing device <NUM> may send subscriber data traffic toward 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. Flow <NUM> illustrated in <FIG> represents one or more upstream packet flows from any one or more computing devices <NUM> and directed to public network <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.

As described herein, service provider network includes services complex <NUM> having a cluster of service nodes 110A to 110N ("service nodes <NUM>," and representing any number of service nodes) that provide an execution environment for the network services. That is, each of service nodes <NUM> apply one or more services. As examples, service nodes <NUM> may apply firewall and security services, carrier grade network address translation (CG-NAT), media optimization (voice/video), 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. Each of service nodes <NUM> in this way represents a service instance.

Although illustrated as part of a services complex <NUM>, which may represent a data center, service nodes <NUM> may, for instance, be coupled by one or more switches or virtual switches of core network <NUM>. In one example, each of service nodes <NUM> may run as a virtual machine in virtual compute environment. Moreover, the compute environment may comprise a scalable cluster of general computing devices or servers. As another example, service nodes <NUM> comprise a combination of general purpose computing devices and special purpose appliances. As virtualized, individual network services provided by service nodes <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. Although described and illustrated to suggest that services complex <NUM> may be housed in a single data center, services complex <NUM> may span multiple data centers and/or geographic locations.

As shown in <FIG>, gateway <NUM> steers individual packet flows <NUM> through defined sets of services provided by service nodes <NUM>. That is, each subscriber packet flow may be forwarded through a particular ordered combination of services provided by service nodes <NUM>, each ordered set being referred to herein as a "service chain. " In the example of <FIG>, one or more flows <NUM> are directed along a first service chain 128A and, therefore, receive services applied by service nodes 110A, 110B and 110N, in that order. Similarly, one or more flows <NUM> are directed along a second service chain 128B and, therefore, receive services applied by service nodes 110C, 110B and 110N.

In this way, subscriber flows <NUM> may be processed by service nodes <NUM> as the packets flow between access network <NUM> and public network <NUM> according to service chains configured by the service provider. In the illustrated example, service chain 128A identifies the ordered set of service nodes 110A, 110B, and 110N according to the listed ordering. Service chain 128B identifies the ordered set of service nodes 110C, 110B, and 110N. Accordingly, packet flows <NUM> processed according to service chain 128A follow a service path that traverses service nodes 110A, 110B, and finally node 110N as the terminal node for service chain 128A. A particular service node <NUM> may support multiple service chains. In this example, service node 110B supports service chains 128A, 128B.

Once processed at a terminal node of the service chain, i.e., the last service node <NUM> to apply services to packets flowing along a particular service path, the terminal node may direct the traffic back to gateway <NUM> for further processing and/or forwarding to public network <NUM>. For example, traffic engineered service paths may start and terminate with gateway <NUM>.

In <FIG>, software-defined networking controller <NUM> ("SDN controller <NUM>") provides a high-level controller for configuring and managing routing and switching infrastructure of service provider network <NUM> (e.g., gateway <NUM>, core network <NUM> and service nodes <NUM>). In some instances, SDN controller <NUM> manages deployment of virtual machines within the operating environment of services complex <NUM>. For example, SDN controller <NUM> may interact with gateway <NUM> to specify service chain 128A, 128B information. For example, the service chain information provided by SDN controller <NUM> may specify any combination and ordering of value-added services provided by service nodes <NUM>, traffic engineering information (e.g., labels or next hops) for tunneling or otherwise transporting (e.g., MPLS or IP tunnels) packet flows along service paths, rate limits, Type Of Service (TOS) markings or packet classifiers that specify criteria for matching packet flows to a particular service chain 128A, 128B.

In accordance with one or more aspects of the present disclosure, SDN controller <NUM> may configure one or more of access network <NUM>, core network <NUM>, and/or gateway <NUM> to implement one or more policies for packets within service provider network <NUM>. For instance, with reference to <FIG>, policy control server <NUM> receives input from an administrator describing policies that are to be carried out on packets and/or packets associated with various applications executing on computing devices <NUM>. Such policies may describe or be used to derive service chain operations that are to be performed on certain packets traversing service provider network <NUM>. Policy control server <NUM> configures, or causes SDN controller <NUM> to configure, access networks <NUM>, core network <NUM>, gateway <NUM>, and/or services complex <NUM> to implement the policies consistent with administrator input.

Service provider network <NUM> may receive a packet that is to be processed in a service chain subject to a constraint or a service chain performance constraint such as a timing or other requirement mandated by a service level agreement requiring service chain processing within a certain timeframe. For instance, in an example that can be described with reference to <FIG>, access network <NUM> receives packet <NUM> from a device, such as computing device 116A. Access network <NUM> communicates packet <NUM> to core network <NUM>, and core network <NUM> communicates packet <NUM> to gateway <NUM>. Gateway <NUM> determines, based on the configuration and/or policies established by policy control server <NUM> and/or SDN controller <NUM>, that packet <NUM> is associated with an application that requires specific functions of a service chain be performed on packet <NUM>. Gateway <NUM> determines that the service chain for packet <NUM> requires performance of three service functions, and further, that the performance of the three service functions is subject to a service chain performance constraint, or a service level agreement (SLA), requiring that the service chain be completed within an overall round-trip time (RTT) of <NUM> milliseconds.

Service provider network <NUM> may select an appropriate service node <NUM> to perform the first function in the service chain. For instance, still referring to the example being described with reference to <FIG>, gateway <NUM> determines which of service nodes <NUM> should perform the first function in the service chain on packet <NUM>. To make the determination, gateway <NUM> considers which of service nodes <NUM> are capable of performing the required service function. Gateway <NUM> further considers which of service nodes <NUM> are capable of performing the required service function within the required round-trip time of <NUM> milliseconds. To determine which of service nodes <NUM> are capable of performing the required service function within the required time, gateway <NUM> consults available information about expected round-trip times associated with each of service nodes <NUM>. In the example being described, gateway <NUM> determines that the service node 110A is capable of performing the first function in the service chain, and that the round-trip time service node 110A is expected to consume in performing the function is <NUM> milliseconds. In some examples, the expected time required to perform the service function may be specified as a round-trip time or other metric specifying the latency associated with service node 110A performing the required service function.

Service provider network <NUM> includes information about timing requirements within packet <NUM> and causes service node 110A to perform the first network service function. For instance, in the example being described with reference to <FIG>, gateway <NUM> updates information in the network services header of packet <NUM> to reflect the timing and/or performance constraint (e.g., SLA) requirements associated with service chain processing for packet <NUM>. In some examples, gateway <NUM> includes information within packet <NUM> indicating that after service node 110A performs the first network function, <NUM> milliseconds will be remaining on RTT SLA (i.e., <NUM> milliseconds is calculated by subtracting the <NUM> milliseconds expected to be consumed by service node 110A from the original <NUM> milliseconds SLA requirement). Further, in some examples, gateway <NUM> may store alternative or additional information about the RTT SLA in the network services header for packet <NUM>, such as the original RTT SLA requirement (i.e., <NUM> milliseconds) or information about other metrics specified by policy or SLA requirement. Gateway <NUM> outputs packet <NUM> to service node 110A. Service node 110A performs the network service function on packet <NUM>.

Service node 110A selects an appropriate service node <NUM> to perform the second function in the service chain. For instance, again referring to the example being described with reference to <FIG>, service node 110A determines an appropriate service node <NUM> to perform the next (i.e., second) service function in the service chain. To make the determination, service node 110A considers which of service nodes <NUM> are capable of performing the second service function, and also considers which of service nodes <NUM> are capable of performing the required service function within the amount of time remaining in the required round-trip time SLA. To determine how much time remains in the round-trip time SLA, service node 110A consults the information that gateway <NUM> previously stored in the network services header of packet <NUM>, as described above. Service node 110A determines, based on information stored within the network services header for packet <NUM>, that <NUM> milliseconds remains in the RTT SLA. To determine which of service nodes <NUM> are capable of performing the required service function within the remaining time, service node 110A consults information about expected round-trip times associated with each of service nodes <NUM>. In some examples, service node 110A maintains a table of information indicating expected round-trip times for each of service nodes <NUM> for various network functions. Service node 110A may maintain such a table using information based on historical or observed latencies (e.g., round-trip times) or based on probing procedures used to determine the latency between two nodes. In the example being described, service node 110A chooses service node 110B to perform the next network function in the service chain. Service node 110A further determines that in performing the next network function, service node 110B is expected to consume <NUM> milliseconds.

Service node 110A includes, within packet <NUM>, information about the amount of time remaining in the RTT SLA, and causes service node 110B to perform the second service function. For instance, referring still to <FIG>, service node 110A determines that after service node 110B performs the second network function, <NUM> milliseconds are expected to remain from the original SLA requirement of <NUM> milliseconds (after subtracting the <NUM> milliseconds expected to be consumed by service node 110B from the <NUM> milliseconds remaining after service node 110A performs the first network function). Service node 110A forwards packet <NUM> to service node 110B. Service node 110B performs the network service function on packet <NUM>, completing the second of the three functions in the service chain.

Service node 110B selects an appropriate service node <NUM> to perform the third and final service function in the service chain. For instance, again with reference to the example being described in connection with <FIG>, service node 110B determines which of service nodes <NUM> is to perform the third service function on packet <NUM>. Service node 110B makes this determination based on the service function to be performed, expected RTT values associated with each of service nodes <NUM>, and the remaining SLA RTT time of <NUM> milliseconds specified by the network services header for packet <NUM>. In the example being described, service node 110B determines, by consulting a table of RTT times associated with each of service nodes <NUM>, that service node 110C is expected to consume <NUM> milliseconds of RTT (consisting of both the link latency and the service latency). Service node 110B further determines that service node 110B satisfies other requirements (e.g., local policy) for selecting a service node for performing the third network function. Accordingly, in the example being described, service node 110B selects service node 110C to perform the third network services function.

Service node 110B updates the network services header of packet <NUM> to indicate that after processing by service node 110C, <NUM> milliseconds is expected to be remaining in the original RTT SLA requirement of <NUM> milliseconds. Service node 110B forwards the packet <NUM> (with the updated RTT SLA information included within the network services header) to service node 110C. Service node 110C performs the third network function. Service node 110C determines that service node 110C is the terminal node, and that the service chain is complete. Service node 110C forwards packet <NUM> back to gateway <NUM>. Gateway <NUM> forwards packet <NUM> to public network <NUM>.

The techniques described herein may provide one or more technical advantages. Including information about SLA requirements within a network packet, for example, helps ensure that appropriate selections of network service function routes or paths can be more effectively made in light of SLA requirements. Including information about SLA requirements, and dynamically updating such information through the service chain is an easier, more efficient, and more accurate way to help ensure that network service function nodes are properly selected to satisfy SLA requirements. Maintaining such information within the network service header is, compared to prior techniques for helping to ensure compliance with SLAs, easier, more efficient, and more accurate. Further, including dynamically-updated SLA information within each packet also helps ensure that up-to-date information about progress in satisfying SLA requirements for a given packet is available.

<FIG> is a conceptual diagram illustrating processing of an example network packet in a service chain between an example access network and an example public network, in accordance with one or more aspects of the present disclosure. The example of <FIG> illustrates packet <NUM> originating at access network <NUM> (or from a device connected to access network <NUM>), and being processed by services complex <NUM> before being output to public network <NUM>. Packet <NUM> is processed pursuant to a service chain implemented by services complex <NUM>. As illustrated in <FIG>, services complex <NUM> includes service nodes 210A through 210F ("service nodes <NUM>"), each of which are capable of performing one or more service functions within a service chain. Table <NUM> illustrates an example RTT values that may, for various hops in a service chain as described herein, be included within a network services header associated with packet <NUM>.

In general, systems, devices, packets or data items, and/or components illustrated in Figures herein (e.g., packet <NUM>, access network <NUM>, public network <NUM> in <FIG>) may correspond to like-numbered systems, devices, packets or data items, and/or components illustrated elsewhere herein (e.g., packet <NUM>, access network <NUM>, public network <NUM> in <FIG>). Such like-numbered systems, devices, packets or data items, and/or components may be described in a manner consistent with the description provided in connection with such other illustrations. In some examples, however, such systems, devices, packets or data items, and/or components may involve alternative implementations with more, fewer, and/or different capabilities in different Figures. Further, one or more systems, devices, packets or data items, and/or components may represent and/or be described as an example or alternative implementation of systems, devices, packets or data items, and/or components illustrated in another figure, even if such systems, devices, packets or data items, and/or components do not have identical reference numerals. For instance, one or more of service nodes <NUM> in <FIG> may correspond to one or more of service nodes <NUM> of <FIG>, and each of service nodes <NUM> may represent and/or be described as an example or alternative implementation of one of one or more of service nodes <NUM> in <FIG> or elsewhere.

In <FIG>, various service nodes <NUM> are illustrated along with connections between various service nodes <NUM> and IP addresses associated with such connections. Further, round-trip time (RTT) values associated with each of the connections between service nodes <NUM> are shown in <FIG>. For instance, the value for the RTT between service node 210A and service node 210B is <NUM> milliseconds, which may be an expected round-trip time, an observed round-trip time, or may be a value determined based on a probing mechanism or procedure or in another way. Similarly, the RTT value between service node 210B and service node 210E is <NUM> milliseconds, which again may be an expected round-trip time, or may be a value determined based on a probing procedure or based on other information. Where a probing procedure is used, information sufficient to periodically or occasionally update the RTT values between nodes may be collected and analyzed.

In the example of <FIG>, each of service nodes <NUM> may maintain its own set of information about RTT values associated with its adjacent nodes. Each of service nodes <NUM> may use such information to select a next hop in a service chain. By using information about RTT values for adjacent nodes, each of service nodes <NUM> may help ensure that a service chain performance constraint, such as an RTT SLA associated with a given packet, is met or satisfied. Accordingly, since each of service nodes <NUM> may select one of service nodes <NUM> to perform any subsequent service functions, the service path for a particular packet may be considered dynamic, and might not be known prior to the completion of the service chain.

In accordance with one or more aspects of the present disclosure, service node 210A may determine a round-trip time service chain performance constraint or SLA that applies to packet <NUM>. For instance, in <FIG>, access network <NUM> receives packet <NUM> and outputs packet <NUM> to service node 210A. Service node 210A evaluates packet <NUM> and identifies an application associated with packet <NUM>. Service node 210A further identifies one or more policies to be applied to packets for the identified application and/or one or more policies that may otherwise apply to packet <NUM>. Based on this policy information, or based on other information, service node 210A determines the maximum duration of the total round-trip time associated with an SLA that applies to packet <NUM>. In one example, service node 210A determines that the SLA indicates that no longer than <NUM> milliseconds should be consumed by the service chain (see table <NUM>).

Service node 210A may identify one or more nodes capable of performing a service function while meeting the service chain performance constraint (i.e., the RTT SLA). For instance, in an example that can be described with reference to <FIG>, identifies a service function that should be performed on packet <NUM>. Service node 210A identifies service nodes <NUM> capable of performing the required function. Service node 210A also evaluates the information about the maximum duration of the total round-trip time associated with an SLA that applies to packet <NUM>, and identifies service nodes <NUM> that are capable of performing the required function within the RTT SLA (i.e., <NUM> milliseconds). In some examples, multiple adjacent service nodes <NUM> may be capable of performing the relevant service function within the required RTT (e.g., in <FIG> service node 210B, service node 210C, service node 210F may each be capable of performing the required function within <NUM> milliseconds).

Service node 210A may select a node to perform the required service function. For instance, in the example being described with reference to <FIG>, service node 210A may choose from among several qualifying nodes based on one or more criteria. In one example, service node 210A select the node having the lowest RTT value. In other examples, however, service node 210A may choose among the multiple qualifying service nodes <NUM> based on other considerations and/or local policy. Accordingly, service node 210A might not necessarily choose the node having the lowest RTT value, and instead, may use the RTT values of adjacent nodes to identify a group of nodes to consider as a next hop. From that group of nodes to consider, local policy or other considerations may be applied to choose one node from among the group of nodes. In the example being described, service node 210A chooses service node 210B, which is expected to consume <NUM> milliseconds of round-trip time.

Service node 210A may update packet <NUM> to include RTT SLA information. For instance, in the example being described with reference to <FIG>, once service node 210A selects service node 210B, service node 210A adds information to packet <NUM> about the SLA requirements for the total round-trip time for the service chain. In some examples, service node 210A adds the information to the network services header of packet <NUM>, and such information may reflect the amount of time expected to remain on the RTT SLA after processing by service node 210B. In such an example, service node 210A includes information indicating that <NUM> milliseconds are expected to remain from the original RTT SLA requirement after taking into account the RTT expected to be consumed by service node 210B when performing the appropriate service function. Service node 210A outputs packet <NUM> to service node 210B over path 201A. When traveling over path 201A, packet <NUM> includes information indicating <NUM> milliseconds remain in the SLA (see table <NUM>).

Service node 210B may use RTT information when selecting a node for the next service function in the service chain. For instance, in the example being described, service node 210B receives packet <NUM> from service node 210A and performs the appropriate service function. Service node 210B chooses one of service nodes <NUM> to perform the next service function in the service chain. Service node 210B makes such a determination by evaluating the information about the remaining RTT SLA stored in the network service header of packet <NUM>. Service node 210B limits its choice of available service nodes <NUM> to those service nodes <NUM> that are capable of performing the function within the remaining RTT SLA time (<NUM> milliseconds). If more than one of service nodes <NUM> can perform the required function within the required time, service node 210B chooses among qualifying service nodes <NUM> based on other considerations or local policy, as described above. In the example being described, service node 210B chooses service node 210D, which is one of service nodes <NUM> capable of performing the next function in the service chain within the remaining RTT, as indicated by the information stored within the network services header of packet <NUM>.

Service node 210B may update the RTT SLA information in packet <NUM>. For instance, continuing with the example and with reference to <FIG>, service node 210B determines that service node 210D is expected to consume <NUM> milliseconds of the remaining RTT SLA. Service node 210B therefore updates the network services header of packet <NUM> to reflect that <NUM> milliseconds remain in the RTT SLA. Service node 210B outputs packet <NUM> to service node 210D (path 201B). When traveling over path 201B, packet <NUM> thus includes information indicating that <NUM> milliseconds remain in the RTT SLA (see table <NUM>).

Service node 210D may use the updated RTT information to select the next node in the service chain. For instance, still continuing with the example being described with reference to <FIG>, service node 210D receives packet <NUM> from service node 210B and performs the appropriate service function. Service node 210D chooses one of service nodes <NUM> to perform the next service function, and as with earlier service nodes <NUM>, service node 210D makes a choice by limiting its selection to those service nodes <NUM> capable of performing the appropriate service function within the remaining RTT SLA. In the example being described, service node 210D chooses service node 210F, which is expected to consume <NUM> milliseconds. Service node 210D updates the network services header of packet <NUM> to reflect that <NUM> milliseconds remain in the RTT SLA after the expected time consumed by service node 210F in performing the service function. When traveling over path 201C, therefore, packet <NUM> includes information indicating that <NUM> milliseconds remain in the RTT SLA (see table <NUM>). Service node 210D outputs packet <NUM> to service node 210F.

Service node 210F may output packet <NUM> over public network <NUM>. For instance, in the example of <FIG>, service node 210F receives packet <NUM> from service node 210D. Service node 210F performs the appropriate service function. Service node 210F determines that it is the terminal node. Service node 210F outputs packet <NUM> to public network <NUM>.

<FIG> are conceptual diagrams illustrating example network service headers (NSH) that may be used to realize a service function chain, in accordance with one or more aspects of the present disclosure. Header 301A of <FIG> and header 301B of <FIG> illustrate fields of a network service header consistent with RFC <NUM> and/or consistent with an extension to RFC <NUM>. As shown in <FIG>, the first <NUM> bits of both header 301A and header 301B are the same, and include information about the version of the NSH ("Ver"), an OAM ("O") bit, a TTL field (indicating the maximum service function forwarder hops for a service function path), a length field, an MD Type field, and a Next Protocol field, as described in RFC <NUM>. Header 301A and header 301B also include a service path identifier (uniquely identifying a service function path) and a service index (providing a location within the service function path).

The header of <FIG> includes, starting after the first <NUM> bits, field 303A. Field 303A includes optional fixed or variable length context headers, also described in RFC <NUM>.

In some examples, field 303B of <FIG>, which may span some or all of the corresponding portion of field 303A of <FIG>, may be used for storing next hop SLA information. Specifically, field 303B may be used to carry, with the network packet, information about RTT SLA metrics for that packet. In some examples, field 303B may include data about the remaining RTT SLA associated with the network packet. Field 303B may be updated by one or more nodes (e.g., service nodes <NUM>), in the manner described herein, as the network packet is processed by a service chain. In other examples, information stored within field 303B may include information about not just round-trip times, but may also or alternatively include information about other metrics that may also be subject to SLA requirements. Such metrics may include jitter, or information about permissible packet loss (e.g., based on an SLA specifying a maximum percentage of packet loss).

<FIG> is a block diagram illustrating an example host device that may provide an operating environment for one or more service nodes, in accordance with one or more aspects of the present disclosure. In the example of <FIG>, host device <NUM> includes underlying physical compute hardware that includes power source <NUM>, one or more processors <NUM>, and one or more network adapters <NUM>. Network adapters <NUM> may receive packets being processed in a service chain, such as any of the other service chains described herein (e.g., service chains <NUM> of <FIG>). One or more of the devices, modules, storage areas, or other components of host device <NUM> may be interconnected to enable inter-component communications (physically, communicatively, and/or operatively). In some examples, such connectivity may be provided by through communication channels (e.g., communication channels <NUM>), a system bus, a network connection, an inter-process communication data structure, or any other method for communicating data.

Hypervisor <NUM> may serve as a virtual machine monitor that instantiates, creates, and/or executes virtual machines 411A through 411N ("virtual machines <NUM>," representing any number of virtual machines) on an underlying host hardware device. In some examples, each of service nodes service nodes 410A, 410B, through 410N ("service nodes <NUM>," and representing any number of service nodes) may be implemented through one or more virtual machines <NUM>. In some contexts, hypervisor <NUM> may be referred to as a virtual machine manager (VMM). Hypervisor <NUM> may execute within the execution environment provided by a storage device and one or more processors <NUM> within host device <NUM> or on top of an operating system kernel (e.g., kernel <NUM>). In some examples, hypervisor <NUM> is an operating system-level component that executes on a hardware platform (e.g., host device <NUM>) to provide a virtualized operating environment and orchestration controller for virtual machines, and/or other types of virtual computing instances. In other examples, hypervisor <NUM> may be a software and/or firmware layer that provides a lightweight kernel and operates to provide a virtualized operating environment and orchestration controller for virtual machines, and/or other types of virtual computing instances. Hypervisor <NUM> may incorporate the functionality of kernel <NUM> (e.g., as a "type <NUM> hypervisor"), or may execute on a kernel (e.g., as a "type <NUM> hypervisor").

In the example illustrated in <FIG>, service node 410A includes virtual machine 411A, as well as next hop selection table 413A, SLA module 414A, and one or more service function modules 415A. Similarly, service node 410B includes virtual machine 411B, next hop selection table 413B, SLA module 414B, and one or more service function modules 415B. And in general, service node 410N includes virtual machine 411N, next hop selection table 413N, SLA module 414N, and one or more service function modules 415N.

Next hop selection table 413A, for example, may represent a table of information that virtual machine 411A uses to select a next hop or a node to perform a function in a service chain. Next hop selection table 413A may include service path index column <NUM> and service index column <NUM> identifying a service path index and service index associated with various service paths. Possible next hops for a given service path index may each be identified by an address (next hop address column <NUM>) and metric information enabling implementation of a local or other policy for selecting from among possible next hops (metric column <NUM>).

In addition, for each respective service node <NUM>, a next hop selection table <NUM> may include a column specifying additional metric information that can be used to help ensure that one or more SLA requirements are met. Next hop selection table 413A for service node 410A, for example, includes SLA metric column <NUM>, which in the example shown in <FIG> may contain information about round-trip times associated with each possible next hop for a given service chain. In other examples, SLA metric column <NUM> may include other information, such as information relating to SLAs pertaining to jitter or packet loss. Each of virtual machines <NUM> or service nodes <NUM> may maintain include its own next hop selection table <NUM> that reflects SLA information (e.g., RTT information) associated with each of the adjacent nodes associated with a respective service node <NUM>. Next hop selection tables <NUM> may be maintained by respective SLA modules <NUM>, may be included within and/or stored within respective virtual machines <NUM>, and may be dynamically updated by virtual machine <NUM> or by SLA module <NUM> as RTT or other information changes. Such information may change as, for example, loads on a network change.

Each of SLA modules <NUM> may perform functions relating to selection of a service node to perform a function in a service chain. For instance, SLA module 414A of service node 410A may operate as an application or service executing on virtual machine 411A. SLA module 414A may evaluate information in next hop selection table 413A and determine, based on a given service path index and information in SLA metric column <NUM> associated with that service path index, which of the next hop addresses to choose for performing a function in a service chain. In some examples, each of SLA modules <NUM> may limit its selection of a service path (i.e., a next hop) to those RTT values that enable any applicable service chain performance constraints on RTT times (i.e., an RTT SLA) to be satisfied. If multiple next hops are available to perform a given function while also satisfying an applicable RTT SLA, a given SLA module <NUM> may select a next hop based on other information, such as a local network policy, or information in metric column <NUM> of the appropriate next hop selection table <NUM>.

Each of service nodes <NUM> include one or more of service function modules <NUM>, which may operate as applications or services executing on a respective virtual machine <NUM>, and may perform each of the services within a service chain. In some examples, one or more of service function modules <NUM> may apply, to given packet (e.g., packet <NUM>) or network traffic, firewall and security services, carrier grade network address translation (CG-NAT), media optimization (voice/video), IPSec/VPN services, deep packet inspection (DPI), HTTP filtering, counting, accounting, charging, load balancing of packet flows, and/or other types of services.

Although service nodes <NUM> illustrated in <FIG> are shown executing on a single host device <NUM>, in other examples, one or more of service nodes <NUM> may execute on multiple host devices distributed across one or more data centers and/or distributed across one or more geographical areas. Further, although each of service nodes <NUM> are illustrated as being implemented by a single virtual machine <NUM>, in other examples, a single virtual machine <NUM> may implement multiple service nodes <NUM>, or a single service node <NUM> may be implemented by multiple virtual machines <NUM>. Similarly, although each of service nodes <NUM> are illustrated as being implemented in a virtual machine environment, one or more of service nodes <NUM> may be implemented pursuant to other virtualization arrangements (e.g., through a containerized environment) or through one or more bare metal servers.

In accordance with one or more aspects of the present disclosure, host device <NUM> may receive packet <NUM> for processing in a service chain. For instance, in an example that can be described with reference to <FIG>, network adapter <NUM> detects input and outputs to hypervisor <NUM> an indication of input. Hypervisor <NUM> determines that the input corresponds to packet <NUM> being received pursuant to service chain <NUM>. Hypervisor <NUM> further determines that packet <NUM> is destined for service node 410A. Hypervisor <NUM> outputs packet <NUM> to virtual machine 411A associated with service node 410A.

One or more of service nodes <NUM> may perform a function in a service chain. For instance, continuing with the example being described and with reference to <FIG>, hypervisor <NUM> identifies a service function that is to be performed on packet <NUM> pursuant to service chain <NUM>. Virtual machine 411A of service node 410A causes one or more of service function modules 415A to perform the identified service function.

Service node 410A may select a service node to perform an additional service function. For instance, again referring to the example being described and with reference to <FIG>, virtual machine 411A determines that service chain <NUM> requires one more additional services to be performed on packet <NUM>. Virtual machine 411A outputs information about the required additional services to SLA module 414A. SLA module 414A determines that service chain <NUM> is associated with service path index <NUM> and service index <NUM> (i.e., the first row of next hop selection table 413A). SLA module 414A evaluates information about SLA requirements that may be stored in a network services header of packet <NUM>, and determines, in one example, that only <NUM> milliseconds remain in the RTT SLA for packet <NUM>. SLA module 414A identifies address <NUM>. <NUM> as an appropriate next hop, since the service node at that address is expected to complete the service function in a RTT of <NUM> milliseconds (see next hop selection table 413A). The service node associated with address <NUM>. <NUM>, on the other hand, is expected to require <NUM> milliseconds RTT, and that exceeds the RTT SLA for packet <NUM>, as indicated by the network services header of packet <NUM>. Accordingly, SLA module 414A removes <NUM>. <NUM> from consideration when selecting a service node to perform the next function in service chain <NUM>. SLA module 414A selects the service node at <NUM>. <NUM> for performing the next service function.

Host device <NUM> may perform the next function in service chain <NUM>. For instance, once again referring to the example being described and with reference to <FIG>, SLA module 414A of service node 410A updates packet <NUM> (e.g., the network services header of packet <NUM>) to reflect that after the next service function is performed, <NUM> milliseconds are expected to remain from the RTT SLA for packet <NUM>. (This <NUM> millisecond value is calculated by subtracting <NUM> milliseconds of RTT expected to be consumed by the next service function from the <NUM> milliseconds remaining in the RTT SLA as indicated by the network services header of packet <NUM>. Virtual machine 411A outputs to hypervisor <NUM> information about the appropriate next hop. Hypervisor <NUM> determines that the address <NUM>. <NUM> corresponds to service node 410B being hosted by host device <NUM>. Hypervisor <NUM> outputs packet <NUM> to virtual machine 411B of service node 410B. Virtual machine 411B causes one or more of service function modules 415B to perform the appropriate service function within the time remaining in the RTT SLA for packet <NUM>.

In the example being described in connection with <FIG>, packet <NUM> is processed by consecutive service nodes within the same host device <NUM>. In other examples, however, different service functions may be performed on packet <NUM> by different host devices <NUM>, in different data centers, and/or in different geographical regions.

Modules illustrated in <FIG> (e.g., virtual machines 411A through 411N and/or SLA modules 414A through 414N) and/or illustrated or described elsewhere in this disclosure may perform operations described using software, hardware, firmware, or a mixture of hardware, software, and firmware residing in and/or executing at one or more computing devices. For example, a computing device may execute one or more of such modules with multiple processors or multiple devices. A computing device may execute one or more of such modules as a virtual machine executing on underlying hardware. One or more of such modules may execute as one or more services of an operating system or computing platform. One or more of such modules may execute as one or more executable programs at an application layer of a computing platform. In other examples, functionality provided by a module could be implemented by a dedicated hardware device.

Although certain modules, data stores, components, programs, executables, data items, functional units, and/or other items included within one or more storage devices may be illustrated separately, one or more of such items could be combined and operate as a single module, component, program, executable, data item, or functional unit. For example, one or more modules or data stores may be combined or partially combined so that they operate or provide functionality as a single module. Further, one or more modules may interact with and/or operate in conjunction with one another so that, for example, one module acts as a service or an extension of another module. Also, each module, data store, component, program, executable, data item, functional unit, or other item illustrated within a storage device may include multiple components, sub-components, modules, sub-modules, data stores, and/or other components or modules or data stores not illustrated.

Further, each module, data store, component, program, executable, data item, functional unit, or other item illustrated within a storage device may be implemented in various ways. For example, each module, data store, component, program, executable, data item, functional unit, or other item illustrated within a storage device may be implemented as a downloadable or pre-installed application or "app. " In other examples, each module, data store, component, program, executable, data item, functional unit, or other item illustrated within a storage device may be implemented as part of an operating system executed on a computing device.

<FIG> is a flow diagram illustrating operations performed by an example service node in accordance with one or more aspects of the present disclosure. <FIG> is described herein within the context of services complex <NUM> and one or more of service nodes <NUM> of <FIG>. In other examples, operations described in <FIG> may be performed by one or more other components, modules, systems, or devices. Further, in other examples, operations described in connection with <FIG> may be merged, performed in a difference sequence, omitted, or may encompass additional operations not specifically illustrated or described.

In the process illustrated in <FIG>, and in accordance with one or more aspects of the present disclosure, services complex <NUM> may receive a packet (<NUM>). For instance, in some examples, access network <NUM> receives packet <NUM>. Access network <NUM> outputs packet <NUM> to service node 210A within services complex <NUM>.

Services complex <NUM> may identify service chain constraints (<NUM>). For instance, in some examples, service node 210A evaluates packet <NUM> and identifies a service chain that is to be applied to packet <NUM>. Service node 210A determines, based on the service chain to be applied to packet <NUM>, that a performance constraint is applicable to packet <NUM> and is to be satisfied when processing packet <NUM>. Such a constraint may be a service level agreement that mandates that packet <NUM> be processed by the service chain in no more than specified period of time, or a specified round-trip time (RTT), such as <NUM> milliseconds.

Services complex <NUM> may identify a service node to perform a service function (<NUM>). For instance, in some examples, service node 210A identifies which of service nodes <NUM> are capable of performing the first service function. From the service nodes <NUM> capable of performing the first service function, service node 210A identifies which such service nodes <NUM> are capable of performing the first service function within the time mandated by the service level agreement. In the example being described, service node 210A determines that service node 210B is both capable of performing the first service function, and can complete the service chain operation within the <NUM> milliseconds mandated by the service level agreement.

Services complex <NUM> may determine an expected impact that performing the service function will have (<NUM>). For instance, in some examples, service node 210A determines, based on information maintained by service node 210A (e.g., SLA metric column <NUM> of next hop selection table <NUM> of <FIG>), that service node 210B will consume <NUM> milliseconds in round-trip time to perform the first service function. The <NUM> milliseconds value may include both the round-trip link latency between service node 210A and service node 210B as well as the latency in service node 210B performing the service function. Accordingly, service node 210A determines that service node 210B performing the first service function will impact the maximum RTT mandated by the service level agreement by <NUM> milliseconds. Specifically, service node 210A determines that after service node 210B performs the service function, <NUM> milliseconds will remain to complete the service chain while complying with service level agreement. If the expected time to perform the service function by service node 210B is too long and consumes all of the RTT remaining on the service level agreement, service node 210A may choose a different service node (NO path from <NUM>). Otherwise, service node 210A selects service node 210B to perform the first service function (YES path from <NUM>).

Services complex <NUM> may modify the packet to reflect the expected impact (<NUM>). For instance, in some examples, service node 210A inserts into the network services header of packet <NUM> information indicating that <NUM> milliseconds remain to complete the service chain to comply with the service level agreement. This information can be used by later service nodes to select an appropriate service node to perform service functions further along the chain, after service node 210B performs the first service function.

Services complex <NUM> may enable the service node 210B to perform the service function (<NUM>). For instance, in some examples, service node 210A outputs packet <NUM> to service node 210B. Services complex <NUM> enables service node 210B to perform the first service function.

In some examples, services complex <NUM> may continue to perform the remaining service function in the service chain (<NUM>). For instance, in some examples, service node 210B may, after performing the first service function, choose another one of service nodes <NUM> to perform the next service function in the service chain. In making such a choice, service node 210B may limit its selection to those service nodes <NUM> that are capable of performing the next service function within the time specified in the network services header of packet <NUM> (i.e., now <NUM> milliseconds). Service node 210B may then update the network services header to reflect the amount of time (e.g., RTT) that is expected to be consumed by the next service node <NUM> that performs the next service function. In some examples, updating the network service header to reflect that amount of time may involve subtracting the expected RTT time to perform the next service function from the <NUM> milliseconds currently reflected by packet <NUM>. Thus, service node 210B may update the network services header to reflect that some amount time less than <NUM> milliseconds remains to complete the service chain. Each additional service node <NUM> may perform a similar procedure for each function in the service chain, thereby maintaining information with packet <NUM> that reflects, at each service node <NUM>, how much time remains to complete the service chain.

For processes, apparatuses, and other examples or illustrations described herein, including in any flowcharts or flow diagrams, certain operations, acts, steps, or events included in any of the techniques described herein can be performed in a different sequence, may be added, merged, or left out altogether (e.g., not all described acts or events are necessary for the practice of the techniques). Moreover, in certain examples, operations, acts, steps, or events may be performed concurrently, e.g., through multi-threaded processing, interrupt processing, or multiple processors, rather than sequentially. Further certain operations, acts, steps, or events may be performed automatically even if not specifically identified as being performed automatically. Also, certain operations, acts, steps, or events described as being performed automatically may be alternatively not performed automatically, but rather, such operations, acts, steps, or events may be, in some examples, performed in response to input or another event.

For ease of illustration, only a limited number of devices (e.g., data sources <NUM>, client devices <NUM>, computing systems <NUM>, administrator devices <NUM>, as well as others) are shown within the Figures and/or in other illustrations referenced herein. However, techniques in accordance with one or more aspects of the present disclosure may be performed with many more of such systems, components, devices, modules, and/or other items, and collective references to such systems, components, devices, modules, and/or other items may represent any number of such systems, components, devices, modules, and/or other items.

The Figures included herein each illustrate at least one example implementation of an aspect of this disclosure. The scope of this disclosure is not, however, limited to such implementations. Accordingly, other example or alternative implementations of systems, methods or techniques described herein, beyond those illustrated in the Figures, may be appropriate in other instances. Such implementations may include a subset of the devices and/or components included in the Figures and/or may include additional devices and/or components not shown in the Figures.

The detailed description set forth above is intended as a description of various configurations and is not intended to represent the only configurations in which the concepts described herein may be practiced. The detailed description includes specific details for the purpose of providing a sufficient understanding of the various concepts. However, these concepts may be practiced without these specific details. In some instances, well-known structures and components are shown in block diagram form in the referenced figures in order to avoid obscuring such concepts.

Accordingly, although one or more implementations of various systems, devices, and/or components may be described with reference to specific Figures, such systems, devices, and/or components may be implemented in a number of different ways. For instance, one or more devices illustrated in the Figures herein (e.g., <FIG> and/or <FIG>) as separate devices may alternatively be implemented as a single device; one or more components illustrated as separate components may alternatively be implemented as a single component. Also, in some examples, one or more devices illustrated in the Figures herein as a single device may alternatively be implemented as multiple devices; one or more components illustrated as a single component may alternatively be implemented as multiple components. Each of such multiple devices and/or components may be directly coupled via wired or wireless communication and/or remotely coupled via one or more networks. Also, one or more devices or components that may be illustrated in various Figures herein may alternatively be implemented as part of another device or component not shown in such Figures. In this and other ways, some of the functions described herein may be performed via distributed processing by two or more devices or components.

Further, certain operations, techniques, features, and/or functions may be described herein as being performed by specific components, devices, and/or modules. In other examples, such operations, techniques, features, and/or functions may be performed by different components, devices, or modules. Accordingly, some operations, techniques, features, and/or functions that may be described herein as being attributed to one or more components, devices, or modules may, in other examples, be attributed to other components, devices, and/or modules, even if not specifically described herein in such a manner.

Although specific advantages have been identified in connection with descriptions of some examples, various other examples may include some, none, or all of the enumerated advantages. Other advantages, technical or otherwise, may become apparent to one of ordinary skill in the art from the present disclosure. Further, although specific examples have been disclosed herein, aspects of this disclosure may be implemented using any number of techniques, whether currently known or not, and accordingly, the present disclosure is not limited to the examples specifically described and/or illustrated in this disclosure.

If implemented in software, the functions may be stored, as one or more instructions or code, on and/or transmitted over a computer-readable medium and executed by a hardware-based processing unit. Computer-readable media may include computer-readable storage media, which corresponds to a tangible medium such as data storage media, or communication media including any medium that facilitates transfer of a computer program from one place to another (e.g., pursuant to a communication protocol). In this manner, computer-readable media generally may correspond to (<NUM>) tangible computer-readable storage media, which is non-transitory or (<NUM>) a communication medium such as a signal or carrier wave.

By way of example, and not limitation, such computer-readable storage media can include RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage, or other magnetic storage devices, flash memory, or any other medium that can be used to store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disk and disc, as used, includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk and Blu-ray disc, where disks usually reproduce data magnetically, while discs reproduce data optically with lasers.

Accordingly, the terms "processor" or "processing circuitry" as used herein may each refer to any of the foregoing structure or any other structure suitable for implementation of the techniques described. In addition, in some examples, the functionality described may be provided within dedicated hardware and/or software modules.

The techniques of this disclosure may be implemented in a wide variety of devices or apparatuses, including a wireless handset, a mobile or non-mobile computing device, a wearable or non-wearable computing device, an integrated circuit (IC) or a set of ICs (e.g., a chip set). Rather, as described above, various units may be combined in a hardware unit or provided by a collection of interoperating hardware units, including one or more processors as described above, in conjunction with suitable software and/or firmware.

Claim 1:
A method comprising:
receiving (<NUM>), by a service complex having a plurality of service nodes, a packet associated with a service chain representing a series of services to be performed on the packet by one or more of the plurality of service nodes;
identifying (<NUM>), by the service complex, one or more service chain performance constraints associated with the service chain;
identifying (<NUM>), by the service complex and based on the service chain performance constraints, a service node to perform a service function on the packet; prior to applying the service function to the packet, determining (<NUM>), by the service complex, an expected impact that performance of the service function will have on satisfying the service chain performance constraints; and
modifying (<NUM>), by the service complex, the packet by including information in the packet to reflect the expected impact that performance of the service function will have on satisfying the service chain performance constraints.