協議棧演算法操作系統

『壹』 操作系統進程調度演算法模擬

第一部分： 實時調度演算法介紹

對於什麼是實時系統，POSIX 1003.b作了這樣的定義：指系統能夠在限定的響應時間內提供所需水平的服務。而一個由Donald Gillies提出的更加為大家接受的定義是：一個實時系統是指計算的正確性不僅取決於程序的邏輯正確性，也取決於結果產生的時間，如果系統的時間約束條件得不到滿足，將會發生系統出錯。

實時系統根據其對於實時性要求的不同，可以分為軟實時和硬實時兩種類型。硬實時系統指系統要有確保的最壞情況下的服務時間，即對於事件的響應時間的截止期限是無論如何都必須得到滿足。比如航天中的宇宙飛船的控制等就是現實中這樣的系統。其他的所有有實時特性的系統都可以稱之為軟實時系統。如果明確地來說，軟實時系統就是那些從統計的角度來說，一個任務（在下面的論述中，我們將對任務和進程不作區分）能夠得到有確保的處理時間，到達系統的事件也能夠在截止期限到來之前得到處理，但違反截止期限並不會帶來致命的錯誤，像實時多媒體系統就是一種軟實時系統。

一個計算機系統為了提供對於實時性的支持，它的操作系統必須對於CPU和其他資源進行有效的調度和管理。在多任務實時系統中，資源的調度和管理更加復雜。本文下面將先從分類的角度對各種實時任務調度演算法進行討論，然後研究普通的 Linux操作系統的進程調度以及各種實時Linux系統為了支持實時特性對普通Linux系統所做的改進。最後分析了將Linux操作系統應用於實時領域中時所出現的一些問題，並總結了各種實時Linux是如何解決這些問題的。

1. 實時CPU調度演算法分類

各種實時操作系統的實時調度演算法可以分為如下三種類別[Wang99][Gopalan01]：基於優先順序的調度演算法（Priority-driven scheling-PD）、基於CPU使用比例的共享式的調度演算法（Share-driven scheling-SD）、以及基於時間的進程調度演算法（Time-driven scheling-TD），下面對這三種調度演算法逐一進行介紹。

1.1. 基於優先順序的調度演算法

基於優先順序的調度演算法給每個進程分配一個優先順序，在每次進程調度時，調度器總是調度那個具有最高優先順序的任務來執行。根據不同的優先順序分配方法，基於優先順序的調度演算法可以分為如下兩種類型[Krishna01][Wang99]：

靜態優先順序調度演算法：

這種調度演算法給那些系統中得到運行的所有進程都靜態地分配一個優先順序。靜態優先順序的分配可以根據應用的屬性來進行，比如任務的周期，用戶優先順序，或者其它的預先確定的策略。RM（Rate-Monotonic）調度演算法是一種典型的靜態優先順序調度演算法，它根據任務的執行周期的長短來決定調度優先順序，那些具有小的執行周期的任務具有較高的優先順序。

動態優先順序調度演算法：

這種調度演算法根據任務的資源需求來動態地分配任務的優先順序，其目的就是在資源分配和調度時有更大的靈活性。非實時系統中就有很多這種調度演算法，比如短作業優先的調度演算法。在實時調度演算法中， EDF演算法是使用最多的一種動態優先順序調度演算法，該演算法給就緒隊列中的各個任務根據它們的截止期限（Deadline）來分配優先順序，具有最近的截止期限的任務具有最高的優先順序。

1.2. 基於比例共享調度演算法

雖然基於優先順序的調度演算法簡單而有效，但這種調度演算法提供的是一種硬實時的調度，在很多情況下並不適合使用這種調度演算法：比如象實時多媒體會議系統這樣的軟實時應用。對於這種軟實時應用，使用一種比例共享式的資源調度演算法（SD演算法）更為適合。

比例共享調度演算法指基於CPU使用比例的共享式的調度演算法，其基本思想就是按照一定的權重（比例）對一組需要調度的任務進行調度，讓它們的執行時間與它們的權重完全成正比。

我們可以通過兩種方法來實現比例共享調度演算法[Nieh01]：第一種方法是調節各個就緒進程出現在調度隊列隊首的頻率，並調度隊首的進程執行；第二種做法就是逐次調度就緒隊列中的各個進程投入運行，但根據分配的權重調節分配個每個進程的運行時間片。

比例共享調度演算法可以分為以下幾個類別：輪轉法、公平共享、公平隊列、彩票調度法（Lottery）等。

比例共享調度演算法的一個問題就是它沒有定義任何優先順序的概念；所有的任務都根據它們申請的比例共享CPU資源，當系統處於過載狀態時，所有的任務的執行都會按比例地變慢。所以為了保證系統中實時進程能夠獲得一定的CPU處理時間，一般採用一種動態調節進程權重的方法。

1.3. 基於時間的進程調度演算法

對於那些具有穩定、已知輸入的簡單系統，可以使用時間驅動（Time-driven:TD）的調度演算法，它能夠為數據處理提供很好的預測性。這種調度演算法本質上是一種設計時就確定下來的離線的靜態調度方法。在系統的設計階段，在明確系統中所有的處理情況下，對於各個任務的開始、切換、以及結束時間等就事先做出明確的安排和設計。這種調度演算法適合於那些很小的嵌入式系統、自控系統、感測器等應用環境。

