Patent Description:
Information-centric networking ("ICN") has been proposed as a network protocol which solves problems inherent in Internet Protocol ("IP")-based networking. Rather than clients communicating with hosts by IP address, under ICN, clients request data by content name; clients send outgoing interest packets representing requests for named content to be fulfilled, and in turn these requests are fulfilled by nodes where the named content is cached. The requested data may be served from any network node where the requested content is cached, and thus communications are decoupled from connections between clients and hosts, and decoupled from data location.

ICN as proposed in theory takes the form of a total replacement of IP-based networking. However, such implementation is currently not feasible at scale since the Internet is foundationally implemented based on IP networking. Therefore, proposals have been set forth for implementing ICN functionality on top of existing IP-based networking infrastructure. Such proposals include, for example, Named Data Networking ("NDN") or Content-Centric Networking ("CCN"), wherein implementation of ICN is, in part, achieved by caching a Pending Interest Table ("PIT") at nodes. A PIT caches information about unfulfilled interest packets so that nodes receiving data packets matching the named content requested by some number of interest packets may return the data packets to the client(s) from which each request originated by an "interest path" delineated by the PITs.

However, the implementation of PIT does not inherently provide a mechanism for returning the data packets to the client(s) in this situation. This remains an open question, subject to additional constraints, such as storage capacity, scalability and latency, as well as the possibility that an interest path is suboptimal. Improved solutions to returning named data packets to the client(s) that requested them are desirable.

<CIT> discloses an approach for routing in an ICN network in which a central device determines a path for routing of an interest packet by an ICN network device.

The invention, as set out in the independent claims, is mainly described with reference to <FIG> and <FIG>. The parts of the description referring to other figures are useful for understanding the background.

This disclosure describes techniques for implementing centralized path computation for routing in hybrid information-centric networking protocols implemented as a virtual network overlay connecting traffic between content consumer client nodes and content producer and storage servers. A method includes receiving an interest packet header from a forwarding router node of a network overlay. The method further includes determining an interest path of the interest packet and one or more destination router nodes of the network overlay. The method further includes computing one or more paths over the network overlay. The method further includes determining an addressing method for the one or more computed paths over the network overlay. The method further includes performing at least one of encoding each computed path in a data packet header, and encoding each computed path as state entries of each router node of the network overlay on each respective path. The method further includes returning the computed path information to the forwarding router node.

Additionally, another method includes a first router node receiving an interest packet from a second router node of a network overlay, the interest packet being operative to request particular named content. The method further includes the first router node determining whether the second router node has caching interest for the requested named content. The method further includes the first router node determining whether the interest packet should be forwarded to more than one other router nodes of the network overlay. The method further includes the first router node inserting information entries into a header of the interest packet indicating the first router node being in an interest path of the interest packet; and forwarding the interest packet to one or more other router nodes of the network overlay.

Additionally, the techniques described herein may be performed by a system and/or device having non-transitory computer-readable media storing computer-executable instructions that, when executed by one or more processors, performs the methods described above.

The methods described herein may be implemented by apparatus comprising means for implementing each of the steps. Moreover, also encompassed herein are methods corresponding to the apparatus steps described and computer programs, computer program products and computer readable media which, when executed by a computer, cause the computer to carry out the steps of the methods described herein.

The hybrid information-centric networking ("hICN") proposal for implementing ICN implements transportation of named data packets by providing an hICN-enabled network having ICN router nodes in addition to IP router nodes. Whereas IP router nodes are physical or virtual network nodes which implement at least conventional routing of IPv4 and IPv6 traffic consisting of data packets encapsulated by, for example, the TCP/IP stack headers, ICN router nodes are physical or virtual network nodes which implement at least routing of traffic encapsulated by, for example, ICN stack headers. As IP headers and ICN stack headers may be non-interoperable, ICN routers according to hICN may further implement routing for both data packets encapsulated by IP headers and data packets encapsulated by ICN headers, and may further implement mapping between IP addresses as specified by IP headers and content name as specified by ICN headers.

Implementations of hICN according to the present disclosure may provide a virtual network overlay over a network underlay. A network underlay is a physical or virtual network having any number of physical and/or virtual nodes forming a network topology. A network underlay may include any number of IP router nodes as described above, which may support suitable IP routing algorithms. According to examples of the present disclosure, IP routing algorithms may include segment routing algorithms, which may include at least one of Segment Routing over Multiprotocol Label Switching ("SR-MPLS") and Segment Routing over IPv6 ("SRv6").

In contrast to conventional routing algorithms such as distance vector or link state, segment routing algorithms may be implemented by a central controller which computes a path for a data packet through a network, then writes path information into the data packet such that router nodes of the network may forward the data packet based on the path information, rather than router nodes of the network incrementally computing the path for the data packet. The central controller which computes the path may be, for example, a Path Computation Element ("PCE").

A PCE as a network element may be a physical or virtual node of a network, a physical or virtual computing system connected to the network, a service running on a physical or virtual computing node of the network, or any other dedicated computing system or service accessible by nodes of the network. A node of the network accessing the PCE may act as a Path Computation Client ("PCC"). Acting independently from PCCs, a PCE may determine, for a data packet originating from a source node and destined for a destination node both in the network, an end-to-end path from the source node to the destination node.

According to implementations of SR-MPLS, path information may be written into the data packet as a stack of labels. According to implementations of SRv6, path information may be written into the data packet as an IPv6 header format, such as a Segment Routing Header ("SRH").

Elements of a PCE may include a physical or virtual computation module operative to compute, by any suitable pathfinding algorithm as known to persons skilled in the art and based on topology of the network layer wherein the PCE resides, an end-to-end path from a source node of a data packet to a destination node of the data packet as described above; a database operative to store and update information regarding topology of the network layer; and a communication module operative to receive information regarding topology of the network layer. Modules of the PCE may be computer-executable instructions stored in one or more physical and/or virtual non-transitory computer-readable media of the PCE and executable by one or more physical and/or virtual processor(s) of the PCE to perform their respective functions.

A database of a PCE may be referred to as, for example, a Traffic Engineering Database ("TED"). A PCE may update a TED upon receiving information such as topology information, resource information such as bandwidth capacity and availability, metrics for traffic engineering, and other types of information from individual network nodes or from other sources of information.

