Processing data signals

• US 6,374,202 B1
• Filed: 03/10/1998
• Issued: 04/16/2002
• Est. Priority Date: 07/16/1996
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Robinson, Gerald
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Thomson, William
• Application Number:
  US09/029,934
• Time in Patent Office: 1,498 Days
• Field of Search: 703/13, 703/14, 703/21, 703/23, 703/24, 709/223, 709/224, 709/220, 709/221, 709/222
• US Class Current: 703/13
• CPC Class Codes: H04Q 3/0079 involving restoration of networks, e.g. disaster recovery, self-healing networks

Abstract

A network'"'"'s components are represented in the form of data signals arranged into a hierarchical tree structure. A population comprising a large number of randomly created tree structures, each relating to an individual network, is generated. The tree structures undergo a process of evolution through successive generations, by selectively breeding the most successful tree structures. Through the process of breeding, one or a plurality of optimal tree structures emerges. A network is constructed in accordance with the data signals represented by the optimal tree structure. The network may be any network comprising a set of nodes and links, e.g. a gas pipeline network, an electricity supply network, a water pipeline network or the like, but the disclosure is particularly relevant to a telecommunications network or a computer network.

Claims

1. A method of designing a telecommunications network having a plurality of switching nodes interconnected by a plurality of links, the method comprising:

(a) establishing a population of randomly generated tree structures comprising switching node signals and connecting signals;

(b) converting the population established by step (a) into corresponding network designs;

(c) testing said corresponding network designs for viability;

(d) testing for fitness those network designs which pass the viability test of step (c);

(e) determining from those network designs which pass the fitness test of step (d) a preferred network design;

(f) establishing a new population of tree structures comprising tree structures generated by genetic evolution from randomly generated tree structures representing network designs which pass the fitness test of step (d);

(g) converting the new population of tree structures established by step (f) into corresponding network designs;

(h) repeating steps (c), (d), (e) and (f) thereby obtaining a succession of respective preferred network designs; and

(i) determining from said succession of respective preferred network designs a most preferred network design,

wherein the step (a) comprises the sub-steps of;

(a1) randomly generating a tree structure comprising switching node signals and connecting signals;

(a2) converting the randomly generated tree structure into a corresponding network design;

(a3) selecting the randomly generated tree structure as a member of the population if it passes the viability test of step (c);

(a4) repeating steps (a1), (a2) and (a3) until the population reaches a predetermined size; and

wherein

each said connecting signal has a left argument and a right argument and is either a link signal or a graft signal,

each link signal argument is a switching node signal or another link signal, and

each graft signal argument is a link signal or another graft signal.

2. A method according to claim 1, wherein the switching node signals of each of the tree structures have unique identifiers in accordance with a given tree traversal convention, and the connecting signals of each of the tree structures have unique identifiers in accordance with that tree traversal convention, and wherein step (f) comprises the substeps of:

(f1) interchanging a subtree of a first of the tree structures representing network designs which pass the fitness test of step (d) with a subtree of a second of the tree structures representing network designs which pass the fitness test of step (d) and thereby generating two offspring tree structures;

(f2) verifying that the respective unique identifiers of the switching node signals and connecting signals of the newly generated offspring tree structures are consistent with that tree traversal convention; and

in the event that a switching node signal or connecting signal of a newly generated offspring tree structure is found by substep (f2) to have an identifier that is inconsistent with that tree traversal convention,

(f3) determining a correct value for that inconsistent identifier; and

(f4) changing all occurrences of that inconsistent identifier in the offspring tree structure into said correct value.

3. A method according to claim 2, wherein the substep (f2) comprises the substeps of:

(f2.1) in the event that, in accordance with that given tree traversal convention, a node signal is encountered having a number which is more than one higher than the highest consecutive node signal number allocated so far in a renumbering process, renumbering that node signal so encountered to be one higher than the highest consecutive node signal number allocated so far in the renumbering process; and

(f2.2) changing any reference of the tree structure which refers to that node signal by using its previous number to a reference which refers to that node signal by using its new number.

4. A computer-readable medium containing computer-executable program instructions for performing the method of claim 1.

5. A computer system programmed to perform the method of claim 1.

6. A method according to claim 1, wherein substep (a2) comprises the substeps of:

(a2.1) traversing the tree structure and upon encountering a tree node formed by a connecting signal,

(a2.2) if that connecting signal is a graft signal, searching respective sub-trees formed by the left and right arguments of that connecting signal to find any existing link therebetween,

(a2.2.1) if no such link between the respective sub-trees is found, creating a new link between an external tree node of one of the respective sub-trees and an external tree node of the other of the respective sub-trees;

(a2.3) if that connecting signal is a link signal, searching said respective sub-trees to find any existing link between a first switching node signal of the sub-tree formed by the left argument of that connecting signal and a second, different, switching node signal of the respective sub-tree formed by the right argument of that connecting signal,

(a2.3.1) if no such link between the said first and second switching node signals is found, creating a new link between said first and second switching node signals; and

(a2.4) if no such second, different, switching node signal is found in the sub-tree formed by the left argument of that connecting signal, converting that connecting signal to a graft signal, and performing substep (a2.2).

7. A method according to claim 6, wherein substep (a2.2.1) comprises selecting said external tree nodes of the respective sub-trees on the basis of the shortest physical distance between actual telecommunications network nodes represented by external tree nodes of the respective sub-trees.

8. A method according to claim 7, wherein, in substep (a2.2.1), if said shortest physical distance is greater than a predetermined value, the creation of a new link between the selected external tree nodes comprises creating a tree node formed by a switching node signal and representing an switching node intermediate said actual telecommunications network nodes represented by external tree nodes of the respective sub-trees.

9. A method according to claim 1, wherein the switching nodes represent pieces of node equipment and the locations of the pieces of equipment.

10. A method according to claim 1, wherein step (d) comprises testing against a cost criteria.

11. A method according to claim 1, wherein the link signals are used to create sub-trees and the graft signals are used to connect the sub-trees into an overall tree structure having a single root.

12. A computer-readable medium containing computer-executable program instructions for performing the method of claim 11.

13. A computer system programmed to perform the method of claim 11.

14. A method according to claim 1, wherein the link signals describe information about physical link equipment and their connection pattern to switching node equipment and the graft signals denote the joining of physical links or sub-networks at switching node equipment.