這種調度演算法的優點是任務的執行有很好的可預測性，但最大的缺點是缺乏靈活性，並且會出現有任務需要被執行而CPU卻保持空閑的情況。

2. 通用Linux系統中的CPU調度

通用Linux系統支持實時和非實時兩種進程，實時進程相對於普通進程具有絕對的優先順序。對應地，實時進程採用SCHED_FIFO或者SCHED_RR調度策略，普通的進程採用SCHED_OTHER調度策略。

在調度演算法的實現上，Linux中的每個任務有四個與調度相關的參數，它們是rt_priority、policy、priority（nice）、counter。調度程序根據這四個參數進行進程調度。

在SCHED_OTHER 調度策略中，調度器總是選擇那個priority+counter值最大的進程來調度執行。從邏輯上分析，SCHED_OTHER調度策略存在著調度周期（epoch），在每一個調度周期中，一個進程的priority和counter值的大小影響了當前時刻應該調度哪一個進程來執行，其中 priority是一個固定不變的值，在進程創建時就已經確定，它代表了該進程的優先順序，也代表這該進程在每一個調度周期中能夠得到的時間片的多少； counter是一個動態變化的值，它反映了一個進程在當前的調度周期中還剩下的時間片。在每一個調度周期的開始，priority的值被賦給 counter，然後每次該進程被調度執行時，counter值都減少。當counter值為零時，該進程用完自己在本調度周期中的時間片，不再參與本調度周期的進程調度。當所有進程的時間片都用完時，一個調度周期結束，然後周而復始。另外可以看出Linux系統中的調度周期不是靜態的，它是一個動態變化的量，比如處於可運行狀態的進程的多少和它們priority值都可以影響一個epoch的長短。值得注意的一點是，在2.4以上的內核中， priority被nice所取代，但二者作用類似。

可見SCHED_OTHER調度策略本質上是一種比例共享的調度策略，它的這種設計方法能夠保證進程調度時的公平性--一個低優先順序的進程在每一個epoch中也會得到自己應得的那些CPU執行時間，另外它也提供了不同進程的優先順序區分，具有高priority值的進程能夠獲得更多的執行時間。

對於實時進程來說，它們使用的是基於實時優先順序rt_priority的優先順序調度策略，但根據不同的調度策略，同一實時優先順序的進程之間的調度方法有所不同：

SCHED_FIFO：不同的進程根據靜態優先順序進行排隊，然後在同一優先順序的隊列中，誰先准備好運行就先調度誰，並且正在運行的進程不會被終止直到以下情況發生：1.被有更高優先順序的進程所強佔CPU；2.自己因為資源請求而阻塞；3.自己主動放棄CPU（調用sched_yield）；

SCHED_RR：這種調度策略跟上面的SCHED_FIFO一模一樣，除了它給每個進程分配一個時間片，時間片到了正在執行的進程就放棄執行；時間片的長度可以通過sched_rr_get_interval調用得到；

由於Linux系統本身是一個面向桌面的系統，所以將它應用於實時應用中時存在如下的一些問題：

Linux系統中的調度單位為10ms，所以它不能夠提供精確的定時；

當一個進程調用系統調用進入內核態運行時，它是不可被搶占的；

Linux內核實現中使用了大量的封中斷操作會造成中斷的丟失；

由於使用虛擬內存技術，當發生頁出錯時，需要從硬碟中讀取交換數據，但硬碟讀寫由於存儲位置的隨機性會導致隨機的讀寫時間，這在某些情況下會影響一些實時任務的截止期限；

雖然Linux進程調度也支持實時優先順序，但缺乏有效的實時任務的調度機制和調度演算法；它的網路子系統的協議處理和其它設備的中斷處理都沒有與它對應的進程的調度關聯起來，並且它們自身也沒有明確的調度機制；

3. 各種實時Linux系統

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大學（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，為了在Linux系統中提供對於硬實時的支持，它實現了一個微內核的小的實時操作系統（我們也稱之為RT-Linux的實時子系統），而將普通Linux系統作為一個該操作系統中的一個低優先順序的任務來運行。另外普通Linux系統中的任務可以通過FIFO和實時任務進行通信。RT-Linux的框架如圖 1所示：

圖 1 RT-Linux結構

RT -Linux的關鍵技術是通過軟體來模擬硬體的中斷控制器。當Linux系統要封鎖CPU的中斷時時，RT-Linux中的實時子系統會截取到這個請求，把它記錄下來，而實際上並不真正封鎖硬體中斷，這樣就避免了由於封中斷所造成的系統在一段時間沒有響應的情況，從而提高了實時性。當有硬體中斷到來時， RT-Linux截取該中斷，並判斷是否有實時子系統中的中斷常式來處理還是傳遞給普通的Linux內核進行處理。另外，普通Linux系統中的最小定時精度由系統中的實時時鍾的頻率決定，一般Linux系統將該時鍾設置為每秒來100個時鍾中斷，所以Linux系統中一般的定時精度為 10ms，即時鍾周期是10ms，而RT-Linux通過將系統的實時時鍾設置為單次觸發狀態，可以提供十幾個微秒級的調度粒度。