The implementation of ICN routers may establish a virtual network overlay, which providers virtual nodes connected by a virtual network topology over nodes making up the network underlay. ICN routers may be mapped to logical interfaces of router nodes of the physical network, and may not correspond directly to router nodes of the physical network. Thus, a hICN-enabled network may have a network overlay topology different form that of the network underlay topology.

According to proposals for ICN routing, rather than employ algorithmic path computation at a router or at a node such as a PCE, routing of named content may instead be performed based on cached information. One aspect of cache-based routing according to ICN routing implementations is for ICN router nodes to, while forwarding outbound interest packets from a requesting client, cache pointers to the direction in the network topology from which the interest packet was received. A Pending Interest Table ("PIT") may be cached at each ICN router node which receives an interest packet and forwards it onward. A PIT caches state entries pointing to client(s) from which unfulfilled interest packets were forwarded. Additional data structures such as a Forwarding Information Base ("FIB"), which may store interface (port) identifiers for each reachable network node for routing purposes, may also be cached at each ICN router node.

Another aspect of cache-based routing according to ICN routing implementations is that ICN router nodes may be interested or not interested in caching local copies of named content. Criteria for ICN router nodes having caching interest or not having caching interest may be specified according to various criteria according to ICN routing proposals, including, for example, according to names of named content and/or according to local storage capacity or availability of the ICN router nodes. Specifics of such criteria shall need not be reiterated herein. For the purpose of the present disclosure, it should merely be understood that an ICN router node has or does not have caching interest in caching a local copy of any given named content.

Interest packets may ultimately arrive at a content server, which may store or generate named content which satisfies the request of the interest packets. Data packets containing the named content may be returned to the client node over the hICN-enabled network, in which router nodes receiving data packets may match the data packets to requested named content cached at the PIT, and thereby may return the data packets in the direction(s) of the client(s) from which each request originated. State entries in the PITs therefore delineate "interest paths" for routing named content without algorithmic path computation.

In addition to PITs, named content sent by a content server over the hICN-enabled network may be cached at various ICN router nodes thereof to increase availability of the named content and reduce latency in requesting the named content, since retrieving the named content from a cache would be faster than retrieving it from the content server. However, cached named content needs to advertise its availability to client requesting content. One proposed methodology is so-called "breadcrumb" routing, a designation for caching-based routing wherein a data packet routed to a network node causes a "trail," referring to information pointing to nodes from which the data packet was routed and pointing to nodes to which the data packet will be routed, to be cached at the node, so that subsequent interest packets requesting for the same named content may be forwarded by searches following the cached "trails" to arrive at nodes where the named content is ultimately located. Thus, transport of named content over an hICN-enabled network may cause information regarding additional paths to be cached at ICN router nodes, enabling off-path routing for routing requests for named content without algorithmic path computation.

Cached routing information as described herein, including state entries in PITs delineating interest paths and including breadcrumb trails, may be limited to paths actually taken by data packets, while omitting information regarding alternative paths that data packets did not take. <FIG> illustrates an example system-architectural diagram of cached routing information in an hICN-enabled network wherein the cached routing information delineates an interest path which is suboptimal for transport of requested named data. As <FIG> illustrates, over a virtual network overlay <NUM>, the overlay topology may include a first ICN router node <NUM>, a second ICN router node <NUM>, a third ICN router node <NUM>, and a fourth ICN router node <NUM>. Each of the ICN router nodes <NUM> to <NUM> may have a connection to each other, and each may serve as an ingress router for nodes outside the network overlay <NUM><NUM> and may serve as an egress router for data over the network overlay <NUM>. Each such connection is illustrated in solid lines in <FIG>.

The network overlay <NUM> may carry traffic originating from nodes of a network underlay <NUM>, including interest packets and data packets making up named content requested by interest packets. In the network underlay <NUM>, a client node <NUM> may send interest packets requesting certain named content through a connection to the network overlay <NUM>. The network underlay <NUM> also includes a first content server <NUM>, a second content server <NUM>, and a third content server <NUM>, where each content server may store and/or generate various named content, which may or may not include the named content requested by the client node <NUM>. The second ICN router node <NUM> may map to a logical interface of the first content server <NUM>. The third ICN router node <NUM> may map to a logical interface of the second content server <NUM>. The fourth ICN router node <NUM> may map to a logical interface of the third content server <NUM>.

In the example illustrated by <FIG>, the client node <NUM> may connect to the network overlay <NUM> through the first ICN router node <NUM> as an ingress router. The client node <NUM> may send interest packets over the network overlay <NUM> to discover which of the content servers have the named content requested by the interest packets. Interest packets sent by the client node <NUM> may be forwarded by the first ICN router node <NUM> to the other ICN router nodes, though not to all other ICN router nodes.

Persons skilled in the art generally recognize that broadcasting of interest packets (that is, addressing interest packets to all nodes in the network) is undesirable due to likelihood of causing network congestion and disruption, and thus a variety of proposals exist for selective forwarding of interest packets over ICN-enabled networks, which need not be reiterated herein. For the purpose of the present disclosure, it should merely be understood that forwarding of interest packets from an ICN router node is generally selective, without regard as to any particular criteria for such selective forwarding (such as, for example, according to names of named content).

In the example illustrated by <FIG>, the first ICN router node <NUM> forwards an interest packet to the second ICN router node <NUM>, and does not forward the interest packet to the third ICN router node <NUM> or the fourth ICN router node <NUM>. The second ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is not stored or generated at the first content server <NUM> and is not cached at the second ICN router node <NUM>. The second ICN router node <NUM> may decide to cache the requested named content upon its arrival at the second ICN router node <NUM>, or may decide not to cache the requested named content (based on, for example, local cache policy, local resource capacity, and the like). Regardless, the second ICN router node <NUM> then forwards the interest packet to the third ICN router node <NUM>, and does not forward the interest packet to the fourth ICN router node <NUM>. The second ICN router node <NUM> also updates a locally cached PIT to indicate that the interest packet requesting the named content was forwarded from the first ICN router node <NUM> and forwarded to the third ICN router node <NUM>, thus caching interest path information for subsequently arriving data packets.

