NETWORKS

TECHNICAL FIELD

[0001] Embodiments relate to the field of computer networking; and more specifically, to techniques for congestion control in information-centric networks.

BACKGROUND

[0002] Information-Centric Networking (ICN) is a relatively new networking paradigm in which communication is based on named content, unlike traditional host-centric Internet Protocol (IP) networking which is based upon the use of named hosts. A core belief underlying the concept of ICN is that the Internet is commonly used by users who, in most cases, are interested in content and not the location of content. Accordingly, ICN uses content as the primitive and decouples content from its location. Entities can communicate by providing or requesting named data without regard to its location. This facilitates several features such as request aggregation, caching, multi-path forwarding, etc.

[0003] Request aggregation is a key advantage of the ICN approach, which allows requests for a same content item to be aggregated along the path from the requesters to the data source, forming a data distribution tree. Accordingly, data can be distributed in a multicast fashion, resulting in bandwidth savings and as a consequence, improved scalability as each requester does not require a separate unicast data stream to be originated from the source. Rather, a stream for a particular data object can be unique between two consecutive ICN hops.

[0004] ICN has two approaches to route requests towards the content source. One approach is name-based routing (also referred to herein as "coupled routing"), where names of content objects are used as routing identifiers. This approach utilizes a global name-based routing protocol to share routing information of content in the network. A second approach, referred to herein as "decoupled routing," is where names of content objects are decoupled from the routing identifiers. This second approach utilizes a global Name Resolution System (NRS) that routes requests using a two-step process. In the first step, a requested content object name is resolved into a routing identifier. In the second step, the routing identifier is used to route the request towards the content source.

[0005] The decoupled routing approach can also be executed in a hop-by-hop fashion where every intermediate node between a requester and a source sends a separate name resolution query to the NRS, and the NRS constructs the request path in a stepwise manner. This process, which can be referred to as "non-transparent caching", is somewhat similar to how most Content Delivery Network (CDN) providers currently function.

[0006] In ICN, the atomic piece of content is termed an "Object." ICN currently does not impose any restriction on how large an object can be. For example, an object can be a huge 4K movie file, or even a few bytes of sensor data from an Internet-of-Things (IoT) device.

Moreover, an object can also represent a file segment. For example, in the case of live video streaming, each video chunk can be packaged in an ICN object. Depending on the video encoding, each video chunk can be arbitrarily long.

SUMMARY

[0007] According to some embodiments, a method in a first node in an information centric network serving a plurality of clients, wherein the first node is to store popularity values for different content objects, includes receiving, from a client or a second node in the information centric network, a first message comprising the number of interests xj for a content object j. The method also includes updating a first popularity value Pj for content object j by

setting Pj = Pj + xj. The method also includes determining a first condition value QJ, where QJ is a function of Pj . The method also includes determining a second condition value Q ^' j where Q ^' j is a function of P j being a second popularity value for object j which has been determined before receiving the first message comprising the number of interests xj . The method also includes, if the relationship between the first condition value QJ and the second condition value Q ^' j fulfills a predetermined condition, calculating the difference between the first and second popularity value yj = Pj - P'j and also setting the second popularity value equal to the first popularity value P'j = Pj. The method also includes sending a second message comprising the value yj to a third node in the information centric network.

[0008] In some embodiments, the predetermined condition is that the first condition value QJ is within a first predefined value range and the second condition value Q ^' j is within a second predefined value range and wherein the first and second vale ranges are not overlapping each other. In some embodiments, the first condition value QJ is set to QJ = Pj and the second condition value Q ^' j is set to QJ = Pj. In some embodiments, the first condition value QJ is set as a ratio between the first popularity value Pj and the sum of all stored first popularity values for different objects and wherein the second condition value Q ^' j is set as a ratio between the second popularity value PJ and the sum of all stored second popularity values for different objects. In some embodiments, the first condition value QJ is set as a ratio between the first popularity value Pj and the sum of the first popularity value Pj and a third popularity value Pk for content object k and wherein the second condition value Q ^' j is set as a ratio between the second popularity value P'j and the sum of the second popularity value P'j and a corresponding fourth popularity value P'k for content object k. In some embodiments, the first and the third node are routers, the third node being a next hop router. In some embodiments, the first message is received from the client being either an interest request message representing the value xj=l or an unsubscribe message representing the value xj= -1. In some embodiments, the second node is a router and the first message received from the second node and is a popularity update message PUj for the content object j comprising the value xj . In some embodiments, the second node is a name resolution server and the first message received from the name resolution server is a popularity update message PUj for the content object j comprising the value xj.

[0009] According to some embodiments, a first node in an information centric network is to serve a plurality of clients and is further to store popularity values for different content objects. The node comprises a processor coupled to a non-transitory memory storing computer program instructions and the processor is further coupled to a communication interface. When the processor executes the instructions, the first node is caused to receive from a client or a second node in the information centric network a first message comprising the number of interests xj for a content object j . The first node is also caused to update a first popularity value Pj for content object j by setting Pj = Pj + xj . The first node is also caused to determine a first condition value Qj, where Qj is a function of Pj . The first node is also caused to determine a second condition value Q j where Q ^' j is a function of P ^' j being a second popularity value for object j which has been determined before receiving the first message comprising the number of interests xj . The first node is also caused to, if the relationship between the first condition value Qj and the second condition value Q ^' j fulfills a predetermined condition, calculate the difference between the first and second popularity value yj = Pj— P'j and subsequently set the second popularity value equal to the first popularity value P'j = Pj . The first node is also caused to send a second message comprising the value yj to a third node in the information centric network.

[0010] In some embodiments, the predetermined condition is that the first condition value Qj is within a first predefined value range and the second condition value Q ^' j is within a second predefined value range and wherein the first and second vale ranges are not overlapping each other. In some embodiments, the first condition value Qj is determined to be Qj = Pj and the second condition value Q ^' j is determined to be Q'j = Pj. In some embodiments, the first condition value Qj is set as a ratio between the first popularity value Pj and the sum of all stored first popularity values for different objects and wherein the second condition value Q ^' j is set as a ratio between the second popularity value P'j and the sum of all stored second popularity values for different objects. In some embodiments, the first condition value Qj is set as a ratio between the first popularity value Pj and the sum of the first popularity value Pj and a third popularity value Pk for content object k and wherein the second condition value Q j is set as a ratio between the second popularity value P'j and the sum of the second popularity value P'j and a corresponding fourth popularity value P'k for content object k. In some embodiments, the first and the third node are routers, the third node being a next hop router. In some embodiments, the second node is a router. In some embodiments, the second node is a resolution server.

[0011] According to some embodiments, a non-transitory computer-readable storage medium stores instructions which, when executed by a processor of an electronic device, cause the electronic device to perform any of the above methods. According to some embodiments, a device comprises one or more processors and the non-transitory computer-readable storage medium.

[0012] According to some embodiments, a device is to implement a first node in an information centric network comprising a plurality of nodes that serve a plurality of clients. The first node is to store popularity values for different content objects. The device comprises a reception module to receive, from a client or a second node in the information centric network, a first message comprising the number of interests xj for a content object j . The device also comprises a popularity tracking module to update a first popularity value Pj for content object j by setting Pj = Pj + xj. The device also comprises a first condition module to determine a first condition value Qj, where Qj is a function of Pj . The device also comprises a second condition module to determine a second condition value Q j where Q j is a function of P ^' j being a second popularity value for object j which has been determined before receiving the first message comprising the number of interests xj . The device also comprises a calculation module to calculate, if the relationship between the first condition value Qj and the second condition value Q ^' j fulfills a predetermined condition, the difference between the first and second popularity value yj = Pj - P'j and subsequently setting the second popularity value equal to the first popularity value P'j = Pj. The device also comprises a transmission module to send a second message comprising the value yj to a third node in the information centric network.

[0013] According to some embodiments, a system comprises the device of the preceding paragraph and the plurality of nodes of the preceding paragraph.

[0014] According to some embodiments, a method in a resolution server implemented by one or more electronic devices is for providing popularity-based routing in an information centric network (ICN) comprising a plurality of routers. The method includes receiving, at the resolution server from a client, an interest request message identifying a first object that the client seeks to acquire. The method also includes updating, by the resolution server, a popularity value corresponding to the first object. The popularity value indicates how many clients are currently interested in the first object. The method also includes determining, by the resolution server, a next hop router that the client is to use for acquiring the first object. The method also includes transmitting, by the resolution server, a message comprising an identifier of the next hop router. The method also includes determining, by the resolution server based at least in part upon the updated popularity value, whether to transmit one or more popularity update (PU) messages, each including the updated popularity value, to one or more routers of the plurality of routers.

[0015] In some embodiments, the method further includes responsive to determining to transmit the one or more PU messages, transmitting the one or more PU messages to the one or more routers. In some embodiments, the one or more routers includes at least the determined next hop router. In some embodiments, the one or more routers further includes a second router, wherein the second router and the next hop router are on a data path to be used to provide the first object to the client. In some embodiments, said determining whether to transmit the one or more PU messages comprises: determining whether a current condition value, that is based upon the updated popularity value, together with a previous condition value, satisfy one or more defined logical statements. In some embodiments, the method further includes responsive to determining, by the resolution server, that a path through the ICN for the first object is to be changed: transmitting, to a second router on the path, a message indicating that the second router is to unsubscribe from a third router for the first object and further indicating that the second router is to subscribe to a fourth router for the first object; and transmitting, to the third router, a message indicating that the third router is to unsubscribe to the first object. In some

embodiments, further responsive to the determining that the path is to be changed, the method further comprises: receiving, from the fourth router, a message indicating a request for a next hop to be used by the fourth router to reach the first object; and transmitting, to the fourth router, a message comprising an identifier of another router of the plurality of routers or an identifier of a source node that provides the first object.

[0016] According to some embodiments, a non-transitory computer readable storage medium has instructions which, when executed by one or more processors of an electronic device, cause the electronic device to implement a resolution server to perform any of the methods described in the preceding two paragraphs.

[0017] According to some embodiments, an electronic device comprises one or more processors and the non-transitory computer readable storage medium of the preceding paragraph.

