 |
OR/MS Today - April 2003
International OR
'FIDO': Telecom's Best Friend
OR-based software helps design local-access optical fibre networks in New Zealand
By Andy Philpott, Andrew Mason and John Davenport
The telecommunications industry, which uses techniques ranging from queueing and simulation to mixed integer programming, is one of the success stories of applied operations research. The problem of designing local access fibre networks, for example, has been extensively researched, and a number of OR-based packages have been developed to tackle this problem. So, when John Davenport of TelstraClear contacted Andy Philpott at the University of Auckland for help with the design of a local-access telecommunications network, it initially appeared to be a case of simply identifying and recommending a suitable off-the-shelf package. However, six months later, Philpott and his team delivered FIDO (Fibre Diversity Optimizer), a new special-purpose software package for designing robust local access networks using an innovative thinning-ring optical fibre architecture. In the course of the following year, FIDO was used in the design and construction of the networks for the central business districts of the three largest cities in New Zealand.
This article is an account of the successful development and deployment of FIDO in a collaboration between TelstraClear, their network design contractor, Pulse Communications, the University of Auckland, and a spinoff software company, Optimal Systems Limited. We shall describe some of the unique features of this package, and discuss why re-inventing the wheel in this case was the correct approach.
The history of FIDO begins in February 2000 with the formation by Telstra — the well-known Australian telecommunications operator — of a new telecommunications company in New Zealand. The press release detailing the new company, now known as TelstraClear, included the announcement that the new company had a five-year budget of 1.2 billion New Zealand dollars to construct a new broadband network that would pass 65 percent of New Zealand homes and 80 percent of New Zealand businesses in New Zealand's five major cities. Unlike the network of the incumbent operator, this new network was intended to carry the full range of telephone, data, Internet, mobile, and cable and satellite TV services.
In June 2000, John Davenport, the network design director at TelstraClear, contacted Philpott, requesting assistance with their design process. Davenport had collaborated with Philpott over a number of years as a sponsor of small projects involving graduate students in the Department of Engineering Science at the University of Auckland, and recognized the value of OR modeling in making good design and operational decisions.
In the first meeting, Davenport described the approach to be adopted by TelstraClear. They were intending to construct a design that could provide inexpensive voice and high-bandwidth data services to customers. TelstraClear's point of difference with the incumbent operator was the provision of services that were robust in the sense that a failure in any single line would not disrupt the connection. This requires each customer to have two paths of fibre optic cables (Figure 1) connecting them to the telecommunication exchange (and hence the outside world) that are geographically separated. If the fibres being used by a customer are accidentally cut, switching equipment in the customer's building and the exchange immediately switches over to the second unbroken fiber connection without disrupting transmission.
Figure 1: A schematic of fibre optic cable construction.
Images from DataCottage.com and NewScientistJobs.com
The problem of designing two-connected networks of this type has been well-studied in the operations research literature (see e.g. [1], [3], [4]). A famous paper on this problem by a team from Bellcore was a finalist in the 1994 Edelman Prize competition [1]. The Bellcore paper describes the development of the SONET Toolkit, a suite of optimization algorithms and heuristics for designing rings of fibre joined together at junction points by add-drop multiplexors. By directing traffic that enters each ring both ways around the ring en route to its destination, this architecture provides the robustness desired by network provisioners.
Unfortunately, SONET networks require expensive multiplexors to be installed each time a path of fibre diverges from a ring. Many multiplexors can be required if a SONET architecture is employed in an area with dense customer connections, making such a network expensive to install.
The approach proposed by Davenport's team was to eliminate the need for multiplexors by connecting each customer to the exchange with their own dedicated ring. The simplest approach to such as design is to choose the routes for the customers' rings independently, where each ring is chosen to minimize the length of fibre that it requires. This gives a huge number of low-capacity rings that together minimize the total length of fibre required. This network is the robust version of a simple network in which customers are connected by single, shortest-path routes to the exchange.
Building a network in this way ignores the economies of scale that arise from bundling fibres together into larger cables. These economies can be realized, however, by noting that since all of the fibre rings connect with the exchange, the number of fibres required in ducts close to the exchange will be larger than those at the extremities of the network (see Figure 2). Therefore, larger cable sizes can be used closer to the exchange, giving a network that forms a set of thinning rings. The size of the cables close to the exchange can be increased by reducing the number of possible routes available to the individual rings. In practice, this limitation arises naturally as a result of planning rules that limit the number of streets that can be trenched to lay fibre cables.
Figure 2: The TelstraClear customers are each connected to the Telstra exchange using rings that start at one side of the exchange, travel out to the customer, and then back to the other side of the exchange. This figure shows how the total number of fibres laid down each street decreases with increasing distance from the exchange.
The commitment of the TelstraClear design team to a thinning-ring architecture precluded the use of existing software like the SONET Toolkit. It was clear that a new piece of software would be needed to help with the design process. Back at the University, Philpott enlisted the help of colleague Andrew Mason, and together they embarked on the development of a first version of FIDO. The software development work was a successful collaboration between the commercial arm of the University of Auckland and a small software company called Optimal Systems. The University provided modeling expertise, while much of the coding and testing was carried out by programmers in Optimal Systems.
To illustrate the architecture of a single fibre ring, consider the example shown in Figure 3. Here a ring is required to serve customers in three buildings, denoted B, D and F, on one side of a street. (The other buildings do not have connections with TelstraClear.) Street ducting is laid down the street joining the vaults p and q located at opposite ends of the street. This street ducting includes T-junctions and spurs that run to the buildings. Buildings B and F within the street obtain a diverse service by being connected to both vaults p and q using fibre optic cable laid in the street ducting. Inside these vaults, these building fibres are welded into larger feeder cables that run from the vaults back to the exchange in feeder ducts, thus providing two physically continuous fibre-optic connections from the exchange to the building. The two feeder paths used to connect p and q to the exchange are strictly disjoint in that they never share any vaults or roads. We can thus consider each building to belong to a fibre ring, in this case defined by vaults u, t, p, q, w, v. This ring topology ensures there is a diverse service delivered to each customer in the street that will not be disrupted even if the fibre cables in some roads are accidentally cut.
Figure 3: A sample ring that feeds customer buildings B, D and F in a street. The street is connected to the exchange by two feeders, one following a feeder path from vault p through vault t to the exchange entry point u, and the other following a path from vault q though vault w to entry point v.
Building D in this example is not a high-speed data user, but instead has requested a low-speed, copper-wire connection. Rather than running copper back to the exchange, TelstraClear provides a copper connection to a building by feeding it off one of their multiplexors located within some other building in the street. In this case, a copper wire is run within the street ducting from the multiplexor in building B through to building D. The multiplexor handles the combining of the data streams from buildings B and D into a single data stream for transmission, and the demultiplexing of received data back into their separate data streams. In practice it may not be feasible to let building B feed building D since B's owner may object. In this case, another building that has the owner's consent will be used to feed building D. FIDO determines which multiplexors will be used by the copper connections, and which buildings will house these multiplexors, by applying dynamic programming to solve a lot-sizing problem.
The development of this street layout was a highly dynamic process. One of TelstraClear's design goals was to reduce their costs by only adding connections as actual customer demand was realized. This meant that although the street ducts would be laid en masse, fibres would only be run into these ducts as customers were connected. This process is made complicated by the fact that fibres can be fed from a spur into a street duct, but cannot normally be guided in the opposite direction. "Telstra was not happy with some of our initial solutions," Mason says. "We had assumed that when feeding copper between buildings, the copper cables would be run into a spur at each building, then join the main street duct and emerge at a vault at the end of the street. The cables would be joined at the vault, thereby completing the connection."
The unnecessarily large cable lengths associated with this approach prompted Davenport's team to develop a new system where copper cables could be steered through the ducting from one building to another. The bosses were only convinced after numerous tests of the new procedure had been performed in their labs.
The approach adopted in FIDO was to provide a tool to enable designers to quickly evaluate different design options. This involved the solution of three related optimization models, each of which is assumed to be independent. We only give a sketch of these here (the details can be found in [2] and [5]).
FIDO must determine the least-cost paths that will be used for the fibre from the exchange that will connect the vaults for each street. These paths must be chosen from a set of pre-specified feeder arcs corresponding to those streets that will be trenched for feeder ducts. (The cost of this trenching was assumed to be fixed.) Finding these paths for each street can be formulated as a network flow problem in a graph in which each arc corresponds to a road segment that is being trenched for feeders, and each node corresponds to a vault. We assume that each network contains just a single exchange represented by two nodes, u∈V and v∈V, being its two feeder entry points. Consider a street running between vaults p∈V and q∈V. The nodes p and q are given a supply of 1 unit each, matched by demands of 1 unit at each of the exchange nodes u and v. All other nodes have demand 0. Feeder arc (p,q), if it exists, is deleted from the network. Each remaining feeder arc (r,s)∈A is replaced by two directed arcs (r,s) and (s,r), each with capacity 1 and a cost equal to c(r,s), the length of the original feeder arc (r,s). To ensure node diversity, we split each node in this graph into two nodes joined by a directed with cost 0 and capacity 1. Solving for the least cost flow on this network gives unit flows in those arcs that define the two desired feeder paths for street (p,q).
Figure 4 shows a screen shot from the FIDO program with a single street selected. FIDO has displayed the buildings associated with the street and the minimum-length feeder paths connecting this street to the exchange.
Figure 4: Feeder paths from a single street back to the two fibre entry points at the exchange. Buildings are shown as circles, where a hollow building indicates that it does not contain a multiplexor.
Once the feeder paths for the streets have been calculated, and the fibre requirement for each path is known, we need to determine how the fibres in the feeders will be packed into cable sizes. We can use welding at a vault to connect two or more small cables to a single larger cable, such as maybe two 24-fibre cables into a 48, or (with some wastage) three 24s into a 96. While the larger cable sizes are cheaper per fibre, there are significant costs associated with each weld that need to be taken into account. As well as welding smaller cables onto larger ones, it is also possible to partially cut a cable at some point along its length, and weld fibres into the middle of the cable. This is useful when "dropping" fibres onto a street from a large cable that passes through a vault. Figure 5 shows examples of these weld types.
Figure 5: Examples of a join weld (left) combining two 48 fibre cables into a 96 fibre cable and (right) a drop weld feeding 24 fibres from a street into a 96 fibre feeder cable. The figures show the number of fibres involved.
A greedy heuristic procedure was developed for determining where welds should occur, and what mix of cable sizes should be run within each feeder duct. This heuristic begins by working from the streets back up to the exchange determining where cables should be joined. It then uses a first-fit-decreasing bin-packing heuristic to pack the street fibres and incoming cables into typically larger cables. The FIDO screen shot in Figure 6 shows the cables that are used to feed the street highlighted in Figure 4.
Figure 6: Cables feeding a street. The cables closer to the exchange are larger as they pick up, through welded joins, fibres for a greater number of streets. Drop welds are typically used to connect the feeders to the streets; only one of these streets is shown. Feeder cables of different size along the feeder paths are connected using join welds.
A recent enhancement to FIDO [5] is the replacement of the welding heuristic by a dynamic program that computes the mix of cable sizes and welds to give a minimum combined cable and weld cost. Since the state space for this dynamic program is very large, the implementation of this routine is time consuming. However, some heuristic state-space reduction has been possible with little degradation in the objective, which has turned out to about seven percent better than the objective yielded from the bin-packing heuristic.
A major benefit of FIDO was the ease with which fibre layouts could be redesigned. This became necessary as new feeders were added, and some existing feeders were removed (due to municipal authorities altering access for trenching), and different demand scenarios contemplated. Indeed, the highly dynamic nature of TelstraClear's architecture design process meant that FIDO had to be very flexible to move with the continually evolving problem specification. The success of FIDO depends as much on its flexibility and built-in visualization capabilities as on the optimization and heuristic algorithms it contains.
FIDO was developed to meet an evolving specification within strict deadlines. In this environment, attempting to provide TelstraClear with a system that guaranteed global optimality to what is essentially a massive stochastic integer programming model was not a practical or economically feasible option. Nevertheless developing appropriate stochastic programming methodologies for attacking this problem continues to be an active area of our research and development effort.
FIDO has now been used to assist in the network planning for the Auckland, Christchurch and Wellington central business districts. By the end of 2000, Aucklanders were witnessing extensive trenching work throughout the central business district (Figure 7) as TelstraClear rolled out the first stages of their new network, based on the designs determined by our software. A year later, their network was up and running and successfully attracting new customers. FIDO is acknowledged as being a key contributor to the speed at which this development was completed.
Figure 7: Ducts being laid in Auckland for the fibre optic network. Source: The New Zealand Herald.
References
- Cosares, S., Deutsch, D.N, Saniee, I., and Wasem, O.J., 1995, "SONET Toolkit: A decision support system for designing robust and cost-effective fiber-optic networks," Interfaces, Vol. 25, pgs. 20-40.
- Mason, A.J. and Philpott, A.B., 2001, "Development of FIDO — A Network Design Tool for Fibre Cable Layout," in Proceedings of the 34th Annual Conference of ORSNZ Conference, 2001.
- Monma, C.L. and Shallcross, D.F., 1989, "Methods for designing communications networks with certain two-connected survivability constraints," Operations Research, Vol. 37, pgs. 531-541.
- Grotschel, M., Monma, C.L. and Stoer, M., 1992, "Computational results with a cutting plane algorithm for designing communications networks with low-connectivity constraints," Operations Research, Vol. 40, pgs. 309-330.
- O'Sullivan, M., 2002, "Optimal Fibre-Optic Cable Layout using Dynamic Programming," Masters Thesis, Department of Engineering Science, University of Auckland, Auckland, New Zealand, August 2002.
Andy Philpott and Andrew Mason work in the Department of Engineering Science at the University of Auckland (www.esc.auckland.ac.nz). John Davenport is a senior network architect at TelstraClear. See www.telstraclear.co.nz for more information. The authors acknowledge the contributions to this work of Matthew O'Sullivan of the University of Auckland, Vaughan Andrews of TelstraClear and Craig Douthat of Pulse Communications. Further information on FIDO can be obtained from Optimal Systems Ltd. (www.optimalsystems.co.nz).
Table of Contents
OR/MS Today Home Page
OR/MS Today copyright © 2003 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Rd., Suite 220, Marietta, GA 30060 USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2003 by Lionheart Publishing, Inc. All rights reserved.
|