CN113938417B - Content center network multi-path selection method based on Topson sampling - Google Patents

Abstract

The invention discloses a Thompson sampling-based content-centric network multi-path selection method. The method uses a multi-armed gambling machine method to model the multi-path selection on forwarding nodes; the probability density function of the forwarding probability of the selected path obeys Beta Distribution, comprehensive packet loss rate, bandwidth, and round-trip time for path evaluation, and the evaluation results are used as the basis for adjusting the path forwarding probability distribution; the improved Thompson sampling method is used to adaptively select the optimal path to forward Interest packets. In a multi-path selection scenario, the method of the present invention does not depend on a preset forwarding strategy, can adapt to different network conditions, and intelligently select a forwarding path according to path rating results. The method of the invention effectively avoids the cold start problem of the forwarding strategy; selects the forwarding path according to multi-index evaluation, effectively avoids network congestion, and reduces the delay of data transmission.

Description

Multi-path selection method for content-centric network based on Thompson sampling

technical field

The invention relates to the field of computer network data communication, in particular to a Thompson sampling-based content-centric network multi-path selection method.

Background technique

Content-Centric Networking (CCN) is a new type of network architecture proposed to adapt to the transformation of future network communication models and provide native support for scalable and efficient content acquisition. The end-to-end communication mode driven by (Dispatcher) is changed to the content (Contents) acquisition mode driven by the receiver (Recipient). In CCN, the user (User) pays more attention to the content itself rather than the specific location where the content is provided, and uses the content name (Content name) to uniquely identify different contents (Contents). The communication process mainly includes two types of packets: a request packet (Interest Packet, also known as an Interest Packet) and a data packet (Data Packet). The request node (Request node) of the content (Contents) searches for the required request information (Request information) by sending a request packet with a content name ID (Contentname ID), and the request packet will be forwarded by the CCN routing node. If the content matching the request information (Request information) is found in the cache of a forwarding node (Forwarding node) in the CCN network, it is said that the request information (Request information) hits the cache of the forwarding node. At this time, the hit node (Hit node) sends the corresponding data packet (Data Packet) back to the request node (Request node) along the reverse path of the request packet, and completes the information transmission process.

The selection of network paths can be divided into direct routing and indirect routing. The CCN needs to use indirect routing for path selection. Existing forwarding schemes only rely on a preset policy model (such as Best Route), and sort the forwarding ports by obtaining a single factor that affects line performance (such as transmission delay, packet loss rate, and bandwidth). Select forwarding ports for Interests with probabilities computed by the model. The pre-set model strategy cannot perform intelligent forwarding, and the evaluation of the pros and cons of a path based on the impact of a single factor on the line cannot fully improve the CCN forwarding performance; for example, the selection of factors such as data transmission delay and packet loss rate will lead to the cold start problem of forwarding .

Contents of the invention

In order to solve the technical problems of network congestion and transmission delay caused by the forwarding strategy of the existing content-centric network CCN, the present invention proposes a multi-path selection method for the content-centric network based on Thompson sampling. The method of the present invention is to map the path selection problem when CCN forwards to a multi-armed gambling machine problem, and then apply Thompson sampling self-learning and select a suitable next-hop port to adapt to different network characteristics and realize interest packets and data packets. Intelligent forwarding. The method of the invention can avoid the cold start problem caused by factors such as the prior packet loss rate; and avoid network congestion and reduce data transmission time by comprehensively evaluating the three factors of packet loss rate, time delay and bandwidth.

A kind of content-centric network multi-path selection method based on Thompson sampling of the present invention is characterized in that comprising the following steps:

Step 1, using improved Thompson sampling to obtain forwarding paths;

Step 11, obtaining all paths on the forwarding node;

中的所有路径；After the forwarding node node _forwards any Interest packet AA _a , the alternative path that can be confirmed is the forwarding node-path set

all paths in

Step 12, calculating the path return value on each path;

When any data packet BB _{b arrives} at the forwarding node node, use the path return value formula to calculate the path return value on each path;

The path return value formula is:

ω _rtt represents the weight coefficient of transmission delay;

ω _drop represents the weight coefficient of the packet loss rate;

ω _bw represents the weight coefficient of the bandwidth;

RTT_Q represents the normalized transmission delay return value;

Drop_Q represents the normalized packet loss rate return value;

Bandwidth_Q represents the normalized bandwidth return value;

Normalized transmission delay return value

Normalized packet loss rate return value

Normalized Bandwidth Return Value

Step 13, calculating the path forwarding probability at the next moment;

且

所述

的丢包率、传输时延和带宽可以看作是当前时刻t下的路径选择的状态因素，记为

且

The path reward value of any path R _i at the current moment t, denoted as

and

said

The packet loss rate, transmission delay and bandwidth can be regarded as the state factors of path selection at the current time t, denoted as

and

表示路径R_i在当前时刻t的归一化的传输时延回报值；

Indicates the normalized transmission delay return value of the path R _i at the current time t;

表示路径R_i在当前时刻t的归一化的丢包率回报值；

Indicates the normalized packet loss rate return value of the path R _i at the current moment t;

表示路径R_i在当前时刻t的归一化的带宽回报值；

Indicates the normalized bandwidth return value of the path R _i at the current moment t;

且

当前时刻t的路径转发概率为

且

所述

服从Beta分布，转发节点node_转依赖得到的当前回报值

来调整Beta函数，从而调整下一时刻路径的转发概率

且

The path forwarding probability of any path R _i located on the _forwarding node node is

and

The path forwarding probability at the current moment t is