[0018] According to some embodiments, an electronic device is to implement a resolution server to provide popularity-based routing in an information centric network (ICN) comprising a plurality of routers. The electronic device includes a reception module to receive, from a client, an interest request message identifying a first object that the client seeks to acquire. The electronic device also includes a popularity tracking module to update a popularity value corresponding to the first object. The popularity value indicates how many clients are currently interested in the first object. The electronic device also includes a next hop determination module to determine a next hop router that the client is to use for acquiring the first object. The electronic device also includes a transmission module to transmit a message comprising an identifier of the next hop router. The electronic device also includes a PU message determination module to determine, based at least in part upon the updated popularity value, whether to transmit one or more popularity update (PU) messages, each including the updated popularity value, to one or more routers of the plurality of routers.

[0019] According to some embodiments, a computer program product has computer program logic to put into effect any of the preceding methods.

[0020] Embodiments described herein can easily enable efficient congestion control in ICN networks to be employed via use of tracked popularity values for requested objects. In some embodiments, upon congestion at an ICN router, the ICN router can have visibility into the popularity of the objects having data packets and make routing/forwarding decisions (e.g., prioritization of processing) based upon this popularity, which can improve the overall quality of experience for the largest number of users. In some embodiments, an NRS can track and use object popularity information to intelligently design paths for object traffic, and/or upon detection of a possible or actual congestion issue, efficiently re-route ones of these paths with full knowledge of how many users would be affected by such a change. Accordingly, some embodiments can provide superior quality of experience for the largest possible number of the clients utilizing an ICN network.

BRIEF DESCRIPTION OF THE DRAWINGS

[0021] The invention may best be understood by referring to the following description and accompanying drawings that are used to illustrate embodiments of the invention. In the drawings:

[0022] Figure 1 is a high-level block diagram illustrating some exemplary routing problems in an ICN-adherent system.

[0023] Figure 2 is a flow diagram illustrating exemplary operations for processing an ICN interest message to enable popularity tracking according to some embodiments.

[0024] Figure 3 is a flow diagram illustrating exemplary operations for processing a PU update message to enable popularity tracking according to some embodiments. [0025] Figure 4 is a high-level block diagram illustrating a weighted fair queuing mechanism that can be used for object popularity-based forwarding according to some embodiments.

[0026] Figure 5A is a high-level block diagram illustrating a decoupled routing ICN system architecture providing priority-based ICN routing according to some embodiments.

[0027] Figure 5B is a high-level block diagram illustrating an example of priority-based ICN routing with decoupled routing according to some embodiments.

[0028] Figure 6 is a flow diagram illustrating operations for handling interest requests in a decoupled routing configuration according to some embodiments.

[0029] Figure 7 is a sequence diagram illustrating operations for data path modification is according to some embodiments.

[0030] Figure 8 is a flow diagram illustrating operations for utilizing and propagating object popularity information according to some embodiments.

[0031] Figure 9 is a flow diagram illustrating operations for centralized object popularity tracking according to some embodiments.

[0032] Figure 10A illustrates a non-limiting example functional block diagram of a server computing device in accordance with some embodiments.

[0033] Figure 10B illustrates a non-limiting example functional block diagram of a network device in accordance with some embodiments.

[0034] Figure 11 A illustrates connectivity between network devices (NDs) within an exemplary network, as well as three exemplary implementations of the NDs, according to some embodiments.

[0035] Figure 1 IB illustrates an exemplary way to implement a special-purpose network device according to some embodiments.

[0036] Figure 11C illustrates various exemplary ways in which virtual network elements (VNEs) may be coupled according to some embodiments.

[0037] Figure 1 ID illustrates a network with a single network element (NE) on each of the NDs, and within this straight forward approach contrasts a traditional distributed approach (commonly used by traditional routers) with a centralized approach for maintaining reachability and forwarding information (also called network control), according to some embodiments.

[0038] Figure 1 IE illustrates the simple case of where each of the NDs implements a single NE, but a centralized control plane has abstracted multiple of the NEs in different NDs into (to represent) a single NE in one of the virtual network(s), according to some embodiments.

[0039] Figure 1 IF illustrates a case where multiple VNEs are implemented on different NDs and are coupled to each other, and where a centralized control plane has abstracted these multiple VNEs such that they appear as a single V E within one of the virtual networks, according to some embodiments.

[0040] Figure 12 illustrates a general purpose control plane device with centralized control plane (CCP) software according to some embodiments.

DETAILED DESCRIPTION

[0041] The following description describes methods, apparatuses, machine-readable media, and systems utilizing techniques for congestion control in information-centric networks. In the following description, numerous specific details such as logic implementations, opcodes, means to specify operands, resource partitioning/sharing/duplication implementations, types and interrelationships of system components, and logic partitioning/integration choices are set forth in order to provide a more thorough understanding of the present invention. It will be

appreciated, however, by one skilled in the art that the invention may be practiced without such specific details. In other instances, control structures, gate level circuits and full software instruction sequences have not been shown in detail in order not to obscure the invention. Those of ordinary skill in the art, with the included descriptions, will be able to implement appropriate functionality without undue experimentation.

[0042] References in the specification to "one embodiment," "an embodiment," "an example embodiment," etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to affect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described.

[0043] Bracketed text and blocks with dashed borders (e.g., large dashes, small dashes, dot- dash, and dots) may be used herein to illustrate optional operations that add additional features to embodiments of the invention. However, such notation should not be taken to mean that these are the only options or optional operations, and/or that blocks with solid borders are not optional in certain embodiments of the invention.

[0044] In the following description and claims, the terms "coupled" and "connected," along with their derivatives, may be used. It should be understood that these terms are not intended as synonyms for each other. "Coupled" is used to indicate that two or more elements, which may or may not be in direct physical or electrical contact with each other, co-operate or interact with each other. "Connected" is used to indicate the establishment of communication between two or more elements that are coupled with each other.

[0045] When discussing ICN, a request message for an object can be referred to as an "interest message," and also the corresponding requestor may be referred to as "subscribing" to the object. Thus, the terms "request message", "interest," and/or "subscribe message" may be used synonymously unless indicated otherwise or unless it is apparent based upon the context of use.

[0046] As described in the Background, request aggregation is one aspect of ICN that can provide a key advantage over traditional IP -based networks as it can provide substantial savings in bandwidth and network forwarding processing. However, request aggregation also introduces additional challenges such as congestion control and Quality of Experience (QoE). When requests are aggregated by an ICN node, the number of requesters behind a particular request is not visible to a next-hop ICN node. This will hinder the next-hop ICN node in determining how to prioritize between incoming requests based on their popularity. Accordingly, in a congestion situation this can result in a severely degraded QoE for users.

[0047] In a current approach adhering to ICN, e.g., Content-Centric Networking (CCN), multiple object interests for a same object are aggregated into one interest at their first interest forwarding routers. Thus, intermediate routers along the path have no idea how many users (clients) are interested in the object, and as a result intermediate routers may treat different objects equally by allocating equal bandwidth to them. In case of congestion, especially when the objects may belong to a live media stream, the existing solution utilized in CCN will likely result in non-optimal global quality of experience (or total throughput).

[0048] For example, Figure 1 is a high-level block diagram illustrating some exemplary routing problems in an ICN-adherent routing system 100. In Figure 1, the four circles on the left-hand side of the Figure having thin borders and diagonal stripes represent clients 111 that are interested in a first object (or "object 1" or "Obj 1"), whereas the single circle with a thick border and horizontal stripes represents a client 112 interested in a second object (or "object 2" or "Obj2"). As is known to those of skill in the art, a client can be an electronic device (or a software module or application executed by an electronic device) such as a server device or end user device - e.g., workstations or personal computers (PCs), laptops, tablets, smartphones, etc.

[0049] As illustrated in Figure 1, all of the clients 111 seeking object 1 may connect to a first router "Rl" 110 as the "first hop" ICN router to indicate their interest in object 1. As is known to those of skill in the art, this connection may not be a direct physical connection between the two, and may or may not pass through other network nodes (e.g., switches, routers) and/or networks. [0050] Due to request aggregation, router Rl 110 will only send one interest message to router R2 120 for object 1, even though four clients 111 are actively seeking this object. Additionally, router Rl 110 will also send one interest message to router R2 120 for object 2 (based upon client 112 sending its interest request to router Rl 110 for object 2).

[0051] Thus, router R2 120 has no idea how many clients are actually interested in each of these objects. Accordingly, when router R2 120 receives object 1 and object 2 from source 1 130 and source 2 140, respectively, it will forward these objects to router Rl 110.

[0052] However, if router R2 120 is suffering from congestion, router R2 120 may treat these objects - object 1 and object - equally and may thus drop the packets of either (or both) objects somewhat indiscriminately, perhaps according to some configured scheme that is not based upon the importance of the objects. Thus, upon suffering congestion, router R2 120 may decide to drop packets of object 1 while allowing packets of object 2 to be forwarded. This results in the overall quality of experience for the four clients 111 being degraded substantially, while the single client 112 may not suffer a degraded experience. However, it is likely more desirable in most scenarios to have router R2 120 prioritize the processing/forwarding of packets of objectl over object2 due to the substantially larger number of clients seeking that object, which would result in the four clients 111 interested in object 1 having a sufficient quality of experience while only one client 1 12 would experience a degraded quality of experience. Under such an approach, the overall QoE of the routing system 100 can be increased, which can be especially important for live streaming applications, where an ICN router should be able to give preferential treatment to objects belong to a more popular live stream than objects belonging to a less popular live stream.

[0053] Accordingly, embodiments disclosed herein can enable improved routing in ICN systems by allowing preferential routing treatment to be given to objects based upon the popularity of these objects. In some embodiments, actors in an ICN routing system (e.g., ICN routers) can propagate a value within the ICN routing system indicating a popularity of an object, e.g., how many clients are interested in the object, which can help the ICN routing system to better allocate network resources, such as when congestion occurs.

[0054] In some embodiments, ICN routing can be decoupled from the name resolution and the popularity information can be propagated in the name resolution system. In some embodiments, name resolution servers can send the popularity information to the corresponding ICN router(s) along the data path. In some embodiments, the name resolution system also controls the data path searching, and can also use the popularity of the objects to find an optimal data path for each object. [0055] Thus, in some embodiments every hop along the path from the requester to the data source can keep track of the number of users behind a particular request - i.e., the request popularity. In a congestion situation, this information can be useful in prioritizing between different requests. Prioritizing between requests, in this context, could mean allocating bandwidth proportional to the request popularity when serving the request.

