Small satellites networks are characterized by intermittent connectivity and rare communication opportunities between satellites and ground stations. To overcome this problem, inter-satellite links can be used and predictability of satellite movements can be exploited to plan the communication in advance. Mathematical optimization techniques are typically applied to create such communication plans. However, the resulting optimization problems are often large and therefore problematic to solve. To handle them more efficiently, we propose a novel decomposition approach based on Benders decomposition. To the best of our knowledge, we are the first to apply Benders decomposition in the context of satellite networks. Our evaluation results show that our approach considerably outperforms the state-of-the-art solution.