and

said

Obey the Beta distribution, and forward the current reward value obtained _by the forwarding node node to rely on

To adjust the Beta function, thereby adjusting the forwarding probability of the path at the next moment

and

Step 14, adjusting the forwarding probability based on Beta distribution;

服从Beta(α_i,β_i)分布；α_i表示路径R_i上的正向回报参数；β_i表示路径R_i上的负向回报参数；forwarding probability

Obey the Beta(α _i , β _i ) distribution; α _i represents the positive return parameter on the path R _i ; β _i represents the negative return parameter on the path R _i ;

服从Beta(α_i,t+1,β_i,t+1)分布，初始化阶段，转发概率

服从均匀分布Beta(1,1)，即α_i,1＝β_i,1＝1；The forwarding probability of the path at the next moment for any path R _i

Obey Beta(α _i,t+1 ,β _i,t+1 ) distribution, initialization stage, forwarding probability

Obey the uniform distribution Beta(1,1), that is, α _i,1 =β _i,1 =1;

后，比较

与平均路径回报值

且

When the path R _i receives the returned path return value at the current time t

After, compare

vs mean path return value

and

大于等于

则调整α_i,t+1，且

like

greater or equal to

Then adjust α _i,t+1 , and

小于

则调整β_i,t+1，且

like

less than

Then adjust β _i,t+1 , and

Step 15, obtaining the forwarding path of the Interest packet;

中选取出最大值的转发概率，记为

From Next Moment - Forwarding Probability Set

Select the forwarding probability of the maximum value in , denoted as

对应的路径作为兴趣包的转发路径HR；Then, the described

The corresponding path is used as the forwarding path HR of the interest packet;

Step 2, construct PR_FIB table;

An improved interest forwarding table, which is recorded as the PR_FIB table; the PR_FIB table adds two pieces of information, forwarding probability and return value, to the traditional FIB table;

The PR_FIB table _in the forwarding node node needs to generate the forwarding probability corresponding to the path according to the Beta distribution of each path before forwarding any received interest packet AA _a , and fill it into the forwarding probability column of the PR_FIB table; when After the forwarding node node _forwards any data packet BB _b , it will fill in the path return value recorded in the PR_FIB table for the corresponding forwarding port;

Step 3, the forwarding mechanism of the interest packet and the data packet on the forwarding node;

From the point of view of the forwarding process of the _forwarding node node: the path selection is divided into the interest packet processing stage and the data packet processing stage:

Step 31, the processing process of the interest packet;

After the forwarding node node _forwards the interest packet AA _a , it first checks whether there is a data packet BB _b corresponding to the content prefix prefix in the content cache CS;

If so, send the data packet BB _b to the source path of the interest packet AA _a ;

If not, query the pending request table PIT;

If there is the content prefix prefix in the PIT table, it means that the _forwarding node node has received the prefix, and the source port _{is increased} for the forwarding node node; while discarding the interest packet AA _a ;

If there is none in the PIT table, then query the PR_FIB table;

对应的转发路径HR，然后用所述转发路径HR来转发兴趣包AA_a；If the PR_FIB table exists, generate a forwarding probability for the forwarding port corresponding to the content prefix prefix, and select the maximum forwarding probability

The corresponding forwarding path HR, and then use the forwarding path HR to forward the interest packet AA _a ;

If there is no PR_FIB table, then discard the interest packet AA _a ;

Step 32, the processing process of the data packet;

After the forwarding node node _forwards any data packet BB _b , the first aspect uses the path return value formula to calculate the path return value Q ^HR of the forwarding path HR, and the second aspect uses the Beta distribution to calculate the forwarding probability, and calculates the obtained The forwarding probability is recorded in the PR_FIB table; the third aspect uses the pending request table PIT to return the data packet BB _b via the source port;

The path return value Q ^HR of the forwarding path HR is:

Q ^HR ＝ω _rtt ×RTT_Q+ω _drop ×Drop_Q+ω _bw ×Bandwidth_Q

后，比较

与平均路径回报值

且

When the forwarding path HR receives the returned path return value at the current time t

After, compare

vs mean path return value

and

大于等于

则调整α_HR,t+1，且

like

greater or equal to

Then adjust α _HR,t+1 , and

小于

则调整β_HR,t+1，且

like

less than

Then adjust β _HR,t+1 , and

The advantages of the content-centric network multi-path selection method based on Thompson sampling in the present invention are:

① The present invention introduces the Thompson sampling algorithm to map the path selection problem during CCN forwarding to a multi-armed gambling machine problem, and intelligently selects the forwarding path for the next time period without relying on the preset forwarding strategy model.

②The present invention designs a prediction model of forwarding probability based on the Beta distribution, and adjusts the probability distribution by learning the path return value after forwarding. Since the Beta distribution is uniformly distributed in the initial stage, the cold start problem of forwarding can be effectively avoided; since the probability distribution varies with the path The change of return value can effectively avoid network congestion.

③ The present invention rates paths based on multiple attributes of path packet loss rate, transmission delay, and bandwidth, and does not rely on a single attribute to select a path, which can improve network performance more comprehensively.

Description of drawings

Fig. 1 is a flow chart of the multi-path selection of the content-centric network based on Thompson sampling in the present invention.

Fig. 2 is a flow chart of an embodiment of the Thompson sampling-based content-centric network multi-path selection method of the present invention.

FIG. 3 is a topological structure diagram of the CCN network in Embodiment 1.

FIG. 4 is a data structure diagram of a forwarding node in Embodiment 1.