[0056] Some embodiments utilizing these disclosed techniques can be implemented extremely simply and can be easy to be adopted by the current ICN implementations using small extensions. Some embodiments can also provide, to end users, information describing how popular a particular request (or object) is. For example, in some embodiments providing live video streaming, a user can be provided an indication of how many people are watching the stream at a particular moment, which can be achieved by propagating the popularity rating downstream towards the user along with the content.

[0057] Thus, as disclosed herein, in some embodiments ICN routers propagate and maintain an indication of the number of clients that are interested in a specific object or flow/live stream. The information can then be used, for example, to implement a traffic prioritization scheme when network congestion exists. Embodiments can utilize coupled routing techniques or decoupled routing techniques, as described in turn below.

Coupled Routing

[0058] In a coupled routing scenario, as there are no name resolution servers, ICN clients can send interests (i.e., interest messages) for objects directly to the ICN routers. These ICN routers will then forward the interests according to their respective forwarding tables until an interest message reaches a router that has the object in its cache (or reaches a node that is the source of the object). Then, the object is sent back along the same data path to the client(s).

[0059] Object Popularity Tracking and Propagation

[0060] Figure 2 is a flow diagram illustrating exemplary operations 200 for processing an ICN interest message to enable popularity tracking according to some embodiments. The operations in the flow diagrams will be described with reference to the exemplary embodiments of the other figures. However, it should be understood that the operations of the flow diagrams can be performed by embodiments of the invention other than those discussed with reference to the other figures, and the embodiments of the invention discussed with reference to these other figures can perform operations different than those discussed with reference to the flow diagrams. As one example, the operations 200 may be performed by an ICN router 110/120 of Figure 1. [0061] Given a particular ICN router, it may receive an interest message (e.g., interest message210) either from an ICN client or a neighbor ICN router.

[0062] For clarity and ease of discussion, we first assume that the ICN router does not have object in its local cache (the other case, in which the ICN router does have the object in its cache, will be detailed further later herein). The ICN router will first determine whether the interest already exists in its Pending Interest Table (PIT) at block 220. As is known to those of skill in the art, a PIT includes one or entries, each of which identifies one or more incoming interfaces of a particular interest message, along with an identifier of the object identified by the interest message, so that resulting data packets of the object can be delivered back on the same path via those interfaces toward the requesting client(s).

[0063] In some embodiments, if a PIT entry does already exist for the object (i.e., another client has already expressed an interest in the object), the ICN router can place the sender's identifier (or "ID", such as an interface upon which the interest message was received, etc.) into the entry of that interest in the PIT at block 225.

[0064] Moreover, in some embodiments, the ICN router maintains an additional "popularity" number in each entry of the PIT. This number indicates how many clients are interested in (e.g., have a current interest in) each object. Thus, as indicated by block 230, the corresponding popularity value (or "Pj") in the PIT is increased (e.g., by 1), which may be propagated to the corresponding next hop router as described herein.

[0065] As the popularity of an object (or a live stream) can change dynamically (e.g., additional clients subscribe and/or unsubscribe to an object or a live stream over time), an ICN router may have to update the popularity numbers in its own PIT as well as propagate the updates to the appropriate neighbors. Accordingly, in some embodiments a new type of message for ICN can be utilized, which is referred to herein as a Popularity Update (PU) message, though other names can be used as well.

[0066] Although a PU message can be sent upon receipt, by an ICN router, of every interest message or unsubscribe message, this approach is not optimal and may violate the interest aggregation principle of ICN. Accordingly, in some embodiments, a PU message is sent when the corresponding popularity satisfies some set of one or more conditions (or put another way, the popularity - or a derivation thereof - causes one or more logical statements to evaluate to true), examples of which will be discussed further herein.

[0067] For example, in some embodiments we can define a condition value (or "Qj") that is based upon the popularity value (Pj), and when this condition value (perhaps with other values) satisfies one or more defined logical statements, the PU message will be sent. Similarly, in some embodiments when the condition value does not satisfy the logical statement(s), the PU message will not be sent, despite the ICN router having received a new interest message or unsubscribe message and updated the popularity value Pj. Moreover, in some embodiments a previous condition value (or "Q ^' j") can be tracked that indicates a previous value of the condition value Qj.

[0068] Thus, following the flow of Figure 2, at block 230 the popularity value Pj can be adjusted (e.g., increased by one) and the condition value Qj and previous condition value Q ^' j can be updated. Thus, at decision block 235, if condition value Qj satisfies the defined logical statement(s), the operations 200 further include block 240; otherwise, the flow continues to block 260 and ends.

[0069] In some embodiments, a previous popularity value (or "P ^' j") ^{can a} l ^so be tracked, which indicates the value of the popularity value Pj at the time when a last PU message for that PIT entry was transmitted. Thus, at block 240, due to the defined logical statement(s) being satisfied (at least in part due to the value of condition value Q), the previous popularity value P ^' j can be set to the current popularity value Pj.

