Hybrid communication systems: forming a multilevel mathematical concept of routing

Full Text

Introduction

The transition from predominantly terrestrial communication networks to hybrid architectures that integrate terrestrial, stratospheric, and space segments makes routing a central challenge in modern telecommunications engineering. While in traditional IP backbone networks, a significant portion of the infrastructure relies on a relatively stable topology and long-term wired or fixed radio relay connections, in hybrid systems the network itself is heterogeneous, self-organizing, and significantly more volatile over time [1].

This problem is particularly acute in architectures where space and stratospheric segments must be connected to each other and to ground infrastructure via wireless communication channels. In such a network, the route ceases to be a virtually immutable path through a stable framework and becomes subject to regular recalculation: the mutual visibility of nodes, available channels, throughput, latency, interference levels, and even the set of permissible connections themselves change. For networks with aerial and unmanned platforms, this is compounded by the need for continuous topological restructuring and adaptation of routes to node movements [2; 3].

An additional challenge is created by the rapidly growing mobility of subscribers and intermediate access nodes. While in the classic Internet a significant portion of traffic is generated by stationary or semi-mobile end systems, in advanced hybrid networks, unmanned vehicles, mobile relays, and distributed aerial platforms are playing an increasingly prominent role. In this case, not only the channel state changes, but also the requirements matrix itself: traffic sources and receivers are actively moving, and valid routes and relay points must be reconfigured more quickly than required in traditional network operation scenarios [2; 3].

Therefore, routing tools suitable for comparatively more stable public networks cannot be considered sufficient for a hybrid wireless architecture without significant modification. Even such practically important mechanisms as Equal-Cost Multi-Path (ECMP) and segment routing are oriented toward a limited set of paths and a comparatively more stable control plane, whereas in a hybrid network, the topology itself, propagation conditions, and the composition of available intersegment channels change [4–6].

These conditions require a mathematical framework that allows for the simultaneous evaluation of the achievable share of served demand, the total volume of traffic handled, the impact of priorities, delays, and time dynamics, as well as the limited number of feasible routes. This is precisely why the multicommodity flow (MCF) problem is particularly relevant here: it defines a natural, high-level model for distributing multiple demands across a resource-constrained network, and its further extensions allow for the transition to models that minimize traffic delays, settings with a limited number of paths and flows over time [7–26].

Routing in a hybrid network should not be viewed as an isolated path selection problem, but rather as the basis for a broader class of related network management problems. Routing decisions directly influence frequency and channel planning algorithms [27], the synthesis and restructuring of the network structure itself, including the selection and placement of repeaters [3], and the methods for distributing routing information [28]. In other words, it is not enough to simply find the optimal set of routes; it is also necessary to ensure consistent distribution of radio resources, maintenance of a functional topology, and timely delivery of routing information to all nodes involved in traffic forwarding.

The purpose of this paper is not a simple review of existing results, but rather to formulate a multi-level mathematical routing concept for hybrid communication systems. Following this logic, we construct a hierarchy combining three levels: fractional traffic distribution, discrete route constraints, and nonlinear delay minimization. This unification yields a problem combining properties of linear, combinatorial, and convex optimization. Unlike existing works, which analyze these approaches separately, this paper integrates them into a single hierarchical framework adapted to hybrid networks with variable topologies, limited radio resources, and strict delay requirements. Existing results in each of these areas serve as the mathematical foundation for the corresponding levels. Their unification into a coherent system constitutes the main conceptual result of the paper.

1. General fractional formulation of the MCF problem

We consider a directed graph

$G=\left(V,E\right),$

where $V$ is a set of vertices; $E$ is a set of arcs. Let $\left|V\right|=n$ and $\left|E\right|= m$. For each arc $e\in E$ a bandwidth is specified $c_e>0$. There are many requirements $K=\mathrm{1,}\dots ,k$. For each requirementa $i\in K$ stock source $s_i$ and demand $d_i>0$ are specified.

In the arc form, the flow is defined by variables $x_e^i$ denoting the volume of demand flow $i$ passing along the arc $e$ Let

$y_e=\sum _{i\in K}{x}_e^i$

is a total arc load e. Then the capacity constraints are

$y_e\le c_e,$ где $e\in E.$