FIG. 5 is a data structure diagram of the PIT lookup performed by the forwarding node in Embodiment 1.

FIG. 6 is a data structure diagram of Beta distribution performed by forwarding nodes in Embodiment 1.

FIG. 7 is a data structure diagram of path reporting performed by forwarding nodes in Embodiment 1. FIG.

Fig. 8 is a comparison diagram of the average time delay of the data packets received by the forwarding node in embodiment 1 processed by the method of the present invention.

Fig. 9 is a comparison chart of the packet loss rate of forwarding nodes in Embodiment 1 processed by the method of the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments.

In the present invention, the network characteristic is denoted as NC, and the network characteristic NC refers to networks with different topological structures and different bandwidths.

In the present invention, the network topology is the shape of the network, or the physical connectivity of the network. Network topology refers to the physical layout of various devices interconnected by transmission media, that is, how to connect computers and other devices in the network. The topology diagram shows the network configuration of network servers and workstations and the connections between them. There are many topological structures of the network, mainly star structure, ring structure, bus structure, distributed structure, tree structure, mesh structure, honeycomb structure and so on.

In the present invention, a node is denoted as node. The forwarding node is denoted as node _transfer .

In the present invention, the interest packet is denoted as AA. A plurality of said Interest packets AA constitute an Interest packet set MA, where MA={AA ₁ , AA ₂ , . . . , AA _a , . . . , AA _A }.

AA ₁ indicates the first Interest packet.

AA ₂ indicates the second Interest.

AA _a represents the a-th Interest packet.

AA _A indicates the last Interest packet.

The subscript a is the identification number of the Interest packet, and the subscript A is the total number of Interest packets. For convenience of description, the AA _a is also referred to as any Interest packet.

In the present invention, a data packet is denoted as BB. A plurality of said data packets BB constitute a data packet set MB, MB={BB ₁ , BB ₂ , . . . , BB _b , . . . , BB _B }.

BB ₁ means the first packet.

BB ₂ indicates the second data packet.

BB _b indicates the bth packet.

BB _B indicates the last packet.

Subscript b is the identification number of the data packet, and subscript B is the total number of data packets. For convenience of description, the BB _b is also referred to as any data packet.

且

In the present invention, the path label _forwarded by the forwarding node node is denoted as R. The multiple paths existing on the _forwarding node node constitute the forwarding node-path set, denoted as

and

R ₁ represents the first path existing on the _forwarding node node, referred to as the first path for short.

R ₂ represents the second path existing on the _forwarding node node, which is referred to as the second path for short.

R _i represents the i-th path existing _on the forwarding node node, which is referred to as the i-th path for short.

R _k represents the last path existing on the _forwarding node node, which is referred to as the last path for short.

The subscript i is the identification number of the path existing _on the forwarding node node, and the subscript k is the total number of paths existing on _{the forwarding} node node. For convenience of description, the R _i is also referred to as any path.

(即

)。任意一条路径R_i的转发概率，记为

任意一条路径R_i的丢包率，记为

任意一条路径R_i的传输时延，记为

任意一条路径R_i的带宽，记为

In the present invention, the path return value of any path R _i is denoted as

(Right now

). The forwarding probability of any path R _i is denoted as

The packet loss rate of any path R _i is denoted as

The transmission delay of any path R _i is denoted as

The bandwidth of any path R _i is denoted as

Referring to Fig. 1, shown in Fig. 2, the content-centric network multi-path selection method based on Thompson sampling of the present invention includes the following steps:

Step 1, using improved Thompson sampling to obtain forwarding paths;

Step 11, obtaining all paths on the forwarding node;

然后采用多臂赌博机方法将转发节点－路径集

中的各个路径映射为多臂赌博机的臂元素。In the present invention, all the paths _transferred by the forwarding node node are collected to form a forwarding node-path set

Then use the multi-armed bandit method to convert the forwarding node-path set

Each path in is mapped to an arm element of a multi-armed bandit.

中的所有路径。After the forwarding node node _forwards any Interest packet AA _a , the alternative path that can be confirmed is the forwarding node-path set

All paths in .

Step 12, calculating the path return value on each path;

且

_When any data packet BB _b arrives at the forwarding node node, use the path return value formula to calculate the path return value on each path, and obtain the path return value set, denoted as

and

表示第一条路径R₁的路径回报值。

Indicates the path reward value of the first path _R1 .

表示第二条路径R₂的路径回报值。

Indicates the path reward value of the second path _R2 .

表示第i条路径R_i的路径回报值。

Indicates the path reward value of the i-th path R _i .

表示最后一条路径R_k的路径回报值。

Indicates the path reward value of the last path R _k .

也称为任意一条路径R_i的路径回报值。For convenience of description, the

It is also called the path return value of any path R _i .

In the present invention, the path return value formula is:

ω _rtt represents the weight coefficient of transmission time delay.

ω _drop represents the weight coefficient of the packet loss rate.

ω _bw represents the weight coefficient of the bandwidth.

RTT_Q represents the normalized transmission delay return value.

Drop_Q represents the normalized packet loss rate return value.

Bandwidth_Q represents the normalized bandwidth return value.

当RTT_Q的值越大时，说明转发节点上的路径的传输时延情况越差。而RTT_Q与

成反比关系。In the present invention, the normalized transmission delay return value

When the value of RTT_Q is larger, it indicates that the transmission delay of the path on the forwarding node is worse. while RTT_Q with

Inversely proportional relationship.

当Drop_Q的值越大，说明转发节点上的路径的丢包率就越大。而Drop_Q与

