Feasibility issues in shortest-path routing with traffic flow split
(2007) International Network Optimization Conference INOC 2007- Abstract
- In the Internet’s autonomous systems packets are routed on shortest paths to their destinations. A related problem is how to find an admissible traffic routing configuration using paths that can be generated by a system of weights assigned to IP links. This problem is NP-hard. It can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective cuts (valid inequalities) can be derived. In this paper we discuss admissibility of shortest-path routing configurations represented by binary variables specifying whether or not a particular link is on a shortest path to a particular destination. We present a linear programming problem for testing routing admissibility and derive solutions of this problem which... (More)
- In the Internet’s autonomous systems packets are routed on shortest paths to their destinations. A related problem is how to find an admissible traffic routing configuration using paths that can be generated by a system of weights assigned to IP links. This problem is NP-hard. It can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective cuts (valid inequalities) can be derived. In this paper we discuss admissibility of shortest-path routing configurations represented by binary variables specifying whether or not a particular link is on a shortest path to a particular destination. We present a linear programming problem for testing routing admissibility and derive solutions of this problem which characterize non-admissible routing configurations. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1024458
- author
- Pioro, Michal LU and Tomaszewski, Artur
- organization
- publishing date
- 2007
- type
- Contribution to conference
- publication status
- published
- subject
- keywords
- IP networks, OSPF routing, ECMP flow, branch-and-cut
- pages
- 7 pages
- conference name
- International Network Optimization Conference INOC 2007
- conference location
- Spa, Belgium
- conference dates
- 2007-04-22 - 2007-04-25
- language
- English
- LU publication?
- yes
- id
- 32c8a706-8b4f-4caa-b38d-e291d27aa9ff (old id 1024458)
- date added to LUP
- 2016-04-04 14:41:00
- date last changed
- 2018-11-21 21:21:41
@misc{32c8a706-8b4f-4caa-b38d-e291d27aa9ff,
abstract = {{In the Internet’s autonomous systems packets are routed on shortest paths to their destinations. A related problem is how to find an admissible traffic routing configuration using paths that can be generated by a system of weights assigned to IP links. This problem is NP-hard. It can be formulated as a mixed-integer program and attempted with a branch-and-cut algorithm if effective cuts (valid inequalities) can be derived. In this paper we discuss admissibility of shortest-path routing configurations represented by binary variables specifying whether or not a particular link is on a shortest path to a particular destination. We present a linear programming problem for testing routing admissibility and derive solutions of this problem which characterize non-admissible routing configurations.}},
author = {{Pioro, Michal and Tomaszewski, Artur}},
keywords = {{IP networks; OSPF routing; ECMP flow; branch-and-cut}},
language = {{eng}},
title = {{Feasibility issues in shortest-path routing with traffic flow split}},
url = {{https://lup.lub.lu.se/search/files/6416492/2594735.pdf}},
year = {{2007}},
}