Development of Smart Planning Tools for BT and Network Optimisation
Submitting InstitutionUniversity of Sunderland
Unit of AssessmentComputer Science and Informatics
Summary Impact TypeTechnological
Research Subject Area(s)
Information and Computing Sciences: Artificial Intelligence and Image Processing, Computation Theory and Mathematics, Information Systems
Summary of the impact
A series of funded research projects have been completed by the
University of Sunderland in close collaboration with BT Research Labs
Ipswich. This research, which has resulted in a series of novel
optimisation approaches, led to the development of suite of tools used for
network planning. These tools are primarily based upon the application of
evolutionary computing methods. Researchers produced intelligent network
planning tools for the development of the national Internet. The tools
have been used extensively since 2008, and the network for the Olympic
games in London 2012 was designed and planned using these smart tools. A
company specialising in vehicle tracking has also been formed as a direct
result of the research.
Access network planning involves determining the position of components
and multicore cables in the network that connects the user to the
telephone exchange. The access network was, in the past, the weak link in
the BT network. Access network planning has been treated as a numerical
nonlinear combinatorial problem. A number of algorithms (Tindle and Poon,
2000; Tindle et al, 2006) have been developed by a team at Sunderland, to
solve the planning problem for xDSL (digital subscriber loop) and TPON
(telephone passive optical networks) technology.
The Sunderland team comprises, and has comprised, Professor John Tindle
(Professor, now Emeritus, 1981 — present), Professor Hugh Ryan (Professor,
now Emeritus, 1985 - present), Dr Ian Fletcher (Senior Lecturer, 1987 -
present), Dr Phillip Tann (Part-time lecturer, 2005 - 2010) and Robert
Warrender (Senior Lecturer, 2000 - present). The work has been undertaken
in collaboration with staff at BT, led by Dr John Mellis, who has been
Visiting Professor at the University of Sunderland (2005 - present), and
is employed in BT Innovate & Design as Head of UK MNC Network Design
and Delivery. Mellis manages a team of network designers focused on BT's
major Multi-National Corporation clients, and has been intimately involved
with all of the developments in this case study.
A number of collaborative projects, led by Tindle and funded by BT,
provided the basis for this work:
- During the period 1994 - 1997 Tindle and Ryan, with the support of PhD
student Harald Paul, developed the first intelligent PON planning tool
for the access network. The embedded optimiser used a hybrid version of
the genetic algorithm (Paul & Tindle, 1996). This project was funded
- Tindle and Ryan, with the support of PhD student Christian Woeste
(1994 - 1998) developed the first PON planning tool based upon the Tabu
Search method. An object oriented model of the access network was
created. Standard data structures required for network planning were
also defined. This project was funded by BT.
- Tindle and Poon (Kin F Poon, PhD student, 1997 - 2001) developed a new
and much more efficient version of the planning tool. This tool could
design the layout of a city with 1000 nodes within a time of 30 minutes
(Tindle and Poon, 2000). This project was jointly funded by BT, and BT
spin-out company Evolved Networks. Dr Poon now works for BT, and has
continued the collaboration and the work of the group.
- Tindle, Tindle (Sonia J Tindle, PhD student, 2001 - 2005) and Fletcher
developed a multistep algorithm to determine the allocation of PON
equipment in cabinets. This is the first PON component allocation
algorithm that considered both location and time in a single
formulation. This project compared the performance of optimisers based
upon both genetic algorithms and particle swarm optimisation (Tindle S J
et al, 2003; Mellis et al, 2007). EPSRC CASE award with BT.
- Tindle, Tann (Phillip Tann, PhD. student, 2002 - 2006) and Fletcher
produced a prototype tool to automatically convert network data written
upon paper based maps into digital information required for input into
the planning process (Tindle et al, 2002). This work employed a hybrid
algorithm built using neural networks, genetic algorithms and GPS. This
was funded by an EPSRC CASE award with BT. Tann was appointed as a
part-time lecturer and continued research as part of the group after
obtaining his PhD.
- Tindle, Turner (Steven Turner, PhD student, 2004 - 2008) and Fletcher
considered issues related to the development of a generic network
planning tool for water, gas electrical and telecomm networks. In this
project they developed a parallel genetic algorithm based optimiser.
This project employed the Pan Reif Solver and web services methods. This
was funded by an EPSRC CASE award with BT.
The above projects have resulted in a suite of novel algorithms and
software tools, which have resulted in the impacts presented in this case
References to the research
1. Mellis J, Tann P, Tindle S J, Mortimore D, Tindle J, (2007).
Application of intelligent methods to generate computer-based network
records for automated planning, Proceedings of 8th European Conference on
Networks and Optical Communications, pp242 - 248, 3-905084-69-4. This
paper presents an algorithm, using neural networks, genetic algorithms
and GPS, to automatically convert network data written upon paper based
maps into digital information required for input into the planning
2. Paul H, Tindle J, (1996) Passive optical network planning in local
access networks: an optimisation approach utilising genetic algorithms, BT
Technology journal, Ed. Richard Padwick, Vol 14, No 2, pp110, 13583948. This
paper presents an early project by the group, which was the first
intelligent PON planning tool for the access network.
3. Tindle J, Fletcher I, Tindle S J, Mellis J, Mortimore D, Turner
S, (2006). Planning of Complex Industrial Systems using a Novel Parallel
Genetic Algorithm, International Conference on System Engineering 2006,
Coventry University, 1-84600-013-0. This paper presents novel
algorithms, based on genetic algorithms, for network planning.
4. Tindle J, Fletcher I, Tindle S J, Tann P, (2002). Application
of Evolutionary Computing for Symbol Recognition, Proceedings of 4th
International Conference on Recent Advances in Soft Computing RASC 2002,
pp41, 1842330764. This paper presents the first PON component
allocation algorithm to consider both location and time in a single
formulation. The research used both genetic algorithms and particle
5. Tindle J, Poon K F, (2000). Addressing Optimisation Issues in
Network Planning with Evolutionary Computing, chapter in Modern Heuristic
Search Methods in Telecommunications Engineering, Editors: David W. Corne,
University of Reading; Martin J. Oates, BT Research Labs; George D. Smith,
University of East Anglia, Publisher: Wiley, pp. 79-97, ISBN:
0-471-988553. This paper reviews the work of the group, including the
then recent work of Poon and Tindle which produced a more efficient
6. Tindle S J, Fletcher I, Mellis J, Mortimore D, Tann P, Tindle J,
(2003). Automated Planning for Broadband Passive Optical Networks, 16th
International Conference on Systems Engineering, pp5, 0905949919. This
paper presents novel work on network planning for broadband PONs.
Papers 1, 2, 5 are representative of the quality and subject matter of
Total funding related to network planning projects has been £465,000,
comprising direct funding from BT, a number of EPSRC CASE awards, and
funding from the spin-out company Evolved Networks, which was managed by
Visiting Professor John Mellis.
Details of the impact
The BT planning tool suite uses the algorithms developed in the research
described above. Professor John Mellis of BT: "This co-operation has
been highly successful, specifically in the area of algorithm
development for `intelligent' network planning tools. The research into
automated planning algorithms led to the successful completion of Ph.D.
theses on automated planning of telecoms networks, including Passive
Optical Networks (now the basis for BT's "Superfast Broadband"
and "Infinity" offerings) and copper access networks (which led to the
Network Optimiser Tool and its use of the Genetic Algorithms created by
the Sunderland team). These tools or their derivatives today play a
crucial role in BT's network planning systems. The ideas and innovations
of the Sunderland team have inspired recent developments, notably the'
BT NetDesign' tool which has been applied to a wide range of BT's
network planning problems including the design of the local area
networks for the London Olympics 2012." (Evidence 1). The evolution
of the tool and the way in which the algorithms developed at Sunderland
have been applied has been clearly documented and agreed between BT and
Sunderland (Evidence 2).
The BT planning tool suite is one of the most successful applications to
date of evolutionary computing to solve a complex real world engineering
problem (Evidence 3). The annual expenditure of BT based upon the output
of these planning tools is in excess of £100M per year since the year
2000. The total expenditure on the access network is therefore a running
total of the order £1.2B. The Sun/BT planning tools have been used to
design a large proportion of the UK national Internet, specifically the
part managed by BT. The tools may be used to determine a near optimal
minimal cost for the installation of a large network. Typically the plans
produced are robust and repeatable to within 0.2% of the average
installation cost. In this way installation costs are minimised and
optimised. The planning process has been transformed into accurate data
preparation by the human planner followed by automated planning carried
out by computer.
A £100M spinout company, Evolved Networks, was created in 2003 to
accelerate the commercial exploitation of the design tools, resulting in
sales of commercial software to BT, Eircom and other European telecoms
companies. This initiative was led by Visiting Professor Mellis.
A BT press release (Evidence 4) explains how the use of BT NetDesign
enabled high-level designs for the communications network infrastructure
of venue buildings to be generated in about 30 minutes. Each design showed
the exact location of equipment, including racks switches and cable. Using
more traditional methods a network planner could take two weeks or longer
to complete a similar sized project. BT NetDesign is unique in its ability
to take a computer aided design (CAD) showing the location of
communication services and then, using `intelligent' software, create a
network communications infrastructure that will keep equipment and overall
cost to a minimum. BT estimated that the number of switches and support
equipment could be reduced by about five per cent as a result of using
NetDesign. NetDesign was employed in the design of the network
infrastructure for more than 75 competition venues and support buildings
which housed 80,000 network connections, 14,000 CATV connections and 1,000
WLAN access points. About 4500km of internal cable was used together with
a huge amount of communications network equipment.
After completing his PhD research Dr Phillip Tann continued to work
part-time for the University as a lecturer. He also started a spin-out
company to track vehicles (taxis, buses, ambulances and cars). Phillip
developed the work he had undertaken with the group to build a tracking
system based upon Java network programming, GPS, embedded microprocessors,
Bluetooth and GSM, using the skills and artificial intelligence algorithms
developed within his PhD. The regional venture capital company NStar
awarded £60,000 seed corn investment to develop the technology. This
resulted in the formation of the company FleetM8 (2008 onwards) to track
vehicles, which employed 15 people (Evidence 5). FleetM8's tracking system
was created to produce dynamic maps for vehicle-navigation systems so
drivers could tell when roads are quiet, or when traffic flows are
sluggish. It has also been fitted on buses in India by Karnataka State
Road Transport in Mysore. FleetM8 were awarded a contract with the North
East bus and train company Arriva, which operates across 12 European
countries. The Sunderland-based company use FleetM8's tracking technology
on bus fleets to immediately spot when the vehicles end up "crowding" by
getting too close together (Evidence 5).
Dr Tann also hit the national press in 2008 when he was caught by a
mobile camera trap, which clocked him doing 41mph in a 30mph zone. But at
the time he happened to be trialling his new invention, a mobile phone
speed and distance recorder which showed he was in fact doing 29mph. He
was charged with speeding, but the case was dropped (Evidence 6). This
technology was then used as evidence by others in further speeding cases
(Evidence 6). A patent application was registered in 2010. The patent was
entitled "Global positioning system error correction, vehicle tracking and
object location", and presented a method and computer program for
determining an error factor for a differential global positioning system,
as well as a method of tracking
a vehicle (Evidence 6).
Sources to corroborate the impact
- Statement from BT can be provided. Head of UK MNC Network Design and
Delivery can also be contacted. This statement details the role of the
University in the development of the smart planning tools.
- A chart detailing Sunderland / BT work can be provided. This chart
pictures the evolution of the projects in which the University and BT
have collaborated and how they impact upon the planning tools.
- Conway A, and Glover T (2011). "An advanced toolset for network
optimization problems." GCC Conference and Exhibition (GCC), 2011 IEEE.
IEEE, 2011. This paper demonstrates recent development of the BT
toolkit, which is based upon the work of the Sunderland team.
- Press release on use of BT NetDesign tool in London Olympics 2012 http://www.btplc.com/Innovation/Innovation/NetDesign/index.htm
This evidences the use of the tools for the design of the network for
the London Olympics 2012.
- Evidence of vehicle tracking work.
FleetM8 is one of the UK's leading providers of GPS tracking and fleet
based in the Northeast of England.
Press coverage of vehicle tracking work in use by Arriva. (2009).
Contact details of the founder of FleetM8 can be provided.
- Evidence of work on vehicle tracking in relation to speed cameras.
Speeding invention. Boffin's Black Box Beat Cops' Speed Camera. (2008)
Evidence of use of speeding invention. (2008).
Patent. Patent application title: Global positioning system error
correction, vehicle tracking and object location. Publication
date: 2010-11-25 Patent application number: 20100295726.
Contact details of the inventor of the system can be provided.