Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Optimal configuration of OSPF aggregates

Rastogi Rajeev , Breitbart, Y, Garofalakis Minos, Kumar Amit

Simple record


URIhttp://purl.tuc.gr/dl/dias/C340C28F-CBFC-4B94-9BC4-883D4116F504-
Identifierhttp://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1194816&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F90%2F26877%2F01194816.pdf%3Farnumber%3D1194816-
Identifierhttps://doi.org/10.1109/TNET.2003.810317-
Languageen-
Extent14 pagesen
TitleOptimal configuration of OSPF aggregatesen
CreatorRastogi Rajeev en
CreatorBreitbart, Yen
CreatorGarofalakis Minosen
CreatorΓαροφαλακης Μινωςel
CreatorKumar Amiten
PublisherInstitute of Electrical and Electronics Engineersen
Content SummaryOpen Shortest Path First (OSPF) is a popular protocol for routing within an autonomous system (AS) domain. In order to scale for large networks containing hundreds and thousands of subnets, OSPF supports a two-level hierarchical routing scheme through the use of OSPF areas. Subnet addresses within an area are aggregated, and this aggregation is a crucial requirement for scaling OSPF to large AS domains, as it results in significant reductions in routing table sizes, smaller link-state databases, and less network traffic to synchronize the router link-state databases. On the other hand, address aggregation also implies loss of information about the length of the shortest path to each subnet, which in turn, can lead to suboptimal routing. We address the important practical problem of configuring OSPF aggregates to minimize the error in OSPF shortest-path computations due to subnet aggregation. We first develop an optimal dynamic programming algorithm that, given an upper bound k on the number of aggregates to be advertised and a weight assignment function for the aggregates, computes the k aggregates that result in the minimum cumulative error in the shortest-path computations for all source-destination subnet pairs. Subsequently, we tackle the problem of assigning weights to OSPF aggregates such that the cumulative error in the computed shortest paths is minimized. We demonstrate that, while for certain special cases (e.g., unweighted cumulative error) efficient optimal algorithms for the weight assignment problem can be devised, the general problem itself is NP-hard. Consequently, we have to rely on search heuristics to solve the weight assignment problem. To the best of our knowledge, our work is the first to address the algorithmic issues underlying the configuration of OSPF aggregates and to propose efficient configuration algorithms that are provably optimal for many practical scenarios.en
Type of ItemPeer-Reviewed Journal Publicationen
Type of ItemΔημοσίευση σε Περιοδικό με Κριτέςel
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2015-10-29-
Date of Publication2003-
SubjectAggregatesen
SubjectOSPFen
SubjectOpen Shortest Path Firsten
Bibliographic CitationR. Rastogi, Y. Breitbart, M. Garofalakis and A. Kumar, "Optimal configuration of OSPF aggregates", IEEE/ACM Trans. Network., vol. 11, no. 2, pp. 181-194, Apr. 2003. doi:10.1109/TNET.2003.810317en

Services

Statistics