Routing for networks with content filtering

• US 20050259648A1
• Filed: 05/21/2004
• Published: 11/24/2005
• Est. Priority Date: 05/21/2004
• Status: Active Grant

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Lakshman, Tirunell V., Kodialam, Muralidharan S., Sengupta, Sudipta
• Granted Patent: US 7,394,763 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002

Abstract

A network of nodes interconnected by links has content filtering specified at certain nodes, and routing of packet connections through the network is generated based on the specified content-filtering nodes. The network is specified via a content-filtering node placement method and a network-capacity maximization method so as to apply content filtering to packets for substantially all traffic (packet streams) carried by the network.

Claims

1. A method of generating routing for one or more connections in a network of nodes interconnected by links, the method comprising the steps of

(a) providing a list of nodes having content filtering for the network;

(b) formulating a routing-with-content-filtering problem (RCFP) for a relatively maximized network capacity subject to a set of constraints such that flow of each connection passes through at least one of the list of nodes having content filtering; and

(c) solving the RCFP to generate a routing solution that specifies routing for the one or more connections through the network.

2. The invention of claim 1, further comprising the step of (d) routing packets of each connection in accordance with the routing solution.

3. The invention of claim 1, further comprising the step of generating the list of nodes having content filtering such that each connection has a corresponding path through the network that includes at least one content-filtering node.

4. The invention of claim 1, wherein step (a) comprises the steps of:

(a1) computing a set of shortest paths through the network for each source-destination node pair;

(a2) generating a corresponding set of intermediate nodes for each set of shortest paths;

(a3) formulating a hitting set problem (HSP) based on each set of intermediate nodes for a hitting node set having a relative minimum cardinality and hitting at least one node of each set of intermediate nodes; and

(a4) solving the HSP to generate a hitting node set, the hitting set corresponding to the list of content filtering nodes.

5. The invention of claim 4, wherein step (a1) generates each set of shortest paths in accordance with a k shortest path algorithm.

6. The invention of claim 4, wherein step (a4) solves the HSP by the steps of:

(i) computing, for each node a in each set of intermediate nodes, a number of inclusion sets of intermediate nodes that include the node a;

(ii) selecting as a hitting set node the node having the maximum number of inclusion sets;

(iii) removing each set of intermediate nodes including the hitting set node of step ((a4)ii); and

iv) repeating steps (a4(i)) through (a4(iv)) until no sets of intermediate nodes remain.

7. The invention of claim 4, wherein step (a4) solves the HSP based on a guaranteed approximation factor algorithm.

8. The invention of claim 1, wherein step (b) formulates the RCFP as:

$\underset{P;<br><br>P\in <br><br>P_k}{\sum <br><br>}<br><br>x<br><br>\left(P\right)=\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(k\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>k$

subject to the primal constraints of;

$\underset{k}{\sum <br><br>}<br><br>\underset{P;<br><br>P\in <br><br>P_k}{\sum <br><br>}<br><br>x<br><br>\left(P\right)\le <br><br>u_e<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>e\in <br><br>E,\mathrm{and}$ $x<br><br>\left(P\right)\ge <br><br>0<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>P\in <br><br>P_k<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>k$

to relatively maximize λ

, wherein λ

is a scale factor, e is a link of the set E of links, u_e is the capacity of link e, k is an integer counter denoting the kth commodity, P_k denotes the set of all paths from source node s(k) to destination node t(k) of the kth commodity that pass through any content filtering node, x(P) denotes the traffic routed on path P in set P_k, and total demand d(k) routed for commodity k along all paths in P_k is equivalent to λ

d(k).

9. The invention of claim 8, wherein step (b) includes the step of formulating a dual of the RCFP.

10. The invention of claim 9, wherein step (b) formulates the dual of the RCFP as:

$\min <br><br>\underset{e\in <br><br>E}{\sum <br><br>}<br><br>u_e<br><br>w<br><br>\left(e\right),$

subject to the dual constraints of;

$\underset{e\in <br><br>E}{\sum <br><br>}<br><br>w<br><br>\left(e\right)\ge <br><br>z<br><br>\left(k\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>P\in <br><br>P_k,\forall <br><br>k,<br><br>\underset{k}{\sum <br><br>}<br><br>d<br><br>\left(k\right)<br><br>z<br><br>\left(k\right)\ge <br><br>1,\mathrm{and}$ $w<br><br>\left(e\right)\ge <br><br>0<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>e\in <br><br>E$

wherein z(k) is a variable for each commodity k corresponding to

$\underset{P;<br><br>P\in <br><br>P_k}{\sum <br><br>}<br><br>x<br><br>\left(P\right)=\mathrm{\lambda <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>d<br><br>\left(k\right)$

∀

k and w(e) is a weight for each link e an element of E corresponding to

$\underset{k}{\sum <br><br>}<br><br>\underset{P;<br><br>P\in <br><br>P_k}{\sum <br><br>}<br><br>x<br><br>\left(P\right)\le <br><br>u_e<br><br>\text{\hspace{1em}<br><br>}<br><br>\forall <br><br>e\in <br><br>E.$

11. The invention of claim 10, wherein step (c) solves the RCFP by the steps of:

(c1) initializing each weight and each flow associated with each link of the network;

(c2) routing a demand for each connection by the steps of;

(c2(i)) generating a shortest path for the demand through at least one node of the hitting set,

(c2(ii)) determining an incremental amount of flow of the demand,

(c2(iii)) routing the incremental amount of flow along the shortest path,

(c2(iv)) updating the flow and the weight of each link based on the incremental amount of flow, and

(c2(v)) repeating steps (c2(i)) through (c2(v)) until the demand is routed; and

(c3) repeating steps (c1), (c2), and (c3) until the dual constraints are met.

12. The invention of claim 11, further comprising the step of:

(c4) generating a scale factor based on a maximum routed flow of a link and the capacity of the link.

13. The invention of claim 1, wherein, for step (a), the network is either an electro-optical network or a packet-based network.

14. A method of generating a routing solution for a network of nodes interconnected by links and having at least one connection routed through the network, wherein 1) one or more of the nodes is included in a set of content filtering nodes, each content filtering node adapted to apply content filtering to a connection passing through the node, and 2) each connection passes through at least one content filtering node, the method comprising the steps of:

(a) initializing each weight and each flow associated with each link of the network;

(b) routing a demand for each connection by the steps of;

(b(i)) generating a shortest path for the demand through at least one node of the set of content filtering nodes,

(b(ii)) determining an incremental amount of flow of the demand,

(b(iii)) routing the incremental amount of flow along the shortest path,

(b(iv)) updating the flow and the weight of each link based on the incremental amount of flow, and

(b(v)) repeating steps (b(i)) through (b(v)) until the demand is routed; and

(c) repeating steps (b1), (b2), and (b3) until the dual constraints are met.

15. The invention of claim 14, further comprising the step of (d) generating a scale factor based on a maximum routed flow of a link and the capacity of the link.

16. The invention of claim 14, further comprising the step of scaling either i) each link capacity or ii) each demand based on the scale factor.

17. The invention of claim 14, further comprising the step of routing packets of each connection in accordance with the routing solution.

18. The invention of claim 14, wherein, for step (b), the network is either an electro-optical network or a packet-based network.

19. A network comprising:

a plurality of nodes interconnected by links and having at least one connection routed through the network, wherein;

1) the network comprises a set of content-filtering nodes of the plurality of nodes, each content filtering node adapted to apply content filtering to a connection passing through the content filtering node;

2) each connection is routed through the network in accordance with a routing solution such that each connection passes through at least one of the set of content-filtering nodes; and

3) the routing solution is generated by;

(a) providing a list of nodes having content filtering for the network, wherein each connection may reach at least one of the list of nodes having content filtering;

(b) formulating a routing-with-content-filtering problem (RCFP) for a relatively maximized network capacity subject to a set of constraints such that each connection passes through at least one of the list of nodes having content filtering; and

(c) solving the RCFP to generate a routing solution, the routing solution specifying routing for the one or more connections through the network so as to apply content filtering to each connection.

20. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for generating routing for one or more connections in a network of nodes interconnected by links, the method comprising the steps of:

(a) providing a list of nodes having content filtering for the network;

(b) formulating a routing-with-content-filtering problem (RCFP) for a relatively maximized network capacity subject to a set of constraints such that flow of each connection passes through at least one of the list of nodes having content filtering; and

(c) solving the RCFP to generate a routing solution that specifies routing for the one or more connections through the network.

21. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method for generating a routing solution for a network of nodes interconnected by links and having at least one connection routed through the network, wherein 1) one or more of the nodes is included in a set of content filtering nodes, each content filtering node adapted to apply content filtering to a connection passing through the node, and 2) each connection passes through at least one content filtering node, the method comprising the steps of:

(a) initializing each weight and each flow associated with each link of the network;

(b) routing a demand for each connection by the steps of;

(b(i)) generating a shortest path for the demand through at least one node of the set of content filtering nodes,

(b(ii)) determining an incremental amount of flow of the demand,

(b(iii)) routing the incremental amount of flow along the shortest path,

(b(iv)) updating the flow and the weight of each link based on the incremental amount of flow, and

(b(v)) repeating steps (b(i)) through (b(v)) until the demand is routed; and

(c) repeating steps (b1), (b2), and (b3) until the dual constraints are met.