  Software-defined satellite-terrestrial integrated networks (SDSTNs) are seen
as a promising paradigm for achieving high resource flexibility and global
communication coverage. However, low latency service provisioning is still
challenging due to the fast variation of network topology and limited onboard
resource at low earth orbit satellites. To address this issue, we study service
provisioning in SDSTNs via joint optimization of virtual network function (VNF)
placement and routing planning with network dynamics characterized by a
time-evolving graph. Aiming at minimizing average service latency, the
corresponding problem is formulated as an integer nonlinear programming under
resource, VNF deployment, and time-slotted flow constraints. Since exhaustive
search is intractable, we transform the primary problem into an integer linear
programming by involving auxiliary variables and then propose a Benders
decomposition based branch-and-cut (BDBC) algorithm. Towards practical use, a
time expansion-based decoupled greedy (TEDG) algorithm is further designed with
rigorous complexity analysis. Extensive experiments demonstrate the optimality
of BDBC algorithm and the low complexity of TEDG algorithm. Meanwhile, it is
indicated that they can improve the number of completed services within a
configuration period by up to 58% and reduce the average service latency by up
to 17% compared to baseline schemes.
