Tóm tắt Luận án Method of resources allocation controller for distributed system in virtual machine base on network coding

d virtualization architecture Based on VMS shown in Fig 2.b, the cloud provides services to the users through VM. Summary, resources allocator in VMS is allocator that optimizes process of resources allocation for applications to increase performance of cloud. 1.2. Related studies 1.2.1. Studies related to resources allocation control in distributed systems 1.2.1.1. Classification of distributed systems 4 − High performance distributed computing − Distributed information systems − Distributed systems 1.2.1.2. The technical problems of network coding control communication resources allocation Thesis research offering optimization models and algorithms proposed adaptive, distributed control rate for the network coding based on the multicast stream. Besides, the optimal solution for multicast communication with network coding is information at the destination set to avoid duplication and achieve optimal throughput. The solution to be implemented on a multicast tree is to rebuild the topology that combines network coding technology to maximize throughput at the destination set. The research algorithms will be experimental, evaluated and can be extended to control message transmission in many different applications. 1.2.1.3. Technical issues in logical timestamps Local states affects the overall operation of the distributed system, two of which are: 1. Logical clock value on servers is inconsistent; 2. The required process into the critical section based on mutual exclusion in Fig 3. The process required into the critical section must wait until receiving enough messages that may affect other servers or deviate from data updates. To solve the local states problem, the Thesis has parallelization of Lamport algorithm to build global state on servers. Fig 3. Mutual exclusion 1.2.1.4. Technical issues shared resources allocation in distributed systems The 3PC algorithm is different from the 2PC algorithm that has precommit state before commit/abort state. The disadvantages of 3PC are commit but non-blocking, in addition to the excessive exchange of messages to restore data independently, resulting in a high of 5 communication overhead. According to Kumar, the comparison between 2PC algorithms and 3PC algorithms is shown in Table 1. Table 1. The comparison between 2PC and 3PC algorithms 2 phases 3 phases Transaction type 2 phases 2 phase extension Voting phase x x Pre-commit phase - x Commit phase x x Blocking low high Message exchange 4(n – 1) 5(n – 1) Communication Overhead low high Log Writes 2n 2n Complexity O(n2) O(n3) Performance low high Apply for distributed transactions hard easy RAS Thời gian thực thi Chính sách Máy ảo Giao thức Gossip Tiện ích Phụ thuộc TN phần cứng Đấu giá Ứng dụng SLA Tổ chức Loại Tải Chi phí Tốc độ Bảo mật Xử lý Kiến thức chuyên môn Thông tin ngang hàng Tài nguyên ngang hàng Thống kê ứng dụng Thời gian đáp ứng Lợi ích Truyền thông CPU I/O Lưu trữ Giá cả thị trường CSDL chia sẻ Hệ thống lớn Thời gian thực Dữ liệu chuyên sâu Chất lượng dịch vụ Thời gian đáp ứng Thông lượng Fig 4. Resources allocation strategies in cloud computing The solution to ensure coherence is one of the necessary solutions to research and build in a distributed system through a message transmission mechanism, strong coherence solutions presented in Section 2.2. In summary, technical mechanism for providing distributed generally respond to application of distributed system deployment. However, limitations of transmission mechanism are redundant problems in communication if multiple servers and allocate information to destination server or client. To overcome this disadvantage, the research challenges is to find solutions eliminate redundant packet if server or client has received same information, there are solutions of network coding. 6 1.2.2. Studies related to resources allocation control in virtualization systems A description of proposed resources allocation strategies in the Cloud Computing model is presented in Fig 4. 1.2.2.1. Network virtualization 1.2.2.2. Software-Defined Networking (SDN) and Network functions virtualization (NVF) 1.2.2.3. Distributed system in virtual machine Fig 5. Distributed system deployments on virtual machines Distributed systems are deployed on VMs on the 3rd level of virtualization system as shown in Fig 5. Each VM can deploy one or more distributed systems in accordance with Fig 5.b. Thus, compared to traditional distribution system, hardware assembly does not need to be considered, instead Virtual system. We call distributed system in this environment is a virtual distributed system. 1.3. Proposed model and solution of resources allocation controller in the virtual server system 1.3.1. Introducing the problem 1.3.2. General model The general model given in Fig 6 describes resourcess allocation controller include five basic parts. 1.3.2. Technical solution The processing takes place inside system is the set of virtual servers Si{i=1..n} through distributed communication system as shown in Fig 7. The network shown in Fig 8 can be described the graph G=(U,V) in Fig 7. The concept of network coding is as follows: In a traditional packet- switched network, the definition of internal data flow is discrete "pieces" from source to destination. At destination or intermediate nodes, the outgoing messages are split into packets, each of which contains some 7 intact or fragmented data messages. All packets do not necessarily transmit by the same routing; but they all came to the same destination, where they were tasked to assemble them into the original message. Fig 6. General model of resources allocation in virtual machine system The Thesis's research on method of resources allocation controller for distributed system in virtual machine base on network coding. The above solution to ensure coherence in virtual distributed system for user and avoid duplication of information, reaching maximum throughput at destination set. Virtual NetworkB Virtual NetworkA Virtual Router VMkVM2 VMi VM1 Virtual Router VMj VMn Virtual Router Fig 7. Virtual distributed communication Fig 8. The network is represented graphically 8 The Thesis presents basic solution of network coding techniques. We consider case of multicast transmission network model shown in Fig 9.b, packets at destination node has a higher reception rate than unicast transmission. Message 1 Message 2 Message 1 Message 1 Message 2 S1 S2 S3 S4 S5 S6 Message 1 Message 2 Message 2 Message 1 Message 1 Message 2 Message 1 hoặc 2 Message 1 hoặc 2 S1 S2 S3 S4 S5 S6(b)(a) Fig 9. Unicast transmission (a) and multicast transmission (b) Considering the network described in Fig 10 is the multicast transmission method associated with the network coding, the XOR operation is performed at intermediate nodes and destinations to eliminate duplicate packets. Message 1 Message 2 Message 2 Message 1 Message 1 Message 2 Message 1Å2 Message 1Å2 S1 S2 S3 S4 S5 S6 Fig 10. Multicast transmission in combination with network coding The probability of remaining cases within 9 events observed probabilities associated probe code can be observed according to Table 2. Table 2. Observed probes No. Destination set Edges S5 S6 S12 S13 S24 S25 S34 S36 S45 S46 1 M1 - 1 0 1 1 0 0 1 0 2 M2 - 0 1 0 0 1 0 1 0 3 M1Å2 - 1 1 1 1 1 0 1 0 4 - M1 1 0 1 0 0 0 0 1 5 - M2 0 1 0 0 1 1 0 1 6 - M1Å2 1 1 1 0 1 1 0 1 7 M1 M1 1 0 1 1 0 0 1 1 8 M2 M2 0 1 0 0 1 1 1 1 9 M1Å2 M1Å2 1 1 1 1 1 1 1 1 9 The Thesis's research on network coding techniques focuses on the following solutions: - The solution of source rate control with network coding is part of a network coding resources allocator in section 3 of the general model to divide packet transmission rate from source to destination set. - The optimal solution of distributed communication based on network coding technology allows optimization of bandwidth, avoiding duplication of information and reaching the maximum throughput at destination set. 1.6. Summary of Chapter 1 The Thesis has given a general model for problem of resources allocation in virtualization system. The Thesis has given an example of the online monitoring system of road motor vehicles presented in the publication (1) and the car parking program presented in the publication (5). Based on the general model presented in the publication (6), the Thesis presents some basic solutions to allow calculation, processing of shared resources on the cloud. The first set of solutions focuses on solving resources allocation problems in distributed systems; the second set of solutions addresses the optimal communication problem for distributed systems in virtual machines based on network coding techniques. CHAPTER 2: SOLUTIONS OF COMMUNICATION RESOURCES ALLOCATION CONTROLLER IN DISTRIBUTED SYSTEM 2.1. The solution to parallelization Lamport algorithm in distributed mutual exclusion 2.1.1. Parallelization of the Lamport algorithm Based on group communication, algorithm Lamport improved way solutions: A station i generated event sending request message is allocated clock value to all remaining stations according to procedure: ( ), , ,i SiS HGETLAM acPOR tT sk all stations after receiving message on check, compare with current value SlocalH of their station ( )1S Si localH H= + and respond to message accepting value with procedure: ( ), ,, , ,local i SiS S H actACC skEPTLAMPORT boolean A message sent simultaneously to station according to procedure to confirm clock value was tied to events ski: ( ), , ,i SiS HUPDATELAMPO T actR sk 10 Fig 11. The global states of messages follows the Lamport algorithm after improvement over Fig 3 The result of parallelization of the Lamport algorithm as shown in Fig 11. The communication resources allocator based on communications grouping is shown in Fig 12. Hệ thống viễn thông ServerA Bộ cung cấp tài nguyên truyền thông Hàng đợi Yêu cầu/ đáp ứng Bên phát ServerB Bộ cung cấp tài nguyên truyền thông Hàng đợi Yêu cầu/ đáp ứng Bên nhận Fig 12. Distributed resources allocation for request/response pair 2.1.2. Applying parallelization of the Lamport algorithm to solve distributed mutual exclusion The study of the Thesis proposed solution of global states processing in the distributed system based on the parallelization of the Lamport algorithm in distributed mutual exclusion. 2.1.3. Performance of parallelization of the Lamport algorithm Parallelization of the Lamport algorithm builds a global state and timestamped of events taking place on servers. Improved algorithms that timestamped of events require 3(N - 1) messages. When applied parallelizing the Lamport algorithm in distributed mutual exclusion, the process enters the critical section requiring (N - 1) message. Therefore, the improved solution of the Thesis has achieved high performance in improving the algorithm of distributed mutual exclusion. 2.2. Proposed 4PcoDT algorithm resources allocation controller in distributed system deployment in virtual machine Distributed system implementation ensures coherence is performed on virtual ring shown in Fig 13. The control fields are separated into eight fields and contents fields described in Table 3. 11 Fig 13. Virtual ring message transmission Table 3. Contents of the control fields in the message Field Meaning F1 Server information starts the virtual ring, 1 1.. 4F n=  (n is number of server). F2 The Jeton value shows up to update server information in the system, the length of the key value is n. Each server will occupy the value at the location of the station itself as specified. F2[i]=0→4, i=1..n F3 The logic clock value is assigned and the message priority setting F4 The current clock value is assigned. If F3=F4, this is the message that starts the request for resources, otherwise the message is moved in the system. F5 Server name is updated when moving in the system. F6 Content corresponding to phase in the system transactions, transactions made four basic phases to ensure data consistency. F7 The state of the action corresponds to the transaction phase in the system F7=1→4, end of ring, F7 increases to one unit. F8 Value ring of registration information, the process of registration completion of a transaction value will increase to one. The structure of message is shown in Fig 13. @$ F1 $$ Content @$ Các trường điều khiển hệ thống Trường nội dung Các biến cờ F2 F3 F4 F5 F6 F7 F8 Fig 14. The message structure of distributed system To ensure coherence, phase processing algorithm of transactions shown in Fig 14. 2.4. Implement topology on distributed systems simulation 2.4.1. Simulation of 4PCoDT algorithm in distributed system To perform simulation process steps follow process: 12 − Step 1: declare the number of virtual buttons to receive and process messages. − Step 2: declare the path to the BRITE file that was exported from the BRITE program − Step 3: run the simulation program − Step 4: get performance results in two forms: graphical display as shown in Fig 14, activities and events as shown in Fig 15. Bắt đầu Giao dịch Kết thúc Giao dịch Kiểm tra tính hợp lệ thông điệp đến Gắn giá trị đồng hồ logic Khóa trường dữ liệu Tạo bảng tạm Chuyển thông điệp di chuyển trong vòng tròn Pha giao dịch = 1 & Hành động = SEND Kiểm tra đồng bộ các sự kiện trên đa Server Phát lệnh thực hiện cập nhật theo giá trị đồng hồ Hủy giao dịch Ghi lại và tách giá trị thông điệp Lấy giá trị pha giao dịch và hành động các pha Sắp xếp trật tự thông điệp Cập nhật bảng tạm Pha giao dịch = 2 & Hành động = TEMP Cập nhật các giá trị trường điều khiển Sắp xếp trật tự thông điệp trong hàng đợi 2 Lấy các giá trị liên quan đến giao dịch từ các máy chủ Pha giao dịch = 3 & Hành động = SYNC Pha giao dịch = 4 & Hành động = UPD Hàng đợi 1 thông điệp Cập nhật bảng tạm Đ S Đ Đ Đ Đ Thực hiện các tiến trình cập nhật CSDL S S S S S Đ Fig 15. The 4PCoDT algorithm ensures coherence Fig 16. Topology implementation results on the DSSim simulation tool 13 Fig 17. The activities and events taking place within the system Event names are shown in Table 4 below: Table 4. Events for nodes No. Event Mean 1 UNKNOWN Unknown events 2 ALL All events 3 MSG_NODE_SEND/ MSG_NODE_RECV Message node send/receive 4 MSG_ROUTE_SEND/ MSG_ROUTE_RECV Message route send/receive 5 ROUTE_BEGIN/ ROUTE_END Route begin/end 6 NODE_BEGIN/ NODE_END Nút bắt đầu/kết thúc 7 NODE_CREATION/ NODE_REMOVAL Node creation/ node removal 8 NODE_TIMER Node timer 9 MSG_DROPPED Message dropped 10 MONITORING_LLINK_CREATION Monitoring link creation 11 MONITORING_LLINK_REMOVAL Monitoring link removal 12 MONITORING_NODE_FUNCTION_CREATION Monitoring node creation 13 MONITORING_NODE_FUNCTION_REMOVAL Monitoring node removal 14 MONITORING_PROP_CHANGED Monitoring prop changed The message structure moving through the system includes the fields description in Fig 16. 2.3.2. Simulation 4PCoDT algorithm in distributed system The thesis presents simulation program of 4PCoDT of distributed system based on car parking problem. Program built on Java language, 14 MySQL database, implemented on Windows Server 2008 deployed in the VMware vSphere. Liên kết Nút vật lý Nút lô gich Dữ liệu di chuyển giữa hai Server Tên sự kiện F1 F2 F3 F4 F5 F6 Giá trị đồng hồ logic hiện tại được gán Fig 18. Structure of a message in a DSSim simulation Fig 19.a shows the current state of data tables on servers, data fields representing state of consistency. The program from client accesses to any server in the system to register location in parking shown in Fig 20.a. After the registration is completed, the notification sent to client that the process was successful. 2.3.3. Review and comment simulation Through four phases implemented in virtual ring, the resulting processes fall into one of two cases: allocate and not allocate shared resources. For processes that are not allocate shared resources, transaction phase cancels transaction and notifies to users. Fig 19. Status of current data tables on servers 15 Fig 20. Program demonstrates the 4PCoDT algorithm Summary of Chapter 2 Chapter 2 presented solutions to communication resources allocation in distributed systems and algorithms to ensure the coherence in the virtual distributed system. Parallelization of the Lamport algorithm in the publication (2) aims to timestamped and builds a global state of processes in distributed systems. Applied parallelizing the Lamport algorithm to ensure a single process enter the critical section and achieve high performance of the distributed system. The 4PCoDT algorithm in the publication (4) ensures the coherence focuses on building messages, control mechanisms, monitoring and routing from source to destination. Disadvantages in communication resources allocation in distributed systems based on multicast transmission are duplicate information at destination, resulting in waste of communication resources. There are many different solutions to solve this problem, the thesis only focuses on solution of network coding. CHAPTER 3: NETWORK CODING TECHNIQUE 3.1. Technical solutions of network coding for communication resources allocation controller in distributed system 3.1.1. Technical advantages of network coding Three major advantages of network coding for communication are optimal throughput, minimum power per bit, and reduced latency. 16 3.1.2. The basic solution of network coding engineering in distributed systems 3.1.3. The constraints in basic solution of network coding The constraints shown in Formula (1) are as follows: , , :( , ) :( , ) 0 if if otherwise i id id i k l l k i l k l U l k l U k ntl dt dt tl k d     − = − =   =    (1) where each link (k, l): , id k ldt is flow of information for destination d of session i, and flow physical of session i with constraints represented by Formula (2) as follows: , , , id i k l k l idt dv d D   (2) The inequality (10) reflects network coding conditions relative to rate between physical flow and information flow Formula (3):  , ,max ,i idk l k l i d dv dt d D=  (3) The rate vector f satisfies constraints Formula (1) and (2) if and only if network coding establishes a multicast connection at arbitrarily close to tli from source Si to destination Di and packets with arbitrary proportions by dtk,l on each link (k, l). 3.2. Proposed solution of source rate controller with network coding 3.2.1. Proposed definitions rates with subgraph Message 1 Message 1 Message 1 Message 1 S1 S2 S4 S5 S6 Message 2 Message 2 Message 2 Message 2 S1 S3 S4 S5 S6 Fig 21. Multicast trees Fig 21 shows muticast tree deployed from encoded subgraphs. 17 Each tree , i x iC x X contains set VxV of links, which determines |V||Xi| multicast matrix MTi has (v, x) element given by Formula (4): 1 0 if otherwise xi vx v V MT  =   (4) Formula (3) becomes Formula (5):  max ,i i idv MT tl ts v Vv x vx x v i i =     (5) Choice source rate tlix to solve general problem by Formula (6) as follows: , max i i x vtl dv ( )ii i T tl (6) Applied to , , i i i vx x v iMT tl dv x X i I     ,iv v i dv ts v V   ( ) ( ) ( ) ( ), , 0i x i i i v x v x z v v ll z tn z tn z   − =      (7) Equation (7) is an equilibrium that allows optimal flow vector. 3.2. Proposed solution to optimize multicast communications with network coding 3.2.1. Requirements for throughput and network topology construction The maximum throughput denoted by thl(U). The packet denoted by g(U). The durability denoted by db(U). The Connection is denoted by kn(U). For unicast transmissions in a U network, balanced parameters are expressed by Formula (8): g(U) = thl(U) = db(U) = kn(U) (8) 3.2.2. Flow information processing techniques Proposed two algorithms are add and remove link include two-phase: start creating topology, and local optimization. 3.2.2.1. Proposed delete links algorithm in multicast The purpose of first phase is to create a relatively low cost k-node connection diagram of this phase as shown in Fig 22. The algorithm of local optimization process is shown in Fig 23. 18 Fig 22. First phase in delete link algorithm 3.2.2.2. Proposed add links algorithm in multicast This algorithm also includes two phases, starting phase generating topology and local optimization process, and second phase is the same as that of remove link algorithm. 3.2.2.3 Propose parallelization Ford Fulkerson algorithm Parallelization Ford Fulkerson algorithm in Figure 24 control all labeled and unapproved nodes with all k-nodes connection, step 2 improvements are as follows: For each edge SjkV, one of two possible situations: . Sj has been labeled and unapproved, Sk unlabeled and S jS jk kll ts . If this situation occurs, labeled it (Sj;+;nhan(Sk)) for Sk, where S ) min( (S ),( )k j jk jS S knhan ts llnhan −= and set Sj has been labeled and approved and Sk is labeled and unapproved; 19 Fig 23. Local optimization algorithm . Sk labeled and unapproved, Sj unlabeled and 0 kS j ll  . If this situation occurss, labeled (Sk;-;nhan(Sj)) for the node Sj, where S ) min( ( )(S ),j Sk kjnhnhan llan= and set Sk are labeled and approved and Sj labeled and unapproved; If node S|U|-1 labeled, go to step 3, otherwise go back to step 2. Parallelization Ford Fulkerson algorithm will follow different constraints and parameters in the thesis study. 3.2.3. Rate of flow in multicast tree with network coding The ratio between network coding and multicast tree is 1,067. Maximum throughput at the target of the networked code solution is double that of the unicast transmission in Figure 25. 20 Fig 24. Parallelization Ford Fulkerson algorithm S1 S2 S3 S4 S5 S6 m1 m1 m1 m1Å m2 (b) (c) Thông lượng cực đại với đa cây định tuyến phân chia multicast là 1.875 Thông lượng cực đại với mã mạng là 2 S1 S2 S3 S4 S5 S6 (a) Thông lượng cực đại với đơn cây định tuyến bán nguyên multicast là 1.5 S1 S2 S3 S4 S5 S6 a c e 1 2 f d 3 b m2 m2 m2 m1Å m2 Fig 25. Advantages of network coding in improving multicast throughput from source to destination 21 3.3. Proposed Linear Network Coding Determine algorithms S1 S2 S3 S4 S5 S6 m1 m1 m1 m1Åm2 m2 m2 m2 m1Åm2 n T D Fig 26. Network coding model The graph follows Figure 26 to distinguish the nodes in the graph. For a node SyT, VO(Sy) denote set of outcoming edge (q,Sy,Sz) from Sy, VI(Sy) denote set incoming edge (q,Sx,Sy) from Sy in Fig 27. A edge v = (q,Sy,Sz) has the tail Sy=Sdu(v) and the head Sz=Sda(v). Sy VO(Sy) Sx Sz VI(Sy) Fig 27. Incoming/outcoming edge of node Sy The Linear Network Coding Determine algorithms shown in Fig 28. The algorithm consists of two phases: − The first phases, the algorithm is implemented to find the traffic, each intermediate intermediate node tT, the set Pt is the discrete discrete path h from the source to the destination. Only the combination of new trees next to be considered during the second phase of the algorithm. − The second phases used a greedy algorithm to visit each edge one at a time and design the linear code used for these edges. The results of implementing network coding for communication resources allocation for distributed systems are shown in Table 5 and Figure 29. 3.4. Evaluate and review technical solutions of network coding communication resources aloocation for distributed systems deployed in virtualized systems Based on the theoretical research and related research results, the Thesis presents algorithms and algorithms for solving general problems of resources allocation controller for distributed system in virtual machine base on network coding. For the solution of ensure coherence in the distributed system, the Thesis has parallelization the Lamport algorithm to allow the process to enter the mutual exclusion in order to eliminate dispersion reciprocity 22 earlier and require less messages than the similar solution. The parallelization of the Lamport algorithm is p