臺灣博碩士論文加值系統

自從1990年代，網際網路盛行開始，人們對於網際網路的依賴不斷加深。越來越多的服務可透過網際網路獲得，同時越來越多的活動轉移到網際網路上進行。人們透過網際網路從事工作、購物和娛樂，網際網路已與現代人們的生活密不可分。一旦網際網路無法獲得，已如同沒有電力、車輛或電話一般，將造成人們生活極大的不方便。對於企業而言，網際網路更是不可或缺的工具，企業透過網際網路服務客戶並且獲得收益。每一分鐘無法透過網際網路提供服務都代表著客戶、收益跟競爭力的流失。網際網路的高可用性因此顯得特別重要。
本論文將專注在網際網路的繞徑問題上討論其高可用性，並且主要涵蓋繞徑路徑(routing path)與目的地(routing destination)備援兩個方向。首先，在繞徑路徑的備援部份，我們提出一個基於k-connected graph與flooding algorithm的多點傳播(multicast)方法，以達成高度可靠的網際網路多點傳播。其次，在繞徑目的地的備援部份，我們提出一個基於WRS的任一群播(anycast)方法，同時擁有負載平衡之特性，以多目的地的備援方式達到高可用性的網際網路傳播。
網際網路上的任一群播，在本質上具備有容錯及負載平衡之特性，因此被廣泛的討論與研究。但是其在定義及實現方法上的不明確性，使得任一群播尚無法廣泛的被應用。因此本篇論文，根據IPv6 extension header的規範，定義出Type 3的routing extension header以為任一群播所使用。我們同時揭露了多種具有前瞻性的任一群播的繞徑方式。

Internet has become popular since 90s’. From that time, people relay more and more on Internet. A vast amount services are provided on Internet. People work on Internet, shop on Internet, and entertain on Internet. Internet has deeply and completely integrated into people’s daily lives. The unavailability of Internet will make people inconveniently just as the unavailability of electric force, telephone, or vehicle. From the view of corporations, the unavailability of Internet will lead to their Internet service become inaccessible. Every minute of service down time can mean lost of customer, revenue, and productivity.
High availability of Internet can be considered and achieved in many aspects. This dissertation will focus on the routing issues of IP networks. Two major dimensions of redundancy will be covered: (1) Redundancy of routing path. (2) Redundancy of routing destination. A reliable multicast scheme based on the flooding algorithm and the k-connected graph is proposed to achieve Internet high availability by way of having redundant routing paths. Besides, a load-balanced anycast routing scheme based on the WRS method is presented to achieve Internet high availability by way of having redundant routing destinations.
Anycast is naturally fault-tolerant and load-balanced. However, the definition and behavior of anycasting are not clear enough until now. To realize anycast, we design the type 3 routing extension header for IPv6 anycasting. A number of new possible anycast routing models are explored too.

CHAPTER 1 INTRODUCTION 1
1.1 HIGH AVAILABILITY 1
1.2 COMMUNICATION TYPES OF IP NETWORKS 3
1.3 RELATED TERMINOLOGY 3
1.4 DISSERTATION OUTLINE 4
CHAPTER 2 RELIABLE MULTICAST BASED ON k-CONNECTED GRAPH 6
2.1 OVERVIEW 7
2.2 MULTICAST ROUTING ALGORITHMS 9
2.3 PROBLEMS OF MULTICAST TREE 11
2.4 K-CONNECTED GRAPH 14
2.4.1 Connectivity 14
2.4.2 Minimum k-Connected Graph Augmentation Problem 16
2.4.3 Applying Graph Augmentation Algorithm to Multicast 17
2.4.4 Characteristics of Minimum k-Connected Graph 18
2.5 FLOODING ON K-CONNECTED GRAPH 19
2.6 ANALYSIS AND COMPARISONS 23
2.7 SUMMARY 27
CHAPTER 3 LOAD-BALANCED ANYCAST WITH MINIMAL AVERAGE DELAY 28
3.1 OVERVIEW 30
3.2 RELATED WORK AND BACKGROUND 31
3.2.1 Related Work 31
3.2.2 Background 32
3.3 PROBLEM MODEL AND MATHEMATICAL DERIVATIONS 34
3.3.1 Problem Model 34
3.3.2 Mathematical Derivations 35
3.4 LOAD-BALANCED ANYCAST ROUTING SCHEME 37
3.4.1 Routing Table Establishment Stage 37
3.4.2 Outgoing Interface Selection Stage 40
3.4.3 Weight Calculation Algorithm 42
3.4.4 Remarks 44
3.5 EVALUATIONS AND ANALYSIS 47
3.6 SUMMARY 49
CHAPTER 4 EXTENSION HEADERS FOR IPv6 ANYCAST 52
4.1 OVERVIEW 53
4.2 SURVEY AND ANALYSIS 55
4.3 DESIGN OF ANYCAST ROUTING HEADERS 57
4.3.1 Format of anycast routing header 58
4.3.2 Routing header for multiple destination routing method 60
4.3.3 Routing header for favorite-list routing method 62
4.3.4 Routing header for decision-deferred routing method 67
4.3.5 Extensibility of anycast routing header 69
4.4 SCENARIOS 70
4.4.1 Scenarios for the multiple destination routing header 70
4.4.2 Scenarios for the favorit-list routing header 71
4.4.3 Scenario for the decision-deferred routing header 72
4.5 SUMMARY 72
CHAPTER 5 CONCLUDING REMARKS 74
5.1 RESEARCH CONTRIBUTIONS 74
5.1.1 Reliable Multicast Based on k-Connected Graph 74
5.1.2 Load-Balanced Anycast Routing 75
5.1.3 Extension Headers for IPv6 Anycast 75
5.2 FUTURE WORKS 76
BIBLIOGRSPHY 78
PUBLICATION LIST 82

