U-turn indicator in internet protocol packets

A network includes a first node having a processor that incorporates a U-turn indicator into a header of an Internet protocol (IP) packet for transmission along a first path towards a second node. The U-turn indicator indicates that the first node expects to receive the IP packet back from the second node. The first node also includes a transceiver that transmits the IP packet including the header having the U-turn indicator along the first path. In some cases, the transceiver (or another transceiver in another node) receives a packet comprising a U-turn indicator. The processor (or another processor in another node) detects the U-turn indicator in a header of the IP packet. The processor forwards the IP packet along a path to a destination node that does not include the node that originally transmitted the IP packet or drops the IP packet depending on whether an alternate path is identified.

BACKGROUND

Networks that operate according to the Internet Protocol (IP) include nodes such as routers that forward packets over corresponding links between the nodes. The nodes have forwarding tables (or routing tables) that include information that is used to typically forward packets based on destination information included in IP headers of the packets. This is the default mode of forwarding of IP packets, which is referred to herein as “destination-based routing.” Although the nodes and links are generally reliable, forwarding of packets can be disrupted by link failures, node failures, errors in the forwarding tables, and the like. The effects of outages are reduced in some cases by computing alternate paths that are used in the event of errors or failures. For example, fast rerouting techniques are used to forward IP packets along precomputed loop free alternate (LFA) paths without incurring loss during a period of outage using redundancy in the IP network to provide the LFA paths through the network. In response to detecting a link failure, the IP network reruns a shortest path algorithm for the routing protocol assuming that the failed link does not exist, which produces an alternate path that bypasses the failed link and allows the network to resume forwarding traffic (if there was no LFA path for fast rerouting) or redirecting traffic from the LFA path to the new alternate path (if packets are being fast rerouted through LFA path after the failure). Examples of routing protocols that support fast rerouting include the Interior Gateway Protocols (IGPs) such as IP networks that operate according to the Intermediate System to Intermediate System (IS-IS) routing protocol, the Open Shortest Path First (OSPF, OSPFv3) protocols, and the like.

DETAILED DESCRIPTION

Link failures or other outages in an IP network that block communication between nodes via a link create the potential for “U-turn” routing. For example, a U-turn occurs if a forwarding table at a first node forwards a packet towards a second node and the forwarding table at the second node directs the packet back to the first node. In some network topologies, there is no LFA path from a source node to a destination node that can be used for fast rerouting. A potential LFA path from the source node to the destination node may not be available if an intermediate node does not have a link that allows it to connect to the destination node, except via a U-turn path that returns to the source node, which is not permitted in conventional LFA path computations. As another example, if the network forwards packets along an LFA path in response to a link failure along the primary path, a second U-turn path can be created if a link along the LFA path fails concurrently with the link failure along the primary path. As yet another example, a transient loop can occur in response to a topology change before convergence of the shortest path algorithm at the nodes in the network. The topology change can create loops including multiple U-turns prior to convergence of the shortest path algorithm. The loops typically resolve in response to convergence of the shortest path algorithm, although the convergence time can be significant and grows with the size of the network.

FIGS.1-15disclose techniques for preventing loops in IP networks by incorporating U-turn indicators into the headers of packets that are forwarded over links that are associated with U-turns in a network topology. A U-turn indicator includes a destination address of a destination node for the packet, one or more flags, and in some embodiments an address of a node (referred to herein as an “originating node” or an “originator”) that added the U-turn indicator to the header of the packet. The originating node incorporates the U-turn indicator into the header of packets associated with routes that include a U-turn path. The U-turn indicator therefore indicate that the originating node expects another node to forward the packet back towards the originating node. In some embodiments, the originating node includes an entry in a routing table for an alternate path that is tagged as a U-turn path because a second node along the alternate path is expected to forward packets back to the originating node. In response to a failure along a primary path, the originating node reroutes the packet along the alternate path and incorporates a U-turn indicator into a header of the packet.

In some embodiments, the originating node receives a packet from another node and decides to forward the packet back to the node. The originating node incorporates a U-turn indicator into the header of the packet before returning the packet to the node that previously transmitted the packet to the originating node. For example, an originating node can include routing tables that are configured to support an alternate path from a first node to a destination in response to failure of the primary path from the first node to the destination. The originating node receives a packet along the alternate path and detects a failure of a link between the originating node and the destination. The originating node is configured with an alternate path to the destination that includes the first node, so originating node decides to reroute the packet back to first node. The originating node then incorporates a U-turn indicator into the packet before returning the packet to the first node. For another example, an originating node can receive a packet from a first node during convergence of a shortest path algorithm. If the shortest path algorithm has not yet converged at the originating node and the routing table in the originating node indicates that the packet is to be routed back to the first node, the originating node incorporates a U-turn indicator into the packet before returning the packet to the first node.