The constraints on maintaining the flow with the total share of demand satisfaction $\mathrm{\lambda }$ are written as follows:

$\sum _{e\in {\delta }^{+}\left(v\right)}{x}_e^i-\sum _{e\in {\delta }^{-}\left(v\right)}{x}_e^i=b_v^i,$

where

$b_v^i=\left\{\begin{array}{ll}\lambda d_i,& v=s_i,\\ -\lambda d_i,& v=t_i,\\ \mathrm{0,}& \text{иначе.}\end{array}\right.$

Then the competitive MCF problem takes the form

$\text{max\hspace{0.33em}}\mathrm{\lambda }$

when flow and capacity constraints are satisfied. In routing notation, the equivalent model is written as

$\text{max\hspace{0.33em}}\mathrm{\lambda },$

$\sum _{p\in P_i}{f}_p^i=\lambda d_i,\text{ где }i\in K,$

$\sum _{i\in K}\sum _{p\in P_i:e\in p}{f}_p^i\le c_e,\text{ где }e\in E,$

$f_p^i\ge 0.$

This notation is convenient when discussing a routing form with a limited number of paths. From a theoretical perspective, this problem belongs to the class of linear programming (LP) problems. In practice, however, the decisive factors are the network scale, the number of requirements, the need for multiple optimizations for various criteria, and the requirement for the solution to be interpretable. Therefore, since the 1990s, the primary focus has gradually shifted from direct LP solutions to fast approximate solutions [7–13].

2. Three canonical formulations of the general fractional MCF

The formulation of the competitive flow problem was given above, but it is not the only one. Three canonical problems of the general fractional MCF are presented in [13]. All three settings use the same variables $x_e^i$ and $y_e$ as above, and the same flow conservation and arc capacity constraints. The difference lies in how the service volume of each requirement is defined and what form the objective function takes.

1. Competitive MCF. In this problem (discussed previously), the same coefficient $\mathrm{\lambda }$ is introduced for all demands, defining the overall share of demand satisfaction. This means that in the flow conservation equations, for each demand $i$, a volume is introduced into the network at the source $s_i$, the same volume $\lambda d_i$ is removed from the network at the sink $t_i$, and the flow balance is maintained at intermediate nodes. The objective function has the form

$\text{max\hspace{0.33em}}\mathrm{\lambda }.$

Thus, the problem is aimed at the most uniform possible servicing of all requirements and is naturally interpreted as setting up a fair distribution of network resources.

2. Maximum MCF . Here, for each requirement $i$, its own coefficient ${\mathrm{\beta }}_i$ is introduced, which determines the volume ${\mathrm{\beta }}_i{d}_i$ served, as well as the following objective function:

$\text{max\hspace{0.33em}}\sum _{i\in K}{\beta }_i.$

In flow conservation equations, an individual coefficient ${\mathrm{\beta }}_i$ is used for demand $i$ instead of the overall value $\mathrm{\lambda }$. Thus, the problem is no longer focused on uniformity, but on maximizing the total volume of traffic handled. If $d_i$ is treated as an upper bound on demand, then applied models often additionally introduce a constraint ${\mathrm{\beta }}_i\le 1$.

3. Maximum weighted MCF . This formulation preserves the individual coefficients ${\mathrm{\beta }}_i$ but supplements them with positive weights $w_i>\mathrm{0,}$ reflecting the priority of requirements. The objective function has the form

$\text{max\hspace{0.33em}}\sum _{i\in K}{w}_i{\beta }_i.$

As a result, requirements with higher weights receive a greater contribution to the objective function. This model is particularly useful for traffic engineering, where it is necessary to distinguish between service classes, critical and background traffic, and requirements with different operational importance.

The remainder of the article focuses on the formulation of the competitive flow problem (it has already been explicitly formulated). This problem is particularly suitable for discussing the fairness of network resource allocation. However, when interpreting the results of applied routing problems, the entire family of three basic objective functions should be kept in mind.

3. Evolution of approximate MCF algorithms on directed graphs

Early combinatorial approximations

A significant step forward was made in [7], where it was shown that multi-commodity flows can be approximately solved significantly faster than expected using large LP models directly. Further developments were related to the ideas of Lagrangian relaxation and fractional packing. Garg and Köhnemann [8] proposed one of the most influential algorithmic frameworks: the flow is constructed iteratively, and the arc lengths in the dual problem are updated depending on their load. Then, Fleischer [9] succeeded in significantly weakening the dependence of the running time on the number of customers, which became an important milestone for sparse graphs and problems with a large number of source-sink pairs.

Karakostas' results and development of methods in 2000–2010

Significant progress for the competitive flow problem was made by Karakostas. His scheme reduces the dependence on the number of requirements and distinguishes between implicit and explicit representations of the solution. For the competitive flow problem, he obtained a time of about

$\tilde{O}\left({\epsilon }^{-2}{m}^2\right)$

for the implicit representation of the flows in the solution and

$\tilde{O}\left({\epsilon }^{-2}\left(m^2+kn\right)\right)$

and for the explicit representation. [10]. Another significant speedup is associated with the use of dynamic graph data structures. In particular, Madry's work shows that many fractional MCF formulations can be solved faster by integrating such structures with approximate optimization schemes[11].

State of the Art: Almost-Linear Algorithms for Directed Graphs

In 2024, Chen and Ye proposed an iterative scheme for high-precision solution of a wide family of multicommodity flow problems on undirected graphs [12]. In the context of this work, the directed case is of key importance. As of 2025, the strongest known result specifically for the general fractional approximate MCF on directed graphs is due to Chen, Graur, and Sidford [13], who obtained algorithms with running time

$m^{1+o\left(1\right)}k{\epsilon }^{-1}$

for finding $\left(1-\mathrm{\epsilon }\right)$ approximate solutions to three basic MCF problems on directed graphs. This asymptotic result significantly outperforms classical approximation schemes of previous generations. This leads to an important methodological conclusion. If we consider only the general approximate MCF on directed graphs, then the classical Garg-Köhnemann approach (route packing) is no longer the best in terms of asymptotics. Nevertheless, it remains valuable for two reasons. First, such schemes are easier to implement in practice and explain the results. Second, they naturally align with the route-based notation of the solution, meaning they are more easily transferred to problem formulations with a limited number of paths, as well as to nonlinear problems aimed at minimizing traffic delay. Although the 2024–2025 results improve the asymptotic bounds, their algorithmic design is based on a significantly more complex chain of reductions and high-precision auxiliary subproblems. Therefore, for engineering problems and practical software implementation, simpler algorithms from the Garg-Koenemann, Fleischer and Karakostas families in many cases remain a more practical tool [8–10; 13].

4. Kleinrock's classical delay model

For telecommunications networks, simply maximizing flow is insufficient. Even if the constraint $y_e\le c_e$ is not violated, network performance can degrade sharply when operating near saturation. This is why latency has become a natural second criterion in hybrid network design.

In Kleinrock's classic work, the network is considered as a collection of links and service nodes, and the main quality metric is given by the average message delay [14]. In particular, in the 1973 paper by Fratta, Gerla, and Kleinrock, the MCF problem is formulated in a nonlinear form and a flow rejection method similar to gradient descent is introduced to solve it, where the "shortest route" in a pre-specified metric plays the role of the improvement direction [15]. A 2014 review emphasizes that this method has been used from the ARPANET to more recent transport and SDN applications [16]. However, Kleinrock's model relies on stationary Poisson flows and exponential service; for hybrid wireless networks with variable throughput, this is an approximation, but it still provides a useful estimate of the average delay and is widely used in network synthesis.

 If we take the traffic arrival rate $y_e$ for the arc $e$ to be equal to, and the service rate to be $c_e$, then for the M/M/1 model the average time a packet spends in the system is written as

$W_e\left(y_e\right)=\frac{1}{c_e-y_e},\text{ где }0\le y_e<c_e.$

Multiplying this time by the flow intensity, we obtain the arc's contribution to the total network delay:

$y_e{W}_e\left(y_e\right)=\frac{y_e}{c_e-y_e}.$

Summation over all arcs yields the classical functional

$J\left(x\right)=\sum _{e\in E}\frac{y_e}{c_e-y_e}.$

From a mathematical point of view

${\varphi }_e\left(y_e\right)=\frac{y_e}{c_e-y_e}$

the function is convex on the interval $\left[\mathrm{0,}{c}_e\right)$. Therefore, minimizing the total delay naturally leads to a convex optimization problem, and the ability to fragment the flow is an important condition: it allows traffic to be distributed among alternative routes and thus avoid a sharp increase in delay on narrow arcs. Convexity ${\varphi }_e\left(y_e\right)$ ensures that the delay minimization problem can be solved by convex optimization methods, such as gradient descent or flow diversion [15; 16].

In later studies, a latency function ${\tau }_e\left(y_e\right)$ is introduced for each arc, which describes the dependence of the arc's transit time on its load. Then, the optimal routing under standard multi-commodity flow constraints is formulated as follows:

$\underset{x}{\text{min}}\Phi \left(x\right)=\sum _{e\in E}{y}_e{\tau }_e\left(y_e\right)$.

When choosing

${\tau }_e\left(y_e\right)=\frac{1}{c_e-y_e}$

we obtain the Kleinrock model as a special case.

A more realistic formulation of the problem includes a fixed delay component $a_e$:

${\tau }_e\left(y_e\right)=a_e+\frac{1}{c_e-y_e},\text{ где }{a}_e\ge \mathrm{0,}$

which yields the objective function

$\Phi \left(x\right)=\sum _{e\in E}{y}_e\left(a_e+\frac{1}{c_e-y_e}\right).$

The review [25] shows that such convex formulations of multi-commodity flows have long been an independent area of research. Temporal dynamics, in turn, leads to time-flow problems, where arcs have travel times, and the flow itself depends on discrete or continuous time [26].

If is ${\tau }_e$ the time of passage of the arc $e$, and $x_{e,\tau }^i$ is the volume of the demand flow $i$ launched along the arc at the time , then the dynamic conservation law can be written as

$\sum _{e\in {\delta }^{+}\left(v\right)}{x}_{e,\tau }^i-\sum _{e=\left(u,v\right)\in E}{x}_{e,\tau -{\tau }_e}^i=b_{v,\tau }^i.$

For requirements with deadlines, the natural constraint takes the form

$\sum _{\tau \le T_i}\sum _{e\in {\delta }^{-}\left(t_i\right)}{x}_{e,\tau }^i\ge d_i,$

Where $T_i$ is an acceptable time limit for delivery of the claim $i$. This is how problems are formulated in modern works on MCF with delivery time constraints, especially for satellite and hybrid networks, where the propagation delay can no longer be neglected [24].

Therefore, modern productions aimed at minimizing delays can be divided into three levels:

1. Static convex MCF, where the delay is given by a convex arc loading function.
2. A quasi-static level where the traffic delay consists of two components: a constant component and a variable component depending on the arc load.
3. A dynamic level where travel times, time-deployed networks, and joint route-calendar optimization appear.

5. Routing with a limited number of paths (κ-separable routing)

In the general fractional MCF, a demand flow can be decomposed over an arbitrary number of routes. This is often inconvenient for real-world networks: a large number of routes increases the complexity of configuration, monitoring, and quality of service control. Therefore, in the literature, a limitation on the flow carrier capacity is introduced: each demand can use no more than routes [17].

If $P_i$ is the set of paths for requirement $i$ and $f_p^i$ is the flow along path $p$, then the κ-splittable formulation of the competitive flow (κ-splittable problem) takes the form

$\text{max\hspace{0.33em}}\mathrm{\lambda },$

$\sum _{p\in P_i}{f}_p^i=\lambda d_i,\text{ где }i\in K,$

$\sum _{i\in K}\sum _{p\in P_i:e\in p}{f}_p^i\le c_e,\text{ где }e\in E,$

$\left|p\in P_i:f_p^i>0\right|\le \kappa ,$

$f_p^i\ge 0.$

This limitation seems "small" compared to the general fractional model, but it is precisely this that moves the problem from the world of pure convex relaxations into a significantly more difficult class of combinatorial optimization problems.

As shown by Bayer, Koehler, and Scutella [17], various formulations of κ-separable flow problems are NP-hard; branch-and-cost methods [18; 19], heuristics [20; 22], and randomized rounding algorithms [21] are used to solve them.

From a practical perspective, the path limitation is well-suited for MPLS, SDN, radio networks, and hybrid telecommunications architectures, simplifying monitoring, diagnostics, and fault-tolerance policies, and helping to avoid excessive fragmentation of traffic into multiple small subflows. In practice, the parameter is typically chosen as a small constant (typically 2–4), due to limitations on the size of forwarding tables, the complexity of load balancing, and the risk of packet reordering [4–6; 29–31].

This is why the limited-path configuration is not a "special technical case" of the general MCF. On the contrary, it is one of the most realistic models for network engineering.

6. Modern representation of the problem: from general MCF to hybrid architecture

The results discussed above allow us to distinguish three different levels of algorithmic architecture.

Level 1: Fast approximation of the general fractional MCF

If the problem is to estimate the achievable share of demand, the total volume of traffic handled, or priority-weighted servicing on very large directed graphs, then the most natural choice is the general approximate MCF. Asymptotically efficient approximation algorithms play a key role here, since they provide an initial answer to the questions "what share of demands can the network handle?", "what total traffic volume can be handled?", and "how to take into account priorities between demands?" [7–13].

Level 2: Limiting the number of routes

If a technically feasible solution is required, it is necessary to move from a general fractional flow to a limited-path or κ-separable model. At this step, a discrete structural choice arises: which routes to leave for each requirement and which flows to route along them [17–23].

Level 3: Re-optimization for latency and timing

Once a limited set of routes has been selected, the problem naturally turns into either a convex optimization with latency functions or a time flow and scheduling problem with delivery time constraints if the time structure is important [14–16; 24–26].

This architecture appears to be the most appropriate for solving routing problems in hybrid communication systems. It doesn't attempt to solve the entire problem in one fell swoop, but leverages the strengths of different classes of methods at different stages.

For a clear comparison of the levels of the proposed concept, the table summarizes their mathematical content and engineering meaning.

 

Three-level mathematical concept of routing in hybrid communication systems

Level	Mathematical model	Optimization criterion	Result	Engineering meaning
1	General fractional MCF	Share of demand, total or weighted traffic	Fractional flow distribution	Upper bound for throughput
2	k-separable routing	Number of routes per request	A small set of feasible routes	Formation of the established route policy
3	Convex MCF	Average delay, deadlines, transfer completion time	Refined distribution of traffic over time and routes	Учёт качества обслуживания и временной динамики сети

 

The fundamental necessity of such a decomposition stems from the fact that combining fractional traffic distribution, discrete route constraints, and nonlinear delay minimization in a single formulation leads to a significantly more complex problem, combining the properties of linear, combinatorial, and convex optimization. Therefore, the transition from a theoretical upper bound to an engineering-implementable routing policy naturally requires a sequential decomposition of the problem into levels.

7. Relationship between theoretical models and real routing in telecommunications

The models discussed above show that the general fractional MCF, finite-path formulations, and delay-minimizing models can conveniently be viewed as successive complication of the basic theory. However, for telecommunications practice, one further clarification is necessary. Even if a mathematical model allows for the partitioning of a single request into an arbitrary number of routes, a real router or switch typically does not implement such partitioning at the data link level. Limitations on the state of the forwarding and label tables, requirements for the stability of the next-hop set, the risk of packet reordering, and operational considerations dictate the use of either a single path or a small number of paths with an explicitly specified allocation policy [4–6; 29; 30].

For packet forwarding and traffic engineering, the reality is usually different. In ECMP mechanisms, a router selects the next hop from a finite set of equal-cost alternatives, typically based on flow field hashing; thus, a single microflow is assigned to a single path from a small set, rather than being arbitrarily spread across all valid routes [4; 30; 31]. BGP multipath and vendor multipath implementations also involve load balancing between multiple paths, but within a limited set of candidates selected according to specified rules [29].

A similar idea is evident in Segment Routing (SR). The SR architecture allows flow to be directed along a specified topological route at the ingress node, while maintaining flow state only at the edge node [5]. In the segment routing policy model, a policy is associated with one or more candidate paths; the concepts of active candidate path, priority, and segment list are essential for operation, meaning the implemented routing again operates on a limited set of paths [6].

This leads to an important methodological conclusion. The general fractional MCF in telecommunications should be interpreted not as a precise model of how a router routes each packet, but as a high-level model for off-the-shelf optimization, capacity planning, and estimating the achievable share of demand. Its solution can then be used to build an engineering routing policy, for example, by limiting the number of paths, approximating with ECMP weights, selecting BGP/SR candidates, or designing backup scenarios.

Conclusion

This paper proposes a three-level mathematical routing concept for hybrid communication systems, combining general fractional multicommodity flow (MCF), route limitation, and delay minimization. The analysis demonstrates that current multicommodity routing research cannot be adequately described by a single model. The proposed framework includes at least three canonical target problems-competitive flow, maximum multicommodity flow, and maximum weighted multicommodity flow-each of which addresses its own engineering objective.

Kleinrock's classical approach and the flow diversion method remain methodologically relevant, as they demonstrate how multi-commodity flows naturally transition into nonlinear traffic delay minimization problems [14–16]. At the same time, limited-path formulations demonstrate that such a structural connection is not merely decorative: it significantly alters the computational nature of the problem and requires the use of branch-and-cost methods, as well as heuristic approaches.

For practical telecommunications applications, the most promising approach is not a single "universal" model, but a sequential three-step architecture: rapid approximation of the general fractional MCF (using simple, feasible algorithms), subsequent route reduction in the finite-path setting, and a final model focused on latency minimization or deadline-constrained optimization. At the highest level, it is useful to distinguish between the goals of fair service, maximization of total traffic, and priority support for critical requirements. This design allows us to combine modern approximate MCF theory with the engineering requirements of routing in real networks.

The most practical interpretation of multi-commodity routing for telecommunications is that the general fractional MCF provides a theoretical limit and a baseline solution for several optimization objectives, and the implementation level should be built on a limited set of paths and models that take into account transmission stability, traffic priorities, and operational constraints.

The proposed concept naturally extends to lossy networks (with arc gains or losses and generalized flow models), as well as dynamic networks and flows over time. Ultimately, the work defines not a specific routing algorithm, but a general mathematical framework in which the problems of throughput, route limitation, delay, loss, and time dynamics are considered as consistent layers of a unified routing concept in hybrid communication systems.

Благодарности

Работа выполнена при финансовой поддержке Фонда НТИ в рамках Договора №70-2025-000804 от 26.05.2025.

Авторы благодарят ректора Университета Решетнева Э. Ш. Акбулатова за помощь в организации исследования и всестороннюю поддержку работы.

Acknowledgements

The study was carried out with the financial support of the NTI Foundation under Agreement No.70-2025-000804 dated May 26, 2025.

The authors thank the Rector of Reshetnev University, E. Sh. Akbulatov, for his assistance in organizing the research and his comprehensive support of the work.

About the authors

Aleksandr A. Kuznetsov

Reshetnev Siberian State University of Science and Technology

Author for correspondence.
Email: alex_kuznetsov80@mail.ru
ORCID iD: 0000-0003-0944-1817

Dr. Sc. (Physics and Mathematics), Professor, Director of the Research and Education Center “Institute of Space Research and High Technologies”

Russian Federation, 31, Krasnoyarskii Rabochii Prospekt, Krasnoyarsk, 660037

Anton Yu. Vlasov

Reshetnev Siberian State University of Science and Technology

Email: vlasov@sibsau.ru
ORCID iD: 0000-0002-6360-7382

Cand. Sc. (Physics and Mathematics), Leading Researcher at the Scientific Laboratory “Satellite Telecommunication Systems”

Russian Federation, 31, Krasnoyarskii Rabochii Prospekt, Krasnoyarsk, 660037

Konstantin E. Gaipov

Reshetnev Siberian State University of Science and Technology

Email: gaipovke@yandex.ru
ORCID iD: 0000-0003-4146-5763

Cand. Sc. (Engineering), Associate Professor of the Department of Electronic Engineering and Telecommunications

Russian Federation, 31, Krasnoyarskii Rabochii Prospekt, Krasnoyarsk, 660037

Konstantin V. Safonov

Reshetnev Siberian State University of Science and Technology

Email: safonovkv@rambler.ru
ORCID iD: 0000-0003-0405-3065

Dr. Sc. (Physics and Mathematics), Professor, Director of Institute of Informatics and Telecommunications

Russian Federation, 31, Krasnoyarskii Rabochii Prospekt, Krasnoyarsk, 660037

References

Supplementary files