How Hexvarium solves fiber network design problems in minutes using Hexaly

Customer stories Telecom Network Design

Léa, Ph.D. Senior Optimization Scientist January 1, 2021

The American company Hexvarium, a next-generation developer, facilitator, and operator of broadband networks, chose Hexaly to solve city-wide optical fiber network design problems in minutes. Hexvarium is a broadband service provider using data-oriented methods to accurately identify, deliver, and connect profitable networks across the United States. Their innovative approach delivers sustainable networks, even in the most challenging circumstances. It enables investors, utilities, municipalities, and businesses to quickly determine how and where to build fiber networks for the best possible impact and return to investors.

Hexvarium’s fiber network design problem

Hexvarium has been tasked with designing the optical fiber network of several cities across the United States. Building such a network requires connecting every client address to the city’s central office while routing the optical fiber cables in the best possible way.

The route connecting a given client to the central office is split into several sections, separated by splitter nodes of different sizes. Along this route, the cables have a higher fiber count when coming out of the central office and a lower fiber count as they get more specific and closer to the client’s address. The hierarchy followed by the different route sections is as follows. The city’s main central office is first connected to several secondary central offices across the city, using thick cables with a high fiber count. The cables from these secondary central offices still have a high fiber count. They must be split several times before connecting to the clients’ addresses, using primary and secondary splitter nodes. The cables from the secondary splitter nodes are individual fibers and can be connected to separate client addresses.

The splitter nodes have very constrained fiber counts. For example, about eight fibers generally come out of each secondary splitter node. To avoid wasting resources, most of those fibers have to be connected to a client address. However, a few fibers should remain unused to make the network more sustainable. Indeed, these unused fibers could be connected to new client addresses.

Mathematical model

Input data

The input data is a graph representing the city’s streets and roads. The city has up to 500,000 road segments for a cumulated length of 13,000 kilometers, corresponding to the graph’s edges. The nodes of the graph are the intersection points between those road segments. Up to 130,000 of these nodes are client addresses. Another node corresponds to the location of the main central office.

Decisions

The fiber network design consists of deciding which road segments should be used to run the cables, and where to place the primary and secondary splitter nodes.

Constraints

There are three types of constraints in the model. The splitter nodes’ hierarchy constraints must be respected. Each cable coming out of the main central office has to go through a secondary central office, at least one primary splitter node, and a secondary splitter node before reaching a client address. There are also degree constraints on the splitter nodes, ensuring that the number of output cables is neither too high nor too low. Finally, the total length of the fiber connecting any client address to a secondary central office should not exceed a certain limit.

Objectives

The objective is to minimize the total deployment cost, which depends on the number of splitter nodes and the total length of fiber in the network.

Why Hexaly?

Hexvarium had already benefited from Hexaly’s expertise on scheduling problems for deployment operations and was very satisfied with the results. Besides, Hexaly already has expertise in telecommunication deployment topics, including network design for Bouygues Telecom. This motivated Hexvarium to choose Hexaly to help them with their fiber network design problem.

Hexvarium’s team is delighted with Hexaly’s ability to provide good solutions quickly. For example, the largest instance with 500,000 road segments and 130,000 client addresses was solved in only 10 minutes. They also greatly appreciate Hexaly’s agile methodology. They appreciate how Hexaly’s experts manage to iterate quickly on the design of the solution based on their operational feedback.

We’ve been working with Hexaly for several years, and their unmatched speed and scalability, combined with the expertise of their exceptional team, have been pivotal in advancing our fiber network design project. Hexaly’s agile methodology has truly been a game-changer, allowing us to swiftly iterate and refine solutions based on real-world operational feedback. Their unwavering support has been instrumental in helping us achieve our objectives with efficiency and precision.

Fabion Kauker Chief Information Officer, Hexvarium