Patent ID: 7409459

Claim:
A computer-readable medium having stored thereon a plurality of instructions including instructions that when executed by a processor cause the processor to implement a system for provisioning QoS paths with restoration in a network, comprising: a primary path generator configured to identify a primary QoS path for normal network operation between source and destination nodes in a network; an auxiliary graph generator, associated with said primary path generator, configured to construct a directed auxiliary graph from an undirected graph representing said network by reversing each link in said primary QoS path of said undirected graph and replacing each other link in said undirected graph that is not a link in said primary QoS path by two directed links; a walk identifier, associated with said auxiliary graph generator, configured to identify a walk in said auxiliary directed graph including bridges in said network; and a bridge identifier, associated with said walk identifier, configured to decompose said walk into a set of bridges in said network such that each link of said primary QoS path is protected by a bridge of said set of bridges and each bridge of said set of bridges protects a different portion of said primary QoS path, wherein a restoration path between said source and said destination includes a bridge from said set of bridges and links of said primary QoS path, both of said restoration path and said primary QoS path satisfying QoS constraints.