e-workflow於電子商務與電子商業領域中已經成為重要的技術之一，其中以路徑控制對e-workflow績效之影響最大。此篇論文主要目的是找出瓶頸問題並選擇有效率之路徑，藉此提升e-workflow路徑處理之績效。大多數傳統方法如靜態式路由、動態式路由，甚至ARC方法皆未考量一些重要之影響因素，如瓶頸問題或是節點與鏈結間權重比率；這些被忽略之因素極可能導致網路堵塞進而形成不穩定之傳輸。有鑑於此，我們參考層級架構與瓶頸問題之概念，提出X-ARC演算法，此演算法架構於Internet-like之網路型態：半仙人掌網路(Semi-Cactus Network)。此演算法的總網路成本計算主要分為節點成本與包含瓶頸成本之鏈結成本，並加入內隱與外顯因素之考量。複雜度分析的部分，利用X-ARC與傳統方法之比較，來證實X-ARC演算法之高效率與選擇路徑之最佳性。此外，使用網路模擬工具NS-2來建立半仙人掌網路之拓樸進行模擬實驗，並加入X-ARC與ARC程式產生X-NS-2模擬器。然後計算出關鍵績效指標(KPI)以評估與比較X-ARC、ARC、與靜態式路徑控制演算法績效之優劣。最後，根據實驗之結果來分析並證實X-ARC演算法具有較好的績效而且使得e-workflow路徑控制更穩定且更具調適性。

E-workflow has been one of main technologies in e-commerce and e-business. The routing control makes a great impact on the performance of e-workflow. The objectives of our thesis are to locate the bottleneck and to find an efficient path for enhancing the processing performance of e-workflow routing. The conventional methods, including Static, Dynamic and ARC routings, do not consider some essential factors such as bottleneck or weight ratios of nodes and links to possibly lead to network congestion and unreliable transmission. Based on layered structure and bottleneck, we take the total cost with bottleneck to design a new algorithm called X-ARC in an Internet-like structure: semi-cactus network. In addition, the total cost can be divided into node cost and link cost with bottleneck, and be taken into account some implicit and explicit factors. In the complexity analysis, we compare the X-ARC, ARC, and Static algorithms to assist us in validating the optimality and efficiency of routing in X-ARC algorithm. Furthermore, we design a simulator with semi-cactus network topology based on NS-2 and inset into X-ARC and ARC procedures called X-NS-2. Besides, we calculate the KPI values for evaluating and comparing the performance among X-ARC, ARC and Static routing algorithms. Consequently, we analyze experimental results and then identify that X-ARC approach can makes e-workflow routing more reliable and adaptive.

Abstract --------------------------------------------------------ii
摘要 --------------------------------------------------------iii
Figures --------------------------------------------------------vi
Tables --------------------------------------------------------vii
1. Introduction ------------------------------------------1
1.1. Backgrounds -------------------------------------------1
1.2. Motivation and Objectives -----------------------------2
1.3. Thesis Structure --------------------------------------3
2. Related Works -----------------------------------------4
2.1. The Workflow Management System ------------------------4
2.2. Conventional Routing Strategies Overview ---------------6
2.3. Influential Parameters on E-workflow Routing Performance --7
3. Research Architecture and Methods ----------------------8
3.1. The Structure of Research -----------------------------8
3.2. Description for Research Method ------------------------9
4. X-ARC Design Issues and Complexity Analysis ------------10
4.1. Related Definitions and Algorithm Design of X-ARC ------10
4.1.1. Related Definitions ----------------------------------10
4.1.2. X-ARC Algorithm Design -------------------------------13
4.2. An Illustrative Example of X-ARC -----------------------17
4.3. Complexity Analysis for X-ARC --------------------------19
5. Simulation Design and Experiments Setup ----------------21
5.1. Simulation Procedures and Design -----------------------21
5.1.1. The Simulation Procedure for X-ARC -------------------21
5.1.2. The Simulation Design of X-ARC -----------------------23
5.2. Experimental Platform and Setup ------------------------25
5.2.1. Experimental Environment -----------------------------25
5.2.2. Experiments Setup ------------------------------------27
6. Performance Evaluation and Results Analysis ------------28
6.1. Performance Evaluation Criteria ------------------------28
6.2. Experimental Results and Analysis ----------------------29
7. Conclusions --------------------------------------------38
References ------------------------------------------------------39
Appendix A. C++ Language in X-NS-2 -----------------------------42
Appendix B. AWK Language in X-NS-2 ----------------------------49

