一、概论

1. 协议是网络中互相通信的对等实体间进行数据交换而建立的规则、标准或约定，保证实体在计算机网络中有序地交换数据。实体(Entity)是指任何可以发送或接收信息的硬件或软件进程，在大多数情况下，就是一个特定的软件进程。位于不同系统的同一层次内交互的实体，就构成了对等实体。
2. 协议是规则，约定，而服务是功能，本领。从层次上来说：协议是通信双方对等层之间才有的，是水平方向上的关系。而服务则是通信某一端上下层之间才有的，是垂直方向上的关系，而且是自下向上提供的 。每一层的协议是通过下层对本层提供的服务来支持实现的，服务是指下层为紧向邻的上层提供的功能调用。
3. 网络协议就是具有规定文法、语法和语义的语言 。文法给出了有效信息的精确格式 ，语法描述了数据交换的规则，语义规定了可交换信息的词汇及其含义。
4. 协议三要素：语法、语义、同步。六元素：服务原语和服务原语时序、协议数据单元PDU和PDU交换时序 、协议状态、协议事件、协议变量、协议操作和谓词。
5. 网络协议中的语法体现为数据报文中的控制信息(通常在报文的首部)和各种控制报文的结构、格式。即规定报文的长度，报文中划分多少个域(Field)，每个域的名称、数据类型、长度等。其中，报文中各个域的类型、长度及相互间的位置、顺序关系则构成了词法。
6. 网络协议的语义可以理解为：协议数据报文中的控制信息和控制报文所约定的含义，即需要完成何种动作，发出何种控制信息以及做出何种响应。例：IP报文首部控制信息中的目的地址域指明了报文的目的地，接收到此报文的网络节点均将该域作为进行路由选择的依据，因而，规定在首部控制信息中的给定域给出目的节点地址就是一种语义。
7. 简单地说，同步是指事件发生顺序的详细说明。具体来说指通信过程中各种控制报文传送的顺序关系。例：例如“允许连接”或“拒绝连接”报文必须是作为请求连接报文的一种响应来发送，“拆除连接”报文也必须在建立连接后的某种条件下发送。
8. 为什么推崇协议标准化：1.产品质量和可靠性 2.提供更好的产品互联性 3.简化使用 4.提高发布效率
9. ISO/IETF/W3C/ATM Forum/ANSI/IEEE/ACM
10. 协议工程过程是协议化、工程化的。
11. “协议的设计、形式描述、验证、实现、测试、运行”这一全过程称为“协议开发”，即协议开发是指协议工程活动的全过程。
12. 协议设计阶段的结果是非形式描述协议文本。协议设计涉及到很多技术，如差错控制技术、流量控制技术、连接管理技术、路由选择技术等。协议设计还必须遵循一些基本原则，如结构化、模块化等。
13. 形式描述模型：有限状态机FSM (Finite State Machine) 、Petri网(PetriNet) 。形式描述语言：CCITT制定的SDL。
14. 协议的验证主要内容包括：可达性分析、死锁和活锁检测、协议的有界性和完整性检验、协议的动作序列检查、通道溢出检查等
15. 协议一致性测试要做到两点：彻底性(彻底测试所实现的协议)和标准化(使用的测试集必须是标准的)。协议的性能主要包括吞吐量和时延。
16. 

二、协议设计

