Method and system for reference counted pending interest tables in a content centric network

• US 10,009,266 B2
• Filed: 07/05/2016
• Issued: 06/26/2018
• Est. Priority Date: 07/05/2016
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wood, Christopher A., Scott, Glenn C.
• Primary Examiner(s): Sefcheck, Gregory
• Assistant Examiner(s): ULYSSE, JAEL M
• Application Number:
  US15/202,071
• Publication Number:
  US 20180013666A1
• Time in Patent Office: 721 Days
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: H04L 45/308 Route determination based on user's profile, e.g. premium users
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/72 Routing based on the source address
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

One embodiment provides a system for facilitating efficient communication of a collection of interests. During operation, the system receives, by an intermediate node, a first packet which has a name and a first nonce, wherein the first packet indicates a set of member interests, wherein a member interest has a name. In response to not obtaining a matching entry in a pending interest table based on the name for the first packet, the system creates a new entry in the pending interest table, wherein an entry includes a second nonce, a reference count, and a set of arrival nonces and corresponding arrival interfaces. The system sets the new entry'"'"'s second nonce to a new nonce, and sets the new entry'"'"'s reference count to a number of member interests indicated in the first packet. The system forwards the first packet, wherein the first nonce is replaced with the new nonce.

Claims

1. A computer-implemented method for forwarding packets, the method comprising:

receiving, by an intermediate node, a first packet which has a name and a first nonce, wherein the first packet indicates a set of two or more member interests, wherein each member interest has a name, wherein a name is a hierarchically structured variable length identifier that includes contiguous name components ordered from a most general level to a most specific level;

performing a search, by the intermediate node, for the name of the first packet in a pending interest table, the pending interest table including a plurality of entries;

in response to not obtaining a matching entry in the plurality of entries of the pending interest table based on the name for the first packet, creating a new entry in the pending interest table, wherein the new entry includes a new nonce generated by the intermediate node, a reference count, and a set of arrival nonces and corresponding arrival interfaces;

setting the new entry'"'"'s reference count to a number of member interests indicated in the first packet;

replacing the first nonce of the first packet with the new nonce;

forwarding the first packet with the new nonce, by the intermediate node, thereby facilitating efficient communication of the set of member interests indicated in the first packet; and

in response to obtaining a content object packet that has a matching entry in the pending interest table, transmitting the content object packet based on arrival interfaces of the matching entry.

2. The method of claim 1, further comprising:

in response to determining that the reference count of an entry in the pending interest table is zero, removing the entry from the pending interest table.

3. The method of claim 1, further comprising:

setting the new entry'"'"'s arrival nonce to the first nonce of the first packet; and

setting the new entry'"'"'s corresponding arrival interface to an interface corresponding to an entity from which the first packet is received.

4. The method of claim 1, wherein in response to obtaining a matching entry in the pending interest table, the method further comprises:

adding to the matching entry'"'"'s set of arrival nonces and corresponding arrival interfaces the first nonce of the first packet and an arrival interface corresponding to an entity from which the first packet is received;

replacing the first nonce of the first packet with a second nonce associated with the matching entry; and

forwarding the first packet with the second nonce.

5. The method of claim 1, wherein the content object packet has a name and a verification nonce, and wherein obtaining the matching entry in the pending interest table is based on the verification nonce, the method further comprises:

decrementing the matching entry'"'"'s reference count by one; and

replacing the verification nonce of the content object packet with the matching entry'"'"'s arrival nonce.

6. The method of claim 1, further comprising:

receiving a second packet which has a name and an arrival nonce;

in response to obtaining a matching entry in the pending interest table based on the name or the arrival nonce of the second packet, incrementing the matching entry'"'"'s reference count by one.

7. The method of claim 1, wherein in response to obtaining a content object that satisfies a member interest, and in response to not obtaining a matching entry in the pending interest table, the method further comprises:

creating the new entry in the pending interest table;

decrementing the new entry'"'"'s reference count by one;

setting a verification nonce of the obtained content object to the first nonce indicated in the first packet; and

transmitting the obtained content object based on the new entry'"'"'s corresponding arrival interface.

8. A computer system for facilitating forwarding of packets, the system comprising:

a processor; and

a storage device storing instructions that when executed by the processor cause the processor to perform a method, the method comprising;

receiving, by an intermediate node, a first packet which has a name and a first nonce, wherein the first packet indicates a set of two or more member interests, wherein each member interest has a name, wherein a name is a hierarchically structured variable length identifier that includes contiguous name components ordered from a most general level to a most specific level;

performing a search, by the intermediate node, for the name of the first packet in a pending interest table, the pending interest table including a plurality of entries;

in response to not obtaining a matching entry in the plurality of entries of the pending interest table based on the name for the first packet, creating a new entry in the pending interest table, wherein the new entry includes a new nonce generated by the intermediate node, a reference count, and a set of arrival nonces and corresponding arrival interfaces;