In response to receiving a packet including a U-turn indicator, nodes selectively forward the packet based on whether the node can identify a path to the destination of the packet that does not include the originating node for the packet that includes the U-turn indicator. The receiving node forwards the packet in response to identifying the path without the originating node. Otherwise, the receiving node drops the packet. For example, if the receiving node is along an alternate path from the originating node to a destination node and a link along the alternate path has failed, the receiving node attempts to identify a second alternate path to the destination node that does not traverse the originating node or the failed link. If the receiving node successfully identifies the second alternate path, the receiving node forwards the packet (including the U-turn indicator) along the second alternate path. Otherwise, the receiving node drops the packet. Thus, loops involving U-turn topologies are stopped if no alternate path that bypasses the U-turn is found.

FIG.1is a block diagram of an Internet Protocol (IP) network100that implements fast rerouting using precomputed alternate paths according to some embodiments. The IP network100includes nodes101,102,103,104, which are collectively referred to herein as “the nodes101-104.” In the illustrated embodiment, the nodes101-104are interconnected by the links111,112,113,114, which are collectively referred to herein as “the links111-114.” A shortest path first (SPF) algorithm is implemented in the nodes101-104and used to calculate paths between the nodes101-104based on weights associated with the links111-114, which are indicated by the numerals in the circles next to the links111-114. For example, the link111has a weight of 1. The SPF algorithm determines that the shortest path from the node101to the node103is via the node102, as indicated by the arrows121,122.

The IP network100includes redundancy to support alternate paths between the nodes101-104. Thus, packets are rerouted along alternate paths in response to failure of one of the links111-114. In the illustrated embodiment, the link111fails, as indicated by the X. In response to detecting the failure, the nodes101-104run instances of the SPF algorithm to determine alternate paths through the IP network100. For example, the node101runs the SPF algorithm and identifies an alternate path to the node103via the node104, as indicated by the arrows123,124. The recovery time for this process is typically on the order of a few seconds. During the convergence (or re-convergence) time for the SPF algorithm, the node101drops packets because there is no available path to the node103. Some applications that receive the packets can recover from the loss by ignoring the packets or requesting retransmission of the lost packets. However, other applications are significantly impacted by packet loss during convergence of the SPF algorithm. For example, voice applications typically expect round-trip response times of less than 250 milliseconds (ms) and an outage that causes the application to lose 3 to 5 seconds of voice packets is unacceptable.

Fast rerouting is used to avoid packet loss during convergence of the SPF algorithm to determine alternate paths. To implement fast rerouting, the nodes101-104precompute alternate paths through the IP network100in addition to a primary path. In the illustrated embodiment, the node101computes the primary path to the node103via the node102and computes the alternate path to the node103via the node104. The primary path and the alternate path are stored in entries of a routing table implemented at the node101so that the node101can immediately switch over to the alternate path in response to detecting a failure along the primary path.

FIG.2is a block diagram of an IP network200that includes a U-turn path as an alternate path according to some embodiments. The IP network200includes nodes201,202,203,204, which are collectively referred to herein as “the nodes201-204.” In the illustrated embodiment, the nodes201-204are interconnected by the links211,212,213, which are collectively referred to herein as “the links211-213.” An SPF algorithm is implemented in the nodes201-204and used to calculate primary and alternate paths between the nodes201-204based on weights associated with the links211-213, which are indicated by the numerals in the circles next to the links211-213. In the illustrated embodiment, the SPF algorithm determines that the primary path from the node201to the node203is via the node202, as indicated by the arrows221,222. The SPF algorithm also determines that the alternate path is from the node201to the node203via the node204, as indicated by the arrow223. Since there is no direct link between the nodes203,204, the SPF algorithm implemented in the node204determines that the shortest path to the node203is via the node201(as indicated by the arrow224) and then via the node202, as indicated by the arrows221,222.

In the illustrated embodiment, the link211fails, as indicated by the X. In response to detecting the failure, the node201reroutes packets from the primary path to the alternate path towards the node204. However, as discussed above, the SPF algorithm has programmed the routing table in the node204to route packets destined for the node203via the nodes201,202. Thus, the packets received by the node204from the node201perform a U-turn at the node204, as indicated by the arrow225. The node204continues to route packets towards the node201until the node204learns that the link211has failed, thereby creating a forwarding loop between the nodes201and204which renders a portion of the network200substantially unusable.

