Abstract: OpenFlow makes up for traditional network, but network session identification is inefficient and packet forwarding path selection is poor. Focusing on forwarding path and matching; we propose OGMD model which combin GPU with biological sequence algorithms and machine learning methods to accelerate matching speed and to improve network environment, we also proposed matching algorithm and path selection algorithm. Experiments show matching algorithm gives a speedup of 325 and path selection algorithm makes link loss rate less than 5%, with an average decline 69.35% and network delay less than 20 msec, average fell 63.28%.
INTRODUCTION
With the development of network technology, innovation of existing network becomes difficult. In order to meet needs of next generation network, Greenberg et al. (2005) and McKeown et al. (2008) proposed a novel network named OpenFlow which supports session management, could make up for deficiencies of traditional network and provides higher quality service and more service types. OpenFlow installed on switch which has a session table, could easily add or delete items and effectively determine session type. Session processed by rules. However, how to quickly and efficiently identify network sessions and select a high-quality forwarding path are current hot problems. For these, Moore and Papagiannaki (2005), proposed identification method from packet load, in order to solve port identification inefficiency, however, scanning packet load is not conducive to privacy protection. Now-a-days, there are two ways could quickly identify, one is using optimization algorithms, such as biological sequences; another is using dedicated hardware devices, such as FPGA, specialized hardware costs too much, is not conducive to popularity. So, using GPU to compute is an alternative method. Session forwarding based on IP address and network status, selecting appropriate path to forward. Previously forwarding based on matching session table, choosing right path, but not all paths optimized. OpenFlow provides more services, how rationally and efficiently use these functions and improve forwarding quality is a serious problem. Current researches take advantage of machine learning methods, such as multi-layer perceptron, support vector machines, neural networks, train historical information and find optimal path.
In this study, focusing on quickly and efficiently identify network session and high-quality forwarding packets in OpenFlow, we propose combining GPU parallel computing ability with biological sequence to enhance network session identification speed and accuracy, at the same time, using machine learning method to select appropriate packet forwarding path.
BIOLOGICAL SEQUENCE METHOD
Biological sequence method is mainly used for amino acids similarity and homology matching in proteins, its main approaches are Needleman and Wunsch (1970) proposed Needleman-Wunsch algorithm (Guillou et al., 2013), Smith and Waterman (1981) proposed Smith-Waterman algorithm (Liu et al., 2013), Aji AM proposed WaveFront algorithm (Aji et al., 2008) in 2008 and Martins proposed TWF algorithm in 2001 (Martins et al., 2001), these algrithms have a trmendous impact on addressing similarity comparision.
| Fig. 1: | Smith-Waterman algorithm data correlation |
Needleman-Wunsch algorithm (Guillou et al., 2013) was first applied to solve the similarity of protein amino acid sequence and determine whether were homologous proteins. In the begining, initializing a matrix as global alignment, in Eq. 2, vertical and horizontal axes represent needed sequences. Using recursive calculate Hij in Eq. 1. Where, S(si, bj) is the similarity of sequences ai and bj, wk is gap penalties. At last, getting the highest score by calculating two sequences and two aligned sequences matching results through back matrix but this algorithm is adapted to comparision sequences in which length and content are similar, is not suited sequence piece comparison:
| (1) |
| (2) |
Smith-Waterman algorithm (Liu et al., 2013) was also applied to similarity comparision, compare with Needleman-Wunsch, this algorithm using local matching, Fig. 1 shows its data correlation. Firstly initializing matrix for local alignments, as Eq. 4. Vertical and horizontal axes represent aligned sequences. Using recursive calculate Hij in Eq. 3.
| Fig. 2: | Wavefront algorithm |
If one unit is negative, using 0 alternatives, way back with the literature (Guillou et al., 2013) algorithm is the same. Literature (Guillou et al., 2013; Liu et al., 2013) algorithms’ time and space complexity are O(mn), where, m and n are the length of sequence:
| (3) |
| (4) |
Wavefonrt algorithm (Aji et al., 2008) changes computation method, its diagonally iteration begining from top left corner, computing all of the anti-diagonal matrix elements, as shown in Fig. 2. Because of independence of anti-diagonal matrix elements, so could taken parallel computing. However, if using literature (Liu et al., 2013) algorithm would cause a large number of communications, that is due to three times element value copy.
TWF algorithm can effectively solve literature (Aji et al., 2008) communication overhead problem. Martins et al. (2001) implemented multi-threaded parallel computing with TWF algorithms. TWF merges a plurality of matrices into a block, in order to reduce communication spending. Block merging that takes RxC matrix elements into a complete block, block computation needs copy left R elements, C elements above and one upper-left element. Block constituted by RxC elements, each iteration calculates anti-diagonal row blocks, Fig. 3 shows TWF algorithm.
In short, biological sequence method could improve matching acuracy which is particularly important for OpenFlow switch but how efficiently and accurately use biological sequences method to enhance network session matching is important.
| Fig. 3: | TWF algorithm |
Machine learing method: Machine learning through developing existing knowledge, provide basis in the future, Simon and Leijonhufvud (2012) thought, learning is an adaptive changing process, allows systems to perform same or similar tasks more effectively. Binford et al. (2013), Herskovits and Cooper (2013) thought learning is experience which could organize or correct things. Expert system developers think that learning is a process of acquiring knowledge. In short,
| • | Learning is an external act |
| • | Learning is a intrinsic process |
| • | Learning from practical engineering knowledge |
The main machine learning methods are Support Vector Machine (SVM), Artificial Neural Networks (ANN), Fuzzy System (FS), combining these researches with this study is to train existing network sessions and rules, applying learning patterns on network sessions forwarding to provide better and more services. However, forwarding sessions are massive, high concurrency and high similarity. For these characteristics, current studies take Support Vector Machine (SVM) (Maji et al., 2013) and so on.
Cortes and Vapnik (1995) used SVM analysis small samples, nonlinear and high dimensional pattern recognition (Maji et al., 2013). Este et al. (2009) proposed using SVM to classify network data stream, although this method is not sensitive to small size sample, but depends on sample data acuracy. Li et al. (2007) proposed using SVM method to solve 7 types of protocls, based on feture extraction, finding best combination, its accuracy more than 99.4%. This method requires samples screening. Although these methods present innovative approachs but they are difficult to implement in massive data training, mainly because SVM need to solve quadratic programming for supportting vector and quadratic programming required to calculate n matrix, its time and space complexity is high. Platt (1998) proposed SMO algorithm (Crammer et al., 2013), Joachims (1999) proposed SVM (Chang and Lin, 2011), Burges (1998) proposed PCGC (Hastie et al., 2009) and Mangasarian and Musicant (1999) proposed SOR algorithm (Carrizosa and Romero Morales, 2013) solving secondary plan for improving n-order matrix.
| Fig. 4: | Kepler OpenFlow switch architecture |
In summary, although machine learning methods provide basis for practical work, regardless Kmeans or SVM exists more or less problems, mainly around sample pre-selection and data size, support vector machine requiring samples high accuracy, as well as restrictions on size. K means method suits for data set less than 10 K.
OGMD OPENFLOW SWITCH MASSIVE NETWORK DATA ANALYSIS MODEL
OGMD OpenFlow switch model is consisted by two parts, one is session matching, the other is session forwarding, matching using biological sequence method based on GPU, forwarding using session ranking algorithm.
OGMD OpenFlow switch massive network data analysis model architecture: OGMD OpenFlow switch effectively integrates GPU into OpenFlow Switch, in order to improve matching accuracy and efficiency, network packets coming from interface, Flow Table module will handle incoming data and then copy these data to GPU Pattern Match which complete rule matching and label network session. OGMD OpenFlow Switch processing framework shown in Fig. 4.
OGMD OpenFlow switch network session matching algorithm: OGMD OpenFlow switch network session matching algorithm based on GPU implement efficient network session matching, achieve wire-speed processing, this section describes concepts and networking session matching algorithm.
| • | Related concepts: | |
| • | Kernel, referring to CUDA GPU running function | |
| • | Thread blocks, refer to thread set, each thread independently run in thread block. Assuming one thread block N threads | |
| • | SM, scheduling concurrent threads in hardware, scheduling overhead does not exist, threads running on SM, each SM could run multi-threaded block | |
| • | OGMD OpenFlow switch network session matching algorithm: In previous section, we mainly introduce biological sequence matching algorithm, although compare TWF algorithm with literature (Aji et al., 2008) algorithm the communication overhead has decreased, but still not take advantage of GPU’s parallel processing capabilities. The main reason is that only one thread involved in calculation, in order to enhance thread utilization of system resources, we propose KTWF algorithm which puts tiles into diamond-shaped pieces, all threads involved in calculation in thread block, using kepler architecture GPU. Tile number: Thread_N, each thread block is responsible for calculating a row tiles, the same color tiles represent different threads parallel execute in the same cycle; arithmetic sequence is consistent with TWF algorithm |
| Algorithm 1 | : OGMD OpenFlow switch network session match |
Because network session matching needs thread blocks parallel computing and atomic operations will affect efficiency. In order to reduce the number of atomic operations, this study selects tree algorithm to improve efficiency:
| • | Thread keep maximum matching value of matrix elements |
| • | After completion calculation, using tree algorithm to obtain maximum tile |
| • | Compare tile with global maximum atomic, complete the newest updating |
OGMD OpenFlow switch network session forwarding algorithm:
| • | Related concepts: During OGMD OpenFlow switch network session forwarding algorithm performing. At first retrieval the most relevant network path, retrieval returns two values, one is authority value which is the center value of all session paths; another is center value refers to network path points authority value. Algorithm iterative steps: update authority value and central value, the center and authority value calculation as shown in Algorithm 2 |
Update authority value rule: ∀P, Update authority value auth(p) as shown in Eq. 5:
| (5) |
Update center value rule: ∀p, Update center value hub(p) as shown in Eq. 6:
| (6) |
where, n is network session number and i is network session p selected path.
| Algorithm 2: | Node auth and hub value calculate algorithm |
OGMD OpenFlow switch networksession forwarding algorithm: At the beginning of execution, ∀p, auth(p) = 1 and hub(p) = 1, assuming two types updating rules: Update authority value rule and Update center value rule. In order to calculate each node two values, you need to repeat the iterative update rules. Steps show in Algorithm 3.
| Algorithm 3: | OGMD session caculate algorithm |
OGMD OPENFLOW SWITCH EXPERIMENT
OGMD OpenFlow Switch experiment use server equipped with 8 i7 processor; 128 GB memory; 2 NVidia Tesla K20 graphics, network card chosen two pairs fiber ports 10000 Mbps card, peak transfer rate up to 40000 Mbps; install Ubuntu OS 64 Bit operating system.
| Fig. 5(a-b): | OpenFlow network forwarding algorithm. (a) Network packet loss and (b) Network time delay |
Test data collects from network backbone real-time data; its size is 1357 GB. Flow table capacity is 370,254 items. Experiments mainly test network session matching efficiency, comparative testing KTWF algorithms are in CPU and GPU environment speedup. Speedup tests flow table capacity from 50000-250,000, data size from 10-100 GB; forwarding algorithm test mainly focus on link state, whether is an appropriate path or existing congestion, through packet delay and loss for analysis.
OGMD OpenFlow switch network session matching algorithm: The OGMD OpenFlow Switch network session matching algorithm testing Needleman-Wunsch, WaveFront, Smith-Waterman, TWF and KTWF algorithm at CPU, GPU runtime and speedup, GPU running time as shown in Table 1, laboratory tests indicate that acceleration KTWF algorithm closer than 325, much better than other algorithms and can meet massive data network needs.
OGMD OpenFlow switch network session forwarding algorithm: Comparison with whether using algorithm link status, test link bandwidth is 1 Gbps. Packet loss as shown in Fig. 5a, network delay as shown in Fig. 5b. Experiments show that using forwarding algorithm packet loss rate and delay appear overall downward trend, average, respectively dropped 69.35 and 63.28%, computation as shown in Eq. 7:
| (7) |
where, i is total numbers, yiwithout is data without adopting algorithmm, yihave is data adopting algorithm.
| Table 1: | Matching algirithm GPU runtime |
| NW*: Needleman-Wunsch, WF*: WaveFront, SW*: Smith-Waterman, KT: KTWF | |
CONCLUSION
This study investigates biological sequence algorithm and GPU, takes both into OpenFlow network session matching, using machine learning method to study network session properties, forwarding sessions to appropriate network link. Focusing on forwarding path and matching, we propose OGMD model which combining GPU with biological sequence algorithms and machine learning methods to accelerate matching speed and improve network environment; we also proposed matching algorithm and path selection algorithm. Experiments show matching algorithm gives a speedup 325 and path selection algorithm makes link loss rate less than 5%, with an average decline 69.35% and network delay less than 20 msec, average fell 63.28%.
ACKNOWLEDGMENTS
Thanks to National Supercomputer Center (Tianjin) and National Internet Information CITIC providing data and technical support for this article.