成反比关系。In the present invention, the normalized packet loss rate return value

When the value of Drop_Q is larger, it means that the packet loss rate of the path on the forwarding node is larger. while Drop_Q with

Inversely proportional relationship.

当Bandwidth_Q的值越大，说明路径的带宽回报值越大，路径性能越好。而Bandwidth_Q与

成正比关系。In the present invention, the normalized bandwidth return value

When the value of Bandwidth_Q is larger, it means that the bandwidth return value of the path is larger and the path performance is better. And Bandwidth_Q with

proportional relationship.

Step 13, calculating the path forwarding probability at the next moment;

In the present invention, the current moment is denoted as t; the moment before the current moment t is denoted as t-1 (abbreviated as the previous moment); the moment after the current moment t is denoted as t+1 (referred to as the next moment). The total number of time points set by the forwarding node in a cycle of forwarding information is denoted as G.

且

所述

的丢包率、传输时延和带宽可以看作是当前时刻t下的路径选择的状态因素，记为

且

表示路径R_i在当前时刻t的归一化的传输时延回报值。In the present invention, the path reward value of any path R _i at the current moment t is denoted as

and

said

The packet loss rate, transmission delay and bandwidth can be regarded as the state factors of path selection at the current time t, denoted as

and

Indicates the normalized transmission delay return value of the path R _i at the current time t.

表示路径R_i在当前时刻t的归一化的丢包率回报值。

Indicates the normalized packet loss rate return value of the path R _i at the current time t.

表示路径R_i在当前时刻t的归一化的带宽回报值。

Indicates the normalized bandwidth return value of the path R _i at the current time t.

In the present invention, since the forwarding node _node does not know the possible return value of each path before forwarding any interest packet AA _a , the Beta distribution is used to calculate the Beta function for the forwarding probability of each path.

且

当前时刻t的路径转发概率为

且

所述

服从Beta分布，转发节点node_转依赖得到的当前回报值

来调整Beta函数，从而调整下一时刻路径的转发概率

且

In the present invention, the path forwarding probability of any path R _i located _on the forwarding node node is

and

The path forwarding probability at the current moment t is

and

said

Obey the Beta distribution, and forward the current reward value obtained _by the forwarding node node to rely on

To adjust the Beta function, thereby adjusting the forwarding probability of the path at the next moment

and

当前时刻t的路径转发概率为

所述

服从Beta分布，转发节点node_转依赖得到的当前回报值

来调整Beta函数，从而调整下一时刻路径的转发概率

Similarly, the path forwarding probability of the path R ₁ located _on the forwarding node node is

The path forwarding probability at the current moment t is

said

Obey the Beta distribution, and forward the current reward value obtained _by the forwarding node node to rely on

To adjust the Beta function, thereby adjusting the forwarding probability of the path at the next moment

当前时刻t的路径转发概率为

所述

服从Beta分布，转发节点node_转依赖得到的当前回报值

来调整Beta函数，从而调整下一时刻路径的转发概率

Similarly, the path forwarding probability of the path R _{2 on} the forwarding node node is

The path forwarding probability at the current moment t is

said

Obey the Beta distribution, and forward the current reward value obtained _by the forwarding node node to rely on

To adjust the Beta function, thereby adjusting the forwarding probability of the path at the next moment

当前时刻t的路径转发概率为

所述

服从Beta分布，转发节点node_转依赖得到的当前回报值

来调整Beta函数，从而调整下一时刻路径的转发概率

Similarly, the path forwarding probability of the path R _{k on} the forwarding node node is

The path forwarding probability at the current moment t is

said

Obey the Beta distribution, and forward the current reward value obtained _by the forwarding node node to rely on

To adjust the Beta function, thereby adjusting the forwarding probability of the path at the next moment

(简称为当前时刻－路径回报值集)，且

In the present invention, the path return value set at the current moment t is denoted as

(referred to as the current moment-path return value set), and

表示当前时刻t的第一条路径R₁的路径回报值。

Indicates the route reward value of the first route _R1 at the current time t.

表示当前时刻t的第二条路径R₂的路径回报值。

Indicates the path reward value of the second path _R2 at the current time t.

表示当前时刻t的第i条路径R_i的路径回报值。

Indicates the path reward value of the i-th path R _i at the current time t.

表示当前时刻t的最后一条路径R_k的路径回报值。

Indicates the path reward value of the last path R _k at the current time t.

(简称为当前时刻－转发概率集)，且

In the present invention, the path forwarding probability set at the current moment t is denoted as

(referred to as the current moment - forwarding probability set), and

表示当前时刻t的第一条路径R₁的路径转发概率。

Indicates the path forwarding probability of the first path _R1 at the current time t.

表示当前时刻t的第二条路径R₂的路径转发概率。

Indicates the path forwarding probability of the second path _R2 at the current time t.

表示当前时刻t的第i条路径R_i的路径转发概率。

Indicates the path forwarding probability of the i-th path R _i at the current time t.

表示当前时刻t的最后一条路径R_k的路径转发概率。

Indicates the path forwarding probability of the last path R _k at the current time t.

(简称为下一时刻－转发概率集)，且

In the present invention, the path forwarding probability set at the next moment t+1 is denoted as

(referred to as the next moment - forwarding probability set), and

表示下一时刻t+1的第一条路径R₁的路径转发概率。

Indicates the path forwarding probability of the first path R ₁ at the next time t+1.

表示下一时刻t+1的第二条路径R₂的路径转发概率。

Indicates the path forwarding probability of the second path _R2 at the next time t+1.

