Design of communications networks

• US 20030181210A1
• Filed: 03/07/2003
• Published: 09/25/2003
• Est. Priority Date: 09/15/2000
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Shipman, Robert A
• Granted Patent: US 7,385,936 B2
• Time in Patent Office: Days
• US Class Current: 455/446
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04Q 3/0083 Network planning or design; Modelling of planned or existing networks

Abstract

An apparatus and method are provided for designing at least a part of a communications network beginning with an initial network design, a set of traffic handling requirements and an initial set of design rules. Each rule includes a condition portion and an action portion and at least one such rule includes a portion expressed in terms of at least one variable parameter. An iterative procedure is implemented to evolve both a network design and a set of design rules comprising variations to rules from the initial rule set. A population of rule sets is generated with each rule set using a different combination of assigned parameter values. For each rule set in the population of rule sets, rules for which the condition portion is satisfied are applied to generate a modified network design. Measures of performance, including cost of each modified design are determined through simulation of the operation of the design on the basis of the traffic handling requirements and the performance and cost of different designs compared. A preferred design then forms the basis for further modified network designs and the particular rule set that generated the preferred design forms the basis of a new rule set population in the next iteration.

Claims

1. A network designing tool for use in designing at least a portion of a communications network, having:

an input for receiving an initial network design and a set of traffic requirements;

a store for storing at least one network design rule;

a rule generator for generating a population of rule sets, each rule set comprising at least one network design rule;

a network modifier for applying rule sets generated by the rule generator to create at least one modified network design;

performance measurement means for calculating at least one measure of network performance in respect of a modified network design when carrying traffic as defined by an input set of traffic requirements; and

an evaluator for comparing modified network designs using respective performance measures calculated by the performance measurement means, for selecting at least one preferred network design satisfying predetermined performance criteria and for identifying a respective rule set used by the network modifier to create said at least one preferred network design;

wherein the rule generator is arranged to receive, from the evaluator, the identity of at least one rule set used to create a preferred network design and to generate a new population of rule sets comprising rules derived from said at least one identified rule set, and wherein the network modifier is arranged to apply rule sets from said new population of rule sets to create further modifications of said at least one preferred network design for input to the performance measurement means and for evaluation by the evaluator.

2. A network designing tool as in claim 1, wherein a network design rule comprises at least one condition portion and at least one action portion with at least one of said portions being defined in terms of at least one variable parameter, and wherein a population of rule sets generated by the rule generator includes rules characterised in having different values assigned to said at least one variable parameter.

3. A network designing tool as in claim 1 or claim 2, wherein a rule comprises a plurality of condition portions, at least one action portion and a variable weighting parameter associated with each of said plurality of condition portions, and wherein rule sets of said population of rules sets generated by the rule generator comprise rules having different values assigned to said variable weighting parameter.

4. A network designing tool as in claim 2 or claim 3, wherein the network modifier is arranged to test each condition portion of a rule in a rule set generated by the rule generator and to apply only those rules in the rule set to modify aspects of the network design for which each said rule condition is satisfied.

5. A network designing tool as in claim 4 when dependent upon claim 3, wherein the network modifier is arranged, when testing each condition portion of a rule, to use respectively assigned weighting parameter values to calculate a measure of the extent to which the weighted rule condition portions are satisfied in respect of a network design to be modified and to modify the network design using only those rules in the rule set for which the weighted rule conditions are most strongly satisfied.

6. A network designing tool as in claim 2, wherein the rule generator is arranged to generate a representation of each network design rule in a rule set, the representation comprising a binary bit string of predetermined length, the assigned value of each variable parameter of the represented network design rule being represented by a predefined sub-section of the bit string, and wherein a population of rule sets comprises a set of said binary bit strings in which selected bits have been altered.

7. A network designing tool as in claim 3, wherein the rule generator is arranged to generate a representation of each network design rule having a variable weighting parameter associated with a condition portion of the rule, the representation comprising a binary bit string of predetermined length, the assigned value of the weighting parameter being represented by a predefined sub-section of the bit string, and wherein a population of rule sets comprises a set of said binary bit strings in which selected bits in the weighting parameter sub-section have been altered.

8. A network designing tool as in any one of the preceding claims, wherein a rule set includes at least one fixed rule and wherein the rule generator is arranged to generate a representation of a fixed rule, the representation comprising a binary bit string of predetermined length for representing a distinct rule identifier assigned to the rule, and wherein a population of rule sets comprises a set of said binary bit strings in which selected bits have been altered to identify different rules.

9. A network designing tool as in any one of claims 6 to 8, arranged to operate a genetic optimisation procedure for the evolution of a network design, wherein the rule generator is arranged to generate a new population of rule sets at each iteration of the procedure comprising rules derived from said at least one identified rule set using genetic operators to alter bit values in a bit string representation of rules in said at least one identified rule set.

10. A network designing tool according to any one of the preceding claims, wherein the population of rule sets generated by the rule generator comprises a single rule set, and wherein the evaluator compares the performance of a modified network design created by the application of said single rule set with the performance of a modified network design generated by an earlier rule set and retains one of said assessed designs as the preferred network design using respective performance measures calculated by the performance measurement means.

11. A method of designing at least a portion of a communications network, the method comprising the steps of:

(i) receiving an initial network design comprising at least the identity of a site for locating a network node;

(ii) receiving predetermined traffic requirements relating to a network to be designed;

(iii) receiving a rule set containing at least one rule for modifying a network design, said rule set including at least one rule comprising at least one condition portion and at least one action portion with at least one of said portions being defined in terms of at least one variable parameter;

(iv) generating an initial population of rule sets including rules characterised in having different values assigned to said at least one variable parameter;

(v) for each rule set in said population of rule sets, generating a corresponding modified network design by applying each rule from the rule set to components of the initial network design for which the respective rule conditions are satisfied;

(vi) calculating at least one measure of network performance in respect of each modified network design generated at step (v) when carrying traffic as defined by traffic requirements received at step (ii);

(vii) evaluating the modified network designs from step (v), comparing them on the basis of said at least one respective measure of performance from step (vi) to identify at least one preferred network design and identifying the corresponding network design rules used to create said at least one preferred network design in step (v);

(viii) generating a new population of rule sets, derived from at least one network design rule identified in step (vii);

(ix) repeating steps (v) to (viii), wherein at step (v) said at least one preferred network design from step (vii) is modified in place of the initial network design.

12. A method of generating a design for at least one communications network, comprising the steps of:

(i) inputting an initial network design comprising at least the identity of a site for locating a network node;

(ii) inputting predetermined traffic requirements relating to a network to be designed;

(iii) inputting a rule set containing at least one rule for modifying a network design, said rule set including at least one rule comprising at least one condition portion and at least one action portion with at least one of said portions being defined in terms of at least one variable parameter;

(iv) generating an initial population of rule sets including rules characterised in having different values assigned to said at least one variable parameter;

(v) for each rule set in said population of rule sets, generating a corresponding modified network design by applying each rule from the rule set to components of the initial network design for which the respective rule conditions are satisfied;

(vi) calculating at least one measure of network performance in respect of each modified network design generated at step (v) when carrying traffic as defined by traffic requirements input at step (ii);

(vii) evaluating the modified network designs from step (v), comparing them on the basis of said at least one respective measure of performance from step (vi) to identify at least one preferred network design and identifying the corresponding network design rules used to create said at least one preferred network design in step (v);

(viii) generating a new population of rule sets, derived from at least one network design rule identified in step (vii);

(ix) repeating steps (v) to (viii), wherein at step (v) said at least one preferred network design from step (vii) is modified in place of the initial network design, until at step (vii) at least one preferred network design is identified satisfying predetermined performance criteria.

13. A method as in claim 12, including the step:

(x) storing the network design rules identified at step (vii), used to create the at least one preferred network design identified at step (ix), for use as input at step (iii) in a further operation of the method.