Patent Description:
Aspects of the disclosure are related to the field of computing and communication infrastructure technology and, more particularly, to managing packet flows over networks.

Content delivery networks, edge cloud platforms, and other types of infrastructure services send and receive huge volumes of data. The data is typically sent and received between servers and end points over logical connections that are created and torn down dynamically as needed to handle packet flows over the connections. The servers and end points establish the connections with each other, typically in accordance with one or more of a variety of protocols, such as the Transport Control Protocol (TCP).

The connections that are created to handle packet flows traverse outbound paths from the servers to the end points and inbound paths from the end points to the servers. TCP and other transport layer protocols like it provide for reliable connectivity over a given path between a server and an end point. For example, TCP provides for data to be retransmitted from one end to another in the event that an earlier attempt to send the data was not acknowledged. However, such retransmissions may not be effective if the cause of a failure is with the inbound or outbound path over which the data has been sent. That is, no amount of retransmitting will be successful if the path between a server and an end point has failed somewhere along the way.

The border gateway protocol (BGP) is a protocol designed to, among other things, address the problem of path failures. BGP is used to exchange routing and reachability information among routing systems on the Internet, thus allowing such systems to react to a path failure by rerouting packet flows over other paths.

Unfortunately, BGP is error prone due to its reliance on timeouts to detect path failures. Even when BGP detects a path failure, routers are known to continue to send traffic to each other regardless. The end result is that, by the time a packet flow can be rerouted in response to a path failure detected by BGP, a great deal of traffic may have been lost. Such problems may be compounded by retransmission attempts that add traffic to the network, even though an outbound path the traffic would traverse has been compromised.

<CIT> discloses a mechanism for determining a congestion metric for a path in a network. <NPL>" discloses load balancing of multipath internet routing. <CIT> discloses a system for routing packets in a network.

Technology is disclosed herein for rerouting packet flows over outbound paths in response to path failures detected at the connection layer.

Many aspects of the disclosure may be better understood with reference to the following drawings. While several embodiments are described in connection with these drawings, the disclosure is not limited to the embodiments disclosed herein.

Technology disclosed herein relates to solutions for rerouting packet flows over paths outbound from infrastructure services such as content delivery networks, cloud edge platforms, and other computing and communications environments.

A reroute processis employed by a server and in unclaimed embodiments may be employed by any one or more of routers, and other elements in an infrastructure service to monitor the forward progress made on a connection from the infrastructure service to an end point. When a path failure is detected, as determined by a measure of the forward progress, a hash value is generated based on an identifying value of the connection and a failure counter associated with the measure of forward progress. The hash value is then used to select a next outbound path for the connection and the packet flow is rerouted over the selected path accordingly.

To produce the hash value, an input to a hash function is generated from the identifying value and the failure counter. In some implementations, the identifying value is one of a set of identifying values in a tuple associated with the connection such as, but not limited to, a protocol identifier, a source Internet protocol (IP) address, a source port, a target IP address, and a target port. The failure counter may be mixed with the tuple such as by replacing one of the values with the failure counter, adding the failure counter to the tuple, performing an exclusive-or operation on one or more of the values and the failure counter, or the like.

In some cases, the failure counter itself may be encoded in a firewall marker property of a socket on the connection being rerouted. This may be accomplished by, for example, encoding the failure counter in the four upper bits of a firewall marker (fwmark). The value of the firewall marker may be used in some implementations to determine which routing table to use when selecting a route. A zero-value firewall marker may correspond to one routing table, for instance, while a non-zero value may correspond to a different routing table, thereby influencing the selection of the new outbound path.

Detecting the failure of the outbound path occurs when the measure of forward progress made on the connection indicates an absence of any forward progress for an amount of time. This may be accomplished by, for example, monitoring for acknowledgments on the connection from the end point. An absence of forward progress may be declared when no acknowledgments are received for an amount of time, after which the failure counter may be incremented.

The outbound path from the infrastructure service to the end point may traverse two or more networks. The detected failure may thus be caused by one or more of the networks along the outbound path. The next outbound path may traverse at least one network not traversed by the outbound path, allowing the packet flow to avoid the detected failure.

In some implementations, an outbound path may have failed before a connection between an end point and a server can even be established. In such instances, fast rerouting may be invoked when a certain number of attempts to establish a connection have occurred. For instance, a request to establish a connection may be received in a server from an end point, in response to which the server sends a reply message. However, the reply message may not reach the end point if the outbound path is blocked. The server may thus trigger a reroute after a certain number of attempts to communicate the reply message.

