Traffic oblivious offline optimization for traffic engineering with segment routing

Patent metadata

Field	Value
Publication number	US-2016294699-A1
Application number	US-201514673195-A
Country	US
Kind code	A1
Filing date	Mar 30, 2015
Priority date	Mar 30, 2015
Publication date	Oct 6, 2016
Grant date	—

Abstract

Various exemplary embodiments relate to a method of offline traffic matrix unaware segment routing. The method may include determining the fraction of traffic between a node i and a node j is routed though node k, by minimizing the maximum value of any link e carrying traffic between node i and node j based upon the following constraints: using a dual variable π(e,e′) where e′ is an alternate link to e′ for comparison, the fraction of traffic from i to j that is routed through intermediate node k is greater than or equal to zero; the total traffic from i to j that is routed through intermediate node k is equal to 1 for all (i,j) pairs; and determining when the total capacity for link e as constrained by the dual variable is less than or equal to the capacity, c of link e′ for all e′.

First claim

What is claimed is:

1 . A method of offline traffic matrix unaware segment routing comprising:
determining the fraction of traffic between a node i and a node j is routed though node k, by minimizing the maximum value of any link e carrying traffic between node i and node j based upon the following constraints: using a dual variable π(e,e′) where e′ is an alternate link to e′ for comparison, the fraction of traffic from i to j that is routed through intermediate node k is greater than or equal to zero; the total traffic from i to j that is routed through intermediate node k is equal to 1 for all (i,j) pairs; and determining when the total capacity for link e as constrained by the dual variable is less than or equal to the capacity, c of link e′ for all e′.

2 . The method of claim 1 , further comprising:
using a linear program to minimize the maximum link utilization over all traffic matrices.

3 . The method of claim 1 , wherein the total traffic from i to j that is routed through intermediate node k is equal to 1 for all (i,j) pairs is calculated using the formula:

∑
k



α
ij
k

=

1




∀

(
ij
)

.

4 . The method of claim 1 wherein,
the fraction of traffic from i to j that is routed through intermediate node k is greater than or equal to zero is calculated using the formula:
α ij k ,π( e,e ′)≧0∀( ij )∀ e,e′,

where π(e,e′) denotes a dual variable of a link e and e′.

5 . The method of claim 1 wherein,
determining when the total capacity for link e as constrained by the dual variable is less than or equal to the capacity, c of link e′ for all e′ uses the formula,

∑
e



c


(
e
)



π


(

e
,

e
′

)

≤

θ




c


(

e
′

)





∀

e
′

where π(e,e′) denotes a dual variable of a link e and e′.

6 . The method of claim 1 , wherein a linear program minimizes the maximum link capacity θ for the following set of equations:

∑
e



g
ij
m



(
e
)



π


(

e
,

e
′

)

≥

∑
k



g
ij
k



(

e
′

)



α
ij
k





∀

(
ij
)





∀

e
′





∀
m

;

∑
e



c


(
e
)



π


(

e
,

e
′

)

Assignees

• Alcatel Lucent Usa Inc

Inventors

• Kodialam Murali
• Bhatia Randeep
• Hao Fang
• Lakshman T V

Classifications

• H04L45/24

  Multipath · CPC title

• H04L47/125 Primary

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/125

  based on throughput or bandwidth · CPC title