Ning Li,Qiaodi Zhu,Zhongliang Deng
School of Electronic Engineering,Beijing University of Posts and Telecommunications,Beijing 100876,China
Abstract: The packet loss classification has always been a hot and difficult issue in TCP congestion control research.Compared with the terrestrial network,the probability of packet loss in LEO satellite network increases dramatically.What’s more,the problem of concept drifting is also more serious,which greatly affects the accuracy of the loss classification model.In this paper,we propose a new loss classification scheme based on concept drift detection and hybrid integration learning for LEO satellite networks,named LDM-Satellite,which consists of three modules:concept drift detection,lost packet cache and hybrid integration classification.As far,this is the first paper to consider the influence of concept drift on the loss classification model in satellite networks.We also innovatively use multiple base classifiers and a naive Bayes classifier as the final hybrid classifier.And a new weight algorithm for these classifiers is given.In ns-2 simulation,LDM-Satellite has a better AUC(0.9885)than the single-model machine learning classification algorithms.The accuracy of loss classification even exceeds 98%,higher than traditional TCP protocols.Moreover,compared with the existing protocols used for satellite networks,LDM-Satellite not only improves the throughput rate but also has good fairness.
Keywords: LEO Satellite Networ;TCP congestion control;concept drift detection;ensemble learning;loss classification
Satellite communication plays an irreplaceable role in the current and future communication systems [1].Among them,the LEO satellite has become a research hotspot in recent years due to its proximity to the ground and short propagation delay[2].However,the high link error rate in LEO satellite network results in an increasing probability of packet loss,which greatly affects the communication quality[3].
There have been some methods for classifying the types of packet loss,wireless link errors or congestion.[4] used some network parameters,like RTTs,ROTTs,and IAT to form classification rules.Biaz[5],mBiaz[6],and Statistical Packet Loss Identification(SPLD) [7] selected the packet arrival time interval,Zigzig [8] and Spike [9] used one-way transmission time,and the Vegas predictor [10] chose The round trip time as parameter,then set a decision threshold.However,these methods have limitations because it is difficult to determine the decision threshold.In addition,only one feature cannot obtain high classification accuracy[11,12].Then,researchers proposed to combine multiple features and algorithms in data mining and machine learning.They made decision based on a driving model by learning the correlation between features.In [13],the machine learning classification method was first proposed.[14] used a Naive Bayes model to classify the loss types.However,the classification accuracy of these single model is greatly affected by the number of samples and features.[15]analyzed the classification accuracy of multiple machine learning models,the classification accuracy of the ensembl learning method is the highest.
Although the ensemble classification model has the best performance,the classification accuracy is greatly affected by the concept drift [16,17].When concept drift occurs,the probability of packet loss increases,and along with the changing data flow distribution,the distribution of lost packets also changes,resulting in a reduction in the accuracy of the current classification model [18].If the occurrence of concept drift can be detected in advance and the classification model adjusted effectively,the cause of packet loss will be confirmed faster [19,20].Gama et al.[21]proposed a drift detection method (DDM) for binary classification.However,this method based on error rate cost high.EDDM [22] is an optimized version of DDM,which is improved based on the average distance and standard deviation between two consecutive errors.[23] proposed a frame detection concept drift(ADWIN)based on a sliding window that changes according to whether concept drift occurs [24].However,existing research based on concept drift only consider ground scenarios where the network environment is stable and the data distribution does not change dynamically.The data distribution in the LEO satellite network changes frequently and the concept drift is greater.
We proposed a new packet loss classification scheme (LDM-Satellite) for LEO satellite networks.As we know,this is the first article to consider concept drift in the research of loss classification.Base on the distribution characteristics of the data flow in the network and the hybrid ensemble learning framework,with the goal of maximizing the difference of multiple base classifiers,we construct a new weight algorithm,by weighting multiple base classifiers,determining the type of packet loss.
The rest of the paper is organized as follows: Section II introduces the overall framework of the proposed LDM-Satellite.Section III is the principle and specific implementation of each module.Section IV is the experimental results,including the performance comparison of LDM-Satellite classification accuracy and Goodput.Finally,Section V is summary.
The framework of LDM-Satellite is shown in Figure 1.It includes three parts: concept drift detection module,packet loss data cache module,and classifier integration module.
Figure 1.LDM-Satellite architecture.
Figure 2.D_ cache caches data samples in the most recent time T.
The data stream first passes the concept drift detection module.If no concept drift occurs,hand over the lost data packet to the classifier in integration module to determine the type of loss,and then update the weight of the corresponding base classifier.If concept drift,it indicates that the network topology has changed,or the communication link has been switched,etc.,causing the distribution characteristics of the data flow changed.Therefore,we can directly update the base classification model without waiting until the accuracy of the ensemble classifier obtained,which greatly improve the classification efficiency of the model.In addition,for updating the model online,every time after classification,here we do not directly discard the collected lost packets,but first move them to the cache.It always remembers the information of lost packets from the current to the past T time.When concept drift,these samples in the cache are used to train new base classifier.The specific introductions of the three modules are in Section III.
Based on the dual threshold detection method,we proposes a corresponding window adjustment strategy in this paper,which makes the decision more timely and effective.
After passing through the window,the data stream S is divided into continuous data blocks S={D1,D2,···Dt,Dt+1,···}.The sample in each data block isXt=where(i=1···n)represents n samples features.We use the unidirectional delay of the packet,the time interval between the last normally arrived packet and the first outof-order packet received,and the number of consecutive lost packet to be the features of the lost packet.ytis the class label of the sample at time t.After features are determined,dual thresholds are set according to the minimum classification error ratepminand the minimum standard deviationδmin.Based on these thresholds,we can detect the concept drift precisely.
The size of sliding window is adjusted according to the detect result.However,if the window is too large,the time point where concept drift occurs may be missed.If the window is too small,the detection is inefficient.In view of the above problems,this paper proposes a segmented window adjustment strategy,which is different from the previous single adjustment method.This strategy sets more accurate and effective window adjustment methods for different judgment results.Details as follows:
1.Whenpt+δt 2.Whenpmin+αδmin 3.Whenpt+δt >βpmin+δmin,concept drift has occurred.We need to compress window,so setwt+1=μwt.At this time,the data distribution in the network environment have changed,so the model is no longer applicable.There needs a new base classifier. Whereα,βis weighting factors and they are two constants,α<β.wtis the current window size andwt+1is the window size at the next moment.FurthermoreWbis the base window size.μrepresents the window change factor,Calculated as follows: Wherepmaxis the maximum value of classification error rate. When concept drift occurs,a new base classifier needs trained.Considering the time correlation between data samples,a data cache D_cache is set here.Following the ”first in first out” principle,we save the information of the lost packets.When concept drift detected,we use these samples to train the base classifier. If the packet lost and the current cache queue Q is not full,adding the information of this lost packet to the Q,as shown in Figure 2.Otherwise,in order to ensure the freshness of the data and the adaptation of the classification model,we removing information of old data before time T from the queue.If there is no packet lost,unnecessary information need not cached,so we directly discard it.The samples that cached in the D_ cache will be used for online training of the base classifier. In this paper,we build a hybrid integration framework with multiple base classifiers and a naive Bayes classifier.Moreover,a weight algorithm of base classifier based on incremental learning is proposed.Finally,we combine the weighted classification result of base classifiers and naive Bayes classifier,which is used for online classifying the type of packet loss.The following is the explanation of this module in depth through the offline training of the base classifier and the online update based on concept drift detection. 1.Offline training phase The hybrid integration framework that we proposed is shown in Figure 3,whereDirepresents the current i-th sample data block,Ciis the i-th base classifier,wiis the weight of this classifier,and K represents the number of classifiers that used for ensemble.If the current number of base classifiers is less than K,then useDito construct a new base classifierCiand assign corresponding weights to it.Otherwise,use the most recent K data blocks to construct a naive Bayes classifierC′.For the sample X inDi,in the naive Bayes classifier,the sample category is determined by the maximum posterior probability.The probability that sample X belongs to categoryymis: Figure 3.Hybrid integration framework. Where P(X)is constant,therefore,formula(2)can be simplified to: Where P(Ym)is the prior probability of categoryYm.In Naive Bayes,it is assumed that the features of the sample are independent of each other,so: WhereP(χi |Ym) is the conditional probability of the i-th featurexiwhen the sample belongs to theYmclass.According to formula (2) (3) (4),the decision equation of the naive Bayes classifier can be derived: The weight allocation algorithm based on incremental learning is as follows: first,the base classifierKiis trained with the data blockDi,and each training sample is given a weightαj,where j is the number of times the sample is processed.The mean square error of the available base classifierKion the sample setDiis: Where|Di|is the number of samples in the data setDi.Then assign weights to each base classifier based on the classification results: In order to prevent the denominator in Equation(7)from being 0,add a small enough positive valueε.Then update the weightαjof the samples in the data setDi.By increasing the weight of the wrongly classified samples,the base classifier will focus more on the wrongly classified samples.The sample weights are updated as follows: Finally,all samples in the data blocksDi?1,Di?2,···,D1,are used as training samples for the base classifierKi.After each training is completed,new weights are assigned to the samples according to Equation (8).The weight ofαjis based on the classification errorδiof the current sample in Equation (6),and the weightwiof each base classifier is updated according to Equation(7).At this point,we obtain the simple Bayesian and base classifiers that required for classification. 2.Online classification stage When distinguishing the type of packet loss online,the classifier in the ensemble module is updated in real time based on the concept drift detection result and the online sample classification result.When a concept drift occurs,the new base classifier is trained,and the classifier with the worst replacement performance is selected based on the weight.Figure 4 is a block diagram of the online update of the classifier. Figure 4.Block diagram of online update of classification model. When detect concept drift,the data in the cache module is used to train a new base classifierand base on the above formula (6) (7) to set weight.Then update the base classifier queue at the same time.Finally integrate multiple base classifiers with weights and naive Bayes classifiers to get the final classifier: The former part of formula (9) is the result of the classifier,whereCiis the i-th base classifier currently ensemble,wiis its weight,through the function sign()and transformation,the final classification result is 1 or 0.That is,packet loss due to congestion or wireless error.The second part is the naive Bayes classifier,which not only eliminates the influence of noisy data,but also weights the classification results of the base classifier to improve the accuracy of packet loss classification. We use the simulation environment of Figure 5 to evaluate LDM-Satellite.In this scenario,in addition to multiple LEO satellites and inter-satellite links in the satellite network,there are multiple sending and receiving ends connected to the earth station.Each cable and satellite link uses HOL priority scheduling queues.We set the number of user connections N=20,the capacity of the satellite link c=1300 segments/s,corresponding to the TCP field of 1000 bytes,the value is close to 10Mb/s.The buffer size of the satellite uplink is 50 segments,the maximum congestion window size is maxCwnd=64 segments,and the buffer size of each receiving end is recCwnd=512 segments.The value of RTT is set to 50ms.The packet loss rate caused by link errors in the satellite link varies from 10?5to 10?1. Figure 5.Simulation scenario of the satellite network. Figure 6.Confusion matrix for packet loss classification. The training data set of this paper was obtained through the network simulator NS-2[25].In our study,collecting 35,441 lost data packets(22,426 are due to congestion).Figure 6 is the confusion matrix of LDMSatellite’s classification results on this data set,where 1 represents congestion(CL),0 represents wireless error(LE),dark blue represents the result of correct classification,and white represents the result of incorrect classification. Figure 7.Comparison of ROC curves of LDM-Satellite and other machine learning methods. According to the classification result of Figure 6,the precision rate Precision=0.984 and the recall rate Recall=0.987.In order to evaluate the classification performance better,based on the accuracy rate and recall rate,we calculate the f1_score,which is more than 0.985.Therefore,it is proved that the classification accuracy of LDM-Satellite is high.Moreover,we compare LDM-Satellite with several common classification algorithms such as LogisticRegression,DecisionTree,RandomForest,and GradientBoosting in Figure7.We can see from the ROC curve that LDMSatellite is significantly better than other classification algorithms. In order to compare their performance in more detail,we get Table 1.Two new TCP variant protocols,Veno and WestWood are added.As shown,the classification performance of the machine learning algorithms is far superior to the traditional TCP variant protocol.LDM-Satellite and Gradient Boosting these two ensemble methods have a higher AUC value than other single classifier.In terms of time consumption,Decision Tree takes the shortest time,but the misclassification rate is too high.Traditional TCP protocol classify lost packet based on multiple arriving ACKs or certain variables,such as RTT’s single threshold.These variable information need to be obtained before classification,so it takes too long.Moreover,the parameters are affected by many factors,so the final classification result is unstable,and the reason for the loss cannot be accurately got. Table 1.Comparison of various classification methods. Table 2 is the classification performance under different packet loss rates,from comparing the TCP protocol with the LDM-Satellite and other commonly used TCP protocols,such as TCP Reno,TCP Veno,and TCP WestWood+.The random packet loss rate is 10?5to 10?1.We can see that,as packet loss rate increases,TCP Reno and TCP WestWood+will randomly lose packet.The probability that a packet is misclassified as congestion increases.The classification performance of TCP Veno is closely related to the value ofβ,hereβis 5.For the proposed LDMSatellite,the accuracy rate of loss classification exceeds 98%,which can effectively avoid unnecessary reduction of congestion windows and improve network transmission performance. Table 2.Comparison of classification results under different packet loss rates. Figure 8 is throughput rates of LDM-Satellite and WestWood+,Veno,and Reno in different scenarios.In (a),the RTT is 50ms and the packet loss rate is set to 2%.It can be seen that the Goodput of all protocols is low when the bandwidth is low.However,as the bandwidth increases,the performance of LDM-Satellite is far superior to the others.In(b),the bandwidth and packet loss rate are 10Mbps and 2%,respectively.As Delay increases,the overall Goodput of TCP variants gradually declines,but Goodput of LDM-Satellite is always higher.Because the traditional TCP protocol adjusts the size of the congestion control window through predefined rules,which is too conservative.LDM-Satellite can quickly adjust the congestion window size based on concept drift detection and high-precision classification.Therefore,LDM-Satellite greatly improves Goodput under different bandwidth and delay scenarios. At the end of the experiment,we compare the throughput and fairness of the LDM-Satellite with the TCP protocols that are suitable for satellite networks,such as Hybly,Peach+,etc.The results are shown in Figure 9 and Figure 10.From Figure 9,in the case of low link error rate,Goodput of all protocols is relatively high,among which LDM-Satellite,Hybla and NewReno are closer to the link capacity c=1300 segments/s.In addition,as the packet loss rate increases,according to the adjustment of the congestionwindow,the value of Goodput decreases.However,LDM-Satellite has a better Goodput,especially when the packet loss rate is very high,for example,when the packet loss rate is 10?1,the Goodput of LDM-Satellite can reach 92%with the link capacity c. Figure 8.Comparison of throughput rates between LDMSatellite and WestWood+,Veno,Reno in different scenarios.(a)Under different bandwidths RTT is 50ms,loss rate is 2%.(b)Under different delaysbandwidth is 10Mbps,loss rate is 2%. Figure 9.Comparison of Goodput with different protocols for LEO. Figure 10.Fairness comparison between LDM-Satellite and multiple LEO satellite TCP. Figure 10 is a fairness index chart of LDM-Satellite and various TCP protocols for satellite networks.It presents,as the packet loss rate increases,the Fairness value of each version of the TCP protocol increases,and all are close to 1.LDM-Satellite guarantees better fairness and will not occupy network bandwidth too aggressively. In this article,we propose a new loss classification strategy of TCP packet (LDM-Satellite) for LEO satellite networks,which fully considers the impact of satellite network dynamics on data distribution characteristics.Since the ensemble classification model is greatly affected by concept drift,this is the first paper that innovatively proposes to detect the concept drift of the data stream before classification.By detecting and then classifying,the current packet loss type can be more accurately determined according to the network status.In addition,this paper also builds a hybrid integration framework of base classifiers and a Naive Bayes classifier,and integrates multiple classifiers by a new weight distribution algorithm.In simulation experiments,our method has higher accuracy than other classification algorithms.Under different packet loss rates,LDM-Satellite performs better.Compared with TCP protocols such as cherry,Hybla,and peach+,it effectively improves Goodput.What’s more,LDMSatellite also has better fairness for other protocols and fairness in resource allocation. ACKNOWLEDGEMENT The authors wish to thank every responsible reviewer for his/her comments.The authors also wish to acknowledge the Wireless Network Positioning and Communication Integration Research Center in BUPT for financial support.3.2 Lost Data Cache Module
3.3 Hybrid Integration Module of Classifier
IV.EXPERIMENTAL RESULTS
V.CONCLUSION