Research On K-shortest Paths With Reliability And Its Optimization Problem

k-shortest paths have the advantages of low latency and high bandwidth in the application of large data centers and high-performance computing cluster networks,and have attracted widespread attention from researchers.In order to achieve the reliable transmission of information among network nodes in the k-shortest paths scheme,this paper studies the reliability and expected k-shortest paths length under the link failure model.The main conclusions are as follows:1.In the reliability model where nodes are reliable and links may fail,this paper considers the equal length path selection problem of k-shortest paths,and converts the selection problem into a reliability optimization problem.Then we propose an accurate algorithm and an approximate algorithm based on Monte Carlo simulation.Examples show the effectiveness of the approximate algorithm in the end.2.This paper establishs a parameter of expected k-shortest paths length to measure network performance,and prove that the expected k-shortest paths length of Generalized De Bruin Graph has near-optimal performance.The simulation results effectively validate the theoretical analysis.