Method and system for selecting least-loaded route based on naive Bayes classifier

Patent metadata

Field	Value
Publication number	US-11201815-B2
Application number	US-201816317063-A
Country	US
Kind code	B2
Filing date	Jan 24, 2018
Priority date	Jan 8, 2018
Publication date	Dec 14, 2021
Grant date	Dec 14, 2021

Abstract

The invention relates to a method and system for selecting a least-loaded route based on a naive Bayes classifier, so that the performance of a method for selecting a least-loaded route is improved. A network snapshot records historical network status information, and a naive Bayes classifier is used to predict the potential future network blocking probability if a service connection is established along a candidate route between each node pair. A network snapshot corresponds to each service request that arrives, and records the number of busy capacity units on each link.

First claim

What is claimed is:

1. A method for selecting a least-loaded route based on a naive Bayes classifier, comprising:
finding candidate routes between a node pair sd when a service connection is established and placing the candidate routes in a set R sd ;
when a service connection is to be established on each candidate route between a pair of nodes, calculating the sum load of each candidate route according to the current network capacity utilization status, and operating a naive Bayes classifier to predict the future potential connection blocking probability of an entire network if a service connection is established along the route; and
choosing a route with the least load as well as having the lowest impact on the success of future service connection establishment based on the following equation:

R
sd
*

=

arg
⁢

min
k

⁢

(

BP
net

sd
,
k

·

u
k
sd

)

wherein R sd * is a route with the least load as well as having the lowest impact on the success of future service connection establishment between the node pair sd, BP net sd,k is a future potential network-wide blocking probability when a service connection is established on a candidate route r k sd between a pair of nodes sd, and u k sd is a sum load of the candidate route r k sd .

2. The method for selecting a least-loaded route based on a naive Bayes classifier according to claim 1 , wherein said “operating a naive Bayes classifier to predict the future potential connection blocking probability of an entire network if a service connection is established along the route” comprises:
whenever a new service request between a pair of nodes arrives, recording the current network link capacity status as a network snapshot, with time, a sequence of network snapshots is formed, the network snapshot is denoted by a vector as follows:
S (i) =[U 1 (i) , . . . , U j (i) , . . . , U L (i) ] T

wherein, superscript i denotes an i th network snapshot, which the one when the i th service connection request arrives, L is the total number of network links, and U j (i) is the total number of capacity units used on link j, U j (i) can be considered as a feature x j in vector X;
for each candidate route r k sd ∈ R sd , it is used to establish a service connection, after which a network snapshot S c would be updated to:
S k =S c +r k sd

after a service connection is established along r k sd based on the network snapshot S k , estimating the potential service blocking probability between a node pair s′d′ as:
BP s′d′ sd,k =P ( Y= 1| S k , s′d′ )

after a service connection is established along r k sd , calculating a network-wide blocking probability as:
Bp net sd,k =Σ s′d′ l s′d′ ·BP s′d′ sd,k

wherein, l s′d′ , is the ratio of traffic load between node pair s′d′ to the total traffic in the entire network, the relationship Σ s′d′ l s′d′ =1 holds, and l s′d′ is calculated as:

l

s
′

⁢

⁢

d
′

=

∑

i
=
1

H

⁢

I
⁢

{

s
′

⁢

⁢

d

′
⁡

(
i
)

=

s
′

⁢

⁢

d
′

}

H

wherein I{s′d′ (i) =s′d′} is an indicator function to tell if the i th service request is initiated by node pair s′d′, and if it is, value of the indicator function is 1, or otherwise value of the indicator function is 0; and
said “calculating the sum load of each candidate route” includes:
for each candidate route r k sd ∈ R sd , calculating their sum load on their traversed links, wherein the sum load is calculated as:
u k sd =Σ i∈r k sd u k,i sd

wherein u k,i sd is capacity utilization on the i th link of route r k sd , and is defined as:

u

k
,
i

sd

=

U
i
c

W
i

wherein W i is the number of total capacity units on link i, U i c is the number of capacity units used on link i in the network snapshot S c , and u k sd is the sum load of a candidate route.

3. The method for selecting a least-loaded route based on a naive Bayes classifier according to claim 2 , wherein a specific calculation method of predicting a potential blocking probability by using the naive Bayes classifier includes: defining a network snapshot and an index of the node pair requesting a service connection as problem instances of the naive Bayes classifier, where a mathematical expression is:
X=[S, sd] T
wherein, S denotes a network snapshot, sd is an in

Assignees

• Univ Soochow

Inventors

• Shen Gangxiang
• Li Longfei
• Zhang Ya

Classifications

• H04L47/127 Primary

  by using congestion prediction · CPC title

• H04L45/123 Primary

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• G06F18/24155

  Bayesian classification · CPC title

• H04L67/63 Primary

  Routing a service request depending on the request content or context · CPC title

• H04L45/38

  Flow based routing · CPC title