A technical effect may thus be appreciated that packet flows may be quickly rerouted from one outbound path to another, thereby mitigating some of the drawbacks of relying upon BGP such as lost packets, excessive retransmissions, and other errors. For example, the speed with which a packet flow may be rerouted using the techniques described herein may be greater than that which is typically accomplished when relying upon BGP. Such speed may be made possible by monitoring the forward progress of a connection (e.g. a transmission control protocol - or TCP - connection) and triggering a reroute to a new outbound path in response to a detected failure as indicated by the measured forward progress.

Another technical effect is the ability to distribute packet flows to one or more other outbound routes so as not to overload any particular outbound route. This is accomplished by incrementing the failure counter associated with a connection and mixing the failure counter with the tuple that is used to produce a hash value. Since the hash value is then used to pick a route, and since hash functions are deterministic, incrementing the failure counter results in different hash values, even if the connection values remain the same. Thus, since different hash values may correspond to different routes in the routing table(s), incrementing the failure counter may result in the selection of different routes (or outbound paths). Such a technique reduces the likelihood of rerouting the packet flows destined for a particular end point to the same outbound path each time a reroute is triggered.

Referring now to the drawings, <FIG> illustrates operational environment <NUM> in an implementation. End points <NUM> and edge service <NUM> establish logical connections with each other, through which content may be requested and sent, of which connections <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> are representative. Edge service transmits the content over one or more outbound paths to a given end point, of which outbound paths <NUM>, <NUM>, and <NUM> are representative.

End points <NUM> are representative of the various computing devices from which requests for content may originate and to which content may be served, such as consumer devices, enterprise devices, and the like. Examples include, but are not limited to, laptop and desktop computers, tablets, mobile phones, wearable devices, entertainment devices, gaming devices, other server computers, Internet of Things (IoT) devices, or any other type of end point device. End points <NUM> communicate with edge service <NUM> over one or more public or private communication networks (e.g. the Internet), combination of networks, or variations thereof.

Edge service <NUM> is representative of a content delivery network, an edge cloud platform, or the like, and is comprised of various physical and/or virtual computing and communication elements suitable for implementing a variety of associated infrastructure services, of which computing system <NUM> in <FIG> is representative. For example, edge service <NUM> may include routers, servers, and other elements that function together to serve content to end points <NUM>. Edge service <NUM> may in some implementations obtain the content from origin servers (not shown) and cache the content on its servers for faster serving to end points. Examples of content that may be served to end points include text, images, video, web pages, objects, applications, or any other type of data.

Connections <NUM> are representative of the transport layer connections that end points <NUM> may make with edge service <NUM> to facilitate the exchange of data. Connections <NUM> may be established in accordance with a variety of communication protocols such as the transmission control protocol (TCP), the stream control transmission protocol (SCTP), quick user datagram Internet connections (QUIC), and other connection-oriented protocols.

Outbound paths <NUM>, <NUM>, and <NUM> are representative of the various paths traffic may take in an outbound direction from edge service <NUM> to end points <NUM>. Traffic sent from end points <NUM> to edge service <NUM> may travel the same or different paths, but in the inbound direction from the perspective of edge service <NUM>. Outbound paths <NUM>, <NUM>, and <NUM> may each traverse one or more networks that connect edge service <NUM> to end points <NUM>, examples of which include (but are not limited to) transit networks, peering networks, backbone networks, Internet service provider (ISP) networks, local ISPs, and any other type of network, combination of networks, or variation thereof.

Edge service <NUM> transmits various packet flows within the context of logical connections, represented by connections <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. The packets of each packet flow traverse a given outbound path selected for the flow when sent by edge service <NUM> to a destination. Thus, a given connection may also be considered to traverse a given outbound path. For exemplary purposes, <FIG> illustrates that connections <NUM> and <NUM> traverse outbound path <NUM>; connections <NUM> and <NUM> traverse outbound path <NUM>; and connections <NUM> and <NUM> traverse outbound path <NUM>. In the inbound direction, the packets may traverse the same or a different path as they took in the outbound direction.

Each connection may be described in terms of a tuple formed by one or more identifying values of the connection. Examples of identifying values of a connection include, but are not limited to its source address, source port, target address, target port, and protocol. Tuple <NUM> is given as an example of identifying values for connection <NUM>. Edge service <NUM> may utilize said tuples to calculate hash values, which may then be used to navigate one or more routing tables that define which route (or outbound path) to use for a given transmission. As the routes may fail or otherwise underperform from time to time, edge service <NUM> employs a reroute process <NUM> for rerouting connections in response to failures or other performance issues.

