Complete rerouting protection

Thomas K. Stidsen, Peter Kjærulff

    Research output: Contribution to journalJournal articleResearchpeer-review

    181 Downloads (Pure)

    Abstract

    Protection of communication against network failures is becoming increasingly important and in this paper we present the most capacity efficient protection method possible, the complete rerouting protection method, when requiring that all communication should be restored in case of a single link network failure. We present a linear programming model of the protection method and a column generation algorithm. For 6 real world networks, the minimal restoration overbuild network capacity is between 13% and 78%. We further study the importance of the density of the network, derive analytical bounds and study methods to speed up the column generation algorithm.
    Original languageEnglish
    JournalJournal of Optical Networking
    Volume5
    Issue number6
    Pages (from-to)481-492
    ISSN1536-5379
    DOIs
    Publication statusPublished - Jun 2006

    Keywords

    • column generation
    • network protectioin

    Cite this

    Stidsen, Thomas K. ; Kjærulff, Peter. / Complete rerouting protection. In: Journal of Optical Networking. 2006 ; Vol. 5, No. 6. pp. 481-492.
    @article{862011dcaa104fb4bbf2f22a9526301b,
    title = "Complete rerouting protection",
    abstract = "Protection of communication against network failures is becoming increasingly important and in this paper we present the most capacity efficient protection method possible, the complete rerouting protection method, when requiring that all communication should be restored in case of a single link network failure. We present a linear programming model of the protection method and a column generation algorithm. For 6 real world networks, the minimal restoration overbuild network capacity is between 13{\%} and 78{\%}. We further study the importance of the density of the network, derive analytical bounds and study methods to speed up the column generation algorithm.",
    keywords = "column generation, network protectioin",
    author = "Stidsen, {Thomas K.} and Peter Kj{\ae}rulff",
    year = "2006",
    month = "6",
    doi = "10.1364/JON.5.000481",
    language = "English",
    volume = "5",
    pages = "481--492",
    journal = "Journal of Optical Communications and Networking",
    issn = "1943-0620",
    publisher = "Institute of Electrical and Electronics Engineers",
    number = "6",

    }

    Complete rerouting protection. / Stidsen, Thomas K.; Kjærulff, Peter.

    In: Journal of Optical Networking, Vol. 5, No. 6, 06.2006, p. 481-492.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - Complete rerouting protection

    AU - Stidsen, Thomas K.

    AU - Kjærulff, Peter

    PY - 2006/6

    Y1 - 2006/6

    N2 - Protection of communication against network failures is becoming increasingly important and in this paper we present the most capacity efficient protection method possible, the complete rerouting protection method, when requiring that all communication should be restored in case of a single link network failure. We present a linear programming model of the protection method and a column generation algorithm. For 6 real world networks, the minimal restoration overbuild network capacity is between 13% and 78%. We further study the importance of the density of the network, derive analytical bounds and study methods to speed up the column generation algorithm.

    AB - Protection of communication against network failures is becoming increasingly important and in this paper we present the most capacity efficient protection method possible, the complete rerouting protection method, when requiring that all communication should be restored in case of a single link network failure. We present a linear programming model of the protection method and a column generation algorithm. For 6 real world networks, the minimal restoration overbuild network capacity is between 13% and 78%. We further study the importance of the density of the network, derive analytical bounds and study methods to speed up the column generation algorithm.

    KW - column generation

    KW - network protectioin

    U2 - 10.1364/JON.5.000481

    DO - 10.1364/JON.5.000481

    M3 - Journal article

    VL - 5

    SP - 481

    EP - 492

    JO - Journal of Optical Communications and Networking

    JF - Journal of Optical Communications and Networking

    SN - 1943-0620

    IS - 6

    ER -