RT-Linux實時子系統中的任務調度可以採用RM、EDF等優先順序驅動的演算法，也可以採用其他調度演算法。

RT -Linux對於那些在重負荷下工作的專有系統來說，確實是一個不錯的選擇，但他僅僅提供了對於CPU資源的調度；並且實時系統和普通Linux系統關系不是十分密切，這樣的話，開發人員不能充分利用Linux系統中已經實現的功能，如協議棧等。所以RT-Linux適合與工業控制等實時任務功能簡單，並且有硬實時要求的環境中，但如果要應用與多媒體處理中還需要做大量的工作。

義大利的RTAI( Real-Time Application Interface )源於RT-Linux，它在設計思想上和RT-Linux完全相同。它當初設計目的是為了解決RT-Linux難於在不同Linux版本之間難於移植的問題，為此，RTAI在 Linux 上定義了一個實時硬體抽象層，實時任務通過這個抽象層提供的介面和Linux系統進行交互，這樣在給Linux內核中增加實時支持時可以盡可能少地修改 Linux的內核源代碼。

3.2. Kurt-Linux

Kurt -Linux由Kansas大學開發，它可以提供微秒級的實時精度[KurtWeb] [Srinivasan]。不同於RT-Linux單獨實現一個實時內核的做法，Kurt -Linux是在通用Linux系統的基礎上實現的，它也是第一個可以使用普通Linux系統調用的基於Linux的實時系統。

Kurt-Linux將系統分為三種狀態：正常態、實時態和混合態，在正常態時它採用普通的Linux的調度策略，在實時態只運行實時任務，在混合態實時和非實時任務都可以執行；實時態可以用於對於實時性要求比較嚴格的情況。

為了提高Linux系統的實時特性，必須提高系統所支持的時鍾精度。但如果僅僅簡單地提高時鍾頻率，會引起調度負載的增加，從而嚴重降低系統的性能。為了解決這個矛盾， Kurt-Linux採用UTIME所使用的提高Linux系統中的時鍾精度的方法[UTIMEWeb]：它將時鍾晶元設置為單次觸發狀態（One shot mode），即每次給時鍾晶元設置一個超時時間，然後到該超時事件發生時在時鍾中斷處理程序中再次根據需要給時鍾晶元設置一個超時時間。它的基本思想是一個精確的定時意味著我們需要時鍾中斷在我們需要的一個比較精確的時間發生，但並非一定需要系統時鍾頻率達到此精度。它利用CPU的時鍾計數器TSC (Time Stamp Counter)來提供精度可達CPU主頻的時間精度。

對於實時任務的調度，Kurt-Linux採用基於時間（TD）的靜態的實時CPU調度演算法。實時任務在設計階段就需要明確地說明它們實時事件要發生的時間。這種調度演算法對於那些循環執行的任務能夠取得較好的調度效果。

Kurt -Linux相對於RT-Linux的一個優點就是可以使用Linux系統自身的系統調用，它本來被設計用於提供對硬實時的支持，但由於它在實現上只是簡單的將Linux調度器用一個簡單的時間驅動的調度器所取代，所以它的實時進程的調度很容易受到其它非實時任務的影響，從而在有的情況下會發生實時任務的截止期限不能滿足的情況，所以也被稱作嚴格實時系統（Firm Real-time）。目前基於Kurt-Linux的應用有：ARTS（ATM Reference Traffic System）、多媒體播放軟體等。另外Kurt-Linux所採用的這種方法需要頻繁地對時鍾晶元進行編程設置。

3.3. RED-Linux

RED -Linux是加州大學Irvine分校開發的實時Linux系統[REDWeb][ Wang99]，它將對實時調度的支持和Linux很好地實現在同一個操作系統內核中。它同時支持三種類型的調度演算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

為了提高系統的調度粒度，RED-Linux從RT-Linux那兒借鑒了軟體模擬中斷管理器的機制，並且提高了時鍾中斷頻率。當有硬體中斷到來時，RED-Linux的中斷模擬程序僅僅是簡單地將到來的中斷放到一個隊列中進行排隊，並不執行真正的中斷處理程序。

另外為了解決Linux進程在內核態不能被搶占的問題， RED-Linux在Linux內核的很多函數中插入了搶占點原語，使得進程在內核態時，也可以在一定程度上被搶占。通過這種方法提高了內核的實時特性。

RED-Linux的設計目標就是提供一個可以支持各種調度演算法的通用的調度框架，該系統給每個任務增加了如下幾項屬性，並將它們作為進程調度的依據：

Priority：作業的優先順序；

Start-Time：作業的開始時間；

Finish-Time：作業的結束時間；

Budget：作業在運行期間所要使用的資源的多少；

通過調整這些屬性的取值及調度程序按照什麼樣的優先順序來使用這些屬性值，幾乎可以實現所有的調度演算法。這樣的話，可以將三種不同的調度演算法無縫、統一地結合到了一起。

