RR-MPF: A Reliable Routing Algorithm Based on Markov Parallel Forecasting for STINs

Satellite–Terrestrial Integrated Networks (STINs) undergo frequent topology reconfiguration due to the high mobility of satellite nodes, which can disrupt active routing paths across time slot boundaries, increase packet drop, and degrade end-to-end reliability. This paper proposes RR-MPF (Reliable Routing with Markov Parallel Forecasting), a routing algorithm that selects paths sustaining high reliability across successive time slots. RR-MPF quantifies time-varying link reliability through toughness, delay, jitter, and packet loss metrics. A Markov chain model, executed in a parallel background thread, estimates the probability that each link remains viable in the next time slot, providing future-state awareness without adding online latency. An enhanced Ant Colony Optimization (ACO) then solves a cross-slot weighted optimization that jointly maximizes current and predicted path reliability, yielding path selections that are robust to imminent topology changes. Numerical results show that RR-MPF reduces the average end-to-end delay by up to 23.9%, the delay jitter by 6.4–21.3%, and the packet drop rate by 6.8–34.4%, while improving the overall path reliability by up to 14.0% compared with three benchmark algorithms (iVACO, DPSO-TA, and GA-CG).