Packet Loss Detection Algorithm And Key Points Of Its Implementation In Network Status Monitor

Since1970s, computer network have widely applied to every field in the world,and played an extremely important role. Research and industry community have paidmuch attention on digging network’s internal running status, in which many noveltymethods were proposed and adopted. Network Status Monitor(NSM) is a kind ofinstrument which could observe internal status of network. This instrument extractspacket loss and delay characteristic by analyzing the trace file generated by passivecapture method. The challenge is how to exactly infer the loss packet exists in localnetwork.A detection method and its improved version on loss packet based on LocalRound Trip Time(LRTT) was proposed and implemented in NSM. The key point of thiswork can be concluded as follow.1. By extending detection methods based on TCP retransmission mechanism oracknowledgement packet analysis, a new detection method based on extreme value ofLRTT to infer packet loss exists in local network in receiving flow was proposed. Themethod can correctly deal with all kind of packet loss, as spurious fast retransmission,spurious time out retransmission, batch loss and loss in retransmission.2. An analytic model for LRTT was setup through TCP acknowledgemechanism,itdivide LRTT’s samples into for four subsets which were triggered bydifferent events. Three of the subsetscan be modeled with experimental distributionswhich make their extreme value estimation available. Profound discussionon details byadopting those extreme values into previous method can conclude that using extremevalue of immediate acknowledgement as its maximum LRTT and introducing a newtime out rule would improve its stability and detecting range.3. To fulfill the large calculation capabilities of analyzing network packets, a newpacket header extraction method based on finite state machine was designed to moveprinciple workload to FPGA(Field Programmable Gate Array), and provide a flexibleextending mechanism. This method solved the performance shortage of centralprocessing unit and provides ability of extracting nestable shim layer protocol. It isproved that the method support a high extracting bandwidth and low resource usage, which especially suit for the area of network measurement and security. To integrate thispacket header extraction module in traditional Media Access Controller(MAC), wepropose two layeredFIFO (First In First Out) architecture to eliminate thedifferencesbetween their interface both in software and hardware.4. The proposed loss detection methods have been proved in network emulator andreal captured traces as is stability and performance. In various environment, theexperiment results show an extremely low false detection rate and acceptable cover rate,which is an important advantage of our detection method, especially the false detectionrate is below0.62%when samples are sufficient, even in opposite situation the falsedetection still keep as lower as11.6%.