网络协议工程总结

1、衿 For pers onal use only in study and research; not for commercial use羂第二章协议设计技术芁1协议层次模型：(主要是描述n与n+1实体间的关系)(H + 1)层(n+1)实体(n+1)实体(n)SPs(n)SPs 盲(M实体世X (n)实体 * (nPDUs；(nd)SPsnSAPnSAP(n-l)Sh :(n-l)SAP提做Ibl)服务：(n-1)SAP ；(n r 1)层通过mi)连接进彳亍通信(n)服务提供者蚁 芆 莆 蚂 聿 艿 莆 肃 螁肇蒆蒄 艿 袇薅实体(entity):表示任何可以发送和接收信息的硬件或软件进

2、程。在许多情况下，实体就是一个特定的模块。蚆n服务：两个(n)实体在(n)协议的控制下的通信，使(n)层能够向上一层(n+1)提供服务。 这种服务就是(n)服务。羁一个(n)实体向上一层所提供的服务由以下三部分构成：(1)(2) 莈(n)实体自己提供的某些功能。(3)(3) 蚈从(n-1)层及其以下各层以及本地系统环境得到的服务。(5)(6)螆通过与处在另一系统中的对等(n)实体的通信而得到的服务。莂 PDU 通常由 2 部分构成：用户数据和协议控制信息 PCI(Protocol Control Information) 。膀PCI般作为首部加在用户数据的前面，但有时也可作为尾部加在用户数据的

3、后面， 例如检验和(checksum)常放在尾部。莇两种类型：袆数据 PDU螃控制PDU,不携带用户数据。薈在不同的协议层次中，PDU还有一些其它的表示法。膆物理层：比特 (bit)；羅数据链路层：帧 (frame) 或信元 (cell)；袀 网络层 ：分组或包 (packet)芀 运输层 ：报文 (Message)羅SDUQSI将层与层之间交换的数据的单元称为服务数据单元SDU(Service Data Un it)。羅一个(n)服务数据单元就是(n)服务所要传送的逻辑数据单元。芁SDU就是数据PDU中的用户数据，但不一定是一一对应关系。螈可以是多个SDU合成为一个PDU(称为拼装”)也可以