『貳』 協議棧的簡介

協議棧（Protocol Stack）是指網路中各層協議的總和，其形象的反映了一個網路中文件傳輸的過程：由上層協議到底層協議，再由底層協議到上層協議。面對眾多不同的計算機和網路生產廠家，以及用戶要求的便宜、靈活、方便的聯網需求，必須建立一個公認的計算機網路連網標准和網路體系結構，以實現任意計算機系統和任意網路系統的互聯。
使用最廣泛的是英特網協議棧，由上到下的協議分別是： 應用層（HTTP，FTP，TFTP，TELNET，DNS，EMAIL等） 表示層（VTP） 會話層 傳輸層（TCP，UDP） 網路層（IP） 數據鏈路層（WI-FI，乙太網，令牌環，FDDI，MAC等） 物理層 將協議應用到計算機網路中，就產生了網路協議。協議是一個描述進程之間信息交換過程的一個術語。在計算機網路中，兩個相互通信的實體必在不同的物理位置，為了能在兩個實體之間進行通信，並進行所要求的處理，通信雙方必須遵守共同的通信規則。

『叄』 Thread協議棧基礎

Thread協議棧是可靠，經濟高效，低功耗，無線D2D（設備到設備）通信的開放標准。它是專為連接家庭應用而設計的，其中需要基於IP的網路，並且可以在協議棧中使用各種應用層。

這些是Thread協議棧和網路的一般特性：

圖1顯示了Thread協議棧的概述。

該標准基於在2.4GHz頻帶中以250kbps運行的IEEE 802.15.4 [IEEE802154] PHY（物理層）和MAC（媒體訪問控制層）。該規范的IEEE 802.15.4-2006版本用於Thread協議棧。

802.15.4 MAC層用於基本的消息處理和擁塞控制。該MAC層包括設備用於監聽干凈信道的CSMA（Carrier Sense Multiple Access，載波偵聽多路訪問）機制，以及用於處理重試和確認消息的鏈路層以用於相鄰設備之間的可靠通信。基於由軟體協議棧的較高層建立和配置的密鑰，被MAC層用於對消息的加密和完整性保護。網路層建立在這些基礎機制上，以在網路中提供可靠的端對端通信。

在由運行Thread協議棧的設備組成的系統中，這些設備都不代表單點故障。雖然系統中有許多設備執行特殊功能，但是Thread協議棧的設計使得它們可以被替換，而不會影響Thread網路中正在進行的通信。例如，一個常眠的子設備需要一個父設備進行通信，因此這個父設備代表它的通信失敗單點。但是，如果常眠設備的父設備不可用，常眠設備可以並將會選擇另一個父設備，因此該轉換不應該對用戶可見。

雖然系統設計用於沒有單點故障，但在某些拓撲結構下，將存在沒有備份功能的單個設備。例如，在具有單個網關的系統中，如果網關斷電，則無法切換到另一個網關。

路由器或邊界路由器可以為Thread網路中的某些功能承擔Leader角色。這個Leader需要在網路內作出決定。例如，Leader分配路由器地址並允許新的路由器請求。Leader角色是被選舉的，如果Leader失敗，會由另一個路由器或邊界路由器承擔Leader角色。正是這種自主操作確保沒有單點故障。

邊界路由器是一種特定類型的路由器，提供從802.15.4網路到其他物理層（例如，Wi-Fi和乙太網）上的相鄰網路的連接。邊界路由器為802.15.4網路中的設備提供服務，包括用於離網操作（off-network operations）的路由服務。Thread網路中可能有一個或多個邊界路由器。

路由器為網路設備提供路由服務。路由器還為嘗試加入網路的設備提供加入和安全服務。路由器是設計為不休眠的。路由器可以降級其功能並成為REED（Router-eligible End Devices，符合路由器的終端設備）。

REED有能力成為路由器，但是由於網路拓撲或條件，這些設備不作為路由器工作。這些設備通常不轉發消息或為Thread網路中的其他設備提供加入或安全服務。如果需要，Thread網路管理REED成為路由器，且無需用戶交互。

常眠終端設備是主機設備。他們只通過他們的父路由器進行通信，不能轉發其他設備的消息。

Thread協議棧中的設備支持[RFC 4291]中指定的IPv6定址架構。設備配置1個或多個ULA（Unique Local Address，唯一本地地址）或GUA（Global Unicast Address，全局單播地址）地址。

啟動網路的設備選擇一個/64前綴，然後在整個Thread網路中使用。該前綴是本地分配的全局ID（Locally Assigned Global ID），通常稱為ULA前綴[RFC 4193]，可以稱為網格本地ULA前綴（mesh local ULA prefix）。Thread網路還可以具有一個或多個邊界路由器，每個邊界路由器可以具有或可以不具有可以用於生成附加GUA的前綴。Thread網路中的設備使用其擴展MAC地址（Extended MAC address）來導出其[RFC 4944]第6節中定義的介面標識符（interface identifier），並且基於此，通過已知的本地前綴FE80 :: 0/64配置鏈路本地IPv6地址，如[RFC 4862]和[RFC 4944]所述。