Referring to <FIG>, reroute process <NUM> according to the invention may be implemented in program instructions in the context of any of the software applications, modules, components, or other such programming elements deployed in the various elements of edge service <NUM>, such as routers and servers. The program instructions direct the underlying physical or virtual computing system or systems to operate as follows, referring parenthetically to the steps in <FIG> in the context of operational environment <NUM> in <FIG>.

To begin, edge service <NUM> sends a packet flow over an initial outbound path (step <NUM>). The packet flow may comprise packets that carry the content requested by an end point. The end point (or edge service <NUM>) establishes a connection via which the packets may be transmitted, e.g. a TCP connection or the like.

Next, edge service <NUM> tracks the forward progress of the connection while sending (or attempting to send) packets to the end point (step <NUM>). As packets are sent from edge service <NUM> to the end point, the end point replies with acknowledgement messages (ACKs) in accordance with the connection protocol implemented between the end point and edge service <NUM>. Edge service <NUM> tracks the forward progress of the connection by monitoring for ACKs from the end point, and determines whether the path has failed based on the monitored forward progress of the connection (step <NUM>). Monitoring for ACKs includes determining whether an ACK has been received for a certain amount of time. If no ACK is received during the amount of time, then a failure may be declared. The amount of time may be a global value or a non-global value. In the case of a non-global value, the timeout period may depend on the round-trip time (RTT) of the connection. That is, the timeout period may vary on a per-connection basis, based on the RTT for a given connection.

In an alternative to declaring failures based on the absence of an ACK, a path may be considered to have failed upon a retransmit timeout for a connection occurring. A failure could also be declared in response to a retransmit of a segment occurring after more than a certain amount of time since it was previously transmitted. In still another alternative, a failure could be declared in response to a retransmit of a segment occurring after more than a certain amount of time has elapsed since a connection entered a retransmit mode.

In some implementations, an outbound path may have failed before a connection between an end point and a server can even be established. In such instances, the outbound path may be considered to have failed when the number of SYN-ACK retransmissions meets or exceeds a threshold.

If the path has not failed, then edge service <NUM> continues to monitor the forward progress of the connection. However, if the path has failed, edge service <NUM> increments a failure counter associated with the connection (step <NUM>). Failure counters <NUM> in <FIG> are representative of the failure counters that edge service <NUM> may maintain for each connection. Failure counters <NUM> include: counter N<NUM> corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; and counter N<NUM> corresponding to connection <NUM>.

Having incremented the failure counter, edge service <NUM> proceeds to generate a hash value from the incremented failure counter and the tuple associated with the connection (step <NUM>). This may involve, for example, mixing the failure counter with the tuple. Mixing the failure counter with the tuple may include replacing one or more of the tuple values with the failure counter, encoding the failure counter in one or more of the tuple values, adding the failure counter to the tuple, or otherwise modifying the tuple to include the value of the failure counter.

Since the path has failed or is otherwise underperforming, edge service <NUM> determines to move the packet flow to a new outbound path, so as to avoid whatever problem along the initial outbound path may be causing the path failure. Edge service <NUM> selects the new outbound path based on the generated hash value (step <NUM>). The hash value may be used to select a specific route from a routing table. In some implementations, the hash value is also used to select the routing table from a set of routing tables.

Edge service <NUM> then reroutes (sends) the packet flow over the new outbound path (step <NUM>). At the same time, other connections that also entered into a failed state may also be rerouted by edge service to the same or other outbound paths. However, the failure condition that triggered the rerouting may eventually abate. Therefore, it may be desired to eventually return (or reroute) all of the rerouted connections to their original outbound paths. If so desired, this step could be performed after a period of time, after the original outbound path has been checked, or in response to some other suitable condition having been met. For instance, a given connection could be returned to the original outbound path and, if successful, then other connections could also be returned to the original outbound path.

<FIG> briefly illustrate the operation of a hash function <NUM> as applied in three different scenarios. It is assumed for exemplary purposes that c ≠ x, j ≠ k, k ≠ <NUM>, and <NUM> ≠ j.

In scenario 300A, tuple <NUM> for one connection is mixed with the failure counter <NUM> for that connection. Mixed input is supplied to hash function <NUM>, which produces hash value <NUM> ("j"). In scenario 300B, tuple <NUM> for a different connection is mixed with the failure counter <NUM> for that connection. The mixed input is supplied to hash function <NUM>, which produces value <NUM> ("k"). However, in scenario 300C, tuple <NUM> is again mixed with failure counter <NUM>. The mixed input produces hash value <NUM> ("<NUM>").