1. 同一系统相邻两层的实体进行交互的地方，通常称为服务访问点SAP (Service Access Point)，服务用户通过SAP调用服务，一个SAP拥有唯一的地址。服务用户通过在一个SAP递交数据并从另一个SAP读出。
2. 在进行交互时所要交换的一些必须信息(或命令)称为服务原语(Service Primitives)，以表明需要本地的或远端的对等实体做什么事情。原语告诉服务实体要执行某个动作，或者将对等实体所执行的动作报告给服务用户。服务的调用是通过SP描述的，具体而言，SP就是服务用户与服务提供者之间的交互的抽象描述，并不限定这些交互如何实现。
3. 每层均可使用的4种服务原语。Request/Indication/Response/Confirm
4. 一个(n)实体向上一层所提供的服务由以下三部分构成： (n)实体自己提供的某些功能、通过与处在另一系统中的对等(n)实体的通信而得到的服务、从(n-1)层及其以下各层以及本地系统环境得到的服务。将(n)层对等实体之间，为实现该层协议所交换的信息单元称为协议数据单元PDU (Protocol Data Unit)。通常将第n层的协议数据单元记为(n)PDU。
5. PDU通常由2部分构成：用户数据和协议控制信息PCI(Protocol Control Information)。PDU两种类型：数据PDU、控制PDU（不携带用户数据）。在不同的协议层次中，PDU还的一些其它的表示法：物理层：比特(bit)；数据链路层：帧(frame)或信元(cell)；网络层 ：分组或包(packet) ；传输层 ：分段(segment)、数据报(datagram)；应用层：消息(message)。
6. OSI将层与层之间交换的数据的单元称为服务数据单元SDU (Service Data Unit)。一个(n)服务数据单元就是(n)服务所要传送的逻辑数据单元。SDU就是数据PDU中的用户数据，但不一定是一一对应关系。 可以是多个SDU合成为一个PDU(称为“拼装”)，也可以是将一个SDU划分为几个PDU(称为“分段”)。
7. 协议是“水平的”，即协议是控制对等实体之间通信的规则。服务是“垂直的”，即服务是由下层向上层通过层间接口提供的。“虚拟”指看起来存在但实际上不存在的事物，“透明”相反。
8. N层中任何两个协议实体通过(n-1)SAP所形成的逻辑数据通路称为(n-1)层通道。通道的类型：空通道、非缓冲通道、缓冲通道。通道队列的主要性质是平均队列长度以及最大队列允许长度。
9. 回程时延RTT。从n层源端实体发出报文到该报文的确认信息到达该实体之间的时间间隔，它包括目标实体收到报文之后，对报文进行处理然后发出确认信息的时间。（处理时延、排队时延、发送时延、传播时延）
10. 如果通道是利用(n-1)层的有（无）连接服务形成的，那么传递的报文不会（有可能）失序。通道的工作方式：单工、半双工、全双工 | 同步与异步。
11. 协议的两大功能：连接管理，数据交换。

• 连接管理：
  • 两种连接：点对点、点对多点
• 三种主要功能：连接建立、连接释放。连接维护
  • 数据交换：
  • n层协议接收n层用户递交的(n)SDU（(n-1)层通道的(n)PDU），将之转换成(n)PDU（提取其中的(n)SDU），从(n-1)层通道发送出去（转交给n层用户）。
  • 一般要实现功能：对齐、分段和合段、拼装和分离、PDU的装配和拆装、SDU的编码与解码、加校验和、抖动补偿、带外数据和紧急数据的发送。(n-1)通道提供的数据通道的可靠性越高，则n层协议需实现的差错控制机制则越少。

12. 用来防止丢失、重复和乱序的方法包括：序号、确认、重传、计时器。(n-1)通道提供的数据通道的可靠性越高，则n层协议需实现的差错控制机制则越少。

• 序号：检测PDU重复、失序、丢失|进行无二义性编号|SDU序号、PDU序号、字节序号|使用一个非常大的序号空间*（从一端到另一端的最大可能的延迟时间L内，所有从源点发送出去的新的数据单元都具有不同的序号）*序号是确认和重传的基础，此外序号还可用于流量控制 
• ACK可以确定PDU和字节。可确认的情况：已正确到达，还没有收到，收到但有错(相当于没有收到)。分为三种类型：AcK，Nak，Select Ack。两种发送方式：独立确认（指用一个确认PDU，可随时发送），应答携带（放在数据PDU中可提高效率，但需要接收方有数据发送）。通常在一种协议中两种确认形式均存在。选择确认信息中包含多个序号时有三种格式：表，范围，位图。
• 计时器的超时值设置依赖RTT。计时器的超时值太短：大量数据重传，加剧网络拥塞程度；太长：数据丢失得不到及时纠正，降低协议性能。
• 基于滑动窗口的重传方法：回退N帧和选择重传。

