Patent Description:
In communication networks, various communications technologies may be used to support various types of communications. Patent publication <CIT> describes a routing header encapsulation method and device of IPv6 message.

The dependent claims define particular embodiments of the invention.

To facilitate understanding, identical reference numerals have been used herein, wherever possible, in order to designate identical elements that are common among the various figures.

Various example embodiments for supporting source routing are presented herein. Various example embodiments for supporting source routing may be configured to support source route compression for source routing. According to the claimed invention, for supporting source route compression for source routing a configuration is set to support communication of a source routed packet over a path from an ingress node to an egress node over a network, wherein the network includes a plurality of sets of network elements, each set having a respective set of network element identifiers sharing a common prefix, wherein the source routed packet has encoded therein a plurality of source route blocks, each source route block including the respective common prefix and a respective offset list, wherein the offset list includes a set of offset values associated with respective ones of the network elements of the path and configured to be combined with the common prefix to recover the network element identifiers of the respective ones of the network elements of the path. It will be appreciated that these and various other example embodiments and advantages or potential advantages of supporting source routing may be further understood by way of reference to the various figures, which are discussed further below.

<FIG> depicts an example embodiment of a communication system configured to support source routing based on source route compression.

The communication system <NUM> includes a communication network <NUM> and a controller <NUM>. The communication network <NUM> is a packet-switched network including a set of routers <NUM>-<NUM> - <NUM>-<NUM> (collectively, routers <NUM>, which are also referred to herein using the notation Rx) and a set of communication links <NUM> via which the routers <NUM> are communicatively connected. The communication network <NUM> is configured to support various data plane and control plane functions for supporting communication of traffic including communication of source routed packets. The communication network <NUM> is configured to support source routing of packets using source route compression. The routers <NUM> are configured to support source routing of packets using source route compression. The routers <NUM>-<NUM> - <NUM>-<NUM> include source routing elements <NUM>-<NUM> - <NUM>-<NUM> (collectively, source routing elements <NUM>), respectively, which are configured to support source routing of packets using source route compression. The controller <NUM> is configured to provide various control functions for the communication network <NUM> (e.g., maintaining network topology and traffic engineering information, computing source routes for ingress routers in the communication network <NUM>, or the like, as well as various combinations thereof) including control functions configured to support source routing of packets by routers <NUM> of communication network <NUM> based on source route compression. The controller <NUM> includes a source routing element <NUM> configured to support source routing of packets, based on source route compression, by routers <NUM> of communication network <NUM>. Various example embodiments for supporting source route compression within the communication network <NUM> may be further understood by first considering various aspects of packet switched networks configured to support source routing.

Packet-switched networks are built on mesh topologies in which multiple paths to a destination exist. The links in the mesh are point-to-point links joined by nodes. A path to a destination may go through any number of nodes, and the path may change at any time due to traffic problems or failed links. In this environment, there are two possible packet routing methods: hop-by-hop destination-based routing and source routing.

Hop-by-hop, destination-based routing is like getting directions along the way. A packet has a destination address. Each node looks at the address and makes a routing decision about how to forward the packet. Thus, decisions are made on a hop-by-hop basis in the network until the packet reaches its destination.

Source Routing, also called explicit path addressing, allows a head-end node to partially or completely specify the route the packet takes through the network. The head-end node discovers an explicit path for a packet flow through the network in advance of sending packets. The explicit path is "encoded" into the packet and transit nodes forward packet based on that path. Source Routing minimizes the states required in transit nodes to forward a packet, since each node only maintains forwarding information to one of its next-hops and is not required to maintain forwarding information to each possible packet destination. An example of a generic method of source routing, described within the context of <FIG>, follows.

For the generic method of source routing, in <FIG>, assume that R1 (head-end node) decides to send a packet along the path R1-R2-R4-R7-R8. Assume that R1, R2, R3. , R8 are loopback addresses assigned as node identifiers. So, R1 encodes the explicit path with node identifiers as {R2, R4, R7, R8} into the packet and sends to R2. When R2 receives the packet, it looks up the first hop in the explicit path, which is R2. Since the first hop R2 identifies itself, it pops the first hop. It then looks up the new first hop, which is R4, and forwards the packet to R4 with the explicit path in the packet as {R4, R7, R8}. R4 pops the first hop in the explicit path, which is R4, since it identifies itself. R4 then looks up the new first hop, which is R7, and forwards the packet to R7 with the explicit path {R7, R8}. When R7 receives the packet, it pops the first hop, which is R7, since it identifies itself. It then looks up the new first hop, which is R8, and forwards the packet to R8 with the explicit path {R8}. When R8 receives the packet, it pops the first hop, which is R8, since it identifies itself. As discussed further below, source routing may be performed using a loose source routing and/or a strict source routing.

In loose source routing, the head-end node can encode a set of nodes to be traversed and intermediate nodes along the path can choose among multiple paths to reach any nodes in the set of nodes. For example, in the example of the generic method of source routing described above, R2 may find the "optimal" path to R4 is via R2-R3-R4 instead of R2-R4. In this case, R2 will send explicit path {R3, R4, R7, R8} to R3. When R3 receives the packet and finds the first hop in the path as R3, it would pop R3, since it identifies itself. R3 then looks up the new next-hop, which is R4, and sends the packet with path {R4, R7, R8} to R4. So, when an explicit path contains one or more node identifier(s) then the path is called a loose source route since an intermediate node can choose one among the multiple paths to reach the a node, which is a loopback address in that node.

In strict source routing, the head-end node can encode a set of hops to be traversed and intermediate nodes along the path forward based on the specified hops. For example, in the example of the generic method of source routing described above, R1 encodes a set of next-hop identifiers such as {R2->R4, R4->R7, R7->R8} to specify the path to be taken by the packet. When R2 receives the packet, it looks up the first hop in the explicit path, which is R2->R4. Since R2->R4 identifies the directly connected link, so R2 pops the first hop from the explicit path. It forwards the packet on the R2->R4 link. Similarly, when R4 receives the packet it forwards the packet to R7. When R7 receives the packet is forwards the packet to R8. In this manner, the exact path traversed by the packet is specified by the source node R1.

It will be appreciated, as indicated above, that a source node also may specify a mix of loose hops and strict hops. For example, in the example of the generic method of source routing described above, R1 can also specify a mix of strict and loose hops such as {R2->R4, R8}. It will be appreciated that strict source routing is preferable when a packet belonging to a service or application that needs to meet strict Quality of Service (QoS) or Service Level Agreement (SLA) and, thus, must follow a strict path. So, strict source routing is the default choice for source routing with traffic engineering (TE). A description of source routing with traffic engineering (SR-TE) follows.

