Advanced

Feasibility issues in shortest-path routing with traffic flow split

Pioro, Michal LU and Tomaszewski, Artur (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:
author
organization
publishing date
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
language
English
LU publication?
yes
id
32c8a706-8b4f-4caa-b38d-e291d27aa9ff (old id 1024458)
date added to LUP
2008-02-05 13:42:25
date last changed
2016-07-12 11:11:31
@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},
  keyword      = {IP networks,OSPF routing,ECMP flow,branch-and-cut},
  language     = {eng},
  pages        = {7},
  title        = {Feasibility issues in shortest-path routing with traffic flow split},
  year         = {2007},
}