設備還支持適當的多播地址（multicast addresses）。這包括鏈路本地所有節點組播（link-local all node multicast），鏈路本地全路由器組播（link-local all-router multicast）和區域本地組播（realm-local multicast）。

加入Thread網路的每個設備都將分配一個16位短地址，如[IEEE 802.15.4]中所規定。對於路由器，該地址使用地址欄位中的較高位分配，低位設置為0，表示路由器地址。然後，對於子設備使用其父設備的高位和適當的低位來為其地址分配一個16位的短地址。這允許Thread網路中的任何其他設備通過使用其地址欄位的高位來了解子設備的路由位置。

圖2說明了Thread短地址。

所有設備使用[RFC 4944]和[RFC 6282]中定義的6LoWPAN。

在Thread網路中使用頭部壓縮（Header compression），設備傳輸消息盡可能多地壓縮IPv6報頭，以最小化發送的數據包的大小。

支持網格包頭（mesh header），用於更有效地壓縮網格內的消息，以及針對如「路由和網路連接」部分中所述的鏈路層轉發（link layer forwarding）。網格標頭（mesh header）還允許消息的端到端分段（end-to-end fragmentation），而不是[RFC 4944]中指定的逐跳分段（hop by hop fragmentation）。Thread協議棧使用路由選擇配置（route-over configuration）。

這些設備不支持[RFC 6775]中規定的鄰居發現（neighbor discovery），因為DHCPv6用於向路由器分配地址。終端設備和REED由他們的路由器父節點分配短地址。然後，該短地址用於配置用於網路內通信的網格（Mesh）本地ULA。

有關6LoWPAN使用和配置的更多詳細信息，請參見「6LoWPAN的Thread用法（Thread Usage of 6LoWPAN）」白皮書。Thread規范的第3章詳細說明了使用的具體6LoWPAN配置。

設備支持ICMPv6（Internet Control Message Protocol version 6，Internet控制消息協議版本6）協議[RFC 4443]和ICMPv6錯誤消息，以及回顯請求（echo request）和回顯回復消息（echo reply messages）。

Thread協議棧支持在[RFC 768]中定義的UDP（用戶數據報協議），用於設備之間的消息傳遞。

Thread協議棧支持Thread網路中所有路由器之間的全網格連接（full mesh connectivity）。

實際拓撲基於Thread網路中路由器的數量。如果只有一個路由器或邊界路由器，則形成具有單個路由器的基本星形拓撲。如果有多個路由器，則自動形成網格（Mesh）拓撲。圖3說明了Thread網路的基本拓撲結構和設備類型。

網格網路（Mesh Networks）通過允許射頻轉發其他射頻的消息，使射頻系統更可靠。例如，如果節點不能直接向另一個節點發送消息，則網格網路（Mesh Networks）通過一個或多個中間節點轉發消息。如「路由和網路連接」一節中所討論的，Thread網路的性質使得所有路由器節點彼此之間保持路由和連接，因此網格不斷維護和連接。Thread網路中通常有最多32個活動路由器的限制。但是，64個路由器地址用於允許回收路由器地址。

在網格網路（Mesh Networks）中，常眠終端設備或REED不會為其他設備路由。這些設備將消息發送到作為路由器的父設備。該父路由器處理其子設備的路由操作。

Thread網路通常最多有32個活動路由器，它們使用基於設備路由表的消息的下一跳路由（next-hop routing）。設備路由表由協議棧維護，以確保所有路由器都具有Thread網路中任何其他路由器的連接和最新路徑。使用RIP（Routing Information Protocol，路由信息協議）演算法（來自[RFC 1058]和[RFC 2080]的演算法，但不採用其特定的消息格式）。所有路由器與其他路由器使用MLE（Mesh Link Establishment），以壓縮格式交換其到Thread網路中的其他路由器的路由成本（cost of routing）。

注意：從IP的角度來看，Thread網路支持路由器和主機。主機是常眠終端設備或REED。

MLE消息（請參閱「Thread規范」第4章「消息鏈路建立（Message Link Establishment）」 中針對Thread進行的擴展[draft-kelsey-intarea-mesh-link-establishment-06]) 用於建立和配置安全射頻鏈路，檢測鄰近設備，以及維護Thread網路中設備之間的路由成本。使用單跳鏈路本地單播（single-hop link local unicasts）和路由器之間多播（multicasts between Routers）來傳輸MLE消息。

隨著拓撲和物理環境的變化，MLE消息用於識別，配置和保護鄰近設備的鏈路。MLE還用於分發跨Thread網路共享的配置值，如通道（channel）和PAN（Personal Area Network，個人區域網路）ID。這些消息可以由MPL（Multicast Protocol for Low power and Lossy Networks，低功耗和有損網路的多播協議）指定的簡單洪泛轉發（forwarded with simple flooding）。（有關詳細信息，請參閱[draft-ietf-roll-trickle-mcast-09]）。

在建立兩個設備之間的路由成本時，MLE消息還確保考慮了非對稱鏈路成本（asymmetric link costs）。802.15.4網路中的非對稱鏈路成本（asymmetric link costs）很常見。為了確保雙向通信是可靠的，考慮雙向鏈路的成本是很重要的。

