Premium
Open shortest path first routing under random early detection
Author(s) -
Liu Jiaxin,
Dimitrov Stanko
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21792
Subject(s) - computer science , open shortest path first , path vector protocol , shortest path problem , equal cost multi path routing , static routing , private network to network interface , routing (electronic design automation) , constrained shortest path first , link state routing protocol , computer network , routing information protocol , routing protocol , mathematical optimization , distributed computing , k shortest path routing , mathematics , theoretical computer science , graph
In this article, we consider a variant of Open Shortest Path First (OSPF) routing that accounts for Random Early Detection (RED), an Active Queue Management method for backbone networks. In the version of OSPF we consider in this article we only require a single network path be available between each origin and destination, a simplification of the OSPF protocol. We formulate a mixed integer non‐linear program to determine the data paths, referred to as a routing policy. We prove that determining an optimal OSPF routing policy that accounts for RED is NP‐Hard. Furthermore, in order for the generated routing policies to be real‐world implementable, referred to as realizable, we must determine weights for all arcs in the network such that solving the all‐pairs shortest path problem using these weights reproduces the routing policies. We show that determining if a set of all‐pairs routes is realizable is also NP‐Hard. Fortunately, using traffic data from three real‐world backbone networks, we are able to find realizable routing policies for these networks that account for RED, using an off‐the‐shelf solver, and policies found perform better than those used in each network at the time the data was collected.