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.

Underpinning 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:

1. 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 by BT.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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 study

References to the research

Papers 1, 2, 5 are representative of the quality and subject matter of the work.

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

1. 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.
2. 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.
3. 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.
4. 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.
5. Evidence of vehicle tracking work.
   FleetM8; http://www.fleetm8.com/
   FleetM8 is one of the UK's leading providers of GPS tracking and fleet management solutions,
   based in the Northeast of England.
   Press coverage of vehicle tracking work in use by Arriva. (2009).
   http://www.busworld.org/articles/detail/768
   Contact details of the founder of FleetM8 can be provided.
6. Evidence of work on vehicle tracking in relation to speed cameras.
   Speeding invention. Boffin's Black Box Beat Cops' Speed Camera. (2008)
   http://news.sky.com/story/574796/boffins-black-box-beat-cops-speed-camera
   Evidence of use of speeding invention. (2008).
   http://neilherron.blogspot.co.uk/2008/12/two-speeding-tickets-and-take-away-in.html
   Patent. Patent application title: Global positioning system error correction, vehicle tracking and object location. Publication date: 2010-11-25 Patent application number: 20100295726.
   http://www.faqs.org/patents/app/20100295726
   Contact details of the inventor of the system can be provided.