Online Service Function Chain Planning for Satellite-Ground Integrated Networks to Minimize End-to-End (E2E) Delay

The combination of software-defined networking (SDN) and satellite-ground integrated networks (SGINs) is gaining attention as a key infrastructure for meeting the granular quality-of-service (QoS) demands of next-generation mobile communications. However, due to the unpredictable nature of end-user requests and the limited resource capacity of low Earth orbit (LEO) satellites, improper Virtual Network Function (VNF) deployment can lead to significant increases in end-to-end (E2E) delay. To address this challenge, we propose an online algorithm that jointly deploys VNFs and forms routing paths in an event-driven manner in response to end-user requests. The proposed algorithm selectively deploys only the essential VNFs required for each Service Function Chain (SFC), focusing on minimizing E2E delay-a critical QoS parameter. By defining a minimum-hop region (MHR) based on the geographic coordinates of the routing endpoints, we reduce the search space for candidate base stations, thereby designing paths that minimize propagation delays. VNFs are then deployed along these paths to further reduce E2E delay. Simulations demonstrate that the proposed algorithm closely approximates the global optimum, achieving up to 97% similarity in both E2E delay and CPU power consumption, with an average similarity of approximately 90%.