[1]Barry W. Johnson, Design and Analysis of Fault-Tolerant Digital Systems, Addison-Wesley, 1989.
[2]Martin L. Shooman, Reliability of Computer Systems and Networks: Fault Tolerance, Analysis, and Design, Wiley, 2002.
[3]Bala Rajagopalan, Reliability and Scaling Issues in Multicast Communication, In Proc. of the Annual ACM SIGCOMM Symposium on Communication Architectures and Protocols, Baltimore, MD, pages 188-197, August 1992.
[4]C. Huitema, Routing in the Internet, second edition, Prentice-Hall, 1999.
[5]B. N. Levine and J. J. Garcia-Luna-Aceves, A Comparison of Reliable Multicast Protocols, ACM Multimedia Systems, August 1998.
[6]S. Paul, K. Sabnani, J. Lin, and S. Bhattacharyya, Reliable multicast transport protocol (rmtp), IEEE Journal on Selected Areas in Communications, 15(3): 407-421, April 1997.
[7]Weijia Jia, W Zhao, D Xuan, and G Xu, An Efficient Fault-Tolerant Multicast Routing Protocol with Core-Based Tree Techniques, IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 10, pp. 984-999, October 1999.
[8]Robin J. Wilson and John J. Watkins, Graphs: An Introductory Approach, Wiley, 1990.
[9]K. P. Eswaran and R. E. Tarjan, Augmentation Problems, SIAM Journal on Computing, 5, pp. 653-665, 1976.
[10]T. Watanabe and A. Nakamura, Edge-Connectivity Augmentation Problems, Journal of Computer and System Sciences, 35(1), pp. 96-144, 1987.
[11]T.-s. Hsu, Graph Augmentation and Related Problems: Theory and Practice, PhD thesis, Department of Computer Sciences, University of Texas at Austin, October 1993.
[12]K. Birman and T. Joseph, Reliable Communication in the Presence of Failures, ACM Transactions on Computer System, Vol. 5, No. 1, pp. 47-76, February 1987.
[13]C. Partridge, T. Mendez, and W. Milliken, Host Anycasting Service, IETF RFC 1546, November 1993.
[14]E. Zegura, M. Ammar, Z. Fei, and S. Bhattacharjee, Application-Layer Anycasting: A Server Selection Architecture and Use in a Replicated Web Service, ACM/IEEE Transactions on Networking, 8(4): 455-466, 2000.
[15]H. Miura, and M. Yamamoto, Server Selection Policy in Active Anycast, IEICE Transactions on Communications, Vol. E84-B. No. 10, October 2001.
[16]D. Xuan, W. Jia, W. Zhao, and H. Zhu, A Routing Protocol for Anycast Messages, IEEE Transactions on Parallel and Distributed Systems, Volume: 11 Issue: 6, Jun 2000.
[17]W.T. Zaumen, S. Vutukury, and J.J. Garcia-Luna-Aceve, Load-Balanced Anycast Routing in Computer Networks, Proceedings Fifth IEEE Symposium on Computers and Communications (ISCC 2000), July 2000.
[18]S. Yu, W. Zhou, and Y. Wu, Research on Network Anycast, Proceedings of the Fifth International Conference on Algorithms and Architectures for Parallel Processing, 2002.
[19]Andrew S. Tanenbaum, Computer Networks, third edition, Prentice-Hall, 1996.
[20]J. Moy, OSPF Version 2, IETF RFC 1247, July 1991.
[21]Donald Gross, and Carl M. Harris, Fundamentals of Queueing Theory, third edition, Wiley-Interscience, 1998.
[22]Sheldon M. Ross, Introduction to Probability Models, 7th edition, San Diego: Harcourt/Academic Press, 2000.
[23]M. S. Bazaraa and C. M. Shetty, Nonlinear Programming: Theory and Algorithm, John Wiley & Sons, 1993.
[24]S. Deering and R. Hinden, Internet Protocol, Version 6 (IPv6) Specification, IETF RFC 2460, December 1998.
[25]D. Johnson and S. Deering, Reserved IPv6 Subnet Anycast Addresses, IETF RFC 2526, March 1999.
[26]R. Hinden and S. Deering, Internet Protocol, Version 6 (IPv6) Specification, IETF RFC 3513, April 2003.
[27]D. Johnson, C. Perkins, and J. Arkko, Mobility Support in IPv6, IETF RFC 3775, June 2004.
[28]S. Weber and L. Cheng, A Survey of Anycast in IPv6 Networks, IEEE Communications Magazine, Vol. 42, Issue 1, pp. 127-132, January 2004.
[29]C. Metz, IP Anycast Point-to-(Any) Point Communication, IEEE Internet Computing, Vol. 6, Issue 2, pp. 94-98, March-April 2002.
[30]S. Ata, H. Kitamura, and M. Murata, Applicability Statement of IPv6 Anycasting, draft-ata-ipv6-anycast-app-00.txt, October 2004.
[31]D. Katabi and J. Wroclawski, A Framework for Scalable Global IP-Anycast (GIA), Proceedings of ACM SIGCOMM, August 2000.
[32]I. Stoica, D. Adkins, S. Zhung, S. Shenker, and S. Surana, Internet Indirection Infrastructure, IEEE/ACM Transactions on Netwoking, Vol. 12, Issue 2, pp. 205-218, April 2004.
[33]V. Ponnusamy, E.K. Karuppiah, and R. Abdullah, Anycast Group Membership Management Protocol, The 9th Asia-Pacific Conference on Communications (APCC 2003), Vol. 3, pp. 1052-1056, September 2003.
[34]C. Y. Lin, J. H. Lo, and S. Y. Kuo, Load-Balanced Anycast Routing, Proceedings of Tenth International Conference on Parallel and Distributed Systems (ICPADS 2004), July 2004.
[35]F. Hao, E. W. Zegura, and M. H. Ammar, QoS Routing for Anycast Communications: Motivation and an Architecture for DiffServ Networks, IEEE Communication Magazine, Vol. 40, Issue 6, June 2002.
[36]Zhang Li, Weijia Jia, Yan Wei, and Li Xiao-Ming, An Efficient Anycast Routing Protocol Based on Multi-Metrics, Proceedings of 7th International Symposium on Parallel Architectures, Algorithms and Networks, May 2004.
[37]G. Agarwal, R. Shah, and J. Walrand, Content Distribution Architecture Using Network Layer Anycast, Proceedings of the Second IEEE Workshop on Internet Applications (WIAPP 2001), July 2001.
[38]D. Katabi, The Use of IP-Anycast for Building Efficient Multicast Trees, Global Telecommunications Conference (GLOBECOM ’99), Vol. 3, 1999.
[39]K. M. Hanna, N. Natarajan, B. N. Levine, Evaluation of a novel two-step server selection metric, Ninth International Conference on Network Protocols, November 2001.
[40]J. Reynolds, Assigned Numbers: RFC 1700 is Replaced by an On-line Database, IETF RFC 3232, January 2002.
[41]S. Thomson, and T. Narten, IPv6 Stateless Address Autoconfiguration, IETF RFC 2462, December 1998.
[42]M. Yamamoto, H. Miura, K. Nishimura, and H. Ikeda, A Network Supported Server Load Balancing Method: Active Anycast, IEICE Transactions on Communications, Special Issue on New Development on QoS Technologies of Information Networks, Vol. E84-B, No. 6, pp. 1561-1568, June 2001.