In SR-TE, various TE parameters are assigned into the network elements (e.g., the nodes and links). The TE parameters of a network element describe the cost, delay, throughput, available bandwidth, packet loss characteristics etc. of the network element. The topology and TE parameters of all network elements are learned and are maintained in a centralized TE Database (TEDB) hosted by a controller (e.g. a Path Computation Element (PCE), a Software Defined Networking (SDN) controller, or the like). The controller can learn topology and TE information by listening to link-state advertisements (LSAs) from the Interior Gateway Protocol (IGP) running among the routers (e.g., Intermediate-System-to-Intermediate-System (ISIS), Open Shortest Path First (OSPF), or the like). The controller can also gather such information from the routers, e.g., using Border Gateway Protocol - Link State (BGP-LS) such as in RFC <NUM>, using a push/pull mechanism or the like, as well as various combinations thereof.

In SR-TE, the head-end node classifies packets into flows based on application or a service. Each flow is associated with specific QoS requirement or SLA. The head-end node sends a request to the controller (e.g., PCE, SDN controller, or the like) to compute an optimal/explicit path that meets the specified QoS/SLA. The controller typically computes such a path by running Constraint Shortest Path First (CSPF) techniques on the TE DB. Once a path is allocated, the controller updates the dynamic TE state (e.g. residual bandwidth) of the network elements along that path into the TEDB. The head-end node sends all packets belonging to a flow over the explicit path that meets the QoS/SLA of the flow. The explicit path is encoded into the packet. Thus, it is possible that packets of different flows to same destination follow diversified paths. The per-flow states are maintained only at the head-end node and transit nodes are completely agnostic of a flow, the QoS/SLA needs of the flow, and so forth. This results in a significant reduction of cost and complexity at transit nodes.

In recent years, Source Routing, which was typically used for Internet Protocol version <NUM> (IPv4), has been revamped as Segment Routing (SR) by extending source routing capabilities into Multiprotocol Label Switching (MPLS) and IP version <NUM> (IPv6). In SR, the loopback address of a router is referred to as a "Prefix Segment" and next-hop adjacency/link between two routers is referred to as an "Adjacency Segment". In SR, each segment is assigned a Segment Identifier (SID), which is encoded into an explicit path to identify the segment. SR using an MPLS dataplane is described in RFC <NUM> and SR using an IPv6 dataplane is described in RFC <NUM>. There is no explicit specification for SR using an IPv4 dataplane, since SR uses the IPv4 source routing described in the base IPv4 specification RFC <NUM>. It is noted that, since SR includes SR-TE aspects, the term "SR" as used herein, unless indicated otherwise, includes SR-TE as well.

In SR using an MPLS dataplane, packet flows are enforced through a specific path by applying, at the ingress node, a specifically designed stack of segment identifiers (SIDs) fully compatible with the MPLS data plane. The stack of SIDs is referred to as a "segment list" and corresponds to the stack of labels in the MPLS architecture. The ingress router sends a packet with the list of SIDs (stack of labels) wherein each SID indicates a next-hop or router to be traversed by the packet. Only the top SID in the list is processed during packet forwarding by transit nodes. Each packet is forwarded along the shortest path toward the network element represented by the top SID. For example, a Prefix-SID can represent an Equal Cost Multipath (ECMP)-aware shortest-path to an IGP prefix (i.e., IGP-Prefix) which identifies a specific router (i.e., IGP-Node Segment). For example, an Adjacency-SID represents a hop over a specific adjacency between two nodes in the IGP (i.e., IGP-Adjacency Segment). A Prefix Segment is typically a multi-hop path while an Adjacency Segment, in most cases, is a one-hop path. Unlike traditional MPLS networks, SR maintains per-flow state only at the ingress node, where the segment list is applied. Therefore, no signaling protocol (e.g., Resource Reservation Protocol with traffic engineering extensions - RSVP-TE) is required to populate the forwarding table of transit nodes. In this way, a simplified control plane is employed, just relying on the IGP that is properly extended to advertise SIDs as additional attributes of LSAs. Thus, scalability of transit nodes is greatly improved, since MPLS Label Switch Paths (LSPs) state information is not required.

In SR using an IPv6 dataplane, similar to SR using an MPLS dataplane, packet flows are enforced through a specific path by applying, at the ingress node, a specifically designed stack of SIDs. In SR using an IPv6 dataplane, however, SIDs are encoded into the packet as IPV6 addresses assigned to Adjacency Segments or Node Segments.

In SR-TE, a strict-hop path would consist of a stack of Adjacency-SIDs where each such SID will designate a strict hop to be traversed. Thus, in SR, a packet traversing <NUM> strict next-hops will start from the head-end with a label stack of <NUM> labels in an MPLS dataplane and list of <NUM> IPV6 addresses in an IPv6 dataplane.

It is noted that, herein, generic source routing specific terminology, rather than SR-specific terminology, is primarily used. For example, a node or a link between two nodes, unless otherwise specified, is generically referred to herein as a "network element" and a network element encoded in the source route is referred to as a "hop" in the source route path.

Various example embodiments may be configured to support a compressed form of encoding a source route into a packet, which can be applied to any packet switching technology (e.g., IPv4, IPv6, MPLS, Ethernet, or the like). Various example embodiments may be configured to provide a generic and efficient mechanism to compress a source route in a manner configured to impose the least overhead in a packet irrespective of whether the source routed network is based on IPv4, IPv6, MPLS, Ethernet, or the like.

Various example embodiments may support a compressed form of encoding a source route into a packet based on assignment of identifiers to network elements where the identifiers share a common prefix (also referred to herein as a shared prefix). The identifiers of the network elements may be assigned one or more blocks of identifiers, multiple contiguous or non-contiguous blocks of identifiers, or the like, as well as various combinations thereof. For example, assume that a common IPv4 prefix <NUM>. <NUM>/<NUM>, which can be used for addressing up to <NUM> network elements, may be used for assigning identifiers to <NUM> network elements and the identifiers may be assigned from two non-contiguous blocks by assigning <NUM> identifiers from the block <NUM>. <NUM>-<NUM>. <NUM> and assigning <NUM> identifiers from the block <NUM>. <NUM>-<NUM>. It will be appreciated that network elements may use various other types and arrangements of identifiers sharing a common prefix. The use of network elements having identifiers that share a common prefix enables the identifier of a network element to be represented as { Shared_Prefix, Offset} where 'Shared_Prefix' is the common prefix of the network element and 'Offset' is the offset of the identifier of the network element in Shared_Prefix. So, the identifier of the network element may be computed as Shared_Prefix + Offset. This enables a source route to be represented as a list of offsets of the network elements of which the source route is composed. It will be appreciated that this may be applied to all or part of a network, may be applied to one or more network partitions where a network is partitioned (as discussed further below), or the like, as well as various combinations thereof).

According to the claimed invention a compressed form of encoding a source route into a packet based on partitioning of the source routed network into "areas" of network elements (e.g., nodes and links) is supported. In each area, one or more blocks of identifiers is allocated to the area and network elements in the area are assigned identifiers from the one or more allocated blocks of identifiers. This enables the identifier of a network element in an area to be represented as { Shared_Prefix, Offset} where 'Shared_Prefix' is the common prefix in the one or more blocks of identifiers in the area and 'Offset' is the offset of the identifier in Shared_Prefix. So, an identifier is computed as Shared_Prefix + Offset. This is illustrated in <FIG>, which uses the same topology from <FIG>, but where the topology has been partitioned into two areas.