[0070] Moreover, in some embodiments, an Update Value (here denoted as xj) can be included in the PU message. The Update Value can be the difference between the current popularity value Pj and the popularity of the time when previous PU message is sent (e.g., previous popularity value P ^' j). Thus, in some embodiments, besides Pj, the ICN router also maintains P ^' j and the Update Value xj, which can be determined as equal to Pj - P ^' j, which is reflected in block 240. Then, at block 245, the PU message can be transmitted to the next hop router for the object, which includes the Update Value xj.

[0071] The usage of the Update Value xj can be shown with a simple example: suppose the ICN router sends a PU message at a time in which the popularity of the interest is 10. Then, assume that in the next 5 seconds, the popularity of the object increases to 100, and the ICN router decides to send a PU message to the next hop router (e.g., due to condition value Q satisfying the defined logical statement(s)). The Update Value xj in the PU message would be 90, as 100 - 10 = 90.

[0072] Notably, it is possible for the update value to be a negative number, such as when clients unsubscribe from an object.

[0073] Turning back to the operations 200 of Figure 2, if after receipt of the interest message 210 it is determined that there is not an entry in the PIT for that interest, the flow may continue to block 250, where an entry is created in the PIT for the interest, and both the current popularity value Pj and previous popularity value P ^' j can be set to one. The flow can continue to block 255, where an interest message for the object is sent to the appropriate next hop router, and at block 260 the flow ends. [0074] We now turn to Figure 3, which is a flow diagram illustrating exemplary operations 300 for processing a PU update message to enable popularity tracking according to some embodiments. When an ICN router receives a PU message with an Update Value x, in some embodiments the ICN router updates the popularity value as P = P + x, determines whether the current popularity of that interest meets the condition, and if yes, sends a PU message with Update Value x to the next hop router. These operations are depicted in Figure 3, where at block 310 a PU message is received for an object that includes an update value xj. At block 315, the current popularity value Pj can be adjusted based upon (e.g., by adding) the received update value xj, and the current and previous condition values Qj and Q ^' j can similarly be updated based upon the values of the current popularity value Pj and the previous popularity value P'j, respectively. At decision block 320, when the current condition value Q does not satisfy the "condition" (e.g., defined logical statement(s)), the operations 300 may terminate at the finish block 335. However, when the current condition value Q does satisfy the "condition" (e.g., defined logical statement(s)), the operations 300 may continue to block 325, where another update value xj (tracked by this ICN router) can be updated, and the previous popularity value P ^' j can also be updated. At block 330, a PU message that includes the update value xj can be sent on to the next hop router, and at block 335 the operations can complete.

[0075] PU message Transmission Conditions

[0076] As described above, there can be one or more defined logical statement(s) defined that are based in part upon a popularity value (e.g., a current popularity value Pj, previous popularity value P ^' j, current condition value Qj, previous condition value Q ^' j) and that allow an ICN router to determine whether to send a PU message.

[0077] In this section, two types of these "conditions" (or logical statements) are shown as examples for the sake of understanding. However, in various embodiments, the conditions can differ in a variety of ways known or derivable by those of skill in the art, and thus these examples are to be understood as being exemplary and not limiting.

[0078] One logical statement ("condition example 1") could be as follows. Multiple

"levels" can be defined based upon a current popularity value - e.g., level 1 is [1, 100), level 2 is [100, 1000), level 3 is [1000, 10000), level 4 is [10000, infinity). Again, the number of levels used and the particular bounds of these levels is merely exemplary, and other numbers of levels and bounds are used in different embodiments. As one example, the current condition value QJ can be defined to be the level corresponding to the current popularity value Pj. Thus, if the current popularity value Pj is 50, then the current condition value QJ can be " 1" (for level one); likewise, if the current popularity value Pj is 1160, then the current condition value QJ can be "3" (for level three). Similarly, the previous condition value Q ^' j can likewise represent the level corresponding to the previous popularity value P ^' j.

[0079] Accordingly, in some embodiments, the ICN router can determine that it is to send a PU message when P and P' belong to different levels - i.e., when the current condition value Qj is not equal to the previous condition value Q ^' j. This test can be part of block 235 of Figure 2, block 320 of Figure 3, etc.

[0080] Another logical statement example ("condition example 2") can be as follows: when there are multiple interests in the PIT for a same object, the "levels" can also be defined as the ratio between the popularity number of the specific object and the sum of the popularities of all the objects in PIT.

[0081] For example, level 1 can be [0, 0.1), level 2 can be [0.1, 0.2), level 3 can be [0.2, 0.3), level 4 can be [0.3, 0.8), level 5 can be [0.8, 1.0]. Again, the particular level number can be represented as the current condition value Qj and the previous condition value Q ^' j, based upon the current popularity value Pj and the previous popularity value P ^' j, respectively.

[0082] Thus, for an object i in the PIT, where Pz denotes its current popularity value, the ICN router may send a PU message for object i when

(i.e., Qj and Q ^' j, respectively) belong to different levels.

[0083] Alternatively, in other embodiments, the ratio can also be calculated based on individual (interest) outgoing interfaces (i.e., links), which also include the incoming interface of the corresponding object packets. For example, if interests of object 1 and object 2 are sent to interface 1 (e.g., "ifal"), while interests of object 3 and object 4 are sent to interface 2 (e.g., "if 2"), then for object 1, the ICN router can send a PU message when

(i.e., Qj and Q ^' j, respectively) belong to different levels.

[0084] Further, some embodiments can utilize multiple logical statements to determine when a PU message is to be transmitted. For example, in some embodiments the above-presented conditions could be combined, e.g., the PU message is sent when either condition example 1 or condition example 2 is met; or the PU message is sent when both condition example 1 and condition example 2 is met, etc. [0085] Forwarding/Receiving objects according to Popularity

[0086] There are many different congestion control mechanisms that can be used to allow for the forwarding/processing of objects according to the popularity values described herein. For the sake of illustration, one example of how to use a popularity value to assist with congestion control is provided, though many other configurations are possible that could be discerned by those of ordinary skill in the art.

[0087] In some embodiments, a weighted fair queuing (WFQ) mechanism can be defined as shown in Figure 4, which is a high-level block diagram illustrating a WFQ mechanism of an ICN router 400 that can be used for object popularity-based forwarding according to some embodiments.

[0088] The illustrated embodiment assumes that a number of "levels" are utilized, such as those described above with regard to the logical statements tested to determine whether a PU message is to be sent by an ICN router - e.g., "level 1", "level 2", and so on.

[0089] Accordingly, in some embodiments, a queue (e.g., queue 425 A) is created for each level being utilized in the system. As indicated above, we say that an object "belongs to" level i if Pz belongs to level i (or, if Qz equals z).

[0090] As data packets for the ICN objects arrive into an ICN router's network interface card (NIC) incoming queue 410, a classifier unit 420 (e.g., hardware circuitry, and/or software logic) can classify these packets according to which level the corresponding objects belong to, and put the packets into the corresponding queue 425A-425d for that level. A WFQ scheduler unit (e.g., hardware circuitry, and/or software logic) can then move the packets from the different level queues 425A-425d into the NIC's outgoing queue 440.

[0091] In some embodiments, different weights are assigned to the queues 425A-425d of different levels. The weight for a specific queue affects the chances that the packets in that queue will be placed into the NIC outgoing queue. For example, the weight for level 1 could be 1; the weight for level 2 could be 2, etc., though in other embodiments the weights can be of different values that are selected based upon the particular usage scenario. In this exemplary configuration, the packets in queue 2 will have twice the chance to be placed into the outgoing queue than the packets in queue 1.

Decoupled Routing

[0092] In the decouple routing case, when an ICN client seeks to acquire some object or subscribe to some live stream, the ICN client first sends an interest request to a Name Resolution System (NRS). In response, the NRS will either provide (to the ICN client) the address of an entity (either a router or the object source) that has the object (to provide to the client), or an address of a first hop ICN router to which the ICN client should send the interest.

[0093] In the current implementation of ICN, the NRS does not keep the popularity number of the objects or live streams. Thus, in such systems, the techniques described above regarding "coupled routing" can be utilized to provide popularity information and allow for popularity- based routing, with a difference is that the ICN client may first get the address of the object source or the first hop ICN router from NRS. However, in some embodiments, the NRS itself may track object popularities.

[0094] NRS Popularity Tracking

[0095] In some embodiments, the popularities of objects can be tracked by the NRS, which can use these popularity values to establish "optimal" (e.g., regarding QoE) paths between the object sources and the ICN clients. One example of the system architecture is shown in Figure 5A, which is a high-level block diagram illustrating a decoupled routing ICN system

architecture 500 providing priority-based ICN routing according to some embodiments. As shown, the NRS 510 can communicate with ICN routers 520A-520D. In the Figure, NRS is shown as a central node; however, it can be implemented in a distributed manner (i.e., with different subcomponents executed at different places, with multiple versions of the NRS 510 at different locations, etc.) and/or in different locations than as shown. For example, in some embodiments the NRS 510 is not external to the routing network (shown as a cloud), though in other embodiments the NRS 510 is external to the routing network.

[0096] Thus, in some embodiments, when an ICN client 530 wants to receive an object, it sends a request to NRS 510, and in response the NRS 510 will update the popularity of that object (similar to as described above as being performed by an ICN router) and send back the address of the first hop ICN router (e.g., router 520A) to the client 530. The client 530 may then transmit an interest message to that ICN router 520A. Assuming that the ICN router 520A is not already able to accommodate the interest in that object, the ICN router 520 A may itself send a request to the NRS 510, and the NRS 510 can send back the address of the next hop router. Assuming that the next hop (from the perspective of router 520A) is router 520D, the router 520A may send the interest message to router 520D, which itself may then send a request to the NRS 510 for a next hop, and so on, until the source 540 is reached. In this way, a path from a client 530 to the source 540 can be established.

[0097] An example is now presented with regard to Figure 5B, which is a high-level block diagram illustrating an example of priority-based ICN routing with decoupled routing according to some embodiments. Figure 5B focuses upon ICN routers 570A-570E, as well as a source node 575. In this case, a client (not shown) wants object 1 and sends a request to NRS (not shown). The RS returns to the client the address of router Rl . The client can send an interest message to router Rl for object 1, and in response router Rl will send a request to the NRS, which will send back the address of router R3 as the next hop. With this information, router Rl sends the interest message to router R3, and upon receipt, router R3 similarly sends a request to the NRS, which returns the address of router R4 as the next hop. Then, router R3 sends the interest message to router R4, triggering router R4 to send a request to the NRS to get back the address of the source (shown as si, 2).

[0098] However, in some embodiments, upon initially configuring a path for an interest to be served (e.g., at the NRS 510 upon receipt of a first request from a client for a path to obtain an object), the NRS 510 may proactively configure the routers on that path by sending messages to each router on the path (and not, as described above, only in response to each router's request). This approach can eliminate the time needed for each router to send a request upon its receipt of an interest message, and the time needed for the NRS to send responses back to each requesting ICN router, before the path is established.

[0099] In some embodiments, the NRS can send PU messages to the ICN routers, and the messages can be sent according some conditions, e.g. "condition example 1" and/or "condition example 2" presented above. The ICN routers can use the popularities to deal with congestion as described above. One exemplary set of operations 600 for an NRS to handle interest requests is shown in Figure 6.

[00100] At block 605, an interest request message for object "j" is received. At decision block 610, a determination is made as to whether the interest request message is from a client. If not - e.g., it is from an ICN router - at block 640 the operations 600 include determining a next hop router (from the perspective of the requesting router) and sending an identifier of the next hop (e.g., a network address) to the requesting router, and finishing at block 645.

[00101] However, if it is determined at decision block 610 that the interest request message is from a client, the flow can continue to block 615, where the current popularity value of the object is adjusted (e.g., incremented by one), and optionally the current condition value OJ and previous condition value Q ^' j are also determined.

[00102] At block 620, a next hop is determined (e.g., as part of a path computation process), and an identifier of the next hop router (e.g., a network address, name, or other identifier) is sent to the client (allowing the client to then send an interest message using that identifier toward that router). At decision block 625, it is determined whether the one or more logical statements are met (or, whether OJ satisfies the condition(s), as described above). If not, a PU message does not need to be send and the flow can finish at block 645. If the one or more logical statements are met, then the flow can continue to block 630, where the Update Value xj can be updated, as well as the previous popularity value P ^' j. At block 635, the flow includes sending a PU message (with the updated Update Value xj, to one or more of the routers in the system - e.g., one or more of the routers along the path, all routers, etc., before the flow finishes at block 645.

[00103] To determine the "best" first hop router for a particular ICN client, there can be a number of different techniques utilized in various embodiments. Two exemplary techniques are presented here, though other embodiments use other techniques that can be crafted by those of ordinary skill in the art with the information disclosed herein. For example, in some

embodiments a nearest router (to the client, in terms of hops, geography, etc.) can be selected. As another example, in some embodiments, there may be specific ICN routers configured as being "first hop routers" for particular objects, and thus, a particular object of a client's request can be used to identify one of these configured first hop routers.

[00104] NRS Data Path Modifications

[00105] In some embodiments, the NRS can cause ICN routers to change the data path for an object. For example, turning back to Figure 5B, suppose there are 100 clients asking for object 1 that connect to router Rl, but only 1 client asking for object 2 that connects to router R2. We also assume that the NRS sets up the path for object 1 as <R1, R3, R4, Sl,2> (meaning that the path is from router Rl to router R3 to router R4 to the source Sl,2), and sets up the path for object 2 as <R2, R3, R5, Sl,2>. Then, suppose at a later point in time, one thousand (1000) clients seeking object 3 connect to router R4.

[00106] In this case, object 1 has to "compete" with object 3 at router R4, and the traffic of object 1 may receive less bandwidth than that of object 3, since it has less number of clients. In some embodiments, the NRS can provide a better solution by changing the path of object 1 to <R1, R3, R5, Sl,2> in order to remove object 1 from transiting through router R4 and thus eliminate the resource contention arising due to the traffic of objects 1 and 3.

[00107] To do this, in some embodiments the NRS can instruct router R3 to "unsubscribe" object 1 to router R4, and "subscribe" to router R5. Similarly, the NRS can instruct router R5 to subscribe to Sl,2. An exemplary sequence diagram for such a data path modification is shown in Figure 7.

[00108] Figure 7 shows the NRS 510, router R3 570C, router R4 570D, router R5 570E, and source Sl,2 575. In this diagram, we continue the preceding example (of Figure 5B) where the NRS 510 changes the path of object 1 from <R1, R3, R4, Sl,2> to <R1, R3, R5, Sl,2> in order to remove the data of object 1 from transiting through router R4 570D.

[00109] In this case, the NRS 510 can send a message 705 instructing R3 570C to unsubscribe from router R4 570D and subscribe to router R5 570E. Router R3 570C can then send a message 710 to router R4 570D seeking to unsubscribe from object 1, and send a message 715 to router R5 570E to subscribe to object 1.

[00110] The RS 510 can also send a message 720 to router R4 570D, instructing it to unsubscribe from object 1. In response, router R4 570D can send a message 725 to source Sl,2 575 indicating that it is unsubscribing from object 1.

[00111] Responsive to the "subscribe" message 715 sent by router R3 570C, the router R5 570E can then send a request message 730 for object 1 to the NRS 510 seeking next hop information. In response, the NRS 510 can send a message 735 including an identifier of the next hop (e.g., an address of source SI, 2 575). The router R5 570E can then send a subscribe message 740 for object 1 to source Sl,2 575. At this point, the change has been effected and the new path is operational.

[00112] Of course, the precise order of operations in this Figure is exemplary and can occur in different orders, with different messages, etc. For example, messages 720 and 725 can be sent substantially simultaneously with (or even before) messages 710 and 715. Moreover, in some embodiments, in some embodiments messages 730, 735, and 740 might be skipped in cases where router R5 570E may have already subscribed to object 1 with source Sl,2 575 (e.g., there could be some interest from other routers). Thus, the particular messages and ordering is intended to be merely exemplary of one particular set of operations in one particular setting, and other operations and settings can be utilized in various embodiments.

[00113] In some embodiments, computing data paths through a network may involve heavy computation, as it can involve solving a non-linear optimization problem. Therefore, in some embodiments a data path is not computed every single time when an interest request is received by NRS. Instead, a path may be computed periodically, or when some other condition is met, e.g., condition example 1 as disclosed above.

[00114] Various techniques known to those of skill in the art are known for computing "optimal data paths" and are not disclosed herein. However, as one example, in some cases when the problem input space is sufficiently big, a simple (or "approximate") algorithm can be utilized. For example, the following greedy algorithm can be of use in such scenarios: for a specific object, the next hop router with the smallest aggregated client number is chosen as the next hop router in the data path. For instance, with regard to router R3 in Figure 5B, before choosing the next hop router for object 1, the aggregated client number in router R4 is 1000, whereas the aggregated client number of router R5 is 1. Therefore, using the greedy algorithm, router R5 can be chosen as the next hop router of router R3 for object 1. The greedy algorithm can also be used when the NRS needs to determine a best next hop router upon receiving a request from an ICN router. [00115] Figure 8 is a flow diagram illustrating operations 800 for utilizing and propagating object popularity information according to some embodiments. The operations 800 of this flow can be performed, for example, by an ICN router as described herein.

[00116] The operations 800 include, at block 805, receiving, from a client or a second node in an information centric network, a first message comprising the number of interests xj for a content object j.

[00117] The operations 800 further include, at block 810, updating a first popularity value Pj for content object j by setting Pj = Pj + xj. The operations 800 further include, at block 815, determining a first condition value Qj, where Qj is a function of Pj .

[00118] The operations 800 further include, at block 820, determining a second condition value Q ^' j where Q ^' j is a function of P ^' j being a second popularity value for object j which has been determined before receiving the first message comprising the number of interests xj.

[00119] The operations 800 further include, at block 825, if the relationship between the first condition value Qj and the second condition value Q ^' j fulfills a predetermined condition, calculating the difference between the first and second popularity value yj = Pj - P'j and subsequently setting the second popularity value equal to the first popularity value P'j = Pj .

[00120] The operations 800 further include, at block 830, sending a second message comprising the value yj to a third node in the information centric network.

[00121] Figure 9 is a flow diagram illustrating operations 900 for centralized object popularity tracking according to some embodiments. The operations 900 of this flow can be performed, for example, by an RS 510 (or "resolution server") as described herein.

[00122] The operations 900 include, at block 905, receiving, from a client, an interest request message identifying a first object that the client seeks to acquire.

[00123] The operations 900 further include, at block 910, updating a popularity value corresponding to the first object, wherein the popularity value indicates how many clients are currently interested in the first object. The operations 900 further include, at block 915, determining a next hop router that the client is to use for acquiring the first object.

[00124] The operations 900 further include, at block 920, transmitting a message comprising an identifier of the next hop router. The operations 900 further include, at block 925, determining, based at least in part upon the updated popularity value, whether to transmit one or more popularity update (PU) messages, each including the updated popularity value, to one or more routers of the plurality of routers.

[00125] Figure 10A illustrates a non-limiting example functional block diagram of a server computing device in accordance with some embodiments, and Figure 10B illustrates a non- limiting example functional block diagram of a network device in accordance with some embodiments.

[00126] It is not strictly necessary that each of these modules be implemented as physically separate units. Some or all modules may be combined in a physical unit. Also, the modules need not be implemented strictly in hardware. It is envisioned that the units may be implemented through a combination of hardware and software. For example, either electronic device 1000 and 1050 may include one or more central processing units executing program instructions stored in a non-transitory storage medium or in firmware to perform the functions of the modules.

[00127] With regard to Figure 10A, the electronic device 1000 can implement a resolution server module 1045, which can include a reception module 1005, a popularity tracking module 1010, a next hop determination module 1015, a transmission module 1020, and/or a PU message determination module 1025.

[00128] The reception module 1005 can be adapted for receiving, from a client, an interest request message identifying a first object that the client seeks to acquire.

[00129] The popularity tracking module 1010 can be adapted for updating a popularity value corresponding to the first object, wherein the popularity value indicates how many clients are currently interested in the first object.

[00130] The next hop determination module 1015 can be adapted for determining a next hop router that the client is to use for acquiring the first object.

[00131] The transmission module 1020 can be adapted for transmitting a message comprising an identifier of the next hop router.

[00132] The PU message determination module 1025 can be adapted for determining, based at least in part upon the updated popularity value, whether to transmit one or more popularity update (PU) messages, each including the updated popularity value, to one or more routers of the plurality of routers.

[00133] With regard to Figure 10B, the electronic device 1050 can implement a router module 1085, which can include a reception module 1055, a popularity tracking module 1060, a first condition module 1065, a second condition module 1070, a calculation module 1075, and/or a transmission module 1080.

[00134] The reception module 1055 can be adapted for receiving, from a client or a second node in an information centric network, a first message comprising the number of interests xj for a content object j .

[00135] The popularity tracking module 1060 can be adapted for updating a first popularity value Pj for content object j by setting Pj = Pj + xj . [00136] The first condition module 1065 can be adapted for determining a first condition value Qj, where Qj is a function of Pj .

[00137] The second condition module 1070 can be adapted for determining a second condition value Q j where Q ^' j is a function of P ^' j being a second popularity value for object j which has been determined before receiving the first message comprising the number of interests xj .

[00138] The calculation module 1075 can be adapted for calculating, when the relationship between the first condition value Qj and the second condition value Q ^' j fulfills a predetermined condition, the difference between the first and second popularity value yj = Pj - P'j and subsequently setting the second popularity value equal to the first popularity value P'j = Pj .

[00139] The transmission module 1080 can be adapted for sending a second message comprising the value yj to a third node in the information centric network.

[00140] An electronic device stores and transmits (internally and/or with other electronic devices over a network) code (which is composed of software instructions and which is sometimes referred to as computer program code or a computer program) and/or data using machine-readable media (also called computer-readable media), such as machine-readable storage media (e.g., magnetic disks, optical disks, read only memory (ROM), flash memory devices, phase change memory) and machine-readable transmission media (also called a carrier) (e.g., electrical, optical, radio, acoustical or other form of propagated signals - such as carrier waves, infrared signals). Thus, an electronic device (e.g., a computer) includes hardware and software, such as a set of one or more processors coupled to one or more machine-readable storage media to store code for execution on the set of processors and/or to store data. For instance, an electronic device may include non- volatile memory containing the code since the non-volatile memory can persist code/data even when the electronic device is turned off (when power is removed), and while the electronic device is turned on that part of the code that is to be executed by the processor(s) of that electronic device is typically copied from the slower nonvolatile memory into volatile memory (e.g., dynamic random access memory (DRAM), static random access memory (SRAM)) of that electronic device. Typical electronic devices also include a set or one or more physical network interface(s) to establish network connections (to transmit and/or receive code and/or data using propagating signals) with other electronic devices. One or more parts of an embodiment of the invention may be implemented using different combinations of software, firmware, and/or hardware.

[00141] A network device ( D) is an electronic device that communicatively interconnects other electronic devices on the network (e.g., other network devices, end-user devices). Some network devices are "multiple services network devices" that provide support for multiple networking functions (e.g., routing, bridging, switching, Layer 2 aggregation, session border control, Quality of Service, and/or subscriber management), and/or provide support for multiple application services (e.g., data, voice, and video).

[00142] Figure 11 A illustrates connectivity between network devices (NDs) within an exemplary network, as well as three exemplary implementations of the NDs, according to some embodiments. Figure 11 A shows NDs 1 lOOA-1100H, and their connectivity by way of lines between 1100 A- 1100B, 1100B- 1100C, 1100C- 1100D, 1100D- 1100E, 1100E- 11 OOF, 1100F- 1100G, and 1 lOOA-1100G, as well as between 1100H and each of 1100 A, 1 lOOC, HOOD, and 1100G. These NDs are physical devices, and the connectivity between these NDs can be wireless or wired (often referred to as a link). An additional line extending from NDs 1100 A, 1100E, and HOOF illustrates that these NDs act as ingress and egress points for the network (and thus, these NDs are sometimes referred to as edge NDs; while the other NDs may be called core NDs).

[00143] Two of the exemplary ND implementations in Figure 11 A are: 1) a special-purpose network device 1102 that uses custom application-specific integrated-circuits (ASICs) and a special-purpose operating system (OS); and 2) a general purpose network device 1104 that uses common off-the-shelf (COTS) processors and a standard OS.

[00144] The special-purpose network device 1102 includes networking hardware 1110 comprising compute resource(s) 1112 (which typically include a set of one or more processors), forwarding resource(s) 1114 (which typically include one or more ASICs and/or network processors), and physical network interfaces (NIs) 1116 (sometimes called physical ports), as well as non-transitory machine readable storage media 1118 having stored therein networking software 1120 and router code 1190 A that can be used to implement an ICN router as described herein. A physical NI is hardware in a ND through which a network connection (e.g., wirelessly through a wireless network interface controller (WNIC) or through plugging in a cable to a physical port connected to a network interface controller (NIC)) is made, such as those shown by the connectivity between NDs 1 lOOA-1100H. During operation, the networking

software 1120 may be executed by the networking hardware 1110 to instantiate a set of one or more networking software instance(s) 1122. Each of the networking software instance(s) 1122, and that part of the networking hardware 1110 that executes that network software instance (be it hardware dedicated to that networking software instance and/or time slices of hardware temporally shared by that networking software instance with others of the networking software instance(s) 1122), form a separate virtual network element 1130A-113 OR. Each of the virtual network element(s) (VNEs) 1130A-113 OR includes a control communication and configuration module 1132A-1132R (sometimes referred to as a local control module or control

communication module) and forwarding table(s) 1134A-1134R, such that a given virtual network element (e.g., 1130A) includes the control communication and configuration module (e.g., 1132A), a set of one or more forwarding table(s) (e.g., 1134A), and that portion of the networking hardware 1110 that executes the virtual network element (e.g., 1130A).

[00145] The special-purpose network device 1102 is often physically and/or logically considered to include: 1) a ND control plane 1124 (sometimes referred to as a control plane) comprising the compute resource(s) 1112 that execute the control communication and configuration module(s) 1132A-1132R; and 2) a ND forwarding plane 1126 (sometimes referred to as a forwarding plane, a data plane, or a media plane) comprising the forwarding