setting the new entry'"'"'s reference count to a number of member interests indicated in the first packet;

replacing the first nonce of the first packet with the new nonce;

forwarding the first packet with the new nonce, by the intermediate node, thereby facilitating efficient communication of the set of member interests indicated in the first packet; and

in response to obtaining a content object packet that has a matching entry in the pending interest table, transmitting the content object packet based on arrival interfaces of the matching entry.

9. The computer system of claim 8, wherein the method further comprises:

in response to determining that the reference count of an entry in the pending interest table is zero, removing the entry from the pending interest table.

10. The computer system of claim 8, wherein the method further comprises:

setting the new entry'"'"'s arrival nonce to the first nonce of the first packet; and

setting the new entry'"'"'s corresponding arrival interface to an interface corresponding to an entity from which the first packet is received.

11. The computer system of claim 8, wherein in response to obtaining a matching entry in the pending interest table, the method further comprises:

adding to the matching entry'"'"'s set of arrival nonces and corresponding arrival interfaces the first nonce of the first packet and an arrival interface corresponding to an entity from which the first packet is received;

replacing the first nonce of the first packet with the matching entry'"'"'s second nonce; and

forwarding the first packet.

12. The computer system of claim 8, wherein the content object packet a name and a verification nonce, and wherein obtaining the matching entry in the pending interest table is based on the verification nonce, the method further comprises:

decrementing the matching entry'"'"'s reference count by one; and

replacing the verification nonce of the content object packet with the matching entry'"'"'s arrival nonce.

13. The computer system of claim 8, wherein the method further comprises:

receiving a second packet which has a name and an arrival nonce;

in response to obtaining a matching entry in the pending interest table based on the name or the arrival nonce of the second packet, incrementing the matching entry'"'"'s reference count by one.

14. The computer system of claim 8, wherein in response to obtaining a content object that satisfies a member interest, and in response to not obtaining a matching entry in the pending interest table, the method further comprises:

creating the new entry in the pending interest table;

decrementing the new entry'"'"'s reference count by one;

setting a verification nonce of the obtained content object to the first nonce indicated in the first packet; and

transmitting the obtained content object based on the new entry'"'"'s corresponding arrival interface.

15. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:

receiving, by an intermediate node, a first packet which has a name and a first nonce, wherein the first packet indicates a set of two or more member interests, wherein each member interest has a name, wherein a name is a hierarchically structured variable length identifier that includes contiguous name components ordered from a most general level to a most specific level;

performing a search, by the intermediate node, for the name of the first packet in a pending interest table, the pending interest table including a plurality of entries;

in response to not obtaining a matching entry in the plurality of entries of the pending interest table based on the name for the first packet, creating a new entry in the pending interest table, wherein the new entry includes a new nonce generated by the intermediate node, a reference count, and a set of arrival nonces and corresponding arrival interfaces;

setting the new entry'"'"'s reference count to a number of member interests indicated in the first packet;

replacing the first nonce of the first packet with the new nonce;

forwarding the first packet with the new nonce, by the intermediate node, thereby facilitating efficient communication of the set of member interests indicated in the first packet; and

in response to obtaining a content object packet that has a matching entry in the pending interest table, transmitting the content object packet based on arrival interfaces of the matching entry.

16. The storage medium of claim 15, wherein the method further comprises:

in response to determining that the reference count of an entry in the pending interest table is zero, removing the entry from the pending interest table.

17. The storage medium of claim 15, wherein in response to obtaining a matching entry in the pending interest table, the method further comprises:

adding to the matching entry'"'"'s set of arrival nonces and corresponding arrival interfaces the first nonce of the first packet and an arrival interface corresponding to an entity from which the first packet is received;

replacing the first nonce of the first packet with the matching entry'"'"'s second nonce; and

forwarding the first packet.

18. The storage medium of claim 15, wherein the content object packet has a name and a verification nonce, and wherein obtaining the matching entry in the pending interest table is based on the verification nonce, the method further comprises:

decrementing the matching entry'"'"'s reference count by one; and

replacing the verification nonce of the content object packet with the matching entry'"'"'s arrival nonce.

19. The storage medium of claim 15, wherein the method further comprises:

receiving a second packet which has a name and an arrival nonce;

in response to obtaining a matching entry in the pending interest table based on the name or the arrival nonce of the second packet, incrementing the matching entry'"'"'s reference count by one.

20. The storage medium of claim 15, wherein in response to obtaining a content object that satisfies a member interest, and in response to not obtaining a matching entry in the pending interest table, the method further comprises:

creating the new entry in the pending interest table;

decrementing the new entry'"'"'s reference count by one;

setting a verification nonce of the obtained content object to the first nonce indicated in the first packet; and

transmitting the obtained content object based on the new entry'"'"'s corresponding arrival interface.