The third ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is not stored or generated at the second content server <NUM> and is not cached at the third ICN router <NUM>. The third ICN router node <NUM> may decide to cache the requested named content upon its arrival at the third ICN router node <NUM>, or may decide not to cache the requested named content (based on, for example, local cache policy, local resource capacity, and the like). Regardless, the third ICN router node <NUM> then forwards the interest packet to the fourth ICN router node <NUM>. The third ICN router node <NUM> also updates a locally cached PIT to indicate that the interest packet requesting the named content was forwarded from the second ICN router node <NUM> and forwarded to the fourth ICN router node <NUM>.

The fourth ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is stored or is generated at the third content server <NUM>, or is cached at the fourth ICN router node <NUM>. The fourth ICN router node <NUM> returns data packets of the requested named content to the third ICN router node <NUM> from which it received the interest packet along the interest path as cached at each ICN router node, as illustrated in <FIG> by a broken line pointing to the fourth ICN router node <NUM>. As <FIG> illustrates, the network overlay <NUM> provides a connection between the fourth ICN router node <NUM> and the first ICN router node <NUM>. Moreover, in the network underlay <NUM>, the fourth ICN router node <NUM> may be physically nearer the first ICN router node <NUM> than any of the other router nodes are physically to the first ICN router node <NUM>. However, due to the interest path of the interest packet pointing back at each ICN router node towards the previous ICN router node that forwarded the interest packet thereto, the fourth ICN router node <NUM> does not have knowledge that the interest packet initially originated from the first ICN router node <NUM>. Thus, ICN router nodes, by cached routing information, may return requested named content to requesting client nodes by a suboptimal path, as illustrated in <FIG> by a broken line pointing to the client node <NUM>.

Therefore, according to examples of the present disclosure, to further improve routing performance and transport of data packets in hICN-enabled networks, routing of data packets may be performed according to both cached routing information and algorithmic path computation. Path computation may be performed by any suitable computing system acting as a central controller such as, for example, a PCE as utilized in implementing routing methodologies such as MPLS and SRv6. Path computation may be performed based on at least knowledge of the network overlay topology, and may further be performed based on knowledge of the network underlay topology.

Knowledge of the network overlay topology and knowledge of the network underlay topology may be stored in a database, such as a TED, of the PCE. Such information may be advertised by an implementation of Border Gateway Protocol ("BGP"), that is, one of various gateway protocols which cause network topology information to be advertised as, for example, Network Layer Reachability Information ("NLRI"). The advertisement of NLRI may be performed by the PCE peering with individual ICN nodes by Interior Gateway Protocol ("IGP"), or, according to implementations such as Border Gateway Protocol - Link State ("BGP-LS"), may be performed by a router neighboring individual ICN nodes, such as a BGP Speaker, communicating with the PCE. The PCE may receive NLRI through a communication module of the PCE, and may build and update the database using received NLRI.

According to examples of the present disclosure, interest packet headers according to hICN-enabled network implementations may include information regarding ICN router nodes along the interest path of the interest packet. Such information may further include information regarding caching interest of each such ICN router node for various named content. Such information may be carried in a header format, such as a Type-Length-Value ("TLV") format, according to data packet encapsulation as implemented on the hICN-enabled network. TLV may generally refer to any encoding format which encodes a value for a particular type of field, where the type of the field is encoded in a type field, the length of the value is encoded in a length field, and the value is encoded in a value field.

For example, for an hICN-enabled network according to an example implementation of CCN as defined by RFC <NUM>, header TLVs may include hop-by-hop header TLVs, which may encode information regarding intermediate ICN router nodes along the interest path of the interest packet, and may include information regarding caching interest of those intermediate ICN router nodes.

Alternatively, header TLVs may be formatted according to various proposed extension TLVs to IPv6 headers, such as, for example, TLVs defined by the In-Band Operations, Administration, and Maintenance ("iOAM") protocol from CISCO SYSTEMS INC. of San Jose, California. In general, information entries as described herein may be formatted according to any packet encapsulation format which enables entry of information regarding nodes along a path of the packet, and enables such entries to be updated on a per-hop basis by each node that the packet is forwarded over.

According to examples of the present disclosure, an ICN router node may insert information entries into headers of received interest packets prior to forwarding those interest packets. These information entries may include information, in a defined format such as a TLV format as described above, indicating the ICN router node being in the interest path of the interest packet and indicating caching interest of the ICN router node for named content requested by the interest packet.

For example, an ICN router node may insert such information entries into a header of a received interest packet in the case that the ICN router node has caching interest for the requested named content.

Furthermore, an ICN router node may insert such information entries into a header of a received interest packet in the case that the ICN router node will forward the interest packet to more than one other ICN router node.

Such information entries, upon being forwarded as part of an interest packet by an ICN router having the requested named content to a PCE of the hICN-enabled network, may enable the PCE to perform any or all of the following path computations for the interest packet:.

Whether there is an end-to-end path from the ICN router node having the named content requested by the interest packet to a requesting client node which is more optimal than an interest path of the interest packet, and if so, computing the end-to-end path;.

Whether there are end-to-end paths from the ICN router node having the requested named content to other ICN routers having interest for caching the named content which are more optimal than the interest path, not redundant to the end-to-end path to the requesting client node, and not redundant to each other, and if so, computing each such end-to-end-path; and.

Whether unicast addressing or multicast addressing is more optimal for transporting the named content on each end-to-end path computed as described above.

<FIG> illustrates a system-architecture diagram of an example hICN-enabled network <NUM> in which a client node requests named data and a PCE computes paths for the requested named data.

As <FIG> illustrates, over a virtual network overlay, the overlay topology may include a first ICN router node <NUM>, a second ICN router node <NUM>, a third ICN router node <NUM>, a fourth ICN router node <NUM>, a fifth ICN router node <NUM>, and a sixth ICN router node <NUM>. Connections among the ICN router nodes may include, as illustrated, a connection between the first ICN router node <NUM> and the second ICN router node <NUM>, a connection between the second ICN router node <NUM> and the third ICN router node <NUM>, a connection between the second ICN router node <NUM> and the sixth ICN router node <NUM>, a connection between the third ICN router node <NUM> and the fourth ICN router node <NUM>, a connection between the third ICN router node <NUM> and the sixth ICN router node <NUM>, a connection between the fourth ICN router node <NUM> and the fifth ICN router node <NUM>, a connection between the fourth ICN router node <NUM> and the sixth ICN router node <NUM>, and a connection between the fifth ICN router node <NUM> and the sixth ICN router node <NUM>. Each such connection is illustrated in solid lines in <FIG>. Each ICN router node may serve as an ingress router for nodes outside the network overlay and may serve as an egress router for data over the network overlay. Any number of the ICN router nodes may map to respective logical interfaces of content servers which may store and/or generate various named content.

