网络协议工程总结

-.z第二章协议设计技术1.协议层次模型：〔主要是描述n与n+1实体间的关系〕实体(entity)：表示任何可以发送和接收信息的硬件或软件进程。在许多情况下，实体就是一个特定的模块。n效劳：两个(n)实体在(n)协议的控制下的通信，使(n)层能够向上一层(n+1)提供效劳。这种效劳就是(n)效劳。一个(n)实体向上一层所提供的效劳由以下三局部构成：(n)实体自己提供的*些功能。从(n-1)层及其以下各层以及本地系统环境得到的效劳。通过与处在另一系统中的对等(n)实体的通信而得到的效劳。PDU通常由2局部构成：用户数据和协议控制信息PCI(ProtocolControlInformation)。PCI一般作为首部加在用户数据的前面，但有时也可作为尾部加在用户数据的后面，例如检验和(checksum)常放在尾部。两种类型：数据PDU控制PDU，不携带用户数据。在不同的协议层次中，PDU还有一些其它的表示法。物理层：比特(bit)；数据链路层：帧(frame)或信元(cell)；网络层：分组或包(packet)运输层：报文(Message)SDU:OSI将层与层之间交换的数据的单元称为效劳数据单元SDU(ServiceDataUnit)。一个(n)效劳数据单元就是(n)效劳所要传送的逻辑数据单元。SDU就是数据PDU中的用户数据，但不一定是一一对应关系。可以是多个SDU合成为一个PDU(称为“拼装〞)，也可以是将一个SDU划分为几个PDU(称为“分段〞)。PDU的装配与拆装:在发送数据之前，(n)协议需要装配PDU，即按照给定格式附上协议控制信息PCI。对于接收后的PDU要对之拆装，拆出PCI。SAP:同一系统中相邻两层的实体进展交互(即交换信息)之处，通常称为效劳访问点SAP(SerivceAccessPoint)SP〔效劳原语〕：在进展交互时所要交换的一些必须信息(或命令)称为效劳原语(ServicePrimitives)，以说明需要本地的或远端的对等实体做哪些事情。每层均可使用的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.连接于非连接：面向连接的(connection-oriented)效劳三个阶段：连接建立、数据传输和连接释放在传送数据时是按序传送的网络层：虚电路效劳比较适合于在一定期间内要向同一目的地发送许多报文的情况永久虚电路：适于两个用户需要经常进展频繁的通信的情况无连接的(connectionless)效劳不能保证报文的丧失、重复、失序三种类型：数据报(datagram)、证实交付(confirmeddelivery,可靠的数据报)、请求答复(request-reply)数据报：不需要接收端做任何响应。尽最大努力交会(besteffortdelivery)证实交付：又称“可靠的数据报〞。对每一个报文产生一个证实给发方用户，不过这个证实不是来自接收端的用户而是来自提供效劳的层请求答复：收端用户每收到一个报文，就向发端用户发送一个应答报文。适于“事务(transaction)〞中的通信。适于传送少量零星的报文3.通道：(基于三种通道的FSM模型)主要有三类：空通道(emptychannels)报文的发送时间和延时时间为0的通道报文一旦从输入端进入就立即在输出端出现非缓冲通道(non-bufferedchannels)在任何时刻，最多只有一个正在传送中的报文的通道缓冲通道(bufferedchannels)允许有多个报文停留的通道形成方式和队列性质〔次要〕〔p12〕4.几种控制：过失控制主要概念在网络上进展通信会造成数据PDU以一定的概率被损坏、丧失、重复和乱序。协议的过失控制功能负责这些过失的检测及恢复，保证数据的可靠传输。n层协议的过失控制机制与它的效劳提供者提供的(n-1)通道的性质有很大关系，(n-1)通道提供的数据通道的可靠性越高，则n层协议需实现的过失控制机制则越少。主要技术有：〔检错重传或丢弃、纠错〕确认(Ack)计时器(Timer)重传(Retransmit)序号(SequenceNumber)过失控制的层次关系从通信和信息处理的角度看，物理层、数据链路层、网络层和运输层属于面向通信局部，因而网络中的绝大局部过失控制功能要在这几层中实现。处于不同层次的协议所采用的过失控制机制是有差异的。流量控制流量控制是指“收端控制发端的发送数据速率以使收端来得及接收，并且使网络不致过载〞Why?接收方的接收能力有限缓存不够处理能力不够E*amples:StopandWaitSlidingwindow拥塞控制在*段时间，假设对网络中*一资源的需求超过了该资源所能提供的可用局部，网络的性能就要变坏。这种情况就叫做拥塞(congestion)。资源(resources)：链路容量交换结点中的缓冲区〔buffer〕处理机拥塞控制的主要功能防止网络因过载而引起吞吐量下降和迟延增加防止死锁在互相竞争的各用户之间公平地分配资源第三章形式化描述技术1.FSM：定义FSM=(S,s0,I,d,F),whereS={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到达终态后不再接收输入实例一：开关实例二：IDLEDIALINGRINGINGPATHACTIVEOn-hook-IDLE-IDLEOff-hookSendDialTone,

DIALING-PATH

ACTIVE-Dial-digit

(Note1)-DIALING

PATHACTIVE--Call-AlertRingPhone,RINGING///2.PETRINET:概念Petri网可定义为一个4元组(P,T,I,O)，其中：P={p1,p2,…,pn}是位置(places)的有限集合；T={t1,t2,…,tm}是变迁(transitions)的有限集合，且T与P不相交，即T∩P=Æ。I是输入函数，是变迁T到位置的映射。对于每一个tk∈T，可得出相应的I(tk)={pi,pj,…}。O是输出函数，也是一种变迁T到位置的映射。对于每一个tk∈T，可以得出相应的O(tj)={pr,ps,…}。M={m1,m2,…,mn}是标记(tokens,“旗标〞或“托肯〞)的集合变迁类型例子：例子二〔行为性质与构造性质见p58〕第四章形式描述语言〔三选二〕1.SDL:系统描述〔p84〕SYSTEMsample;SIGNALS1,S2,S3,S4,S5;CHANNELC1FROMENVTOB1WITHS1,S2;ENDCHANNELC1;CHANNELC2FROMB1TOB2WITHS3;ENDCHANNELC2;CHANNELC3FROMB2TOB1WITHS4;ENDCHANNELC3;CHANNELC4FROMB2TOENVWITHS5;ENDCHANNELC4;BLOCKB1REFERENCED;BLOCKB2REFERENCED;ENDSYSTEMsample;(b)用SDL/PR表示的系统例子功能块描述：〔p85〕BLOCKB1;SIGNALSa,Sb;SIGNALROUTER1FROMENVTOP1WITHS1;SIGNALROUTER2FROMENVTOP2WITHS2;SIGNALROUTER3FROMP1TOENVWITHS3;SIGNALROUTER4FROMENVTOP2WITHS4;SIGNALROUTER5FROMP1TOP2WITHSa;FROMP2TOP1WITHSb;CONNECTC1ANDR1,R2;CONNECTC2ANDR3;CONNECTC3ANDR4;PROCESSP1REFERENCED;PROCESSP2REFERENCED;ENDBLOCKB1;(b)用SDL/PR表示的功能块例子进程描述：〔p87〕宏定义2.ESTELLE:注意点：类别为systemprocess的模块的子模块的类别可以是process或activity；而类别为systemactivity的模块的子模块的类别必须是activity。类别为process的模块的子模块的类别必须是process；同样，类别为activity的模块的子模块的类别必须是activity。两种并行方式：异步并行(asynchronousparallelism)。异步并行性只能存在于不同系统模块之间同步并行(synchronousparallelism)。同步并行性只能存在于一个系统模块内。例子一：模块嵌套举例例子二：滑动窗口协议交互点的位置，可以将IP分为两种：内部交互点，如p19,p20,p21,U*,UY外部交互点(e*ternalIP)。其余的都为外部交互点优先级：如果一个系统模块的类型为systemprocess，则该系统模块内的各个子模块可以并行执行，而父模块则优先于子模块执行。如果一个系统模块的类型为systemactivity，则该系统模块内的各个子模块只能串行运行，具体哪个子模块执行则是随机选择的，父模块仍然优先于子模块执行。3.LOTOS〔传说不会考〕在LOTOS中，信息系统或系统都是从整体上表达信息活动的。例如信息的传输、加工、存储等操作都是系统的信息活动。而系统则由一组互相交互的局部(Part)所组成。在Part中发出的信息活动称为动作(Action)。涉及到两个或多个Part的共同动作则称为交互。为了说明一个系统，LOTOS采用了进程、事件和事件门(gate)等概念。进程被当作一个黑盒子，我们只关心它的外显行为。事件则是发生于进程之间的交互原语的实例，是由相关进程共同执行的。事件门就是交互点，通信双方利用事件门互相传递事件值。LOTOS规定了一组进程的重写规则。进程间交互时发生的事件会使一个进程被重写为另外一个进程。系统状态与事件的关系为树形构造：树结点表示状态，树的边表示在*状态下可能发生的事件。进程间的交互是全同步的:所谓全同步是指只有在互相交互的各个进程都处于就绪状态下，一个事件才有可能发生。事件是原子的，即不能再细分为子事件的。各事件在时间上是互不重叠的。Part与进程都可以逐步细分。第五章验证技术1.一般性质和特殊性质：一般性质〔着重理解：可达性、没有死锁、没有活锁〕特殊性质2.可达性搜索法〔三选一〕穷尽性可达性分析算法(e*haustiveorfullsearch)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；}优点：验证覆盖*围全面，可以证明协议中没有错误。缺点：算法能分析的最大状态数目依赖于协议、描述方法和可用的计算资源。特别是当系统状态的数目非常大时会发生状态空间爆炸，应用*围有限。当状态空间大于存储空间时，全搜索策略将变成局部搜索，且不能保证检查协议中最重要的局部，而搜索质量变得更差。对于复杂的协议，穷尽性可达性分析的效果只能算作是一种低质量的局部搜索。受控局部搜索算法(controlledpartialsearch)/*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；}受控局部搜索算法的目的是证明错误的存在，而不是证明没有错误。优点：与穷尽性可达性分析相比，这种算法可以有效地解决状态空间爆炸问题，同时利用有限的资源来验证协议的最重要的局部，从而最大限度地发现错误。缺点：必须能够预先判断出协议中的错误的大概位置，然而这很难预先做到；虽然这些方法能够减小状态空间的大小，但它们都没有提供任何工具，将状态空间的大小与可用内存相匹配。使用这些方法时，有效搜索的局部状态空间的大小是协议相关的，只能通过实验确定，要想找到一种最优的方法，必须按照不同的选择策略进展屡次验证。随机模拟算法(randomsimulation)。analyze()/*随机模拟*/{q=初始状态;while(1){if(q==错误状态){report_error();q=初始状态;}elseq=q的一个后继状态；}优点：随机模拟算法与协议系统的大小和复杂性无关，即使是无限大小的系统，也可以应用。因此，对于复杂的验证问题，这种算法也许是唯一可用的方法。缺点：它没有明确的终止，无法判断是否已经访问过系统的所有可达状态；由于没有算法的终止，也就无法判断是否已经发现了系统的所有错误因此只能发现协议中的错误，而不能证明协议中没有错误。第七章一致性测试技术(需要看pptp33，掌握9个图+相应的描述)9个图图一：一致性测试模型图二：本地测试法(LocalMehtod)在这种方法中，LT，UT，IUT同处于一台机器中，测试不需要低层通信系统的支持。由于UT和LT可以在同一个程序中实现，因此，UT和LT的测试协同过程TCP(TestCoordinateProcedure)比较容易实现。测试例用UT执行的效劳原语和LT执行的效劳原语来描述。在这里，LT相当于低层效劳提供者。图三：分布式测试法(DistributedMethod)在这种方法中，IUT和UT处于同一台机器中，而LT则分布在其它机器中。LT和IUT之间利用(n-1)层效劳交换报文(可以在线测试)。与本地方法相比，LT和IUT之间的接口PCO从IUT中转换到LT中，LT相当于(n-1)层效劳的使用者测试协同过程TCP隐含在测试例中，测试同步问题由UT和LT的操作者来实现。适用于本地方法的测试例必须改写后才能用于分布式测试法。图四：协调测试法(CoordinationMehtod)协同测试法和分布式测试法的根本区别在于协同测试法引入测试管理协议TMP(TestManagementProtocol)。有了TMP，UT和LT就通过交换TM-PDU实现测试协同过程。交换TM-PDU有两种方法：带内传送法，即将TM-PDU作为(n)ASP的用户数据传送给IUT，IUT再将它传送给LT；带外传送法，即将TM-PDU直接利用(n-1)层效劳来传送。图(c)所示的是带内传送法。同样，分布式测试法的测试例不能用于协同测试法。图五：远程测试法(RemoteMethod)这种测试方法中没有UT，因此也不存在UT和LT之间的协同问题。在这种方法中，测试例完全用(n-1)ASP描述。远程方法比较适用于被动式协议实现或效劳型协议实体的测试。图六、七：渡船测试法(FerryMethod)〔重点之中的重点，综合性较强〕将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处于同一台机器中，测试协同过程像本地方法一样容易实现，被测试系统中只要增加简单的渡船软件即可。只是