Method and Apparatus for Establishing Forwarding State Using Path State Advertisements

Abstract

Paths may be advertised on a network implementing a link state routing protocol by using Path State Advertisements (PSAs) that are distributed in the same manner as link state advertisements. The path state advertisements contain path entries, each of which includes a globally unique path ID and path information such as a series of nodes or links that defines the path through the network. When a PSA is received by a network element, the network element will evaluate the path entries in the PSA to determine if the PSA is relevant and, if necessary, install forwarding state for the relevant path entries. PSAS not relevant to a network element are not used to affect forwarding state on the network element. Label based forwarding may be used by the network elements to forward data along the path, in which the globally unique path ID is used as the label.

1 . A method of establishing forwarding state in network elements on a communication network, the method comprising the steps of:
 creating a path state advertisement containing at least one path entry, said path entry relating to a path through the communication network and including at least a path identifier and path information defining at least a part of the path through the network; and   enabling the path state advertisement to be transmitted onto the communication network as if it were a link state advertisement.   
     
     
         2 . The method of  claim 1 , further comprising the step of computing the path through the communication network from information contained in a link state database containing information obtained from. link state advertisements and path state advertisements. 
     
     
         3 . The method of  claim 1 , wherein the path state advertisement is transmitted using a link state advertisement protocol data unit. 
     
     
         4 . The method of  claim 1 , wherein the path information includes a list of links defining the path through the network. 
     
     
         5 . The method of  claim 1 , wherein the path information includes a list of nodes defining the path claim through the network. 
     
     
         6 . The method of  claim 1 , wherein the path information includes a list of both links and nodes defining the path through the network. 
     
     
         7 . The method of  claim 1 , wherein the path identifier is globally unique on the network. 
     
     
         8 . The method of  claim 1 , wherein the path state advertisement contains multiple path en tries, each of which relates to a different path through the communication network. 
     
     
         9 . The method of  claim 1 , wherein the path state advertisement contains multiple path entries, and at least a plurality of the entries relate to different portions of a tree-shaped path through the communication network. 
     
     
         10 - 19 . (canceled) 
     
     
         20 . The method of  claim 1 , further comprising forwarding the path state advertisement on the communication network as if it were a link state advertisement. 
     
     
         21 . The method of  claim 1 , further comprising, in at least one node of the communication network, evaluating path entries of the path state advertisement to determine whether at least one of the path entries corresponds to a path passing through the at least one node. 
     
     
         22 . The method of  claim 21 , further comprising, evaluating path en tries of the path state advertisement to determine whether at least one of the path entries corresponds to a path passing through the at least one node by looking for at least one of:
 path entries containing a node identifier of the the at least one node; and   path entries containing a link identifier of a link connected to the at least one node.   
     
     
         23 . The method of  claim 21  further comprising, upon finding a path state advertisement for a path entry which passes through the at least one node, installing forwarding state for the path associated with the path entry at the at least one node. 
     
     
         24 . The method of  claim 23 , wherein installing forwarding state comprises associating the path identifier in the path en try with a forwarding action that will cause traffic on the path associated with the path entry to be forwarded along the path specified by the path information in the path entry. 
     
     
         25 . The method of  claim 23 , further comprising transmitting a message from the at least one node installing forwarding state to a node originating the path state advertisement to confirm installation of forwarding state at the at least one node. 
     
     
         26 . The method of  claim 23 , further comprising applying a label containing the path identifier to packets to be transmitted on the path associated with the path entry in the path state advertisement. 
     
     
         27 . The method of  claim 26 , further comprising, at the at least one node, forwarding at least one packet having the label containing the path identifier according the installed forwarding state. 
     
     
         28 . The method of  claim 23 , wherein the installed forwarding state is based on both path identifier and on at least one of input link and input port to enable the at least one node to forward traffic in a correct direction along the path.