A client node <NUM> may connect to the network overlay through the first ICN router node <NUM> as an ingress router. The client node <NUM> may send interest packets over the network overlay to request certain named content. Interest packets sent by the client node <NUM> may be forwarded by the first ICN router node <NUM> to the other ICN router nodes through available connections in the overlay topology as described above.

In the example illustrated by <FIG>, the first ICN router node <NUM> does not have caching interest for named content requested by the interest packet, and the first ICN router node <NUM> can only forward the interest packet to the second ICN router node <NUM>. Therefore, the first ICN router node <NUM> forwards an interest packet to the second ICN router node <NUM> without inserting information entries in the header of the interest packet.

The second ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is not available at the second ICN router node <NUM> (i.e., not stored or generated at a corresponding content server, not cached locally, and the like). However, the second ICN router node <NUM> has caching interest for the requested named content (due to, for example, local cache policy, local resource capacity or availability, and the like). Therefore, the second ICN router node <NUM> inserts information entries in the header of the interest packet indicating the second ICN router node <NUM> being in an interest path of the interest packet and indicating caching interest of the second ICN router node <NUM> for named content requested by the interest packet. The second ICN router node <NUM> then forwards the interest packet to the third ICN router node <NUM>. The second ICN router node <NUM> also updates a locally cached PIT to indicate that the interest packet requesting the named content was forwarded from the first ICN router node <NUM> and forwarded to the third ICN router node <NUM>, thus caching interest path information for subsequently arriving data packets. However, the second ICN router node <NUM> does not forward the interest packet to the sixth ICN router node <NUM> (due to, for example, bandwidth capacity or availability or other metric, or policy information).

The third ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is not stored or generated at the third ICN router <NUM> (i.e., not stored or generated at a corresponding content server, not cached locally, and the like). The third ICN router <NUM> also does not have caching interest for the requested named content (due to, for example, local cache policy, local resource capacity or availability, and the like). The third ICN router <NUM> also determines that it will not forward the interest packet to multiple receiving nodes (due to, for example, bandwidth capacity or availability, or other metric or policy information). Therefore, the third ICN router node <NUM> does not insert information entries in the header of the interest packet. The third ICN router node <NUM> then forwards the interest packet to the fourth ICN router node <NUM>. The third ICN router node <NUM> also updates a locally cached PIT to indicate that the interest packet requesting the named content was forwarded from the second ICN router node <NUM> and forwarded to the fourth ICN router node <NUM>. However, the third ICN router node <NUM> does not forward the interest packet to the sixth ICN router node <NUM> (due to, for example, bandwidth capacity or availability, or other metric or policy information).

The fourth ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is not available at the fourth ICN router node <NUM> (i.e., not stored or generated at a corresponding content server, not cached locally, and the like). However, the fourth ICN router node <NUM> has caching interest for the requested named content (due to, for example, local cache policy, local resource capacity or availability, and the like). Therefore, the fourth ICN router node <NUM> inserts information entries in the header of the interest packet indicating the fourth ICN router node <NUM> being in an interest path of the interest packet and indicating caching interest of the fourth ICN router node <NUM> for named content requested by the interest packet. The fourth ICN router node <NUM> then forwards the interest packet to the fifth ICN router node <NUM>. The fourth ICN router node <NUM> also updates a locally cached PIT to indicate that the interest packet requesting the named content was forwarded from the third ICN router node <NUM> and forwarded to the fifth ICN router node <NUM>, thus caching interest path information for subsequently arriving data packets. However, the fourth ICN router node <NUM> does not forward the interest packet to the sixth ICN router node <NUM> (due to, for example, bandwidth capacity or availability or other metric, or policy information).

The fifth ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is not available at the fifth ICN router node <NUM> (i.e., not stored or generated at a corresponding content server, not cached locally, and the like). However, the fifth ICN router node <NUM> has caching interest for the requested named content (due to, for example, local cache policy, local resource capacity or availability, and the like). Therefore, the fifth ICN router node <NUM> inserts information entries in the header of the interest packet indicating the fifth ICN router node <NUM> being in an interest path of the interest packet and indicating caching interest of the fifth ICN router node <NUM> for named content requested by the interest packet. The fifth ICN router node <NUM> then forwards the interest packet to the sixth ICN router node <NUM>. The fifth ICN router node <NUM> also updates a locally cached PIT to indicate that the interest packet requesting the named content was forwarded from the fourth ICN router node <NUM> and forwarded to the sixth ICN router node <NUM>, thus caching interest path information for subsequently arriving data packets.

The sixth ICN router node <NUM> receives the interest packet, then determines that named content requested by the interest packet is stored or is generated at a corresponding content server, or is cached at the sixth ICN router node <NUM>. The sixth ICN router node <NUM> forwards the interest packet to a central controller <NUM> of the network overlay, such as a PCE, to request the controller <NUM> to compute one or more paths for the interest packet.

The controller <NUM> may compute an end-to-end path from the sixth ICN router node <NUM> to the first ICN router node <NUM> in the event that the controller <NUM> determines that there is an end-to-end path more optimal than an interest path of the interest packet. In this case, the interest path of the interest packet would cause the named content to be returned over, in sequence, the sixth ICN router node <NUM>; the fifth ICN router node <NUM>; the fourth ICN router node <NUM>; the third ICN router node <NUM>; the second ICN router node <NUM>; and the first ICN router node <NUM>, i.e., the interest packet would arrive in five hops. The controller <NUM> may determine that, on a more optimal path from the sixth ICN router node <NUM> to the first ICN router node <NUM>, the named content would be returned over, in sequence, the sixth ICN router node <NUM>; the second ICN router node <NUM>; and the first ICN router node <NUM>, by knowledge of the connection between the second ICN router node <NUM> and the sixth ICN router node <NUM>, which may be discerned from at least overlay topology information and optionally underlay topology information stored in a database, such as a TED, of the controller <NUM>. By this more optimal path, the named content may be returned to the client node <NUM> by three hops rather than five hops, while also being cached at a node having caching interest.

