Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/C340C28F-CBFC-4B94-9BC4-883D4116F504 | - |
| Αναγνωριστικό | http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=1194816&url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F90%2F26877%2F01194816.pdf%3Farnumber%3D1194816 | - |
| Αναγνωριστικό | https://doi.org/10.1109/TNET.2003.810317 | - |
| Γλώσσα | en | - |
| Μέγεθος | 14 pages | en |
| Τίτλος | Optimal configuration of OSPF aggregates | en |
| Δημιουργός | Rastogi Rajeev | en |
| Δημιουργός | Breitbart, Y | en |
| Δημιουργός | Garofalakis Minos | en |
| Δημιουργός | Γαροφαλακης Μινως | el |
| Δημιουργός | Kumar Amit | en |
| Εκδότης | Institute of Electrical and Electronics Engineers | en |
| Περίληψη | Open 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 |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-10-29 | - |
| Ημερομηνία Δημοσίευσης | 2003 | - |
| Θεματική Κατηγορία | Aggregates | en |
| Θεματική Κατηγορία | OSPF | en |
| Θεματική Κατηγορία | Open Shortest Path First | en |
| Βιβλιογραφική Αναφορά | R. 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.810317 | en |
Copyright © DIAS 2013
