The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Feasibility issues in shortest-path routing with traffic flow split

På svenska

Author

  • Michal Pioro
  • Artur Tomaszewski

Summary, in English

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.

Publishing year

2007

Language

English

Document type

Conference paper

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • IP networks
  • OSPF routing
  • ECMP flow
  • branch-and-cut

Conference name

International Network Optimization Conference INOC 2007

Conference date

2007-04-22 - 2007-04-25

Conference place

Spa, Belgium

Status

Published