协议栈算法操作系统

‘壹’ 操作系统进程调度算法模拟

第一部分： 实时调度算法介绍

对于什么是实时系统，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位扩展环境版本。