Design of communications networks

• US 7,385,936 B2
• Filed: 09/14/2001
• Issued: 06/10/2008
• Est. Priority Date: 09/15/2000
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications (BT Group Plc) (BT Group PLC)
• Inventors: Shipman, Robert A
• Primary Examiner(s): Ngo; Ricky Q.
• Assistant Examiner(s): Yuen; Kan
• Application Number:
  US10/363,776
• Publication Number:
  US 20030181210A1
• Time in Patent Office: 2,461 Days
• Field of Search: 370/228, 370/222, 370/236, 370/338, 370/352, 370/229, 370/230, 370/231, 370/230.1, 370/235, 370/254, 370/252, 703/14, 703/1, 703/2, 703/3, 455/446
• US Class Current: 370/254
• 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

At least a part of a communications network is designed 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 including 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, said tool comprising:

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 having an identity, and 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 assessing 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 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 the population of rule sets generated by the rule generator includes rules characterized in having different values assigned to said at least one variable parameter.

3. A network designing tool as in claim 2, 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.

4. 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

the population of rule sets comprises a set of said binary bit strings in which selected bits have been altered.

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

6. A network designing tool as in claim 1, 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.

7. A network designing tool as in claim 6 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; and

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.

8. A network designing tool as in claim 6, wherein:

the rule generator is arranged to generate a representation of each network design rule having the 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 the 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.

9. A network designing tool as in claim 1, 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

the population of rule sets comprises a set of said binary bit strings in which selected bits have been altered to identify different rules.

10. A network designing tool according to claim 1, wherein:

the population of rule sets generated by the rule generator comprises a single rule set, and

the evaluator compares the performance of a first modified network design created by application of said single rule set with the performance of a second modified network design generated by an earlier rule set and retains one of said first and second modified network designs as the preferred network design using respective performance measures calculated by the performance measurement means.

11. A network designing tool as in claim 1, wherein the at least one modified network design includes the relocation, addition or deletion of at least one communication network node.

12. A network designing tool as in claim 1, wherein the at least one modified network design including relative respective locations of plural nodes, and links between nodes.

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

(i) receiving an initial network design comprising at least an 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 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 characterized 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), assessing 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.

14. A method as in claim 13, wherein the corresponding modified network design includes the relocation, addition or deletion of at least one communication network node.

15. A method as in claim 13, wherein the corresponding modified network design including relative respective locations of plural nodes, and links between nodes.

16. A method of generating a design for at least one communications network, said method comprising:

(i) inputting an initial network design comprising at least an 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 characterized 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), assessing them based on 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.

17. A method as in claim 16, further including:

(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.

18. A method as in claim 17, wherein the corresponding modified network design includes the relocation, addition or deletion of at least one communication network node.

19. A method as in claim 16, wherein the corresponding modified network design includes the relocation, addition or deletion of at least one communication network node.

20. A method as in claim 16, wherein the corresponding modified network design including relative respective locations of plural nodes, and links between nodes.