Method and apparatus for exchanging routing information and establishing connectivity across multiple network areas

Abstract

A method ensures that multicast packets follow the same loop-free path followed by unicast packets in a packet communication network. The communication network includes at least one first area interconnected through at least one area border node (“ABN”) to a second area. Each ABN has a first level port connected to each first area and a second level port connected to the second area. Each multicast packet forwarded includes a header having a root-id identifying a root of a multicast tree. A data packet is received at an ABN. Responsive to receiving a multicast packet at a second level port of an area border node, the root-id of the multicast packet is examined and if the multicast packet is to be forwarded over at least one of the first level ports, a different root-id is substituted into the packet before the packet is forwarded over the first level port.

1 . A method for forwarding multicast packets in a packet communication network, the packet communication network having at least one first area, each first area having a first plurality of nodes interconnected by a respective set of links, each first area interconnected through at least one area border node to a second area, the second area having a second plurality of nodes interconnected by a respective set of links, each area border node having at least one first area port connected to the at least one first area and a second area port connected to the second area, each multicast packet forwarded at the at least one area border router including a header comprising a root-id identifying a root of a multicast tree, the method comprising:
 responsive to receiving a multicast packet at the second area port of an area border node:
 examining the root-id of the multicast packet; 
 determining whether the multicast packet is to be forwarded on at least one of the first area ports of the area border node; and 
   responsive to determining that the multicast packet is to be forwarded over at least one of the first area ports, substituting a different root-id into the packet before forwarding the packet over the at least one first area port.   
     
     
         2 . The method of  claim 1 , wherein the different root-id comprises an identifier associated with the second area. 
     
     
         3 . The method of  claim 2 , wherein the identifier associated with the second area is associated with a pseudo-node representing the second area. 
     
     
         4 . The method of  claim 1 , wherein the at least one first area is defined by a first level and the second area is defined by a second level different from the first level. 
     
     
         5 . The method of  claim 4 , wherein the first level is a level X and the second level is a level X+1. 
     
     
         6 . The method of  claim 1 , wherein the packet communication network is an Ethernet network. 
     
     
         7 . The method of  claim 1 , wherein at least one first area is served by a number of area border nodes, the method further comprising dividing the at least one first area served by the number of area border nodes into a number of subsets, the number of subsets being equal to the number of area border nodes, each subset being associated with a respective area border node. 
     
     
         8 . The method of  claim 7 , wherein each subset comprises nodes for which there is no closer area border node than the area border node associated with the subset. 
     
     
         9 . The method of  claim 8 , wherein there is no closer area border node for a node than the area border node associated with the subset when the node has a shortest path to the area border node which is at least as short as any shortest path from the node to any other area border node. 
     
     
         10 . The method of  claim 7 , wherein each node of each subset has a shortest path to the area border node associated with the subset which is at least as short as any shortest path from the node to any other area border node. 
     
     
         11 . The method of  claim 7 , wherein each subset comprises nodes having a shortest path to the area border node associated with the subset. 
     
     
         12 . The method of  claim 7 , wherein dividing the at least one first area into a number of subsets comprises:
 at each border area node serving the at least one first area, originating an advertisement for a link to a pseudo-node representing the second area, the advertisement comprising an associated metric greater than half a maximal logical diameter of the associated first area; and   transmitting the advertisement into the associated at least one first area.   
     
     
         13 . The method of  claim 7 , further comprising assigning a respective unique identifier to each subset. 
     
     
         14 . The method of  claim 13 , wherein the respective unique identifier assigned to each a subset is a root-id. 
     
     
         15 . The method of  claim 14 , further comprising:
 receiving a multicast packet on a first area port of an area border node, the received multicast packet comprising a root-id;   determining that the root-id identifies a node-id within the subset associated with the receiving area border node;   replacing the root-id with the respective unique identifier of the subset associated with the receiving area border node; and   forwarding the at least one multicast packet through the second area port.   
     
     
         16 . The method of  claim 7 , wherein responsive to determining that the multicast packet is to be forwarded over at least one first area port, the method further comprises:
 responsive to determining that the root-id identifies another subset in the first area served by the receiving border area node, dropping the at least one received data packet; and   responsive to determining that the root-id does not identify another subset in the first area served by the receiving area border node:   replacing the root-id with a different root-id; and   forwarding the multicast packet through the subset associated with the receiving area border node.   
     
     
         17 . The method of  claim 7 , further comprising:
 receiving a unicast packet on a first area port of an area border node, the received unicast packet comprising a single destination address, the destination address identifying a node in the at least one first area not associated with a subset of the receiving area border node; and   forwarding the unicast packet on a different first area port.   
     
     
         18 . The method of  claim 7 , further comprising:
 receiving a unicast packet on a second area port of an area border node, the received unicast packet comprising a single destination address, the destination address identifying a node in the at least one first area not associated with a subset of the receiving area border node; and   forwarding the unicast packet on a second area port toward another area border node.