Optimization of OSPF routing in IP networks
(2009) p.199-240- Abstract
- The Internet is a huge world-wide packet switching network comprised of more than 13,000 distinct subnetworks, referred to as Autonomous Systems (ASs) . They all rely on the Internet Protocol (IP) for transport of packets across the network. And most of them use shortest path routing protocols , such as OSPF or IS-IS, to control the routing of IP packets within an AS. The idea of the routing is extremely simple — every packet is forwarded on IP links along the shortest route between its source and destination nodes of the AS. The AS network administrator can manage the routing of packets in the AS by supplying the so-called administrative weights of IP links, which specify the link lengths that are used by the routing protocols for their... (More)
- The Internet is a huge world-wide packet switching network comprised of more than 13,000 distinct subnetworks, referred to as Autonomous Systems (ASs) . They all rely on the Internet Protocol (IP) for transport of packets across the network. And most of them use shortest path routing protocols , such as OSPF or IS-IS, to control the routing of IP packets within an AS. The idea of the routing is extremely simple — every packet is forwarded on IP links along the shortest route between its source and destination nodes of the AS. The AS network administrator can manage the routing of packets in the AS by supplying the so-called administrative weights of IP links, which specify the link lengths that are used by the routing protocols for their shortest path computations. The main advantage of the shortest path routing policy is its simplicity, allowing for little administrative overhead. From the network engineering perspective, however, shortest path routing can pose problems in achieving satisfactory traffic handling efficiency. As all routing paths depend on the same routing metric , it is not possible to configure the routing paths for the communication demands between different pairs of nodes explicitly or individually; the routing can be controlled only indirectly and only as a whole by modifying the routing metric. Thus, one of the main tasks when planning such networks is to find administrative link weights that induce a globally efficient traffic routing configuration of an AS. It turns out that this task leads to very difficult mathematical optimization problems. In this chapter, we discuss and describe exact integer programming models and solution approaches as well as practically efficient smart heuristics for such shortest path routing problems . (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1360525
- author
- Bley, A ; Fortz, B ; Gourdin, E ; Holmberg, K ; Klopfenstein, O ; Pioro, Michal LU ; Tomaszewski, A and Ümit, H
- organization
- publishing date
- 2009
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- OSPF, the Internet, telecommunication networks, shortest path routing, ECMP, integer linear programming, heuristics
- host publication
- Graphs and algorithms in communication networks – studies in broadband, optical, wireless, and Ad Hoc networks
- editor
- Koster, A and Muñoz, X
- pages
- 199 - 240
- publisher
- Springer
- ISBN
- 978-3-642-02249-4
- DOI
- 10.1007/978-3-642-02250-0_8
- language
- English
- LU publication?
- yes
- id
- 6a38e147-5ccf-4344-84ab-b199c77331ac (old id 1360525)
- date added to LUP
- 2016-04-04 10:24:24
- date last changed
- 2018-11-21 20:58:34
@inbook{6a38e147-5ccf-4344-84ab-b199c77331ac,
abstract = {{The Internet is a huge world-wide packet switching network comprised of more than 13,000 distinct subnetworks, referred to as Autonomous Systems (ASs) . They all rely on the Internet Protocol (IP) for transport of packets across the network. And most of them use shortest path routing protocols , such as OSPF or IS-IS, to control the routing of IP packets within an AS. The idea of the routing is extremely simple — every packet is forwarded on IP links along the shortest route between its source and destination nodes of the AS. The AS network administrator can manage the routing of packets in the AS by supplying the so-called administrative weights of IP links, which specify the link lengths that are used by the routing protocols for their shortest path computations. The main advantage of the shortest path routing policy is its simplicity, allowing for little administrative overhead. From the network engineering perspective, however, shortest path routing can pose problems in achieving satisfactory traffic handling efficiency. As all routing paths depend on the same routing metric , it is not possible to configure the routing paths for the communication demands between different pairs of nodes explicitly or individually; the routing can be controlled only indirectly and only as a whole by modifying the routing metric. Thus, one of the main tasks when planning such networks is to find administrative link weights that induce a globally efficient traffic routing configuration of an AS. It turns out that this task leads to very difficult mathematical optimization problems. In this chapter, we discuss and describe exact integer programming models and solution approaches as well as practically efficient smart heuristics for such shortest path routing problems .}},
author = {{Bley, A and Fortz, B and Gourdin, E and Holmberg, K and Klopfenstein, O and Pioro, Michal and Tomaszewski, A and Ümit, H}},
booktitle = {{Graphs and algorithms in communication networks – studies in broadband, optical, wireless, and Ad Hoc networks}},
editor = {{Koster, A and Muñoz, X}},
isbn = {{978-3-642-02249-4}},
keywords = {{OSPF; the Internet; telecommunication networks; shortest path routing; ECMP; integer linear programming; heuristics}},
language = {{eng}},
pages = {{199--240}},
publisher = {{Springer}},
title = {{Optimization of OSPF routing in IP networks}},
url = {{http://dx.doi.org/10.1007/978-3-642-02250-0_8}},
doi = {{10.1007/978-3-642-02250-0_8}},
year = {{2009}},
}