Abstract
Link failure是一種嚴重的網路錯誤的情況，偵測link failure以及找出哪一條link發生錯誤是一件很重要的事。我們可以在網路上放置多個所謂的「detector」，透過讓detector週期性的traceroute到某些固定的節點，藉以比對經過路徑的方式來偵測link failure。為了減少放置detector的成本，必須盡量減少detector的數目。在我們之前所做的研究中，提出了一個可以在static routing環境下找出放置detector位置的方法，利用這個方法所找出的detector數目也相當接近最佳化下的最少數目。但在dynamic routing環境下這個方法有些不適用的地方。不適用的情形在於：當從detector到目的地有兩條以上的路徑時，traceroute會選擇其中之一的路徑傳送封包，如果選擇的路徑改變了，依照我們之前的方法，會被視為另一條路徑上發生了link failure。但事實上也許link是正常的，或是的確發生了link failure，無法僅僅依此就判定發生link failure。在這篇論文中，我們提出了在dynamic routing的環境下正確運作的方法，我們也分析了在各種不同的圖形下detector數目的多寡，並且提出合理的解釋。