We propose a mixed-integer programming (MIP) formulation for a problem of optimal dimensioning of equipment of the fiber-to-the-home optical access network (FTTH-OAN). The optimization aims at minimizing capital expenditures (CAPEX) related to deployment of the FTTH-OAN, i.e., the cost of active equipment (OLTs and OLT cards), cost of passive equipment (optical splitters, cables, fibers, fibers terminations, splices, closures), cost of site preparations (building, cabinets), and cost of necessary labor (duct preparation and rollout of cables). The formulation has been implemented and validated. General results based on selected real-world scale numerical experiments are presented.
1 Introduction
The increasing demand for broadband Internet access and constant pressure imposed by mobile network operators makes fixed access network operators consider adoption of novel fiber-based technologies. In order to attract new customers, fixed access network operators have to substantially increase the quality (in particular, the speed) of offered transport services, and this can only be achieved by bringing the fiber as close to the customer as possible; thus, replacing the legacy copper cables with the fiber in the access parts of their networks is a must.
In this context, Gigabit Passive Optical Networks (GPON/XG-PON—see [10, 11]) seem to be a suitable solution, especially in the long run. They are capable of providing much greater bandwidth than their copper-based alternatives resulting in much more efficient way of handling a potential increase in demand volumes in the future. Simultaneously, these networks allow keeping the necessary expenditures (both CAPEX and OPEX) at a reasonable level in comparison with the competing (EPON, Active Ethernet and optical P2P) technologies (see, e.g., [6, 17]).
Fig. 1
General view of an FTTH-OAN network
×
Advertisement
In this paper, we consider fiber-to-the-home (FTTH) Optical Access Networks (FTTH-OANs)—see Fig. 1—built upon the GPON standardization. An FTTH-OAN (see [10‐13]) spans in between the service node interface (SNI), i.e., the northbound interface of the OLT device, and the user to network interfaces (UNIs), i.e., the interfaces between ONTs and the customer equipment (CE). All ONTs of the FTTH-OAN are partitioned into groups of up to 128 devices, where every ONT of the group is connected to a single port of the OLT by means of an optical distribution network (ODN). The OLT port organizes bidirectional transmission of data between the OLT and every ONT connected to the ODN, providing in case of XG-PON the (total) speed of up to 10 Gbps and up to 2.5 Gbps in, respectively, downstream (i.e., from the OLT to ONTs) and upstream directions.
We consider FTTH-OANs exploiting point-to-multipoint (P2MP) ODNs that take advantage of passive optical splitters. According to the outcomes of the discussions conducted with our industrial partners, we decided to restrict our considerations to 3-tier ODNs that admit installation of up to three splitters on the way between the OLT and any of the ONTs. As illustrated in Fig. 1, we assume that the first level of splitting is performed in the Central Office (CO), the second in the dedicated distribution nodes (street cabinets or pole mast boxes) and the third in the access nodes; depending on the subscriber type—multi dwelling units (MDU) or single-family residential (SFR)—access nodes are placed, respectively, at the customer premises or at the dedicated outdoor compartments (e.g., wells or street cabinets).
Our approach starts from optimizing the OLT locations and ends up at the equipping access nodes. We use industry-acceptable and hence unavoidably complex network models that in particular encompass the following detailed elements: attenuation of cables, splitters, and optical plugs; power budget of the demands; output power of the OLT ports; available telecommunication infrastructure; costs of trenching; costs of cable rollout; costs of splicing fibers. As our research aims at facilitating large deployment projects with up to one million ONTs aggregated into up to 100 k access points, we decided to use both exact MIP-baed approaches and heuristic methods.
In the research, we use our automated FTTH network optimization platform presented in [24]. The methodology implemented there ranges from distributed local search methods and fast evaluation algorithms in the early stages of the design process to modular MIP models aiming at improving the obtained solutions using polishing features of the MIP solvers. In this paper, we concentrate on the stages that effectively use the MIP methodology to improve heuristic solutions to industrial-based FTTH network optimization problems.
Advertisement
The outline of the paper is as follows. We first summarize the literature on FTTH network optimization in Sect. 2. We indicate to what extent the MIP methodology has been so far considered in the FTTH network design. In this way, we justify the novelty of our research. In Sect. 3, we give a general overview of the problem, providing information on its input data, the decisions variables, the objective function, and its structure. Section 4 introduces a model of the FTTH network as well as the catalogue of active and passive equipment constituting a necessary foundation for the actual problem formulation presented in Sect. 5. Sections 4 and 5 are the core of the paper—they define a practical MIP formulation that can be used to facilitate the large-scale FTTH network design.1 The formulation is evaluated in Sect. 6. The paper concludes in Sect. 7.
2 Related work
The FTTH network design problem has been intensively studied over the last decade resulting in vast literature on the topic. However, most of the proposed models lack some important features which makes them impractical from the industrial viewpoint. The reason is that they were proposed when industrial experience in rolling-out such networks was rather scarce. In effect, many of the assumptions adopted by the authors of those papers lead to oversimplified considerations. In 2005 Khan proposed a simple 2-factor approximation to a PON design problem [14] working on a model that does not take an intermediate (between OLT and ONT) split into account. Such an assumption results in the limited flexibility of the solutions and is hardly justified from the viewpoint of the current practice. What is more, the model does not take the existing infrastructure into account, which is unacceptable when designing FTTH networks in urban areas. Another problem arises from the way the problem is approached—in [14] a 2-factor approximation is proposed. Nowadays, thanks to loads of published literature and practical experience in designing FTTH networks, it is known that although a CAPEX difference between good and bad FTTH network designs can be substantial, a CAPEX difference between FTTH network designs obtained by good and bad, but still reasonable, optimization methods hardly exceeds ten percent. Therefore, most approximation algorithms are not particularly useful from the viewpoint of the industry, as the guaranties they can provide are unsatisfactory.
Similar reasons stand behind disregarding the MIP methodology in most industrial circles, as its biggest disadvantage is tractability. MIP approaches to the FTTH network design are efficient either for relatively small test cases, or work efficiently only in unacceptably simplified models. For instance, in [2] only one split is allowed and its ratio is given as an input. On the other hand, in [23] trenching is considered separately for each cable, thus two parallel connections cannot be realized in one trench. Similar simplifications were considered in [20], in which trenching is also considered separately for each connection. Moreover, only one OLT location is considered in their model. Another example is [4], in which the split ratio is not considered. Certainly, MIP models can be very detailed. Consider the model presented in [15], in which even the cost and attenuation of splices are considered. Unfortunately, such models can be utilized for only relatively small use cases, like a 28-node network considered in [15]. One of a few examples of using MIP in industrial circles is a work published by Orange Labs, France [3, 7, 8]. Their model is practically justified. However, they considered densely populated urban areas only. Therefore, in their model the effective reach of FTTH technologies, which does not exceed 10 km in practice for 1:64 split [22], is not taken into account. Moreover, they assume abundant and always available urban underground infrastructure, which is not necessary the case in small cities or developing countries. The methodology used in [3, 7, 8] is MIP facilitated by the use of valid inequalities and various algorithmic enhancements. Another recent work by Orange Labs is [1]. It is similar to our research in majority of assumptions and the methodology used. However, it covers only the last access part of FTTH network; thus, the authors do not consider splitting and OLT costs. Still, the detailed view on the fiber splicing problem presented in [1] is definitely worth noting.
The tractability issues arising in the FTTH network design approached by the MIP methodology convinced researchers to concentrate on heuristic approaches. Below, we discuss a number of papers dealing with such approaches. In the survey, we concentrate both on methodologies used in the cited papers and differences between the model used in our research and the models used by other researchers.
Consider an FTTH optimization model presented in [19]. To solve it the authors present a 4-step deterministic approach that first initializes a tree and then divides all ONTs into groups. For each group an optimal position of a distribution point is selected using the Bellman–Ford algorithm. Finally, the authors use a shortest path algorithm for determining routes of distribution cables and a distance network heuristic [16] for determining routes of trunk cables. In comparison to our model, it lacks for instance the costs related to OLTs. One may claim that those costs are constant, because a number of the served clients is constant. However, not taking those costs into account can create undesirable effects when more than one OLT is considered. In fact, in [24] we show that the cost of line cards is significant, and it can substantially vary during the optimization process (allowing for the cable cost reduction). Another optimization approach is presented in [21], in which the authors propose an algorithm which is a mixture of a genetic approach and a spanning tree algorithm. In their model no cascades of splitters are considered. Similar simplification is adopted in [18], in which Recursive Association and Relocation Algorithm (RARA) is proposed to tackle the FTTH network design problem. RARA is an extended Cooper’s algorithm [5], which has been used to solve the multi-facility location allocation problem in logistics studies, and can be considered as a mixture of Simulated Annealing and various local searches. As far as their model is concerned, in [18] not only cascades of splitters are not taken into account, but also the problem of parallel connections is not adequately addressed.
To summarize, all the approaches presented so far are either exact approaches based on MIP methodology that work with simplified models and relatively small networks, or heuristic approaches that are much faster but in most cases are virtually not able to provide optimal solutions. In some papers, a combination of those two approaches is proposed—a problem is first modeled by a MIP program and then solved using a heuristic approach. In our research, we use an opposite strategy. We first use a heuristic approach to create a good starting solution, and then upgrade it using the MIP methodology. The obtained solution is used not only as a starting solution for an MIP solver, but also it is utilized to generate some vital constraints that limit the size of the problem making it approachable by commercially available MIP solvers. To our knowledge such an approach has so far not been used in the FTTH network design.
3 Base optimization problem
The MIP methodology can be used in various ways while designing an FTTH network. In this research, we use it to upgrade results returned by heuristic algorithms of the optimization framework presented in [24]. The framework takes into account: locations of demands, available infrastructure, labor and equipment cost, and technological constraints. It returns detailed network plans including: network topology, OLTs, OLT cards, cabinets, splitters, cables, splices, and splice closures. Taking all the mentioned aspects into account while modeling a problem would result in a tremendous number of variables and constraints making the obtained model unsolvable by all state-of-the-art MIP solvers. Therefore, the problem had to be simplified to make it approachable. As the main assumption was to use the MIP methodology to upgrade obtained solutions, the simplification of the model could not be based on omitting allegedly less important factors, as for instance splicing. On the contrary, allegedly more important factors, as for instance OLT locations, had to be fixed and removed from the model.
The considered problem can be summarized as follows. We address the problem, denoted by \(\mathcal {P}\), that aims at optimizing the capital expenditures necessary for deployment of an FTTH-OAN network that consists of one or more OLT devices at the CO site and a set of access points situated in or near to CP sites. The network satisfies demands of every access point (i.e., the sum of demands of ONT devices connected through that access point) taking into account admissible splitting scenarios and the power budget of optical paths.
3.1 Prerequisite data
Problem \(\mathcal {P}\) requires the following input data:
catalogue of active and passive equipment,
topology of the infrastructure (duct) network,
infrastructure paths selected for every distribution and access node,
signal demand of each access node,
infrastructure nodes (sites) selected for installation of passive and active equipment.
3.2 Main decision variables
The following decision variables are the subject for optimization:
utilized OLT types (OLT locations are given),
utilized splitter types and their locations,
utilized cable types (network topology is given),
utilized cabinet types (network nodes are given),
splicing locations and utilized splice closures.
3.3 Problem structure
Taking into account the structure and the complexity of the complete problem, we split description of its formulation into four partial problems—represented as ovals in Fig. 2. We emphasise, that the partial problems remain inter-linked—semantics of variables linking particular pairs of partial problems is sketched in rounded rectangles—and what we approach is the global problem as a whole.
Fig. 2
Problem structure
×
First, the bundle layer dimensioning partial problem\(\mathcal {P}^B\) which aims at evaluating the number and types of splitters installed in every node of the FTTH-OAN network as well as at selecting the number of OLT cards (of each type) to be installed at the central office (CO) node. The provided solution guarantees that every access node, regardless of its distance to the CO site, is provided with the required number of optical signals of the sufficient power.
Second, the cables partial problem\(\mathcal {P}^I_{cable}\) that determines the number of cables (of every type) installed at each infrastructure segment (a duct or an overhead line). The installed cables are to provide fibers in the number satisfying requirements of the bundle layer dimensioning problem.
Third, the splices partial problem\(\mathcal {P}^I_{splice}\) that computes the number of optical splices and optical closures of every type that must be installed in each infrastructure node to support the solution evaluated in the bundle layer dimensioning and the cables problems.
Fourth, the site dimensioning partial problem\(\mathcal {P}^I_{site}\) which aims at selecting a site type as well as the number and types of hardware cabinets installed in every infrastructure site.
3.4 Objective function
The objective of problem \(\mathcal {P}\) is to minimize the sum of cost components introduced by every partial problem:
Symbol \(\zeta \) denotes the total cost, while \(\zeta ^B\), \(\zeta ^I_{cable}\), \(\zeta ^I_{splice}\), and \(\zeta ^I_{site}\) denote cost components introduced by, respectively, bundle layer, cables, splices and site dimensioning partial problems.
3.5 Problem description layout
To clarify the presentation, we split the problem description into three parts. The model part (in Section 4) introduces the architectures and notions expressing the organization of the FTTH-OAN network. The equipment catalogue part (in Sect. 4.2) defines a family of catalogue sets that identify different equipment kinds, and for each kind, a set of crucial parameters (like cost, capacity, etc.). Finally, the actual problem formulation part (in Sect. 5) gives detail formulations of the individual partial problems.
4 FTTH network model
In this section, we present a detailed model of the resources of an FTTH-OAN networks (see Fig. 1) that is suitable to the needs of our optimization problem formulation. The model (see Fig. 3) comprises the network fragment—see Sect. 4.1—that describes resources of a set of network layers and the equipment fragment—see Sect. 4.2—that defines a catalogue of equipment admissible for installation in infrastructure segments and infrastructure nodes (like segment preparation types, cables, cable closures, splitters, hardware cabinets, OLT devices, OLT cards, etc.).
Fig. 3
Model fragments
×
4.1 Network fragment
According to general rules for modeling telecommunication networks, e.g., [9], we split the network fragment into a stack of layers where, for each pair of neighbor layers, the upper layer (the client) takes advantage of resources provided by the lower layer (the server). We distinguish four layers—going from the top—the signal layer, the bundle layer, the cable layer, and finally the infrastructure layer.
We start the description with the signal layer model (in Sect. 4.1.3) that constitutes a necessary foundation for our optimization approach, as it identifies elements—signal nodes and signal links—necessary to provide signal network connections between OLT and ONT devices. Unfortunately, as the signal model distinguishes every individual element, its direct application in the optimization problem formulation would lead to unacceptably large optimization problem instances. To overcome that difficulty, we introduce the aggregated bundle layer model (in Sect. 4.1.4) that considers bundles (groups) of signal nodes and signal links instead of individual ones. Links of the bundle layer are supported by optical fibers and optical cables modeled (informally) as the cable layer (see Sect. 4.1.2). Finally, the infrastructure layer (in Sect. 4.1.1) models placeholders, e.g., ducts, trenches, manholes, overhead lines, where cables and active/passive network devices can be installed.
Due to complex relations between the layers, we arranged their description in the sequence that does not adhere to the layer ordering; due to the same reason, description of the layers is complemented by Sect. 4.1.5 that introduces concepts referring to every layer.
Fig. 4
Topology of the infrastructure layer
×
4.1.1 Infrastructure layer model
The infrastructure layer represents a network of ducts (or overhead lines) interconnected by manholes (masts) that can accommodate optical cables supporting one or more ODN networks. The network is required to be connected, as there must exist at least one path between the Central Office and every ONT (and distribution) node.
Topology of the infrastructure layer (see Fig. 4) is modeled by undirected graph \(G^I\!=\!(\mathcal {N}^I,\mathcal {L}^I)\) with set of infrastructure nodes\(\mathcal {N}^I\) and set of undirected infrastructure links\(\mathcal {L}^I\subseteq \mathcal {N}^I\times \mathcal {N}^I\). An infrastructure node \(n\in \mathcal {N}^I\), represents a location, such as a manhole or a mast, in which optical cables can be terminated, while an infrastructure link \(l\in \mathcal {L}^I\) represents a placeholder, e.g., a trench or an overhead line, between a pair of infrastructure nodes. Every infrastructure link can accommodate a number of optical cables.
We distinguish (see Fig. 4) a set \(\mathcal {N}^{IS}\subseteq \mathcal {N}^I\) of infrastructure sites, i.e., such nodes that are equipped to hold either active devices (OLT, ONT) or signal splitters. These sites, depending on their location in a network’s service area (cf. Fig. 1), are partitioned into central office sites \(\mathcal {N}^{ISO}\equiv \{n^{iso}\}\) (the unique central office site \(n^{iso}\), is marked in Fig. 1 by CO), distribution point sites \(\mathcal {N}^{ISD}\) (marked by DP), access point sites \(\mathcal {N}^{ISA}\) (denoted by AP), and customer premise sites \(\mathcal {N}^{ISP}\) (marked by CP).
At last we define set \(\mathcal {P}^I \subseteq \mathcal {L}^I\), of all infrastructure paths with a proper subset \(\mathcal {P}^{IS}\subset \mathcal {P}^I\) of infrastructure trails; by assumption, for a pair \((n_1, n_2) \in \mathcal {N}^{IS} \times \mathcal {N}^{IS}\) of infrastructure sites there is selected at most one infrastructure path \(p\in \mathcal {P}^{I}: p \in \mathcal {P}^{IS}\) referred to as infrastructure trail of that pair.
4.1.2 Cable layer model
An infrastructure trail \(p\in \mathcal {P}^{IS}\), supports a number of parallel directed fiber connections between a pair of its end infrastructure sites. Each fiber connection (see Fig. 5) consists of a sequence of directed fiber segments, connected temporarily or permanently at infrastructure nodes by means of ODFs or optical splices. A fiber segment in turn is a continuous segment of an optical fiber that (together with other fiber segments) resides within a single directed optical cable segment. Finally, the optical cable segment is a continuous segment of optical cable deployed in an infrastructure path consisting of one or more infrastructure segments.
Fig. 5
Fibers and cables
×
4.1.3 Signal layer model
For a single FTTH-OAN network, the signal layer provides a set of downward signal network connections between ports of the OLT device (at the CO site) and ONT terminals (at CP sites) as well as a set of corresponding upward network connections that connects the ONTs to the OLTs. These network connections are provided by passive ODNs (optical distribution networks—each ODN is fed with an optical signal from a single port of the OLT) consisting of a set of signal splitters (signal layer nodes) interconnected by bidirectional optical fiber paths (bidirectional signal layer links).
Fig. 6
Signal nodes, links, and link connections
×
The topology of the signal layer is represented by graph \(G^S=(\mathcal {N}^S, \mathcal {L}^S)\) consisting of the set of signal nodes \(\mathcal {N}^S\) and the set of directed signal links \(\mathcal {L}^S\). Signal nodes \(\mathcal {N}^S\) represent signal transport functions performed by active (OLT and ONTs) and passive (splitters) devices. Signal links \(\mathcal {L}^S\) represent in turn individual optical fiber paths interconnecting pairs of signal nodes. Set of signal nodes \(\mathcal {N}^S\) is partitioned (see Fig. 6) into set \(\mathcal {N}^{SH}\equiv \{n^{sh}\}\) of head-end nodes (a singleton representing the OLT device), set \(\mathcal {N}^{SA}\) of access nodes (representing either ONT or ONU devices), and set \(\mathcal {N}^{SD}\) of signal distribution points representing real or null2 splitters. Set \(\mathcal {N}^{SD}\) is further partitioned into sets \(\mathcal {N}^{SDH}\), \(\mathcal {N}^{SDD}\), and \(\mathcal {N}^{SDA}\) referred to, respectively, as head-end, distribution, and access signal distribution points. The partitioning reflects the level occupied by particular splitters within involved network connections. Access nodes \(\mathcal {N}^{SA}\) are the actual sources of demand—the signal demand of individual access node \(n\in \mathcal {N}^{SA}\), i.e., the number of network connections it requires, is denoted by \(h^S(n)\).
A signal node \(n\in \mathcal {N}^S\), depending on its class—either \(\mathcal {N}^{SH}\), \(\mathcal {N}^{SDH}\), \(\mathcal {N}^{SDD}\), \(\mathcal {N}^{SDA}\), or \(\mathcal {N}^{SA}\)—has defined a subset of infrastructure site types—either \(\mathcal {N}^{ISO}\), \(\mathcal {N}^{ISD}\), \(\mathcal {N}^{ISA}\), or \(\mathcal {N}^{ISP}\)—it can be deployed in. To show the feasible allocations, we take advantage of function \(si\_site(n): \mathcal {N}^S \mapsto \mathcal {N}^{IS}\), that for a given signal node \(n\in \mathcal {N}^S\), designates its hosting infrastructure site \(s\in \mathcal {N}^{IS}\). The following assignments are (by assumption) considered as feasible:
the single head-end signal node \(n^{sh}\in \mathcal {N}^{SH}\) must be assigned to the single CO site \(n^{iso}\in \mathcal {N}^{ISO}\), i.e., \(si\_site(n^{sh})\equiv n^{iso}\),
every head-end signal distribution point \(n\in \mathcal {N}^{SDH}\) must be assigned to the single CO site \(n^{iso}\), i.e., \(\forall _{n\in \mathcal {N}^{SDH}}, si\_site(n)\equiv n^{iso}\),
each distribution signal distribution point \(n\in \mathcal {N}^{SDD}\) can be assigned to either the CO site \(n^{iso}\) or to any DP site \(s\in \mathcal {N}^{ISD}\), i.e., \(\forall _{n\in \mathcal {N}^{SDD}}, si\_site(n) \in \{ n^{iso}\} \cup \mathcal {N}^{ISD}\),
each access signal distribution point \(n\in \mathcal {N}^{SDA}\) can be assigned to an infrastructure site of any type but the CP, i.e, \(si\_site(n)\in \mathcal {N}^{ISO} \cup \mathcal {N}^{ISD} \cup \mathcal {N}^{ISA}\),
finally, each access signal node \(n\in \mathcal {N}^{SA}\), must be assigned to one of CP infrastructure sites \(s\in \mathcal {N}^{ISP}\).
4.1.4 Bundle layer model
The signal layer model identifies every individual element necessary to provide signal network connections between OLT and ONT devices. As its direct application would lead to unacceptably large optimization problem instances, we decided to introduce the aggregated model, called bundle layer model, that considers bundles (groups) of signal nodes and signal links instead of individual ones.
The considered bundle layer model consists of directed graph \(G^B\!=\!(\mathcal {N}^B,\mathcal {L}^B)\) with the set of bundle nodes \(\mathcal {N}^B\) and the set of bundle links \(\mathcal {L}^B\). Graph \(G^B\) constitutes a contraction of graph \(G^S=(\mathcal {N}^S, \mathcal {L}^S)\) of the signal layer, where each bundle node \(n_b\in \mathcal {N}^B\), represents subset \(\mathcal {N}^S_b \subseteq \mathcal {N}^S\) of the signal nodes; each bundle link \(l_b\in \mathcal {L}^B: l_b\in \delta (n_b)\) incident to bundle node \(n_b\) represents in turn set \(\mathcal {L}^S_b=\{l_s\in \mathcal {L}^S: l_s\in \delta (\mathcal {N}^S_b)\}\) of every signal link incident to that selected subset of signal nodes. To facilitate the mapping between the signal and bundle layer models, we introduce function \(bs\_nmap( n_{b}): \mathcal {N}^B \mapsto 2^{|\mathcal {N}^S|}\) that defines a subset of signal nodes \(\mathcal {N}^S\) aggregated to bundle node \(n_{b}\in \mathcal {N}^B\) and function \(bs\_lmap(ln_{b}): \mathcal {L}^B \mapsto 2^{|\mathcal {L}^S|}\) that defines a subset of signal links represented by single bundle link \(l_b\).
Fig. 7
Bundle nodes and bundle links
×
We identify the following subsets of bundle nodes (cf. Fig. 7):
singleton set \(\mathcal {N}^{BH}\equiv \{n^{bh}\}\) that aggregates the head-end signal node \(n^{sh}\) and every head-end signal distribution point \(n_{sdh}\in \mathcal {N}^{SDH}\), that are located in CO infrastructure site \(n^{iso}\). Referring to the sample network presented in Fig. 7, single bundle head-node \(n^{bh}\) aggregates head-end signal node \(n^{sh}\) as well as two head-end signal distribution points \(n_{sdh1}\) and \(n_{sdh2}\);
set \(\mathcal {N}^{BD}\) of distribution bundle nodes; each distribution bundle node \(n_{bd}\in \mathcal {N}^{BD}\), corresponds to the CO or a single DP infrastructure site \(n_{is}\in \mathcal {N}^{ISO}\cup \mathcal {N}^{ISD}\) and aggregates every distribution signal distribution points \(n_{sdd}\in \mathcal {N}^{SDD}: si\_site(n_{sdd})= n_{is}\), located in that site. In the sample network (see Fig. 7), there are two distribution bundle nodes \(n_{bd1}\) and \(n_{bd2}\) that aggregate, respectively, a subset of distribution signal distribution points \(\{n_{sdd1}, n_{sdd2}, n_{sdd3}\}\) and \(\{n_{sdd4}\}\);
set \(\mathcal {N}^{BA}\) of access bundle nodes; each access bundle node \(n_{ba}\in \mathcal {N}^{BA}\), relates to a single infrastructure site \(n_{is}\in \mathcal {N}^{IS}\), and aggregates every access signal distribution point \(n_{sda}\in \mathcal {N}^{SDA}: si\_site(n_{sda})=n_{is}\) as well as every access signal node \(n_{sa}\in \mathcal {N}^{SA}: si\_site(n_{sa})=n_{is}\) located at that site. In the sample network (in Fig. 7), there are three access bundle nodes \(n_{ba1}\), \(n_{ba2}\), and \(n_{ba3}\) that aggregate, respectively, subsets \(\{n_{sda1}, n_{sda2}, n_{sa1}\}\), \(\{n_{sda3}, n_{sa2}\}\), and \(\{n_{sda4}, n_{sa3}\}\) of the signal nodes.
We introduce function \(c( n): \mathcal {N}^{BD} \mapsto 2^{|\mathcal {N}^{BA}|}\) that for each distribution bundle node \(n\in \mathcal {N}^{BD}\) distinguishes a subset \(\{m\in \mathcal {N}^{BA}: \exists {l\in \mathcal {L}^{BD}}, b\_a(l)= n \wedge b\_b(l)=m\}\) of bundle access nodes connected to this distribution node by a bundle link; such set is hereafter referred to as distribution cone of distribution node n.
Bundle links \(\mathcal {L}^B\) are further split into trunk bundle links\(\mathcal {L}^{BH}\) and distribution bundle links\(\mathcal {L}^{BD}\) that interconnect, respectively, the head-end bundle node \(n^{bh}\) with distribution bundle node \(n\in \mathcal {N}^{BD}\), and distribution bundle node \(n\in \mathcal {N}^{BD}\), with access bundle node \(m\in \mathcal {N}^{BD}\). With assistance of functions \(bb\_a( l): \mathcal {L}^B \mapsto \mathcal {N}^B\) and \(bb\_b( l): \mathcal {L}^B \mapsto \mathcal {N}^B\) that identify, respectively, the start and the end bundle node of a directed bundle link \(l\in \mathcal {L}^B\), these two sets can be formally defined as, respectively, \(\mathcal {L}^{BH}= \{l\in \mathcal {L}^{B}: bb\_a(l) \in \mathcal {N}^{BH}, bb\_b(l) \in \mathcal {N}^{BD}\}\) and \(\mathcal {L}^{BD}= \{l\in \mathcal {L}^{B}: bb\_a(l) \in \mathcal {N}^{BD}, bb\_b(l) \in \mathcal {N}^{BA}\}\). Sets \(\mathcal {L}^{BH}\) and \(\mathcal {L}^{BD}\) constitute the partitioning of set \(\mathcal {L}^B\).
The actual demand for signal network connections is generated in access bundle nodes \(\mathcal {N}^{BA}\); demand \(h^B_{n}\) of each individual access bundle node \(n\in \mathcal {N}^{BA}\) can be computed using the following expression:
A directed bundle link \(l\in \mathcal {L}^B\), of the bundle layer is supported by a set of parallel fiber connections between \(si\_site( bb\_a(l))\) and \(si\_site(bb\_b(l))\) infrastructure sites. By assumption, all these fiber connections use the same infrastructure trail \(bi\_p(l)\in \mathcal {P}^{IS}\) (where function \(bi\_p(l): \mathcal {L}^B \mapsto \mathcal {P}^{IS}\) defines an infrastructure trail taken by every fiber connection supporting bundle link l).
Consider a directed trunk bundle link from set \(\mathcal {L}^{BH}\). Every fiber connection that supports that link is called a trunk fiber connection that uses a trunk infrastructure trail and consists of trunk fiber segments (observe that fiber connections and fiber segments are directed w.r.t. bundle link they support). Then, every cable segment that contains trunk fibers is referred to as trunk cable segment and every infrastructure segment that hosts at least one trunk cable segment is referred to as trunk infrastructure segment. The same rules hold with respect to distribution bundle links; thus, they identify distribution infrastructure trails, distribution fiber connections, distribution fiber segments, distribution cables, and finally distribution infrastructure segments.
According to the above rules, we identify set of trunk infrastructure trails\(\mathcal {P}^{ISH}\) and set of distribution infrastructure trails\(\mathcal {P}^{ISD}\). We denote sets of trunk infrastructure segments and distribution infrastructure segments by, respectively, \(\mathcal {L}^{IH}\subseteq \mathcal {L}^I\) and \(\mathcal {L}^{ID}\subseteq \mathcal {L}^I\); we emphasise that sets \(\mathcal {L}^{IH}\) and \(\mathcal {L}^{ID}\) generally do not constitute the partitioning of set \(\mathcal {L}^I\), i.e., an infrastructure link from set \(\mathcal {L}^I\) can belong to both, either, or neither of these sets.
We assume that all trunk infrastructure trails from set \(\mathcal {P}^{ISH}\) that use a single trunk infrastructure segment from set \(\mathcal {L}^{IH}\) traverse the segment in the same direction (the same rule holds in the context of distribution infrastructure trails \(\mathcal {P}^{ISD}\) and distribution infrastructure segments \(\mathcal {L}^{ID}\)). Thus, trunk, as well as distribution, infrastructure segments can be considered as directed. Functions \(ii\_a(l):\mathcal {L}^{I}\mapsto \mathcal {N}^I\) and \(ii\_b(l):\mathcal {L}^{I}\mapsto \mathcal {N}^I\) defines, respectively, the starting and the terminating infrastructure nodes of the infrastructure segment.
Observe that trunk segments in set \(\mathcal {L}^{IH}\) constitute a directed tree with the root at the CO site \(n^{iso}\), while distribution segments in set \(\mathcal {L}^{ID}\) constitute a forest of directed trees, each rooted at a site that hosts a distribution bundle node from set \(\mathcal {N}^{BD}\). Thus, for each trunk segment \(l\in \mathcal {L}^{IH}\) there is none or exactly one ancestor trunk segment \(ii\_ah(l)\) (satisfying \(ii\_b(ii\_ah(l))=ii\_a(l)\)) that connects segment l to its corresponding trunk tree. Similarly, for each distribution segment \(k\in \mathcal {L}^{ID}\) there is none or exactly one ancestor distribution segment \(ii\_ad(k)\) (satisfying \(ii\_b(ii\_ad(k))=ii\_a(k)\)) that connects segment k to its distribution tree.
4.2 Equipment catalogue fragment
The equipment fragment completes the network fragment with catalogue sets defining types of physical equipment admissible for installation at infrastructure nodes, infrastructure segments, and sites of an FTTH network. Every catalogue set is denoted by \(\mathcal {T}\) with a lowercase upper index; the same lowercase index is used for distinguishing properties of an instance of a particular type. Parameters common to every type, like cost or capacity, are denoted by lowercase Greek letters \(\varsigma \) and \(\eta \) with appropriate upper indices.
A brief list of catalogue sets is listed in Table 1.
Set of OLT card types \(\mathcal {T}^c\) identifies types of OLT cards that can be deployed in OLT devices. Each card type \(c\in \mathcal {T}^c\), is characterized by its cost \(\varsigma ^c\), number \(\eta ^c\) of ports, and transmission power \(p^c\) of each port.
4.2.2 OLT devices
Set of OLT device types \(\mathcal {T}^o\) identifies admissible types of OLT devices. Each OLT device type \(o\in \mathcal {T}^o\), is characterized by its cost \(\varsigma ^o\), weight \(w^o\) (i.e., the amount of OLT capacity \(\eta ^{fo}\) it requires in the hosting site), maximum number \(\eta ^o\) of OLT cards it can hold, and set \(\mathcal {T}^{c}(o)\subseteq \mathcal {T}^c\) of OLT card types it can host.
4.2.3 Optical splitters
Set \(\mathcal {T}^r\) identifies admissible types of symmetrical optical splitters. Each particular type of splitter \(r\in \mathcal {T}^r\), is characterized by its cost \(\varsigma ^r\), split ratio \(\eta ^r\), and attenuation \(a^r\) a splitter of this type introduces into a signal network connection. Set \(\mathcal {T}^r\) contains admissible real splitters complemented by an artificial null splitter\(r^1\) with \(\eta ^{r^1}=1\), \(a^{r^1}=0\), and \(\varsigma ^{r^1}=0\). The operation facilitates the modeling process by preserving structural homogeneity of every network connection.
4.2.4 Admissible splitter combinations
Set of admissible triples of splitter types \(\mathcal {T}^{3r}\subseteq \mathcal {T}^r \times \mathcal {T}^r \times \mathcal {T}^r\) facilitates reduction of the number of splitting combinations taken into account in the optimization problem what can lead to significant reduction of the computation time.3 To facilitate the formulation, we additionally introduce set of admissible splitter type pairs \(\mathcal {T}^{2r}\subseteq \mathcal {T}^r \times \mathcal {T}^r\); certainly, sets \(\mathcal {T}^{3r}\) and \(\mathcal {T}^{2r}\) must be consistent, i.e., \(\mathcal {T}^{2r}=\{(r,s): \exists {(t,u,v)\in \mathcal {T}^{3r}}, r=t, s=v \}\).
4.2.5 Sites
Each site type \(f\in \mathcal {T}^f\), represents one of possible site arrangements, e.g., a dedicated building, a street cabinet, a pole box, etc.; it is characterized by its cost \(\varsigma ^f\) and two capacity parameters—cabinet capacity \(\eta ^{fe}\) and OLT capacity \(\eta ^{fo}\)—that define the maximum total weight of, respectively, cabinets and OLT devices a site of the particular type can host.
4.2.6 Hardware cabinets
Equipment deployed within a site is installed in one or more hardware cabinets (equipment racks). Each cabinet type \(e\in \mathcal {T}^e\), is characterized by its weight \(w^e\) (i.e., the amount of cabinet space \(\eta ^{fe}\) it consumes within a hosting site), cost \(\varsigma ^e\), and the maximum number of splitter ports \(\eta ^e\) it can accommodate.
4.2.7 Fiber splices
A fiber splice models permanent connection between two fiber segments. We distinguish only one splice type with cost \(\varsigma ^q\) (deployment of a splice requires engagement of skilled personnel and specialized tools) and attenuation \(a^q\).
4.2.8 Cable closures
There is a given number of cable closure types listed in set \(\mathcal {T}^u\); each type \(u\in \mathcal {T}^u\), is characterized by its cost \(\varsigma ^u\) and capacity \(\eta ^u\), i.e., the number of fiber splices it can accommodate.
4.2.9 Cables
Set \(\mathcal {T}^a\) comprises all admissible cable types; cable type \(a\in \mathcal {T}^a\), is characterized by its cost \(\varsigma ^a\) and by the number of fibers \(\eta ^a\) it contains.
Cable types can additionally differ in terms of their mechanical construction, external shielding, etc. Installation restrictions related to these additional parameters are taken into account in the specification of the segment preparation catalogue set—see the next section.
4.2.10 Infrastructure segment preparations
We define set \(\mathcal {T}^g\) of every segment preparation, i.e., of every technique—like towing, blowing, pulling-in, etc.—that can be used to install a cable segment. Each particular technique (segment preparation) \(g\in \mathcal {T}^g\), due to its mechanical and operational requirements, can be applied to only subset \(\mathcal {T}^a(g)\) of cable types.
Each infrastructure segment \(l\in \mathcal {L}^I\), is described by a subset of admissible segment preparation types \(\mathcal {T}^g(l)\subseteq \mathcal {T}^g\).
To facilitate the model formulation, we take advantage of auxiliary set \(\mathcal {T}^a(l)\subseteq \mathcal {T}^a =\bigcup _{g\in \mathcal {T}^g}\mathcal {T}^a(g)\), \(l\in \mathcal {L}^I\) of cable types admissible for installation at infrastructure segment \(i\in \mathcal {L}^I\).
4.2.11 Common constants
We take advantage of the following additional constant parameters:
common fiber attenuation per kilometer, denoted by a,
common signal power expected at the input port ONT/ONU device, denoted by \(t_c\). The value of this constant can take into account not only the sensitivity of the receiving port but also some additional reserve to compensate aging of optical fibers and components, thermal fluctuations, manipulation, etc. This constant can be easily differentiated between particular access nodes not introducing any additional complexity to the optimization problem.
5 Partial problems detail formulations
This section gives detail formulations of the partial problems—namely the bundle layer dimensioning partial problem \(\mathcal {P}^B\), the cable partial problem \(\mathcal {P}^I_{cable}\), the splice partial problem \(\mathcal {P}^I_{splice}\), and the site partial problem \(\mathcal {P}^I_{site}\) (as introduced in Sect. 3). The mentioned partial problems are described, respectively, in Sects. 5.1, 5.2, 5.3, and 5.4. Each of these sections comprises four parts: the assumptions part (containing assumptions taken in relation to each partial problem; the assumptions have found strong motivation in design and operations practices followed by our industrial partners), the decision variable definition part, the feasible set definition part, and the cost component part. The cable, splice, and the site partial problems contain additional description of variables that link their decision variables with variables of the bundle layer dimensioning partial problem.
The optimization problem aims at minimization of the total cost of the network deployment (1) (see Sect. 3).
5.1 Bundle layer dimensioning partial problem
The bundle layer dimensioning partial problem aims at evaluating the number and types of splitters installed at the head, distribution, and access bundle nodes. Moreover, it selects the number and types of OLT cards installed at the CO site. The provided solution guarantees that every CP site, regardless its distance to the CO site, is provided with a sufficiently strong optical signal.
5.1.1 Assumptions
It is assumed that:
there is exactly one head-end bundle node \(n^{bh}\),
distribution cone \(bb\_c(n)\) of each distribution bundle node \(n\in \mathcal {N}^{BD}\), is given,
the physical length of every infrastructure trail is given; thus, the distance from each access bundle node \(a\in \mathcal {N}^{BA}\), to the head-end bundle node is also known,
every signal network connection that satisfies demand of a given access bundle node \(n\in \mathcal {N}^{BA}\), shares the same distribution infrastructure trail \(p\in \mathcal {P}^{ISD}\), as well as the same trunk infrastructure trail \(q\in \mathcal {P}^{ISH}\),
only symmetrical splitters with uniform splitting ratios are admissible.
The first three assumptions result from the way the presented model is used, i.e., to upgrade solutions returned by heuristic methods by changing sizes of cables and replacing splitters and cabinets. Therefore, trails and their lengths are given and are not subject to changes. The fourth assumption constraints the base (to be upgraded) solutions to use a single path for a single demand. In the paper, resiliency is not taken into account. Therefore, solutions that use more than one path to reach a single customer most probably would not be cost effective. Finally, we restrict our research to symmetrical splitters, because they appear to be much common in use. Still, our model can be extended to cover the case of asymmetric splitters.
5.1.2 Decision variables
The signal layer partial problem introduces the following decision variables.
Integer variables \(R_{cr}\!\in \!\mathbb {Z}_+\), \(\,R_{vcr}\!\in \!\mathbb {Z}_+\), and \(\,R_{tcr}\!\in \!\mathbb {Z}_+\), that represent the number of splitters of type \(r\in \mathcal {T}^r\), being fed from an OLT card of type \(c\in \mathcal {T}^c\), installed, respectively, at the head-end, distribution \(v\in \mathcal {N}^{BD}\), or access \(t\in \mathcal {N}^{BA}\), bundle nodes.
Variable \(X_{vcr}\in \mathbb {R}_+\), that represents the number of signal links at a trunk bundle link leading from the head-end bundle node \(n^{bh}\) to distribution bundle node \(v\in \mathcal {N}^{BD}\), fed from an OLT card of type \(c\in \mathcal {T}^c\), and connected at the head-end bundle node to a splitter of type \(r\in \mathcal {T}^r\).
Variable \(X_{vtcrs} \in \mathbb {R}_+\), that represents the number of signal links at distribution bundle link \(l\in \mathcal {L}^{BD}\), leading from distribution bundle node \(v\in \mathcal {N}^{BD}:bb\_a(l)=v\), to access bundle node \(t\in c(v):v=bb\_b(l)\), in v’s distribution cone; the signal links are fed from an OLT card of type \(c\in \mathcal {T}^c\), and are connected at their distribution v and access t bundle nodes to splitters of type, respectively, \(r\in \mathcal {T}^r\), and \(s\in \mathcal {T}^r\).
Integer variable \(Z_{vcnm} \in \mathbb {Z}_+\), that represents the number of signal links at a trunk bundle link connecting the head-end bundle node to distribution bundle node \(v\in \mathcal {N}^{BD}\), fed from an OLT card of type \(c\in \mathcal {T}^c\), and connected to a splitter of type \(n\in \mathcal {T}^r\), at the head-end bundle node and to a splitter of type \(m\in \mathcal {T}^r\), at distribution bundle node v, such that \((n,m)\in \mathcal {T}^{2r}\).
Finally, integer variable \(C_c \in \mathbb {Z}_+\), represents the number of OLT cards of type \(c\in \mathcal {C}\), installed at the head-end node \(n^{bh}\).
5.1.3 Feasible set
To simplify the formulation, we hereafter assume that set \(\mathcal {T}^c\) is a singleton, i.e., there is exactly one type of an OLT card that can be installed at the head-end bundle node \(n^{bh}\); thus, we can skip indexing set \(\mathcal {T}^c\) in constraints (3a)–(3f). Then, the signal layer partial problem can be presented in the following form.
Constraints (3a) ensure that the total number of signal links at trunk bundle links that are connected at the head-end node to splitters of type \(r\in \mathcal {T}^r\), is not greater than the total number of output ports of such splitters installed at the head-end node.
Constraints (3b) enforce that the number of signal links entering distribution node \(v\in \mathcal {N}^{BD}\), and connected in-there to splitters of type \(s\in \mathcal {T}^r\), is equal to the number of such splitters installed at node v.
Constraints (3c) enforce consistency between variables \(Z_{vcrs}\) and \(X_{vcr}\) stating that the number \(X_{vcrs}\) of signal links at trunk bundle link \(l\in \mathcal {L}^{BD}: bb\_a(l)=n^{bh}, bb\_b(l)=v\), which are connected to splitters of type \(r\in \mathcal {T}^r\), at the head-end node and terminated at splitters of type \(s\in \mathcal {T}^r\), at distribution node v, is lower than the total number \(Z_{vcrs}\) of signal links at this bundle link connected to splitters of type r at the head-end node.
Similarly, constraints (3d) enforce consistency between variables \(Z_{vcrs}\) and \(X_{vtcrs}\) stating that the number of signal links entering access node \(t\in \mathcal {N}^{BA}\), and split at the head-end and distribution nodes \((n^{bh},v)\), \(v\in \mathcal {N}^{BD}\), by splitters of type \((r,s)\in \mathcal {T}^{2r}\), does not exceed the number of output ports of s-type splitters installed at node v, as enforced by respective \(Z_{vcrs}\) variables.
Constraints (3e) ensure that the total number of splitters installed at access node \(t\in \mathcal {N}^{BA}\), does not exceed the total number of signal links entering that node.
Then, constraints (3f) state that the number of w-type splitters installed at access node \(t\in \mathcal {N}^{BA}\), does not exceed the number of signal links entering that node that deliver a sufficiently strong signal. It takes advantage of an auxiliary set \(\mathcal {T}^{2r}_t\subseteq \mathcal {T}^{2r}\) of splitter pairs that guarantees satisfaction of the power budget at access bundle node t defined as \(\mathcal {T}^{2r}_t= \{(r,s) \in \mathcal {T}^{2r}: \exists (a,b,w)\in \mathcal {T}^{3r}, a=r, b=s, a_{rsw} + d_t \cdot a \le t_c\}\), where a denotes an attenuation introduced to optical signal by one kilometer of a fiber and \(t_c\) (see Sect. 4.2.11) denotes the power of optical signal required at input ports of ONT/ONU devices.
Constraints (3g) establish the number \(C_c\) of OLT cards of type \(c\in \mathcal {T}^c\), installed at the head-end node, such that all splitters installed at the head-end node are fed with a sufficiently strong optical signal.
Finally, constraints (3h) state that every signal demand \(h(t), t\in \mathcal {N}^{BA}\) is satisfied; thus, the total number of output signal links of access node \(t\in \mathcal {N}^{BA}\), (which is limited from above by the number of output ports of splitters installed in-there) is not lower than the number of optical signals it requires.
5.1.4 Induced cost
Formulation (3) enforce the installation of specific equipment—OLT cards and optical splitters—at the head-end, distribution, and access bundle nodes. The total cost of this equipment, referred hereafter to as \(\zeta ^{B}\), is expressed by the following equation.
in which consecutive lines (4a), (4b), and (4c) express costs of equipment installed at, respectively, the head-end, distribution, and access bundle nodes.
5.2 Cable partial problem
The cable partial problem consists in evaluating the number and types of trunk and distribution cables to be installed at each infrastructure segment \(l\in \mathcal {L}^I\). The installed cables are to provide the number of trunk and distribution fibers, as required in the bundle layer partial problem \(\mathcal {P}^B\).
5.2.1 Assumptions
We apply the following (simplifying) assumptions:
distribution bundle links of different distribution bundle nodes do not share infrastructure segments,
there is at most one trunk cable at an infrastructure segment,
there is at most one distribution cable at an infrastructure segment,
infrastructure segment can be attributed with at most one segment preparation,
trunk and distribution fiber segments cannot share a cable segment meaning that a distribution fiber and a trunk fiber cannot be buried in the same cable.
The assumptions are introduced not only to make the resulting optimization problem more tractable, but also to simplify the deployment, management, and maintenance of resulting networks. It is worth to notice that the first four assumptions do not restrict spectrum of possible resulting designs, because multiple cables at a same segment can be introduced in input data by adding cable types that in fact consist of a number of independent parallel physical cables. The fifth assumption restricts the region of feasible solutions by eliminating some designs that could prove to be cost-effective. However, according to our preliminary research, cases when a trunk fiber and a distribution fiber can share a cable are not frequent. What is more, the lengths of those shared segments are too small to justify splicing a large number of fibers when the segments end. Summarizing, the fifth assumption increases costs of obtained solutions. However, the increase is not significant and in our opinion does not justify complicating the model at this level. Still, we believe that the fifth assumption can be mitigated in lower level models or in actual network deployments.
5.2.2 Linking variables
We introduce variables \(X^{IH}_l\in \mathbb {R}_+: l\in \mathcal {L}^{IH}\) and \(X^{ID}_k\in \mathbb {R}_+: k\in \mathcal {L}^{ID}\) to link the cable partial problem with the bundle layer partial problem presented in Sect. 5.1. These two variables represent the required number of fibers at, respectively, trunk segment \(l\in \mathcal {L}^{IH}\), and at distribution segment \(k\in \mathcal {L}^{ID}\). They are linked to the variables of the bundle layer partial problem by constraints (5).
In constraints (5) we exploit a set of distribution bundle nodes \(\mathcal {N}^{BD}_i\) and a set of access bundle nodes \(\mathcal {N}^{BA}_i\) whose infrastructure trails take advantage of infrastructure segment \(i\in \mathcal {L}^I\); these sets are defined by the following expressions:
For each infrastructure segment \(l\in \mathcal {L}^I\), we introduce binary variable \(G^{I}_{lg}\in \{0,1\}\), to indicate which segment preparation \(g\in \mathcal {T}^g(l)\), has been selected in that segment.
The number of fibers to be installed in trunk and distribution cables at infrastructure segment \(l\in \mathcal {L}^I\), is then expressed by integer variables, respectively, \(Z^{IH}_l\in \mathbb {Z}_+\) and \(Z^{ID}_l\in \mathbb {Z}_+\); the actual number of trunk and distribution cables of each particular type \(a\in \mathcal {T}^a(l)\), installed in-there is represented by, respectively, integer variables \(A^{IH}_{la}\in \mathbb {Z}_+\) and \(A^{ID}_{la}\in \mathbb {Z}_+\).
5.2.4 Feasible set
Hereafter we present constraints (7) that enforce dimensioning of only distribution cables at infrastructure segment \(i\in \mathcal {L}^{ID}\). The complete formulation would require in addition the analogous set of constraints for dimensioning of trunk cables.
Constraints (7a) enforce that each infrastructure distribution segment \(l\in \mathcal {L}^{ID}\), is assigned with at most one segment preparation type.
Constraints (7b) and (7c) state that type \(a\in \mathcal {T}^a(l)\), of distribution cable installed in segment \(l\in \mathcal {L}^{IA}\), is consistent with cable preparation type \(g\in \mathcal {G}^g(l)\), selected for that segment.
Constraints (7d) set the value of variable \(Z^{ID}_l\) to the total number of fibers in distribution cables installed at segment l.
Finally, constraints (7e) ensure that the number of fibers \(Z^{ID}_l\) in distribution cables installed at infrastructure segment l is sufficient.
5.2.5 Induced cost
Formulation (7) selects segment preparation for distribution (and in the complete version, trunk) infrastructure segments and establishes the number and types of distribution (and trunk) cables deployed in-there. The related cost \(\zeta ^{I}_{cable}\) can be evaluated with the following expression:
The splices and closures partial problem aims at deciding on splicing of optical fibers at infrastructure nodes. Moreover, it decides on types of closures that protect groups of splices in trunk or distribution cables.
5.3.1 Assumptions
None.
5.3.2 Decision variables
Integer variable \(Q^{ID}_l\in \mathbb {Z}_+\), represents the number of distribution splices at the starting node \(ii\_a(l)\) of distribution segment \(l\in \mathcal {L}^{ID}\).
Variable \(W^{ID}_n\in \mathbb {R}_+\), represents the number of splices that are necessary to connect access bundle node \(n\in \mathcal {N}^{BA}\) to collocated site \(s\in \mathcal {N}^{IS}: s=si\_site(n)\) (despite its domain, the variable receives integer value at the optimal solution). No splices are necessary if an entire cable enters a site.
Binary variable \(U^{ID}_{lu}\in \{0,1\}\), decides if closure of type \(u\in \mathcal {T}^u\), is installed at the terminating infrastructure node \(ii\_b(l)\) of distribution infrastructure segment \(l\in \mathcal {L}^{ID}\).
Binary variable \(g^{ID}_l\in \{0,1\}\), indicates if distribution cable at distribution segment \(l\in \mathcal {N}^{IA}\), has been cut, i.e., if splices are required at the starting node \(ii\_a(l)\) of this segment.
Finally, binary variable \(Y^{ID}_n\in \{0,1\}\), decides if at node \(n\in \mathcal {N}^{IS}\), there is a need for cutting fibers going to the collocated access site \(s\in \mathcal {N}^{ISA}: n=s\).
5.3.3 Feasible set
Because splices and closures at trunk and distribution cables are installed according to the same rules, we restrict the description solely to distribution cables.
Constraints (9a) enforce a cable-cut on a distribution cable at infrastructure node \(n\in \mathcal {N}^I\), in every case when node n is a common node of two consecutive distribution segments \(k\in \mathcal {L}^{ID}\), and \(l\in \mathcal {L}^{ID}\), (such that \(n=ii\_bd(k)\) and \(n=ii\_ad(l)\), or equivalently, \(k=ii\_pd(l)\)) that host distribution cables of different types.
Fig. 8
Necessary cable cut in a non-leaf site
×
Constraints (9b) set the lower limit on the number of distribution splices \(Q^{ID}_l\) at the starting node of infrastructure distribution segment \(l\in \mathcal {L}^{IA}\), to the number of distribution fibres \(X^{ID}_l\) required at segment l (if there is a distribution cable cut at node \(n\in \mathcal {N}^{IA}: ii\_ad(l)\)), or to zero, otherwise; the big-M coefficient (denoted as M) is required to be bigger than the number of fibers in the thickest cable type in catalogue set \(\mathcal {T}^a\), i.e., \(M\ge \max _{a\in \mathcal {T}^a}\eta ^a\).
Constraints (9c) (see Fig. 8) ensure that, if infrastructure site \(s\in \mathcal {N}^{IS}\), hosts an access bundle node \(n\in \mathcal {N}^{BA}, bi\_site(n)=s\), which is not a leaf of the FTTH tree (case a) in Fig. 8, the (single, by the assumption of Sect. 5.2) distribution cable that goes through this node must be cut. Otherwise (case b) the cable as a whole can enter the site.
Finally, constraints (9d) and (9e) enforce that distribution splices at the starting end of distribution infrastructure link \(l\in \mathcal {L}^{ID}\) are enclosed within exactly one cable closure.
5.3.4 Induced cost
Splices and closures contribute to the total cost with the following cost components:
where line (10a) represents the total cost of splices, while line (10b) represents the total cost of installed closures.
5.4 Site equipment partial problem
The site equipment partial problem consists in evaluating the type and the amount of equipment installed at every infrastructure site.
5.4.1 Assumptions
None.
5.4.2 Linking variables
The total number of signal links incoming to/outgoing from infrastructure site \(s\in \mathcal {N}^{IS}\), necessary for attaching head-end (\(\mathcal {N}^{BH}\equiv \{n^{iso}\}\)), distribution \(d\in \mathcal {N}^{BD}\), and access \(a\in \mathcal {N}^{BA}\), bundle nodes hosted in-there is represented, respectively, by variables \(U^{BH-}\in \mathbb {Z}_+\), \(U^{BD+}_s\in \mathbb {Z}_+\), \(U^{BD-}_s\in \mathbb {Z}_+\), \(U^{BA+}_s\in \mathbb {Z}_+\), and \(U^{BA-}_s\in \mathbb {Z}_+\) that can be easily expressed by means of variables of the signal partial problem.
5.4.3 Decision variables
We use the following decision variables:
to designate site type \(f\in \mathcal {T}^f\) assigned to site \(s\in \mathcal {N}^{IS}\), we use binary variable \(F_{sf}\in \{0,1\}\),
the number of cabinets of type \(e\in \mathcal {T}^e\), installed at infrastructure site \(s\in \mathcal {N}^{IS}\), for hosted in-there head-end (\(n^{bh}\)), distribution \(\mathcal {N}^{BD}\subseteq \mathcal {N}^B\), and access \(\mathcal {N}^{BA}\subseteq {N}^B\), bundle nodes is represented, respectively, by integer variables \(E^{BH}_{ue}\in \mathbb {Z}_+\), \(E^{BD}_{ue}\in \mathbb {Z}_+\), and \(E^{BA}_{ue}\in \mathbb {Z}_+\),
the number of OLT devices of type \(o\in \mathcal {T}^o\) installed at CO site \(n^{iso}\) is represented by integer variable \(O_o\in \mathbb {Z}_+\).
5.4.4 Feasible set
The site equipment partial problem introduces the following constraints.
Constraints (11a) state that site \(s\in \mathcal {N}^{IS}\) is of at most one site type \(f\in \mathcal {T}^f\).
Then, constraints (11b) and (11c) ensure that the total weight of cabinets and the total weight of OLT devices installed at site \(s\in \mathcal {N}^{IS}\) do not exceed cabinet \(\eta ^{fe}\) and OLT \(\eta ^{fo}\) capacity of that site.
Next, constraints (11d) guarantee that OLT devices installed at the CO site can hold a required number of OLT cards of required types.
Finally, constraints (11e), (11f), and (11g) ensure that cabinets installed at infrastructure sites are able to accommodate the required number of signal links, either trunk or distribution, entering/leaving those sites.
5.4.5 Induced cost
Equipment installed in various sites of the FTTH network add new components to the total cost of the network design (we remember that the costs of OLT cards and optical splitters have already been taken into account in Sect. 5.1.4 with equations (3)). The additional components are expressed by the following equation.
in which line (12a) represents the total cost of installed cabinets, while line (12b) represents the total cost of site preparations and the cost of installed OLT devices.
6 Numerical results
In this section, we evaluate the performance of the presented MIP approach. First, we present the testing methodology used in our experiments. It is followed by a discussion on various simplifications and important setting modifications improving performance of the model. The third subsection covers profits the presented MIP method is able to generate. The section ends with a discussion on obtained optimality gaps.
6.1 Testing methodology
The proposed approach was implemented in AMPL and tested using CPLEX 12.6 on a Fujitsu RX200 server equipped with two Intel Xeon E5-2620v2 6C/12T 2.10GHz processors with 10 cores (20 threads) and 64 GB of RAM dedicated exclusively to our research. The method was compared to a heuristic approach presented in [24], which was implemented in C# using Visual Studio 2010. Both methods were run under Windows Server 2012.
Test cases were obtained using optimization algorithms of the framework presented in [24] on real-world FTTH design problems in Warsaw. The city is an interesting mixture of various building patterns starting from business districts of skyscrapers, through residential districts of MDUs (multi-dwelling-units), ending at vast areas of SFRs (single-family-residentials). Algorithms utilized to optimize head-end and distribution point locations were based on the simulated annealing. Starting from a number of random head-end and distribution point locations and significantly shortening the optimization time we were able to obtained rational designs characterized by notably different locations of head-end and distribution nodes. Therefore, the obtained test cases were by no mean a set of similar FTTH OAN instances.
Distribution and trunk trees are optimized using the simulated annealing. Starting trees are selected using a method that is a compromise between the shortest path algorithm and the minimum spanning tree algorithm. Neighboring solutions are obtained using the same compromise method by setting costs of some edges to zero. This way a large number of different, but reasonable and cost-efficient distribution and trunk trees can be tested. Finally, initial set of utilized splitter combinations is also optimized using the simulated annealing. Assuming that each demand can be served either by the minimum number of splitters or by a set of splitters, which is the smallest and minimizes the number of unused outputs, neighboring solutions are obtained by randomly selecting one of the two ways each demand is served. Details of the methods can be found in [24].
Twenty different designs of FTTH networks covering Warsaw were used. In total, the designs constituted of 200 different FTTH OANs, which varied in terms of their dimensions and capacities.4 General statistics concerning the test cases can be found in Table 2.
Table 2
Test cases
Min
Mean
Max
Demands
321
994
1440
Clients
13,152
23,308
36,849
Edges
740
2107
3179
Edges total length
38.1 km
67.8 km
106.0 km
The testing methodology was as follows. First, the heuristic method of [24] was run for time \(t_{heur}\). The obtained solution was used as a starting solution for the MIP method, which was run for time \(t_{MIP}\). The total time was denoted by \(t_{total}=t_{heur}+t_{MIP}\). In the experiments, we examined different values of \(t_{heur}\) and \(t_{MIP}\) comparing the total costs of obtained designs. The results are discussed in the following sections.
6.2 Simplifications and settings
The sizes of test cases and the quantities of different types of possible equipment do not allow to run the presented MIP model in the raw form. To use the model efficiently, a number of enhancements had to be implemented. First of all, we took a closed look to varieties of different equipment catalogue sets. In the experiments, we considered three different possible types of cabinets, two types of OLTs, six splitter types, three types of splice closures, and seventeen different cable types. Example cost values can be found in Table 3. For the most of equipment catalogue sets computationally reasonable number of types were used. Two apparent exceptions were the cable catalogue set and the splitter catalogue set. As far as the former set is concerned, we decided to limit the number of possible cable types to three for each edge taking: the cable type that had been selected by the heuristic method, one cable type that is slightly thinner than the selected (if possible), and one cable that is slightly thicker than the selected (if possible). The considered number of splitter types is not as large as the considered number of cable types. However, in the model, splitters depend on each other creating splitter combinations consisting of three ordered splitter types. Considering six splitter types the number of feasible (satisfying the splitting ratio constraint) splitter combinations reaches almost one hundred. Therefore, in the research we decided to limit the number of feasible combinations only to those that appeared for a given FTTH OAN in the heuristic solution. This way the sizes of catalogue sets were significantly reduced and the problem became approachable for commercial MIP solvers. Notice that because of reducing the sizes of catalogue sets we neither can assure that solutions returned by MIP solvers are optimal nor that the obtained optimality gap is meaningful. However, it does not influence the general conclusion of our research—using MIP modeling can improve upper bounds of real-world FTTH tree cost minimization problems.
Table 3
Example cost values
Equipment
Cost
OLT with 8 card slots
6000
Card with 8 B-class lasers
8000
Splitter 1:2
10
Splitter 1:64
120
Single splice
2
1 km of a 6-fiber cable
3000
Closure accommodating up to 12 splices
20
Cabinet serving up to 500 fibers
1500
Still, even with the proposed reduction of the problem but using the CPLEX solver’s default settings, the upper bound obtained using the heuristic solution was seldom upgraded. The issue was addressed using a special feature of the solver. Namely, fourth part of available time \(t_{MIP}\) was used by the ordinary CPLEX’s B&B, while the remaining time was given to the special CPLEX’s B&B that concentrates on polishing a solution. Changing those settings allowed the presented MIP model to generate significant savings, as shown in the following subsection.
6.3 Gain
Using the above methodology, the ability of the presented MIP approach to improve heuristic solutions was evaluated. The results are presented in Fig. 9, in which the gains are indicated for different values of time limits \(t_{heur}\) and \(t_{MIP}\). Consider \(c_{start}\) as a cost of a solution that uses engineering rules of [24] for the splitting pattern selection and \(c_{finish}\) as a cost of a solution that optimized those splitting patterns using the methodology of the previous section. Then the gain is understood as \(\frac{c_{start}-c_{finish}}{c_{start}}\). Notice that \(c_{finish}\) should be smaller than \(c_{start}\).
Fig. 9
Obtained gain
×
In the experiments, five different values of the total running time were used, namely: 10, 100, 300, 1000, and 10,000 s. The total time was divided between \(t_{heur}\) and \(t_{MIP}\) in five different ways, namely:
The obtained results are easily interpretable when the total running time was either small (10 and 100 s) or large (10,000 s). In the first case, the time limit was too small for the MIP approach that needs a significant amount of time for CPLEX’s pre-computations and cut generations; thus, prioritizing the approach, i.e., increasing fraction \(t_{MIP}/t_{total}\), only led to decreasing the time used for the actual optimization performed by the heuristic approach. On the other hand, when \(t_{total}\) is sufficiently large, the MIP approach can easily exhibit its superiority over the heuristic approach. It is perfectly indicated in Fig. 9 when \(t_{total}\) equals 10,000 s. If time limits are sufficiently large, the MIP approach outperforms the heuristic approach. In addition, it does not have to be guided, i.e., be provided with a high quality starting solution, but is equally efficient when solely a reasonable starting solution is provided (based on engineering rules, for instance). The situation becomes more complicated when average time limits are considered (300 or 1000 s in our case). The results indicate that for average time limits the MIP approach had to be appropriately guided to exhibit its capabilities to the full extent. When the whole time span of 300 or 1000 s is used solely by the MIP approach the results are not satisfactory. However, when the same MIP approach is used for 80% of the available time to upgrade a solution returned by the heuristic approach run for the first 20% of the available time, the results are much more promising. For 300 s time limit, still the best strategy is to use the heuristic approach for the whole available time. However, in the case when time limit is 1000 s, the mixture of the presented approaches results in the most efficient performance. Figure 9 indicates that for the 1000-second time limit the best strategy was to divide the available time approximately equally between the approaches. When the time given to the MIP approach is smaller than or equal to 20% of the total time, CPLEX cannot utilize to the full extent its computational capabilities. On the other hand, when this time is greater than or equal to 80% of the total time, the starting solution given to CPLEX is of poor quality and it cannot be immediately improved. Finally, the results indicate that for very large time limits, reaching few hours for each FTTH tree, the MIP approach significantly outperformed the heuristic approach providing the gain reaching almost 3%, while the heuristic approach after the initial gain generated during the first hundreds of seconds did not improve much, and finally provided gains lower than 1%.
Fig. 10
Impact of different parts of a solution on a total cost
×
Let us take a closer look at the structure of the gain. In Fig. 10, shares of different equipment types in the total gain are displayed. In the figure, 100% represents the total gain created by the optimization method. For example consider that the total cost of a network was 110 million EUR and was reduced to 100 million EUR after applying the method; thus, the gain was 10 million EUR. If Fig. 10 holds for this example, then during the optimization process the trunk cable cost decreased by approximately 4 million EUR, the distribution cable cost decreased by 2.5 million EUR, but the OLT card cost increased by 1 million EUR, etc.
The results are obtained for the 10000-second time limit test case with the whole available time used by the MIP approach. The results indicate that virtually the whole gain was generated by reducing the sizes of cables and limiting the amount of splicing. On the other hand, to use fibers more efficiently (reducing cable sizes), the number of OLT cards was slightly increased. To explain the phenomenon, let us present a simple example. Consider a small settlement of three buildings, 40 flats each. It can be served by three fibers connected to three OLT ports ending at a 64-output splitter in each building. On the other hand, five 8-output splitters can be located in each building resulting in a 15-fiber cable leaving the settlement. Those fifteen fibers can be connected to two 8-output splitters in the head-end node. The former solution needs a thin 3-fiber cable connecting the settlement and three OLT ports in the head-end node. The latter solution uses a thicker 15-fiber cable, but it needs only two OLT ports in the head-end node. In our test case, apparently the former-like solutions were more desirable. Still, it cannot be considered as a general result—the optimal solution structure depends on prices of various components and highly depends on a particular test case.
Another fact that can be observed in Fig. 10 are relatively small impacts of splitters and cabinets on the total gain. Although the total cost of splitters is stable, they definitely cannot be removed from the MIP model, because they are tightly related to OLT costs. Not taking splitters into account while designing a network would either result in unfeasible solutions (due to unsatisfied power budget constraints) or lead to extreme inefficiency in OLT port utilization resulting in a substantial increase of the total cost. On the other hand, the impact of cabinets seems to be not significant. Assuming a relatively small variety of available cabinets, the sizes of utilized cabinets are seldom modified; thus, they can be removed from the MIP model. Still, the complexity of the constraints related to cabinets is comparable to their impact on the results, i.e., removing those constraints does not visibly reduce the sizes of resulting MIP optimization problems.
Fig. 11
Relative cost changes of components
×
Finally, it is worth to analyze the importance of splicing in the MIP model. It seems that splicing can be removed from the model, as splicing costs are tightly connected to the cable costs, i.e., reducing the cable sizes decreases both cable and splicing costs. Our experiments show that it is only partially true. Obviously, reducing cable sizes also reduces the number of splices; thus, it reduces the splicing costs. Still, the obtained gain generated by optimized splicing cannot result solely from reducing cable sizes. In Fig. 11, relative changes of various cost components are displayed. In detail, the MIP optimization reduced the total cost of distribution cables by <1%. Simultaneously, the total cost of distribution splicing was reduced by almost 4%. For example, if head-end splitters cost 10 thousand EUR in the base design, and Fig. 11 holds, then head-end splitters will cost approximately 8.2 thousand EUR in the optimized design. The results clearly indicate that the splicing gain is not only generated by reducing the amount of splicing by reducing the cable sizes, but contrary, its major part results from optimized splicing, e.g., tapping a cable instead of splicing it into two separate cables.
6.4 Optimality gap
In Fig. 12, the optimality gap obtained by the MIP solver is presented. The methodology used to obtain the results is the same as in the previous case.
Fig. 12
Optimality gap
×
As indicated in Fig. 12, the optimality gap decreases together with the increase in the running time allocated to the MIP approach. For the longest time limits the optimality gap decreases to approximately 1.3%, allowing us to claim that the presented MIP approach usually returns solutions of high quality. Notice that for 100 and 300 s time limits the gap increases when the whole time is given to MIP approach. It means that during that time the utilized MIP solver was not able to increase the lower bound as efficiently as the heuristic method was able to decrease the upper bound, which is another strong argument for enhancing the MIP approach with heuristic approaches for test cases characterized by moderate time limits.
7 Conclusions
We have proposed a MIP formulation for a problem of optimal dimensioning of the FTTH tree equipment. The formulation and the underlying network model were explained in details. The model has been implemented and validated. General results based on selected real-world scale numerical experiments were presented in the paper.
The presented approach proved to be effective—it is capable of improving the solutions obtained by means of a benchmark heuristic approach. Our experiments showed that it is not as efficient as the benchmark approach in improving solutions when running times are seriously limited. However, when a time limit is not an issue, the presented approach is much more efficient than the benchmark approach, as long as it is provided with a decent starting solution (a decent starting solution can be obtained very easily using simple engineering rules).
Acknowledgements
This research was supported by National Science Centre, Poland, under grant 2014/15/ D/ST7/05320 “Open problems in large-scale optical access network design” and by the Ministry of Science and Higher Education, Poland, under grant IP2012 065372 “Distributed optical access network optimization”. The work of M. Mycek and M. Pióro was partially funded through an internal grant of the Institute of Telecommunications, Warsaw University of Technology.
Compliance with ethical standards
Conflict of interest
On behalf of all authors, the corresponding author states that there is no conflict of interest.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Still, our intention was that the reader could gain the general understanding of our work even if these sections (which are, by their nature, very detail and complex) were, for the very first time, omitted.
Introduction of this set is an outcome of discussions conducted with our industrial partners. They are in the position that it is a common trend to limit the number of patterns used in the network to preserve homogeneity and to reduce operational costs.
To protect interests of our industrial partners one constant that significantly influences the optimal number of FTTH OANs covering Warsaw was changed while generating the test cases. Therefore, the authors by no mean claim that 10 is the optimal number of FTTH OANs that should be used in Warsaw.
