Computer science and information processes
Optimization of data transfer in urban information systems based on graph theory methods
D. A. Rybakovab a Plekhanov Russian University of Economics,
36 Stremyannyy lane, Moscow, 115054, Russia
b Department of Information Technology, City of Moscow,
12ñ1, Yakovoapostolsky lane, Moscow, 107078, Russia
Abstract:
The Moscow Urban Information Systems managed by the DIT represent a complex distributed
ecosystem generating and processing huge volumes of heterogeneous data. Efficient transmission of this
data, especially for critical services with strict requirements for latency and reliability, is a key factor in
the functioning of the "smart city" and the quality of public services. Optimization of data transmission in
the Moscow GIS based on graph theory is critical to improve QoS, reliability and efficiency.
Methods. The study was based on detailed modeling of the Moscow DIT infrastructure as a weighted
graph, where vertices represent data processing/storage nodes, and edges represent communication
channels with attributes of throughput, latency and reliability. Data flows for key services were specified
with QoS requirements.
Aim. The research objective is to develop and verify methods for optimizing data transmission in urban
information systems based on graph theory. The objectives include reducing delays, improving reliability,
and enhancing the efficiency of network resources for critical services.
Results. For optimization, specialized graph algorithms are used: modified A* with geographic
heuristics for QoS routing, load balancing algorithms based on searching for the maximum flow/minimum
cost, and methods for ensuring fault tolerance through searching for k-disjoint paths (k = 2). Using the A*
algorithm allow us to reduce the average delay in video stream transmission for the Safe City system by
22–35 % compared to the basic approaches, while guaranteeing SLA compliance (<150 ms). The load
balancing algorithms reduce the 95th percentile of transaction delays for making an appointment with a
doctor from 65 ms to 42 ms by preventing overloads of key nodes. Using two disjoint backup paths reduce
the recovery time for critical services after a channel failure from 500 ms to 50 ms.
Conclusions. The obtained results convincingly prove the high practical value of applying graph theory
to optimizing data transmission in large-scale urban systems. Taking into account the geographical
specificity and hierarchical structure of the Moscow network proved to be a critical factor in success.
Keywords:
graph theory, urban information systems, data transmission optimization, QoS
UDC:
004.733
MSC: 90C26 Received: 10.06.2025
Revised: 11.08.2025
Accepted: 25.09.2025
DOI:
10.35330/1991-6639-2025-27-5-168-179
Fulltext:
PDF file (574 kB)