It may be appreciated from the foregoing scenarios that mixing the failure counters into the tuples decreases the likelihood that all of the packet flows are rerouted to the same new outbound path. That is, mixing the failure counter into the tuple increases the likelihood that the rerouted packet flows are well-distributed over multiple outbound paths, so as to avoid burying a given outbound path by rerouting the packet flows to it. This is because, the greater the difference between the hash inputs, the greater the likelihood that hash values will differ. The difference between the hash inputs is increased by mixing in the different failure counters. In fact, in some implementations, the hash function may exhibit an avalanche effect such that only a small change to the hash input (e.g. changing <NUM> bit) results in a large change to the hash output (e.g. <NUM>% of the bits), thereby ensuring that a single outbound path is not overwhelmed.

In an alternative to mixing the failure counter into the hash input, a random value could be added to the output of the hash function upon an initial path failure. Then, the hash output could be incremented upon the detection of every subsequent path failure.

<FIG> illustrate another operational scenario to further demonstrate the technical effects produced by reroute process <NUM> as employed by edge service <NUM> in operational environment <NUM>. Referring to <FIG>, end points <NUM> establish connections <NUM> with edge service <NUM> to obtain content such as web pages, video, images, text, objects, applications, and the like. The end points <NUM> communicate individual requests for the content over the connections. Edge service <NUM> receives the requests and attempts to reply with the content. In some implementations, edge service <NUM> may obtain the content from an origin server or elsewhere if it does not already have the content at its disposal.

Edge service <NUM> transmits the content in the form of packets. The packets make up a packet flow from edge service <NUM> to a specific one of end points <NUM>. A given set of packets (or packet flow) sent in the outbound direction within the context a connection established between the edge service <NUM> and the end point traverses one of outbound paths <NUM>, <NUM>, and <NUM>. When the end point receives a packet, it replies with an acknowledgement message to signal to edge service <NUM> that the packet was received and need not be retransmitted. Such traffic in-bound to edge service <NUM> may traverse the same or a different path as the packets sent in the outbound direction.

In this example scenario, traffic <NUM> is exchanged in the outbound direction between edge service <NUM> and one or more of end points <NUM> via connection <NUM> and <NUM> over outbound path <NUM>. Acknowledgments and other inbound traffic may traverse the same or a different path. Similarly, traffic <NUM> is exchanged in the outbound direction between edge service <NUM> and one or more of end points <NUM> via connection <NUM> and <NUM> over outbound path <NUM>. Acknowledgments and other inbound traffic may traverse the same or a different path. However, in an attempt to send traffic <NUM> (packets) to one or more of end points <NUM>, a failure <NUM> blocks the packets from being received. Accordingly, no corresponding acknowledgements reach edge service <NUM> (as perhaps none have been sent).

Edge service <NUM>, employing reroute process <NUM>, detects the absence of forward progress on both connections, connection <NUM> and connection <NUM>. Edge service <NUM> increments their respective failure counters N<NUM> and N<NUM> to c+<NUM> and x+<NUM> respectively. The incremented failure counters are mixed with the tuple for each respective connection and input into a hash function. The hash function calculates a hash value from the mixed input. Edge service <NUM> then uses the hash value to select a new outbound route for the packet flows associated with the "failed" connections.

<FIG> illustrates an exemplary result of the fast reroute. Connection <NUM> has been rerouted to outbound path <NUM>, while connection <NUM> has been rerouted to outbound path <NUM>. Traffic <NUM> now includes packets and possibly acknowledgements flowing via connection <NUM>, while traffic <NUM> includes packets and acknowledgements flowing via connection <NUM>. In addition, the failure counters have been incremented and may remain so, at least for a period of time, to promote path diversity with respect to traffic rerouting. It may be appreciated that the inbound acknowledgements may take the same or a different path as the outbound packets.

<FIG> illustrates operational environment <NUM> in an implementation. Operational environment <NUM> includes end points <NUM>, edge service <NUM>, and origin servers <NUM> (optional). Edge service <NUM> includes cache servers <NUM>, of which cache server <NUM> is representative, as well as access point <NUM>. Cache server <NUM> includes routing tables <NUM> and <NUM>, in addition to counter table <NUM>.

End points <NUM> communicate with edge service <NUM> via one or more provider networks, represented for the sake of simplicity by provider network <NUM>, provider network <NUM>, and provider network <NUM>. It may be appreciated that one or more other provider networks may connect provider networks <NUM>, <NUM>, and <NUM> to end points <NUM>.

In operation, end points <NUM> establish connections <NUM> with cache servers <NUM> in edge service <NUM> in accordance with a suitable connection-oriented protocol, such as TCP, RTP, QUIC, and the like. The end points request content from the cache servers <NUM> and the cache servers reply with the content. In instances where a given server does not have the content, the server obtains the content from one or more of origin servers <NUM> or from another cache server.