表示下一时刻t+1的第i条路径R_i的路径转发概率。

Indicates the path forwarding probability of the i-th path R _i at the next time t+1.

表示下一时刻t+1的最后一条路径R_k的路径转发概率。

Indicates the path forwarding probability of the last path R _k at the next moment t+1.

Step 14, adjusting the forwarding probability based on Beta distribution;

服从Beta(α_i,β_i)(下角标i为路径标识号)分布。α_i表示路径R_i上的正向回报参数。β_i表示路径R_i上的负向回报参数。In the present invention, the forwarding probability

Obey Beta (α _i , β _i ) (the subscript i is the path identification number) distribution. α _i represents the positive return parameter on the path R _i . β _i represents the negative reward parameter on the path R _i .

服从Beta(α_i,t+1,β_i,t+1)(下角标i为路径标识号)分布，初始化阶段，转发概率

服从均匀分布Beta(1,1)，即α_i,1＝β_i,1＝1。In the present invention, the forwarding probability of the path at the next moment for any path R _i

Obey Beta(α _i,t+1 ,β _i,t+1 ) (the subscript i is the path identification number) distribution, initialization stage, forwarding probability

It obeys the uniform distribution Beta(1,1), that is, α _i,1 =β _i,1 =1.

α _i,1 represents the positive return parameter on the path R _i at the initial moment.

β _i,1 represents the negative reward parameter on the path R _i at the initial moment.

后，比较

与平均路径回报值

且

When the path R _i receives the returned path return value at the current time t

After, compare

vs mean path return value

and

大于等于

则调整α_i,t+1，且

like

greater or equal to

Then adjust α _i,t+1 , and

小于

则调整β_i,t+1，且

like

less than

Then adjust β _i,t+1 , and

G represents the total number of time points.

表示路径R_i的第1时刻的路径回报值。

Indicates the path reward value of the path R _i at the first moment.

表示路径R_i的第2时刻的路径回报值。

Indicates the route reward value of the route R _i at the second moment.

表示路径R_i的上一时刻的路径回报值。

Indicates the path reward value of the path R _i at the last moment.

α _i,t represents the forward reward parameter on the path R _i at the current moment t.

α _i,t+1 represents the forward return parameter on the path R _i at the next moment t+1.

β _i,t represents the negative reward parameter on the path R _i at the current moment t.

β _i,t+1 represents the negative reward parameter on the path R _i at the next moment t+1.

服从Beta(α_1,t+1,β_1,t+1)分布。In the same way, the forwarding probability of the path at the next moment of the first path R ₁ is

Obey the Beta(α _1,t+1 ,β _1,t+1 ) distribution.

服从Beta(α_2,t+1,β_2,t+1)分布。In the same way, the forwarding probability of the second path R ₂ at the next moment is

Obey the Beta(α _2,t+1 ,β _2,t+1 ) distribution.

服从Beta(α_k,t+1,β_k,t+1)分布。Similarly, the forwarding probability of the next path of the last path R _k

Obey the Beta(α _k,t+1 ,β _k,t+1 ) distribution.

中，达到更新路径转发概率的目的。In the present invention, the forwarding probability of the path at the next moment adjusted by the Beta distribution is recorded into

, to achieve the purpose of updating the path forwarding probability.

In the present invention, the forwarding path selection in step 1 is an improvement on the traditional Thompson sampling algorithm, and the parameter adjustment using the Beta distribution is related to the size of the path return value. When the path return value reaches the set threshold, the greater the path return value , the greater the increase of α _i is; when the path return value does not reach the set threshold, the smaller the path return value, the greater the increase of β _i .

Step 15, obtaining the forwarding path of the Interest packet;

中选取出最大值的转发概率，记为

From Next Moment - Forwarding Probability Set

Select the forwarding probability of the maximum value in , denoted as

对应的路径作为兴趣包的转发路径HR。Then, the described

The corresponding path serves as the forwarding path HR of the Interest packet.

In the present invention, any forwarding node node in the content-centric network CCN is _transferred to the forwarding interest packet set MA={AA ₁ , AA ₂ ,...,AA _a ,...,AA _A } and data packet set MB={BB ₁ ,BB ₂ ,…,BB _b ,…,BB _B }, the path selection is handled by the multi-armed bandit method (namely MAB problem); since the multi-armed bandit method includes three factors of arm, reward and state . Therefore, the information element carried by the forwarding node node of the present invention when _forwarding information is recorded as triple forwarding information CC=[R, Q, E]; the CC=[R, Q, E] is also called CCN path selection problem.

R is the path. In the present invention, R is mapped as an arm in a multi-armed bandit approach.

Q is the path return value. In the present invention, Q is mapped to the reward in the multi-armed bandit approach.

E is a path state factor, that is, E=(DropRate, RTT, Bandwidth). In the present invention, E is mapped as a state in the multi-armed bandit method.

DropRate is the packet loss rate.

RTT is the transmission time delay.

Bandwidth is the bandwidth.

In the present invention, please refer to pages 29-34 of "Statistical Recommendation System" published in the first edition in September 2019 for the multi-armed gambling machine problem, author: [US] Deepak K.garwal, Bee-Chung Chen, translation: Dai Wei, Pan Weike, Ming Zhong.

Step 2, construct PR_FIB table;

The forwarding process of CCN consists of three important data structures: content cache (CS, Content Store), pending request table (PIT, Pending Interest Table), and interest forwarding table (FIB, Forwarding Information Base). In order to be suitable for the multi-path forwarding process of the content-centric network CCN of the present invention, the interest forwarding table FIB is improved, which is called PR_FIB table. The PR_FIB table adds two pieces of information, forwarding probability and return value, to the traditional FIB table.

