Time Management Approaches On Message Delivery Order Consistency In Large-scale Distributed Virtual Environments

Distributed Virtual Environments (DVEs) are networking computing environmentsin which multiple participants can interact with one another, share simulation data, and soon. A DVE aims to proffer for participants a real, integral and immersive virtual worldthrough interactions among geographically distributed computing nodes, local or globaldata share and task collaborations. Time management approaches are the key and fun-damental ones in DVEs, which are important to preserve the consistency of message de-livery order and ensure the rational logic of distributed simulations. It's well known thatthe research on the basic principle and key algorithms of time management is one of thefocuses and difficulties in DVEs. Currently, the research work confronts the challengeof time-space complexity arisen from Wide Area Network (WAN), large scale, frequentinteractions, etc. As to the present time management problems of consistency, real-timeproperty, scalability, and so on, this dissertation carries out the research on the theoriesand approaches oriented to message delivery causal order consistency and total order con-sistency, and provides the time management and preservation in large-scale DVEs.Todistributedlypreservethecausalorderconsistencyofmessagedeliveryinrealtimewith global clock, this dissertation has proposed a novel Lightweight Real-Time CausalOrder(LRTCO)algorithmbasedonmessagelifetimeconstraint. ThebasicideaofLRTCOis: firstly, analyze that the dynamicity of network transmission delay is the primary reasonwhyeventscan'tarrivedestinationnodesintimesothatthecausalorderviolationshappen;secondly, predict and compare the network transmission times of messages so as to selectthe proper causal control information of which the amount is dynamically adapted to thenetwork latency variations; thirdly, effectively resolve the problem about preserving thecorrect cause-effect relation in real time with the message lifetime constraint. Experimen-tal results demonstrate that the network transmission amount of LRTCO is unconcernedwithsystemscales, moreover, itcanimprovethescalabilityofDVEsystemsanddistribut-edly preserve the causal order consistency of message delivery with real-time property inlarge-scale DVEs running on WAN.To maintain the causal order consistency of message delivery in real time withoutglobal clock, this dissertation has proposed a real-time causal order time management approach ADCO (Asynchronous Deadline Causal Order). The basic idea of ADCO is:firstly, deduce the comparison principle of time values of different events from differentnodesbasedonthecommonsensethatamessageisboundtobesentbeforebeingreceived;secondly, throughdynamicallyandproperlyselectingthecausalordercontrolinformationfor each event, ensure that any effect event can identify its current minimum causal eventamong arrived events so as to avoid the causal order violations; thirdly, adjust the amountof control information in accordance with network transmission condition, thus the cause-effect relation can be preserved before the event deadline without costing much networkbandwidth. Analysis and simulations show that with limited causal order control informa-tion, ADCO can still real timely maintain the message delivery causal order consistencywith the message lifetime constraint in the condition of asynchronous clocks.To preserve the total order consistency of message delivery with the global clock,this dissertation has proposed a distributed total order control approach for two differentcommunication scenarios of broadcast and multicast. The basic idea of the approach is:firstly, respectively compute the global vectors of delivered events and undelivered eventsthrough analyzing the fundamental reason for total order violations; secondly, deduce theevent processable moment of each node so that different events can be effectively de-livered in the order of their occurrences, which ensures that all nodes in a DVE preserveconsistent before-after relation of event delivery. Analysis and experiments show that thiscontrol approach can reduce the total order violations with smaller overhead and meet therequirement of total order time management.To keep the total order consistency of message delivery without global clock, thisdissertation has proposed a distributed total order control approach applied in the con-dition of asynchronous clocks. The basic idea of the approach is: firstly, differentiatethe possible before-after relation of events after comparing the asynchronous clocks ofthem based on the principle that sending a message always happens before receiving it;secondly, compute the delivery order of events by defining the ``Interval of Local Simu-lation Time'', which can keep the total order consistency of event delivery. Simulationsand experiments demonstrate that this approach can enhance the degree of total order con-trol with asynchronous clocks, in the meanwhile, it has good scalability and widespreadapplication.To evaluate the performance of consistency control approaches, this dissertation has designed and established a multi-layered message ordering simulation and verificationplatform for time management in large-scale DVEs. Generally, the platform has twoparts: Data Generation and Data Acquisition. It contains several modules as RTI (RunTime Infrastructure), Network Delay Simulator, Consistency Control Approach Module,Application BehaviorLayer, VisualDisplayOutput, Node MonitorModule, DataStatisticModule, etc. On the platform, the researchers can not only testify and analyze a newlydesigned consistency control approach, but also verify the performance of it with appli-cation instances, which is quite beneficial to improve and refine the effectiveness of theapproach.