  Network Functions Virtualization (NFV) aims to support service providers to
deploy various services in a more agile and cost-effective way. However, the
softwarization and cloudification of network functions can result in severe
congestion and low network performance. In this paper, we propose a solution to
address this issue. We analyze and solve the online load balancing problem
using multipath routing in NFV to optimize network performance in response to
the dynamic changes of user demands. In particular, we first formulate the
optimization problem of load balancing as a mixed integer linear program for
achieving the optimal solution. We then develop the ORBIT algorithm that solves
the online load balancing problem. The performance guarantee of ORBIT is
analytically proved in comparison with the optimal offline solution. The
experiment results on real-world datasets show that ORBIT performs very well
for distributing traffic of each service demand across multipaths without
knowledge of future demands, especially under high-load conditions.