Conventional packets do not include header fields that can indicate whether a packet is being returned to a node (due to a U-turn) or the packet is being intentionally forwarded to a node that is programmed to route the packet back to the originating node (thereby forming a U-turn). The nodes101-104shown inFIG.1and the nodes201-204shown inFIG.2are therefore configured to incorporate a U-turn indicator into headers of packets that are (or will be) conveyed along paths including U-turn topologies. For example, a first node (such as the node101shown inFIG.1or the node201shown inFIG.2) can incorporate a U-turn indicator into a header of a packet for transmission along a first path towards a second node (such as the node103shown inFIG.1or the node203shown inFIG.2) that is configured to forward the packet back to the first node. The first node transmits the packet including the header having the U-turn indicator along the first path. Nodes that receive a packet including a U-turn indicator selectively forward the packet (if a path that does not include the originating node can be found) or drop the packet (if a path that does not include the originating node cannot be found). Some embodiments of U-turn indicator include one or more flags such as flags to encode a reason associated with the U-turn such as an indication that the packet is being fast rerouted along a U-turn alternate path, an indication that the packet previously performed a U-turn at a node, and the like. The flags can also encode information indicating that the address of the originating node is included in the U-turn indicator. The U-turn indicator is included in an IPv4 option or an IPv6 extension header. In some embodiments, the destination address field is included in the U-turn indicator to preserve the original destination address in the IP header because the IPv4 option (or an IPv6 extension header) is evaluated by a receiving router only if the destination address in IP header belongs to the receiving router. In other embodiments, the U-turn indicator is evaluated regardless of whether the destination address belongs to the receiving router, in which case the U-turn indicator does not have to carry a destination address field.

FIG.3is a block diagram of an IP network300that implements fast rerouting using precomputed alternate paths along links with varying weights according to some embodiments. The IP network300includes nodes301,302,303,304, which are collectively referred to herein as “the nodes301-304.” In the illustrated embodiment, the nodes301-304are interconnected by the links311,312,313,314, which are collectively referred to herein as “the links311-314.” An SPF algorithm is implemented in the nodes301-304and used to calculate paths between the nodes301-304based on weights associated with the links311-314, which are indicated by the numerals in the circles next to the links311-314. The network300differs from the network100shown inFIG.1because the weight associated with the link313has a weight of 4.

The SPF algorithm determines that the shortest path from the node301to the node303is via the node302, as indicated by the arrows321,322. The SPF algorithm also determines that the alternate path is from the node301to the node303via the node304, as indicated by the arrow323. Due to the relatively high weight (of 4) on the link313between the nodes303,304, the SPF algorithm implemented in the node304determines that the shortest path to the node303is via the node301(as indicated by the arrow324) and then via the node302, as indicated by the arrows321,322. The path along the link313between the nodes303,304is a loop free alternative (LFA) path available to the node304. However, the node304does not route packets along the LFA path including the link313until the node304detects failure of link314.

In the illustrated embodiment, the link311fails, as indicated by the X. In response to detecting the failure, the node301reroutes packets from the primary path to the alternate path towards the node304. However, as discussed above, the SPF algorithm has programmed the routing table in the node304to route packets destined for the node303on a primary path via the nodes301,302. The node304therefore continues to route packets along the U-turn route back to the node301until the SPF algorithm converges and the node304becomes aware that the link311has failed. Thus, the U-turn topology that results from failure of the link311causes a loop to form over the link314between the nodes301and304.

In order to prevent looping of the packet over the link314, the node301programs an entry in its routing table that indicates that the backup next hop for fast rerouting traffic on failure of the link311is to forward the packets to the node304. The node301also programs the entry to indicate that the path to the node304is a U-turn path because the node304is programmed to forward packets back to the node301. In response to detecting failure of the link311, the node301fast reroutes packets to the backup next hop node304. The node301also includes a U-turn indicator in an option or extension header of the rerouted packets based on the U-turn indication programmed into the routing table. The U-turn indicator includes a destination address from the IP header of the packet in a destination IP address field. The destination address in the IP header of the packet is set to the IP address of the backup next hop node304. In some embodiments, one or more flags in the U-turn indicator are set to indicate that the node301is forwarding the packet along a U-turn alternate path. The IP address of the node301is optionally included to indicate a field of the U-turn indicator that includes an originator IP address.

The packet is received by the node304and identifies the U-turn indicator in the option or extension header of the packet. The node304reads the destination address for the packet from the destination IP address field in the U-turn indicator. The node304then looks up the primary path to the node303based on the destination IP address in the U-turn indicator and verifies that the primary path includes a U-turn for the packet. In response to verifying the U-turn topology, the node304attempts to identify an alternate path (LFA or U-turn) that is programmed into a routing table at the node304. In the illustrated embodiment, the node304identifies the LFA path along the link313, which does not include the originating node301. The node304therefore forwards the packet along the link313to the node303. The node304includes the U-turn indicator in the packet that is forwarded over the link313in case there are additional nodes between the node304and the node303. The node304then sets the destination address of the IP header of the packet to the address of the node304and transmits the packet over the link313towards the node304. If the node304is unable to identify a path towards the node303that does not include the node301, the node304drops the packet.

