Veriflow system analysis and optimization

Veriflow;Network;Data Strucutre

Chen, Zhongbo ; Caesar ; Matthew C.

关键词: Veriflow;    Network;    Data Strucutre;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/50668/Zhongbo_Chen.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Computer Networks are complex and prone to bugs. Most existing tools designed to fix these problems run offline and can only fix the problems after they occur. Those tools often run at the timescale of seconds to hours. With the advent of Veriflow [7], network administrators are able to do real-time checking of network-wide invariants.VeriFlow is an efficient tool designated to detect SDN network invariants at run time. It serves as an intermediate layer between software defined networking controller and the actual network devices. When each forwarding rule is to be inserted, modified or deleted into the network, the Veriflow will check for network-wide invariants violation dynamically before an actual action would take place. The Veriflow system can perform checking within hundreds of microseconds per rule. The invariant checking process contains three major phases: 1. Packet lookup phase\textemdash giving a new rule change, find all rules that will be affected given the insertion, deletion or modification of this new rule change. 2. Forwarding Graph Construction phase\textemdash Construct forwarding graph of those rules affected. 3. Graph Traversal phase\textemdash traversing those forwarding graphs to detect problems.In this work, we aim to boost the performance of the Veriflow system because the original system might fail to meet the performance requirements in some aspects. To achieve that, we first performed an experimental study of the system performance to figure out the where the bottleneck is in each of the following three phases. In phase 1, we surveyed a couple alternative lookup data structures and decided to adopt a multi-level red-black tree based solution. We also proposed a new way to find equivalent class based on our new lookup data structure and a new IP prefix format. In phase 2 and 3, we embedded the graph construction into rule insertion and store the graph in the lookup data structure directly to reduce the overhead. In addition, we did quite a few software engineering related optimizations to further reduce the running time and revamped the code base. We feed the same dataset to both implementations and our implementation will always have a consistently high speedup. This speedup grows linearly with the increases in network complexity. The new code base that comes along with our implementation is also better structured and more readable.