4、是将一个 SDU划 分为几个PDU(称为分段”。羈PDU的装配与拆装：在发送数据之前，(n)协议需要装配 PDU,即按照给定格式附上协议控制信息PC。对于接收后的 PDU要对之拆装，拆出PC。芅pciD拓蚂SAP:同一系统中相邻两层的实体进行交互（即交换信息）之处，通常称为服务访问点SAP（Serivce Access Point）蒀SP（服务原语）：在进行交互时所要交换的一些必须信息（或命令）称为服务原语（ServicePrimitives），以表明需要本地的或远端的对等实体做哪些事情。螇每层均可使用的4种服务原语：（P17）膅Request （请求）:一个实体希望得到某种服务肃Indica

5、tion （指示）：把关于某一事件的信息告诉某一实体羈Response响应）：一个实体愿意响应某一事件 薆Confirm （证实）：把一个实体的服务请求加以确认并告诉它系统八蒄过程描述：虿：用户A先发出Request原语，以调用服务提供者的某个进程蕿To：Request原语就引起系统 A的(n)实体向某对等实体发出一个协议数据 单元PDU莅：当系统B的(n)实体收到这个PDU后，就向其服务用户发出In dication原语蚀To ：通常对应于:莁(1)表示系统B的(n)服务用户应当调用一个适当的协议过程，或者莇(2)表示服务提供者已经调用了一个必要的过程。蒅：接着，服务用户B发出Respo n

6、se原语，用以完成刚才In dication 原语所调用的过程肁To：这时，协议又产生一个协议数据单元PDU通过网络到达系统 A。衿：最后，系统 A的(n)实体发出Confirm原语，表示完成了先前由服务用户A发出的Request原语所调用的过程。薅2.连接于非连接:蒂面向连接的(connection-oriented)服务薁三个阶段：连接建立、数据传输和连接释放 袅在传送数据时是按序传送的薄网络层：虚电路服务袃比较适合于在一定期间内要向同一目的地发送许多报文的情况罿永久虚电路：适于两个用户需要经常进行频繁的通信的情况袈无连接的(connectionless服务蚄不能保证报文的丢失、重复、失序

7、羀三种类型：数据报(datagram)、证实交付(confirmed delivery,可靠的数据报)、 请求回答(request-reply)?蚁数据报：不需要接收端做任何响应。尽最大努力交会(best effort delivery)?蚇证实交付：又称“可靠的数据报”。对每一个报文产生一个证实给发方用户，不过这个证实不是来自接收端的用户而是来自提供服务的层?螄请求回答：收端用户每收到一个报文，就向发端用户发送一个应答报文。适于“事务(transaction)中的通信。莁适于传送少量零星的报文腿蒆3.通道：(基于三种通道的FSM模型)袄主要有三类：螂空通道(empty channels)?袁

8、报文的发送时间和延时时间为0的通道?葿报文一旦从输入端进入就立即在输出端出现羄非缓冲通道(non-buffered channels)?膃在任何时刻，最多只有一个正在传送中的报文的通道莈缓冲通道(buffered channels)?芈允许有多个报文停留的通道肄形成方式和队列性质（次要）（p12）薃肀4.几种控制:羆差错控制膄主要概念?螀在网络上进行通信会造成数据PDU以一定的概率被损坏、丢失、重复和乱序。协议的差错控制功能负责这些差错的检测及恢复，保 证数据的可靠传输。?蒈n层协议的差错控制机制与它的服务提供者提供的（n-1）通道的性质有很大关系，（n-1）通道提供的数据通道的可靠性越高，则

9、n层协议需实现的差错控制机制则越少。螅主要技术有：（检错重传或丢弃、纠错）? 膄确认（Ack）? 賺计时器（Timer）?芀重传（Retransmit）?螈序号（Sequenee Number）芃差错控制的层次关系?薂从通信和信息处理的角度看，物理层、数据链路层、网络层和运输 层属于面向通信部分，因而网络中的绝大部分差错控制功能要在这 几层中实现。?蚈处于不同层次的协议所采用的差错控制机制是有差别的。薇流量控制莃流量控制是指“收端控制发端的发送数据速率以使收端来得及接收，并且使网络不致过载”羃 Why?莀接收方的接收能力有限莆缓存不够蒃处理能力不够莄 Examples:?袈 Stop and

10、Wait? 荿 Slidi ng wi ndow薃拥塞控制蒁在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部 分，网络的性能就要变坏。这种情况就叫做拥塞(congestion)。薀资源(resources):?膈链路容量?蚃交换结点中的缓冲区(buffer)?袂处理机芁拥塞控制的主要功能?羆防止网络因过载而引起吞吐量下降和迟延增加?蚃避免死锁?节在互相竞争的各用户之间公平地分配资源蝿蚅第三章形式化描述技术螃 1.FSM蚃定义蒁 FSM = (S, sO, I,、; F), where螈 S = sO, s1, 定的状态si。待限状态集合。在任一确定时刻，FSM只能处于一个确FS

11、M只能接收袃I = aO, a1,有限输入字符集合。在任一确定的时刻,一个确定的输入aj。初：S IS是状态转换函数，如果在某一确定的时刻，FSM处于某一状态si S,并接收一个输入字符 aj I，那么下一时刻将处于一个确定的状态s'=;.（si, aj） S。在这里规定，s =；.（s ,；）,即对任何状态s,当读入空字符；时，有限状态机不发生任何状态转移。衿sO - S是初始状态，FSM由此状态开始接收输入蒇F S是一个终态集（可空），FSM到达终态后不再接收输入羂实例一：开关莆switch off/ stay quietswitch off/ make click sound蚁s

12、tate eventOnOffSwitch onclick, onSwitch offclick, off-芆实例二：电话蚂聿艿 IDLE莆 DIALING肃RINGING螁PATHACTIVE肇 On-hook蒆-蒄 IDLE艿-袇 IDLE薆 Off-hook薁 Send Dial Tone, DIALING羀-薅 PATHACTIVE蚆-羁Dial-digit(Note1)莈-蚈 DIALING PATHACTIVE螆-莂-膀 Call-Alert莇 Ring Pho ne,RINGING祎/螃/薈/膆 2.PETRI NET:羅概念Petri网可定义为一个 4元组(P T , I, 0

13、),其中:袀 P = p1, p2,是位置(places)的有限集合；芀 T = t1, t2,=一。是变迁(transitions)的有限集合，且 T与P不相交，即TA P羅1是输入函数，I(tk)=pi, pj,。是变迁T到位置的映射。对于每一个tk T,可得出相应的羅O是输出函数，也是一种变迁 T到位置的映射。对于每一个tk T,可以得出相应的 0(tj)=pr, ps,。芁M = ml, m2,m标记（tokens,旗标'"或 托肯”的集合螈变迁类型斗顺序变迁。如图所示。只有当-点火后$才能点火。 却并发变迁，如图（b）所示.耳和®！同时（当然也可以单独）点

14、 火*斗互斥变迁#如图所示口 q和$中只能有一个点火。一个点 火后另一个就不能再点火了°蒀CHB变迁6Pi位置的名称变迁名称肅例子:标记。每个 位置中有。个或多个标I记/=(2,0,0,0,0)螇p" = <0, 2, 2, 2,0) 鸟开始具备点火条件膅蒄例子二(行为性质与结构性质见p58)(a)无界、不活、不可逆(b)无界、不活、可逆(e)无界、活性、可逆(d)有界、不活、不可逆(h)有界、活性、可逆(g)有界、活性、不可逆虿蕿第四章 形式描述语言(三选二)莅 1.SDL:蚀系统描述(p84)SYSTEM sample1(1)SIGNAL SHS2,S3,S4,S

15、5;|C】S1,S2|UlC2S3C3 S414C4 S5(a)用SDL/GR表小的系统例子SYSTEMsample;莇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 RE

16、FERENCED;袃BLOCK B2 REFERENCED;罿 ENDSYSTEM sample;袈(b)用SDL/PR表示的系统例子羀功能块描述：(p85)肀C2C3(a)用SDL/GR表示的功能块例子蚇 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

17、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 P1REFERENCED;芈PROCESS P2REFERENCED;肄 ENDBLOCK B1;薃(b)用SDL/PF表示的功能块例子羆 膄 螀 蒈螅膄賺芀螈芃进程描述：(p87)薂蚈PROCESS P1(1,10);DCL num Natural;START;TASK num :=0;NEXTSTATE State_A;STATE State_A;INPUT S1

18、;NEXTSTATE State_B;SAVE Sa;ENDSTATE;STATE State_B:INPUT Sa;DECISION num;(0:9):TASK num := num+1; NEXTSTATE State_B; (=10):OUTPUT S3;STOP;ELSEOUTPUT Sb;STOP;ENDDECISION;ENDSTATE;ENDPROCESS; 用SDL/G表示的进程例子(b) 用SDL/PF表示的进程例子蚁蒁薀膈蚃袂-+- 芁羆蚃节蚅宏定义螃DD蒇s2CCSTATE s1;INPUT Inp;DECISION x>1; (FALSE) : JOIN BB;

19、 (TRUE): TASK x:=0;JOIN AA;ENDDECISION;MACRO m(x+y, AA, BB, CC, DD); CC: NEXTSTATE s2;DD: NEXTSTATE -;(c) SDL/GF芁表示的宏定义调用例子(d) SDL/PR表示的宏定义调用例子芆莆蚂聿MACRODEFINITION mFPAR e.a(TRU E)e > 1">(FALSE)MACRODEFINITION m FPAR e a. b. cn d: a： DECISION e>1 (TRUE) JOIN b: (FALSE) : JOIN c: ENDDECI

20、SION;b: TASK x := y.JOIN d;ENDMACRO m(a) SDUGR 上小的世進乂例j(b) SDUPR盘示的宅定又蒆 2.ESTELLE:冠注意点：艿类别为systemprocess的模块的子模块的类别可以是process或activity ;而类别为systemactivity的模块的子模块的类别必须是activity。袇类别为process的模块的子模块的类别必须是process；同样，类别为activity的模块的子模块的类别必须是activity。薆两种并行方式:薁异步并行(asynchronous parallelism)。异步并行性只能存在于不同系统模块

21、之间羀同步并行(synchronous parallelism)。同步并行性只能存在于一个系统模块内。薅例子一：模块嵌套举例S(specification IPlp!6A( system pintx沾)A1 (process)B(syslcinactivily)右卩kl (activity)A2(aciivit>)pl211 net h itv)-v fp8pig p20A22| acdv itv)p21“pl IA3( process)帀tJ-Th?-Pl?B2( activity)P22羁例子二：滑动窗口协议螆祎螃薈膆羅袀芀羅羅-+-芁螈羈肅交互点的位置，可以将IP分为两种：蚂内部交

22、互点，女口 p19,p20, p21,UX,UY袀外部交互点(external IP)。其余的都为外部交互点腿优先级：薅如果一个系统模块的类型为systemprocess，则该系统模块内的各个子模块可以并行执行，而父模块则优先于子模块执行。蒃如果一个系统模块的类型为systemactivity，则该系统模块内的各个子模块只能串行运行，具体哪个子模块执行则是随机选择的，父模块仍然优先于子模块执行。莈祎3.LOTOS(传说不会考)type BasicBooleans is$ort$ boolopns T# F : -> boolnot : -> bool->baoleqns of

23、 sort boolnot(T) = F;riotF) = T;endty petype Booleans Is BaskBooleans op ins and: bool, bool -> bool r : boat baol -> bool eqn& of sort boolT and T =T;T and F - F;Fand T-F;F and F =F;T or T = T; Tor F =T; F or T = T; For F = F;enrltype袄在LOTOS中，信息系统或系统都是从整体上体现信息活动的。例如信息的 传输、加工、存储等操作都是系统的信息活

