• 作者： 邱光輝; 陳文村; 許丕榮
• 作者服務機構： 資訊工業策進會; 國立清華大學資學研究所
• 中文摘要： 本文探討分封交換計算機網路各個結點間連線具有不同之計價單位時的路由問題，網路結點間連線的計價單位可能為一個資料傳輸框中的分封數或連線的傳輸容量。本文探討的路由問題為：給一資料源結點及一資料目地的結點，找出從此源結點至目地的結點的最低成本的路徑。本文證明此問題為NP- hard。並提出一branch-and-bound的計算方法以求最佳解。另根據虛線路及資料信封觀念，分別提出兩個啟發式的計算方法。我們做了一些實驗以證明此兩啟發式的計算方法的有效性。
• 英文摘要： In this paper, we consider the routing problem in packet-switched computer networks in which acharge unit is associated with every link. The charge unit may be the number of packets within a dataframe, the capacity of a communication link, and so on. The routing problem is to find a route to sendmessages from a source node to a destination node with minimal cost, In this paper, we prove that thisproblem is NP-hard. To find the optimal solution, a branch-and-bound algorithm is proposed. Also, twoheuristic algorithms are suggested. One is based on the virtual circuit concept and the other is based on thedatagram concept. Experimental results clearly show that our proposed heuristic algorithms are quiteeffective.
• 中文關鍵字： branch-and-bound algorithm; computer network; heuristic algorithm; NP-hard; routing problem
• 英文關鍵字： --