Veriflow system analysis and optimization

Chen, Zhongbo

Permalink

https://hdl.handle.net/2142/50668 Copy

Description

Title

Veriflow system analysis and optimization

Author(s)

Chen, Zhongbo

Issue Date

2014-09-16

Director of Research (if dissertation) or Advisor (if thesis)

Caesar, Matthew C.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Veriflow
• Network
• Data Strucutre

Abstract

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.

Graduation Semester

2014-08

Permalink

http://hdl.handle.net/2142/50668

Copyright and License Information

Copyright 2014 Zhongbo Chen

Owning Collections