Abstract:
A computer readable storage medium includes a set of instructions executable by a processor. The instructions are operable to receive a node indication for each of a plurality of undamaged backbone nodes of a communication network; receive a link indication for each of a plurality of backbone links connected between undamaged backbone nodes of the communication network; and assign a fragment identifier to each of a plurality of backbone fragments, each of the backbone fragments comprising one or more of the backbone nodes, wherein the one or more backbone nodes comprising each backbone fragment indicates connectivity between the one or more backbone nodes.

Description:
BACKGROUND 
       [0001]    Modern telecommunications networks typically comprise complicated, interconnected networks of nodes and links. Network providers strive to provide service to their customers both during normal operations and during situations when the network is damaged, either moderately or severely. In order to insure that service can be provided in situations when a network is damaged, providers may use modeling algorithms to analyze various possible failure scenarios. Because networks with large numbers of nodes and links may have a correspondingly large number of failure scenarios, such modeling algorithms should be as simple as possible in order for them to execute quickly and thus be able to model complicated systems in a reasonable amount of time. 
       SUMMARY OF THE INVENTION 
       [0002]    The present invention is directed to a computer readable storage medium including a set of instructions executable by a processor. The instructions are operable to receive a node indication for each of a plurality of undamaged backbone nodes of a communication network; receive a link indication for each of a plurality of backbone links connected between undamaged backbone nodes of the communication network; and assign a fragment identifier to each of a plurality of backbone fragments, each of the backbone fragments comprising one or more of the backbone nodes, wherein the one or more backbone nodes comprising each backbone fragment indicates connectivity between the one or more backbone nodes. 
         [0003]    The present invention is further directed to a system including a memory and a processor. The memory stores a representation of a plurality of network components, the network components including backbone components. The processor is configured to receive a fragmentation of the network components and to assign one of a plurality of unique identifiers to each of a plurality of fragments of the backbone corresponding to the fragmentation. 
         [0004]    The present invention is further directed to a computer readable storage medium including a set of instructions executable by a processor. The instructions are operable to receive a node indicator for each of a plurality of backbone nodes of a communication network; receive a link indicator for each of a plurality of backbone links of a communication network, wherein the backbone links connect two or more backbone nodes; receive a damage indication of one or more of the backbone nodes; and assign a fragment identifier to each of one or more undamaged backbone nodes in backbone fragments, each backbone fragment comprising undamaged backbone nodes that are connected, directly or indirectly, by backbone links. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]      FIG. 1   a  shows an exemplary communications network that may be modeled by the exemplary embodiments of the present invention. 
           [0006]      FIG. 1   b  shows the exemplary network of  FIG. 1   a  while experiencing an exemplary failure scenario, which will be used to illustrate the operation of the exemplary embodiments of the present invention. 
           [0007]      FIG. 2  shows an exemplary embodiment of a method according to the present invention. 
           [0008]      FIG. 3   a  shows a first version of an array of nodes to be generated by the exemplary method of  FIG. 2 . 
           [0009]      FIG. 3   b  shows a second version of an array of nodes to be generated by the exemplary method of  FIG. 2 . 
           [0010]      FIG. 3   c  shows a third version of an array of nodes to be generated by the exemplary method of  FIG. 2 . 
           [0011]      FIG. 3   d  shows a fourth version of an array of nodes to be generated by the exemplary method of  FIG. 2 . 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    The exemplary embodiments of the present invention may be further understood with reference to the following description and the appended drawings, wherein like elements are referred to with the same reference numerals. The exemplary embodiments describe methods and systems for modeling connectivity between multiple end points attached to a network that is subjected to multiple failures. 
         [0013]    It should initially be noted that the exemplary embodiments will be described with reference to a Voice over Internet Protocol (“VoIP”) network. Thus, the specific end points described and analyzed in the description of the exemplary embodiments will be those appropriate to this type of network. However, the exemplary methods and systems may be equally applicable to any other type of problem involving a need to validate connectivity between multiple end points attached to a common network or other type of graph. 
         [0014]    Providers of communication networks employ various modeling techniques to evaluate network survivability under a variety of hypothetical damage/outage scenarios. The total number of scenarios that must be analyzed is often extremely large. For example, in a network with 25 nodes and 100 links, there are over 10,000,000 different combinations involving the failure of one, two, three or four links or nodes; the total number of multiple failure scenarios is over 4.25×10 37 . Further, for each scenario, the connectivity between a large number of equipment pairs must be analyzed. For example, in a network with 1,000 users, an assessment of connectivity between all user pairs requires analysis of roughly 1,000,000 pairs of users. Additionally, more complex call flows, which may involve network validation, routing, and service processing equipment, require connectivity analysis for an even larger number of pairs of end points. Thus, it is extremely important to enhance the speed of the modeling of such networks. Faster modeling may enable more failure scenarios to be analyzed, resulting in more accurate survivability evaluations. 
         [0015]      FIG. 1   a  illustrates an exemplary communication network  100  in an undamaged state. As stated above, the exemplary network  100  is a VoIP network. The elements described herein will therefore be those appropriate to this type of network, but as stated above, the broader principles of the invention may be equally applicable to other types of networks. The network  100  includes eight backbone nodes  111 ,  112 ,  113 ,  114 ,  115 ,  116 ,  117  and  118 . These nodes may be, for example, backbone routers. The backbone nodes  111 - 118  are connected to one another by eleven backbone links  121 ,  122 ,  123 ,  124 ,  125 ,  126 ,  127 ,  128 ,  129 ,  130  and  131 , shown on  FIG. 1   a  as thick solid lines. These may be, for example, high-capacity trunk data links. 
         [0016]    The exemplary network  100  also includes two user nodes  141  and  142 , which may represent various types of user equipment capable of connecting to the network  100 , such as a computer with VoIP software. Those of skill in the art will understand that the precise number and relationship of the various components shown in the network  100  of  FIG. 1   a  is only exemplary, and that the number, relationship and function of components and links in other networks may be significantly greater than shown and may vary from network to network. Further, those of skill in the art will understand that a real-world VoIP implementation may include processing nodes, routing nodes, etc., but that these are not shown in  FIGS. 1   a  and  1   b  as they are not relevant to the exemplary method to be described below. 
         [0017]    Typically, a VoIP call may require connectivity to different network nodes. A call placed by a first user to a second user may require that the first user connect to a routing node, then to a processing node, and finally directly to the second user. For clarity,  FIG. 1   a  only illustrates user nodes  141  and  142 . These nodes may be, for example, private branch exchanges (“PBX”). The user node  141  is connected to the network  100  via access link  151 , which connects it to backbone node  111 ; the user node  142  is connected to the network  100  via access links  152  and  153 , which connect it to backbone nodes  113  and  117  respectively. The access links  151 - 153  may typically have lower capacity than the backbone links  121 - 131 . The access links are illustrated in  FIG. 1   a  as thin solid lines. 
         [0018]    It will be apparent to one of skill in the art that a properly designed network that has suffered no damage or outage, as illustrated in  FIG. 1   a , will provide for all necessary connectivity. In this example, the user node  141  may connect to the user node  142  via access link  151 , backbone node ill, backbone link  121 , backbone node  114 , backbone link  124 , backbone node  113  and access link  152 . Generally, networks such as the network  100  are designed to withstand single node or link failure without significant performance degradation. Thus, connectivity is generally available in such a case. For example, in the event of a single outage of backbone node  114 , a connection between users  141  and  142  could still be accomplished via backbone nodes  111 ,  116 ,  115  and  117 . 
         [0019]    However, as discussed above, a main goal of the exemplary embodiments is to model situations where a network has suffered damage or outage. Those of skill in the art will understand that damage may be due to natural disasters (e.g., hurricanes, earthquakes, etc.), due to manmade disasters (e.g., steam pipe explosions, acts of war, etc.), or due to network-related outages (e.g., software failure, power failure, etc.). The exemplary embodiments described herein may discover all backbone fragments that may have been isolated from one another due to such damage. Backbone fragmentation may then cause a loss of connectivity between, for example, user nodes within a network. Referring to the network  100 , as long as user nodes  141  and  142  are connected to at least one common backbone fragment, they are thus connected to one another, and may communicate with one another through the backbone network (e.g., nodes  111 - 118  and links  121 - 131 ). If, however, the nodes  141  and  142  are connected to different fragments (e.g., there is no common backbone fragment shared by the two), they are then rendered unable to communicate with one another by the modeled damage scenario. Thus, discovering isolated network fragments is an important part of modeling network survivability. 
         [0020]      FIG. 1   b  illustrates damaged network  101 , which is network  100  in a damaged state. In damaged network  101 , backbone nodes  114  and  115  have suffered damage and are unavailable to handle network traffic.  FIG. 1   b  illustrates damaged nodes  114  and  115  grayed out and the links that connect to those nodes (e.g., backbone links  121 ,  123 ,  124 ,  126 ,  127 ,  128 ,  129  and  130 ) as dashed lines. 
         [0021]      FIG. 2  illustrates an exemplary method  200  according to the present invention. The method  200  will be described with reference to the damaged network  101  of  FIG. 1   b . Those of skill in the art will understand that the method  200  represents the evaluation of a single network failure scenario, and that a real-world implementation of the method  200  will repeat as a plurality of possible failure scenarios are evaluated. In the exemplary method  200 , each fragment of the damaged network  101  is assigned a unique identifier. The method  200  describes an embodiment wherein the unique identifiers are colors, which may be preferable for a graphical representation of the fragmented network; however, those of skill in the art will understand that the unique identifiers may also be numbers, letters, words, place designations, network component designations, etc., or any other type of identifier that may be used to distinguish the various isolated backbone fragments from one another. 
         [0022]    In step  210 , the network elements (e.g., nodes) are received. These may be stored into an array with a size N equal to the number of nodes in the scenario to be analyzed. It should be noted that only functioning nodes are received in this step (e.g., in the damaged network  101 , nodes  111 ,  112 ,  113 ,  116 ,  117  and  118 , but not nodes  115  and  116 ). The array may initially include a pointer from the array name to the first node and from each node to the next node.  FIG. 3   a  illustrates an exemplary initial array  300  for the damaged network  101  described above. 
         [0023]    In step  220 , the network links are received and processed. For a link between two nodes A and B, the array entry for node A will reflect that node B is its neighbor, and vice versa. As for step  210 , only functioning links are received in step  220 .  FIG. 3   b  illustrates exemplary linked array  301 , which is the array  300  of  FIG. 3   a  with neighboring nodes added. 
         [0024]    In step  230 , the method determines whether any uncolored nodes remain. If so, the method continues to step  240 . If all nodes have been colored, the method terminates. In step  240 , the next unused color is selected. For example, when the method begins, as no colors have been used, COLOR 1  is the first unused color. For example, COLOR 1  may be yellow. 
         [0025]    In steps  250  and  260 , the first node that has not yet been assigned a color is removed from the uncolored list and added to the list for the currently selected color. The selected node is marked with the appropriate color in the node array. Additionally, in step  270  all uncolored neighbors of the selected node are assigned the selected color. For example, if the selected node is ill and the selected color is yellow, then node  111  and node  116  will be assigned the color yellow. Also in step  270 , all newly colored nodes are removed from the uncolored node list and appended to the end of the current color node list. Pointers are updated to reflect the new first uncolored node, the first node of the current color, and any subsequent nodes of the current color. Subsequently, in the loop including steps  270 - 290 , all uncolored neighbors of the remaining entries in the group are assigned the current color. Pointers are again updated. Those of skill in the art will understand these steps may continue to repeat as long as new nodes are added to the group. Continuing with the above example, node  118  is assigned the color yellow in this step as it is a neighbor of step  116 . 
         [0026]    Once it is determined, in step  280 , that the current node is the last in the list (e.g., no more neighboring nodes have been assigned the current color), the method returns to step  230 , where it is again determined whether there are uncolored nodes remaining. If so, the method returns to step  240  and continues with the next color, to be assigned to the next fragment of the network. If no uncolored nodes remain, the method terminates. 
         [0027]    The application of the method  200  to the damaged network  101  may proceed as follows. In steps  210  and  220 , the survived nodes ( 111 ,  112 ,  113 ,  116 ,  117  and  118 ) and links ( 122 ,  125 ,  131 ) are received, resulting in the node array as illustrated in  FIG. 3   b . In step  240 , the first color COLOR 1  (e.g., yellow) is selected for assignment. In steps  250  and  260 , the first uncolored node  111  is assigned the first color COLOR 1 . In step  270 , node  116 , a neighbor of node  111 , is also assigned COLOR 1 . Next, in steps  280  and  290 , the method continues with the analysis of the neighbors of node  116 . In step  270 , COLOR 1  is assigned to node  118 , as it is a neighbor of node  116 .  FIG. 3   c  illustrates array  302 , which is the array  300  at this point in the exemplary application of the method. At this point, the discovery of the first (e.g., “yellow”) network fragment is completed. Nodes  111 ,  116  and  118  have been assigned COLOR 1 ; nodes  112 ,  113  and  117  remain uncolored. The uncolored pointer is to node  112 , the first uncolored node, and subsequently to nodes  113  and  117 ; the COLOR 1  pointer is to node  111 , and subsequently to nodes  116  and  118 . 
         [0028]    Continuing with the exemplary application of the method  200 , after step  280  the method returns to step  230 , in which it is determined that uncolored nodes remain in the uncolored node list. Thus, the method progresses to step  240 , where COLOR 2  (e.g., green) is selected. In step  260 , COLOR 2  is assigned to the first remaining uncolored node, node  112 . The COLOR 2  pointer is assigned to node  112 , and the uncolored pointer is assigned to node  113 , the new first remaining uncolored node. No additional nodes are assigned COLOR 2  in step  270 , as node  112  borders no other functioning nodes. At this point, the discovery of the second (e.g., “green”) network fragment is completed. In step  280 , the method determines that the current node  112  is the last in the COLOR 2  list, so it returns to step  230 , in which it is again determined that uncolored nodes remain, so the method again proceeds to step  240  to discover the next network fragment. 
         [0029]    In the third iteration of step  240 , COLOR 3  (e.g., blue) is selected. In step  260 , COLOR 3  is assigned to the first uncolored node, node  113 . COLOR 3  is then also assigned to node  117 , as a neighbor of color  113 , in step  270 . The COLOR 3  pointer is updated to point to node  113 , and subsequently from node  113  to node  117 . At this point, the discovery of the third (e.g., “blue”) network fragment is completed. The uncolored pointer is eliminated, as no uncolored nodes remain. No changes take place in the ensuing loop including step  280 ,  290 ,  270  and  280 , as all nodes have been colored. The method again returns to step  230 , in which it is determined that no uncolored nodes remain, and the method terminates.  FIG. 3   d  illustrates the array  303 , which is the array  300  at the conclusion of the execution of the exemplary method  200 . 
         [0030]    The exemplary method  200  provides for a more rapid assessment of network fragmentation than prior methods. Step  210  may be accomplished on the order of O(N) time, where N is the number of backbone nodes in the network  100 , as there are several fixed actions performed for each node. Step  220  may be completed in O(M) time, where M is the number of backbone links between backbone nodes in the network  100 ; as for step  210 , there are a number of fixed actions taken per link. Finally, the iteration of the loop comprising steps  230 - 260  may be completed in O(N)+O(M) time. Each node is moved once from uncolored to one of the colored lists (e.g., as in steps  260  and  270 ). Subsequently, each node may be accessed again when all its neighbors are examined (e.g., as in steps  270  and  290 ). These activities may be accomplished in O(N) time based on the number of nodes. Furthermore, each node may be accessed again to see if the node is already colored (and possibly to color it) when it represents a neighbor node for the currently analyzed node (e.g., as in step  270 ). Examination and selective coloring of all pairs of neighbors in the network in step  270  may be accomplished in O(M) time based on the number of links since each surviving link will be accessed twice, first to inspect and possibly to color the second link endpoint when the first endpoint is being examined, and again to inspect and possibly to color the first link endpoint when the second endpoint is being examined. Total time for the loop is thus O(N) plus O(M) as stated above. 
         [0031]    Adding all estimates, execution time for the exemplary method  200  is O(N)+O(M). Further, because in typical service provider networks the number of links M is usually much greater than the number of nodes N, the execution time may be expressed as simply O(M). In prior art methods, isolated network fragments may be determined by minimum spanning tree algorithms, such as Kruskal&#39;s, Prim&#39;s or Sollin&#39;s algorithms. These algorithms may typically complete in O(M log N) time, where, as above, M is the number of backbone links and N is the number of backbone nodes. It will be obvious to those of skill in the art that this execution time is larger than the execution time of the exemplary method  200  for any network of reasonable size. 
         [0032]    By the application of the exemplary method  200 , fragmentation of a damaged network may be assessed. Each group of backbone nodes represented by a single color or other unique identifier may represent a single isolated fragment of the network. As such, each node within a single group may communicate with every other node within the group, either directly or indirectly; nodes that are connected to one another by a single backbone link may be considered as connected directly, while nodes that are connected to each other through two or more backbone links and one or more intermediate backbone nodes may be considered as connected indirectly. Conversely, a node in one group may be incapable of communicating with nodes in other groups. 
         [0033]    It will be apparent to those skilled in the art that various modifications may be made in the present invention, without departing from the spirit or the scope of the invention. Thus, it is intended that the present invention cover modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.