Table 1, the structure of the original FIB table

Table 2 Structure of PR_FIB table

In the present invention, the PR_FIB table _in the forwarding node node needs to generate the forwarding probability corresponding to the path according to the Beta distribution of each path before forwarding any interest packet AA _a received, and fill in the forwarding probability of the PR_FIB table. in the probability column. When the forwarding node _node forwards any data packet BB _b , it will fill in the path return value recorded in the PR_FIB table for the corresponding forwarding port.

Step 3, the forwarding mechanism of the interest packet and the data packet on the forwarding node;

As shown in Figure 2, from the point of view of the forwarding process of _forwarding node node: the path selection is divided into the interest packet processing stage and the data packet processing stage:

Step 31, the processing process of the interest packet;

After the forwarding node node _forwards the interest packet AA _a , it first checks whether there is a data packet BB _b corresponding to the content prefix prefix in the content cache CS;

If so, send the data packet BB _b to the source path of the interest packet AA _a ;

If not, query the pending request table PIT;

If there is the content prefix prefix in the PIT table, it means that the _forwarding node node has received the prefix, and the source port _{is increased} for the forwarding node node; while discarding the interest packet AA _a ;

If there is none in the PIT table, then query the PR_FIB table;

对应的转发路径HR，然后用所述转发路径HR来转发兴趣包AA_a；If the PR_FIB table exists, generate a forwarding probability for the forwarding port corresponding to the content prefix prefix, and select the maximum forwarding probability

The corresponding forwarding path HR, and then use the forwarding path HR to forward the interest packet AA _a ;

If there is none in the PR_FIB table, the said Interest packet AA _a is discarded.

Step 32, the processing process of the data packet;

After the forwarding node node _forwards any data packet BB _b , the first aspect uses the path return value formula to calculate the path return value Q ^HR of the forwarding path HR, and the second aspect uses the Beta distribution to calculate the forwarding probability, and calculates the obtained The forwarding probability is recorded in the PR_FIB table; the third aspect uses the pending request table PIT to return the data packet BB _b via the source port.

In the present invention, the path return value Q ^HR of the forwarding path HR is:

Q ^HR ＝ω _rtt ×RTT_Q+ω _drop ×Drop_Q+ω _bw ×Bandwidth_Q

后，比较

与平均路径回报值

且

In the present invention, when the forwarding path HR receives the returned path return value at the current moment t

After, compare

vs mean path return value

and

大于等于

则调整α_HR,t+1，且

like

greater or equal to

Then adjust α _HR,t+1 , and

小于

则调整β_HR,t+1，且

like

less than

Then adjust β _HR,t+1 , and

表示转发路径HR的第1时刻的路径回报值。

Indicates the path reward value of the forwarding path HR at the first moment.

表示转发路径HR的第2时刻的路径回报值。

Indicates the path reward value of the forwarding path HR at the second moment.

表示转发路径HR的上一时刻的路径回报值。

Indicates the path reward value of the forwarding path HR at the previous moment.

α _HR,t represents the forward return parameter on the forwarding path HR at the current time t.

α _HR,t+1 represents the forward return parameter on the forwarding path HR at the next time t+1.

β _HR,t represents the negative reward parameter on the forwarding path HR at the current time t.

β _HR,t+1 represents the negative reward parameter on the forwarding path HR at the next time t+1.

From the forwarding stage of the overall CCN network, the forwarding stage is divided into initialization stage, exploration stage and utilization stage:

服从Beta(1,1)分布，该分布是均匀分布，此时路径的选择是随机的。Initialization phase: when the forwarding node receives the first Interest packet AA ₁ , due to the forwarding probability of the optional forwarding path

Obey the Beta(1,1) distribution, which is a uniform distribution, and the path selection is random at this time.

的分布曲线宽，集中度小，各路径的转发概率

不确定，此时转发概率

的Beta分布中心值低的路径仍有机会被选择。Exploration phase: the forwarding probability of the path that can be selected

The distribution curve is wide, the concentration is small, and the forwarding probability of each path

Uncertain, the forwarding probability at this time

The path with a low central value of the Beta distribution still has a chance to be selected.

的分布曲线窄，集中度高，各路径的转发概率相对确定，但若遇到路径R_i拥塞，导致时延

变长、丢包率

变大，本发明会根据回报值

对转发概率

的Beta分布做出调整。Exploitation stage: the forwarding probability of the path that can be selected

The distribution curve is narrow, the concentration is high, and the forwarding probability of each path is relatively certain. However, if the path R _i is congested, it will cause delay

Variable length, packet loss rate

become larger, the invention will according to the return value

pair forwarding probability

Adjusted for the Beta distribution.

Example 1

和

Referring to the CCN network topology shown in Figure 3, the path between forwarding port 1 and producer 1 is marked as the first path R ₁ in the figure, and the path between forwarding port 2 and producer 2 is marked as the second path The path R ₂ , the path between the forwarding port 3 and the producer 3 is recorded as the third path R ₃ . The data structure of the forwarding node is shown in Figure 4. The weight coefficient of transmission delay of the forwarding node ω _rtt =0.6, the weight coefficient of packet loss rate ω _drop =0.3, and the weight coefficient of bandwidth ω _bw =0.1. The average path return values of the three paths on the forwarding node are all set to 0.5, namely

and

