Research On The Network Space Embedding Model And Its Applications

Latency-sensitive applications play very important roles in current environments. Akey issue for its optimization is how to gain the latency between any two nodes in thesystem. As a kind of latency estimation method which with both high-scalability,high-accuracy and low measurement load, network space embedding model has beenwidely deployed in many latency-sensitive applications including peer-to-peer networks,content distribution networks and cloud computing, etc. Hence the theoretical basis andthe optimization methods of this model are of great value to study and put into use.How to ensure the estimation accuracy with low computation cost is the basic issueof the network space embedding model and it is also the central part of this dissertation.On the basis of the accurate classification of the space embedding models, thisdissertation conducts advanced analysis on four aspects: the heterogeneity of the latencycharacteristics, the security problems of the distributed models, the computation costand the generalization ability of those models which rely on the point multiplication,and then, the churns existing in the system. For these four aspects, this dissertationproposes a series of optimization algorithms to improve the performance of the model.The main research and innovations of this dissertation are embodied as following:1. To resolve the contradiction between the homogeneity of the embedding spaceand the heterogeneity of the latency characteristics caused by the different routingstrategies in different autonomous systems (AS), two improved methods is put forwardin this dissertation. The optimization of the loss function is categorized as a kind ofiterative method to solve non-linear equations. Thus the problem of adaptive estimationof the iterative factor in the classic model is raised based on equations’ contradictory,and presents a slow-start strategy for iterative factor estimation through measuring thenormalized error periodically; according to the clustering characteristic presented in theembedding space, this dissertation also presents a clustering characteristic enhancingmethod named drwMDS without any prior knowledge of the topology information ofInternet. Experiments show that compared with the baseline algorithm, these twomethods can improve the accuracy of latency estimation significantly. Furthermore,these methods are compatible with the baseline method which has been deployedwidely and can be upgraded smoothly from the baseline method. 2. A distributed network space embedding model with intrusion-tolerant support isproposed. With the assumption of the inevitability and undetectability of the adversaries,this model can provide acceptable latency estimation accuracy within the limits of thetolerance of the system. In this model, the reputation value of the reference nodes ratherthan the local error of the reference nodes reported by themselves in the classic modelare deemed as the weighting vector, thus this negative influences caused by theadversaries can be mitigated by the quantitative and qualitative superiority of the normalnodes, which provides us a better robustness when facing abnormal latency sequences.This model can be deployed not only as a kind of rescue method while the intrusiondetecting filter or the reputation system becomes invalid, but also independently as asingle space embedding model with strong robustness.3. An adaptive distributed completion algorithm for network latency matrix isproposed. According to the discussion on a kind of sub-gradient descending matrixcompletion algorithm, this problem is deemed as a bi-convex one which can be solvedby the alternative direction method. Thus an Adaptive Distributed Matrix Completionalgorithm, ADMC, is proposed in this dissertation. ADMC utilizes the historyinformation of the latency sequence to give the upper bound of the iterative step size. Itcan reduce the computation cost significantly without any additional measurement orcommunication cost. ADMC also provides a sufficient condition of the loss functionselection to ensure the convex property of the optimization problem, thus, can improvethe generalization capability of the matrix completion algorithm through supportingvarious loss functions.4. Two improving algorithms are proposed to handle the node churn problem. Thechurns is splitted into two different classes: the churns on the network layer and thechurns on the application layer. For the noise existed in the latency sequences whichcaused by the churns on the network layer, this dissertation discusses the robustness of akind of matrix-factorization based non-gradient descending completion method deeplyand then analyzes the significant impact to the intrinsic ill-posed and ill-conditionedinverse problems in the methods caused by the oscillations of the latency sequences. Tomitigate the impact and improve the performance of the matrix completion methods inthe wild, we import a regularization factor to improve the spectrum signature of thecoefficient matrix and a median-kalman filter to smooth the latency sequences. At last,to deal with the topology mutation caused by the churns on the application layer, a two-stage bootstrap algorithm is proposed for the fresh nodes. The whole lifecycle ofthe nodes is splitted into a bootstrap phase and an error-celebration phase and themutation of the topology of the overlay network can be mitigated through delaying thebroadcast of the coordinates of the fresh nodes. This algorithm requires fresh node tokeep radio silent in bootstrap phase and executes the classic algorithm to update andbroadcast its coordinate. Experiments and simulations show that our methods canimprove the estimation accuracy of the network space embedding model in the wild.