24、动。肀而系统则由一组互相交互的部分(Part)所组成。在Part中发出的信息活动称为动作(Action)。涉及到两个或多个 Part的共同动作则称为交互。罿为了说明一个系统，LOTOS采用了进程、事件和事件门(gate)等概念。螅进程被当作一个黑盒子，我们只关心它的外显行为。肁事件则是发生于进程之间的交互原语的实例，是由相关进程共同执行的。螂事件门就是交互点，通信双方利用事件门互相传递事件值。螈LOTOS规定了一组进程的重写规则。进程间交互时发生的事件会使一个进 程被重写为另外一个进程。系统状态与事件的关系为树形结构：树结点表示状态，树的边表示在某状态下可能发生的事件。袅进程间的交互是全同步的

25、：蒂所谓全同步是指只有在互相交互的各个进程都处于就绪状态下，一个事 件才有可能发生。腿事件是原子的，即不能再细分为子事件的。各事件在时间上是互不重叠 的。蒇Part与进程都可以逐步细分。袂第五章验证技术羁1.一般性质和特殊性质：芅一般性质(着重理解：可达性、没有死锁、没有活锁) 羅特殊性质芃2.可达性搜索法(三选一)荿穷尽性可达性分析算法 (exhaustive or full search)芈 start()肅 W = 初始状态; /*工作集：分析的状态*/莀 A = ； /*已分析过的状态*/肁an alyze();肇膅analyze() /*全局搜索*/螁蕿if (W 为空)return

