网络协议工程总结.docx

第二章 协议设计技术1.协议层次模型：（主要是描述n与n+1实体间的关系）l 实体(entity)：表示任何可以发送和接收信息的硬件或软件进程。在许多情况下，实体就是一个特定的模块。l n服务：两个(n)实体在(n)协议的控制下的通信，使(n)层能够向上一层(n+1)提供服务。这种服务就是(n)服务。 l 一个(n)实体向上一层所提供的服务由以下三部分构成： (1) (n)实体自己提供的某些功能。 (2) 从(n-1)层及其以下各层以及本地系统环境得到的服务。 (3) 通过与处在另一系统中的对等(n)实体的通信而得到的服务。 l PDU通常由2部分构成：用户数据和协议控制信息PCI(Protocol Control Information)。PCI一般作为首部加在用户数据的前面，但有时也可作为尾部加在用户数据的后面，例如检验和(checksum)常放在尾部。 两种类型：数据PDU 控制PDU，不携带用户数据。 在不同的协议层次中，PDU还有一些其它的表示法。 物理层：比特(bit)； 数据链路层：帧(frame)或信元(cell)；网络层 ：分组或包(packet) 运输层 ：报文(Message)l SDU:OSI将层与层之间交换的数据的单元称为服务数据单元SDU(Service Data Unit)。 一个(n)服务数据单元就是(n)服务所要传送的逻辑数据单元。 SDU就是数据PDU中的用户数据，但不一定是一一对应关系。 可以是多个SDU合成为一个PDU(称为“拼装”)，也可以是将一个SDU划分为几个PDU(称为“分段”)。 PDU的装配与拆装: 在发送数据之前，(n)协议需要装配PDU，即按照给定格式附上协议控制信息PCI。对于接收后的PDU要对之拆装，拆出PCI。 l SAP:同一系统中相邻两层的实体进行交互(即交换信息)之处，通常称为服务访问点SAP (Serivce Access Point) l SP（服务原语）：在进行交互时所要交换的一些必须信息(或命令)称为服务原语(Service Primitives)，以表明需要本地的或远端的对等实体做哪些事情。每层均可使用的4 种服务原语：（P17） Request (请求): 一个实体希望得到某种服务 Indication (指示)：把关于某一事件的信息告诉某一实体 Response (响应)：一个实体愿意响应某一事件 Confirm (证实)：把一个实体的服务请求加以确认并告诉它 过程描述： ：用户A先发出Request原语，以调用服务提供者的某个进程 To ：Request原语就引起系统A的(n)实体向某对等实体发出一个协议数据单元PDU ：当系统B的(n)实体收到这个PDU后，就向其服务用户发出Indication原语 To ：通常对应于： (1)表示系统B的(n)服务用户应当调用一个适当的协议过程，或者(2)表示服务提供者已经调用了一个必要的过程。 ：接着，服务用户B发出Response原语，用以完成刚才Indication原语所调用的过程 To ：这时，协议又产生一个协议数据单元PDU，通过网络到达系统A。 ：最后，系统A的(n)实体发出Confirm原语，表示完成了先前由服务用户A发出的Request原语所调用的过程。 2.连接于非连接：l 面向连接的(connection-oriented) 服务 三个阶段：连接建立、数据传输和连接释放 在传送数据时是按序传送的 网络层：虚电路服务 比较适合于在一定期间内要向同一目的地发送许多报文的情况 永久虚电路：适于两个用户需要经常进行频繁的通信的情况 l 无连接的(connectionless)服务 不能保证报文的丢失、重复、失序 三种类型：数据报(datagram)、证实交付(confirmed delivery, 可靠的数据报)、请求回答(request-reply) 数据报：不需要接收端做任何响应。尽最大努力交会(best effort delivery) 证实交付：又称“可靠的数据报”。对每一个报文产生一个证实给发方用户，不过这个证实不是来自接收端的用户而是来自提供服务的层 请求回答：收端用户每收到一个报文，就向发端用户发送一个应答报文。适于“事务(transaction)”中的通信。 适于传送少量零星的报文3.通道：(基于三种通道的FSM模型)l 主要有三类： 空通道(empty channels) 报文的发送时间和延时时间为0的通道 报文一旦从输入端进入就立即在输出端出现 非缓冲通道(non-buffered channels) 在任何时刻，最多只有一个正在传送中的报文的通道 缓冲通道(buffered channels) 允许有多个报文停留的通道l 形成方式和队列性质（次要）（p12）4.几种控制：l 差错控制 主要概念 在网络上进行通信会造成数据PDU以一定的概率被损坏、丢失、重复和乱序。协议的差错控制功能负责这些差错的检测及恢复，保证数据的可靠传输。 n层协议的差错控制机制与它的服务提供者提供的(n-1)通道的性质有很大关系，(n-1)通道提供的数据通道的可靠性越高，则n层协议需实现的差错控制机制则越少。 主要技术有：（检错重传或丢弃、纠错） 确认 (Ack) 计时器 (Timer) 重传 (Retransmit) 序号 (Sequence Number) 差错控制的层次关系 从通信和信息处理的角度看，物理层、数据链路层、网络层和运输层属于面向通信部分，因而网络中的绝大部分差错控制功能要在这几层中实现。 处于不同层次的协议所采用的差错控制机制是有差别的。l 流量控制流量控制是指“收端控制发端的发送数据速率以使收端来得及接收，并且使网络不致过载” Why? 接收方的接收能力有限 缓存不够 处理能力不够 Examples: Stop and Wait Sliding window l 拥塞控制 在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏。这种情况就叫做拥塞(congestion)。 资源(resources)： 链路容量 交换结点中的缓冲区（buffer） 处理机 拥塞控制的主要功能 防止网络因过载而引起吞吐量下降和迟延增加 避免死锁 在互相竞争的各用户之间公平地分配资源 第三章 形式化描述技术1.FSM：l 定义FSM = (S, s0, I, d, F), where S = s0, s1, , sn: 有限状态集合。在任一确定时刻，FSM只能处于一个确定的状态si。 I = a0, a1, , am: 有限输入字符集合。在任一确定的时刻，FSM只能接收一个确定的输入aj。 d ：S I S是状态转换函数，如果在某一确定的时刻，FSM处于某一状态si S, 并接收一个输入字符aj I，那么下一时刻将处于一个确定的状态 s = d(si , aj) S。在这里规定，s = d(s , e)，即对任何状态s，当读入空字符e时，有限状态机不发生任何状态转移。 s0 S是初始状态，FSM由此状态开始接收输入 F S是一个终态集（可空），FSM到达终态后不再接收输入l 实例一：开关 l 实例二：电话IDLEDIALINGRINGINGPATHACTIVEOn-hook-IDLE-IDLEOff-hookSend Dial Tone,DIALING-PATH ACTIVE-Dial-digit(Note 1)-DIALING PATH ACTIVE-Call-AlertRing Phone,RINGING/2.PETRI NET:l 概念Petri网可定义为一个4元组 (P, T , I, O)，其中： P = p1, p2, pn是位置(places)的有限集合； T = t1, t2, tm是变迁(transitions)的有限集合，且T与P不相交，即TP = 。 I是输入函数，是变迁T到位置的映射。对于每一个tkT，可得出相应的I(tk)=pi, pj,。 O是输出函数，也是一种变迁T到位置的映射。对于每一个tkT，可以得出相应的 O(tj)=pr, ps,。 M = m1, m2, mn是标记(tokens, “旗标”或“托肯”)的集合l 变迁类型l 例子：l 例子二（行为性质与结构性质见p58）第四章 形式描述语言（三选二）1.SDL:l 系统描述（p84）SYSTEM sample; SIGNAL S1, S2, S3, S4, S5; CHANNEL C1 FROM ENV TO B1 WITH S1, S2; ENDCHANNEL C1; CHANNEL C2 FROM B1 TO B2 WITH S3; ENDCHANNEL C2; CHANNEL C3 FROM B2 TO B1 WITH S4; ENDCHANNEL C3; CHANNEL C4 FROM B2 TO ENV WITH S5; ENDCHANNEL C4; BLOCK B1 REFERENCED; BLOCK B2 REFERENCED;ENDSYSTEM sample;(b) 用SDL/PR表示的系统例子l 功能块描述：（p85）BLOCK B1; SIGNAL Sa, Sb; SIGNALROUTE R1 FROM ENV TO P1 WITH S1; SIGNALROUTE R2 FROM ENV TO P2 WITH S2; SIGNALROUTE R3 FROM P1 TO ENV WITH S3; SIGNALROUTE R4 FROM ENV TO P2 WITH S4; SIGNALROUTE R5 FROM P1 TO P2 WITH Sa; FROM P2 TO P1 WITH Sb; CONNECT C1 AND R1, R2; CONNECT C2 AND R3; CONNECT C3 AND R4; PROCESS P1 REFERENCED; PROCESS P2 REFERENCED;ENDBLOCK B1;(b) 用SDL/PR表示的功能块例子l 进程描述：（p87）l 宏定义2.ESTELLE:l 注意点： 类别为systemprocess的模块的子模块的类别可以是process或activity；而类别为systemactivity的模块的子模块的类别必须是activity。 类别为process的模块的子模块的类别必须是process；同样，类别为activity的模块的子模块的类别必须是activity。 l 两种并行方式： 异步并行(asynchronous parallelism)。异步并行性只能存在于不同系统模块之间 同步并行(synchronous parallelism)。同步并行性只能存在于一个系统模块内。l 例子一：模块嵌套举例l 例子二：滑动窗口协议l 交互点的位置，可以将IP分为两种： 内部交互点，如p19,p20, p21,UX,UY 外部交互点(external IP)。其余的都为外部交互点l 优先级： 如果一个系统模块的类型为systemprocess，则该系统模块内的各个子模块可以并行执行，而父模块则优先于子模块执行。 如果一个系统模块的类型为systemactivity，则该系统模块内的各个子模块只能串行运行，具体哪个子模块执行则是随机选择的，父模块仍然优先于子模块执行。 3.LOTOS（传说不会考） 在LOTOS中，信息系统或系统都是从整体上体现信息活动的。例如信息的传输、加工、存储等操作都是系统的信息活动。 而系统则由一组互相交互的部分(Part)所组成。在Part中发出的信息活动称为动作(Action)。涉及到两个或多个Part的共同动作则称为交互。 为了说明一个系统，LOTOS采用了进程、事件和事件门(gate)等概念。 进程被当作一个黑盒子，我们只关心它的外显行为。 事件则是发生于进程之间的交互原语的实例，是由相关进程共同执行的。 事件门就是交互点，通信双方利用事件门互相传递事件值。 LOTOS规定了一组进程的重写规则。进程间交互时发生的事件会使一个进程被重写为另外一个进程。系统状态与事件的关系为树形结构：树结点表示状态，树的边表示在某状态下可能发生的事件。 进程间的交互是全同步的: 所谓全同步是指只有在互相交互的各个进程都处于就绪状态下，一个事件才有可能发生。 事件是原子的，即不能再细分为子事件的。各事件在时间上是互不重叠的。 Part与进程都可以逐步细分。 第五章 验证技术1.一般性质和特殊性质： 一般性质（着重理解：可达性、没有死锁、没有活锁） 特殊性质2.可达性搜索法（三选一）l 穷尽性可达性分析算法(exhaustive or full search)start() W = 初始状态; /* 工作集：分析的状态 */ A = ; /* 已分析过的状态 */ analyze(); analyze() /* 全局搜索 */ if (W为空) return; q = 取自W的元素； 将q加入到A中 if (q是错误状态) report_error(); /* 报告错误 */ else for (q的每一个后继状态s) if (s不在A或W中) 把s加入到W中；analyze(); 从W中删除q； 优点：验证覆盖范围全面，可以证明协议中没有错误。 缺点： 算法能分析的最大状态数目依赖于协议、描述方法和可用的计算资源。特别是当系统状态的数目非常大时会发生状态空间爆炸，应用范围有限。 当状态空间大于存储空间时，全搜索策略将变成部分搜索，且不能保证检查协议中最重要的部分，而搜索质量变得更差。 对于复杂的协议，穷尽性可达性分析的效果只能算作是一种低质量的部分搜索。 l 受控部分搜索算法(controlled partial search)/* start()与算法5.1中的相同 */analyze() /* 部分搜索 */ if (W为空) return; q = 取自W的元素； 将q加入到A中 if (q是错误状态) report_error(); /* 报告错误 */ else for (q的某些后继状态s) if (s不在A或W中) 把s加入到W中；analyze(); 从W中删除q； 受控部分搜索算法的目的是证明错误的存在，而不是证明没有错误。 优点：与穷尽性可达性分析相比，这种算法可以有效地解决状态空间爆炸问题，同时利用有限的资源来验证协议的最重要的部分，从而最大限度地发现错误。 缺点：必须能够预先判断出协议中的错误的大概位置，然而这很难预先做到；虽然这些方法能够减小状态空间的大小，但它们都没有提供任何工具，将状态空间的大小与可用内存相匹配。 使用这些方法时，有效搜索的部分状态空间的大小是协议相关的，只能通过实验确定，要想找到一种最优的方法，必须按照不同的选择策略进行多次验证。l 随机模拟算法(random simulation)。 analyze() /* 随机模拟 */ q = 初始状态; while (1) if (q = 错误状态) report_error(); q = 初始状态; else q = q的一个后继状态； 优点：随机模拟算法与协议系统的大小和复杂性无关，即使是无限大小的系统，也可以应用。因此，对于复杂的验证问题，这种算法也许是唯一可用的方法。 缺点： 它没有明确的终止，无法判断是否已经访问过系统的所有可达状态； 由于没有算法的终止，也就无法判断是否已经发现了系统的所有错误 因此只能发现协议中的错误，而不能证明协议中没有错误。 第七章 一致性测试技术(需要看ppt p33，掌握9个图+相应的描述)l 9个图n 图一：一致性测试模型n 图二：本地测试法(Local Mehtod) 在这种方法中，LT，UT，IUT同处于一台机器中，测试不需要低层通信系统的支持。 由于UT和LT可以在同一个程序中实现，因此，UT和LT的测试协同过程TCP(Test Coordinate Procedure)比较容易实现。 测试例用UT执行的服务原语和LT执行的服务原语来描述。在这里，LT相当于低层服务提供者。 n 图三：分布式测试法(Distributed Method) 在这种方法中，IUT和UT处于同一台机器中，而LT则分布在其它机器中。 LT和IUT之间利用(n-1)层服务交换报文(可以在线测试)。 与本地方法相比，LT和IUT之间的接口PCO从IUT中转换到LT中，LT相当于(n-1)层服务的使用者 测试协同过程TCP隐含在测试例中，测试同步问题由UT和LT的操作者来实现。 适用于本地方法的测试例必须改写后才能用于分布式测试法。 n 图四：协调测试法(Coordination Mehtod) 协同测试法和分布式测试法的根本区别在于协同测试法引入测试管理协议TMP(Test Management Protocol)。 有了TMP，UT和LT就通过交换TM-PDU实现测试协同过程。交换TM-PDU有两种方法： 带内传送法，即将TM-PDU作为(n)ASP的用户数据传送给IUT，IUT再将它传送给LT； 带外传送法，即将TM-PDU直接利用(n-1)层服务来传送。图 (c)所示的是带内传送法。 同样，分布式测试法的测试例不能用于协同测试法。 n 图五：远程测试法(Remote Method) 这种测试方法中没有UT，因此也不存在UT和LT之间的协同问题。 在这种方法中，测试例完全用(n-1)ASP描述。 远程方法比较适用于被动式协议实现或服务型协议实体的测试。 n 图六、七：渡船测试法(Ferry Method)（重点之中的重点，综合性较强） 将UT从被测系统中移到LT 所在系统中，从而可将UT和LT合在一个程序中实现，因而有本地测试法的优点。 在被测试系统中需要一个代替UT的软件，即渡船软件。UT发送给IUT的(n)ASP和UT从IUT获取的(n)ASP通过这个渡船软件进行。 与协同测试法一样，根据UT和渡船软件之间交换F-PDU方法的不同，渡船测试法又可分为带内传送法 (图 (a)和带外传送法(图 (b) 。 在带内传送法中，UT将测试事件通过LT，再通过IUT传送给渡船软件。 带外传送法中，UT通过(n-1)层服务直接传送给渡船软件。 最大优点是：由于UT和LT处于同一台机器中，测试协同过程像本地方法一样容易实现，被测试系统中只要增加简单的渡船软件即可。 只是协同测试法的一种变种，是协同测试法在实现技术上的一种改进，它们之间没有本质区别。n 图八、图九：中继系统测试法 和远程测试法一样，中继系统