Additionally, the controller <NUM> may determine from information entries in the header of the interest packet that the second ICN router node <NUM>, the fourth ICN router node <NUM>, and the fifth ICN router node <NUM> each has caching interest in the requested named content. The controller <NUM> may determine that there is no path from the sixth ICN router node <NUM> to the second ICN router node <NUM> more optimal than the path determined above to the first ICN router node <NUM>. The controller <NUM> may further determine that, on a path from the sixth ICN router node <NUM> over the fifth ICN router node <NUM> and the fourth ICN router node <NUM>, the named content would be returned to both the fourth ICN router node <NUM> and the fifth ICN router node <NUM>, both of which have caching interest for the named content. By this more optimal path, the named content may be cached at two nodes having caching interest.

Thus, the controller <NUM> determines, for the named content, a first path to the first ICN router node <NUM> and to the second ICN router node <NUM>, and a second path to the fourth ICN router <NUM> and the fifth ICN router <NUM>. Each of these respective paths is more optimal than the interest path for its respective destinations; more optimal than each of the other paths for its respective destinations; and, together, these paths are not redundant to each other for their respective destinations (i.e., no path encompasses the destinations of any of the other paths). <FIG> illustrates the system-architecture diagram of <FIG> with each of these computed paths shown in broken lines.

Additionally, the controller <NUM> may determine that multicast addressing is more optimal than unicast addressing for transporting the named content over each of the paths computed as described above. Since the named content will be forwarded to two different destinations from the sixth ICN router node <NUM>, multicast addressing for data packets of the named content to each of these two destinations may be more optimal than unicast addressing of data packets to a single destination at a time.

The controller <NUM> may encode each computed path in a header according to a suitable encapsulation format as implemented for the hICN-enabled network. For example, for an hICN-enabled network implementing MPLS, a computed path may be encoded as a stack of labels. For an hICN-enabled network implementing SRv6, a computed path may be encoded as segment information in a SRH header. The encoded information may further include addressing according to an addressing method as described above.

Alternatively, or additionally, the controller <NUM> may encode each computed path as state entries in PITs and FIBs of each ICN router node on each respective path. These state entries may modify interest path information in the existing state entries in the respective PITs and FIBs. For example, since state entries of the PITs and FIBs of the fourth ICN router node <NUM> previously referenced an interest path pointing back to the third ICN router node <NUM>, the controller <NUM> may remove these state entries so that data packets forwarded to the fourth ICN router node <NUM> according to the computed paths are not forwarded on to the third ICN router node <NUM>.

Thus, the controller <NUM> returns the computed path information to the sixth ICN router node <NUM>. The sixth ICN router node <NUM> may forward one copy of the data packets of the requested named content to each next-hop destination from the sixth ICN router node <NUM> as encoded in the computed path information. In this case, the sixth ICN router node <NUM> forwards one copy of the data packets to the second ICN router node <NUM> and another copy of the data packets to the fifth ICN router node <NUM>. The first copy of the data packets will be cached at the second ICN router node <NUM>, and forwarded on by the second ICN router node <NUM> in accordance with path information encoded in the header and/or updated local PIT/FIB routing information to the first ICN router node <NUM>, where the data packets are received by the client node <NUM>. The second copy of the data packets will be cached at the fifth ICN router node <NUM>, and forwarded on by the fifth ICN router node <NUM> in accordance with path information encoded in the header and/or updated local PIT/FIB routing information to the fourth ICN router node <NUM>, where the data packets are cached at the fourth ICN router node <NUM> and not forwarded on further.

<FIG> illustrates a flow diagram of an example method <NUM> for computing paths for named content in an hICN-enabled network based on network topology and interest information. The method may be executing on one or more processors of a central controller of a virtual network overlay logically defined over a network underlay. The controller may include one or more processors and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform the method <NUM>. A controller may be, for example, a PCE consistent with the present disclosure as described above.

At <NUM>, a controller of a network overlay receives an interest packet header from a router node of the network overlay. As illustrated by <FIG>, step <NUM> may be performed after the sixth ICN router node <NUM> receives the interest packet and forwards the interest packet to the controller <NUM>. In examples of the present disclosure where the controller is a PCE, the router node may communicate with the PCE as a PCC according to any suitable protocol for PCE-PCC communications.

The received interest packet may originate from a client node outside the network overlay requesting certain named content which is stored at, generated at, cached at, or otherwise available at the router node to forward to the client node over the network overlay. The received interest packet header may include information entries regarding router nodes along the interest path of the interest packet, and may further include information entries regarding caching interest of each such router node for various named content, in accordance with the present disclosure as described above.

At <NUM>, the controller determines an interest path of the interest packet and one or more destination router nodes of the network overlay. The one or more destination router nodes of the network overlay includes an originating router node of the network overlay from which the interest path originates. The one or more destination router nodes of the network overlay may further include one or more other caching router node(s) of the network overlay having caching interest for named content requested by the interest packet. Each of these determinations is made based on information entries of the interest packet header as described above.

At <NUM>, the controller computes one or more paths over the network overlay, the one or more paths non-redundantly encompassing each of the one or more destination router nodes, and the one or more paths each being no less optimal than the interest path according to at least topology of the network overlay. Non-redundantly encompassing each of the above-mentioned router nodes means that among all of the one or more paths, each of the above-mentioned router nodes is included in only one path and included only one time. A path being no less optimal than the interest path according to at least topology of the network overlay may mean the path includes no more hops than the interest path over nodes of the network overlay. The path may further be more optimal than the interest path according to topology of the network overlay, meaning the path includes fewer hops than the interest path. Optimality may be determined by topology and metrics regarding router nodes of the network overlay, which may be built and updated in manners according to the present disclosure as described above. Moreover, optimality may further be determined by topology and metrics regarding nodes of the network underlay which correspond to the nodes of the network underlay, which may be built and updated in manners according to the present disclosure as described above. For example, proximity of nodes of the network underlay, topological connections of the network underlay, bandwidth capacity and availability of connections of the network underlay, and the like may be considered in conjunction with topology of the network overlay.

