Method and apparatus for forwarding an interest packet based on a probability tree in an information network

Patent metadata

Field	Value
Publication number	US-10355986-B2
Application number	US-201615760988-A
Country	US
Kind code	B2
Filing date	Aug 18, 2016
Priority date	Aug 18, 2016
Publication date	Jul 16, 2019
Grant date	Jul 16, 2019

Abstract

A method and device for forwarding an interest packet based on a probability tree in an information network. By introducing a probability tree, the process of forwarding an interest packet is finally changed into a selection process: starting from a root node of the probability tree, selecting child nodes of a current node according to the probability of each child node of the current node, and stopping selecting until the selected child node is a leaf node. Moreover, the introduced probability tree provides a good carrier for machine learning. By considering the selection process as an optimization problem, the selection process can be converged to be approximate to an optimal state using online machine learning, and moreover, the probability of each node in the probability tree can be adjusted according to changes in network conditions, so that the forwarding method and device have strong adaptability to the network changes, thereby improving self-adaptability. Compared with the existing interest packet forwarding solution, the present invention improves the forwarding efficiency, increases throughput, and achieves load balance.

First claim

We claim:

1. A method of forwarding an interest packet based on a probability tree in an information network, comprising:
setting a threshold function according to a type of a to-be-forwarded interest packet, the threshold function being arranged for deciding whether to trigger the probability tree where leaf nodes correspond one-to-one to all optional forwarding interfaces for the interest packet to learn;
after the threshold function triggers the probability tree to learn, computing a cost value of each of the optional forwarding interfaces for the interest packet, respectively;
adjusting the probability tree by incrementing probabilities of a leaf node and non-leaf nodes in the probability tree, where the leaf node corresponds to an optional forwarding interface that has a smallest cost value and the non-leaf nodes refer to those nodes that have to be traversed from a root node till the leaf node;
based on the adjusted probability tree, starting from the root node of the probability tree, selecting, in accordance with probabilities of respective sub-nodes of a current node, a sub-node of the current node, and stopping till the selected sub-node is a leaf node; and
forwarding the to-be-forwarded interest packet from the optional forwarding interface corresponding to the selected leaf node.

2. The method of forwarding an interest packet based on a probability tree in an information network according to claim 1 , further comprising: when the threshold function fails to trigger the probability tree to learn, directly starting, based on the probability tree, from the root node of the probability tree, selecting the sub-node of the current node according to the probabilities of the respective sub-nodes of the current node, and stopping till the selected sub-node is a leaf node.

3. The method of forwarding an interest packet based on a probability tree in an information network according to claim 1 , further comprising:
determining whether a received interest packet needs to be forwarded; when determining a need to forward, searching all optional forwarding interfaces corresponding to the interest packet based on a forwarding information base; and
detecting whether a corresponding probability tree already exists in all optional forwarding interfaces corresponding to the received interest packet; in the case of non-existence, creating a probability tree and initializing the probability tree, wherein leaf nodes of the created probability tree correspond one-to-one to all optional forwarding interfaces for the interest packet.

4. The method of forwarding an interest packet based on a probability tree in an information network according to claim 1 , characterized in that a simulated annealing algorithm is adopted during a probability learning process so as to cause the probability tree to step out of a current status at a certain probability.

5. The method of forwarding an interest packet based on a probability tree in an information network according to claim 1 , characterized in that when computing the cost value of each of the optional forwarding interfaces, the cost value of the each of the optional forwarding interfaces is computed based on a network attribute and a probability value of the each of the optional forwarding interfaces.

6. An apparatus for forwarding an interest packet based on a probability tree in an information network, comprising a processor, a memory containing instructions, wherein when the instructions are executed by the processor, the apparatus is configured to:
set a threshold function according to a type of a to-be-forwarded interest packet, the threshold function being arranged for deciding whether to trigger the probability tree where leaf nodes correspond one-to-one to all optional forwarding interfaces for the interest packet;
after the threshold function triggers the probability tree to learn, compute a cost value of each of the optional forwarding interfaces for the interest packet, respectively;
adjust the probability tree by incrementing probabilities of a leaf node and non-leaf nodes in the probability tree, where the leaf node corresponds to an optional forwarding interface that has a smallest cost value and the non-leaf nodes refer to those nodes that have to be traversed from a root node till the leaf node;
based on the adjusted probability tree, start from the root node of the probability tree, select, in accordance with probabilities of respective sub-nodes of a current node, a sub-node of the current node, and stop till the selected sub-node is a leaf node; and
forward the to-be-forwarded interest packet from the optional forwarding interface corresponding to the selected leaf node.

7. The apparatus for forwarding an interest packet based on a probability tree in an information network according to claim 6 , wherein when the threshold function fails to trigger the probability tree to learn, the apparatus is further configured to directly start, based on the probability tree, from the root node of the probability tree, select the sub-node of the current node according to the probabilities of the respective sub-nodes of the current node, and stop till the selected sub-node is a leaf node.

8. The apparatus for forwarding an interest packet based on a probability tree in an information network according to claim 6 , wherein the apparatus is further configured to:
determine whether a received interest packet needs to be forwarded;
when the interest packet needs to be forwarded, search all optional forwarding interfaces corresponding to the interest packet based on a forwarding information base; and
detect whether a corresponding probability tree already exists in all optional forwarding interfaces corresponding to the received interest packet; and
when a result of the detection is non-existence, create a probability tree and initialize the probability tree, wherein leaf nodes of the created probability tree correspond one-to-one to all optional forwarding interfaces for the interest packet.

9. The apparatus for forwarding an interest packet based on a probability tree in an information network according to claim 6 , wherein the apparatus is further configured to adopt a simulated annealing algorithm during a probability learning process so as to cause the probability tree to step out of a current status at a certain probability.

10. The apparatus for forwarding an interest packet based on a probability tree in an information network according to claim 6 , wherein the apparatus is configured to compute the cost value of the each of the optional forwarding interfaces based on a network attribute and a probability value of the each of the optional forwarding interfaces.

Assignees

• Univ Peking Shenzhen Graduate School

Inventors

• Lei Kai
• Gong Lirui
• Yuan Jie
• Zhang Lizhu

Classifications

• H04L45/70

  Routing based on monitoring results · CPC title

• H04L45/48 Primary

  Routing tree calculation · CPC title

• H04L67/327

  Electricity · mapped topic

• H04L43/12

  Network monitoring probes · CPC title

• H04L45/12

  Shortest path evaluation · CPC title