26、;祎q =取自W的元素；芄将q加入到A中膂if (q是错误状态)report_error(); /*报告错误 */芁else 衿for (q的每一个后继状态 s)莄if (s不在A或W中)把s加入到 W中；analyze();螀蚈 从W中删除q；蒄羄优点：验证覆盖范围 全面，可以证明协议中没有错误。蒁缺点：?莇算法能分析的最大状态数目依赖于协议、描述方法和可用的计算资源。特别是当系统状态的数目非常大时会发生状态空间爆炸，应用范围有限。?蒄当状态空间大于存储空间时，全搜索策略将 变成部分搜索，且不能保证检查协议中最重要的部分，而搜索 质量变得更差。?賺对于复杂的协议，穷尽性可达性分析的效果只能算

27、作是一种低质量 的部分搜索。袈受控部分搜索算法(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 ；袃螄受控部分搜索算法的目的是证明错误的存在，而不是证明没有错误。芈优点： 与穷尽性可达性分析相比，这种算法可以有效地解决状态空间爆炸问题

28、，同时利用有限的资源来验证协议的最重要的部分， 从而 最大限度 地发 现错误。蝿缺点 ：必须能够预先判断出协议中的错误的大概位置 ，然而这很难预先做到；虽然这些方法能够减小状态空间的大小，但它们都 没有提供任何工具 将状态空间的大小与可用内存相匹配。羃使用这些方法时，有效搜索的部分状态空间的大小是协议相关的，只能通 过实验确定， 要想找到一种最优的方法， 必须按照不同的选择策略进行多次 验证。袁随机模拟算法 (random simulation) 。羀 analyze() /* 随机模拟 */薈 q = 初始状态 ;肃 while (1) 节 if (q = 错误状态 )蚂 report_er

29、ror();芇 q = 初始状态 ;肃 else q = q 的一个后继状态；蚃膀优点： 随机模拟算法与协议系统的大小 和复杂性无关 ，即使是无限大小的 系统，也可以应用。因此，对于复杂的验证问题，这种算法也许是 唯一可用 的方法。肆缺点：?膃它没有明确的终止，无法判断是否已经访问过系统的 所有可达状态；?肄由于没有算法的终止，也就无法判断是否已经发现了系统的所有错误?袁因此只能发现协议中的错误，而不能证明协议中没有错误。芃第七章一致性测试技术(需要看ppt p33，掌握9个图+相应的描述)膀9个图UT(Upper Tester)是上测试器(上层 测试软件或硬件)0 是对IUT的上服务 边界进

30、行控制和观 匕所提供的手塁丿I ri*( oTCP被测'51: *1(n-l>ASP«1对象J(n-l)Ser ice ProviderUTt(n)ASP*PCOIUTPCO(n-i)ASP是下测试器(下层 测试软件或硬件h 是在测试执行期 间，为了经下层 JK务提供者而对1JT的下服务边界 进行间接控制和察所提供的手丿 段.薁图二：本地测试法(LocalMehtod)羁在这种方法中，LT，UT，IUT 同处于一台机器中，测试不需要低层通信系统 的支持。蚆由于UT和LT可以在同一个 程序中实现，因此，UT和LT的测试协同过程 TCP(Test Coordi nate P

31、rocedure)比较容易实现。蚇测试例用UT执行的服务原语和LT执行的服务原语来描述。在这里，LT艿图一：一致性测试模型LT何本地测试法相当于低层服务提供者。葿 虿 螇 蒃 賺 蒈 祎 袄 虿 芇莁羆图三：分布式测试法(Distributed Method)肆莂蝿聿膆螃在这种方法中，IUT和UT(b)分布测试法处于同一台机器中，而 LT则分布在其它机器中。薀LT和IUT之间利用(n-1)层服务交换报文(可以在线测试)。螈与本地方法相比，LT和IUT之间的接口 PCO从IUT中转换到LT中，LT相当 于(n-1)层服务的使用者芆测试协同过程 TCP隐含在测试例中，测试同步问题由 UT和LT的操

32、作者来 实现。膃适用于本地方法的测试例必须改写后才能用于分布式测试法。羈莅图四：协调测试法 (Coordi nation Mehtod)TM-PDU直接利用(n-1)层服务来传送。图(c)协同测试法所示的是带内传送法。祎LT 4蚅(n)PDU碣* 占 i- * * i* -fa i *IUTPCO(n-l)ASPf(n-l)W务提供者蒃图五：远程测试法(Remote Method)莈袀同样，分布式测试法的测试例不能用于协同测试法。袄这种测试方法中没有UT,因此也不存在 UT和LT之间的协同问 题。肀在这种方法中，测试例 完全用(n-1)ASP描述。罿远程方法比较适用于 被动式协议实现或服务型协

33、议实体的测试。(c)远程测试法蒇图六、七：渡船测试法(Ferry Method)(重点之中的重点，综合性较强)袅LT芅将.(n)PDU啪蝌TUT(n系)®务提供者r 1 JLTIUT(n)PDU pcop*IUT(n-l)ASP(nJ)服务提供者膅渡訓测试岛悄内传送)到LT(b)渡船测试法(带外传送)羅所在系统中，从而可将UT和LT合在一个程序中实现，因而有本地测试法的优点。芃在被测试系统中需要一个代替UT的软件，即渡船软件。UT发送给IUT的(n)ASP和UT从IUT获取的(n)ASP通过这个渡船软件进行。荿与协同测试法一样，根据UT和渡船软件之间交换 F-PDU方法的不同，渡船测

