In this paper we investigate the request routing problem in the onboard Video-on-Demand (VoD) service which is a key to provide good user experience. We model the system as a controlled queuing system including a dispatcher and several VoD servers. The system is formulated by Markov Decision Process (MDP). Since the MDP formulation suffers from the so-called “the curse of dimensionality” problem we then develop a greedy heuristic approximate algorithm which is simple and can be implemented online.The effectiveness of the approximation algorithm is evaluated through extensive simulations.