FIG.4is a block diagram of an IP network400that implements fast rerouting in a dual failure scenario according to some embodiments. The IP network400includes nodes401,402,403,404, which are collectively referred to herein as “the nodes401-404.” In the illustrated embodiment, the nodes401-404are interconnected by the links411,412,413,414, which are collectively referred to herein as “the links411-414.” An SPF algorithm is implemented in the nodes401-404and used to calculate paths between the nodes401-404based on weights associated with the links411-414, which are indicated by the numerals in the circles next to the links411-414. The network400differs from the network400shown inFIG.1because both the link411and the link413have failed in the illustrated embodiment.

Prior to failure of the links411,413, the SPF algorithm determines that the shortest path from the node401to the node403is via the node402, as indicated by the arrows421,422. The SPF algorithm also identifies an LFA path from the node401to the node403via the node404, as indicated by the arrows423,424. The SPF algorithm then programs entries in the routing tables in the node401to indicate the primary path and the LFA path. The SPF algorithm determines that the shortest path from node404to the node403is via link413which is indicated by arrow424. The SPF algorithm also identifies an LFA path from node404to node403via node401, as indicates by the arrows423,421,422. However, the dual failure of the links411,413causes the node401to forward packets to the node404(as indicated by the arrow423) and causes the node404to forward packets back the node401(as indicated by the arrow425), thereby creating a micro loop and rendering that portion of the network400unusable.

To avoid forming the loop between the nodes401and404in the dual failure scenario, the node404includes a U-turn indicator in the packet that was received from the node401before the node404returns the packet to the node401. The destination address that was included in the IP header of the packet received from the node401(e.g., the address of the node403) is preserved in the destination IP address field of the U-turn indicator. The destination address in the IP header of the packet that is returned to the node401is set to the address of the node401. In the illustrated embodiment, flags in the U-turn indicator are set to indicate that the packet has made a U-turn and, optionally, the IP address of the node404is included as the originator IP address in the U-turn indicator. In response to receiving the packet including the U-turn indicator, the node401attempts to rerouting the packet via a path that does not include the node404that originated the U-turn indicator. If successful, the node401forwards the packet along the alternate path. Otherwise, the node401drops the packet, thereby preventing formation of the loop.

Although the formation of micro loops as discussed inFIGS.1-4in the context of alternate or LFA paths for fast rerouting, loops are also formed in some embodiments that use other forms of policy-based routing (PBR) or flow-based routing. For example, if the links411,412,414have weights of 1 and the link413has a weight of 4 (as shown inFIG.3), a routing table in the node401indicates that the shortest path between the nodes401and403is via the node402. If the node401is configured with PBR or flow-based routing, the node401uses a set of rules that are applied based on fields included in one or more headers of the packets processed by the node401. The rules associate packets with different paths based on a mapping between the paths and the values of the fields in the headers of the packets. Thus, the PBR or flow-based routing rules can override the entries in the routing table determined based on shortest path routing and steer packets to an alternate next hop based on the rules. Loops can form if the PBR or flow-based routing rules cause packets to be forwarded along U-turns, e.g., if the node401forwards packets to the node404and the node404forwards the packets back to the node401.

FIG.5is a block diagram of the communication system500that has developed micro-loops during convergence of an SPF algorithm according to some embodiments. The communication system500provides communication pathways to convey packets from a source505to a destination510, as indicated by the arrow515. The source505and the destination510are implemented in one or more entities such as desktop computers, laptop computers, tablet computers, smart phones, Internet of Things (IoT) devices, and the like. The communication system500includes a set of nodes520,521,522,523,524,525, which are collectively referred to herein as “the nodes520-525.”

Packets are conveyed from the source505to the destination510along a path that includes the nodes520-522. In the illustrated embodiment, a link between the node521and the node522fails, as indicated by the cross530. In response to failure of the link, the nodes521and522sends a link state update that informs the nodes520-525that the link has failed. The SPF algorithm implemented in the nodes520-525eventually determines that the shortest path from the source505to the destination510is from the node520to the node522via the nodes523-525. However, the SPF algorithm takes a finite amount of time to converge at the nodes520-525and does not necessarily converge at the same time at all the nodes520-525, which can result in the nodes520-525forwarding packets along an inconsistent path.