At <NUM>, the controller determines an addressing method for the one or more computed paths over the network overlay. An addressing method may be selected from known addressing methods supported by IP networking, ICN networking, and such networking protocols. For example, an addressing method may be selected from unicast addressing, multicast addressing, broadcast addressing, and the like. A most appropriate or optimal addressing method may be selected depending on the number of paths computed, the comparative topologies of those paths, and such factors. For example, if a single path is computed for all destination router nodes, unicast addressing may be more appropriate than multicast addressing; if multiple paths are computed, multicast addressing may be more appropriate than unicast addressing.

At <NUM>, the controller performs at least one of:.

Each type of encoding may be performed according to formats of examples of the present disclosure as described above.

At <NUM>, the controller returns the computed path information to the router node of the network overlay. The router node, and other router nodes of the network overlay, may then route data packets of the requested named content according to the computed path information.

<FIG> illustrates a flow diagram of a non-claimed example method <NUM> for handling interest packet routing by router nodes in an h ICN-enabled network. The method may be executing on one or more processors of a router node of a virtual network overlay logically defined over a network underlay. The controller may include one or more processors and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform the method <NUM>.

At <NUM>, a router node of a network overlay receives an interest packet from another router node of the network overlay. The interest packet may be operative to request particular named content. A header of the interest packet may have a format which supports information entries indicating particular router nodes of the network overlay being in the interest path of the interest packet and indicating caching interest of particular router nodes of the network overlay for the requested named content.

At <NUM>, the router node determines whether the router node has caching interest for the requested named content (based on, for example, local cache policy, local resource capacity, and the like).

At <NUM>, the router node determines whether the interest packet should be forwarded to more than one other router node of the network overlay. As described above, it should merely be understood that forwarding of interest packets from an ICN router node is generally selective, without regard as to any particular criteria for such selective forwarding.

At <NUM>, in the event that the router node has caching interest or the interest packet should be forwarded to more than one other router node, the router node inserts information entries into a header of the interest packet indicating the router node being in an interest path of the interest packet. In the event that the router node has caching interest, the information entries further indicate caching interest of the router node for named content requested by the interest packet.

At <NUM>, the router node forwards the interest packet to one or more other router nodes of the network overlay.

<FIG> is a computing system diagram illustrating a configuration for an hICN-enabled network <NUM> in which a virtual network overlay established over a network underlay connects client nodes with content servers.

Networking resources of an hICN-enabled network <NUM> may be a collection of physical nodes located across geographic areas forming a network underlay <NUM>, over which a virtual network overlay <NUM> is logically defined. The network overlay <NUM> utilizes the resources of the network to implement a data plane topology interconnecting ICN router nodes <NUM>(<NUM>)-<NUM>(N) where N is any integer greater than "<NUM>. " The network overlay <NUM> may be a distributed network through which a user may connect, via a client node <NUM>, to any of router nodes <NUM>(<NUM>)-<NUM>(N) to request named content which may be stored and/or generated at any of the content servers <NUM>(<NUM>)-<NUM>(N) where N is any integer greater than "<NUM>.

The hICN-enabled network <NUM> may provide, via the router node <NUM>(<NUM>)-<NUM>(N) of the data plane topology, access to content servers <NUM>(<NUM>)-<NUM>(N) hosted in the network underlay <NUM>. In some examples, the hICN-enabled network <NUM> may be managed and maintained by a service provider hosting various services accessible on the hICN-enabled network <NUM> and defining various policies which govern use and availability of these services.

As described above, a controller <NUM> may be a physical or virtual node of the network underlay <NUM> or the network overlay <NUM>, a physical or virtual computing system connected to the network underlay <NUM> or the network overlay <NUM>, a service running on a physical or virtual computing node of the network underlay <NUM> or the network overlay <NUM>, or any other dedicated computing system or service accessible by nodes of the network underlay <NUM> and/or the network overlay <NUM>.

Elements of a controller <NUM> may include a physical or virtual computation module <NUM>; a database <NUM>; and a communication module <NUM> each as described above. Modules of the PCE may be computer-executable instructions stored in one or more physical and/or virtual non-transitory computer-readable media of the PCE and executable by one or more physical and/or virtual processor(s) of the PCE to perform their respective functions.

As described above, a database of a PCE may be a TED, which tracks information such as topology information, resource information such as bandwidth capacity and availability, metrics for traffic engineering, and other types of information from individual network nodes or from other sources of information.

In some instances, the network overlay <NUM> may provide computing resources, like VM instances and storage, on a permanent or an as-needed basis. Among other types of functionality, the computing resources provided by the network overlay <NUM> may be utilized to implement the various services described above. The computing resources provided by the virtual network overlay <NUM> can include various types of computing resources, such as data processing resources like VM instances, data storage resources, networking resources, data communication resources, network services, and the like.

Each type of computing resource provided by the network overlay <NUM> can be general-purpose or can be available in a number of specific configurations. For example, data processing resources can be available as physical computers or VM instances in a number of different configurations. The VM instances can be configured to execute applications, including web servers, application servers, media servers, database servers, some or all of the network services described above, and/or other types of programs. Data storage resources can include file storage devices, block storage devices, and the like. The network overlay <NUM> can also be configured to provide other types of computing resources not mentioned specifically herein.

The computing resources provided by the network overlay <NUM> may be enabled in one embodiment by one or more servers located over a physical space to provide a hICN-enabled network as described above. The servers may be housed in spaces to operate computer systems and associated components, typically including redundant and backup power, communications, cooling, and security systems. The servers can also be located in geographically disparate locations.

<FIG> shows an example computer architecture for a router <NUM> capable of executing program components for implementing the functionality described above. The computer architecture shown in <FIG> illustrates a computing device assembled from modular components, and can be utilized to execute any of the software components presented herein. The router <NUM> may, in some examples, run or virtualize an ICN router node as described above.

One or more hardware modules <NUM> installed in a router <NUM> may be a physical card or module to which a multitude of components or devices can be connected by way of a system bus or other electrical communication paths. In one illustrative configuration, one or more central processing units ("CPUs") <NUM> operate in conjunction with a chipset <NUM>. The CPUs <NUM> can be standard programmable processors that perform arithmetic and logical operations necessary for the operation of the hardware module <NUM>.

