Routing protocol broadcast link extensions

Abstract

A first router in a first AS, the first router comprises: a processor configured to: obtain information about a broadcast link connecting the first router to a second router in a second AS, and generate a link state message comprising the information; and a transmitter coupled to the processor and configured to transmit the link state message to a third router, wherein the third router is in the first AS and is adjacent to the first router. A method comprises: receiving a first link state message from a first router; receiving a second link state message from a second router; receiving a third link state message from a third router; determining which of the first router, the second router, and the third router are ASBRs connected to a broadcast link based on information in the first link state message, the second link state message, and the third link state message.

What is claimed is: 
     
         1 . A method comprising:
 receiving link state messages from routers in a routing system; and   determining, based on the link state messages, autonomous system border routers (ASBRs) connected to a broadcast link.   
     
     
         2 . The method of  claim 1 , wherein the method is implemented by a path computation element (PCE). 
     
     
         3 . The method of  claim 1 , wherein each of the link state messages is an Intermediate System to Intermediate System (IS-IS) link state protocol data unit (LSP) or an Open Shortest Path First (OSPF) link state advertisement (LSA). 
     
     
         4 . The method of  claim 1 , wherein the routers are all routers in the routing system. 
     
     
         5 . The method of  claim 1 , wherein the routers are all routers connected to a link. 
     
     
         6 . The method of  claim 1 , wherein receiving the link state messages from the routers comprises receiving the link state messages directly from the routers. 
     
     
         7 . The method of  claim 1 , wherein receiving the link state messages from the routers comprises receiving the link state messages indirectly from the routers and through paths comprising multiple routers. 
     
     
         8 . The method of  claim 1 , further comprising further determining the ASBRs based on flags in the link state messages. 
     
     
         9 . The method of  claim 1 , further comprising determining that the ASBRs are connected to the broadcast link by obtaining local Internet Protocol (IP) addresses from the link state messages. 
     
     
         10 . The method of  claim 9 , further comprising further determining that the ASBRs are connected to the broadcast link by applying a mask to each of the local IP addresses to obtain masked IP addresses. 
     
     
         11 . The method of  claim 10 , further comprising further determining that the ASBRs are connected to the broadcast link by determining that the ASBRs are part of a link when the masked IP addresses corresponding to the ASBRs are the same. 
     
     
         12 . The method of  claim 11 , further comprising further determining that the ASBRs are connected to the broadcast link by determining that the link is the broadcast link when the link state messages corresponding to the ASBRs comprise sub-type-length-values (sub-TLVs) indicating a link type is multi-access. 
     
     
         13 . The method of  claim 1 , further comprising designating a designated router (DR) and a backup designated router (BDR) based on the link state messages. 
     
     
         14 . The method of  claim 13 , wherein designating the DR and the BDR comprises:
 designating the DR as a first router from which one of the link state messages is received; and   designating the BDR as a second router from which another one of the link state messages is received.   
     
     
         15 . The method of  claim 13 , further comprising creating a pseudo node system comprising the ASBRs, a pseudo node, and virtual links, wherein the pseudo node is a virtual node that represents a center point among the ASBRs, and wherein the virtual links connect the ASBRs to the pseudo node. 
     
     
         16 . The method of  claim 15 , further comprising designating the BDR as a new DR when the DR is disabled. 
     
     
         17 . The method of  claim 15 , further comprising computing a routing path using the pseudo node. 
     
     
         18 . An apparatus comprising:
 a memory configured to store instructions; and   a processor coupled to the memory and configured to execute the instructions to cause the apparatus to:
 receive link state messages from routers in a routing system; and 
 determine, based on the link state messages, autonomous system border routers (ASBRs) connected to a broadcast link. 
   
     
     
         19 . The apparatus of  claim 18 , wherein the processor is further configured to execute the instructions to cause the apparatus to determine the ASBRs connected to the broadcast link by:
 determining the ASBRs based on flags in the link state messages;   obtaining local Internet Protocol (IP) addresses from the link state messages;   applying a mask to the local IP addresses to obtain masked IP addresses;   determining that the ASBRs are part of a link when the masked IP addresses corresponding to the ASBRs are the same; and   determining that the link is the broadcast link when the link state messages corresponding to the ASBRs comprise sub-type-length-values (sub-TLVs) indicating a link type is multi-access.   
     
     
         20 . A computer program product comprising instructions that are stored on a computer-readable medium and that, when executed by a processor, cause an apparatus to:
 receive link state messages from routers in a routing system; and   determine, based on the link state messages, autonomous system border routers (ASBRs) connected to a broadcast link.