Loops form between the nodes520-525while the SPF algorithms are converging at the nodes520-525. For example, if the SPF algorithm at the node521converges before the SPF algorithm at the node520, the node520continues to forward packets to the node521(along the original shortest path) and the node521forwards the packets back to the node520(along the new shortest path), thereby forming a loop535. In response to the SPF algorithm converging at the node520, the node520forwards packets to the node523. However, if the SPF algorithm has not yet converged at the node523, the node520forwards packets to the node523(along the new shortest path) and the node523forwards the packets back to the node520(along the original shortest path) thereby forming a loop540. In a similar manner, loops541,542,543can form while the SPF algorithm is converging at the nodes522,524,525. The loops535,540-543form between pairs of nodes520-525and are therefore referred to herein as micro-loops. The duration of the loops is proportional to the time required to propagate the topology change through the network, as well as the time required for the SPF algorithm to converge at the nodes520-525and for the nodes520-525to update their routing tables.

In principle, the effects of the micro-loops could be eliminated by speeding the whole convergence process to almost zero, but fundamental limits such as the speed of light and memory update latency make this highly unlikely or impossible. Some embodiments of IP networks reduce the impact of transient loops using Fast-Rerouting (FRR) of packets, as discussed herein. The FRR technique uses LFA paths computed by link state protocols as a backup path if the backup path does not cause a forwarding loop. To avoid forwarding loops, the nodes520-525perform additional calculations to verify that a candidate backup path does not create a forwarding loop. A path that does not cause a forwarding loop is identified as an LFA path. The nodes520-525identify the LFA paths in advance and install them against the respective primary paths (shortest paths) into the routing tables of the nodes520-525.

The loops535,540-543are avoided by configuring the nodes520-525to incorporate U-turn indicators into packets. In the illustrated embodiment, the node520forwards packets to the node521(along the original shortest path) and the routing table in the node521indicates that the packet should be forwarded back to the node520(along the new shortest path), which causes the loop535to form, as discussed herein. However, the loop535is avoided or bypassed if the node521incorporates a U-turn indicator into the packet received from the node520before forwarding the packet back to the node520. In response to receiving the packet including the U-turn indicator, the node520attempts to identify an alternate path to the destination510that does not include the node521. If the node520is successful in identifying an alternate path, e.g., because the SPF algorithm has converged and the node520has identified the path to the node523, the node520forwards the packet along the alternate path. Otherwise, the node520drops the packet, thereby keeping the packet from being caught in the loop535.

FIG.6illustrates an IPv4 header600including options that convey U-turn indicators according to some embodiments. The IPv4 header600is included in packets transmitted in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5. The options fields in the IPv4 header600provide for control functions that are needed or useful in some situations but are unnecessary for the most common communications. The Options include provisions for timestamps, security, and special routing.

The options start with a 1-octet type field followed by type specific encoding. Options are of variable length. Thus, minimum size of an Option is 1-octet (Only type) if it does not have any type specific data. The maximum size of an Option is limited by maximum permissible value of IHL field in the IPv4 Header600.

The 1-octet Type is viewed as having 3 fields:1 bit copied flag,2 bits option class,5 bits option number.
The copied flag indicates that this option is copied into all fragments on fragmentation.0=not copied1=copied
The option classes are:0=control1=reserved for future use2=debugging and measurement3=reserved for future use
The IPv4 header includes an IPv4 option that is referred to herein as a “U-turn indicator option.” If the U-turn indicator option is standardized, then the option number31is reserved in the IPv4 parameter registry in IANA. For example, the U-turn indicator can have the format:

An IPv4 option is processed by a receiving router if the destination address in the IPv4 header is a local address in the receiving router. Thus, when U-turn indicator option is included in a packet, the original destination address in the IPv4 header is preserved in the U-turn indicator. Some embodiments of the U-turn indicator include additional flags that encode one or more reason codes, such as codes that indicate whether packet is being fast rerouted along a U-turn alternate path or the packet has previously made a U-turn at another node. In some embodiments, a local IPv4 address of the node that originated the U-turn indicator is encoded in the U-turn indicator option; if present then it is indicated in the flags. The U-turn indicator option therefore carries the fields:
{Destination IPv4 Address,Flags,<Originator's IPv4 Address>}
Parameters within “< >” are not included in some embodiments. In response to a node receiving an IPv4 packet with a destination address for the node and with a U-turn indicator option, the node makes a forwarding decision for the packet based on the Destination IPv4 Address in the U-turn indicator. If the node decides to pass along the option in the forwarded packet, then the node sets the destination address in the IPv4 header to the next hop IPv4 address. If the node decides to exclude the options from the forwarded packet, then the node sets the destination address in IPv4 header to the original address, e.g., the Destination IPv4 Address in the U-turn indicator.

FIG.7illustrates a U-turn indicator option700that is included in an IPv4 header according to some embodiments. The U-turn indicator option700is included in some embodiments of the IPv4 header600shown inFIG.6. The fields in the encoding of the U-turn indicator option700are as follows.Type: 1-octet field that indicates U-turn indicator option in tuples of COPY, CLASS and NUMBER.Length: 1-octet field that indicates length of this option that includes Type, Length, Flags, Reserved, Destination IPv4 Address and optional Originator's IPv4 Address. If Originator's IPv4 Address is included then length is 12, otherwise the length is 8.Flags: 1-octet field that indicates several flags as below:

+−+−+−+−+−+−+−+−+|     | O|U|F |+−+−+−+−+−+−+−+−+F: If set to 1, then indicates that packet is fast rerouted along a U-turn alternate path.U: If set to 1, then indicates that packet has made a U-turn.O: If set to 1, the indicates Originator's IPv4 Address field is present.Reserved: 1-octet field reserved for future use. Sender sets this field to 0 and receiver ignores this field.Destination IPv4 Address: The original destination address from IPv4 Header is preserved in this 4-octet field.Originator's IPv4 Address: Optional 4-octet field, which is present only if 0 flag is set to 1. This field carries an IPv4 address of the router that originated the U-turn indicator in the IPv4 packet.

In some embodiments, an IPv4 Router Alert option is used in conjunction with including U-turn indicator option in an IPv4 packet. The presence of the Router Alert option in the IPv4 packet means a receiver examines the contents of the IPv4 packet irrespective of the destination address in the IPv4 header of the packet. Examination of the IPv4 packet includes examination of the U-turn indicator option, if present. Since the original destination address in the IPv4 header remains unmodified when U-turn indicator option is included along with Router alert option, the Destination IPv4 Address field in not required in U-turn indicator. Thus, some embodiments define the U-turn indicator option with following fields:
{Flags,<Originator's IPv4 Address>}

FIG.8illustrates IPv6 headers800,801that include header extensions such as a header extension that conveys U-turn indicators according to some embodiments. The IPv6 header800is included in packets transmitted in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5. The IPv6 headers800,801include a first portion805made up of a set of fields including a version field110, a class field811, a flow label812, a length813, a next header field814, a hop limit815, a source address816, and a destination address817. The next header field814includes information (such as a pointer) to an additional header such as an upper layer header818. Examples of upper layer headers are transport protocol headers such as TCP, UDP, SCTP, etc. The IPv6 headers800,801are appended to a corresponding payload820to form an IPv6 packet.

The first portion805of the IPv6 header remains fixed in size (e.g., 40 bytes) and extension headers are added to provide for control functions in some embodiments. For example, extension headers can be used for timestamps, security, and special routing. In the illustrated embodiment, the next header field825includes information (such as a pointer) indicating another next header field830that is associated with extension header831. The next header field830includes information (such as a pointer) indicating a subsequent next header field835that is associated with extension header836. The next header field835includes information (such as a pointer) indicating a subsequent next header field840that is associated with extension header841. The next header field840includes information (such as a pointer) to the upper layer header818. Although four next header fields825,830,835,840are shown inFIG.8, some embodiments of the IPv6 header800include more or fewer next header fields.

In the illustrated embodiment, one of the extension headers831,836,841is used for a U-turn indicator. The IPv6 extension headers831,836,841are processed by a receiving node only if the destination address817in the IPv6 header805is a local address in the receiving node. If a U-turn indicator header is included in a packet, the original destination address817in the IPv6 header805is preserved in the U-turn indicator header. Some embodiments of the U-turn indicator include one or more additional flags that encode one or more reason codes, such as whether packet is fast rerouted along a U-turn alternate path or the packet made a U-turn, and the like. In some embodiments, a local IPv6 address of the node that originated the U-turn indicator is encoded in the U-turn indicator header. If the local IPv6 address of the node is present in the U-turn indicator, then it is indicated in the flags. The U-turn indicator header carries the fields:
{Destination IPv6 Address,Flags,<Originator's IPv6 Address>}

Parameters enclosed within “< >” are not included in some embodiments. When a node receives an IPv6 packet with destination address817that refers to the node and with U-turn indicator header, the node makes the forwarding decision for the packet based on the Destination IPv6 Address in the U-turn indicator. If the node decides to pass along the extension header in the forwarded packet, then the node sets the destination address817in the IPv6 header to the next hop IPv6 address. If the node decides to exclude the extension header from the forwarded packet, then the node sets the destination address817in IPv6 header to the original destination address, e.g., the Destination IPv6 Address in the U-turn indicator. In some embodiments, the type of the extension header including the U-turn indicator is type150and is referred to as a “U-turn Indicator Header” to carry the U-turn indicator in an IPv6 packet. If the techniques disclosed herein are standardized, then the EH Type is reserved in IPv6 parameters registry in IANA.

FIG.9illustrates a U-turn indicator header900that is included in an IPv6 header according to some embodiments. The U-turn indicator header900is included in some embodiments of the IPv6 header800shown inFIG.8. The fields in the encoding of the U-turn indicator header900are as follows:Next Header 8-bit selector. Identifies the type of header immediately following the U-turn Indicator Header. Uses the same values as the IPv4 Protocol field [PROT_NUM].Hdr Ext Len 8-bit unsigned integer. Length of the U-turn header in number of octets, not including the first 2 octets. If the optional Originator's IPv6 Address is included then value of this field is 34, else 18.Flags: 1-octet field that indicates several flags as below:

+−+−+−+−+−+−+−+−+|     | O|U|F |+−+−+−+−+−+−+−+−+F: If set to 1, then indicates that packet is fast rerouted along a U-turn alternate path.U: If set to 1, then indicates that packet has made a U-turn.O: If set to 1, the indicates Originator's IPv6 Address field is present.Reserved: 1-octet field reserved for future use. Sender sets this field to 0 and receiver ignores this field.Destination IPv6 Address: The original destination address from IPv6 Header is preserved in this 16-octet field.Originator's IPv6 Address: 16-octet field, which is present in some embodiments if 0 flag is set to 1. This field carries an IPv6 address of the router that originated the U-turn indicator header in the IPv6 packet.

In some embodiments the U-turn indicator is encoded as a TLV in an IPv6 Hop-by-Hop options EH. The presence of a Hop-by-Hop options header in the IPv6 packet means a receiver examines the information within the header, irrespective of the destination address in the IPv6 header of the packet. The Hop-by-Hop options header can carry one or more TLVs and each TLV encodes independent information to be examined routers that forward the IPv6 packet. Since the original destination address in the IPv6 header remains unmodified when U-turn indicator option is encoded as a TLV in a Hop-by-Hop options header, the Destination IPv6 Address field in not required in U-turn indicator. Thus, some embodiments define the U-turn indicator option with following fields:
{Flags,<Originator's IPv6 Address>}

FIG.10is a flow diagram of a first portion1000of a method of originating and processing a U-turn indicator according to some embodiments. The first portion1000of the method is implemented at the nodes in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5.

The method begins at block1001. The method receives input1005including the IP packet that is to be forwarded by the node and the link/interface on which the IP packet arrived at the node.

At block1010, the node determines whether the destination address in the IP header of the IP packet is local to the node. If not, the method flows to the block1015. If the destination address in the IP header of the IP packet is local to the node, the method flows to decision block1020.

At block1015, the node reads the destination address in the IP header as a key (or index) for looking up a corresponding entry in the routing table. The method then flows to the block1030.

At the decision block1020, the node determines whether the IP header includes a U-turn indicator. If not, the method flows to the block1035and the node handles the IP packet using conventional techniques. The method then flows to the node1, which connects to the node1inFIG.12. If the IP header includes a U-turn indicator, the method flows to the block1025.

At block1025, the node reads the destination address field from the U-turn indicator and uses the value in the destination address field as the key (or index) for looking up a corresponding entry in the routing table.

At block1030, the node uses the key (or index) determined in block1015or block1025to look up a corresponding entry in the routing table for the node.

At decision block1040, the node determines whether a corresponding entry that matches the key (or index) is found in the routing table. If not, the method flows to node2, which connects with the node2inFIG.12. If the node identifies a matching entry in the routing table, the method flows to node3, which connects with the known3inFIG.11.

FIG.11is a flow diagram of a second portion1100of the method of originating and processing a U-turn indicator according to some embodiments. The second portion1100of the method is implemented at the nodes in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5. Node3connects the decision block1105with the decision block1040inFIG.10.

At decision block1105, the node determines whether the next hop along the primary path for the IP packet is operational. If so, the method flows to the decision block1110. Otherwise, the method flows to the decision block1120.

At decision block1110, the node determines whether the next hop link is the same as the link that conveyed the IP packet to the node. If so, the path traversed by the IP packet has a U-turn topology and the method flows to the decision block1115. If not, the method flows to the node4, which connects to the node4inFIG.12.

At decision block1115, the node determines whether the IP packet includes a U-turn indicator. If not, the method flows to the node4, which connects to the node4inFIG.12. If the IP packet includes a U-turn indicator, e.g., in an option of the header or an extension header, the method flows to decision block1120. The presence of a U-turn indicator in the IP packet indicates that the IP packet should not make an additional U-turn. Instead, the IP packet should be forwarded on an alternate next hop associated with a path that does not include the originating node for the U-turn indicator. The IP packet should be dropped if an alternate next hop cannot be found.

At decision block1120, the node determines whether there is a backup next hop that is operational. If not, the method flows to the node2, which connects with the node2inFIG.12. If a backup next hop is operational, the method flows to the node5, which connects with the node5inFIG.12.

FIG.12is a flow diagram of a third portion1200of the method of originating and processing a U-turn indicator according to some embodiments. The third portion1200of the method is implemented at the nodes in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5. Node1connects the block1205with the block1035inFIG.10. Node2connects the decision block1210with the decision block1040inFIG.10and the decision block1120inFIG.11. Node3connects the decision block1105with the decision block1040inFIG.10. Node4connects the block1215with the decision blocks1110,1115inFIG.11. Node5connects the block1220with the decision block1120inFIG.11.

At block1210, the node drops the IP packet. In some embodiments, the node also performs related actions such as sending an error indication back to the source of the dropped packet. The method then flows to the node1205and the method ends.

At block1215, the node sets the primary next hop as the next hop to forward the IP packet. The method then flows to the block1225.

At block1220, the node sets the backup next hop as the next hop to forward the IP packet. The method then flows to the block1225.

At block1225, the node forwards the IP packet to the next hop selected by the operations at block1215or at block1220. In some embodiments, the node performs origination of a U-turn indicator in the IP packet, if required. The method then flows to the block1205and the method ends.

FIG.13is a flow diagram of a first portion1300of a method of forwarding an IP packet to a next hop according to some embodiments. The method is implemented at the nodes in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5. Some embodiments of the method are used to perform the operations in block1225shown inFIG.12.

The method begins at block1301. The method receives input1305including the IP packet that is to be forwarded by the node, the next hop on which to forward the IP packet, and the link/interface on which the IP packet arrived at the node.

At block1310, the node initializes a local variable (Flags) that is used to set the flags for the U-turn indicator, if the flags are included in the U-turn indicator.

At decision block1315, the node determines whether the next hop is marked as a U-turn backup next hop or a U-turn alternate next hop. If yes, the method flows to the block1320. If the next hop is not marked as a U-turn backup/alternate next hop, the method flows to the decision block1325.

At the block1320, the node sets the F bit in the local variable Flags to indicate that the IP packet is forwarded on a U-turn alternate path. The method then flows to node1, which connects to the node1inFIG.14.

At decision block1325, the node determines whether the next hop link is the same as the link on which the IP packet arrived at the node. If yes, the method flows to the block1330. If the next hop link is not the same as the link on which the packet arrives, the method flows to the decision block1335.

At block1330, the node sets the U bit in the local variable Flags to indicate that the IP packet is making a U-turn at the node. The method then flows to node1, which connects to the node1inFIG.14

At decision block1335, the node determines whether the IP packet already includes a U-turn indicator. If not, the method flows to the node2, which connects to the node2inFIG.14. If the IP packet already includes a U-turn indicator, the U-turn indicator should be passed on to the next hop. The method therefore flows to the node3, which connects to the node3inFIG.14.

FIG.14is a flow diagram of a second portion1400of the method of forwarding the IP packet to a next hop according to some embodiments. The second portion1100of the method is implemented at the nodes in some embodiments of the communication systems100,200,300,400,500shown inFIGS.1-5. Node1connects the decision block1405with the block1320,1330inFIG.13. Node2connects the block1410with the decision block1335inFIG.13. Node3connects the block1415with the decision block1335inFIG.13.

At decision block1405, the node determines whether the IP packet already includes a U-turn indicator. If not, the method flows to the block1420. If the IP packet includes a U-turn indicator, the method flows to the block1415.

At the block1420, the node inserts a U-turn indicator into the header of the IP packet. The node copies the destination address from the IP header of the received packet into the destination IP address field of the U-turn indicator. Some embodiments of the U-turn indicator also include the local Flags variable, the local address of the node as the originator IP address field in the U-turn indicator, or a combination thereof. The method then flows to block1415.

At the block1415, the node sets the destination address in the IP header as the address of the next hop because the IP packet includes a U-turn indicator. The method then flows to the block1410.

At the block1410, the node sends the IP packet to the next hop. The method then flows to the block1425and the method ends.

FIG.15is a block diagram of a communication system1500that implements U-turn alternate paths in packet rerouting according to some embodiments. The communication system1500includes nodes1501and1502that are used to implement some embodiments of the nodes in communication systems100,200,300,400,500shown inFIGS.1-5. In the illustrated embodiment, the nodes1501and1502are implemented using transceivers1505,1506to transmit and receive packets such as IP packets that are conveyed through the network, memories1510,1511to store data and instructions, and processors1515,1516to execute the instructions, e.g., by performing operations indicated by the instructions stored in the corresponding memory1510,1511on the data stored in the corresponding memory1510,1511and storing the results in the corresponding memory1510,1511. The nodes1501and1502are therefore able to implement some embodiments of the methods shown inFIGS.10-14.