The chipset <NUM> provides an interface between the CPUs <NUM> and the remainder of the components and devices on the hardware module <NUM>. The chipset <NUM> can provide an interface to a RAM <NUM>, used as the main memory in the hardware module <NUM>. The chipset <NUM> can further provide an interface to a computer-readable storage medium such as a readonly memory ("ROM") <NUM> or non-volatile RAM ("NVRAM") for storing basic routines that help to startup the hardware module <NUM> and to transfer information between the various components and devices. The ROM <NUM> or NVRAM can also store other software components necessary for the operation of the hardware module <NUM> in accordance with the configurations described herein.

The hardware module <NUM> can operate in a networked environment using logical connections to remote computing devices and computer systems through a network, such as the hICN-enabled network <NUM>. The chipset <NUM> can include functionality for providing network connectivity through a NIC <NUM>, such as a gigabit Ethernet adapter. The NIC <NUM> is capable of connecting the hardware module <NUM> to other computing devices over the network <NUM>. It should be appreciated that multiple NICs <NUM> can be present in the hardware module <NUM>, connecting the computer to other types of networks and remote computer systems.

The hardware module <NUM> can be connected to a storage device <NUM> that provides non-volatile storage for the hardware module <NUM>. The storage device <NUM> can store an operating system <NUM>, programs <NUM>, a BIOS <NUM>, and data, which have been described in greater detail herein. The storage device <NUM> can be connected to the hardware module <NUM> through a storage controller <NUM> connected to the chipset <NUM>. The storage device <NUM> can consist of one or more physical storage units. The storage controller <NUM> can interface with the physical storage units through a serial attached SCSI ("SAS") interface, a serial advanced technology attachment ("SATA") interface, a fiber channel ("FC") interface, or other type of interface for physically connecting and transferring data between computers and physical storage units.

The hardware module <NUM> can store data on the storage device <NUM> by transforming the physical state of the physical storage units to reflect the information being stored. The specific transformation of physical state can depend on various factors, in different embodiments of this description. Examples of such factors can include, but are not limited to, the technology used to implement the physical storage units, whether the storage device <NUM> is characterized as primary or secondary storage, and the like.

For example, the hardware module <NUM> can store information to the storage device <NUM> by issuing instructions through the storage controller <NUM> to alter the magnetic characteristics of a particular location within a magnetic disk drive unit, the reflective or refractive characteristics of a particular location in an optical storage unit, or the electrical characteristics of a particular capacitor, transistor, or other discrete component in a solid-state storage unit. Other transformations of physical media are possible without departing from the scope and spirit of the present description, with the foregoing examples provided only to facilitate this description. The hardware module <NUM> can further read information from the storage device <NUM> by detecting the physical states or characteristics of one or more particular locations within the physical storage units.

In addition to the mass storage device <NUM> described above, the hardware module <NUM> can have access to other computer-readable storage media to store and retrieve information, such as program modules, data structures, or other data. It should be appreciated by those skilled in the art that computer-readable storage media is any available media that provides for the non-transitory storage of data and that can be accessed by the hardware module <NUM>. In some examples, the operations performed by a router node of the network overlay, and or any components included therein, may be supported by one or more devices similar to the hardware module <NUM>. Stated otherwise, some or all of the operations performed by a router node of the network overlay, and or any components included therein, may be performed by one or more hardware modules <NUM> operating in a networked, distributed arrangement over one or more logical fabric planes over one or more networks.

By way of example, and not limitation, computer-readable storage media can include volatile and non-volatile, removable and non-removable media implemented in any method or technology. Computer-readable storage media includes, but is not limited to, RAM, ROM, erasable programmable ROM ("EPROM"), electrically-erasable programmable ROM ("EEPROM"), flash memory or other solid-state memory technology, compact disc ROM ("CD-ROM"), digital versatile disk ("DVD"), high definition DVD ("HD-DVD"), BLU-RAY, or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information in a non-transitory fashion.

As mentioned briefly above, the storage device <NUM> can store an operating system <NUM> utilized to control the operation of the hardware module <NUM>. According to one embodiment, the operating system comprises the LINUX or NETBSD operating system and derivatives thereof. According to another embodiment, the operating system comprises the CISCO IOS operating system from CISCO SYSTEMS INC. of San Jose, California. It should be appreciated that other operating systems can also be utilized. The storage device <NUM> can store other system or application programs and data utilized by the hardware module <NUM>.

In one embodiment, the storage device <NUM> or other computer-readable storage media is encoded with computer-executable instructions which, when loaded into a computer, transform the computer from a general-purpose computing system into a special-purpose computer capable of implementing the embodiments described herein. These computer-executable instructions transform the hardware module <NUM> by specifying how the CPUs <NUM> transition between states, as described above. According to one embodiment, the hardware module <NUM> has access to computer-readable storage media storing computer-executable instructions which, when executed by the hardware module <NUM>, perform the various processes described above with regard to <FIG>. The hardware module <NUM> can also include computer-readable storage media having instructions stored thereupon for performing any of the other computer-implemented operations described herein.

<FIG> shows an example computer architecture for a server <NUM> capable of executing program components for implementing the functionality described above. The computer architecture shown in <FIG> illustrates a conventional server computer, workstation, network appliance, or other computing device, and can be utilized to execute any of the software components presented herein. The server <NUM> may, in some examples, correspond to a network node described herein.

The server <NUM> includes a baseboard <NUM>, or "motherboard," which is a printed circuit board to which a multitude of components or devices can be connected by way of a system bus or other electrical communication paths. In one illustrative configuration, one or more central processing units ("CPUs") <NUM> operate in conjunction with a chipset <NUM>. The CPUs <NUM> can be standard programmable processors that perform arithmetic and logical operations necessary for the operation of the server <NUM>.

The chipset <NUM> provides an interface between the CPUs <NUM> and the remainder of the components and devices on the baseboard <NUM>. The chipset <NUM> can provide an interface to a RAM <NUM>, used as the main memory in the server <NUM>. The chipset <NUM> can further provide an interface to a computer-readable storage medium such as a read-only memory ("ROM") <NUM> or non-volatile RAM ("NVRAM") for storing basic routines that help to startup the server <NUM> and to transfer information between the various components and devices. The ROM <NUM> or NVRAM can also store other software components necessary for the operation of the server <NUM> in accordance with the configurations described herein.

