Method of Traffic Engineering for Provisioning Routing and Storage in Content-Oriented Networks

• US 20140126370A1
• Filed: 03/13/2013
• Published: 05/08/2014
• Est. Priority Date: 11/08/2012
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Xie, Haiyong, Wang, Guo-Qiang
• Granted Patent: US 9,401,868 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A transceiver configured to receive and transmit data in a content oriented network (CON), and a processor configured to obtain a jointly provisioned routing and storage solution resolved according to an aggregated data flow equation generating a conventional data flow of content on a link to a destination, and an aggregated data flow of the content on the link, and a storage indicator, and to determine whether to store and transmit the data.

Claims

1. An apparatus comprising:

a transceiver configured to receive and transmit data in a content oriented network (CON);

a processor configured to obtain a jointly provisioned routing and storage solution resolved according to an aggregated data flow equation generating a conventional data flow of content on a link to a destination, and an aggregated data flow of the content on the link, and a storage indicator, and to determine whether to store and transmit the data based on the solution.

2. The apparatus of claim 1, wherein the jointly provisioned routing and storage solution accommodates fractional values of the storage indicator z_k^c.

3. The apparatus of claim 1, wherein the aggregated data flow equation is:

Σ

<sub>iε

out (k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c=0,∀

k,k∉

{t,o(c)},∀

c

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c={circumflex over (d)}_k^c,k=o(c),∀

c,

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c=−

{circumflex over (d)}_k^c,k∀

=t,∀

c;

wherein {circumflex over (d)}_k^c is the reduced demand of content c at node k, required to satisfy (i) {circumflex over (d)}_k^c=d_c^k, if z_k^c=0, and (ii) {circumflex over (d)}_k^c=1, if z_k^c=1, wherein d_k^c is the total number of downstream demands for content c attached to node k, t is a destination node, and o(c) is the set of content origin nodes, and wherein x_l^t,c is the conventional data flow of content c on link l to destination t.

4. The apparatus of claim 3, wherein jointly provisioning the solution comprises coupling the aggregated data flow equation with a flow conservation constraint, and wherein the flow conservation constraint is:

d_k^c+Σ

<sub>lε

out(k)</sub>y_l^c−

Σ

<sub>lε

in(k)</sub>y_l^c≦

Bz_k^c,∀

kε

V,∀

c;

wherein y_l^c is the aggregated data flow of the content c on the link l, wherein z_k^c=1 means that node k stores content c and z_k^c=0 means that node k does not store content c.

5. The apparatus of claim 1, wherein a Traffic Engineering (TE) for the CON is formulated as:

min Σ

_cΣ

_lF(y_l^c)

Σ

_cy_l^c≦

C_l,∀

lε

E

Σ

_cz_k^c≦

S_k,∀

kε

V

y_l^c≧

x_l^{t,c},∀

l,∀

tε

V,∀

c

z_k^cε

{0,1},y_l^c≧

0,x_l^{t,c}≧

0.

where F(y_l^c) is a general traffic engineering objective function, C_l is the bandwidth capacity of link l, and S_k is the storage capacity of a node k.

6. The apparatus of claim 1, wherein obtaining the jointly provisioned routing and storage solution comprises determining x_l^t,c,y_l^c,z_k^c, and B, wherein x_l^t,c the conventional data flow of content c on link l to destination t, wherein y_l^c is the aggregated data flow of content c on link l, wherein z_k^c=1 means that node k stores content c and z_k^c=0 means that node k does not store content c, and wherein B is an upper bound of total outgoing flow.

7. The apparatus of claim 1, wherein routing provisioning is decoupled from content storage provisioning, and wherein the solution is determined at least in part based on satisfying at least one routing provisioning objective comprising a linear function of x_l^t,c,y_l^c,z_k^c, wherein x_l^t,c is the conventional data flow of content c on link l to destination t, wherein y_l^c is the aggregated data flow of content c on link l, wherein z_k^c=1 means that node k stores content c and z_k^c=0 means that node k does not store content c, and wherein B is an upper bound of total outgoing flow.

8. A traffic engineering method executable by a processor in a network node, comprising:

receiving content at a network node in a content oriented network (CON), wherein the network node has a routing capability and a storage capability; and

deciding whether to store the content at the node, wherein the decision is based on selection criteria identified by a process comprising;

decoupling routing provisioning from coordinated storage provisioning; and

jointly provisioning the routing capability and the storage capability of the network node, wherein the provisioning complies with a set of flow conservation laws and at least one content storage constraint, and wherein the routing provisioning is decoupled from the coordinated storage provisioning of the routers.

9. The method of claim 8, wherein the set of flow conservation laws comprise an aggregated data flow equation:

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c=0,∀

k,k∉

{t,o(c)},∀

c,

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c={circumflex over (d)}_k^c,k=o(c),∀

c,

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c=−

{circumflex over (d)}_k^c,k∀

=t,∀

c

wherein {circumflex over (d)}_k^c is the reduced demand of content c at node k, required to satisfy (i) {circumflex over (d)}_k^c=d_c^k, if z_k^c=0, and (ii) {circumflex over (d)}=1, if z_k^c=1, wherein di is the total number of downstream demands for content c attached to node k, t is a destination node, and o(c) is the set of content origin nodes, and wherein x_i^t,c is the conventional data flow of content c on link l to destination t.

10. The method of claim 9, wherein provisioning further complies with a flow conservation constraint, wherein the flow conservation constraint comprises:

d_k^c+Σ

<sub>lε

out(l)</sub>y_l^c−

Σ

<sub>lε

in(k)</sub>y_l^c≦

Bz_k^c∀

kε

V,∀

c.

wherein y_l^c is the aggregated data flow of the content c on the link l, wherein z_k^c=1. means that node k stores content c, wherein z_k^c=0 means that node k does not store content c, and wherein B is an upper bound of total outgoing flow.

11. The method of claim 8, wherein provisioning is determined at least in part based on satisfying at least one routing provisioning objective selected from a group consisting of:

bandwidth usage, maximum link utilization (MLU), Bit Cost Product (BCP), and Bit Hop-count Product (BHP).

12. The method of claim 8, wherein provisioning comprises:

initializing Lagrangian multipliers; and

iteratively processing an algorithm to optimize the joint provisioning until a stopping criterion or maximal number of iterations has been reached.

13. The method of claim 8, wherein the selection criteria comprises the content value as expressed in terms of Σ

<sub>lε

out(k)</sub>y_l^c, and wherein y_l^c is the aggregated data flow of the content c on the link l.

14. The method of claim 13, further comprising:

evicting a second content with a lesser value of Σ

<sub>lε

out(k)</sub>y_l^c; and

storing the content.

15. A computer program product comprising computer executable instructions stored on a non-transitory medium that when executed by a processor cause the processor to perform the following:

utilize a set of aggregated flow conservation rules;

determine a storage capacity limit;

select a TE objective comprising a linear function of x_l^t,c,y_l^c,z_k^c;

determine x_l^t,c, y_l^c, and z_k^c, that comply with the set of aggregated flow conservation rules, the storage capacity, and the TE objective, wherein x_l^t,c is the conventional data flow of content c on link l to destination t, and wherein y_l^c is the aggregated data flow of content c on link l, wherein z_k^c=1 means that node k stores content c and z_k^c=0 means that node k does not store content c;

determine a joint provisioning routing and storage solution; and

store content c on a network node and transmit traffic from the network node based on the jointly provisioned routing and storage solution.

16. The computer program product of claim 15, wherein the set of aggregated flow conservation rules comprises an aggregated data flow constraint d_k^cΣ

<sub>lε

out(k)</sub>y_l^c−

Σ

<sub>lε

in(k)</sub>y_l^c, wherein the total outgoing flow is less than or equal to a constant value B multiplied by z_k^c, wherein B is an upper bound of total outgoing flow, wherein d_k^c is a total number of downstream demands for content c attached to node k, wherein y_l^c is an aggregated data flow of content c on link l, wherein Σ

<sub>lε

out(k)</sub>y_l^c is the sum of all outgoing data flow for content c on link l at node k for all links, and wherein Σ

<sub>lε

out(k)</sub>y_l^c is the sum of all incoming data flow for content c on link l at node k for all links.

17. The computer program product of claim 15, wherein determining the joint provisioning routing and storage solution comprises satisfying at least one routing provisioning objective selected from a group consisting of:

bandwidth usage, maximum link utilization (MLU), Bit Cost Product (BCP), and Bit Hop-count Product (BHP).

18. The computer program product of claim 15, wherein the set of aggregated flow conservation rules comprises an aggregated flow conservation constraint:

d_k^c+Σ

<sub>lε

out(k)</sub>y_l^c−

Σ

<sub>lε

in(k)</sub>y_l^c≦

Bz_k^c,∀

kε

V,∀

c, wherein d_k^c is a total number of downstream demands for content c attached to node k, wherein y_l^c is an aggregated data flow of content c on link l, wherein Σ

<sub>iε

out(k)</sub>y_l^c is the sum of all outgoing data flow for content c on link l at node k for all links, wherein Σ

<sub>lε

in(k)</sub>y_l^c is the sum of all incoming data flow for content c on link l at node k for all links, and wherein B is an upper bound of total outgoing flow.

19. The computer program product of claim 15, wherein determining x_l^t,c, y_l^c, and z_k^c comprises solving a minimization problem.

20. The computer program product of claim 15, wherein determining the jointly provisioned routing and storage solution comprises solving:

min Σ

_l(w_l+α

_—

l)·

y_l^c+Σ

_kβ

_k·

z_k^c−

Σ

_lα

_l·

C_l−

Σ

_kβ

_l·

S_k

s.t. y_l^c≧

x_l^{t,c},∀

l,∀

tε

V,∀

c

z_k^cε

{0,1},y_l^c≧

0,x_l^{t,c}≧

0

where F(y_l^c) is a general traffic engineering objective function, C_l is the bandwidth capacity of link l, and S_k is the storage capacity of a node k;

wherein the jointly provisioned routing and storage solution satisfies;

a flow conservation constraint given by;

d_k^c+Σ

<sub>lε

out(k)</sub>y_l^c−

Σ

<sub>lε

in(k)</sub>y_l^c≦

Bz_k^c,∀

kε

V,∀

c

wherein y_l^c is the aggregated data flow of the content c on the link l, wherein B is an upper bound of total outgoing flow, wherein the storage indicator z_k^c=1 means that node k stores content c and z_k^c=0 means that node k does not store content c;

and an aggregated data flow equation;

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c=0,∀

k,k∉

{t,o(c)},∀

c,

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c={circumflex over (d)}_k^c,k=o(c),∀

c,

Σ

<sub>lε

out(k)</sub>x_l^t,c−

Σ

<sub>lε

in(k)</sub>x_l^t,c=−

{circumflex over (d)}_k^c,k∀

=t,∀

c;

wherein {circumflex over (d)}_k^c is the reduced demand of content c at node k, required to satisfy (i) {circumflex over (d)}_k^c=d_c^k, if z_k^c=0, and (ii) {circumflex over (d)}_k^c=1, if z_k^c=1, wherein d_k^c is the total number of downstream demands for content c attached to node k, t is a destination node, and o(c) is the set of content origin nodes, and wherein x_l^t,c is the conventional data flow of content c on link l to destination t.