13. N层协议所提供的服务是N层协议外部行为的体现。在协议的控制下， N层的两个对等实体间通信，使其能够向上一层提供服务。要实现本层协议，需要使用下一层所提供的服务。一般用服务规范(Service Specification)来定义和描述N层协议向外部所提供的服务，包括：服务原语和服务原语时序。N 层协议的服务原语和原语参数详细准确地描述了N层协议和它的服务用户之间的接口。
14. 协议的主体是它的状态-事件转换机制 。一个完整的服务原语通常包括原语名字、原语类型和原语参数三大部分，如T-CONNECT.request(被叫地址，主叫地址，......)。
15. 根据使用服务原语的角度来考虑，可将服务分为两类： 需要证实的服务，不需要证实的服务。根据所提供的服务的不同，为完成某功能所需的服务原语的个数和服务原语的时序是不同的。
16. 三次握手需要用到三个PDU：CR(连接请求)，CC(连接证实)，AK(确认)。
17. 协议状态分为：局部状态，全局状态。N层协议必须定义所有的协议状态。
18. 协议事件根据用途可分为：输入事件，输出事件。根据作用范围可分为：通信事件（收发服务原语或收发PDU，可分为同步时间或叫协同事件和异步事件），内部事件。三个性质：成对性（通信事件成对，内部事件不成对）、原子性、时序性。每种协议功能都是通过一组协议过程的执行来实现。
19. 协议操作只有在一定条件（谓词）下才能够被执行。描述一个协议过程必须说明该过程所包含的操作以及执行操作的谓词。
20. 元素之间的有机联系：在什么协议状态下，在什么输入事件驱动下，调用什么协议过程；协议过程在什么条件下(谓词)，采取什么协议动作(操作)，输出什么事件或修改哪些协议状态和变量。
21. 协议三种运行方式：协议交替、协议并发、协议并行。
22. 协议文本中最重要、最主要部分是协议元素的描述。必须对每一项协议元素作出准确、清晰、无二义性的定义。
23. 一个好的结构化协议设计，应具有以下特点：简单、模块化、有界性自稳定性和自适应性、健壮性、一致性。前两个最基本。分层设计难点：层次太少会使每一层协议太复杂，太多则在描述和综合各层的系统时难度较大。协议分层优点：各层独立、灵活性好、结构上可分割、易于实现和维护、能促进标准化工作。
24. 流量控制：发送方以不超过接收方处理能力的速率发送数据。差错控制有全局性。相同：提高网络性能。

三、协议形式化描述技术-概述

1. 形式化技术 FDTs (Formal Description Techniques)，FSM是个五元组：FSM = (S, s0, I, delta, F)

• S，有限状态集合。任一确定时刻，FSM只能处于一个确定的状态。
• s0，初始状态，开始接受输入。
• I，有限输入字符集合，任一确定的时刻智能接受一个。
• delta，状态转换函数，
• F，终态集(可空)，不再接收输入。

2. Moore 机：输出与状态有关。Moore FSM is 6-tuple: FSM = (S, s0, I, O, delta, lambda)。

• O，有限输出字符集合。
• lambda，s->O，输出函数。
• Moore机只是在接收输入串的过程中不断改变状态，并且在每个状态上有字符输出。 有限状态机可看做是Moore机的一个特例。 对于任何一个有限状态机(S, s0, I, delta, F)，引入输出字符集合 O = {0, 1}，并定义S到O的映射lambda为：s属于F, lambda(s)=1；s不属于F, lambda(s)=0。这样得到一个Moore机M=(S, s0, I, O, delta, lambda)，在该Moore机中，输出为1的状态为终结状态，输出为0的状态即为非终结状态。

3. Mealy机：输出与状态和输入有关

• lambda，s*I->O，输出函数。
• Mealy机只是在接收输入串的过程中不断改变状态，并且字符输出与当前状态及输入串有关。 Moore机可看做是Mealy机的一个特例。 对于任何一个Moore机 M=(S, s0, I, O, delta, lambda)，PPT三-32

4. 停等协议的状态变迁表：发帧的2竖列除了准备发且发了的，其他状态都不改变，且斜杠后只有发了的有东西。准备发时收到ACK状态不变。准备发和发了的超时，变为准备发相同的状态。

5. 

6. 

7. 

8. 

四、协议形式化描述技术-PetriNet

1. 四元组(P, T , I, O)

• P，位置(places)的有限集合。
• T，变迁(transitions)的有限集合，且T与P不相交。
• I，输入函数，是变迁T到位置的映射。
• O，输出函数，同I。
• 点火前，取出标记数量=远离圆的弧线数；点火后，放入标记数量=进入圆的弧线数。