In Embodiment 1, it is defined that what the forwarding node needs to forward is the first Interest packet AA ₁ and the first data packet BB ₁ .

Producer 1, Producer 2, and Producer 3 have the first data packet BB ₁ with the content prefix prefix_3 in their CSs. According to Step 2, establish the PR_FIB table structure belonging to the CCN network topology shown in Figure 3. The data structure of the forwarding node is shown in Figure 4. When the consumer requests the first data packet BB ₁ with content prefix prefix_3 at 250 per second, the following process is performed:

(1) The consumer sends the first Interest packet AA ₁ whose content prefix is prefix_3;

(2) When the first interest packet AA ₁ arrives at the forwarding node, search in the CS according to step 31, there is no first data packet BB ₁ whose content prefix is prefix_3;

(3) The forwarding node searches in the PIT, and there is no first data packet BB ₁ with the content prefix prefix_3, and finally records the content prefix prefix_3 and the source port 1 corresponding to the content prefix prefix_3, as shown in Figure 5 in the data structure.

(4) The forwarding node looks up in the PR_FIB table, there is the first data packet BB ₁ with content prefix prefix_3, and there are 3 forwarding ports, namely forwarding port 1, forwarding port 2 and forwarding port 3;

(5) The forwarding node obtains the forwarding path set corresponding to the forwarding port of the first Interest packet AA ₁ whose content prefix is prefix_3 according to step 11

的初始Beta分布，计算得到转发概率；第一个兴趣包AA₁是第一个达到的兴趣包，计算出转发概率为0.8、0.9、0.4并记录，如图6所示的数据结构中；(6) forwarding node according to step 13 and forwarding path set

The initial Beta distribution of the calculated forwarding probability; the first Interest packet AA ₁ is the first Interest packet to arrive, and the calculated forwarding probabilities are 0.8, 0.9, 0.4 and recorded, as shown in the data structure in Figure 6;

(7) The forwarding node forwards the first interest packet AA ₁ from the second path R ₂ corresponding to the forwarding port 2 according to step 15;

(8) When the first interest packet AA ₁ arrives at producer 2, there is a first data packet BB ₁ with content prefix prefix_3 in the CS of producer 2, and the first data packet BB ₁ is sent according to step 31 Give the source path of the first interest packet AA1, that is, the second path R ₂ ;

(9) When the first data packet BB ₁ whose content prefix is prefix_3 is returned to the forwarding node, the bandwidth of the second path R ₂ is 20, the delay is 0.2, and the packet loss rate is 0; the forwarding node calculates according to step 12 The path return value of the second path _R2 is 0.9, and is recorded in the data structure shown in Figure 7;

(10) Adjust the Beta distribution of the second route R ₂ according to step 14, 0.9>0.5, adjust α _2,2 = α _2,1 +1×0.9=1.9, α _2,1 is the second route at the initial moment The positive return parameter on the path R ₂ , α _2,2 is the positive return parameter on the second path R ₂ at the current moment, at this time, the forwarding probability of the second path R ₂ obeys Beta(1.9,1) ;

(11) Search in the PIT according to step 32, there is a record of the content prefix prefix_3, and forward the first data packet BB ₁ to the consumer according to the source port 1 of the record. So far, the request of the first data packet BB ₁ whose content prefix is prefix_3 is completed.

Referring to Figures 8 and 9, the method of the present invention is simulated on the ndnSIM platform. When the line bandwidth is 5 Mbps and the line delay is 3 ms, the requester sends Interest packets at a rate of 250 Interest packets per second, and the forwarding node The average delay of obtaining data packets is 0.07s. The average packet loss rate of forwarding nodes is 0.38 (constant dimension, the unit is not represented by %). Compared with the best-route method after being processed by the method of the invention, the time delay is reduced by 65%, and the packet loss rate is reduced by 38%. Compared with the multicast forwarding strategy (multicast) method after being processed by the method of the invention, the time delay is reduced by 73%, and the packet loss rate is reduced by 48%.

Claims (2)

1. A content-centric network multi-path selection method based on Thompson sampling is characterized in that comprising the following steps: Step 1, using improved Thompson sampling to obtain forwarding paths; Step 11, obtaining all paths on the forwarding node; After the forwarding node node _forwards any Interest packet AA _a , the alternative path that can be confirmed is the forwarding node-path set

all paths in Step 12, calculating the path return value on each path; When any data packet BB _{b arrives} at the forwarding node node, use the path return value formula to calculate the path return value on each path; The path return value formula is:

ω _rtt represents the weight coefficient of transmission delay; ω _drop represents the weight coefficient of the packet loss rate; ω _bw represents the weight coefficient of the bandwidth; RTT_Q represents the normalized transmission delay return value; Drop_Q represents the normalized packet loss rate return value; Bandwidth_Q represents the normalized bandwidth return value; Normalized transmission delay return value

Normalized packet loss rate return value

Normalized Bandwidth Return Value

Step 13, calculating the path forwarding probability at the next moment; The path reward value of any path R _i at the current moment t, denoted as

and

said

The packet loss rate, transmission delay and bandwidth can be regarded as the state factors of path selection at the current time t, denoted as

and

Indicates the normalized transmission delay return value of the path R _i at the current time t;

Indicates the normalized packet loss rate return value of the path R _i at the current moment t;

Indicates the normalized bandwidth return value of the path R _i at the current moment t; The path forwarding probability of any path R _i located on the _forwarding node node is

and

The path forwarding probability at the current moment t is

and

said

Obey the Beta distribution, and forward the current reward value obtained _by the forwarding node node to rely on

