Research On The Key Technologies Of Real-time Flow Measurement On Optical Fiber Backbone Network

With the rapid development of network communication technologies and theexplosive increase of network applications, the network has become an importantinfrastructure which deeply affects human society. The performance of the network andits running stability become the key issues related to the development of our society. Asan important means to understand the network, network measurement technology is theresearch foundation for network management, network behavior analysis and thepremise condition for optimizing the network, ensuring network security. According tomeasuring zone, network measurement can be classified as measurement on local areanetwork, measurement on access network and measurement on optical fiber backbonenetwork. Among them, measurement on optical fiber backbone network is a popularresearch topic because it can realize large-scale and multi-user’s overall measurement.The traditional studies of network measurement technology usually concentrate onthe packet-level measurement which makes the management system difficult to processand analyze the huge information. Since it treats the received packets equally, thepacket-level measurement can’t get the internal relations among the packets andhigher-level characteristics of the packets, which are necessary for network behaviorobservation, network management and optimization. To overcome the shortages of thetraditional packet-level network measurement, the flow-level network measurement hasbeen widely concerned by the researchers all over the world. How to realize real-timeflow measurement on optical fiber backbone network by using limited hardwarecomputation and storage resources becomes a challenging and practical research topic.Based on the summary and analysis of the existing research achievements, thisdissertation conducts an in-depth study of the key technologies of real-time flowmeasurement on optical fiber backbone network, including real-time IP packetextraction algorithm, real-time IP packet flow match algorithm, flow timeout strategyand elephant flow measurement algorithm.The main contents and contributions of thisdissertation are as follows:1. Aiming at making the most effective use of the hardware resources, the paralleldescrambling algorithm in IP packet extraction process is studied. A novel resource-optimized parallel descrambling algorithm (ROPDA) is proposed. Compared with theparallel descrambling algorithm based on logic design, ROPDA saves the logicresources, reduces system complexity and improves system performance. Comparedwith the parallel descrambling algorithm based on memory structure, ROPDA can runin the situation of less on-chip memory. What is more, the parameters in ROPDA can beadjusted according to the residual logic and on-chip memory resources in the system. According to the real-time IP packet extraction process, a real-time IP packet extractionhardware platform for optical fiber backbone network is designed. The test results showthat this hardware platform can accomplish the real-time IP packet extraction task onoptical fiber backbone network.2. To ensure the real-time property of flow match for IP packets, the timecomplexity of flow match algorithm should be O(1). For this purpose, theTCAM(Ternary Content Addressable Memory) chip can be used because it can realizeflow match with the time complexity of O(1). However, the memory resource of theTCAM chip can’t contain millions of flows existing on optical fiber backbone network.To solve this bottleneck problem, a real-time IP packet flow match algorithm based ontwo-layer XOR Hash and TCAM (RFMA-HT) is proposed. By using XOR Hashalgorithm, the104bits(96bits) of IP packet head are transferred to reduce the requiredmemory, and a three-layer memory space is designed to avoid conflict in matching. Thetime complexity, memory complexity, processing speed and the feasibility of RFMA-HT are theoretically analyzed. Some practical optical fiber backbone network data areused to evaluate the performance of RFMA-HT. The test results demonstrate thatRFMA-HT is of low computational complexity and conflict rate which can satisfy theneed of real-time IP packet flow matching on optical fiber backbone network.3. There is a great abundance of single-packet flows existing on optical fiberbackbone network which consume lots of system resources. Based on analyzing thecharacteristics of the single-packet flows on optical fiber backbone network, asingle-packet flow optimized timeout strategy (SFOTS) is presented. In this strategy,the single-packet flows can be found and deleted from the memory quickly by setting alow timeout threshold. Therefore, SFOTS improves the memory utilization efficiency ofthe system greatly. The preferences of SFOTS are theoretically analyzed. Somepractical optical fiber backbone network data are used to evaluate the performance ofSFOTS. The test results demonstrate that SFOTS can ensure measurement accuracywhile consuming less memory resources. Especially in the situation of network attack orworm eruption, SFOTS can perform better which can ensure the stability of the system.4. Since the existing elephant flow measurement algorithms have some shortages,such as single definition of elephant flow, high granularity and low stability, a novelelephant flow measurement algorithm based on three-layer LRU and state-hold(3LRU+Hold) is proposed. In each periodic time slice, the flows are classified as longflow, middle flow and short flow according to the number of packets involved in theflow and processed respectively. Thus, the possible elephant flows can be protected. Atthe end of each time slice, the information of the possible elephant flows and elephantflows are retained and updated. The preferences and the feasibility of3LRU+Hold aretheoretically analyzed. Performance of3LRU+Hold is investigated with respect to accuracy and stability by using practical optical fiber backbone network data and Opnetnetwork simulation software. The test results demonstrate that compared with LRU,3LRU+Hold has better accuracy. Also,3LRU+Hold has higher stability, compared withSample and Hold, Multistage Filters and LRU.In summary, several efficient algorithms are developed in this dissertation to tacklethe key problems in real-time flow measurement on optical fiber backbone network.This provides fundamental theory and technique support for the establishment ofreal-time flow measurement system on optical fiber backbone network, networkmanagement and network behavior analysis.