按需路由發現（On-demand route discovery）通常用於低功耗802.15.4網路。然而，由於路由發現請求洪泛網路（route discovery requests flooding the network），按需路由發現（on-demand route discovery）在網路開銷和帶寬方面是昂貴的。

在Thread網路中，所有路由器定期交換包含到所有鄰居路由器鏈路成本信息（link cost information to all neighbor Routers）的單跳MLE廣告包（single-hop MLE advertisement packets），以及到Thread網路中所有其他路由器的路徑開銷（path costs to all other Routers）。通過這些定期的本地更新，所有路由器都具有Thread網路中任何其他路由器的最新路徑開銷信息，因此不需要按需路由發現。如果路由不再可用，路由器可以在到達目的地的下一個最合適的路由上進行選擇。這種自愈路由機制允許路由器快速檢測其他路由器是否已經脫離Thread網路，並計算最佳路徑以維護與Thread網路中所有其他設備的連接。

每個方向的鏈路質量（link quality in each direction）基於來自該鄰近設備的傳入消息的鏈路成本（link cost on incoming messages from that neighboring device）。此傳入鏈路成本（incoming link cost）映射到從0到3的鏈路質量（link quality）。值為0表示未知成本。鏈路成本（link cost is a measure of RSSI）是接收到的消息高於接收等級的RSSI（接收信號強度指示）的度量。

表1總結了鏈路質量和鏈路成本。

圖4示出了Thread網路上的各種鏈路成本的示例。

Thread網路中任何其他節點的路徑開銷就是到達該節點的鏈路成本的最小值。路由器監控這些成本，即使網路的射頻鏈路質量或拓撲變化，並通過使用周期性MLE廣告消息在Thread網路傳播新的成本。路由成本基於兩個設備之間的雙向鏈路質量。

為了說明一個簡化的例子，想像一下預先委託的網路（pre-commissioned network），其中共享安全材料，所有的設備同時啟動。每個路由器將周期性地發送初始填充的到單跳鄰居成本的廣告。在內部，每個路由器將存儲未在廣告中發送的下一跳信息（next hop information）。

前幾個廣告的路徑成本等於鏈路成本，因為已知的唯一路由器是立即鄰居，如圖5所示。

但是，隨著路由器開始收聽來自鄰居的廣告，其中包含兩跳或更多跳的其他路由器的成本，它們的表填充了多跳路徑成本，然後傳播得更遠，直到最終在所有路由器之間存在如圖6和圖7所示的連接信息網路。

當路由器從鄰居接收到新的MLE廣告時，它或者已經具有該設備的鄰居表項，或者添加一個。MLE廣告包含來自鄰居的進入成本（incoming cost from the neighbor），因此在路由器的鄰居表中更新（updated in the Router』s neighbor table）。MLE廣告還包含其他路由器的更新的路由信息​​（updated routing information for other Routers），並且該信息在設備路由表中更新（updated in the device routing table）。

通過查看子設備的地址的高位來確定父路由器地址（Parent Router address），可以實現到子設備的路由。一旦設備知道父路由器，它就具有該設備的路徑開銷信息和下一跳路由信息（path cost information and next-hop routing information）。

活動路由器的數量僅限於可以包含在單個802.15.4數據包中的路由和成本信息的數量。此限制目前為32個路由器，但提供了64個活動路由器地址以允許老化掉路由器地址（aging out of Router addresses）。

設備使用IP路由轉發數據包（IP routing to forward packets）。設備路由表（device routing table）填充有路由器的網格本地ULA地址的壓縮形式和適當的下一跳（compressed form of a mesh local ULA address for Routers and the appropriate next hop）。

距離向量路由（Distance vector routing）用於獲取到Thread網路上路由器地址的路由（get routes to Router addresses）。當在Thread網路上進行路由時，該16位地址的高6位定義了目標路由器的路由器地址。如果目的地址的低位為0，則路由器為最終目的地址。否則，目的路由器負責根據16位目的地址的較低位轉發到最終目的地。

對於超出Thread網路的路由，邊界路由器通知Leader其所服務的特定前綴（particular prefix(es) it serves），並且該信息作為MLE數據包中的Thread網路數據分發（distributed as Thread Network data within the MLE packets）。Thread網路數據包括：前綴數據（prefix data），它是前綴本身，6LoWPAN上下文（6LoWPAN context），邊界路由器（Border Routers）和該前綴的DHCPv6伺服器（DHCPv6 server for that prefix）。如果設備要使用該前綴配置IPv6地址，則使用SLAAC（Stateless Address Autoconfiguration，無狀態地址自動配置）或聯系相應的DHCP（Dynamic Host Configuration Protocol，動態主機配置協議）伺服器。Thread網路數據還包括路由伺服器列表（a list of routing servers），它們是默認的邊界路由器的路由器地址。

Leader被指定做出決策，選擇REED成為路由器或允許路由器降級為REED。Leader也分配和管理路由器地址。然而，此路由Leader中包含的所有信息都存在於其他路由器中，並且如果路由Leader變得無法訪問，則另一個路由器將自主被選擇並作為Leader接管，而無需用戶干預。

