Optimization of data transfer in urban information systems based on graph theory methods

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.

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.

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.

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.