resource(s) 1114 that utilize the forwarding table(s) 1134A-1134R and the physical NIs 1116. By way of example, where the ND is a router (or is implementing routing functionality), the ND control plane 1124 (the compute resource(s) 1112 executing the control communication and configuration module(s) 1132A-1132R) is typically responsible for participating in controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) and storing that routing information in the forwarding table(s) 1134A-1134R, and the ND forwarding plane 1126 is responsible for receiving that data on the physical NIs 1116 and forwarding that data out the appropriate ones of the physical NIs 1116 based on the forwarding table(s) 1134A-1134R.

[00146] Figure 1 IB illustrates an exemplary way to implement the special-purpose network device 1102 according to some embodiments. Figure 1 IB shows a special-purpose network device including cards 1138 (typically hot pluggable). While in some embodiments the cards 1138 are of two types (one or more that operate as the ND forwarding plane 1126

(sometimes called line cards), and one or more that operate to implement the ND control plane 1124 (sometimes called control cards)), alternative embodiments may combine functionality onto a single card and/or include additional card types (e.g., one additional type of card is called a service card, resource card, or multi-application card). A service card can provide specialized processing (e.g., Layer 4 to Layer 7 services (e.g., firewall, Internet Protocol Security (IPsec), Secure Sockets Layer (SSL) / Transport Layer Security (TLS), Intrusion Detection System (IDS), peer-to-peer (P2P), Voice over IP (VoIP) Session Border Controller, Mobile Wireless Gateways (Gateway General Packet Radio Service (GPRS) Support Node (GGSN), Evolved Packet Core (EPC) Gateway)). By way of example, a service card may be used to terminate IPsec tunnels and execute the attendant authentication and encryption algorithms. These cards are coupled together through one or more interconnect mechanisms illustrated as backplane 1136 (e.g., a first full mesh coupling the line cards and a second full mesh coupling all of the cards). [00147] Returning to Figure 11 A, the general purpose network device 1104 includes hardware 1140 comprising a set of one or more processor(s) 1142 (which are often COTS processors) and network interface controller(s) 1144 (NICs; also known as network interface cards) (which include physical NIs 1146), as well as non-transitory machine readable storage media 1148 having stored therein software 1150 including router code 1190B that can be used to implement an ICN router as described herein. During operation, the processor(s) 1142 execute the software 1150 to instantiate one or more sets of one or more applications 1164A-1164R. While one embodiment does not implement virtualization, alternative embodiments may use different forms of virtualization. For example, in one such alternative embodiment the virtualization layer 1154 represents the kernel of an operating system (or a shim executing on a base operating system) that allows for the creation of multiple instances 1162A-1162R called software containers that may each be used to execute one (or more) of the sets of

applications 1164A-1164R; where the multiple software containers (also called virtualization engines, virtual private servers, or jails) are user spaces (typically a virtual memory space) that are separate from each other and separate from the kernel space in which the operating system is run; and where the set of applications running in a given user space, unless explicitly allowed, cannot access the memory of the other processes. In another such alternative embodiment the virtualization layer 1154 represents a hypervisor (sometimes referred to as a virtual machine monitor (VMM)) or a hypervisor executing on top of a host operating system, and each of the sets of applications 1164A-1164R is run on top of a guest operating system within an instance 1162A-1162R called a virtual machine (which may in some cases be considered a tightly isolated form of software container) that is run on top of the hypervisor - the guest operating system and application may not know they are running on a virtual machine as opposed to running on a "bare metal" host electronic device, or through para-virtualization the operating system and/or application may be aware of the presence of virtualization for optimization purposes. In yet other alternative embodiments, one, some or all of the applications are implemented as unikernel(s), which can be generated by compiling directly with an application only a limited set of libraries (e.g., from a library operating system (LibOS) including drivers/libraries of OS seraces) that provide the particular OS services needed by the application. As a unikernel can be implemented to run directly on hardware 1140, directly on a hypervisor (in which case the unikernel is sometimes described as running within a LibOS virtual machine), or in a software container, embodiments can be implemented fully with unikernels running directly on a hypervisor represented by virtualization layer 1154, unikernels running within software containers represented by instances 1162A-1162R, or as a combination of unikernels and the above-described techniques (e.g., unikernels and virtual machines both run directly on a hypervisor, unikernels and sets of applications that are run in different software containers).

[00148] The instantiation of the one or more sets of one or more applications 1164A-1164R, as well as virtualization if implemented, are collectively referred to as software instance(s) 1152. Each set of applications 1164A-1164R, corresponding virtualization construct (e.g.,

instance 1162A-1162R) if implemented, and that part of the hardware 1140 that executes them (be it hardware dedicated to that execution and/or time slices of hardware temporally shared), forms a separate virtual network element(s) 1160A-1160R.

[00149] The virtual network element(s) 1160A-1160R perform similar functionality to the virtual network element(s) 1130A-1130R - e.g., similar to the control communication and configuration module(s) 1132A and forwarding table(s) 1134A (this virtualization of the hardware 1140 is sometimes referred to as network function virtualization (NFV)). Thus, FV may be used to consolidate many network equipment types onto industry standard high volume server hardware, physical switches, and physical storage, which could be located in Data centers, NDs, and customer premise equipment (CPE). While embodiments of the invention are illustrated with each instance 1162A-1162R corresponding to one VNE 1160A-1160R, alternative embodiments may implement this correspondence at a finer level granularity (e.g., line card virtual machines virtualize line cards, control card virtual machine virtualize control cards, etc.); it should be understood that the techniques described herein with reference to a correspondence of instances 1162A-1162R to VNEs also apply to embodiments where such a finer level of granularity and/or unikernels are used.

[00150] In certain embodiments, the virtualization layer 1154 includes a virtual switch that provides similar forwarding services as a physical Ethernet switch. Specifically, this virtual switch forwards traffic between instances 1162A-1162R and the NIC(s) 1144, as well as optionally between the instances 1162A-1162R; in addition, this virtual switch may enforce network isolation between the VNEs 1160A-1160R that by policy are not permitted to communicate with each other (e.g., by honoring virtual local area networks (VLANs)).

[00151] The third exemplary ND implementation in Figure 11 A is a hybrid network device 1106, which includes both custom ASICs/special-purpose OS and COTS

processors/standard OS in a single ND or a single card within an ND. In certain embodiments of such a hybrid network device, a platform VM (i.e., a VM that that implements the functionality of the special-purpose network device 1102) could provide for para- virtualization to the networking hardware present in the hybrid network device 1106.

[00152] Regardless of the above exemplary implementations of an ND, when a single one of multiple VNEs implemented by an ND is being considered (e.g., only one of the VNEs is part of a given virtual network) or where only a single V E is currently being implemented by an D, the shortened term network element (NE) is sometimes used to refer to that VNE. Also in all of the above exemplary implementations, each of the VNEs (e.g., VNE(s) 1130A-1130R,

VNEs 1160A-1160R, and those in the hybrid network device 1106) receives data on the physical NIs (e.g., 1116, 1146) and forwards that data out the appropriate ones of the physical NIs (e.g., 1116, 1146). For example, a VNE implementing IP router functionality forwards IP packets on the basis of some of the IP header information in the IP packet; where IP header information includes source IP address, destination IP address, source port, destination port (where "source port" and "destination port" refer herein to protocol ports, as opposed to physical ports of a ND), transport protocol (e.g., user datagram protocol (HDP), Transmission Control Protocol (TCP), and differentiated services code point (DSCP) values.

[00153] Figure 11C illustrates various exemplary ways in which VNEs may be coupled according to some embodiments. Figure 11C shows VNEs 1170 A.1-1170A.P (and optionally VNEs 1170A.Q-1170A.R) implemented in ND l lOOA and VNE 1170H.1 in ND 1100H. In Figure 11C, VNEs 1170A.1-P are separate from each other in the sense that they can receive packets from outside ND 1100 A and forward packets outside of ND 1100 A; VNE 1170 A.1 is coupled with VNE 1170H.1, and thus they communicate packets between their respective NDs; VNE 1170A.2-1170A.3 may optionally forward packets between themselves without forwarding them outside of the ND 1100 A; and VNE 1170A.P may optionally be the first in a chain of VNEs that includes VNE 1170A.Q followed by VNE 1170A.R (this is sometimes referred to as dynamic service chaining, where each of the VNEs in the series of VNEs provides a different service - e.g., one or more layer 4-7 network services). While Figure 11C illustrates various exemplary relationships between the VNEs, alternative embodiments may support other relationships (e.g., more/fewer VNEs, more/fewer dynamic service chains, multiple different dynamic service chains with some common VNEs and some different VNEs).

[00154] The NDs of Figure 11 A, for example, may form part of the Internet or a private network; and other electronic devices (not shown; such as end user devices including

workstations, laptops, netbooks, tablets, palm tops, mobile phones, smartphones, phablets, multimedia phones, Voice Over Internet Protocol (VOIP) phones, terminals, portable media players, Global Positioning System (GPS) units, wearable devices, gaming systems, set-top boxes, Internet-enabled household appliances) may be coupled to the network (directly or through other networks such as access networks) to communicate over the network (e.g., the Internet or virtual private networks (VPNs) overlaid on (e.g., tunneled through) the Internet) with each other (directly or through servers) and/or access content and/or services. Such content and/or services are typically provided by one or more servers (not shown) belonging to a service/content provider or one or more end user devices (not shown) participating in a peer-to- peer (P2P) service, and may include, for example, public webpages (e.g., free content, store fronts, search services), private webpages (e.g., username/password accessed webpages providing email services), and/or corporate networks over VPNs. For instance, end user devices may be coupled (e.g., through customer premise equipment coupled to an access network (wired or wirelessly)) to edge NDs, which are coupled (e.g., through one or more core NDs) to other edge NDs, which are coupled to electronic devices acting as servers. However, through compute and storage virtualization, one or more of the electronic devices operating as the NDs in Figure 11 A may also host one or more such servers (e.g., in the case of the general purpose network device 1104, one or more of the software instances 1162A-1162R may operate as servers; the same would be true for the hybrid network device 1106; in the case of the special- purpose network device 1102, one or more such servers could also be run on a virtualization layer executed by the compute resource(s) 1112); in which case the servers are said to be co- located with the VNEs of that ND.

[00155] A virtual network is a logical abstraction of a physical network (such as that in Figure 11 A) that provides network services (e.g., L2 and/or L3 services). A virtual network can be implemented as an overlay network (sometimes referred to as a network virtualization overlay) that provides network services (e.g., layer 2 (L2, data link layer) and/or layer 3 (L3, network layer) services) over an underlay network (e.g., an L3 network, such as an Internet Protocol (IP) network that uses tunnels (e.g., generic routing encapsulation (GRE), layer 2 tunneling protocol (L2TP), IPSec) to create the overlay network).

[00156] A network virtualization edge (NVE) sits at the edge of the underlay network and participates in implementing the network virtualization; the network-facing side of the NVE uses the underlay network to tunnel frames to and from other NVEs; the outward-facing side of the NVE sends and receives data to and from systems outside the network. A virtual network instance (VNI) is a specific instance of a virtual network on a NVE (e.g., a NE/VNE on an ND, a part of a NE/VNE on a ND where that NE/VNE is divided into multiple VNEs through emulation); one or more VNIs can be instantiated on an NVE (e.g., as different VNEs on an ND). A virtual access point (VAP) is a logical connection point on the NVE for connecting external systems to a virtual network; a VAP can be physical or virtual ports identified through logical interface identifiers (e.g., a VLAN ID).

[00157] Examples of network services include: 1) an Ethernet LAN emulation service (an Ethernet-based multipoint service similar to an Internet Engineering Task Force (IETF) Multiprotocol Label Switching (MPLS) or Ethernet VPN (EVPN) service) in which external systems are interconnected across the network by a LAN environment over the underlay network (e.g., an NVE provides separate L2 VNIs (virtual switching instances) for different such virtual networks, and L3 (e.g., IP/MPLS) tunneling encapsulation across the underlay network); and 2) a virtualized IP forwarding service (similar to IETF IP VPN (e.g., Border Gateway Protocol (BGP)/MPLS IPVPN) from a service definition perspective) in which external systems are interconnected across the network by an L3 environment over the underlay network (e.g., an NVE provides separate L3 VNIs (forwarding and routing instances) for different such virtual networks, and L3 (e.g., IP/MPLS) tunneling encapsulation across the underlay network)). Network services may also include quality of service capabilities (e.g., traffic classification marking, traffic conditioning and scheduling), security capabilities (e.g., filters to protect customer premises from network - originated attacks, to avoid malformed route announcements), and management capabilities (e.g., full detection and processing).

