On building the minimum number of tunnels: an ordered-split approach to manage IPSec/VPN policies

Most of the current work in policy management for IPSec/VPN focuses on how to configure a single IPSec box or a pair of IPSec boxes. However, it has been shown (Fu et al. (2001)) that the local correctness of IPSec policies in every box individually does not necessarily guarantee global correctness. Therefore, it is critical to have a systematic way to analyze the security requirements globally and to generate, automatically and correctly, a set of IPSec policies to ensure the security for all the end-to-end connections. Previously (Fu et al. (2001)), two different algorithms (i.e. bundle and direct) were introduced to solve the policy generation problem in an "offline" fashion. While these two algorithms are efficient in producing globally correct policy rules, the number of output policy rules (i.e., the results themselves) is much greater than necessary. In other words, while the existing approaches can produce a solution quickly, the quality of the solution is far from optimal. In practice, this is undesirable for several reasons. For instance, "more IPSec policy rules" implies "more complicated virtual network topology". Therefore, in this paper, we focus on "how to produce a minimum set of IPSec/VPN tunnels". We formulate this problem as a special type of task-scheduling problem and develop a new method, the ordered-split approach, to produce a provably minimum set of globally correct policy rules. We have also compared the new approach with existing methods in simulation, and our results clearly demonstrate that the ordered-split approach performs significantly better.