Method and system for resilient routing reconfiguration
OwnerYin Zhang, Lili Qiuinventors
Life of this patent
Estimating the term…
Abstract
A method and system for resilient routing reconfiguration, which provides provably congestion-free rerouting under a large number of failure scenarios and achieves efficiency and flexibility in accommodating different performance requirements, is disclosed. The method of embodiments comprises an offline precomputation phase and an online reconfiguration phase. Embodiments of the present invention also provide a number of useful functionalities, including (i) coping with traffic variations, (ii) supporting realistic failure scenarios, (iii) accommodating prioritized traffic with different protection levels, and (iv) balancing the trade-off between performance and resilience.
Claims42
A method for rerouting traffic in an Internet Protocol (IP) network, the method comprising:
- creating a virtual demand for links in said IP network;
- precomputing a routing for an actual demand plus said virtual demand for said links in said IP network on an original network topology prior to detecting any failures in said links in said IP network in order to minimize a maximum link utilization over said IP network after an occurrence of link failures;
- detecting one or more links in said IP network that have failed;
- and
- converting, by a processor, said precomputed routing into a routing that does not traverse said detected one or more failed links in said IP network in response to detecting said one or more failed links in said IP network, wherein said routing that does not traverse said detected one or more failed links is guaranteed to be congestion free provided that said maximum link utilization is less than one.
A non-transitory computer readable storage medium storing a computer program product for rerouting traffic in an Internet Protocol (IP) network, the computer program product comprising the programming instructions for:
- creating a virtual demand for links in said IP network;
- precomputing a routing for an actual demand plus said virtual demand for said links in said IP network on an original network topology prior to detecting any failures in said links in said IP network in order to minimize a maximum link utilization over said IP network after an occurrence of link failures;
- detecting one or more links in said IP network that have failed;
- and
- converting said precomputed routing into a routing that does not traverse said detected one or more failed links in said IP network in response to detecting said one or more failed links in said IP network, wherein said routing that does not traverse said detected one or more failed links is guaranteed to be congestion free provided that said maximum link utilization is less than one.
A system, comprising:
- a memory unit for storing a computer program for rerouting traffic in an Internet Protocol (IP) network;
- and
- a processor coupled to said memory unit, wherein said processor, responsive to said computer program, comprises:
- circuitry for creating a virtual demand for links in said IP network;
- circuitry for precomputing a routing for an actual demand plus said virtual demand for said links in said IP network on an original network topology prior to detecting any failures in said links in said IP network in order to minimize a maximum link utilization over said IP network after an occurrence of link failures;
- circuitry for detecting one or more links in said IP network that have failed;
- and
- circuitry for converting said precomputed routing into a routing that does not traverse said detected one or more failed links in said IP network in response to detecting said one or more failed links in said IP network, wherein said routing that does not traverse said detected one or more failed links is guaranteed to be congestion free provided that said maximum link utilization is less than one.
Dependencies are inferred from the claim text.