Open Problems:9 - Revision history

Krzysztof Onak at 01:39, 7 March 2013

2013-03-07T01:39:25Z

Krzysztof Onak at 05:02, 16 November 2012

2012-11-16T05:02:46Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 9: OSPF Routing}} {{Infobox |label1 = Proposed by |data1 = Sampath Kannan |label2 = Source |data2 = Kanpur 2006 |label3 = Shor..."

2012-10-01T10:02:08Z

Created page with "{{DISPLAYTITLE:Problem 9: OSPF Routing}} {{Infobox |label1 = Proposed by |data1 = Sampath Kannan |label2 = Source |data2 = Kanpur 2006 |label3 = Shor..."

New page

{{DISPLAYTITLE:Problem 9: OSPF Routing}}
{{Infobox
|label1 = Proposed by
|data1 = Sampath Kannan
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/9
}}
Open-Shortest-Path-First (OSPF) routing is an intra-domain routing protocol where each link of a network is assigned a weight and each packet is forwarded along the shortest path given these weights (e.g. {{cite|KuroseR-04}}). Initially, the weight of a link is the reciprocal of the bandwidth of the link. However, as a link becomes congested, it would make sense to discourage the use of the link by increasing the weight of the link. We are interested in setting these weights such that the flows in the network are routed “optimally” for some appropriate notion of optimality. At present this is done locally at each link. Unfortunately, this often causes oscillatory behavior. Is there a distributed-stream approach to this problem? In particular, traffic is monitored at each router subject to the usual streaming constraints and a limited amount of communication is permitted between the routers. Given these limitations, is it possible to implement a better, more “global” solution.

It should be mentioned that for many notions of optimality, achieving optimal routing is NP-hard even when the traffic matrix is known and weights are set by some central authority. Consequently, it would be necessary to focus on notions of optimality that are at least achievable in such an idealized setting. Alternatively, one could ask which heuristics can be implemented in the distributed-stream setting. Comparisons between different solutions could be in terms of the rate of convergence to stable solutions.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Sampath Kannan

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 9: OSPF Routing}}
+{{Header
-{{Infobox
+|title=Open-Shortest-Path-First Routing
-|label1 = Proposed by
+|source=kanpur06
-|data1 = Sampath Kannan
+|who=Sampath Kannan
 }}
 Open-Shortest-Path-First (OSPF) routing is an intra-domain routing protocol where each link of a network is assigned a weight and each packet is forwarded along the shortest path given these weights (e.g. {{cite|KuroseR-04}}). Initially, the weight of a link is the reciprocal of the bandwidth of the link. However, as a link becomes congested, it would make sense to discourage the use of the link by increasing the weight of the link. We are interested in setting these weights such that the flows in the network are routed &ldquo;optimally&rdquo; for some appropriate notion of optimality.  At present this is done locally at each link. Unfortunately, this often causes oscillatory behavior. Is there a distributed-stream approach to this problem? In particular, traffic is monitored at each router subject to the usual streaming constraints and a limited amount of communication is permitted between the routers. Given these limitations, is it possible to implement a better, more &ldquo;global&rdquo; solution.
 It should be mentioned that for many notions of optimality, achieving optimal routing is NP-hard even when the traffic matrix is known and weights are set by some central authority. Consequently, it would be necessary to focus on notions of optimality that are at least achievable in such an idealized setting. Alternatively, one could ask which heuristics can be implemented in the distributed-stream setting. Comparisons between different solutions could be in terms of the rate of convergence to stable solutions.

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)