| 1. |
- Brostrom, Peter, et al.
(författare)
-
Design of OSPF networks using subpath consistent routing patterns
- 2009
-
Ingår i: TELECOMMUNICATION SYSTEMS. - : Springer Science and Business Media LLC. - 1018-4864 .- 1572-9451. ; 41:4, s. 293-309
-
Tidskriftsartikel (refereegranskat)abstract
- We address the problem of designing IP networks where the traffic is routed using the OSPF protocol. Routers in OSPF networks use link weights set by an administrator for determining how to route the traffic. The routers use all shortest paths when traffic is routed to a destination, and the traffic is evenly balanced by the routers when several paths are equally short. We present a new model for the OSPF network design problem. The model is based on routing patterns and does not explicitly include OSPF weights. The OSPF protocol is modeled by ensuring that all pairs of routing patterns are subpath consistent, which is a necessary condition for the existence of weights. A Lagrangean heuristic is proposed as solution method, and feasible solutions to the problem are generated using a tabu search method. Computational results are reported for random instances and for real-life instances.
|
|
| 2. |
|
|
| 3. |
|
|
| 4. |
- Broström, Peter, et al.
(författare)
-
Compatible Weights and Valid Cycles in Non-spanning OSPF Routing Patterns
- 2009
-
Ingår i: Algorithmic Operations Research. - 1718-3235. ; 4:1, s. 19-35
-
Tidskriftsartikel (refereegranskat)abstract
- Many IP (Internet Protocol) networks use OSPF (Open Shortest Path First) for determining the routing of traffic. OSPF routers compute routing paths using link weights set by the network administrator, and the routers send traffic on all shortest paths to the destination. An interesting question is whether or not a set of prespecified routing patterns can be realized in an OSPF network. If not, we seek structural properties that explain why no such weights exist. Mathematical models for finding weights and for combining routing patterns are presented. We show that two possibly non-spanning routing patterns forming a ``valid cycle'' cannot simultaneously be obtained in an OSPF network. Two new methods for finding valid cycles are presented, illustrated by numerical examples, and shown to be faster that those previously known.
|
|
| 5. |
|
|
| 6. |
|
|
| 7. |
- Broström, Peter, 1973-, et al.
(författare)
-
Determining the Non-Existence of a Compatible OSPF Metric
- 2004
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Many telecommunication networks use Internet Protocol for deciding the routing of traffic. The specifications OSPF (Open Shortest Path First) and ECM (Equal Cost Multipath) are very common, and state that each router sends the traffic on the shortest path to the destination. If there are several shortest path, the router splits the traffic evenly. In order to have some control over the traffic distribution, the operator can assign weights to the links in the network, and these weights are used by the routers when calculating the shortest paths. It has been shown that by optimizing over the values of the weights, the performance of a network can be much improved. A difficult question is whether or not for a set of desired traffic patterns there exists a compatible metric, i.e. weights making the routers give the specified traffic patterns. There is one known necessary condition for the existence of such a metric, but up to now no sufficient conditions. We investigate this problem, and find more general necessary conditions for the existence of compatible weights for a set of given desired "shortest path"-graphs. A polynomial algorithm that for most cases verifies the non-existence of a compatible metric is presented. The algorithm also indicates which parts of the traffic patterns that are in conflict. A few numer;cal examples are used to illustrate the procedure, and some computational tests are reported.
|
|
| 8. |
|
|
| 9. |
|
|
| 10. |
- Broström, Peter, et al.
(författare)
-
Multiobjective design of survivable IP networks
- 2006
-
Ingår i: Annals of Operations Research. - : Springer Science and Business Media LLC. - 0254-5330 .- 1572-9338. ; 147:1, s. 235-253
-
Tidskriftsartikel (refereegranskat)abstract
- Modern communication networks often use Internet Protocol routing and the intra-domain protocol OSPF (Open Shortest Path First). The routers in such a network calculate the shortest path to each destination and send the traffic on these paths, using load balancing. The issue of survivability, i.e. the question of how much traffic the network will be able to accommodate if components fail, is increasingly important. We consider the problem of designing a survivable IP network, which also requires determining the routing of the traffic. This is done by choosing the weights used for the shortest path calculations.
|
|
