臺灣博碩士論文加值系統

隨著網際網路上分散式架構的持續進步，分散式的應用變得更加多元化，如多人視訊會議、線上影音傳輸…等等。把處理負荷分散開來，可以增進系統效能，但也隨之衍生了不少分散式系統的問題，其中群組通訊的因果順序(causal ordering)問題就是一個值得探討的議題。

訊息的因果順序問題，指的是維持訊息間彼此的執行或接收時的順序關係。分散式系統裡，元件間彼此傳訊的機會很大，且訊息間很可能有著複雜的從屬關係。要保證訊息間因果順序的正確性，讓系統有正確的執行結果，無論在有線的網路應用或無線的網路上都是很必要的。舉一個例子來講，在影音傳輸方面，我們當然會希望影像片段和聲音能有正確的配合，能照我們所希望的順序執行，不會因為網路延遲或其他情形而失去了我們要的順序結果。

處理訊息因果順序的方式，可分為二種：1：發送端預先排序，並於接收端再做一次排序。2：將處理因果順序程序放在接收端。二種方式各有其利弊，所以我們的作法就是提出發送端預先排序，然而經網路傳輸後，可能會因網路延遲，而導致次序錯誤，所以在接收端再做一次排序的改良方法。在MOM上預先排序，來獲得較可靠且自動管理的傳訊方式，這樣就不必運用到太多發送端的資源，可適用於行動裝置。

在接收端處理方面，本論文改進causal order的演算法，並加入了時間限制的觀念。在訊息的relation裡區分強度(strength)，依照不同的訊息關係賦於不同的接受順序，並可把訊息因果關係表示成人類易懂的樹狀圖，讓系統可以根據此relation來進行訊息的演算法處理，本論文的方法稱之為Unified Extended Causal Ordering。

With the growth of distributed architecture in the internet, the distributed applications become more and more variable. Distributed computing would enhance the network system performance, and in addition, it would incur some problems like message causal ordering problem.
The message causal ordering problem is to satisfy messages ordering relations between messages when they are executed or received. To guarantee the correctness of message causal ordering is important in wireless networks and wired networks. For example, we would like to have the correct matched voice and video when we watch TV online. We will hope the message ordering can perform just like the ordering we want after network transmitting.
There are two approaches to solve the message causal ordering problem. One is pre-order approach, which schedules messages in senders and reorders them in receivers. The other is just to order in receivers. Both of they have their advantages and disadvantages. Our method is to provide a new approach of scheduling messages in senders and reorder them in receivers to get a better solution. Using the MOM and JMS in the pre-order approach can get reliable communication and automatic management, and we can use our method in mobile devices.
This thesis improves the causal ordering algorithm and adds the limit of time in our post-order. We classify the strength of message relation, and give different deliver sequences according to the strength of message relations. Then we express the relation of message causal ordering into tree graph that human being can easy to know and system can use the algorithm according to this relation. Our method is called ‘ Unified Extended Causal Ordering ’.

中文摘要 ………………………………………….……………………….….……… Ⅰ
英文摘要 ………………………………………….………………………….…….… Ⅱ
誌謝 ………………………………………….…………………………….….……… Ⅲ
目錄 ………………………………………….………………………….…….… Ⅳ
圖目錄 ………………………………………..……………………..…………………... Ⅵ
表目錄 …………………………………………………………………………...……… Ⅷ
第一章 緒論(Introduction) ……………………………………………….…….…….… 1
1.1研究動機與目的 …………………………………….………………….. 1
1.2論文架構 ...…………………………………………..………………….. 3
第二章 背景與相關研究(Background and Related Work) … .………………………….. 4
2.1網路訊息通訊 ….…………………...……………………...……………… 4
2.2因果順序(causal ordering ) .…………………………….………………….. 6
2.2.1 Happened before relation ..……………….……………………….. 7
2.2.2 Causal ordering of events .………………………………………… 8
2.3 MOM(Message Oriented Middleware) ………….……..…………….…….. 9
2.3.1 MOM簡介 ………………………………………………...……… 9
2.3.2 Java Message Service……………………………………………....... 10
第三章 系統架構與研究方法 ........................................................…………………... 12
3.1訊息系統架構部份 …………………….………………………………….. 13
3.1.1訊息pre-order的方法 ……………………………...……………… 13
3.1.2系統架構 …………………………….………………………...…… 16
3.2我們的causal ordering 演算法 ….……………..…………………………. 18
3.2.1 Pre-Order Messages Selection Algorithm .………...……………… 18
3.2.2 Unified Extended Causal Ordering ...………………………...…… 25
3.2.3 the ordering algorithm .......………………………………………... 32
第四章 系統實作與實驗流程 ........................………………….……………..……… 37
4.1系統實作 ……………………………….………………………………….. 37
4.1.1 Message Pre-order module ………………………...……………… 38
4.1.2 Message Post-order module …………………………………...…… 43
4.2實驗 ……………………………………………………………………...… 45
4.2.1測試環境 …………………………….………………………….. 46
4.2.2訊息可靠性測試 .…………………………………………………... 47
4.2.3接收端的評估 ………………………………………………...… 49 4.2.3發送端的評估 ………………………………………………...… 52
第五章 結論與未來發展 ………………………………………….………………….. 57
5.1結論 .….……………………………………………….…………………… 57
5.2未來發展 ...…………………………………………..………………….. 58
參考文獻(Reference) …………………………………………………………………... 59
附錄 ………………………………………………………………………………………. 62
經歷 ………………………………………………………………………………………. 73

