METHOD AND APPARATUS FOR EXCHANGING ROUTING INFORMATION AND ESTABLISHING CONNECTIVITY ACROSS MULTIPLE NETWORK AREAS

• US 20100020797A1
• Filed: 10/07/2009
• Published: 01/28/2010
• Est. Priority Date: 12/14/2006
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: BRAGG, Nigel Lawrence, CASEY, Liam M., ALLAN, David Ian, CHIABAUT, Jerome
• Granted Patent: US 8,270,319 B2
• Time in Patent Office: Days
• US Class Current: 370/390
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's

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.

Claims

1. A method for ensuring that multicast packets follow a same loop-free path as a path followed by unicast packets in a packet communication network, the packet communication network including at least one first area defined by a first level, each first area including a first plurality of nodes interconnected by a first set of links, each first area interconnected through at least one area border node to a second area defined by a second level, the second area including a second plurality of nodes interconnected by a second set of links, each area border node having at least one first level port connected to the at least one first area and a second level port connected to the second area, each multicast packet forwarded over the loop-free path including a header having a root-id identifying a root of a multicast tree, the method comprising:

receiving at least one data packet at an area border node; and

responsive to receiving a multicast packet at a second level 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 level 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 level ports, substituting a different root-id into the packet before forwarding the packet over the at least one first level port.

2. The method of claim 1, wherein the packet communication network is an Ethernet network.

3. The method of claim 1, wherein at least one first area is serviced by more than one area border node, the method further comprises dividing the at least one first area into a group of subsets, the group of subsets including an amount of subsets equal to an amount of area border nodes servicing the first area, each subset associated with a specific area border node.

4. The method of claim 3, wherein each subset includes nodes having a shortest path to the associated area border node.

5. The method of claim 3, wherein dividing the at least one first area into a group of subsets comprises:

each area border node originating an advertisement for a link to a pseudo node representing the second area, the advertisement including an associated metric greater than half a maximal logical diameter of the associated first areas; and

transmitting the advertisement into its associated first areas.

6. The method of claim 5, further comprising assigning a unique identifier to each subset.

7. The method of claim 6, wherein a unique identifier for a subset is included in the advertisement as a root-id.

8. The method of claim 7, wherein the at least one received data packet is a multicast packet received on a first level port, the at least one received data packet including a root-id, the method further comprises:

determining that the root-id identifies a node within the subset associated with the receiving area border node;

replacing the root-id with the unique identifier of the subset associated with the receiving area border node; and

forwarding the at least one data packet through the second level port.

9. The method of claim 3, wherein responsive to determining that the multicast packet is to be forwarded over at least one of the first level ports, the method further comprises:

responsive to determining that the root-id identifies another subset in the first area served by the receiving area border 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 at least one data packet through the subset associated with the receiving area border node.

10. The method of claim 3, wherein the at least one received data packet is a unicast packet including a single destination address, the destination address identifying a node in the first area not associated with a subset of the receiving area border node, the method further comprises:

responsive to receiving the at least one data packet on a first level port, forwarding the at least one data packet through a different first level port; and

responsive to receiving the at least one data packet on a second level port, forwarding the at least one data packet through the second level port towards another area border node.

11. An area border node for use in a packet communication network, the packet communication network including at least one first area defined by a first level, each first area including a first plurality of nodes interconnected by a first set of links, each first area interconnected to through at least one area border node to a second area defined by a second level, the area border node comprising:

at least one first level port connected to each first area, the at least one first level port operable to receive data packets from and transmit data packets to the corresponding first area;

a second level port connected to the second area, the second level port operable to receive data packets from and transmit data packets to the second area;

at least one processor electrically connected to the at least one first level port and to the second level port, responsive to receiving a multicast packet at a second level port, the multicast packet including a header having a root-id identifying a root of a multicast tree,

the processor is operable to;

examine the root-id of the multicast packet;