The server <NUM> can operate in a networked environment using logical connections to remote computing devices and computer systems through a network, such as the hICN-enabled network <NUM>. The chipset <NUM> can include functionality for providing network connectivity through a NIC <NUM>, such as a gigabit Ethernet adapter. The NIC <NUM> is capable of connecting the server <NUM> to other computing devices over the network <NUM>. It should be appreciated that multiple NICs <NUM> can be present in the server <NUM>, connecting the server node to other types of networks and remote computer systems.

The server <NUM> can be connected to a storage device <NUM> that provides non-volatile storage for the computer. The storage device <NUM> can store an operating system <NUM>, programs <NUM>, and data, which have been described in greater detail herein. The storage device <NUM> can be connected to the server <NUM> through a storage controller <NUM> connected to the chipset <NUM>. The storage device <NUM> can consist of one or more physical storage units. The storage controller <NUM> can interface with the physical storage units through a serial attached SCSI ("SAS") interface, a serial advanced technology attachment ("SATA") interface, a fiber channel ("FC") interface, or other type of interface for physically connecting and transferring data between computers and physical storage units.

The server <NUM> can store data on the storage device <NUM> by transforming the physical state of the physical storage units to reflect the information being stored. The specific transformation of physical state can depend on various factors, in different embodiments of this description. Examples of such factors can include, but are not limited to, the technology used to implement the physical storage units, whether the storage device <NUM> is characterized as primary or secondary storage, and the like.

For example, the server <NUM> can store information to the storage device <NUM> by issuing instructions through the storage controller <NUM> to alter the magnetic characteristics of a particular location within a magnetic disk drive unit, the reflective or refractive characteristics of a particular location in an optical storage unit, or the electrical characteristics of a particular capacitor, transistor, or other discrete component in a solid-state storage unit. Other transformations of physical media are possible without departing from the scope and spirit of the present description, with the foregoing examples provided only to facilitate this description. The server <NUM> can further read information from the storage device <NUM> by detecting the physical states or characteristics of one or more particular locations within the physical storage units.

In addition to the mass storage device <NUM> described above, the server <NUM> can have access to other computer-readable storage media to store and retrieve information, such as program modules, data structures, or other data. It should be appreciated by those skilled in the art that computer-readable storage media is any available media that provides for the non-transitory storage of data and that can be accessed by the server <NUM>. In some examples, the operations performed by the virtual network overlay, and or any components included therein, may be supported by one or more devices similar to server <NUM>. Stated otherwise, some or all of the operations performed by the virtual network overlay, and or any components included therein, may be performed by one or more server <NUM> operating in a cloud-based arrangement.

As mentioned briefly above, the storage device <NUM> can store an operating system <NUM> utilized to control the operation of the server <NUM>. According to one embodiment, the operating system comprises the LINUX operating system. According to another embodiment, the operating system comprises the WINDOWS® SERVER operating system from MICROSOFT Corporation of Redmond, Washington. According to further embodiments, the operating system can comprise the UNIX operating system or one of its variants. It should be appreciated that other operating systems can also be utilized. The storage device <NUM> can store other system or application programs and data utilized by the server <NUM>.

In one embodiment, the storage device <NUM> or other computer-readable storage media is encoded with computer-executable instructions which, when loaded into the server <NUM>, transform the computer from a general-purpose computing system into a special-purpose computer capable of implementing the embodiments described herein. These computer-executable instructions transform the server <NUM> by specifying how the CPUs <NUM> transition between states, as described above. According to one embodiment, the server <NUM> has access to computer-readable storage media storing computer-executable instructions which, when executed by the server <NUM>, perform the various processes described above with regard to <FIG>. The server <NUM> can also include computer-readable storage media having instructions stored thereupon for performing any of the other computer-implemented operations described herein.

The server <NUM> can also include one or more input/output controllers <NUM> for receiving and processing input from a number of input devices, such as a keyboard, a mouse, a touch pad, a touch screen, an electronic stylus, or other type of input device. Similarly, an input/output controller <NUM> can provide output to a display, such as a computer monitor, a flatpanel display, a digital projector, a printer, or other type of output device. It will be appreciated that the server <NUM> might not include all of the components shown in <FIG>, can include other components that are not explicitly shown in <FIG>, or might utilize an architecture completely different than that shown in <FIG>.

The server <NUM> may support a virtualization layer <NUM> executing in the operating system <NUM>. In some examples, the virtualization layer <NUM> may be supported by a hypervisor that provides one or more virtual machines running on the server <NUM> to perform functions described herein. The virtualization layer <NUM> may generally support a virtual resource that performs at least portions of the techniques described herein, such as performing the functions of the virtual network overlay.

In summary, this disclosure describes techniques for implementing centralized path computation for routing in hybrid information-centric networking protocols implemented as a virtual network overlay. A method includes receiving an interest packet header from a forwarding router node of a network overlay. The method further includes determining an interest path of the interest packet and one or more destination router nodes of the network overlay. The method further includes computing one or more paths over the network overlay. The method further includes determining an addressing method for the one or more computed paths over the network overlay. The method further includes performing at least one of encoding each computed path in a data packet header, and encoding each computed path as state entries of each router node of the network overlay on each respective path. The method further includes returning the computed path information to the forwarding router node.

Claim 1:
A method comprising:
receiving an interest packet header from a forwarding router node (<NUM>) of a network overlay (<NUM>), wherein the received interest packet header comprises one or more information entries regarding router nodes (<NUM>-<NUM>) along an interest path of the interest packet;
determining the interest path of the interest packet and one or more destination router nodes of the network overlay based on the information entries;
computing one or more paths over the network overlay that non-redundantly encompass each of the one or more destination router nodes, wherein non-redundantly encompassing each of the above- mentioned router nodes means that among all of the one or more paths, each of the destination router nodes is included in only one path and included only one time;
determining an addressing method for the one or more computed paths over the network overlay;
performing at least one of:
a.) encoding each computed path in a data packet header; and
b.) encoding each computed path as state entries of each router node of the network overlay on each respective path; and
returning the computed path information to the forwarding router node.