Systems, methods and algorithms for named data network routing with path labeling

Patent metadata

Field	Value
Publication number	US-9019971-B2
Application number	US-201213589619-A
Country	US
Kind code	B2
Filing date	Aug 20, 2012
Priority date	Jul 20, 2012
Publication date	Apr 28, 2015
Grant date	Apr 28, 2015

Abstract

A computer-implemented system and computer program product for routing at least one interest packet in a named data network including a plurality of nodes. The system comprises a mapping unit configured for mapping each of a plurality of names of a respective plurality of the data objects to one of a plurality of path labels, wherein each path label uniquely identifies a path between a source node and a destination node; and a node in operative communication with the mapping unit configured for providing an interest packet having both the name of a requested data object and one of the path labels, wherein the path label provided with the interest packet points to the requested data object at the destination node of the path label provided with the interest packet.

First claim

What is claimed is:

1. A non-transitory computer readable storage medium, tangibly embodying a program of instructions executable by the computer for routing at least one interest packet in a named data network including a plurality of nodes, the program of instructions, when executing, performing the following steps:
mapping each of a plurality of names of a respective plurality of data objects to one of a plurality of path labels, wherein each path label uniquely identifies a path between a source node and a destination node;
providing an interest packet having both the name of a requested data object and one of the path labels, wherein the path label provided with the interest packet points to the requested data object at the destination node of the path label provided with the interest packet;
receiving the interest packet at an intermediate node, the intermediate node being a node on the path identified by the path label provided with the interest packet and the intermediate node is between the source node and the destination node;
checking if the requested data object identified by the name in the interest packet is locally cached at the intermediate node;
replying to the interest packet from the intermediate node if the requested data object identified by the name in the interest packet is locally cached at the intermediate node; and
forwarding the interest packet from the intermediate node to the destination node if the requested data object identified by the name in the interest packet is not locally cached at the intermediate node.

2. The non-transitory computer readable storage medium of claim 1 , wherein the mapping encodes each path label with a unique identifier for each respective path.

3. The non-transitory computer readable storage medium of claim 1 , wherein the mapping encodes each path label with a sequence of nodes for each respective path.

4. The non-transitory computer readable storage medium of claim 1 , wherein the path between a given pair of source and destination nodes includes at least one intermediate node.

5. The non-transitory computer readable storage medium of claim 1 , wherein the program of instructions, when executing, further performs the following: assigning, from a plurality of possible path labels, an assigned path label to include in the interest packet.

6. The non-transitory computer readable storage medium of claim 5 , wherein the assigned path label is selected randomly.

7. The non-transitory computer readable storage medium of claim 5 , wherein the assigned path label is assigned based at least in part upon at least one of:
a load of each of the possible paths associated with the possible path labels; and
a capacity of each of the possible paths associated with the possible path labels.

8. The non-transitory computer readable storage medium of claim 5 , wherein the assigned path label is assigned such that for a given data object name the same path is always chosen for the same source node and destination node pair.

9. The non-transitory computer readable storage medium of claim 5 , wherein the assigned path label is assigned such that for a given data object name the path that converges to a previous path used for the same data object name is again used.

10. A computer-implemented system for routing at least one interest packet in a named data network including a plurality of nodes, the system comprising:
a mapping unit configured for mapping each of a plurality of names of a respective plurality of the data objects to one of a plurality of path labels, wherein each path label uniquely identifies a path between a source node and a destination node;
a node in operative communication with the mapping unit configured for providing an interest packet having both the name of a requested data object and one of the path labels, wherein the path label provided with the interest packet points to the requested data object at the destination node of the path label provided with the interest packet;
an intermediate node receiving the interest packet, the intermediate node being a node on the path identified by the path label provided with the interest packet and the intermediate node is between the source node and the destination node;
the intermediate node checking if the requested data object identified by the name in the interest packet is locally cached at the intermediate node;
the intermediate node replying to the interest packet if the requested data object identified by the name in the interest packet is locally cached at the intermediate node; and
the intermediate node forwarding the interest packet to the destination node if the requested data object identified by the name in the interest packet is not locally cached at the intermediate node.

11. The system of claim 10 , wherein the path between a given pair of source and destination nodes includes at least one intermediate node.

12. The system of claim 10 , wherein the mapping encodes each path label with a unique identifier for each respective path.

13. The system of claim 10 , wherein the mapping encodes each path label with a sequence of nodes for each respective path.

14. The system of claim 10 , wherein an assigned path label to include in the interest packet is assigned from a plurality of possible path labels.

15. The system of claim 14 , wherein the assigned path label is assigned such that for a given data object name the same path is always chosen for the same source node and destination node pair.

16. The system of claim 14 , wherein the assigned path label is assigned such that for a given data object name the path that converges to a previous path used for the same data object name is again used.

17. The system of claim 14 , wherein the assigned path label is assigned randomly.

18. The system of claim 14 , wherein the assigned path label is assigned based at least in part upon at least one of:
a load of each of the possible paths associated with the possible path labels; and
a capacity of each of the possible paths associated with the possible path labels.

Assignees

• Calo Seraphin
• Dilmaghani Raheleh B
• Ko Bong Jun
• Lee Kang-Won
• Pappas Vasileios
• Raghavendra Ramya
• Song Yang
• Verma Dinesh
• IBM

Inventors

• Calo Seraphin
• Dilmaghani Raheleh B
• Ko Bong Jun
• Lee Kang-Won
• Pappas Vasileios
• Raghavendra Ramya
• Song Yang
• Verma Dinesh

Classifications

• H04L45/38 Primary

  Flow based routing · CPC title

• H04L45/34

  Source routing · CPC title

• H04L45/306

  Route determination based on the nature of the carried application · CPC title