determine whether the multicast packet is to be forwarded on at least one of the first level 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 level ports, substituting a different root-id into the packet before initiating forwarding of the packet over the at least one first level port.

12. The area border node of claim 11, further comprising:

at least one memory electrically connected to at least one processor, the at least one memory including;

a first forwarding information base (“

FIB”

) associated with the at least one first level port; and

a second forwarding information base (“

FIB”

) associated with the second level port;

wherein the at least one processor is operable to;

forward a data packet received on the at least one first level port according to the first FIB; and

forward a data packet received on the second level port according to the second FIB.

13. The area border node of claim 11, wherein at least one first area is serviced by more than one area border node, the processor is further operable to divide the at least one first area into a group of subsets by transmitting an advertisement for a link to a pseudo node representing the second area into its associated first areas through the at least one first level port, the group of subsets including an amount of subsets equal to an amount of area border nodes servicing the at least one first area, each subset associated with a specific area border node, the subset associated with the area border node including only nodes having a shortest path to the associated area border node, the advertisement including an associated metric greater than half a maximal diameter of the associated first areas.

14. The area border node of claim 13, wherein a unique identifier is assigned to each subset, the unique identifier for one subset included in the advertisement as a root-id.

15. The area border node of claim 14, wherein responsive to receiving a multicast packet at a first level port, the multicast packet including a header having a root-id identifying a root of a multicast tree,

the at least one processor is further operable to:

determine that the root-id identifies a node within the subset associated with the receiving area border node;

replace the root-id with the unique identifier of the subset associated with the receiving area border node; and

forward the at least one data packet through the second level port.

16. The area border node of claim 13, wherein responsive determining that the multicast packet is to be forwarded over at least one of the first level ports, the processor is further operable to:

responsive to determining that the root-id identifies another subset in the first area served by the area border node, drop 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 area border node;

replace the root-id with a root-id for a second level pseudo node; and

forward the at least one data packet through the subset associated with the area border node.

17. The area border node of claim 13, wherein responsive to receiving a unicast packet including a single destination address, the destination address identifying a node in the first area not associated with a subset of the area border node, the processor is further operable to:

responsive to receiving the at least one data packet on an a first level port, forward the at least one data packet through a different first level port; and

responsive to receiving the at least one data packet on the second level port, forward the at least one data packet through the second level port towards another area border node.

18. A packet communication system comprising:

at least one first area, each first area configured as an link state protocol controlled Ethernet network area, each first area including a first plurality of nodes interconnected by a first set of links; and

a second area configured as an link state protocol controlled Ethernet network area, the second area including a second plurality of nodes interconnected by a second set of links, the second area interconnected to each first area;

at least one area border node interconnecting the second area to each first area, the at least one border node operable to serve two or more disjoint first areas, each area border node including;

a second level port connected to the second area, the second level port operable to receive data packets from and transmit data packets to the second area;

at least one first level port operable connected to each first area, the at least one first level port operable to receive data packets from and transmit data packets to the corresponding first area;

at least one processor electrically connected to the second level port and to the at least one first level port,

responsive to receiving a multicast packet at a second level port, the multicast packet including a header having a root-id identifying a root of a multicast tree,

at least one processor is operable to;

examine the root-id of the multicast packet;

determine whether the multicast packet is to be forwarded on at least one of the first level 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 level ports, substituting a different root-id into the packet before initiating forwarding of the packet over the at least one first level port.

19. The packet communication network of claim 18, wherein at least one first area is serviced by more than one area border node, the at least one first area is partitioned into a group of subsets, the group of subsets including an amount of subsets equal to an amount of area border nodes servicing the corresponding first area, each subset associated with a specific area border node, the subset associated with the area border node including only nodes having a shortest path to the associated area border node.

20. The packet communication network of claim 19, wherein the area border node represents in an advertisement transmitted into its associated first areas through the at least one first level port that there is a link to a pseudo node representing the second area, the advertisement including an associated metric greater than half a maximal diameter of the associated first areas.