Cache servers <NUM> transmit the content to end points <NUM> via one or more of paths <NUM>, <NUM>, <NUM>. Paths <NUM>, <NUM>, and <NUM> are representative the various paths traffic may take in an outbound direction from access point <NUM> to end points <NUM>. Traffic sent from end points <NUM> to access point <NUM> may travel the same or different paths, but in the inbound direction from the perspective of edge service <NUM>. Paths <NUM>, <NUM>, and <NUM> each traverse one or more networks that connect edge service <NUM> to end points <NUM>, of which provider networks <NUM>, <NUM>, and <NUM> are representative. Examples of provider networks <NUM>, <NUM>, and <NUM> include (but are not limited to) transit networks, peering networks, backbone networks, Internet service provider (ISP) networks, local ISPs, and any other type of network, combination, or variation thereof. Examples of access point <NUM> include, but are not limited to, physical or virtual switches, physical or virtual routers, or any combination or variation thereof.

Cache servers <NUM> transmit their various packet flows within the context of the logical connections made with end points <NUM>, represented by connections <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. The packets of each packet flow traverse a given outbound path selected for the flow. Thus, a given connection may also be considered to traverse a given outbound path. For exemplary purposes, <FIG> illustrates that connections <NUM> and <NUM> traverse path <NUM> in the outbound direction; connections <NUM> and <NUM> traverse path <NUM> in the outbound direction; and connections <NUM> and <NUM> traverse path <NUM> in the outbound direction. Traffic flowing in the inbound direction may take the same or different path as the outbound traffic.

Each connection may be described in terms of a tuple formed by one or more identifying values of the connection. Examples of identifying values of a connection include but are not limited - to its source address, source port, target address, target port, and protocol. Tuple <NUM> is given as an example of identifying values for connection <NUM>. Cache servers <NUM> may utilize said tuples to calculate hash values, which may then be used to navigate one or more routing tables that define which route (or outbound path) to use for a given transmission. As the routes may fail or otherwise underperform from time to time, the cache servers <NUM> employ a reroute process <NUM> for rerouting traffic in response to failures or other performance issues. In addition, cache servers <NUM> employ a reroute process <NUM>. Reroute process <NUM> is described in more detail in <FIG>, while reroute process <NUM> is illustrated in <FIG>.

Reroute process <NUM> and reroute process <NUM> may each be implemented in program instructions in the context of any of the software applications, modules, components, or other such programming elements of cache servers <NUM>. The program instructions direct the underlying physical or virtual computing system or systems (of which computing system <NUM> is representative) to operate as follows, referring parenthetically to the steps in <FIG> and <FIG> in the context of operational environment <NUM> in <FIG> and with respect to cache server <NUM>.

Referring to <FIG>, cache server <NUM> sets a firewall marker (fwmark) to "<NUM>" on the socket used for a connection, via which the cache server sends the packets in a flow (step <NUM>). Setting the firewall marker to zero indicates to reroute process <NUM> in the cache server that a main or base routing table should be used to select a route for a packet.

The packets are sent by access point <NUM> to an end point. If the end point receives the packets, it replies with acknowledgments. If not, then no acknowledgments are forthcoming. Cache server <NUM> therefore monitors for the end point associated with a connection to return an acknowledgment (step <NUM>) and makes a determination, based on the forward progress on the connection, whether the path has failed (step <NUM>). An absence of forward progress would be indicated by a lack of any acknowledgment message.

If the path has not failed, then cache server <NUM> continues to monitor the forward progress of packets being sent on the connection to the end point. However, if the path has failed, then cache serer <NUM> increments a failure counter associated with the connection (step <NUM>). In this implementation, the failure counter is represented in the upper <NUM> bits of the firewall marker value.

Failure counters <NUM> in <FIG> are representative of the failure counters that cache server <NUM> may maintain for each connection that it makes with an end point. Failure counters <NUM> include: counter N<NUM> corresponding to connection <NUM>; counter Nsia corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; counter N<NUM> corresponding to connection <NUM>; and counter N<NUM> corresponding to connection <NUM>.

Having incremented the failure counter for the connection, cache server <NUM> continues to process and send packets to access point <NUM> in the context of the same connection, but with the firewall marker for the connection set to a value greater than zero (step <NUM>). The process repeats for the remaining packets in the flow or until some other event causes the process to cease.

