Hierarchical tree-based protection scheme for mesh networks

• US 7,203,743 B2
• Filed: 12/28/2001
• Issued: 04/10/2007
• Est. Priority Date: 12/28/2001
• Status: Active Grant

• Current Assignee: Ciena Corporation
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Shah-Heydari, Shahram
• Primary Examiner(s): Etienine; Ario
• Assistant Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US10/029,194
• Publication Number:
  US 20030126299A1
• Time in Patent Office: 1,929 Days
• Field of Search: 709/252, 709/238, 709/253, 709/251, 709/248, 709/249, 709/220, 709223-224, 707/10, 707/201, 707/100
• US Class Current: 709/223
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination

Abstract

In a hierarchical tree-based protection scheme, a node in a mesh network is designated as a root node of a spanning hierarchical protection tree and subsequently invites each adjacent node to become its child within the tree. If the inviting node provides a more capacious protection path to the root node than is currently enjoyed by the invitee, the invitee designates the inviting node as its primary parent and assumes a new tree position. Otherwise, the invitee designates the inviting node as a backup parent. A node assuming a new tree position invites all adjacent nodes except its parent to become its child. The invitations propagate throughout the network until a spanning hierarchical protection tree is formed. Upon a subsequent failure of a straddling link, the tree may be used to re-route data. Further, given a tree link failure, protection switching is quickly achieved at a disconnected node through use of a backup parent as the new primary parent. Dynamic tree reconfiguration in the event of network topology changes may be limited to the network area surrounding the change.

Claims

1. A method comprising:

extending a spanning hierarchical protection tree in a mesh network by;

at a current node, receiving an invitation to become a child of a first adjacent node;

if a minimum link bandwidth along a protection path from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.

2. The method of claim 1, further comprising:

if said minimum capacity along said protection path from said current node to said root node which visits the first adjacent node is not greater than said minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a backup parent of said current node in said tree.

3. The method of claim 2, wherein said backup parent is one of a number of backup parents of said current node, each one of said number of backup parents having a priority based on a minimum link bandwidth of a protection path from said current node to said root node which visits said one of said number of backup parents, with a higher minimum link bandwidth being associated with a higher priority.

4. The method of claim 3, further comprising ensuring that said designating of said first adjacent node as a primary parent of said current node does not introduce a loop into said spanning hierarchical protection tree.

5. The method of claim 1 further comprising:

subsequent to said extending, upon a failure of a link between the current node and any adjacent node that neither is designated as the primary parent of the current node in the tree nor designates the current node as its primary parent in the tree, re-routing network traffic intended for said any adjacent node to the adjacent node that is designated as the primary parent of the current node in the tree.

6. A computing device comprising:

a processor;

memory, in communication with said processor, storing processor readable instructions adapting said device to extend a spanning hierarchical protection tree in a mesh network by;

at a current node, receiving an invitation to become a child of a first adjacent node; and

if a minimum link bandwidth along a protection path from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.

7. The computing device of claim 6, wherein said memory further comprises instructions adapting said device to:

if said minimum link bandwidth along said protection path from said current node to said root node which visits the first adjacent node is not greater than said minimum link bandwidth of any existing protection path from said current node to said root node, designate said first adjacent node as a backup parent of said current node in said tree.

8. The computing device of claim 7, wherein said backup parent is one of a number of backup parents of said current node, each one of said number of backup parents having a priority based on a minimum capacity of a protection path from said current node to said root node which visits said one of said number of backup parents, with a higher minimum capacity being associated with a higher priority.

9. The computing device of claim 8, wherein said instruction further adapt said device to ensure that said designating of said first adjacent node as a primary parent of said current node does not introduce a loop into said spanning hierarchical protection tree.

10. The computing device of claim 6 wherein said memory further stores processor readable instructions adapting said device to, subsequent to said extending, upon a failure of a link between the current node and any adjacent node that neither is designated as the primary parent of the current node in the tree nor designates the current node as its primary parent in the tree, re-route network traffic intended for said any adjacent node to the adjacent node that is designated as the primary parent of the current node in the tree.

11. A computer readable medium storing computer software that, when loaded into a computing device, adapts said device to extend a spanning hierarchical protection tree in a mesh network by:

at a current node, receiving an invitation to become a child of a first adjacent node; and

if a minimum link bandwidth along a protection path from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.

12. The computer readable medium of claim 11, wherein said software is further capable of adapting said device by:

if said minimum link bandwidth along said protection path from said current node to said root node which visits the first adjacent node is not greater than said minimum link bandwidth of any existing protection path from said current node to said root node, designating said first adjacent node as a backup parent of said current node in said tree.

13. The computer readable medium of claim 12, wherein said backup parent is one of a number of backup parents of said current node, each one of said number of backup parents having a priority based on a minimum link bandwidth of a protection path from said current node to said root node which visits said one of said number of backup parents, with a higher minimum capacity being associated with a higher priority.

14. The computer readable medium of claim 13, wherein said software is further capable of adapting said device to extend a spanning hierarchical protection tree in a mesh network by ensuring that said designating of said first adjacent node as a primary parent of said current node does not introduce a loop into said spanning hierarchical protection tree.

15. The computer readable medium of claim 11 wherein said software further adapts said device to, Subsequent to said extending, upon a failure of a link between the current node and any adjacent node that neither is designated as the primary parent of the current node in the tree nor designates the current node as its primary parent in the tree, re-route network traffic intended for said any adjacent node to the adjacent node that is designated as the primary parent of the current node in the tree.

16. A computer readable medium storing computer software that, when loaded into a computing device, adapts said device to:

extend a spanning hierarchical protection tree in a mesh network by;

at a current node, receiving an invitation to become a child of a first adjacent node; and

if a minimum link bandwidth alone a protection oath from said current node to a root node of the spanning hierarchical protection tree which visits the first adjacent node is greater than a minimum link bandwidth of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node; and

reconnect a node disconnected from said spanning hierarchical protection tree in said mesh network to the spanning hierarchical protection tree by;

designating a backup parent of said disconnected node in said tree to be a primary parent of said disconnected node in said tree; and

from said disconnected node, sending an invitation to become a child of said disconnected node in said tree to each adjacent node of said disconnected node that is not said primary parent, said invitation providing an indication of a minimum link bandwidth of a protection path to a root node of the spanning hierarchical protection tree which visits said disconnected node.

17. A computer readable medium storing computer software that, when loaded into a computing device, adapts said device to connect an auxiliary node to a spanning hierarchical protection tree in a mesh network by:

requesting an invitation from each adjacent node of said auxiliary node for said auxiliary node to become a child of said adjacent node;

from each said adjacent node, receiving an invitation to become a child of said adjacent node; and

for each said adjacent node;

if a minimum link bandwidth along a protection path from said auxiliary node to a root node of the spanning hierarchical protection tree which visits said adjacent node is greater than a minimum link bandwidth of any existing protection path from said auxiliary node to said root node;

designating said adjacent node as a primary parent of said auxiliary node in said tree; and

from said auxiliary node, sending an invitation to become a child of said auxiliary node in said tree to each further adjacent node of said auxiliary node that is not said primary parent adjacent node.

18. The computer readable medium of claim 17, wherein said software is further capable of adapting said device to connect said auxiliary node to said tree by:

for each said adjacent node;

if said minimum link bandwidth along a protection path from said auxiliary node to said root node of the spanning hierarchical protection tree which visits said adjacent node is not greater than said minimum link bandwidth of any existing protection path from said auxiliary node to said root node, designating said adjacent node as a backup parent of said auxiliary node in said tree.

19. A computer-readable medium storing computer software that, when loaded into a computing device, adapts said device to extend a spanning hierarchical protection tree in a mesh network, comprising:

executable code for receiving, at a current node, an invitation to become a child of a first adjacent node;

executable code for, if a lowest bandwidth link of links of a protection path from said current node to a root of the spanning hierarchical protection tree which visits the first adjacent node is greater than a lowest bandwidth link of links of any existing protection path from said current node to said root node;

designating said first adjacent node as a primary parent of said current node in said tree; and

from said current node, sending an invitation to become a child of said current node in said tree to each adjacent node of said current node that is not said first adjacent node.