2. 状态变迁类型：顺序、并发、互斥变迁。
3. Petri网的性质：行为性质(与初始标记量有关)、结构性质(无关)。

• 行为性质
  • 可达性。
  • 有界性。(任一可达)位置p为k有界；Petri网为k有界(每个位置都K有界)；有界性意味着位置中的标记数量不会无限地增加。
  • 安全性。如果位置p为1有界，则称位置p是安全的。
  • 活性。从M0可达的任一标记向量出发，都可以通过执行某一变迁序列而最终引发变迁t，则称t在标记向量M0下是活的。
  • 可逆性、可覆盖性、可持续性、公平性。
• 结构性质
  • 结构活性、结构有界性、可重复性、相容性结构有界公平性

五、SDL

1. 规范及其描述语言SDL (Specification and Description Language)。SDL是基于扩展有限状态机和抽象数据类型的混合技术。一个SDL应用的静态结构由系统(System)、功能块(Block)、进程(Process)、过程(Procedure)和通道(Channel)构成。各功能块包含若干个进程，SDL系统的动态行为具体表现为各进程的实例的并发操作。
2. 一般来说，SDL中的数据类型定义包括三个部分：类定义，操作符(Operators)定义和等价式(Equations)定义。
3. 编程

• SDL中的数据类型定义包括三个部分：类定义，操作符(Operators)定义和等价式(Equations)定义

• 类定义：newtype ... endnewtype

• 等价式、等值类。等价式参数化：FOR ALL x, z IN Real  ((x/z)*z = = IF z/=0 THEN x ELSE ERROR! FI)。产生器，如：数组、串、幂集。继承INHERITS Sort1

• 记录

//定义
STRUCT
	last_name, first_name, street, city: Charstring;
	number : Integer;
//赋值
address :=(.Lai, Richard, Carbost Court, Macleod, 2.);
//取出一个变量
town := address!city;

• 功能块内通信手段主要包括共享变量或通过信号路由(signal routes)交换信号。信号路由中的箭头在线条的两端。 通道在中间。

六、协议验证技术

1. 通过协议验证，可以获知协议设计是否满足正确性、完整性和一致性等要求。

• 服务规范 协议规范的一致
• 协议规范 协议实现的一致

2. 形式化协议验证两类方法：模型检测(可达性分析、不变性分析、重要问题：状态空间爆炸)、演义验证。协议验证着重在于一般性质，而协议测试则着重于特殊性质。
3. 安全性 v.s. 活动性

• 安全性：
  • Bad things never happen。
  • 协议的所有动作均需与它的服务规范保持一致，且没有不期望的情况出现。
  • 安全性保证协议不出现错误。
• 活动性
  • Good things eventually happen。
  • 在有穷时间内，完成规范所规定的动作(或所有的服务必须在有限时间内完成。
  • 协议的活动性体现在终止性(termination)和进展性(progress)两个方面。终止性是指协议从任何一个状态开始运行，经过有限时间总能正确地到达终止状态；进展性是指协议从初始状态运行，经过有限时间总能到达指定状态。

4. 可达性分析

• 原理：采用穷举法检查同一层内两个或多个协议实体间所有可能的交互所产生的全局状态。

• 三种算法：

  • 穷尽性可达性分析(完全搜索)算法 (exhaustive or full search)：优点在于可以证明协议中没有错误，当系统状态的数目非常大时，会发生状态空间爆炸。
  • 受控部分搜索算法：证明错误的存在，而不是证明没有错误。解决了状态空间爆炸，但只能最大限度地发现错误。
  • 随即模拟算法：即使是无限大系统也可以应用。没有明确的终止，无法判断是否已经访问过系统的所有可达状态，也就无法判断是否已经发现了系统的所有错误。不能证明协议中没有错误。

• 解决空间状态爆炸：部分规范描述和验证、选择大的动作单元、分解或划分、按断言来分类状态。

七、一致性测试技术

1. “一致性测试”的目的是检查一个给定协议实现的外部行为是否符合协议的规范，“验证”则是检查形式化规范的逻辑正确性。

ps：就是这第七章，当时听谁说不考，就没看多少，结果出了几个小题和一个大题 =_=