5
Addressing Optimization Issues
in Network Planning with
Evolutionary Computation
John Tindle and K. F. Poon
5.1 Introduction
In line with the rapid growth of telecommunications networks in recent years, there has
been a corresponding increase in the level of network complexity. Consequently, it is now
generally accepted that advanced computer aided simulation and analysis methods are
essential aids to the management of large networks.
The 1990s will be recalled as the decade of business process re-engineering. Most large
conventional manufacturing organisations have already applied some re-engineering to
improve their overall process efficiency, resulting in the establishment of streamlined
management structures, optimised production schedules and facilities, reduced staffing
levels and much closer control over working budgets and expenditure for major projects.
A similar process of re-engineering is now taking place in the telecommunications
sector. In the future, information will assume a much greater level of importance. It is
becoming increasingly evident that many businesses will achieve and actively maintain their
competitive edge by continuously gathering, analysing and exploiting operational data in
new and novel ways. Large-scale systems models can now be created and intelligently
evolved to produce near-optimal topological structures. Macro-level network system
analysis can now be attempted because of developments in heuristic, mathematical and
intelligent methods, and the availability of low cost high performance desktop computers.
Personal workstations can now solve complex problems by processing vast amounts of data
Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D. Corne, M.J. Oates and G.D. Smith
© 2000 John Wiley & Sons, Ltd
Telecommunications Optimization: Heuristic and Adaptive Techniques.
Edited by David W. Corne, Martin J. Oates, George D. Smith
Copyright © 2000 John Wiley & Sons Ltd
ISBNs: 0-471-98855-3 (Hardback); 0-470-84163X (Electronic)
Telecommunications Optimization: Heuristic and Adaptive Techniques80
using new smart algorithms, thereby providing better solutions and deeper insight into the
complex structure of network problems. The primary goals for telecommunications network
operators are to develop methodologies for the following:
Optimal planning methods are required to minimise the cost of building new network
structures.
Impact analysis is required to predict the impact that new components and systems will
have on the network and business.
Business modelling is required to evaluate the effects that selected, individual and grouped
changes will ultimately have upon the whole business and organisation.
Fault analysis is required to accurately identify and repair faults with the minimum
disruption to network performance.
This chapter considers network planning and impact analysis for the Plain Old Telephone
System (POTS). In the past, new network designs were predominately undertaken by human
planners using simple manual or partially automated methods. The methods employed were
characteristically labour-intensive with relatively low levels of productivity. A planner, for
example, would usually be expected to design a typical network layout within three working
days. Generally, this work would entail two stages or more of design iteration, each stage
taking twelve hours. In most cases, the solutions generated were sub-optimal, and therefore
the resultant capital costs were often higher than necessary. It became clear that there was
an urgent need for new automated planning tools to handle complexity and aid network
designers.
Henderson (1997) provides a very interesting and illustrative case study. This project
involved the installation of a national SDH network for Energis UK. He states that,
“Building of the network commenced before the design was complete. The truth is, the
design was not complete until some time after it was built and working! In practice parallel
design and build is becoming more common as the time scale pressures of our competitive
environment increase”. In addition, “Unfortunately, build never occurs as planned.
Unforeseen difficulties delay sections, whilst others prove easy. With a virtual workforce of
1500 people, working to very tight time scales, logistics control was a major problem”.
The inability to produce good plans sufficiently rapidly can sometimes result in poorly
assigned capacity levels in a network. It is also likely that sub-optimal designs could be
implemented which incur higher than necessary capital costs. In most cases, the additional
costs of rework to solve these problems will be very high.
5.2 The Access Network
In the UK access, 90% of new systems are copper based and only 10% optical fibre.
Incumbent service operators are finding it difficult to justify the installation of fibre as a
replacement technology to support narrow band services carried by the existing copper
network. At present, the cost of optical network components is considered too high,
especially the electronic Line Termination Unit (LTU). In addition, the introduction of
Asymmetric Digital Subscriber Line (ADSL) technology has the potential to greatly
Addressing Optimization Issues in Network Planning with Evolutionary Computation 81
increase the available bandwidth in the copper access network, thus potentially extending its
working lifetime.
Consequently, copper bearer platforms still attract significant levels of investment from
many telecommunications operators. Although it was previously considered that fibre would
be deployed more aggressively in the access sector, copper remains the dominant
technology option for the narrow band service sector. The continuous use of copper into the
near future has justified the development of a new smart planning tool to automate the
planning process for greenfield developments. Although in this instance, the methods
described in this chapter have been applied to solve the Copper Planning Problem (CPP), it
is believed the approach in general can be successfully tailored to suit a variety of different
network problems.
In the UK, an ongoing development programme is in place to provide telephony to new
housing estates. It is essential that an estimate of the cost of work is produced, a bill of
materials and a resource schedule. This information is passed on to construction team for
installation. To produce a satisfactory project plan for the construction team by the manual
method proved very difficult, time consuming and tedious because of the many complex
factors planners were required to consider.
The smart tool, GenOSys, which has been developed primarily to aid network planners,
automates the design of the secondary cable and duct networks necessary to connect new
customers to the exchange. GenOSys employs Evolutionary Computation (EC) techniques
to facilitate the rapid solution of large and complex network problems.
In order to develop an efficient search strategy yielding optimal or near-optimal
solutions, it is essential to understand both the nature of the problem and the structure of the
search space. The various merits of using EC methods to address the CPP are discussed in
the following section.
5.2.1 An overview of the Greenfield CPP
The copper network provides customer access to a range of narrow and mid-band services.
Most copper architectures comply with a three tier model consisting of the primary,
secondary and distribution networks, all implemented in a tree structure.
The primary network connects the secondary network to the exchange via a Primary
Connection Point (PCP), as shown in Figure 5.1. The distribution network connects
customers to Distribution Points (DPs), which are connected via the secondary network to
the PCP.
Access networks are normally accommodated within an underground duct network. The
duct network forms the links between the access nodes, such as joint boxes, which are used
to accommodate cable joints and DPs. The duct network is normally highly interconnected
to provide flexible schemes routing between the exchange and customer. A typical
secondary network structure connecting customers to PCPs, is shown in Figure 5.2,
In this context, local access network planning is defined in the following manner. For a
predefined geographical area, duct structure and particular demand profile determine the
following:
Telecommunications Optimization: Heuristic and Adaptive Techniques82
DP
DP
DP
DP
PCP
PCP
Main Pairs
Cables
Direct Pairs
cables
Primary Network Secondary
Network
Distribution
Network
= Customer
DP
Pairs
DP
= Distribution
Point
= Primary
Connection Point
Exchange
Figure 5.1 Copper access network.
1. location of all access nodes (footway boxes),
2. location of DPs,
3. assignment of customers to DPs,
4. aggregation of DPs into sub-networks,
5. assignment of DPs to cable paths, and
6. route of all cables to satisfy customer demand at the lowest cost.
The distribution network architecture is built from a number of different types of
sleeves, joint boxes, cables and ducts. Customers are connected to the network at connection
points called sleeves, which are normally accommodated in underground joint boxes. Ducts
are used to house the secondary and distribution multicore cables, which range in size from
5 to 100 pairs.
5.2.2 Network Object Model
A model of the network was created using object-oriented development methods, Object
oriented analysis OOA and design OOD enable development of flexible, intuitive models.
Object-oriented models are based upon the underlying domain structure. A system built
around domain entity structures is normally more stable than one based around
functionality. It has been recognised that most software modifications are associated with
system functionality rather than the underlying domain (Paul et al., 1994).
Addressing Optimization Issues in Network Planning with Evolutionary Computation 83
PCP
Sleeve
DP
Customer
Cable
Duct
Figure 5.2 Secondary copper network.
These principles are then applied to create a model (Paul et al., 1994).
Classification (abstraction) is the operation of grouping together objects with similar
features.
Inheritance (generalisation) if there are specialised types of a class which exhibit common
features, the principle of inheritance can be used to organise them.
Association represents a relationship between two different classes of objects.
Aggregation (whole/part structure) expresses a special relationship in which one class
contains another.
As object modelling is based upon the organisation principles of human thought
processes, domain specialists are able to contribute to the design of an object model without
requiring specialist computer skills. In an object-oriented model, the objects and their
associations correspond directly to real world entities and their relationships. Consequently,
the object model is modular and closely resembles the real network. Objects can represent
both physical items (copper cables) and abstract concepts (time slots in a frame). These
characteristics make object models easy to understand, maintain and extend.
A network object model is required to capture the network topology and its connection
rules. Persistent computer based objects capture the functionality of network components
and state attributes. The use of object-oriented methods proved successful because they
allowed the complex rules relating to network component connectivity to be represented in a
flexible and concise manner. This scheme allows the seamless integration of engineering
rules into the computer based objects. The majority of constraint checking for engineering
rules is therefore carried out implicitly, through the mechanisms provided by the model.