Referring to reroute process <NUM> in <FIG>, cache server <NUM> generates the packets to send over a connection to an end-point (step <NUM>) and identifies which routing table to use based on the value of the firewall marker identified on the socket for the connection (step <NUM>). If the firewall value is zero, then cache server <NUM> utilizes table <NUM>. However, if the firewall value is greater than zero, then cache server <NUM> uses table <NUM>. It may be assumed for exemplary purposes that the base table (table <NUM>) contains fewer routes than table <NUM>. Thus, a non-zero value for the firewall marker results in a greater selection of potential routes for a given packet.

Next, cache server <NUM> generates a hash value using a mixed tuple produced from the failure counter and the tuple for a subject connection (step <NUM>). For instance, cache server <NUM> may mix the failure counter with the tuple. Mixing the failure counter with the tuple may include replacing one or more of the tuple values with the failure counter, encoding the failure counter in one or more of the tuple values, adding the failure counter to the tuple, or otherwise modifying the tuple to include the value of the failure counter.

The mixed input is supplied to a hash function implemented by cache server <NUM> to generate the hash value. The hash function is used to map input values to possible output values. The output values (hash values) may then be used to lookup a particular outbound path or route for a packet.

Cache server <NUM> enters table <NUM> with the hash value to select the appropriate route for the packet (step <NUM>). Table <NUM> stores a list of routes in association with hash values, hash ranges, or other such indications. As such, the resulting hash value is used to look-up or otherwise identify the corresponding route (outbound path). Cache server <NUM> then sends the packet addressed to the end point via the identified route (step <NUM>). This may include, for example, sending the packet to access point <NUM> with the identified route indicated in the packet, in data that encapsulates the packet, or by some other mechanism. In some implementations, each route is identified by a different multi-protocol label switching (MPLS) label.

Cache server <NUM> continues to generate and process incoming packets in this manner. Thus, as the firewall marker is incremented, the resulting hash value may change. The change in hash value may drive a change in outbound routes. In this manner, packet flows may be rerouted, but without over-burdening any given route.

<FIG> illustrate another operational scenario to further demonstrate the technical effects produced by reroute process <NUM> and reroute process <NUM>. Referring to <FIG>, end points <NUM> establish connections <NUM> with edge service <NUM> to obtain content such as web pages, video, images, text, objects, applications, and the like. The end points <NUM> communicate individual requests for the content over the connections. Cache server <NUM> receives the requests and attempts to reply with the content. In some implementations, cache server <NUM> may obtain the content from origin server <NUM> or elsewhere if it does not already have the content at its disposal.

Cache server <NUM> sends the packets to access point <NUM> to send in the form of packets to the end points. The packets make of a packet flow from edge service <NUM> to a specific one of end points <NUM>. A given set of packets (or packet flow) sent within the context a connection established between the edge service <NUM> and the end point traverses one of paths <NUM>, <NUM>, and <NUM>. When the end point receives a packet, it replies with an acknowledgement message to signal to edge service <NUM> that the packet was received and need not be retransmitted. The acknowledgements may traverse the same or a different path as the packets but are shown as traversing the same provider network merely for the sake of simplicity.

In this example scenario, traffic <NUM> (including packets and acknowledgements) is exchanged between edge service <NUM> and one or more of end points <NUM> via connection <NUM> and <NUM> over path <NUM>, although the acknowledgements may optionally take a different path. Similarly, traffic <NUM> (including packets and acknowledgments) is exchanged between edge service <NUM> and one or more of end points <NUM> via connection <NUM> and <NUM> over outbound path <NUM>, although the acknowledgements may optionally take a different path. However, in an attempt to send traffic <NUM> (packets) to one or more of end points <NUM>, a failure <NUM> blocks the packets from being received. Accordingly, no corresponding acknowledgements reach edge service <NUM>, possibly because none have been sent since the packets were blocked.

Cache server <NUM>, employing reroute process <NUM>, detects the absence of forward progress on both connections, connection <NUM> and connection <NUM>. Cache server <NUM> increments their respective failure counters N<NUM> and N<NUM> to c+<NUM> and x+<NUM> respectively. The incremented failure counters are mixed with the tuple for each respective connection and input into a hash function by access point <NUM>. The hash function calculates a hash value from the mixed input. Cache server <NUM> then uses the hash value to select a new outbound route for the packet flows associated with the "failed" connections.