[00158] Fig. 1 ID illustrates a network with a single network element on each of the NDs of Figure 11 A, and within this straight forward approach contrasts a traditional distributed approach (commonly used by traditional routers) with a centralized approach for maintaining reachability and forwarding information (also called network control), according to some embodiments. Specifically, Figure 1 ID illustrates network elements (NEs) 1170A-1170H with the same connectivity as the NDs 1 lOOA-1100H of Figure 11 A.

[00159] Figure 1 ID illustrates that the distributed approach 1172 distributes responsibility for generating the reachability and forwarding information across the NEs 1170A-1170H; in other words, the process of neighbor discovery and topology discovery is distributed.

[00160] For example, where the special-purpose network device 1102 is used, the control communication and configuration module(s) 1132A-1132R of the ND control plane 1124 typically include a reachability and forwarding information module to implement one or more routing protocols (e.g., an exterior gateway protocol such as Border Gateway Protocol (BGP), Interior Gateway Protocol(s) (IGP) (e.g., Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), Routing Information Protocol (RIP), Label Distribution Protocol (LDP), Resource Reservation Protocol (RSVP) (including RS VP-Traffic Engineering (TE): Extensions to RSVP for LSP Tunnels and Generalized Multi-Protocol Label Switching

(GMPLS) Signaling RSVP-TE)) that communicate with other NEs to exchange routes, and then selects those routes based on one or more routing metrics. Thus, the NEs 1170A-1170H (e.g., the compute resource(s) 1112 executing the control communication and configuration module(s) 1132A-1132R) perform their responsibility for participating in controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) by distributively determining the reachability within the network and calculating their respective forwarding information. Routes and adjacencies are stored in one or more routing structures (e.g., Routing Information Base (RIB), Label Information Base (LIB), one or more adjacency structures) on the ND control plane 1124. The ND control plane 1124 programs the ND forwarding plane 1126 with information (e.g., adjacency and route information) based on the routing structure(s). For example, the ND control plane 1124 programs the adjacency and route information into one or more forwarding table(s) 1134A-1134R (e.g., Forwarding

Information Base (FIB), Label Forwarding Information Base (LFIB), and one or more adjacency structures) on the ND forwarding plane 1126. For layer 2 forwarding, the ND can store one or more bridging tables that are used to forward data based on the layer 2 information in that data. While the above example uses the special-purpose network device 1102, the same distributed approach 1172 can be implemented on the general purpose network device 1104 and the hybrid network device 1106.

