Abstract
錯繞法使在內接網路裡的訊息繞離其目的以疏導擁塞, 避免可能形成的死 結, 以及曾進網路流通量。在大部份狀況裡, 錯繞法是比最短路徑繞徑法 更具有威力, 尤其在不均勻的流量下。但是為了充分發揮錯繞法的優點, 我們必須避免死結, 活結, 以及挨餓和在各種網路疏入分佈保持網路效 應. 死結及活結在最近的幾篇論文中有討論. 挨餓及保持網路效應卻未完 善的討論。現有的技術或解決方法也過於複雜且不有效, 不完備。在本論 文裡, 我們提出一新的方法來解決這些問題, 它叫水龍頭繞徑法, 它藉由 控制交通來達成此一目的。這方法不僅有效, 而且簡單--僅需兩條線以傳 遞負載訊息於兩個相鄰的繞徑器中。為了顯示水龍繞徑法的好處, 我們將 描述如何應用水龍頭繞徑法於兩個一般的模型上。我們會推導出避免在此 二模型產生死結的條件。每個模型均有其特有的特性, 以及應用水龍頭繞 徑法所產生的優點將會被展示。我們的實驗結果顯示, 使用水龍頭繞徑法 後, 網路在各種不同的輸入下仍然維持它的最高效應。與自願錯繞法做比 較, 水龍頭繞徑法可以達到曾進 50%的網路流量效應, 卻不會對網路延遲 有所影響, 這是一個很重要的結果。 Misrouting deroutes messages away from their destinations in an interconnection network to bypass congested region, avoid possible deadlock, and improve network throughput. In most cases, misrouting is substantially more powerful than shortest- path routing, especially under non-uniform load distribution. However, to take the full advantages of misrouting, we have to avoid deadlock, livelock, and starvation problems in the network and to maintain the network performance across all levels of network loading. The starvation and performance degradation problems are not fully exploited and existing approaches tend to be complex, ineffective, and insufficient. In this thesis, we propose a new routing scheme for misrouting, called valved routing, which solves the performance degrada- tion and starvation problems by controlling the traffic entering into and flowing around in the network. The scheme is very pow- erful but is very simple - only two handshaking lines are needed to exchange loading information between neighboring routers. To illustrate the benefits of valved routing, we describe how to adopt valved routing in two different general router models. We will derive the conditions to avoid deadlock in these two router models. Each model has its own charateristics, and its benefits of adopting valved routing will be demonstrated. Our simulation results show that, through valved routing, the net- work will operate near its maximum throughput at all loading levels. Compared with the voluntary misrouting, valved routing can achieve a performance improvement of more than 50% in net- work throughput without sacrificing the latency, which is a very significant result.