<FIG> illustrates an exemplary result of the fast reroute. Connection <NUM> has been rerouted to path <NUM>, while connection <NUM> has been rerouted to outbound path <NUM>. Traffic <NUM> now includes both packets and acknowledgements flowing via connection <NUM>, while traffic <NUM> includes packets and acknowledgements flowing via connection <NUM>. In addition, the failure counters have been incremented and may remain so, at least for a period of time, to promote path diversity with respect to traffic rerouting. It may be appreciated that the acknowledgement messages may traverse different return paths, including traversing a different provider network(s) than the path travelled by the outbound packets, and are shown as traversing the same paths merely for the sake of simplicity.

<FIG> illustrates the sequence of operations discussed with respect to <FIG> and <FIG> with respect to a single end point. In operation, end point <NUM> sends a content request via provider network <NUM> and access point <NUM> to cache server <NUM>. Cache server <NUM> receives the content request and determines whether the request is a "hit" or a "miss. " A hit means that the server has the requested content, whereas a miss means that the server must obtain the content from an origin server <NUM>, another cache server, or elsewhere.

Cache server <NUM> replies to the content request by sending the content to the end point via access point <NUM>. Cache server <NUM> sets a firewall marker value on the socket for the connection to zero, which causes cache server <NUM> look up the route for the packets in table <NUM>. Cache server <NUM> uses a hash value calculated using a mixed input of the tuple for the connection and the failure counter to look up the route. Accordingly, cache server <NUM> transmits packets to access point <NUM> with a label or other such indication that identifies the selected route/provider (e.g. PID-<NUM>, for network provider <NUM>).

Access point <NUM> receives the packets from cache server <NUM> and sends the packets on the prescribed route addressed to end point <NUM>. End point <NUM> receives the packets and replies with acknowledgment messages per the connection protocol used to establish a connection between end point <NUM> and cache server <NUM>. As mentioned, the acknowledgment messages may (or may not) traverse the same path as the packets. However, a failure <NUM> along the path between cache server <NUM> and end point <NUM> may result in lost packets or other conditions that prevent end point <NUM> from transmitting an ACK to cache server <NUM> (since end point <NUM> would have received nothing to acknowledge).

The absence of forward progress on the connection caused by the failures triggers cache server <NUM> to increment a failure counter encoded in the firewall marker. Cache server <NUM> continues to send packets to the end point <NUM>, but now with the firewall marker on the connection set to the non-zero value of the failure counter. The non-zero value of the firewall marker triggers cache server <NUM> to look in table <NUM> for the appropriate route. Cache server <NUM> does so again with a hash value calculated based on the failure counter and the tuple for the subject connection. However, since a different table is being used, and because the failure counter has been incremented, it is very likely that cache server <NUM> picks a route other than the existing path. Accordingly, cache server <NUM> sends the packets addressed to end point <NUM> but via the new outbound path, so as to avoid whatever problems along the old route prevented end point <NUM> from returning ACKs to cache server <NUM>. In this example, cache server <NUM> affects this by identifying provider network <NUM> as the new route (e.g. PID-<NUM>). As the packets reach end-point <NUM> successfully, end-point <NUM> replies with acknowledgments, which may travel a return path that is the same or different than that of the incoming packets.

<FIG> illustrates computing system <NUM> that is representative of any system or collection of systems in which the various processes, programs, services, and scenarios disclosed herein may be implemented. Examples of computing system <NUM> include, but are not limited to, server computers, routers, web servers, cloud computing platforms, and data center equipment, as well as any other type of physical or virtual server machine, physical or virtual router, container, and any variation or combination thereof.

Computing system <NUM> may be implemented as a single apparatus, system, or device or may be implemented in a distributed manner as multiple apparatuses, systems, or devices. Computing system <NUM> includes, but is not limited to, processing system <NUM>, storage system <NUM>, software <NUM>, communication interface system <NUM>, and user interface system <NUM> (optional). Processing system <NUM> is operatively coupled with storage system <NUM>, communication interface system <NUM>, and user interface system <NUM>.

Processing system <NUM> loads and executes software <NUM> from storage system <NUM>. Software <NUM> includes and implements reroute process <NUM>, which is representative of the reroute processes discussed with respect to the preceding Figures. When executed by processing system <NUM> to provide packet rerouting, software <NUM> directs processing system <NUM> to operate as described herein for at least the various processes, operational scenarios, and sequences discussed in the foregoing implementations. Computing system <NUM> may optionally include additional devices, features, or functionality not discussed for purposes of brevity.

Referring still to <FIG>, processing system <NUM> may comprise a microprocessor and other circuitry that retrieves and executes software <NUM> from storage system <NUM>. Processing system <NUM> may be implemented within a single processing device but may also be distributed across multiple processing devices or sub-systems that cooperate in executing program instructions. Examples of processing system <NUM> include general purpose central processing units, graphical processing units, application specific processors, and logic devices, as well as any other type of processing device, combinations, or variations thereof.