[00161] Figure 1 ID illustrates that a centralized approach 1174 (also known as software defined networking (SDN)) that decouples the system that makes decisions about where traffic is sent from the underlying systems that forwards traffic to the selected destination. The illustrated centralized approach 1174 has the responsibility for the generation of reachability and forwarding information in a centralized control plane 1176 (sometimes referred to as a SDN control module, controller, network controller, OpenFlow controller, SDN controller, control plane node, network virtualization authority, or management control entity), and thus the process of neighbor discovery and topology discovery is centralized. The centralized control plane 1176 has a south bound interface 1182 with a data plane 1180 (sometime referred to the infrastructure layer, network forwarding plane, or forwarding plane (which should not be confused with a ND forwarding plane)) that includes the NEs 1170A-1170H (sometimes referred to as switches, forwarding elements, data plane elements, or nodes). The centralized control plane 1176 includes a network controller 1178, which includes a centralized reachability and forwarding information module 1179 that determines the reachability within the network and distributes the forwarding information to the NEs 1170A-1170H of the data plane 1180 over the south bound interface 1182 (which may use the OpenFlow protocol). Thus, the network intelligence is centralized in the centralized control plane 1176 executing on electronic devices that are typically separate from the NDs.

[00162] For example, where the special-purpose network device 1102 is used in the data plane 1180, each of the control communication and configuration module(s) 1132A-1132R of the ND control plane 1124 typically include a control agent that provides the VNE side of the south bound interface 1182. In this case, the ND control plane 1124 (the compute resource(s) 1112 executing the control communication and configuration module(s) 1132A-1132R) performs its responsibility for participating in controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) through the control agent communicating with the centralized control plane 1176 to receive the forwarding information (and in some cases, the reachability information) from the centralized reachability and forwarding information module 1179 (it should be understood that in some embodiments of the invention, the control communication and configuration module(s) 1132A-1132R, in addition to communicating with the centralized control plane 1176, may also play some role in determining reachability and/or calculating forwarding information - albeit less so than in the case of a distributed approach; such embodiments are generally considered to fall under the centralized approach 1174, but may also be considered a hybrid approach).

[00163] While the above example uses the special-purpose network device 1102, the same centralized approach 1174 can be implemented with the general purpose network device 1104 (e.g., each of the V E 1160A-1160R performs its responsibility for controlling how data (e.g., packets) is to be routed (e.g., the next hop for the data and the outgoing physical NI for that data) by communicating with the centralized control plane 1176 to receive the forwarding information (and in some cases, the reachability information) from the centralized reachability and forwarding information module 1179; it should be understood that in some embodiments of the invention, the VNEs 1160A-1160R, in addition to communicating with the centralized control plane 1176, may also play some role in determining reachability and/or calculating forwarding information - albeit less so than in the case of a distributed approach) and the hybrid network device 1106. In fact, the use of SDN techniques can enhance the NFV techniques typically used in the general purpose network device 1104 or hybrid network device 1106 implementations as NFV is able to support SDN by providing an infrastructure upon which the SDN software can be run, and NFV and SDN both aim to make use of commodity server hardware and physical switches.

[00164] Figure 1 ID also shows that the centralized control plane 1176 has a north bound interface 1184 to an application layer 1186, in which resides application(s) 1188. The centralized control plane 1176 has the ability to form virtual networks 1192 (sometimes referred to as a logical forwarding plane, network services, or overlay networks (with the NEs 1170A- 1170H of the data plane 1180 being the underlay network)) for the application(s) 1188. Thus, the centralized control plane 1176 maintains a global view of all NDs and configured

NEs/VNEs, and it maps the virtual networks to the underlying NDs efficiently (including maintaining these mappings as the physical network changes either through hardware (ND, link, or ND component) failure, addition, or removal).

[00165] While Figure 1 ID shows the distributed approach 1172 separate from the centralized approach 1174, the effort of network control may be distributed differently or the two combined in certain embodiments of the invention. For example: 1) embodiments may generally use the centralized approach 1174 (e.g., SDN), but have certain functions delegated to the NEs (e.g., the distributed approach may be used to implement one or more of fault monitoring, performance monitoring, protection switching, and primitives for neighbor and/or topology discovery); or 2) embodiments of the invention may perform neighbor discovery and topology discovery via both the centralized control plane and the distributed protocols, and the results compared to raise exceptions where they do not agree. Such embodiments are generally considered to fall under the centralized approach 1174, but may also be considered a hybrid approach.

[00166] While Figure 1 ID illustrates the simple case where each of the NDs 1 lOOA-1100H implements a single NE 1170A-1170H, it should be understood that the network control approaches described with reference to Figure 1 ID also work for networks where one or more of the NDs 1 lOOA-1100H implement multiple VNEs (e.g., VNEs 1130A-1130R, VNEs 1160A- 1160R, those in the hybrid network device 1106). Alternatively or in addition, the network controller 1178 may also emulate the implementation of multiple VNEs in a single ND.

Specifically, instead of (or in addition to) implementing multiple VNEs in a single ND, the network controller 1178 may present the implementation of a VNE/NE in a single ND as multiple VNEs in the virtual networks 1192 (all in the same one of the virtual network(s) 1192, each in different ones of the virtual network(s) 1192, or some combination). For example, the network controller 1178 may cause an ND to implement a single VNE (a NE) in the underlay network, and then logically divide up the resources of that NE within the centralized control plane 1176 to present different VNEs in the virtual network(s) 1192 (where these different VNEs in the overlay networks are sharing the resources of the single VNE/NE implementation on the ND in the underlay network).

