Network updating arrangement using simulated annealing process to select level of service capabilities of permanent grouped communication links without changing network topology

• US 6,023,562 A
• Filed: 08/22/1995
• Issued: 02/08/2000
• Est. Priority Date: 12/16/1993
• Status: Expired due to Fees

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Crabtree, Ian Barry, Baker, Stephen Charles
• Primary Examiner(s): Luu, Le Hien
• Application Number:
  US08/507,316
• Time in Patent Office: 1,631 Days
• Field of Search: 395/13, 395/51, 395/200.71, 395/200.74, 709/241, 709/244, 379/201
• US Class Current: 709/241
• CPC Class Codes: H04Q 3/0062 Provisions for network management

Abstract

A method and arrangement are provided for network update operations in communications network technology. A simulated annealing technique is used to generate a solution to the problem of providing minimum service capabilities via links of the network, at minimum cost, particularly in terms of the number of exchanges to be updated. Two operations are provided in particular which increase the speed at which a solution is generated while avoiding, at least to a significant extent, the effect of local minima.

Claims

1. A network updating arrangement, for a network which comprises a plurality of permanent communication links with associated switches, each switch having an update status selected from at least two alternative statuses, the service capabilities of each link being functionally affected by the update status of at least one switch, and the links being grouped according to allocated identifiers, each group sharing a common identifier,

the arrangement comprising a database system for logging an update status indicator for each switch, the database system comprising data stored in at least two different data structures, these comprising a link data structure and a switch data structure, the link data structure logging for each link of the network its allocated identifier, or identifiers and all switches whose update status functionally affects the service capabilities of that link, and the switch data structure providing for each switch an index to the link data structure, logging thereby all permanent links whose service capabilities are functionally affected by the update status of that switch, and storing for each switch the update status indicator,

the arrangement further comprising data input means to the link data structure, for selecting, in respect of one or more identifiers, a minimum number of the permanent links in the group of links for which it is the common identifier, and indicating means responsive to said selection to indicate one or more of the switches whose update status can be changed to enable predetermined service capabilities to be provided on said minimum number of links without changing the association between links and services,

wherein each identifier corresponds to specific terminal equipment, said terminal equipment having access to the group of permanent links sharing that identifier for communications by means of the network.

2. A network updating arrangement, for a network which comprises a plurality of communication links with associated switches, each switch having an update status selected from at least two alternative statuses, the service capabilities of each link being functionally affected by the update status of at least one switch, and the link being grouped according to allocated identifiers, each group sharing a common identifier,

the arrangement comprising a database system for logging an update status indicator for each switch, the database system comprising data stored in at least two different data structures, these comprising a link data structure and a switch data structure, the link data structure logging for each link of the network its allocated identifier or identifiers, a service capability indicator, and all switches whose update status functionally affects the service capabilities of that link, and the switch data structure providing for each switch an index to the link data structure, logging thereby all links whose service capabilities are functionally affected by the update status of that switch, and storing for each switch the update status indicator,

the arrangement further comprising data input means to the switch data structure, for selecting one or more switches and changing the associated update status indicator for the selected switch or switches, the link data structure being responsive to said selection and change to update the service capability indicators for links whose service capabilities are functionally affected by the update status of the selected switch or switches.

3. A method of updating a communications network, which network comprises a plurality of communication links with associated switches, each switch having an update status selected from at least two alternative statuses, the service capabilities of each link being functionally dependent on the update status of at least one switch, and the links being grouped according to allocated identifiers, each group sharing a common identifier, wherein the method comprises:

i) storing an indicator indicating the update status for each switch in a first data structure of a database system;

ii) logging all links whose service capabilities are functionally affected by the update status of each switch, by means of a plurality of indexes to a second data structure of said database system;

iii) selecting, in respect of one or more identifiers, a minimum number of links in the group of links for which it is the common identifier; and

iv) identifying by means of a simulated annealing process an optimal set of switches, selected from the switches of the network, for which said selected minimum number of links will have different service capabilities as a consequence of changing the update status of each of said optimal set of switches.

4. A method of updating a communication network, which network comprises a plurality of communication links with associated switches, each switch having an update status selected from at least two alternative statuses, the service capabilities of each link being functionally dependant on the update status of at least one switch, and the links being grouped according to allocated identifiers, each group sharing a common identifier, wherein the method comprises:

i) storing an indicator indicating the update status for each switch, in a first data structure of a database system;

ii) logging all links whose service capabilities are functionally affected by the update status of each switch, by means of a plurality of indexes to a second data structure of said database system;

iii) selecting a set of switches and changing the update status indicator of each switch of said set; and

iv) identifying by means of said plurality of indexes the links whose service capabilities would be changed as a consequence of a corresponding change in update status for the switches of said set.

5. A network planning tool, for use in updating a communications network, the network comprising a plurality of communication links joined by switches to provide services to terminal equipment, wherein the service capability of each link is dependent on the update status of at least one switch,

said tool comprising a first data structure, a second data structure and a user interface,

the first data structure comprising a log of the links of the network, and of identifiers related to the links, each identifier being associated with specific terminal equipment served by a selected group of said links of the network,

the second data structure comprising a log of the switches of the network, a log of update status indicators for the switches, and an index, for each switch, to the first data structure, which index provides a log of the links whose service capabilities are dependant on the update status for that switch, and

the user interface comprising data input means for selection of any one of a group of variables, the group comprising a set of said identifiers, a number or capacity of links associated with each identifier, and a set of one or more switches,

said tool further comprising indicator means responsive to a selection made by means of the data input means to indicate any of a group of data sets, said group of data sets comprising firstly an optimal set of switches whose update status can be changed so as to provide a minimum change in service capability of links having a common identifier, and secondly a number or capacity of links, grouped according to their common identifier, whose service capability will be changed by a change in update status of a selected set of switches.

6. A method for use in updating a communications network, the network comprising a plurality of switches which control routing for data or voice traffic on a plurality of traffic links, which method comprises the application of a simulated annealing technique to the problem of generating a set of switches selected from the switches of the network, which set of switches, on updating, facilitate improved service capabilities on links of the network according to predetermined requirements,

wherein the method comprises the application of at least two alternative operations, these being a toggle operation wherein an update status relevant to a switch is changed regardless of whether it was initially positive or negative,

and a switch operation wherein update statuses relevant to two switches are both changed in one operation, the initial update status for the two switches being different.

7. A method according to claim 6 which further comprises a selection step for selecting an operation to apply.

8. A method according to claim 7 wherein a toggle operation is selected unless one or more conditions are met.