[1]S. Alagar and S. Venkatesan, Causal ordering in mobile distributed systems, IEEE Trans. Comput., 46(4): 353--361, 1997
[2]K. P. Birman and R. van Renesse, Reliable Distributed Computing with the Isis Toolkit}, IEEE Computer Society Press, 1994.
[3]K. P. Birman and T. A. Joseph, Exploiting virtual synchrony in distributed systems, Proc. 11th ACM Symp. Oper. Syst. Principles, pp. 123--138, Nov 1987.
[4]K. P. Birman and T. Joseph. Reliable communications in the presence of failures, ACM Trans. Comput. Syst., 5(1): 47--76, Feb 1987.
[5]K. P. Birman, A. Schiper, and P. Stephenson, Lightweight causal and atomic group multicast, ACM Trans. Comput. Syst., 9(3): 272--314, 1991.
[6]K. P. Birman, Building Secure and Reliable Network Applications, Manning Publications Co., 1996.
[7]K. P. Birman, The process group approach to reliable distributed computing, Commun. ACM, 36(12): 37--53, Dec 1993.
[8]Grady Booch; Ivar Jacobson; James Rumbaugh, The Unified Modeling Language User Guide, Addison Wesley Publishing Company, 30. October 1998
[9]Wentong Cai, Bu-Sung Lee, Junlan Zhou , Causal Order Delivery in a Multicast Environment: An Improved Algorithm, Journal of Parallel and Distributed Computing, Vol. 62, No. 1, Jan 2002, pp. 111-131
[10]Jim Gray , The cost of messages , Proceedings of the seventh annual ACM Symposium on Principles of distributed computing January 2000 Pages: 1 - 7
[11]David R. Jefferson , Virtual time , ACM Transactions on Programming Languages and Systems (TOPLAS) July 1985 Volume 7 Issue 3
[12]J. Konorski; K. Malicki, Ordered multicast protocol based on credited virtual acknowledgment ,Electronics Letters , Volume: 38 Issue: 2 , 17 Jan. 2002 Page(s): 101 -102
[13]L. Lamport. Time,Clocks and Ordering of Events in a Distributed System. In Communications of the ACM, 21(7) Pages 558-565, July 1978
[14]Bu-Sung Lee ;Wentong Cai; Junlan Zhou , A causality based time management mechanism for federated simulation , Parallel and Distributed Simulation, 2001. Proceedings. 15th Workship on , 2001 Page(s): 83 -90
[15]Aomar Maddi , Fodil Dahamni , An efficient algorithm for causal messages ordering , Proceedings of the 2001 ACM symposium on Applied computing March 2001 Pages: 499 - 503
[16]Richard Monson-Haefel , David A. Chappell, Java message service , O''Reilly, 2001
[17]Richard Monson-Haefel ,”Enterprise JavaBean,3/e”, Oreilly , 2001
[18]Sun Microsystem , ”Java 2 Platform Enterprise Edition”, in http://java.sun.com/j2ee/index.html
[19]Sun Microsystem , “Java Message Service API 1.0.2”,in http://www.javasoft.com/products/jms/index.html
[20]L. Rodrigues; R. Baldoni; E. Anceaume.; M. Raynal , Deadline-constrained causal order, Object-Oriented Real-Time Distributed Computing, 2000. (ISORC 2000) Proceedings. Third IEEE International Symposium on , 2000 Page(s): 234 -241
[21]M. Raynal, About logical clocks for distribute systems, Operating System Review, 26(1):41-48,1992
[22]Shannon , Hapner , Materena and Davidson , Java 2 Platform Enterprise Edition , Addison Wesley , 2000
[23]Michael Shoffner,”Write your own MOM! ”, http://www.javaworld.com/javaworld/jw-05-1998/jw-05-step.html, Mar. 2002.
[24]Youhei Timura ; Katsuya Tanaka ; Makoto Takizawa , Causal precedent relations among messages in object-based systems ,Parallel and Distributed Systems, 2001. ICPADS 2001. Proceedings. Eighth International Conference on , 2001 ,Page(s): 355 -362
[25]Youhei Timura ; Katsuya Tanaka ; Makoto Takizawa , Group protocol for inter-object communications , Computer Networks and Mobile Computing, 2001. Proceedings. 2001 International Conference on , 2001 Page(s): 297 -302
[26]Youhei Timura ; Katsuya Tanaka ; Makoto Takizawa , Causality of messages in object-based systems, Information Networking, 2001. Proceedings. 15th International Conference on , 2001 Page(s): 619 -625
[27]Youhei Timura ; Katsuya Tanaka ; Makoto Takizawa , Group protocol for object-based systems, Object-Oriented Real-Time Distributed Computing, 2001. ISORC - 2001. roceedings. Fourth IEEE International Symposium on , 2001 Page(s): 145 -152
[28]Youhei Timura ; Katsuya Tanaka ; Makoto Takizawa , Object-based precedency of messages in object-based systems, Object-Oriented Real-Time Dependable Systems, 1999. Proceedings. Fifth International Workship on , 2000 Page(s): 141 -147
[29]Youhei Timura ; Katsuya Tanaka ; Makoto Takizawa , Ordered delivery of messages for various types of invocations in object-based systems , Object-Oriented Real-Time Dependable Systems, 2001. Proceedings. Sixth International Workshop on , 2001, Page(s): 251 -254
[30]Gregory V. Chockler , Idit Keidar , Roman Vitenberg , Group communication specifications ,ACM Computing Surveys (CSUR) December 2001 Volume 33 Issue 4
[31]Takaichi Yoshida , Message ordering based on the strength of a causal relation , Information Networking, 2001. Proceedings. 15th International Conference on , 2001 Page(s): 915 -920
[32]林世燦，An Adaptive Causal Ordering Protocol for Group Model in Wireless Environment ，國立中正大學資訊工程研究所博士論文，2000
[33]黃智源, 利用訊息排程以支援因果次序之分散性群組通訊協定實做 , 國立中正大學電機工程研究所碩士論文, 2000.