Method for selecting nodes in a network

• US 7,706,286 B2
• Filed: 07/08/2008
• Issued: 04/27/2010
• Est. Priority Date: 07/08/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Karloff, Howard
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US12/217,705
• Publication Number:
  US 20100008368A1
• Time in Patent Office: 658 Days
• Field of Search: None
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/128 for finding disjoint paths

Abstract

Given a set of network nodes B that are sought to be monitored, and a set of potential monitoring nodes, a subset M of the monitoring nodes is chosen that insures monitoring each node b in B with a pair of nodes m_i and m_j such that no node except b is on both any shortest path from b to m_i and on any shortest path from b to m_j. Some of the nodes in M are chosen in a first step by identifying a subset of B having nodes b that are “t-good” nodes, choosing a subset of potential monitoring nodes as First Partner nodes, and choosing a corresponding subset of potential monitoring nodes as Second Partner nodes. Others are chosen in a second step that handles nodes b that are not “t-good,” using a greedy algorithm.

Claims

1. A method executed in one or more processing modules for identifying a set of type-A nodes from a set of nodes m of a network having a working association with a set B of nodes b of said network, said nodes m are nodes that are not precluded from installing a processing module of said processing modules, hereinafter also referred to as potential type-A nodes, comprising the steps of:

identifying a subset T of nodes b that are t-good, where a node m_k is good for node b_j if all lowest-cost paths from node b_j to node m_k leave node b_j on one and the same link, and node b_j is t-good if at least t of the potential type-A nodes are good for b_j, where t is a preselected positive integer not greater than the number of said potential type-A nodes;

then, choosing a subset of said potential type-A nodes as type-A nodes, such that that for each t-good node b in T, at least one node of the type-A nodes is good for node b;

then, choosing zero or more additional ones of said potential type-A nodes as type-A nodes to cause a pair of two distinct type-A nodes m_i and m_j to exist for each t-good node b in T that is not also a type-A node, such that no node other than node b is on any lowest-cost path from b to m_i and on any lowest-cost path from b to m_j;

then, if there are nodes b in B that are not t-good, choosing zero or more additional ones of said potential type-A nodes as type-A nodes to provide, for each node b_p in B that is not t-good,

(a) one type-A node if said node b_p in B that is not t-good is also a potential type-A node, or

(b) a pair of type-A nodes, m_i and m_j, such that no node other than said node b_p is on any lowest-cost path from b_p to m_i and on any lowest-cost path from b_p to m_j.

2. The method of claim 1 where said type-A nodes are monitoring nodes, and said nodes b are nodes to be monitored.

3. The method of claim 1 further comprising a step of minimalizing the set of those of said potential type-A nodes that were chosen as type-A nodes.

4. A method executed in one or more processing modules for choosing nodes from a given set M of network nodes, where nodes in said set M are not precluded from installing a processing module of said processing modules and where the chosen nodes have a specified working relationship with nodes b from a set B of said network nodes, referred to herein as branch nodes, comprising the steps of:

identifying a subset T of branch nodes, b^T, that satisfy a preselected criterion;

choosing, by means of a first algorithm, for each node b^T, a pair of nodes from set M consisting of a first partner (FP) nodes and a second partner (SP) node, such that all shortest paths from said each node b^T, to the chosen FP node are disjoint from all shortest paths from said each node b^T, to the chosen SP node;

selecting, by means of a second algorithm that is qualitatively different from the first algorithm, for each of said branch nodes that are not in subset T, b^T a pair of nodes from set M consisting of a first partner (FP) node and a second partner (SP) node, such that that all shortest paths from said each node b^T, to the selected FP node are disjoint from all shortest paths from said each node b^T, to the selected SP node.

5. The method of claim 4 where the first algorithm is a hitting set heuristic.

6. The method of claim 4 where said hitting set heuristic comprises a process for identifying nodes b that belong to subset T.

7. The method of claim 4 where said process for identifying said nodes b that belong to subset T is one where

a branch node b_j belongs to set T if it is t-good,

said branch node b_j is t-good when it is good for at least t nodes in set M, where t is a preselected scalar, and

said branch node b_j is good for node m_k in set M if all lowest-cost paths from node b_j to node m_k leave node b_j on one and the same link.

8. The method of claim 7 where said first algorithm comprises a first process for choosing the FP nodes and a second process for choosing the SP nodes.

9. The method of claim 8 where the first process comprises the steps of:

populating cells of a table having two dimensions, where a first dimension is rows of said table and the second dimension is columns of said table, where said branch nodes in subset T correspond to one dimension of the table and the nodes in set M are the second dimension of the table, by placing in a cell a 1 if the branch node that is associated with the cell is good for the set-M node that is associated with the cell;

identifying one or more of said set-M nodes that each has a largest number of associated cells that contain a 1;

selecting one of the set-M nodes identified in said step of identifying as said FP node and identifying nodes that are hit by the selected FP node, identified by a 1 in column of cells corresponding to the selected FP node;

for each branch node that is hit by a selected FP node, identifying an outgoing link from said each branch node on its least-cost path toward said selected FP node, and removing said branch node from said table;

returning to said step of identifying when said table is not empty, and terminating said first process otherwise.

10. The method of claim 8 where a branch node that is also a set-M node is treated as being good for said set-M node.

11. The method of claim 10 where, when said step of identifying set-M nodes identifies more than one of said set-M nodes, and one of the identified node is a branch node, the step of selecting then selects as said FP node the set-M node that is also a branch node.

12. The method of claim 7 where said first process comprises the steps of:

populating cells of a table having two dimensions, where a first dimension is rows of said table and the second dimension is columns of said table, where said branch nodes in subset T correspond to one dimension of the table and the set-M nodes are the other dimension of the table, by placing in each cell corresponding to branch node b_i and set-M node m_j the identity of outgoing link of each lowest-cost path from b_i to m_j;

identifying one or more of said set-M nodes that each has a largest number of associated cells that contain a single entry;

selecting one of the set-M nodes identified in said step of identifying as FP node and identifying nodes that are hit by the selected FP node, identified by a single outgoing link entry in the cells in column of cells corresponding to the selected FP node;

for each branch node that is hit by the selected FP node, identifying outgoing link from said each branch node on its least-cost path toward said FP node, and removing said branch node from said table;

returning to said step of identifying when said table is not empty, and terminating said first process otherwise.

13. The method of claim 7 where said second process comprises the steps of:

populating cells of a table having two dimensions, where a first dimension is rows of said table and the second dimension is columns of said table, where said branch nodes in set T, less those of said branch nodes that are also FP nodes correspond to one dimension of the table and the set-M nodes are the other dimension of the table, by placing a 1 in a cell if the branch node that is associated with the cell and the set-M node that is associated with the cell are such that all least cost paths from the branch node that is associated with the cell to the set-M node associated with the cell do not use the identified outgoing link;

identifying one or more of said set-M nodes that each has a largest number of associated cells that contain a 1;

selecting one of the set-M nodes identified in said step of identifying as SP node;

removing from said table those branch nodes that are hit by the selected SP node;

returning to said step of identifying when said table is not empty, and terminating said second process otherwise.

14. The method of claim 5 where the second algorithm is a greedy algorithm.

15. The method of claim 7 where t=1.

16. The method of claim 7 where

17. The method of claim 7 where t is an integer portion of a preselected fraction of number of said set-M nodes.