[00167] On the other hand, Figures 1 IE and 1 IF respectively illustrate exemplary abstractions of NEs and VNEs that the network controller 1178 may present as part of different ones of the virtual networks 1192. Figure 1 IE illustrates the simple case of where each of the NDs 1100A- 1100H implements a single NE 1170A-1170H (see Figure 1 ID), but the centralized control plane 1176 has abstracted multiple of the NEs in different NDs (the NEs 1170A-1170C and 1170G-1170H) into (to represent) a single NE 11701 in one of the virtual network(s) 1192 of Figure 1 ID, according to some embodiments. Figure 1 IE shows that in this virtual network, the NE 11701 is coupled to NE 1170D and 1170F, which are both still coupled to NE 1170E.

[00168] Figure 1 IF illustrates a case where multiple VNEs (VNE 1170A.1 and VNE 1170H.1) are implemented on different NDs (ND 1100 A and ND 1100H) and are coupled to each other, and where the centralized control plane 1176 has abstracted these multiple VNEs such that they appear as a single VNE 1170T within one of the virtual networks 1192 of Figure 1 ID, according to some embodiments. Thus, the abstraction of a NE or VNE can span multiple NDs.

[00169] While some embodiments of the invention implement the centralized control plane 1176 as a single entity (e.g., a single instance of software running on a single electronic device), alternative embodiments may spread the functionality across multiple entities for redundancy and/or scalability purposes (e.g., multiple instances of software running on different electronic devices).

[00170] Similar to the network device implementations, the electronic device(s) running the centralized control plane 1176, and thus the network controller 1178 including the centralized reachability and forwarding information module 1 179, may be implemented a variety of ways (e.g., a special purpose device, a general-purpose (e.g., COTS) device, or hybrid device). These electronic device(s) would similarly include compute resource(s), a set or one or more physical NICs, and a non-transitory machine-readable storage medium having stored thereon the centralized control plane software. For instance, Figure 12 illustrates, a general purpose control plane device 1204 including hardware 1240 comprising a set of one or more processor(s) 1242 (which are often COTS processors) and network interface controller(s) 1244 (NICs; also known as network interface cards) (which include physical NIs 1246), as well as non-transitory machine readable storage media 1248 having stored therein centralized control plane (CCP) software 1250 and NRS software 1251 which, when executed, can implement the NRS module 1299 that performs operations of a NRS 510 disclosed herein.

[00171] In embodiments that use compute virtualization, the processor(s) 1242 typically execute software to instantiate a virtualization layer 1254 (e.g., in one embodiment the virtualization layer 1254 represents the kernel of an operating system (or a shim executing on a base operating system) that allows for the creation of multiple instances 1262A-1262R called software containers (representing separate user spaces and also called virtualization engines, virtual private servers, or jails) that may each be used to execute a set of one or more

applications; in another embodiment the virtualization layer 1254 represents a hypervisor (sometimes referred to as a virtual machine monitor (VMM)) or a hypervisor executing on top of a host operating system, and an application is run on top of a guest operating system within an instance 1262A-1262R called a virtual machine (which in some cases may be considered a tightly isolated form of software container) that is run by the hypervisor ; in another

embodiment, an application is implemented as a unikernel, which can be generated by compiling directly with an application only a limited set of libraries (e.g., from a library operating system (LibOS) including drivers/libraries of OS services) that provide the particular OS services needed by the application, and the unikernel can run directly on hardware 1240, directly on a hypervisor represented by virtualization layer 1254 (in which case the unikernel is sometimes described as running within a LibOS virtual machine), or in a software container represented by one of instances 1262A-1262R). Again, in embodiments where compute virtualization is used, during operation an instance of the CCP software 1250 (illustrated as CCP instance 1276A) is executed (e.g., within the instance 1262A) on the virtualization layer 1254. In embodiments where compute virtualization is not used, the CCP instance 1276A is executed, as a unikernel or on top of a host operating system, on the "bare metal" general purpose control plane

device 1204. The instantiation of the CCP instance 1276A, as well as the virtualization layer 1254 and instances 1262A-1262R if implemented, are collectively referred to as software instance(s) 1252.

[00172] In some embodiments, the CCP instance 1276A includes a network controller instance 1278, which can implement an NRS module 1299 to perform operations of an NRS 510 as disclosed herein. The NRS module 1299 includes a centralized reachability and forwarding information module instance 1279 (which is a middleware layer providing the context of the network controller 1178 to the operating system and communicating with the various NEs), and an CCP application layer 1280 (sometimes referred to as an application layer) over the middleware layer (providing the intelligence required for various network operations such as protocols, network situational awareness, and user - interfaces). At a more abstract level, this CCP application layer 1280 within the centralized control plane 1176 works with virtual network view(s) (logical view(s) of the network) and the middleware layer provides the conversion from the virtual networks to the physical view.

[00173] The centralized control plane 1176 transmits relevant messages to the data plane 1180 based on CCP application layer 1280 calculations and middleware layer mapping for each flow. A flow may be defined as a set of packets whose headers match a given pattern of bits; in this sense, traditional IP forwarding is also flow-based forwarding where the flows are defined by the destination IP address for example; however, in other implementations, the given pattern of bits used for a flow definition may include more fields (e.g., 10 or more) in the packet headers. Different NDs/NEs/VNEs of the data plane 1180 may receive different messages, and thus different forwarding information. The data plane 1 180 processes these messages and programs the appropriate flow information and corresponding actions in the forwarding tables (sometime referred to as flow tables) of the appropriate NE/VNEs, and then the NEs/VNEs map incoming packets to flows represented in the forwarding tables and forward packets based on the matches in the forwarding tables.

[00174] Standards such as OpenFlow define the protocols used for the messages, as well as a model for processing the packets. The model for processing packets includes header parsing, packet classification, and making forwarding decisions. Header parsing describes how to interpret a packet based upon a well-known set of protocols. Some protocol fields are used to build a match structure (or key) that will be used in packet classification (e.g., a first key field could be a source media access control (MAC) address, and a second key field could be a destination MAC address).

[00175] Packet classification involves executing a lookup in memory to classify the packet by determining which entry (also referred to as a forwarding table entry or flow entry) in the forwarding tables best matches the packet based upon the match structure, or key, of the forwarding table entries. It is possible that many flows represented in the forwarding table entries can correspond/match to a packet; in this case the system is typically configured to determine one forwarding table entry from the many according to a defined scheme (e.g., selecting a first forwarding table entry that is matched). Forwarding table entries include both a specific set of match criteria (a set of values or wildcards, or an indication of what portions of a packet should be compared to a particular value/values/wildcards, as defined by the matching capabilities - for specific fields in the packet header, or for some other packet content), and a set of one or more actions for the data plane to take on receiving a matching packet. For example, an action may be to push a header onto the packet, for the packet using a particular port, flood the packet, or simply drop the packet. Thus, a forwarding table entry for IPv4 / IPv6 packets with a particular transmission control protocol (TCP) destination port could contain an action specifying that these packets should be dropped.

[00176] Making forwarding decisions and performing actions occurs, based upon the forwarding table entry identified during packet classification, by executing the set of actions identified in the matched forwarding table entry on the packet.

[00177] However, when an unknown packet (for example, a "missed packet" or a "match- miss" as used in OpenFlow parlance) arrives at the data plane 1180, the packet (or a subset of the packet header and content) is typically forwarded to the centralized control plane 1176. The centralized control plane 1176 will then program forwarding table entries into the data plane 1180 to accommodate packets belonging to the flow of the unknown packet. Once a specific forwarding table entry has been programmed into the data plane 1180 by the centralized control plane 1176, the next packet with matching credentials will match that forwarding table entry and take the set of actions associated with that matched entry.

[00178] A network interface (NI) may be physical or virtual; and in the context of IP, an interface address is an IP address assigned to a NI, be it a physical NI or virtual NI. A virtual NI may be associated with a physical NI, with another virtual interface, or stand on its own (e.g., a loopback interface, a point-to-point protocol interface). A NI (physical or virtual) may be numbered (a NI with an IP address) or unnumbered (a NI without an IP address). A loopback interface (and its loopback address) is a specific type of virtual NI (and IP address) of a

NE/VNE (physical or virtual) often used for management purposes; where such an IP address is referred to as the nodal loopback address. The IP address(es) assigned to the NI(s) of a ND are referred to as IP addresses of that ND; at a more granular level, the IP address(es) assigned to NI(s) assigned to a NE/VNE implemented on a ND can be referred to as IP addresses of that NE/VNE.

[00179] Each VNE (e.g., a virtual router, a virtual bridge (which may act as a virtual switch instance in a Virtual Private LAN Service (VPLS) is typically independently administrable. For example, in the case of multiple virtual routers, each of the virtual routers may share system resources but is separate from the other virtual routers regarding its management domain, AAA (authentication, authorization, and accounting) name space, IP address, and routing database(s). Multiple VNEs may be employed in an edge ND to provide direct network access and/or different classes of services for subscribers of service and/or content providers.

[00180] Within certain NDs, "interfaces" that are independent of physical NIs may be configured as part of the VNEs to provide higher-layer protocol and service information (e.g., Layer 3 addressing). The subscriber records in the AAA server identify, in addition to the other subscriber configuration requirements, to which context (e.g., which of the VNEs/NEs) the corresponding subscribers should be bound within the ND. As used herein, a binding forms an association between a physical entity (e.g., physical NI, channel) or a logical entity (e.g., circuit such as a subscriber circuit or logical circuit (a set of one or more subscriber circuits)) and a context's interface over which network protocols (e.g., routing protocols, bridging protocols) are configured for that context. Subscriber data flows on the physical entity when some higher-layer protocol interface is configured and associated with that physical entity.

[00181] While embodiments have been described in relation to information centric networks, other embodiments can be implemented for other types of networks. Therefore, embodiments of the invention are not limited to use in information centric networks.

[00182] While the flow diagrams in the figures show a particular order of operations performed by certain embodiments of the invention, it should be understood that such order is exemplary (e.g., alternative embodiments may perform the operations in a different order, combine certain operations, overlap certain operations, etc.).

[00183] While the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described, can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting.