协议工程复习要点

协议工程复习要点第一章协议工程概论1、概述协议：是某种活动或者行为所遵守的准则或规则。在计算机世界中，协议是计算机之间或者计算机与其它设备之间用来通信的规则或语言。协议工程学：是研究协议设计，协议验证、协议实现、协议测试等技术的一门新地计算机学科。协议工程：一体化、形式化的协议开发过程。协议工程研究目的：旨在减少协议开发种潜在地错误，提高协议开发效率，促进协议标准化地发展第一章协议工程概论2、SDU、PDU和PCI之间的关系(n)SDU(n)PDU(n)PCI(n)PDU(n-1)层(n-1)SDU(n-1)SDU第一章协议工程概论3、协议开发过程协议的开发包括六个过程协议设计(PDU格式,协议机制,服务原语等设计)协议描述,用某种语言确切地描述协议元素协议的验证与性能分析,对所描述的协议严正其正确性,分析其性能;协议实现,根据描述的协议产生网络硬软件协议测试,对实现的协议进行测试协议维护,对网络软硬件进行维护第一章协议工程概论4、协议的复杂性，如何理解（P5)分布性、并发性、异步性、实时性、通道系统的不稳定性第一章协议工程概论5、协议工程的研究内容协议工程技术可归结为5个方面（1）协议设计技术(构造、综合、开发)（2）协议模型及形式描述技术（3）协议验证分析技术（4）协议实现技术（5）协议测试技术第二章协议构造技术1、协议构造包括以下内容：①协议环境分析：用户要求、通道性质、工作模式②协议功能设计③协议组织形式的确定（层次化、阶段化、分类、运行方式（交替、并发、并行））④协议元素的构成（重点）⑤协议文本的编写第二章协议构造技术2、协议有六种元素：●服务原语和服务原语的时序●协议数据单元（PDU）和PDU交换时序●协议状态●协议事件●协议变量●协议行动和谓词第三章协议模型技术1、协议性质（P35-36）（1）活动性（概念、体现——终止性与进展性；协议的回归性）（2）安全性（概念）（3）一致性（概念）（4）完备性（概念）第三章协议模型技术2、协议元素性质（P37）（1）事件的成对性（2）事件的原子性（3）事件的时序性（4）状态时序性（5）变量的有界性（6）过程的原子性第三章协议模型技术2、有限状态自动机（FSM）S,I,E,T(1)有限状态自动机定义(2)通道FSM空通道FSM模型非缓冲通道FSM模型半双工非缓冲通道FSM模型(3)AB协议系统有限状态自动机模型(S,R实体)第三章协议模型技术3Petri网（1）Petri网的定义（2）Petri网触发规则（3）AB协议实体S、R的petri网模型（4）通道的Petri网模型（5）AB协议的petri网模型第三章协议模型技术4、时序逻辑时序逻辑系统和谓词逻辑一样，时序逻辑（TL,Temporallogic）公式由命题、谓词、函数、常量、变量、量词和逻辑操作符组成。不同的是，它对谓词逻辑进行扩充，增加时序操作等（模态算子），“时序”指系统状态序列。时序操作符此处引用王元元所使用的时序操作符。(1)□“今后”（henceforth），“总是”（always），□A表示：当前状态开始（包括当前状态），A总是为真。(2)◇“最终”（eventually），“某时”（sometime）。◇A表示：从当前状态开始，系统存在一个状态，A为真。(3)○“下次”（next）。○A表示：A在系统的下个状态为真。(4)▽“直到”（until）。A▽B表示：从当前状态开始直到B为真位置（包括B为真的那个状态），A总是为真。时间（状态）的参考点是正确理解时序操作符含义的关键，请看下述复合操作符的含义。第三章协议模型技术□◇A从当前状态开始，系统存在多个状态，A为真。它可直译为：从当前状态开始，取系统的任意一个状态为起点◇A为真。◇□A系统中存在一个状态，从那个状态开始，A总是为真。○□A下个状态开始，A总是为真（当前状态可能不为真）。○◇A下个状态开始，系统存在一个状态，A为真。□○A从任何状态开始，系统的下个状态为真。◇○A系统存在一个状态，它的下个状态，A为真。第三章协议模型技术通道性质的描述用TL描述通道的性质是非常容易的。AB协议的通道性质可表述为：CH1:after(a?ack0)←→at(b!ack0)CH2:after(a?ack1)←→at(b!ack1)CH3:□◇after(b?m0)→□◇at(a!m0)CH4:□◇after(b?m1)→□◇at(a!m1)上一章思考题8的假定条件3（认可报文不丢失，不出错，不重复）由CH1和CH2恰当地表述出来了。CH3和CH4是假定条件2的描述，可能释为：R重复收到报文n次，意味着S重复发出报文m次（mn），就是说，S重复发一个报文m次，总会有n哥报文到达R。第三章协议模型技术3协议实体性质的描述AS1:(seq＝0)∧◇after(A?any)→□◇at(a!m0)after(a?ack0)AS2:(seq＝1)∧◇after(A?any)→□◇at(a!m1)after(a?ack1)AS3:after(a?ack0)←→success(m0)←→(seq＝0→seq＝1)AS4:after(a?ack1)←→success(m1)←→(seq＝1→seq＝0)AS1的含义是：S在顺序寄存器的值为“0”时（个体变量seq＝0）一旦从用户那里获取一个报文，它就向通道发送多次序号为“0”的报文，发送直到接收到ack0为止。AS1的蕴含符号不能改写成等价符号，因为AS1的前项在初始状态为真，后项在“S已有”的状态下为真。第三章协议模型技术AB协议的R可表述为：AR1◇at(b!ack0)→□◇after(b?m0)AR2◇at(b!ack1)→□◇after(b?m1)AR3at(b!ack0)←→at(B!m0)←→(seq＝0→seq＝1)AR4at(b!ack1)←→at(B!m1)←→(seq＝1→seq＝0)＝0)AR1的含义是：R一旦向S发送ack0就意味着它曾接受过多次m0。AR3说明R向S发送ack0，向用户递交报文m0，以及改变序号的行动是等价的。第三章协议模型技术5通信进程演算（CCS）第四章形式描述语言1、协议可以用哪些语言来描述，各有和特点。（P67）2、ESTELLE基本概念（模块、模块类别以及调用关系）。3、ESTELLE语言的特点与应用方法（P81）。4、LOTOS语言的特点与应用方法第五章协议验证技术1、可达性分析2、不变性分析3、等价性分析（重点）基于FSM的观察等价性分析：（1）强互拟等价（2）弱互拟等价（3）互拟关系的两个重要应用第五章协议验证技术（1）FSM的简化（P105）（2）FSM的等价比较（P105）第六章协议综合技术1、多阶段协议的综合方法(重点)（1）按运行阶段将协议分成许多独立的协议功能；（2）对各个协议功能进行设计和验证，或从别的地方获取成熟的协议的功能模块。（3）按照一定功能将协议供功能连接起来，产生目标协议。第六章协议综合技术2、CFSM网（1）协议实体CFSM（2）CFSM网（3）（M,N）状态（M，N）网的状态定义为四元数组（V,W,X,Y），这里V和W为M和N的两个结点。X和Y为流经FIFO通道报文流，X为N-M的报文流，Y为M-N的报文流。（M，N）网的初始状态记作（V0，W0，E，E），这里，V0，W0分别为M和N的初始结点，E表示通道为空（Empty）。3）（M,N）网的状态变化（1）终止条件（2）死锁条件（3）未确定接收条件（4）（M.N)网的有界性4）多阶段网的联接规则（P112）第六章协议综合技术2、交替功能协议的综合方法：设P1=(M1,N1)和P2=(M2,N2)为两个CFSM网，将P1中M1的初始结点和P2中M2的的初始结点结合起来，P1中N1的的初始结点和P2中的的N2初始结点结合起来，我们就得P=(M,N)网。如果(M,N)网有能力执行P1的功能或者P2的功能，但不能同时执行两者的功能，我们称这样的网为交替功能的CFSM网，其协议为交替功能协议(protocolwithalternativefunctions)第六章协议综合技术（1）同步问题（p113）（2）碰撞问题（p113）第七章协议实现技术1.协议研制基本步骤（P124）2.数据缓冲技术涉及的主要问题（P132）第八章协议一致性测试1、基本概念（1）一致性定义（P141）(2)一致性测试模型（P141）(3)协议测试工作流程（P142）2、测试方法（1）本地测试方法（2）分布式测试方法（3）协同测试方法（4）远程测试方法（5）渡船测试方法（6）多层协议测试方法