Storage system <NUM> may comprise any computer readable storage media readable by processing system <NUM> and capable of storing software <NUM>. Storage system <NUM> may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. Examples of storage media include random access memory, read only memory, magnetic disks, optical disks, flash memory, virtual memory and non-virtual memory, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other suitable storage media. In no case is the computer readable storage media a propagated signal.

Software <NUM> (including reroute process <NUM>) may be implemented in program instructions and among other functions may, when executed by processing system <NUM>, direct processing system <NUM> to operate as described with respect to the various operational scenarios, sequences, and processes illustrated herein. For example, software <NUM> may include program instructions for implementing a reroute process to reroute packet traffic as described herein.

In particular, the program instructions may include various components or modules that cooperate or otherwise interact to carry out the various processes and operational scenarios described herein. The various components or modules may be embodied in compiled or interpreted instructions, or in some other variation or combination of instructions. The various components or modules may be executed in a synchronous or asynchronous manner, serially or in parallel, in a single threaded environment or multi-threaded, or in accordance with any other suitable execution paradigm, variation, or combination thereof. Software <NUM> may include additional processes, programs, or components, such as operating system software, virtualization software, or other application software. Software <NUM> may also comprise firmware or some other form of machine-readable processing instructions executable by processing system <NUM>.

In general, software <NUM> may, when loaded into processing system <NUM> and executed, transform a suitable apparatus, system, or device (of which computing system <NUM> is representative) overall from a general-purpose computing system into a special-purpose computing system customized to provide packet rerouting. Indeed, encoding software <NUM> on storage system <NUM> may transform the physical structure of storage system <NUM>. The specific transformation of the physical structure may depend on various factors in different implementations of this description. Examples of such factors may include, but are not limited to, the technology used to implement the storage media of storage system <NUM> and whether the computer-storage media are characterized as primary or secondary storage, as well as other factors.

For example, if the computer readable storage media are implemented as semiconductor-based memory, software <NUM> may transform the physical state of the semiconductor memory when the program instructions are encoded therein, such as by transforming the state of transistors, capacitors, or other discrete circuit elements constituting the semiconductor memory. A similar transformation may occur with respect to magnetic or optical media. Other transformations of physical media are possible without departing from the scope of the present description, with the foregoing examples provided only to facilitate the present discussion.

Communication interface system <NUM> may include communication connections and devices that allow for communication with other computing systems (not shown) over communication networks (not shown). Examples of connections and devices that together allow for inter-system communication may include network interface cards, antennas, power amplifiers, RF circuitry, transceivers, and other communication circuitry. The connections and devices may communicate over communication media to exchange communications with other computing systems or networks of systems, such as metal, glass, air, or any other suitable communication media. The aforementioned media, connections, and devices are well known and need not be discussed at length here.

Communication between computing system <NUM> and other computing systems (not shown), may occur over a communication network or networks and in accordance with various communication protocols, combinations of protocols, or variations thereof. Examples include intranets, internets, the Internet, local area networks, wide area networks, wireless networks, wired networks, virtual networks, software defined networks, data center buses and backplanes, or any other type of network, combination of network, or variation thereof. The aforementioned communication networks and protocols are well known and need not be discussed at length here.

Claim 1:
A method (<NUM>) of operating a server (<NUM>, <NUM>, <NUM>) in an infrastructure service to reroute a packet flow sent from the server (<NUM>, <NUM>, <NUM>) to an end point (<NUM>, <NUM>) over an outbound path (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>), the method comprising:
detecting a failure (<NUM>) of the outbound path (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) based on at least a measure of forward progress (<NUM>) made on a connection between the server (<NUM>, <NUM>, <NUM>) and the end point (<NUM>, <NUM>) while sending packets from the server (<NUM>, <NUM>, <NUM>) to the end point (<NUM>, <NUM>), where the measure of forward progress is related to an amount of time elapsed after sending a first packet from the server (<NUM>, <NUM>, <NUM>) to the end point (<NUM>, <NUM>) without receiving an acknowledgment from the end point (<NUM>, <NUM>); and
characterised by:
in response to the failure, generating (<NUM>) a hash value (<NUM>, <NUM>, <NUM>) based at least on an identifying value of the connection and a failure counter (<NUM>, <NUM>, <NUM>, <NUM>) associated with the measure of forward progress made on the connection;
selecting (<NUM>) a next outbound path (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) for the packet flow based on at least the hash value generated in response to the failure; and
sending (<NUM>) the packet flow over the next outbound path (<NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) to the end point (<NUM>, <NUM>).