34、试法又可分为带内传送法(图(a)和带外传送法(图(b)。芈在带内传送法中，UT将测试事件通过 LT,再通过IUT传送给渡船软件。肅带外传送法中，UT通过(n-1)层服务直接传送给渡船软件。莀最大优点是：由于UT和LT处于同一台机器中，测试协同过程像本地方法 一样容易实现，被测试系统中只要增加简单的渡船软件即可。肁只是协同测试法的一种变种，是协同测试法在实现技术上的一种改进，它们之间没有本质区别。肇图八、图九：中继系统测试法(SI)闭环测试法(b)橫断测试法螁和远程测试法一样，中继系统的测试也不需要UT。蕿闭环测试法的缺点是被测中继系统只有一端的行为能被直接观察到，而另一端的行为不能被正确地评价

35、。祎横断测试法则使中继系统在正常操作模式下得到完全的测试，且两端的行为都能够被观察到。芄膂理解CI,ASPPDU作用与传输过程芁LT和IUT通过(n-1)层服务交换(n-1)ASP,而UT和LT利用(n-1)层提供的另 外一条通道交换协同信息CI(Coordinated Information)。衿理解PCO莄PCO由下列三种因素标识：? IUT内对测试事件进行 控制与观察的服务边界；? 在该点进行控制和观察的一组测试事件(ASPs或PDUS;? 对这些测试事件的控制和观察是在SUT内还是在测试系统中。如果IUT是运输层协议实体，那么? (n)ASP就是运输服务原语 TSP(Transport Service Primitives), UT 使用 的PCO就是运输服务访问点 TSAP? (n-1)ASP就是网络服务原语 NSP(Network Service Primitives) , LT使用 的PCO就是网络服务访问点 NSA