[1]W.M.P. Van Der Aalst, “Process Oriented Architectures for Electronic Commerce and Interorganizational Workflow”, Information Systems, Vol. 24, No. 8, December 1999, pp. 295-318.
[2]W.M.P Van Der Aalst, “How to Handle Dynamic Change and Capture Management Information? An Approach Based on Generic Workflow Models”, International Journal of Computer Systems, Science, and Engineering, Vol. 16, No. 5, 2001, pp. 295-318.
[3]David H. Bailey, “Little’s Law and High Performance Computing”, RNR Technical Report, September 10, 1997.
[4]Michael Barbehenn, “A Note on the Complexity of Dijkstra’s Algorithm for Graphs with Weighted Vertices”, IEEE Transactions on Computers, Vol. 47, No.2, February 1998, pp. 263.
[5]J. Cardoso, S. Amit and J. Miller, "Workflow Quality of Service," Enterprise Inter- and Intra-Organizational Integration - Building International Consensus, November 2002, pp. 303-312.
[6]Jae Chung and Mark Claypool, “NS by Example”, Worcester Polytechnic Institute (WPI) Computer Science, Available Online at http://nile.wpi.edu/NS/.
[7]Douglas E. Comer, Computer Networks and Internets, with Internet Applications (3rd Edition), Prentice Hall, February 2001.
[8]David Edmond and Arthur H.M. Ter Hofsted, “A Reflective Infrastructure for Workflow Adaptability”, Data and Knowledge Engineering, Vol. 34, No. 3, September 2000, pp. 271-304.
[9]S. Ellis, K. Keddara, and G. Rozenberg, “Dynamic Change within Workflow Systems”, In Proceedings of ACM Conference On Organizational Computing Systems (COOCS 95), 1995.
[10]Paul Grefen, Karl Aberer, Yigal Hoffner, and Heiko Ludwig, “CrossFlow: Cross- organizational Workflow Management in Dynamic Virtual Enterprises”, International Journal of Computer Systems Science & Engineering, Vol. 15, No. 5, September 2000, pp. 277-290.
[11]Marc Greis, “Tutorial for Network Simulator ns”, Available Online at http://www.isi.edu/ns/tutorial/.
[12]Jonathan Grudin, “Computer-Supported Cooperative Work: History and Focus”, IEEE Computer Society Press, Vol. 27, No. 5, May 1994, pp. 19 – 26.
[13]E Guntama, E Chang, N Jayaratna, and Leo Pudhota, “Extension of Activity Diagrams for Flexible Business Workflow Modeling”, International Journal of Computer Systems Science & Engineering, Vol. 18, No. 3, May 2003, pp. 137-152.
[14]David Hollingsworth, “Workflow Management Coalition -The Workflow Reference Model”, WfMC-TC-1003, Version 1.1, Available Online at http://www.aiim.org/wfmc/ standards/docs/tc003v11.pdf, January 1995.
[15]Polly Huang, John Heidemann, “Minimizing Routing State for Light-weight Network Simulation”, In Proceedings of the International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, August 2001.
[16]Justus Klingemann, “Controlled Flexibility in Workflow Management”, In Proceedings of 12th International Conference on Advanced Information Systems, June 2000, pp. 126-141.
[17]A. Kumar and J.L. Zhao, “Dynamic Routing and Operational Controls in Workflow Management Systems”, Management Science, Vol. 45, No. 2, February 1999, pp. 253-272.
[18]P. Lawrence, Workflow Handbook 1997 (1st Edition), John Wiley & Sons, January 1997.
[19]A. Nemirovsky, “Towards Characterizing Network Processors: Needs and Challenges”, Xstream Logic, white paper.
[20]Francisco J. Ros and Pedro M. Ruiz, “Implementing a New Manet Unicast Routing Protocol in NS2”, GNU Free Documentation License, Version 1.2, Available Online at http://ants.dif.um.es/masimum/download.html, December 2004.
[21]William Stallings, High-Speed Networks and Internets: Performance and Quality of Service (2nd Edition), Prentice Hall, January 2002.
[22]H. Tangmunarunkit, R. Govindan, D. Estrin, and S. Shenker, “The Impact of Routing Policy on Internet Paths”, In Proceedings of 20th IEEE INFOCOM, April 2001, pp.736-742.
[23]Shin-Jer Yang, Chung-Kung Yen, and Yung-Cheng Chou, “Adaptive Routing Control of Workflow System on the Internet”, In Proceedings of 17th International Conference on Computers and Their Applications (CATA-2002), April 2002, pp. 354-359.
[24]W. Chung-Kung Yen, “The Bottleneck Core Problem on Weighted Graphs”, Shih Hsin University Journal, Taipei, Taiwan, 2002, pp. 281-304.
[25]“AWK Tutorial Guide”, The ASPAC（Academia Sinica PACkage）Project, Version 2.2, Available Online at http://phi.sinica.edu.tw/aspac/reports/94/94011/, December 1994.
[26]“Cygwin/X User's Guide”, GNU Free Documentation License, Version 1.1, Available Online at http://xfree86.cygwin.com/docs/ug/cygwin-x-ug.html, 2000.
[27]“Nam: Network Animator”, Information Sciences Institute, Available Online at http://www.isi.edu/nsnam/nam/index.html, Page Last Updated: July 3, 2002.
[28]“The Network Simulator - ns-2”, The VINT Project, Available Online at http://www.isi.edu/nsnam/ns/, 1995.
[29]“The ns Manual (formerly ns Notes and Documentation)”, The VINT Project, Available Online at http://www.isi.edu/nsnam/ns/ns-documentation.html, December 2003.