雖然在Thread協議棧中使用UDP消息傳遞，但仍然需要可靠的消息傳遞。這是使用一系列輕量級機制完成的，如下所示：

加入設備（joining device）必須經歷各個階段才能參與Thread網路：

所有加入都是Thread網路中用戶啟動的。一旦加入，設備就可以完全參與Thread網路，並可以與Thread網路內外的其他設備和服務交換應用層信息。

加入設備（joining device）必須發現Thread網路，並與路由器建立聯系（establish contact with a Router）以進行調試（commissioning）。加入設備掃描所有信道（scans all channels），在每個信道上發出信標請求（issues a beacon request），並等待信標響應（waits for beacon responses）。信標包含一個有效載荷，包括網路SSID（Service Set Identifier，服務集標識符）和允許加入信標的許可證（a permit joining beacon），指示Thread網路是否正在接受新的成員。一旦設備發現Thread網路，它將使用MLE消息來建立一個相鄰的路由器（establish a neighboring Router），通過它可以執行調試（perform commissioning）。

如果設備已經獲得了調試信息（obtained commissioning information），因為它已經有足夠的信息直接附加到Thread網路，則不需要發現。

Thread提供兩種調試方法：

注意：僅在通過信標有效載荷中的許可證加入標志（joining solely via the permit joining flag in the beacon payload）的典型802.15.4加入方法不在Thread網路中使用。這種方法最常用於沒有用戶界面或到設備的帶外頻道的按鈕類型加入（push button type joining）。在有多個網路可用的情況下，該方法可能存在設備轉向（device steering）問題，並且也可能存在安全問題。

具有調試信息（commissioning information）的加入設備（joining device）與父路由器聯系，然後通過父路由器交換MLE鏈路配置消息（exchanging MLE link configuration messages）附加到Thread網路。設備作為終端設備（end device）或REED附加到Thread網路，並由父路由器分配16位短地址，如圖8所示。

一旦REED已經附加到Thread網路，它可能會發出一個地址請求（issue an address request）成為一個路由器，然後由Leader分配一個路由器地址。

一旦設備連接到Thread網路，就需要有各種各樣的信息來保持其在網路中的參與。MLE提供服務以在整個網路中分發網路數據，並在鄰居之間交換鏈路成本（link costs）和安全幀計數器（security frame counters）。

MLE消息分發或交換以下信息：

注意 ：MLE消息是被加密的，除非是在發現時，加入設備獲得所需的安全資料過程中。

DHCPv6 [RFC 3315]是一種基於UDP的客戶端 - 伺服器協議，用於管理網路中設備的配置。DHCPv6使用UDP從DHCP伺服器請求數據。

邊界路由器上的DHCPv6服務用於配置：

所有設備都支持ICMPv6錯誤消息，以及回顯請求（ echo request）和回顯回應消息（ echo reply messages）。

設備上的應用層可以訪問一組設備管理和診斷信息，這些信息可以在本地使用或收集並發送到其他管理設備。

Thread協議棧從802.15.4 MAC層使用的信息包括：

Thread協議棧從網路層使用的信息包括：

由於各種原因，在現場操作的設備可能會意外重置或故障重置。已重置的設備需要重新啟動網路操作，無需用戶干預。為此，需要將一組信息存儲在非易失性存儲中。這包括：

『肆』 TCP/IP協議棧與操作系統的關系

ARP(AddressResolutionProtocol)地址解析協議它是用於映射計算SNMP(SimpleNetworkManagementP)網路管理協議它是TCP/IP協議中的一部份，它為本地和遠端的網路設備管理提供了一個標准化途徑，是分布式環境中的集中化管理的重要組成部份。AppleShareprotocol(AppleShare協議)它是Apple機上的通信協議，它允許計算機從伺服器上請求服務或者和伺服器交換文件AppleTalk協議它是Macintosh計算機使用的主要網路協議。WindowsNT伺服器有專門為Macintosh服務，也能支持該協議。BGP4(BorderGatewayProtocolVertion4)邊界網關協議-版本4它是用於在自治網路中網關主機(每個主機有自己的路由)之間交換路由信息的協議BOOTP協議它是一個基於TCP/IP協議的協議，它可以讓無盤站從一個中心伺服器上獲得IP地址，現在我們通常使用DHCP協議進行這一工作。CMIP()通用管理信息協議它是建立在開放系統互連通信模式上的網路管理協議。相關的通用管理信息服務(CMIS)定義了訪問和控制網路對象，設備和從對象設備接收狀態信息的方法Connection-orientedProtocol/ConnectionlessProtocol面向連接的協議/無連接協議在廣域網中，兩台計算機建立物理連接過程所使用的協議，這種物理連接要持續到成功地交換完數據為止。DHCP()動態主機配置協議它是在TCP/IP網路上使客戶機獲得配置信息的協議，它是基於BOOTP協議，並在BOOTP協議的基礎上添加了自動分配可用網路地址等功能。FTP(FileTransferProtocol)文件傳輸協議HDLC(High-LevelDataLinkControl)高層數據鏈路協議HTTP1.1(.1)超文本傳輸協議-版本1.1HTTPS()安全超文本傳輸協議ICMP()Internet控制信息協議IMAP4()Internet郵件訪問協議-版本4NNTP(NetworkNewsTransferProtocol)網路新聞傳輸協議IOTP(InternetOpenTradingProtocol)Internet開放貿易協議IPv6(InternetProtocolVersion6)Internet協議-版本6IPX/SPX(InternetworkPacketExchange/SequentialPacketExchange)互連網包交換/順序包交換MIME(Multi-PurposeInternetMailExtensions)多功能Internet郵件擴展NetBEUI(NetBIOSEnhancedUserInterface)網路基本輸入輸出系統擴展用戶介面POP3(PostOfficeProtocolVersion3)郵局協議-版本3PPP(PointtoPointProtocol)點對點協議RIP(RoutingInfomationProtocol)路由信息協議SLIP(SerialLineInternetProtocol)串列線路Internet協議LMTP(LocalMailTransferProtocol)本地郵件傳輸協議SMTP(SimpleMailTransferProtocol)簡單郵件傳送協議TCP/IP(TransmissionControlProtocol/InternetProtocol)傳輸控制協議/Internet協議TELNETProtocol虛擬終端協議TimeProtocol時間協議TFTP(TrivialFileTransferProtocol)小文件傳輸協議UDP(UserDatagramProtocol)用戶數據報協議這個回答你滿意了吧，具體解釋請參照這里．

『伍』 單片機TCP/IP的已有的單片機TCP/IP協議棧

由於TCP協議棧的程序流程較為復雜，因為程序中需要處理對方發送過來的數據、發起的連接，而我方並不知道對方會何時進行什麼樣的操作，這就使得協議處理起來較為復雜。另外一個原因是單片機TCP/IP協議棧的穩定性是以非常重要的問題，一個穩定的協議棧需要在實際應用中經過長時間的測試，所以編寫一個穩定的單片機TCP/IP協議棧更加困難。為此另外一種選擇就是使用現有的TCP/IP協議棧。
1． eCos單片機TCP/IP協議棧：eCos TCP/IP棧是涉及與eCos操作系統/內核一起運行的。eCos（和TCP/IP棧）由大量處理其結構支持。eCos TCP/IP棧當前發布了一個測試版，作為一個單獨的模塊。
2． ZLIP 51單片機TCP/IP協議棧：ZLIP是專門為51單片機設計的嵌入式TCP/IP協議棧，可以在有操作系統和沒有操作系統情況下運行，具有代碼量適中、運行速度快、用戶介面簡單、兼容BSD socket介面的特點。實現了TCP、UDP、ICMP、ARP協議，ZLWeb實現了HTTP協議。支持多TCP連接、多UDP連接同時運行，支持在uc/os-II操作系統下多任務運行數據收發。可以用於51單片機TCP/IP上網解決方案。
3． uc/ip 單片機TCP/IP協議棧:uC/IP(mew-kip)是為為控制其設計的一個TCP/IP協議棧。代碼基於BSD（很像所有其它棧）但對非常小的覆蓋范圍功能有所減少。它當前為Linux和DOS目標而建。
4． BSD 單片機TCP/IP協議棧：BSD棧歷史上是其他商業棧的開始點，大多數專業TCP/IP棧（如帶Wind-River VxWorks內核的）是BSD棧派生的。這是因為BSD在BSD許可協議下提供了他們的棧，它們的許用證使你能以修改或未修改的形式結合它們的代碼而無須向創建者付版稅。與GPL許用證相比，如果你結合GPL源代碼，後者要求你的GPL中公開你的源代碼。
5． lwIP 單片機TCP/IP協議棧：lwIP（輕型）TCP/IP棧是TCP/IP協議棧的一個小型實現。它包括帶IP和ICMP的TCP和UDP傳輸層。還提供一個可選的BSD套結籽API。為了性能，還包括一個零拷貝API。LwIP協議棧是為嵌入式系統設計的並能適合40KB的ROM和幾百位元組的RAM。為了可移植性它用C編寫。
6． uIP 單片機TCP/IP協議棧：uIP是專門為8位和16單片機設計的一個非常小的TCP/IP協議棧。uIP完全用C編寫，以此可以移植到各種不同的結構和操作系統上。一個編譯的棧可以有幾KB ROM或幾百位元組RAM中運行。uIP還包括一個HTTP伺服器作為服務內容。
7． TinyTCP 單片機TCP/IP協議棧：TinyTCP棧是TCP/IP的一個非常小的簡單的實現，它包括一個FTP客戶。TinyTCP是為燒入ROM設計的並且現在開始對大端結構似乎是有用的（初始目標是68000晶元）。TinyTCP也包括一個簡單的乙太網驅動器用於3Com多匯流排卡。
8． WATTCP 單片機TCP/IP協議棧：WATTCP是為嵌入基於DOS的系統而設計的一個小型TCP/IP棧。它包括一個Real Mode DOS版本和另一個32位擴展環境版本。