To adjust the Beta function, thereby adjusting the forwarding probability of the path at the next moment

and

Step 14, adjusting the forwarding probability based on Beta distribution; forwarding probability

Obey the Beta(α _i , β _i ) distribution; α _i represents the positive return parameter on the path R _i ; β _i represents the negative return parameter on the path R _i ; The forwarding probability of the path at the next moment for any path R _i

Obey Beta(α _i,t+1 ,β _i,t+1 ) distribution, initialization stage, forwarding probability

Obey the uniform distribution Beta(1,1), that is, α _i,1 =β _i,1 =1; α _i,1 represents the positive return parameter on the path R _i at the initial moment; β _i,1 represents the negative return parameter on the path R _i at the initial moment; When the path R _i receives the returned path return value at the current time t

After, compare

vs mean path return value

and

like

greater or equal to

Then adjust α _i,t+1 , and

like

less than

Then adjust β _i,t+1 , and

G represents the total number of time points;

Indicates the path return value of the path R _i at the first moment;

Indicates the path return value at the second moment of path R _i ;

Indicates the path return value of the path R _i at the previous moment; α _i,t represents the positive return parameter on the path R _i at the current moment t; α _i,t+1 represents the positive return parameter on the path R _i at the next moment t+1; β _i,t represents the negative return parameter on the path R _i at the current moment t; β _i,t+1 represents the negative return parameter on the path R _i at the next moment t+1; Step 15, obtaining the forwarding path of the Interest packet; From Next Moment - Forwarding Probability Set

Select the forwarding probability of the maximum value in , denoted as

Then, the described

The corresponding path is used as the forwarding path HR of the interest packet; Step 2, construct PR_FIB table; An improved interest forwarding table, which is recorded as the PR_FIB table; the PR_FIB table adds two pieces of information, forwarding probability and return value, to the traditional FIB table; The PR_FIB table _in the forwarding node node needs to generate the forwarding probability corresponding to the path according to the Beta distribution of each path before forwarding any received interest packet AA _a , and fill it into the forwarding probability column of the PR_FIB table; when After the forwarding node node _forwards any data packet BB _b , it will fill in the path return value recorded in the PR_FIB table for the corresponding forwarding port; Step 3, the forwarding mechanism of the interest packet and the data packet on the forwarding node; From the point of view of the forwarding process of the _forwarding node node: the path selection is divided into the interest packet processing stage and the data packet processing stage: Step 31, the processing process of the interest packet; After the forwarding node node _forwards the interest packet AA _a , it first checks whether there is a data packet BB _b corresponding to the content prefix prefix in the content cache CS; If so, send the data packet BB _b to the source path of the interest packet AA _a ; If not, query the pending request table PIT; If there is the content prefix prefix in the PIT table, it means that the _forwarding node node has received the prefix, and the source port _{is increased} for the forwarding node node; while discarding the interest packet AA _a ; If there is none in the PIT table, then query the PR_FIB table; If the PR_FIB table exists, generate a forwarding probability for the forwarding port corresponding to the content prefix prefix, and select the maximum forwarding probability

The corresponding forwarding path HR, and then use the forwarding path HR to forward the interest packet AA _a ; If there is no PR_FIB table, then discard the interest packet AA _a ; Step 32, the processing process of the data packet; After the forwarding node node _forwards any data packet BB _b , the first aspect uses the path return value formula to calculate the path return value Q ^HR of the forwarding path HR, and the second aspect uses the Beta distribution to calculate the forwarding probability, and calculates the obtained The forwarding probability is recorded in the PR_FIB table; the third aspect uses the pending request table PIT to return the data packet BB _b via the source port; The path return value Q ^HR of the forwarding path HR is: Q ^HR ＝ω _rtt ×RTT_Q+ω _drop ×Drop_Q+ω _bw ×Bandwidth_Q When the forwarding path HR receives the returned path return value at the current time t

After, compare

vs mean path return value

and

like

greater or equal to

Then adjust α _HR,t+1 , and

like

less than

Then adjust β _HR,t+1 , and

Indicates the path return value of the forwarding path HR at the first moment;

Indicates the path return value at the second moment of the forwarding path HR;

Indicates the path return value of the forwarding path HR at the previous moment; α _HR,t represents the positive return parameter on the forwarding path HR at the current moment t; α _HR,t+1 represents the positive return parameter on the forwarding path HR at the next moment t+1; β _HR,t represents the negative return parameter on the forwarding path HR at the current moment t; β _HR,t+1 represents the negative reward parameter on the forwarding path HR at the next time t+1. 2. the content-centric network multi-path selection method based on Thompson sampling according to claim 1 is characterized in that: from the forwarding stage of the overall CCN network, the forwarding stage is divided into initialization stage, exploration stage and utilization stage; Initialization phase: when the forwarding node receives the first Interest packet AA ₁ , due to the forwarding probability of the optional forwarding path

Obey the Beta(1,1) distribution, which is a uniform distribution, and the path selection is random at this time; Exploration phase: the forwarding probability of the path that can be selected

The distribution curve is wide, the concentration is small, and the forwarding probability of each path

Uncertain, the forwarding probability at this time

The path with a low central value of the Beta distribution still has a chance to be selected; Exploitation stage: the forwarding probability of the path that can be selected

The distribution curve is narrow, the concentration is high, and the forwarding probability of each path is relatively certain. However, if the path R _i is congested, it will cause delay

Variable length, packet loss rate

become larger, according to the return value

pair forwarding probability

Adjusted for the Beta distribution.

Images