In <FIG>, communication system <NUM> is similar to the communication system <NUM> of <FIG>. The communication system <NUM> includes the same routers as in <FIG>, and includes a PCE configured to operate as the controller of <FIG>.

In <FIG>, nodes R1-R5 are in Area <NUM> and nodes R6-R8 are in Area <NUM>. Network elements in Area <NUM> share the common prefix '<NUM>' and network elements in Area <NUM> share the common prefix '<NUM>'. In <FIG>, the identifiers are shown in the notation of Shared _Prefix. Offset (e.g., the identifier of node Rx is Shared_Prefix_of_Rx. X and the identifier of the link between Rx and Ry is the Shared _Prefix_of_Rx. A few example identifiers are as follows: (<NUM>) Node R3 = <NUM>, (<NUM>) Node R6 = <NUM>, and (<NUM>) Link R4->R7 = <NUM>.

In this way, the network elements in an area are represented as an offset to the Shared_Prefix. This allows the segment of a source route within an area to be encoded as the tuple { Shared _Prefix, Size _Of Offset, Offset_List[]}, where Offset_ List[]' is the list of the offsets of the hops in the path and 'Size_Of_Offset' is the length of an entry in the Offset_List[] in bytes. Then, the identifier of the hop 'n' in the path is computed as Shared_Prefix+ Offset_List[n]. This encoding is referred to herein as a Compressed Source Route Block (CSRB). According to the claimed invention, a Compressed Source Route (CSR) includes a plurality of CSR Blocks where each block represents the hops in an area within the source route. A generic encoding of CSR Block for an area is illustrated in <FIG> and a generic format of a CSR for a packet is illustrated in <FIG>, both of which can be extrapolated to any packet switching technology.

In <FIG>, the CSR Block <NUM> includes a Shared_Prefix field, a Size_of_Offset field, and an Offset_List[] including [n] Offset _List fields (denoted as Offset_List[<NUM>] - Offset _List[n]). In <FIG>, the Size_of_Offset field can be encoded in various ways. For example, the Size_of_Offset field can be encoded with the following values: (a) <NUM> = size of an entry in Offset_List[] is 1B and (b) <NUM> = size of an entry in Offset _List[] is 2B. For example, the Size_of_Offset field can be encoded by the number of bits in an entry in Offset_List[].

According to the claimed invention, in <FIG>, the CSR <NUM> includes P CSRBs associated with P areas of the network to be traversed by the packet including the CSR (denoted as CSRB <NUM> through CSRB P). It will be appreciated that each of the CSRBs depicted in <FIG> may be encoded as a CSRB presented with respect to <FIG> (i.e., in the CSR, each CSRB can include n Offset_List entries for the n network elements of the area with which the CSRB is associated).

If the size of an entry in Offset_List[] is chosen as 1B, then up to <NUM> network elements can be included in an area. If the size of an entry in Offset _List[] is chosen as 2B, then up to <NUM> network elements can be included in an area, which is typically more than the number of network elements in a typical source routed network. So, with a 2B size, the entire network can be accommodated within a single area and, thus, the CSR would include only one CSRB.

The concept of CSR is illustrated with the generic example of <FIG>. For example, assume that a strict source route is {R1->R2, R2->R4, R4->R7, R7->R8}. Since the path traverses two areas, the CSR would include two CSR Blocks. The encoding of the CSR would be: {CSRBlock <NUM> = {Shared_Prefix = <NUM>, Size_Of_Offset = <NUM>, Offset _List [] = {<NUM>, <NUM>, <NUM>}}, CSR Block <NUM> = {Shared_Prefix = <NUM>, Size_Of_Offset = <NUM>, Offset _List[] = {<NUM>}}}.

It is noted that, in IPv4 and IPv6, the concept of sub-netting is already used in allocation of IP addresses to network elements, so an IP subnet can be assigned to an area for allocation of the identifiers for its network elements. Then, all network elements in an area can be represented as offset to the IP prefix of the subnet.

The compression which may be achieved based on use of a CSR in an IPv4 network may be understood with respect to the following examples. In an existing IPv4 source route, <NUM> hops consumes 30x4B = 120B. As a first example, assume that, in an IPv4 source routed network, an area is assigned a subnet <NUM>. <NUM>/<NUM>. So, the area can have up to <NUM> network elements. Here, further assume that a source route of <NUM> hops traverses only through that single area, which would be the best case. In that case, Shared_Prefix = <NUM>. <NUM> (of length 4B) and Size_Of_Offset = <NUM>. Then, the total size of the CSR is: 4B of Shared_Prefix + 1B of Size_Of_Offset + 30x1B of Offset_List[] = 35B. So, here, compared with an existing IPv4 source route, CSR offers a compression of (<NUM>-<NUM>)×<NUM>/<NUM> = <NUM>%. As a second example, assume that in an IPv4 source routed network, the subnet is <NUM>. <NUM>/<NUM>. So, the area can have up to <NUM> network elements and the entire source routed network can be accommodated within a single area. In that case, the total size of the CSR for any source route is: 4B of Shared_Prefix + 1B of Size_Of_Offset + 30x2B of Offset_List[] = 65B. So, here, compared with an existing IPv4 source route, CSR offers a compression of (<NUM>-<NUM>) × <NUM>/<NUM> = <NUM>%. Thus, it is evident that IPv4 source routing gains a significant benefit from use of source route compression.

The compression which may be achieved based on use of a CSR in an IPv6 network may be understood with respect to the following examples. In an existing IPv6 source route, <NUM> hops consume 30x16B = 480B. As a first example, assume that, in an IPv6 source routed network, an area is assigned a subnet IPv6_Prefix/<NUM>. So, the area can have up to <NUM> network elements. Here, further assume that a source route of <NUM> hops traverses only through that single area, which would be the best case. In that case, Shared_Prefix = IPv6_Prefix (of length 16B) and Size_Of_Offset = <NUM>. Then, the total size of the CSR is: 16B of Shared_Prefix + 1B of Size_Of_Offset + 30x1B of Offset_List[] = 47B. So, here, compared with an existing IPv6 source route, CSR offers a compression of (<NUM>-<NUM>)x100/<NUM> = <NUM>%. As a second example, assume that, in an IPv6 source routed network, the subnet is IPv6_Prefix/<NUM>. So, the area can have up to <NUM> network elements and the entire source routed network can be accommodated within a single area. In that case, the total size of CSR for any source route is: 16B of Shared_Prefix + 1B of Size_Of_Offset + 30x2B of Offset_List[] = 77B. So, here, compared with an existing IPv6 source route, CSR offers a compression of (<NUM>-<NUM>) × <NUM>/<NUM> = <NUM>%. Thus, it is evident that IPv6 source routing gains a significant benefit from use of source route compression.

The compression which may be achieved based on use of a CSR in an MPLS network may be understood with respect to the following examples. In an existing MPLS source route, <NUM> hops consumes 30x4B = 120B. In MPLS networks, the global label space can be used for allocation of sub-netted labels to areas (e.g., each area is assigned a block of labels to be assigned to its network elements). The <NUM> bit label value can be segregated into { Shared_Prefix, Offset}. As a first example, assume that, in an MPLS source routed network, an area is assigned a label block with subnet label_prefix/<NUM>. So, the area can have up to <NUM> network elements. Here, further assume that a source route of <NUM> hops traverses only through that single area, which would be the best case. In that case, Shared_Prefix = label_prefix (of length 4B) and Size_Of_Offset = <NUM>. Then, the total size of the CSR is: 4B of Label_Prefix+ 1B of Size_Of_Offset + 30x1B of Offset_List[] = 35B. So, here, compared with an existing MPLS source route, CSR offers a compression of (<NUM>-<NUM>)×<NUM>/<NUM> = <NUM>%. As a second example, assume that, in an MPLS source routed network, an area is assigned a label block with subnet label_prefix/<NUM>. So, the area can have up to <NUM> network elements and the entire source routed network can be accommodated by a single area. In that case, the total size of CSR for any source route is: 4B of Shared_Prefix + 1B of Size_Of_Offset + 30x2B of Offset_List[] = 65B. So, here, compared with an existing MPLS source route, CSR offers a compression of (<NUM>-<NUM>) × <NUM>/<NUM> = <NUM>%.

The compression which may be achieved based on use of a CSR in an Ethernet network may be understood with respect to the following example. In an existing Ethernet source route, <NUM> hops consumes 30x6B = 180B, where each hop is identified by a 6B Media Access Control (MAC) address. In an Ethernet network, it is possible to allocate virtual MAC addresses to the network elements in an area using sub-netting techniques. For example, assume that, in an Ethernet source routed network, an area is assigned a subnet of virtual MAC addresses as MAC_Prefix/<NUM>. So, the area can have up to <NUM> network elements. Here, further assume that a source route of <NUM> hops traverses only through that single area, which is the best case. In that case, Shared_Prefix = MAC_Prefix (of length 6B) and Size_Of_Offset = <NUM>. Then, the total size of the CSR is: 6B of Shared_Prefix + 1B of Size_Of_Offset + <NUM>×1B of Offset_List[] = ~ 37B. So, here, compared with an existing Ethernet source route, CSR offers a compression of (<NUM> - <NUM>)x100/<NUM> = <NUM>%.

It will be appreciated that, although primarily presented herein within the context of using source route compression within the context of source routing of unicast packets, source route compression may be used within the context of source routing of stateless multicast packets where the source route encodes the list of network elements in the multicast tree.

<FIG> depicts an example embodiment of a method for construction of a compressed source route by an ingress node of the source route. In <FIG>, for simplicity, it is assumed that the source route traverses only a single area; however, it will be appreciated that method <NUM> of can be readily extrapolated to a source route spanning multiple areas. The input to the method <NUM> is a source route with the list of hops to be traversed. At block <NUM>, the method <NUM> begins. The input <NUM> to the method <NUM> is a source route with the list of hops to be traversed. Block <NUM> finds the Shared_Prefix for the area associated with the source route, and the method <NUM> then proceeds to block <NUM>. Block <NUM> derives the Size_Of_Offset from the subnet mask associated with the Shared _Prefix, and the method <NUM> then proceeds to block <NUM>. Block <NUM> initializes an empty Offset _List[], and the method <NUM> then proceeds to block <NUM>. Block <NUM> initializes an index variable to index into the hops in the Source Route and Offset_List[], and the method <NUM> then proceeds to <NUM>. Block <NUM> sets the Offset_List[] entry for the index by decrementing the Shared_Prefix from the hop in the Source Route for the same index, and the method <NUM> then proceeds to block <NUM>. Block <NUM> checks if there are more hops in the Source Route to be converted into an entry in Offset_List[]. If there are more hops in the Source Route to be converted into an entry in Offset_List[] then the method <NUM> proceeds to block <NUM>, otherwise the method <NUM> proceeds to block <NUM>. Block <NUM> increments the index by one and the method <NUM> then returns to block <NUM> to repeat the blocks for next hop. Block <NUM> builds the CSRB/CSR from Shared _Prefix, Size_Of_Offset and Offset _List[]. From block <NUM>, the method <NUM> proceeds to block <NUM>. At block <NUM>, the method <NUM> ends.

<FIG> depicts an example embodiment of a method for generation of a hop identifier by a transit node or egress node of the source route based on a compressed source route. In <FIG>, for simplicity, it is assumed that the CSR carries only one CSRB (i.e., the source route spans one area); however, it will be appreciated that method <NUM> of can be readily extrapolated to a CSR carrying multiple CSRBs (i.e., a source route spanning multiple areas). At block <NUM>, the method <NUM> begins. The inputs <NUM> to the method <NUM> are (<NUM>) a CSR encoded packet and (<NUM>) an Index to the offset of the hop in CSR. Block <NUM> parses the CSR from the packet, and the method <NUM> then proceeds to block <NUM>. Block <NUM> parses the offset value in the CSRB at the specified index. This block takes into account the Size_Of_Offset value in the CSRB to parse the value. From block <NUM>, the method <NUM> proceeds to block <NUM>. Block <NUM> generates the hop identifier by adding the offset value to the Shared_Prefix in the CSRB. From block <NUM>, the method <NUM> proceeds to block <NUM>. At block <NUM>, the method <NUM> ends.

Various example embodiments may be configured to support implementation of CSR in IPv4 networks. Various example embodiments may be configured to support implementation of CSR in IPv4 networks in various ways (e.g., based on implementation of CSR as an IPv4 Option, based on implementation of CSR as an IP-Shim Protocol, or the like, as well as various combinations thereof).

Various example embodiments may be configured to support implementation of CSR in IPv4 networks based on implementation of CSR as an IPv4 Option.

IPv4 supports several Options that can be appended to an IPv4 Header, and various example embodiments may be configured to support implementation of CSR in IPv4 networks based on implementation of CSR as an IPv4 Option in an IPv4 Header.

<FIG> depicts an example embodiment of an IPv4 Header including Options. The IPv4 Header <NUM> includes the usual fields of an IPv4 Header and Options. The Options provide for control functions needed or useful in some situations but unnecessary for the most common communications. For example, the Options include provisions for timestamps, security, and special routing. Each Option starts with a <NUM>-octet type field followed by a type-specific encoding. Options are of variable length. Thus, the minimum size of an Option is <NUM>-octet (Only type) if it does not have any type specific data. Maximum size of an Option is limited by maximum permissible value of IP Header Length (IHL) field in the IPV4 Header since the field includes the length of all Options included in the IPv4 Header. The <NUM>-octet Type is viewed as having <NUM> fields: (<NUM>) a <NUM> bit copied flag field, (<NUM>) a <NUM> bit option class field, and (<NUM>) a <NUM> bit option number field. The copied flag indicates whether or not the Option is copied into all fragments on fragmentation (e.g., <NUM> = not copied and <NUM> = copied). The option classes are: (a) <NUM> = control, (b) <NUM> = reserved for future use, (c) <NUM> = debugging and measurement, and (d) <NUM> = reserved for future use. Various example embodiments may be configured to support implementation of CSR in IPv4 networks based on implementation of CSR as an IPv4 Option referred to as the CSR Option. An example format of a CSR Option is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a CSR Option for use in the IPv4 Header of <FIG> to provide a CSR for source route compression. The CSR Option <NUM> includes a Type field, a Length field, and a CSRB list field. The Type field is a <NUM>-octet field that indicates the CSR Option in tuples of COPY, CLASS and NUMBER, which is <NUM>. The Length field is a <NUM>-octet field that indicates the length of this option that includes Type octet, Length octet, octets in the list of CSRBs. The CSRB list field includes a list of P CSRBs. An example format of a CSRB is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a CSRB for use in the CSR Option of <FIG> to provide a CSR for source route compression. The CSRB <NUM> includes a Shared_Prefix field, a Length field, a Size_of_Offset field, a Pointer field, and an Offset_List[n] field. The Shared_Prefix field is a <NUM>-octet field that encodes the IPv4 Shared_Prefix. The Length field is a <NUM>-octet field that indicates length of the CSRB that includes the Shared_Prefix octets, the Length octet, the Size_Of_Offset octets, the Pointer octet, and the octets in Offset_List[]. The Size_of_Offset is a <NUM>-octet field that indicates the size of an entry in the Offset_List[] in units of bytes. The Pointer field is a <NUM>-octet field that indicates the octet in Offset_List[] which begins the next offset to process. The pointer is relative to this Option, and the smallest legal value for the Pointer is <NUM>, which points to the <NUM>th octet, i.e., the area immediately after the Pointer field. The Offset_List[] field is composed of a series of offset entries where each entry is of Size_Of_Offset octets.

The IPv4 CSR Option, as indicated above, supports implementation of CSR in IPv4 networks. When a router routes an IPv4 packet, it checks to see if the CSR Option is present and, if the CSR Option is present, the router parses the offset value beginning at the octet indicated by the Pointer and increments the Pointer by Size_Of_Offset. If the Pointer exceeds the Length, then it means the CSRB is already traversed. Then, if there is a next CSRB in the CSR then the next CSRB is processed. The CSRBs are processed in this manner as the packet traverses the source route path.

It will be appreciated that various example embodiments configured to support implementation of CSR in IPv4 networks based on implementation of CSR as an IPv4 Option may be supported in various other ways.

Various example embodiments may be configured to support implementation of CSR in IPv4 networks based on implementation of CSR as an IP-Shim Protocol.

The Internet Header Length (IHL) field in an IPv4 Header has <NUM> bits, which represents the number of <NUM>-bit words on the IPv4 header, including the variable number of IPv4 Options. As a <NUM>-bit field the maximum value is <NUM> words (15x32 bits, or <NUM> bits = <NUM> bytes). The minimum value of IHL is <NUM>, which indicates a length of 5x32 = <NUM> bits = <NUM> bytes, i.e. the fixed size of IPv4 header excluding the Options. This means that the maximum size of Options can be <NUM>-<NUM>=<NUM> bytes, which limits the size of CSR Option to <NUM> bytes.

In at least some example embodiments, implementation of CSR in IPv4 networks may be based on implementation of CSR as an IP-Shim Protocol. A generic IP-Shim Layer may be inserted between the IPv4 header and the upper-layer/transport protocol header (e.g., Transmission Control Protocol (TCP), User Datagram Protocol (UDP), Internet Control Message Protocol (ICMP), or the like). The placement of the IP-Shim layer in the protocol stack is shown in <FIG>.

<FIG> depicts an example embodiment of a protocol stack for illustrating use of an IP-Shim Layer to provide a Compressed Source Route for source route compression. The protocol stack <NUM> illustrates the IP-Shim disposed between IP and Transport Protocols (e.g., TCP, UDP, ICMP, or the like). The IP-Shim Layer is carried using a new IP Protocol number in the IPv4 Header, which can be reserved from the registry maintained by the International Assigned Number Authority (IANA). For example, the IP-Protocol number for the IP-Shim layer may be <NUM> or any other suitable number. The IP-Shim Layer is defined as being generic such that it can carry any "enhancement" related to IP layer which, in order to support implementation of CSR in IPv4 networks, would include the CSR. The only router that inspects the IP-Shim Header is the router corresponding to the destination address of the packet or any router if a Router Alert Option is set in the IPV4 Header. An example format of an IP-Shim Header for use in the IP-Shim Layer is presented with respect to <FIG>.

<FIG> depicts an example embodiment of an IP-Shim Header for use to provide a Compressed Source Route for source route compression. The IP-Shim Header <NUM> includes a Type field, a Length field, a Next Header field, and a Payload field. The IP-Shim Protocol is defined as generic and may carry different types within it. The Type field is an <NUM>-bit field that carries the type. A new Type may be defined for an IPv4 CSR. For example, the new Type for the IPv4 CSR may be defined as follows: Type <NUM> = IPv4-Compressed-Source-Route (IPv4-CSR). It is noted that, herein, "IPv4-CSR-Shim Header" means the IP-Shim Header Type <NUM>. It will be appreciated that other values may be used for the Type for the IPv4-CSR. The Length field is a <NUM>-bit field that carries the length of the payload in octets, where the octets of the Type, Length, and Next Header fields are excluded. The Next Header field provides the IP Protocol type of the header next to the IP-Shim Header (e.g., TCP, UDP, ICMP, or the like). The Payload field includes the type-specific format. The payload includes one or more CSRBs. An example format of a Payload of the IPv4-CSR-Shim Header is presented with respect to <FIG>.

<FIG> depicts an example embodiment of an IPv4 Compressed Source Route for use as a payload in the IP-Shim Header to provide a Compressed Source Route for source route compression. The IPv4-CSR-Shim Payload <NUM> includes P CSRBs.

The IPv4-CSR-Shim Header, as indicated above, supports implementation of CSR in IPv4 networks. The originator of IPv4-CSR-Shim Header, in addition to inserting the IPv4-CSR-Shim Header, also inserts a Router Alert Option so that every router inspects the IPv4-CSR-Shim Header. When a router routes an IPv4 packet that includes a Router Alert Option, then it checks to see if an IPv4-CSR-Shim Header is present. If an IPv4-CSR-Shim Header is present, the router evaluates each CSRB in the CSR sequentially to find the next CSRB to process. If the Pointer in a CSRB is greater than the Length, then CSRB is considered to be traversed. Then, if there is a next CSRB in the CSR then the next CSRB is processed. The router parses from the CSRB the offset value beginning at the octet indicated by the Pointer and increments the Pointer by Size_Of_Offset.

It will be appreciated that various example embodiments configured to support implementation of CSR in IPv4 networks based on implementation of CSR as an IP-Shim Protocol may be supported in various other ways.

It will be appreciated that various example embodiments configured to support implementation of CSR in IPv4 networks may be supported in various other ways.

Various example embodiments may be configured to support implementation of CSR in IPv6 networks. Various example embodiments may be configured to support implementation of CSR in IPv6 networks in various ways (e.g., based on implementation of CSR as an IPv6 Extension Header, based on implementation of CSR as an IP-Shim Protocol, or the like, as well as various combinations thereof).

Various example embodiments may be configured to support implementation of CSR in IPv6 networks based on implementation of CSR as an IPv6 Extension Header.

IPv6 supports several IPv6 Extension Headers (EHs) that can be appended to an IPv6 Header, and various example embodiments may be configured to support implementation of CSR in IPv6 networks based on implementation of CSR as an IPv6 EH in an IPv6 Header.

<FIG> depicts an example embodiment of an IPv6 Header configured for use to provide a CSR for source route compression. In the IPv6 Header <NUM>, the main IPv6 header remains fixed in size (<NUM> bytes) while customized EHs are added as needed. The EHs provide for control functions needed or useful in some situations but unnecessary for the most common communications. For example, the EHs include provisions for timestamps, security, and special routing. Each EH starts with a <NUM>-octet Next Header field, followed by its own body. The format of the body is dependent on the type of EH. The Next Header field of an EH points to the type of the next EH. So, multiple EHs are chained together by their Next Header fields. The Next Header field on the last EH in the chain indicates the type of the IPv6 payload. Section <NUM> in the IPv6 specification describes an EH referred to as a "Hop-by-Hop Options Header" that can be used to carry optional information that must be examined by each router along the delivery path of the packet. It is identified by the value of <NUM> in the Next Header field of the IPv6 Header or of an EH. This EH is generic and multiple options can be defined within the EH. So, any special directive to be examined by each transit router of an IPv6 packet is defined as an option within the Hop-by-Hop Options Header. An example format of a Hop-by-Hop Options Header is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a Hop-By-Hop Options Header for use in the IPv6 Header of <FIG> to provide a CSR for source route compression. The Hop-by-Hop Options Header <NUM> includes a Next Header field, a Header Extension Length field, and an Options field. The Next Header is an <NUM>-bit selector that identifies the type of header immediately following the Hop-by-Hop Options header. The Header Extension Length field is an <NUM>-bit unsigned integer that indicates the length of the Hop-by-Hop Options header in <NUM>-octet units, not including the first <NUM> octets. The Options field is a variable-length field of length such that the complete Hop-by-Hop Options header is an integer multiple of <NUM> octets long. The Options field includes one or more TLV-encoded options. An example format of a TLV encoded option configured for use in the Hop-By-Hop Options Header of <FIG>, to provide a CSR for source route compression, is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a TLV-encoded option configured for use in the Hop-By-Hop Options Header to provide a CSR for source route compression. The TLV-encoded option <NUM> includes an Option Type field, an Option Data Length field, and an Option Data field. The Option Type field is an <NUM>-bit identifier of the type of option. The Option Data Length field is an <NUM>-bit unsigned integer that indicates the length of the Option Data field of this option, in octets. The Option Data field is a variable-length field that includes Option-Type-specific data.

The Hop-by-Hop Options Header, as indicated above, supports implementation of CSR in IPv6 networks. The sequence of Options within an IPv6 Header will be processed strictly in the order that the Options appear in the header. A receiver will not, for example, scan through the header looking for a particular kind of option and process that option prior to processing all preceding ones.

The Option Type identifiers are internally encoded such that the highest-order two bits specify the action to be taken if the processing IPv6 node does not recognize the Option Type: (a) <NUM> - skip over this option and continue processing the header, (b) <NUM> - discard the packet, (c) <NUM> - discard the packet and, regardless of whether or not the Destination Address of the packet was a multicast address, send an ICMP Parameter Problem, Code <NUM>, message to the Source Address of the packet, pointing to the unrecognized Option Type, and (d) <NUM> - discard the packet and, only if the Destination Address of the packet was not a multicast address, send an ICMP Parameter Problem, Code <NUM>, message to the Source Address of the packet, pointing to the unrecognized Option Type.

The Option Type identifiers are internally encoded such that the third-highest-order bit of the Option Type specifies whether or not the Option Data of that option can change en-route to the final destination of the packet: (a) <NUM> - Option Data does not change en-route and (b) <NUM> - Option Data may change en-route. When an Authentication Header (another type of EH that carries an authentication digest of the packet) is present in the packet, for any option whose data may change en-route, its entire Option Data field will be treated as zero-valued octets when computing or verifying the authenticating digest of the packet.

The three high-order bits described above are to be treated as part of the Option Type, not independent of the Option Type. That is, a particular option is identified by a full <NUM>-bit Option Type, not just the low-order <NUM> bits of an Option Type. The Option Type for the Hop-by-Hop Options Header for source route compression is referred to as a CSR Option. An example format of a CSR Option is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a CSR Option for use in a Hop-By-Hop Options Header to provide a CSR for source route compression. The CSR Option <NUM> includes an Option Type field, an Option Data Length field, a Reserved field, and a CSRB list field.

The Option Type field encodes the option type that indicates it as CSR option. The highest-order <NUM>-bits are encoded with the value <NUM>, which indicates to discard the packet and, regardless of whether or not the Destination Address of the packet was a multicast address, send an ICMP Parameter Problem, Code <NUM>, message to the Source Address of the packet, pointing to the unrecognized Option Type. The <NUM>rd highest order bit is encoded with the value <NUM>, which indicates that the Option Data may change en-route, because the content of CSR changes at each hop/router. The remaining <NUM>-bits are assigned the value <NUM>, which results in the value of Option Type field as 0x32. The Option Data Length field is variable and the value of this field indicates the length of remaining bytes in the CSR option. The CSRB list field includes a list of P CSRBs. An example format of a CSRB is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a CSRB configured for use in the CSR Option of <FIG> to provide a CSR for source route compression. The CSRB <NUM> includes a Shared_Prefix field, a Length field, a Size_of_Offset field, a Pointer field, and an Offset_List[] field. The Shared_Prefix field is a <NUM>-octet field that encodes the IPv6 Shared _Prefix. The Length field is a <NUM>-octet field that indicates length of the CSRB that includes the Shared_Prefix octets, the Length octet, the Size_Of_Offset octets, the Pointer octet, and the octets in Offset_List[]. The Size_of_Offset is a <NUM>-octet field that indicates the size of an entry in the Offset_List[] in units of bytes. The Pointer field is a <NUM>-octet field that indicates the octet in Offset_List[] which begins the next offset to process. The pointer is relative to this Option, and the smallest legal value for the Pointer is <NUM>, which points to the <NUM>th octet, i.e., the area immediately after the Pointer field. The Offset_List[] field is composed of a series of offset entries where each entry is of Size_Of_Offset octets.

The IPv6 CSR Option, as indicated above, supports implementation of CSR in IPv6 networks. When a router routes an IPv6 packet that includes a Hop-by-Hop Options Header, the router checks to see if the CSR Option is present within the Header. If the Pointer in a CSRB is greater than the Length, then CSRB is considered to be traversed. Then, if there is a next CSRB in the CSR then the next CSRB is processed. The router parses from the CSRB the offset value beginning at the octet indicated by the Pointer and increments the Pointer by Size_Of_Offset.

It will be appreciated that various example embodiments configured to support implementation of CSR in IPv6 networks based on implementation of CSR as an IPv6 Extension Header may be supported in various other ways.

Various example embodiments may be configured to support implementation of CSR in IPv6 networks based on implementation of CSR as an IP-Shim Protocol.

In at least some example embodiments, implementation of CSR in IPv6 networks may be based on implementation of CSR as an IP-Shim Protocol. A generic IP-Shim Layer may be inserted between the IPv6 header and the upper-layer/transport protocol header (e.g., TCP, UDP, ICMP, or the like). The protocol stack may be similar to the protocol stack presented in <FIG> for IPv4.

The IP-Shim Layer is carried using a new IP Protocol number in the IPv6 Header, which can be reserved from the registry maintained by the IANA. For example, the IP-Protocol number for the IP-Shim layer may be <NUM> or any other suitable number. The IP-Shim Layer is defined as being generic such that it can carry any "enhancement" related to IP layer which, in order to support implementation of CSR in IPv6 networks, would include the CSR. The only router that inspects the IP-Shim Header is the router corresponding to the destination address of the packet or any router if a Router Alert Option is set in the IPv6 Header. The IP-Shim Header may be similar to the IP-Shim Header presented in <FIG>.

The IP-Shim Header includes a Type field, a Length field, a Next Header field, and a Payload field. The IP-Shim Protocol is defined as generic and may carry different types within it. The Type field is an <NUM>-bit field that carries the type. A new Type may be defined for an IPv6 CSR. For example, the new Type for the IPv4 CSR may be defined as follows: Type <NUM> = IPv6-Compressed-Source-Route (IPv6-CSR). It is noted that, herein, "IPv6-CSR-Shim Header" means the IP-Shim Header Type <NUM>. It will be appreciated that other values may be used for the Type for the IPv6-CSR. The Length field is a <NUM>-bit field that carries the length of the payload in octets, where the octets of the Type, Length, and Next Header fields are excluded. The Next Header field provides the IP Protocol type of the header next to the IP-Shim Header (e.g., TCP, UDP, ICMP, or the like). The Payload field includes the type-specific format. The payload includes P CSRBs. The Payload of the IPv6-CSR-Shim Header may be similar to the Payload presented in <FIG> for IPv4 with each of the CSRBs being similar to the CSRB format presented in <FIG>.

The IPv6-CSR-Shim Header, as indicated above, supports implementation of CSR in IPv6 networks. The originator of IPv6-CSR-Shim Header, in addition to inserting the IPv6-CSR-Shim Header, also inserts a Router Alert Option so that every router inspects the IPv6-CSR-Shim Header. When a router routes an IPv6 packet that includes a Router Alert Option, then it checks to see if an IPv6-CSR-Shim Header is present. If an IPv6-CSR-Shim Header is present, the router evaluates each CSRB in the CSR sequentially to find the next CSRB to process. If the Pointer in a CSRB is greater than the Length, then CSRB is considered to be traversed. Then, if there is a next CSRB in the CSR then the next CSRB is processed. The router parses from the CSRB the offset value beginning at the octet indicated by the Pointer and increments the Pointer by Size_Of_Offset.

It will be appreciated that various example embodiments configured to support implementation of CSR in IPv6 networks based on implementation of CSR as an IP-Shim Protocol may be supported in various other ways.

It will be appreciated that various example embodiments configured to support implementation of CSR in IPv6 networks may be supported in various other ways.

Various example embodiments may be configured to support implementation of CSR in MPLS networks.

In an MPLS-based source routed network (e.g., segment routing using the MPLS data plane), each CSRB is an independent label stack. So, a CSR is composed of one or more consecutive label stacks of one or more CSRBs. An example format of a CSRB is presented with respect to <FIG>.

<FIG> depicts an example embodiment of a CSRB for use to provide a CSR for source route compression in an MPLS-based network. The CSRB <NUM> includes a CSRB-Indicator (CSRB-I), a Base Label, a CSRB Descriptor, and an Offset Label Stack.

The CSRB-I is configured to enable receiving routers to distinguish between CSRB labels and non-CSRB labels. The CSRB-I is inserted into the label stack such that it immediately precedes (where "precedes" means closer to the top of the label stack and farther from the bottom of stack indication) the other labels of the CSRB (i.e., it may or may not be considered to form part of the CSRB). It will be appreciated that, if source route compression is standardized in IETF then a value of CSRB-I may be reserved at the IANA registry on special-purpose labels. It is noted that the EXP and TTL fields in CSRB-I will be set to <NUM> and a receiving router will ignore these fields. The sending router and receiving router of CSRB-I will use the EXP field of the label underneath the CSRB-I for mapping to the appropriate forwarding class. The S-bit in CSRB-I will be set to <NUM> since the other labels of the CSRB follow.

The Base Label, which follows the CSRB-I, is the Base Label (Shared_Prefix) for the offsets included in the CSRB. The EXP and TTL fields will be set to the desired value. The S-bit will be set to <NUM> since other labels of the CSRB follow.

The CSR Descriptor, which follows the Base Label, is a special label that describes the Size_Of_Offset (SOO) and the number of subsequent Offsets in the CSRB. So, this label does not carry a special fixed value. An example format of a CSRB Descriptor is presented with respect to <FIG> depicts an example embodiment of a CSRB Descriptor configured for use in the CSRB of <FIG> to provide a CSR for source route compression in an MPLS-based network. The CSRB Descriptor <NUM> includes a Size_of_Offset (SOO) field, a Number of Offsets (Num Offsets) field, an EXP field, an S-bit, and a TTL field. The SOO field is a <NUM>-bit field that encodes the Size_of_Offset. The SOO field may encode values of: (a) <NUM>, which means that the size of an offset is 1B, so the area associated with the CSRB can address up to <NUM> network elements or (b) <NUM>, which means that the size of an offset is 2B, so the area associated with the CSRB can address up to <NUM>,<NUM> network elements. The Number of Offsets field is a <NUM>-bit field, the value of which indicates the number of subsequent offsets that belong to the CSRB. If the value is 'N' then subsequent N offsets (following the CSRB descriptor), each of size SOO, belong to the CSRB. The EXP field is set to <NUM> by the originator of the CSRB and ignored by the receiver of the CSRB. The S-bit field is set to <NUM>, as the labels describing the offsets follow. The TTL is set to <NUM> and the receiver will ignore the value of this field.

The Offset Label Stack (OLS) is the body of the CSRB that includes the Offset_List[]. The exact structure depends on the value in SOO field in the CSRB descriptor. An example format of the OLS when the SOO value is <NUM> (i.e., 1B Offsets are used) is presented with respect to <FIG> depicts an example embodiment of an OLS configured for use in the CSRB of <FIG> to provide a CSR for source route compression in an MPLS-based network. The OLS <NUM> includes N Offset Labels. Here, the OLS <NUM> may be supported by extending each MPLS label to <NUM>-bits (e.g., by overwriting the EXP, S-bit, and TTL fields, as these latter three fields are not necessary) and then segmenting each of the MPLS labels into four 1B fields. In this manner, each of the extended <NUM>-bit MPLS labels may be used to encode four of the 1B Offset Labels. In the OLS <NUM>, each 1B Offset Label field encodes an offset value for the corresponding hop (network element) in the CSRB. The label for the hop is obtained by adding the offset value to Base Label.

<FIG> depicts an example embodiment of a CSR-encoded MPLS packet configured to provide a CSR for source route compression in an MPLS-based network. In the CSR-encoded MPLS packet <NUM>, since the source route traverses two areas, the CSR includes two CSRB label stacks for the two areas, respectively.

It will be appreciated that various example embodiments configured to support implementation of CSR in MPLS networks may be supported in various other ways.

<FIG> depicts an example embodiment of a method for supporting source routing based on source route compression. It will be appreciated that, although primarily presented herein as being performed serially, at least a portion of the functions of method <NUM> may be performed contemporaneously or in a different order than as presented in <FIG>. At block <NUM>, the method <NUM> begins. At block <NUM>, support communication of a source routed packet over a path from an ingress node to an egress node over a network, wherein the network includes a set of network elements having a respective set of network element identifiers sharing a common prefix, wherein the source routed packet has encoded therein a source route block including the common prefix and an offset list, wherein the offset list includes a set of offset values associated with respective ones of the network elements of the path and configured to be combined with the common prefix to recover the network element identifiers of the respective ones of the network elements of the path. At block <NUM>, the method <NUM> ends.

Various example embodiments for supporting source routing based on source route compression may provide various advantages or potential advantages. For example, various example embodiments for supporting source routing based on source route compression may be generic and, thus, may be configured to support source route compression for various packet switching technologies, such as IPv4, IPv6, MPLS, Ethernet, or the like. For example, various example embodiments for supporting source routing based on source route compression may be generic and, thus, may be configured to support source route compression for various packet switching technologies, such as IPv4, IPv6, MPLS, Ethernet, or the like, with minor changes in the data plane. For example, various example embodiments for supporting source routing based on source route compression may be configured to support significant header compression in Segment Routing (SR) for various packet switching technologies, such as IPv4 (e.g., SR with IPv4 may support header compression of approximately <NUM>% - <NUM>%), IPv6 (e.g., SR with IPv6 may support header compression of approximately <NUM>%-<NUM>%, SR with MPLS may support header compression of approximately <NUM>% - <NUM>%, SR with Ethernet may support header compression of approximately <NUM>%, and so forth). For example, various example embodiments for supporting source routing based on source route compression may be configured to support significant header compression in SR for IPv6 which, in the absence of source route compression as presented herein, may experience significant overhead (e.g., for a 1500B packet the SR IPv6 would impose a <NUM>% overhead penalty which translates to an immediate loss of <NUM> gigabits per second out of a <NUM> Gigabit per second link and for a 512B packet the SR IPv6 would impose a <NUM>% overhead penalty which translates to an immediately loss of <NUM> gigabits per second on a <NUM> Gigabit per second link). Various example embodiments for supporting source routing based on source route compression may provide various other advantages or potential advantages.

<FIG> depicts an example embodiment of a computer suitable for use in performing various functions presented herein.

The computer <NUM> includes a processor <NUM> (e.g., a central processing unit (CPU), a processor, a processor having a set of processor cores, a processor core of a processor, or the like) and a memory <NUM> (e.g., a random access memory, a read only memory, or the like). The processor <NUM> and the memory <NUM> may be communicatively connected. In at least some example embodiments, the computer <NUM> may include at least one processor and at least one memory including computer program code, wherein the at least one memory and the computer program code are configured to, with the at least one processor, cause the computer to perform various functions presented herein.

The computer <NUM> also may include a cooperating element <NUM>. The cooperating element <NUM> may be a hardware device. The cooperating element <NUM> may be a process that can be loaded into the memory <NUM> and executed by the processor <NUM> to implement various functions presented herein (in which case, for example, the cooperating element <NUM> (including associated data structures) can be stored on a non-transitory computer-readable storage medium, such as a storage device or other suitable type of storage element (e.g., a magnetic drive, an optical drive, or the like)).

It will be appreciated that computer <NUM> may represent a general architecture and functionality suitable for implementing functional elements described herein, portions of functional elements described herein, or the like, as well as various combinations thereof. For example, computer <NUM> may provide a general architecture and functionality that is suitable for implementing one or more elements presented herein, such as a node or a portion thereof, a router or a portion thereof, a source routing element or a portion thereof, a controller or a portion thereof, or the like, as well as various combinations thereof.

It will be appreciated that at least some of the functions presented herein may be implemented within hardware, for example, as circuitry that cooperates with the processor to perform various functions. It will be appreciated that at least some of the functions presented herein may be implemented in software (e.g., via implementation of software on one or more processors, for executing on a general purpose computer (e.g., via execution by one or more processors) so as to provide a special purpose computer, and the like) and/or may be implemented in hardware (e.g., using a general purpose computer, one or more application specific integrated circuits, and/or any other hardware equivalents). It will be appreciated that at least some of the functions presented herein may be implemented by an apparatus including at least one processor and at least one memory including computer program code, wherein the at least one memory and the computer program code are configured to, with the at least one processor, cause the apparatus to perform various functions presented herein. It will be appreciated that portions of the functions/elements described herein may be implemented as a computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer such that the methods and/or techniques described herein are invoked or otherwise provided. Instructions for invoking the various methods may be stored in fixed or removable media (e.g., non-transitory computer-readable media), transmitted via a data stream in a broadcast or other signal bearing medium, and/or stored within a memory within a computing device operating according to the instructions.

It will be appreciated that the term "or" as used herein refers to a non-exclusive "or" unless otherwise indicated (e.g., use of "or else" or "or in the alternative").

Claim 1:
An apparatus, comprising:
at least one processor; and at least one memory including computer program code; wherein the at least one memory and the computer program code are configured to, with the at least one processor, cause the apparatus at least to:
support communication of a source routed packet over a path from an ingress node to an egress node over a network, wherein the network includes a set of network elements having a respective set of network element identifiers associated therewith,
wherein the source routed packet has encoded therein a plurality of source route blocks (<NUM>) associated with respective subsets of network elements of the path sharing respective common prefixes based on the respective network element identifiers of the network elements in the respective subsets of network elements of the path,
wherein each of the source route blocks (<NUM>) includes, respectively, the respective common prefix shared by the network elements in the respective subset of network elements of the path and a respective offset list including a respective set of offset values associated with respective ones of the network elements in the respective subset of network elements of the path and configured to be combined with the respective common prefix shared by the network elements in the respective subset of network elements of the path to recover the respective network element identifiers of the respective ones of the network elements in the respective subset of network elements of the path.