In this chapter, we apply the Big Data analytics from graph computing perspective to help traffic engineering in SDN networks. Specifically, we propose a high-speed top K shortest paths (KSP) algorithm to calculate routes, develop several efficient schemes for routing errors detection, and present a novel edge-set-based graph processing engine to deal with large-scale graph data from SDN. Compared to existing solutions, the experiments show that our proposed KSP algorithm brings 3-6× speedup, and our graph processing engine achieves 3-16× speedup.

Chapter Contents:

• 20.1 Introduction
• 20.2 Related work
• 20.3 Finding top-K shortest simple paths
• 20.3.1 MPS algorithm for top K shortest simple paths
• 20.3.2 Improved MPS algorithm with efficient implementation
• 20.3.2.1 Pseudotree with pruning
• 20.3.2.2 Pseudotree with internal ID and reversed order
• 20.4 Routing check and detection
• 20.4.1 Subnet partition
• 20.4.2 Loop detection
• 20.4.3 Black hole detection
• 20.4.4 Reachability detection
• 20.5 Efficient graph engine
• 20.5.1 Edge-set representation
• 20.5.2 Consolidation
• 20.5.3 Multimodal organization
• 20.5.4 Scheduling and prefetching
• 20.6 Experiments
• 20.6.1 Performance evaluation of finding top-K shortest simple paths
• 20.6.2 Performance evaluation of the efficient graph engines
• 20.7 Open issues and challenges
• 20.8 Conclusions
• References

Inspec keywords: error detection; software defined networking; telecommunication network routing; Big Data; graph theory; telecommunication traffic; data analysis; set theory

Other keywords: routing errors detection; graph computing perspective; control planes; high-speed top K shortest paths algorithm; large-scale graph data; traffic engineering; KSP algorithm; Big Data analytics; SDN networks; edge-set-based graph processing engine; data planes

Subjects: Combinatorial mathematics; Communication network design, planning and routing; Data handling techniques; Computer communications; Computer networks and techniques; Combinatorial mathematics