Functional Emulations of IP Router

[[abstract]]傳輸技術的研究使得傳輸線的頻寬持續獲得改善，但是改善的速度卻十分緩慢。同時，更大頻寬的網路需求卻快速的增加。 不幸的是，單獨只有傳輸線並無法構成一個完整的網路。若要改善整個網路的效能，必須使得其他的元件變得更快速。例如主機轉接器、作業系統、交換器、多工器及路由器。 路由器通常被視為是較為落後的技術。因此，如何使路由器的技術能跟上腳步變成為改進的方法之一。 在本論為中我們主要是在LINUX的環境之下重建LINUX核心（kernel）來完成路由器功能的模擬。 路由器功能模擬要是根據RFC1812的轉送演算法來完成路由器功能模擬，並加以測試轉送演算法以確定動作無誤。轉送演算法包含了選項（option）、標頭檢查總和（Header Checksum）、存活時間（Time to Live）、定址（Addressing）、IP廣播位址、IP標頭的確認、本地遞送決策（Local Delivery Decision）、決定下一站位址、IP目的地位址、本地/遠端決策（Local/Remote Decision）。 同時，我們亦使用以雜湊法為基礎的繞送表，其結構是由轉送資訊庫以及路徑快取所組成，並非早期路由器所使用的繞送表。 因為現今快取記憶中的替換演算法大都使用LRU替換演算法，而LRU替換演算法若遇到周期性的存取便會產生很高的為命中率，因此最後我們針對快取路由中的替換換演算法提出改進的方法，以期使快取路由的未命中率下降。 第一個方法為替換死行演算法，經過與最佳替換演算法的比較之後，我們發現一個改進的方法，就是替換快取路由中的死行可以有效的降低快取路由的未命中率。 第二個方法為遮蔽目錄，它將快取路由分成兩部分，分別為主目錄與遮蔽目錄，當某個新的項調入主目錄時，相同組內K項中的某一項從Cache中淘汰，被淘汰的那一項記入掩蔽目錄並淘汰該目錄中相應組內K行中的一項。並且將未命中的情況分為兩種，過渡未命中與掩蔽未命中，並依據這兩種狀況來管理快取路由。[[abstract]]Transmission link bandwidths keep improving, at a seemingly inexorable rate, as the result of research in transmission technology. Simultaneously, expanding network usage is creating an ever-increasing demand that can only be served by these higher bandwidth links. Unfortunately, transmission links alone do not make a network. To achieve an overall improvement in networking performance, other components such as host adapters, operating systems, switches, multiplexers, and routers also need to get faster. Routers have often been seen as one of the lagging technologies. One result of these improvements has been to put pressure on router technology to keep pace. In this thesis, we rebuild LINUX kernel to emulate IP router’s functions. We are according to RFC 1812 spec. to emulate IP router’s functions, and test it. Forwarding algorithm includes option, header checksum, time to live, addressing, local delivery decision, determining the next hop address, IP destination address, local/remote decision. We also use new architecture to achieve the routing table. Routing table consist of routing cache and forwarding information base. Nearly all caches in commerical production use least-recently used (LRU) policy to manage the lines in a set. One problem with the LRU replacement policy is that it does not anticipate the future well when sequential or cyclical activity is in progress. We point out two ways to obtain improvements over LRU replacement. The first way is to replace dead line in the LRU cache. The other way is to shadow directory. It consists of main directory and shadow directory. When a new item is brought into the main cache, one of K items in the same set is discarded from that cache. The discarded item is entered in the shadow directory, displacing one of K items from the corresponding set in that directory. The key to the cache’s operation is that there are two kinds of misses, transient miss and shadow miss. That information is used to control replacement