第一章 概述

一、协议定义

1. 为网络中互相通信的对等实体间进行数据交换二建立的规则、标准或约定，保证实体在计算机网络中有序地交换数据。

   
   
   实体及对等实体.png

2. 协议是关于分布式系统进行信息交换时地一种约定，协议应按照语言地方式进行定义。即：网络协议就是具有规定文法、语法和语义地语言。

   
   
   文法语法及语义
3. 延伸为计算机通信协议
   协议时计算机网络和分布式系统中各种通信实体或进程间相互交换信息是必须遵守的一组规则或约定。

二、协议三要素

语法、语义、同步

1. 语法
   网络协议中地语法体现为数据报文中的控制信息和各种控制报文的结构、格式。
2. 语义
   协议数据报文中的控制信息和控制报文所约定的含义，即需要完成何种动作，发出何种控制信息及做出何种响应。
3. 同步
   同步是指事件发生顺序的详细说明。具体来说，同步是指通信过程中各种控制报文传送的顺序关系。
   常用建立通信双方的有限状态机的方法来描述网络协议。

三、网络体系结构

采用层次式结构

网络体系结构=计算机网络的各层+各层协议的集合

ISO的OSI/RM：

七层模型

IETF的TCP/IP：
网络访问层、互联网层、传输层、应用层

TCP/IP协议结构

四、协议标准化

符合其用途
促进贸易、交流和技术转让
简化以提高可用性
规定一类设备必须能够执行的任务或者描述一个装置和它的安全特征。

五、协议工程

协议工程

1. 协议工程学用形式化方法描述协议设计和维护中的各个过程。

2. 协议工程过程

集成化、形式化的协议开发过程。

• 集成化
  协议描述、验证、实现和测试等技术前后衔接。
• 形式化
  指用形式描述技术FDT贯穿协议开发的各个阶段。

目的：减少协议开发过程中潜在的错误，提高协议开发的效率，促进协议标准化的发展。

3. 协议开发过程

协议设计、形式描述、验证、实现、测试、运行

协议开发过程

设计

根据协议的需求说明构造协议的非形式描述文本称为协议设计。
包括：协议环境分析、协议的功能设计、协议组织形式的确定、协议元素的构造、协议文本的编制等。
遵循原则：结构化、模块化等。
结果：非形式描述协议文本。

形式描述

形式描述模型：
1. 有限状态机FSM
2. Petri网
形式描述语言：
CCITT制定的SDL

验证

两项工作：

1.在语法和语义方面进行验证
2.进行计算机模拟

验证的主要内容：

1.可达性分析
2.死锁和活锁检测
3.协议的有界性和完整性检查
4.协议的动作序列检查
5.通道溢出检查等

验证方法：

1.模型检查
最常见方法：可达性分析。包括状态穷举、状态随机枚举、状态概率枚举等方法。
2.证明：推理演算，严密证明
3.模拟：通过模拟试验测试协议的各种性质

实现

协议实现是指由协议规范到协议的可执行目标代码的过程
协议实现的自动化：协议工程的主要目的之一。
通过形式化描述技术可实现半自动化。步骤：
1.利用翻译程序将协议的形式描述文本转换成与机器无关的源代码
2.手工编写与机器有关的、在协议规范中没有描述的问题的处理代码。

测试

验证一个协议的实现，主要考虑：
1.协议一致性测试
1.1 检测新协议实现是否能满足该协议规范所规定的规则。
1.2 如果协议实现不能通过一致性测试，则说明该协议实现与其他同样通过一致性测试的协议实现不能在同一个全局系统中很好地协调工作。
1.3 一致性测试的基础：FDT
1.4 一致性测试要解决的问题：
-> 测试系统设计
测试方法和测试系统体系结构
-> 测试序列的产生
“彻底性”、“标准化”。测试序列的自动生成和形式化描述。
1.5 测试序列生成器
可以产各种可能发生的情况组合，测试所实现的协议是否在各种正常和非正常情况下均能正确工作。
2.对协议实现的评价。
要求：
1.彻底性 须彻底测试所实现的协议
2.标准化 使用的测试集须是标准的

性能

主要包括吞吐量和时延
目的：
改善协议机制，提高执行效率。

协议维护

六、思考题

1.“软件工程”和“协议工程”的关系。
区别：
协议工程比软件工程更加一体化，形式化。协议工程的目的是减少协议开发过程中潜在的错误，提高协议开发效率，促进协议标准化的发展。
协议工程的开发过程包括：
设计，描述，验证，实现，性能分析和测试
软件工程的开发过程包括：
可行性分析，需求分析，概要设计，详细设计，具体开发。
联系：
协议工程和软件工程都是为了简化开发过程，协议工程时以协议软件为研究对象的软件工程。
2.选择一个网络协议，说明该协议的三要素。

第二章 协议设计

一、两种标准

1. OSI/RM

法律上的国际标准——开放系统互联参考模型，并没有得到市场的认可。只要遵循OSI标准，一个系统就可以和位于世界上任何地方的、也遵循这同一标准的其他任何系统进行通信。

1.1 各层基本功能

ISO/OSI各层基本功能

1.2 OSI失败的原因

1. OSI的专家们缺乏实际经验，他们在完成OSI标准时缺乏商业驱动力；
2. OSI的协议实现起来过于复杂，而且运行效率很低；
3. OSI标准的制定周期太长，因而使得OSI标准生产的设备无法及时进入市场；
4. OSI的层次划分不太合理，有些功能在多个层次中重复出现。

2. TCP/IP

非国际标准，但常被称为事实上的国际标准。

2.1 TCP/IP各层对应的主要协议

TCP/IP各层及主要协议

2.2 IP数据包的转发过程

整体情况

个别情况

两个路由器的IP地址并不出现在IP数据报的首部中，路由器只根据目的站的IP地址的网络号进行路由选择

路由情况

二、为什么要分层

1. 分层的好处

• 各层之间是独立的
  由于每一层只实现一种相对独立的功能，因而可将一个难以处理的复杂问题分解为若干个较容易处理的、更小一些的问题。这样，整个问题的复杂程度就下降了。
  某一层并不需要知道它的下一层是如何实现的，而仅仅需要知道该层通过层间的接口所提供的服务。
• 灵活性好
  当任何一层发生变化时，只要层间接口关系保持不变，则在这层以上或以下的各层均不受影响。故易于扩充或者改变协议。
• 结构上可分割开
  各层可以采用最合适的技术来实现
• 易于实现和维护
  因为整个的系统已被分解为若干个相对独立的子系统，使得实现和调试变得容易。
• 能促进标准化工作
  因为每一层的功能及其所提供的服务都已有了精确的说明。

2. 不分层的后果

如果不分层，每一个新的应用程序都必须为每个网络重新实现一次。

三、OSI模型的核心

服务、接口、协议

• Service – says what a layer does
  指某一层向上一层提供的一组原语(操作)，一个服务由一组原语正式说明，用户进程通过这些原语来访问服务
  定义了该层准备代表其用户执行哪些操作，但不涉及如何实现这些操作
• Interface – says how to access the service
  规定了有哪些参数，以及结果是什么
• Protocol – says how is the service implemented
  一组规则，规定了同一层的对等实体之间所交换的数据包或者报文的格式和含义。
  对等实体利用协议来实现他们的服务定义，可以自由改变协议，只要不改变呈现给他们的用户的服务即可。

服务与协议是完全分离的，服务涉及层与层之间的接口，协议涉及不同机器上两个对等实体之间发送的数据包

四、n层协议模型

协议模型

• 相关概念
  实体、（n）服务、（n）用户、SP、SAP、TSAP、NSAP

1. 实体

在OSI中，实体(entity)表示任何可以发送和接收信息的硬件或软件进程。在许多情况下，实体就是一个特定的模块。

2. SP-服务原语

在进行交互时所要交换的一些必须信息或命令，以表明需要本地的或远端的对等实体做什么事情。

• 4种服务原语
  Request (请求): 一个实体希望得到某种服务
  Indication (指示)：把关于某一事件的信息告诉某一实体
  Response (响应)：一个实体愿意响应某一事件
  Confirm (证实)：把一个实体的服务请求加以确认并告诉它

3. SAP-服务访问点

同一系统相邻两层的实体进行交互的地方。服务用户通过在一个SAP递交数据并从另一个SAP读出。

• TSAP-传输服务访问点（端口）
• NSAP-网络服务访问点（例如IP地址）

4. 服务

一个(n)实体向上一层所提供的服务由以下三部分构成：
(1) (n)实体自己提供的某些功能。
(2) 通过与处在另一系统中的对等(n)实体的通信而得到的服务。
(3) 从(n-1)层及其以下各层以及本地系统环境得到的服务。

服务与协议：
本层的服务用户只能看见服务而无法看见下面的协议。下面的协议对上面的服务用户是透明的。
协议是“水平的”，即协议是控制对等实体之间通信的规则。
服务是“垂直的”，即服务是由下层向上层通过层间接口提供的。
“透明”-指存在但看不见的事物
“虚拟”-指看起来存在但实际上不存在的事物

5. 协议数据单元PDU

将(n)层对等实体之间，为实现该层协议所交换的信息单元称为协议数据单元PDU (Protocol Data Unit)。通常将第n层的协议数据单元记为(n)PDU。

• 组成
  PDU通常由用户数据和协议控制信息PCI组成
  PCI一般作为首部加在用户数据的前面，有时也可作为尾部加在用户数据后，如检验和。
• 类型
  1.数据PDU
  2.控制PDU，不携带用户数据
• 不同的协议层次的PDU表示法
  1.物理层：比特(bit)；
  2.数据链路层：帧(frame)或信元(cell)；
  3.网络层 ：分组或包(packet)
  4.运输层 ：分段(segment)、数据报(datagram)
  5.应用层：消息(message)

6. 服务数据单元SDU

OSI将层与层之间交换的数据的单元称为服务数据单元SDU。
一个(n)服务数据单元就是(n)服务所要传送的逻辑数据单元。

PDU与SDU的区别与联系：
SDU就是数据PDU中的用户数据，但不一定是一一对应关系。
可以是多个SDU合成为一个PDU(称为“拼装”)，也可以是将一个SDU划分为几个PDU(称为“分段”)。

PDU和SDU

7. 通道

N层中任何两个协议实体通过(n-1)SAP所形成的逻辑数据通路称为(n-1)层通道。

n层协议的通信环境：

1.用户应用要求
2.(n-1)层通道(Channel)的性质
3.n层协议运行时的操作系统和硬件环境

通道的类型：

1.空通道-报文的发送时间和延迟时间为0的通道
2.非缓冲通道-通道中 最多只有一个正在传送中的报文
3.缓冲通道-允许有多个报文停留的通道

通道性质：

(n-1)层通道的性质对n层协议的构成有非常重要的影响

1.通道的形成方式：

A和B建立并独占一条连接，此时(n-1)层应提供有连接服务
A和B与其它协议实体一起共享一条连接
A和B利用(n-1)层提供的无连接服务进行通信
如果(n-1)层为物理层，A和B可独占一条物理信道，或共享一条物理信道

2.通道的队列性质：

除物理层外，一般可将(n-1)层通道看作是队列通道。
即一个数据报文从n层源端协议实体发出之后要在n层以下各层多次存贮转发，在每个存贮转发处就存在一个队列。
队列的主要性质是平均队列长度以及最大队列允许长度。
队列越长，那么数据报文在通道中的时延就会越大；
如果队列长度达到最大允许长度，那么后续的数据报文将会丢失 。

3.回程时延RTT

RTT是从n层源端实体发出报文到该报文的确认信息到达该实体之间的时间间隔，它包括目标实体收到报文之后，对报文进行处理然后发出确认信息的时间。

时延的产生

4.差错特性

• 参数：
  报文的出错率、报文的丢失率、报文的重复率、报文失序率
• 差错特性与它的形成方式有关：
  1.如果通道是利用(n-1)层的有连接服务形成的，那么传递的报文不会失序；
  2.如果通道是利用(n-1)层的无连接服务形成的，或是物理信道，则报文的顺序就有可能失序。

5.可靠性

通道的可靠性是指通道无故障，如连接中断、复位等。

6.报文的最大长度或最大传输单元MTU

通道所能接收的最大报文长度。主要影响n层协议的报文分段、拼接等功能。

7.工作方式

-单工、半双工、全双工
-同步与异步

8.通信方式

1. 点对点-任意两个N 层协议实体利用一条(N - 1)层通道通信，协同完成指定协议功能。如TCP连接，UDP点对点方式。
2. 点对多点-任意两个以上N 层协议实体利用多条(N - 1)层通道通信，协同执行一定的任务。如ATM的点对多点连接，UDP的广播方式。

9.安全性

对用户数据加密和安全控制（如口令、权限）

10.通道的带宽

通信线路的带宽也称通频带，用频率来度量。
通道的带宽可进一步分为前向带宽、后向带宽、峰值带宽等。

五、协议提供的服务

1. 面向连接的服务

• 三个阶段：
  连接建立、数据传输和连接释放
• 在传送数据时是按序传送的
• 比较适合于在一定期间内要向同一目的地发送许多报文的情况
• 网络层：虚电路服务
• 永久虚电路：适于两个用户需要经常进行频繁的

2. 无连接的服务

• 不能保证报文的丢失、重复、失序
• 三种类型：
  1.数据报-不需要接收端做任何响应
  2.证实交付（可靠的数据报）-对每一个报文产生一个证实给发放用户，这个证实来自提供服务的层。
  3.请求应答-收端用户每收到一个报文，就向发端用户发送一个应答报文。始于“事务”中的通信。
• 适于传送少量零星的报文

3. 思考题

1. 面向连接的服务和无连接服务的选择。
   答：
   强调数据传输的完整性、可靠性和可控制性时，选择面向连接的服务。
   强调数据传输性能时，选择无连接的服务。
2. HTTP协议利用有连接的TCP作为传输通道，并不断建立连接和断开连接。这样做的好处与坏处分别是什么。
   答：
   好处：管理简单，存在的连接都是有用的连接。一定程度保证完整性、可靠性。
   坏处：如果请求过于频繁，将在TCP的建立与关闭上浪费时间和带宽。

六、协议功能

（N）层协议为了向上一层提供服务，必须实现一定的功能。

1. 基本的协议功能的类型

• 连接管理
• 数据交换
  --
• 差错控制
• 流量控制
• 拥塞控制

1.1 连接管理

两种连接：

点对点、点对多点

三种主要功能：

连接建立

双方协商工作参数：初始序号
信用量、QoS。协商失败则连接建立失败。

连接释放

突然释放-立即关闭
文明释放-成功发送所有数据后关闭

连接维护

如Keep-alive查询、参数变更等。

针对延迟的保护措施：

• 如TCP三次握手机制
• 基于时钟的连接管理方法

1.2 数据交换

数据的发送与接收：

• n层协议接收n层用户递交的(n)SDU，将之转换成(n)PDU，从(n-1)层通道发送出去；
• 反之，它接收(n-1)层通道的(n)PDU，提取其中的(n)SDU，将之转交给n层用户。

协议支持的用户数据、类型：

块数据、流数据、批数据、优先数据、带外数据、紧急数据、编码数据。

实现数据传输的子功能：

• 对齐
• 分段和合段
• 拼装和分离
• PDU的装配与拆装（封装/解封装）
• SDU编码与解码
• 加校验和
  以（n）数据的全部或部分作为输入，产生一个固定大小的校验和作为输出。
• 抖动补偿
  使得协议能接受任何类型的通信量模式的SDU数据流作为输入，产生一个连续的SDU流作为输出。
• 带外数据、紧急数据的发送和接收

1.3 差错控制

差错：丢失、重复、乱序等。
(n-1)通道提供的数据通道的可靠性越高，则n层协议需实现的差错控制机制则越少。

• 序号
• 确认
• 计时器
• 重传

序号：

序号是确认和重传的基础，此外序号可用于流量控制。

1）三种不同的产生方式

• SDU序号
  对每个SDU都编号，从SDU序号得到PDU的序号。若某个SDU被分段携带在多个PDU中，应附加一个SDU分段号。
• PDU序号
  对PDU连续编号，不管它们携带的SDU的数据量。
• 字节序号
  对SDU的每个字节编号。PDU的序号来自与它所携带的SDU的第一个字节序号和最后一个字节的序号。

2）如何防止序号重复

使用一个非常大的序号空间。
使得在数据单元从一端到另一端的最大可能延迟时间L内，所有从源点发送出去的新数据单元都有不同的序号。

3）序号空间的大小与信道特点、确认方法、流量控制方法和PDU中的数据字段长度有关

• 如果信道的质量比较好，则序号空间要求比较大，从而可以连续发送多个数据单元，提高协议效率
• 采用周期性确认，序号空间就不一定要很大
• 在停止等待协议中，只需要0和1两个序号即可
• 一般来说，序号空间的大小与数据字段的长度成反比

确认：

接收者显式地通知发送者所发送的数据的接受情况

1） 被确认的对象

• PDU
• 字节

2）确认的情况

• 已正确到达
• 还没有收到
• 收到但有错

3）确认分为三种类型

• 肯定确认（Ack）
• 否定确认（Nak）
• 选择确认（Select Ack）
  指示收到的和没收到的PDU

4）两种发送方式

在一种协议中，通常两种确认形式并存。

• 独立确认
  使用一个确认PDU来携带确认信息。可随时发送。
• 应答携带
  将确认信息放在数据PDU中发送，可提高协议效率，要求接收方有数据发送时才能发送确认。

5）如何标识被确认的对象

用被确认的数据 PDU或字节的序号来标识

6）累计确认

如果否定确认或肯定确认的语义是表示所给定的序号之前的所有序号(包括或不包括本序号)的数据PDU都已被成功地接收了，则该确认又称为累计确认。

计时器：

检测数据PDU、确认PDU或重传请求信号的丢失。

1）超时值的设置

• 依赖于PDU的往返时间RTT
• 使用算法，动态估计往返时间和定时值

2）计时器超时值设置不当会导致什么后果？

如果超时值设置太短，连续大量的数据重传，严重情况下将加剧网络的拥塞程度，出现更多数据丢失 ；
如果超时值设置太长，出现数据丢失而得不到及时纠正，也会降低协议的性能。

3）TCP协议中的计时器

• 重传计时器
• 坚持计时器
• 保活计时器
• 时间等待计时器

重传：

发送者重传：

• 由确认PDU所指出的数据PDU
• 重传计时器超时仍未收到确认的数据PDU

1）基于滑动窗口的重传方法

• 回退n帧
  接收方直接地丢弃所有不按序到达的数据PDU。
  发送方从第一个否定的确认或发生超时的时刻所指出的数据PDU的序号开始，重传所有后续数据PDU。

• 选择重传
  发送方只重传否定确认、选择确认和超时的时刻所指出的那些数据PDU

1.4 流量控制

指“接收端控制发送端的数据发送速率以消除接收端缓存溢出的可能性，并使网络不致过载”

1）为什么使用流量控制？

• 接收方接受能力有限
• 缓存不够
• 处理能力不够

2）举例

• 停等协议
• 滑动窗口

1.5 拥塞控制

在某段时间，若对网络中某一资源（链路容量、交换节点中的缓冲区、处理机）的需求超过了网络所能提供的可用部分，网络的性能就要降低。这种情况就叫做拥塞(congestion)。

1）拥塞控制的主要功能

• 防止网络因过载二引起吞吐量下降和延迟增加
• 在互相竞争的各用户之间公平地分配资源
• 避免死锁：直接死锁，重装死锁
  直接死锁-由互相占用了对方需要地资源而造成地死锁。
  重装死锁-由于分组不完整无法交付给主机产生地死锁。

2）拥塞控制与流量控制地区别和联系

区别：
流量控制只在一对给定的发送方和接收方之间，控制发送方以不超过接收方处理能力的速率发送数据。
拥塞控制是一个全局性的过程，涉及到网络中所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。

联系：
流量控制限制了进入网络中地信息总量，可以在一定程度上减缓拥塞地作用。

2. 其他功能

• 无活动控制
• 通信量（流量）监控
• 通信量填充（防止通信量分析）
• 通信量整形
• 路由选择
• 媒体访问控制

七、协议元素

协议三要素

语法、语义、同步

协议的主体

状态-事件转换机制

协议六元素

并不是所有协议都必须包含以下六种元素。多个协议功能组成一个完整的协议之后，这六种元素一般使必须的。

元素之间的有机联系：在什么协议状态下，在什么输入事件驱动下，调用什么协议过程；协议过程在什么条件下(谓词)，采取什么协议动作(操作)，输出什么事件或修改哪些协议状态和变量。
在上述元素中，通常用状态变迁表或状态转换图来描述协议的状态、事件、操作和谓词。

• 服务原语和服务原语时序
• 协议数据单元PDU和PDU交换时序
• 协议状态
• 协议事件
• 协议变量
• 协议操作和谓词

1. 服务原语及其时序

一般用服务规范(Service Specification)来定义和描述N层协议向外部所提供的服务。
服务规范定义了服务用户和服务提供者之间的交互作用的规则，包括：服务原语和服务原语时序。
N 层协议的服务原语和原语参数详细准确地描述了N层协议和它的服务用户之间的接口。

1）根据服务原语对服务的分类：

1.需要证实的服务
2.不需要证实的服务

2）一个完整的服务原语通常包括

原语名字、原语类型、原语参数

原语

2. PDU及其时序

N层协议的PDU从语法和语义上详细准确地定义了n层协议实体之间交换的信息（PDU编码格式/协议使用的词汇表）。

3. 协议状态

• 局部状态：单个协议实体在某时刻的执行情况
• 全局状态：参与执行某种协议功能的所有协议实体的状态总和。包括（n-1)层通道。

N层协议必须定义所有的协议状态。

4. 协议事件

1）根据用途分类

• 输入事件
  a.收到一个PDU
  b.收到n层服务用户的一条服务原语
  c.内部事件（如计时器超时）
• 输出事件
  a.发送一个PDU
  b.向n层服务用户发出一条服务原语

2）根据事件的作用范围分类

• 通信事件
  收发服务原语或收发PDU，又可分为同步事件和异步事件。
• 内部事件：如计时器超时。

3）协议事件的三个性质

• 成对性
  指一个事件的发生总是伴随着另一个事件的发生。通信事件成对，内部事件不成对。
• 原子性
  指事件要么不发生，一旦发生就一定完成。
  具有原子性的事件被称为原子事件。
• 时序性
  指发生的事件在时间上是有先后顺序的。
  事件时序性决定了状态的时序性。

5. 协议变量

保存协议运行的历史数据、运行参数的变量，以及协议机制本身所设置的变量。

常见的协议变量：

• 发送序号变量
• 接受序号变量
• 重发时间间隔变量

6. 协议操作和谓词

每种协议功能都是通过一组协议过程的执行来实现的。
协议过程：协议在输入事件的驱动下，在一定条件下，执行一系列的操作或动作。

一定条件：
这些约束条件涉及协议参数、协议变量、协议运行环境等。将描述这些约束条件的语句称之为谓词(predicate)。

这些操作包括：
-产生输出事件
-清楚和设置计时器
-修改协议变量
-改变协议状态

原子过程：
原子过程包含多个协议操作，并且过程一旦启动之后，所有包括的操作一次性完成，不经历中间协议状态，不被其它过程打断。
一般来说，在协议运行时，可将它从一个状态到另一个状态的转换处理成原子过程。

八、协议组织

协议组织是指将相关协议功能和协议元素组成一个完整协议的过程。

这个过程涉及以下技术和方法：

• 协议层次化
• 协议阶段化
• 协议分类
• 协议的运行方式

1. 协议层次化

如果n层协议的功能和结构仍然很复杂，可将n层协议的众多功能进一步分成多个子层。
子层的划分可使复杂协议的结构变得清晰，有利于协议的设计、验证、实现和测试。但是，子层的划分可能降低协议性能。

2.协议阶段化

可将n层协议分成多个运行阶段，每个阶段只涉及到一部分协议功能。如OSI体系结构的运输层协议的正常运行被分为三个阶段：连接建立阶段、数据传输阶段、连接释放阶段。

3.协议分类

由于不同用户的需求以及协议的运行环境的不同导致协议的复杂性。因此，可以将协议分成不同类别或不同级别，每类协议只适用于特定用户和特定环境，那么复杂协议就会变得简单。

4.运行方式

协议运行方式有三种：

• 协议交替 - n层内的多个协议或一个协议的多个类别或一个协议的多个协议功能交替活跃
  可在不同时间内适用于不同用户和不同通道的协议环境。相比并发和并行性能低。
• 协议并发 - 同时活跃，并发运行
  可在同一时间内适用多种协议环境
• 协议并行 - 同时活跃，同时运行
  协议性能更好

九、协议文本

协议文本是协议设计阶段的最终结果。
协议文本中，最重要、最主要部分是协议元素的描述。必须对每一项协议元素作出准确、清晰、无二义性的定义。此外，协议的各元素是有机联系的，协议文本应清晰表达这些关系。

十、协议设计方法

1. 设计原则

• 简单
• 模块化
• 有界性
• 健壮性
• 一致性

其中，最基本的是：简单和模块化。

2. 分层的原则

• 当需要有一个不同等级的抽象时，就应当有一个相应的层次
• 每一层的功能应当是非常明确的
• 选择的层与层的边界应该使通过这些边界的信息量尽量地少
• 难点：层次太少会使每一层协议太复杂，太多则在描述和综合各层的系统时难度较大。

3. 自顶向下的设计方法

协议设计方法

第三章 协议形式化描述技术

• 有限状态机FSM
• Petri网
• SDL

一、形式化技术的产生

过去人么习惯使用自然语言描述协议。
优点：方便易懂
缺点：不严格、不精确、结构不好、没有描述标准、有二义性。不同的人对协议描述的理解不同。难以进行验证、实现和测试自动化。

解决办法：形式化技术

是将协议工程各阶段在技术上衔接起来的纽带。

形式描述模型FDM

• 状态变迁模型：
  有限状态机FSM
  扩展的有限状态机EFSM模型
  通信有限状态机CFSM模型
  Carl Adam Petri的Petri网
• 时态逻辑TL
• 进程代数：
  通信系统演算CCS（以进程代数为基础）
  通信顺序进程CSP（以CCS为基础）

形式描述语言FDL

• ISO制定的Estelle和LOTOS
• CCITT制定的SDL
  ……

模型与语言

模型：
对象或系统的抽象（OSI/RM）
描述对象或系统的方法或技术（FSM/PetriNet）

形式语言：
具有严格的语法和语义；
可精确、完全表述协议的功能及行为；
以一种或多种数学方法或形式模型为基础。如SDL基于扩展的FSM和抽象数据类型。

二、FSM

1. 有限状态机FSM的几个概念

状态（State）

指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。

事件（Event）

指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。

转换、转移、变迁、迁移（Transition）

指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生且满足某个特定条件时进入第二个状态。

动作（Action）

指的是状态机中可以执行的原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。

2. 形式化定义

FSM和非确定FSM，可以看成仅接收输入并发生状态改变，但无任何输出的自动机。

FSM的形式化定义

对于不确定的有限自动机NFA，其下一时刻状态为一个状态子集。

3. Moore机和Mealy机

具有输出的自动机器模型按照输出的不同分成两类：

• Moore 机：输出与状态有关
• Mealy机：输出与状态和输入有关

Moore机在接收输入串的过程中不断改变状态并在每个状态上有字符输出。
Mealy机只是在接收输入串的过程中不断改变状态，并且字符输出与当前状态及输入串有关。

有限状态机可看作是Moore机的一个特例
Moore机可看作是Mealy机的一个特例

Moore机FSM形式化定义

Mealy机FSM形式化定义

4. 如何设计FSM

• 理解系统的功能：
  通过系统的需求与实现的目标，理解系统的运转过程
  可以通过系统的流程图，划分出系统的各功能模块
• 确定FSM的设计策略
• 整理出系统的全部输入和输出
• 构造状态空间
  从系统中抽象出全部的系统状态，进行状态分割，构造FSM的状态空间
• 明确系统各状态之间的迁移关系
• 明确各状态迁移关系所对应的输入事件与输出事件
• 确定FSM
  画出系统状态迁移图或状态迁移表，明确系统FSM的所有要素
• 状态空间简化
  FSM状态空间的简化，尽可能使状态重复利用，消除冗余的状态，简化设计，降低系统复杂度，提高可靠性
• 系统编码
  对输入、输出、各状态及各状态转移关系根据设计策略进行编码
  其它的设计阶段

5. FSM的优点

• 简单性
• 可预测性
• 易于实现
• 易于测试

6. 停等协议

停等协议甲乙双方

将甲乙两方各自的有限状态机合在一起，用一个有限状态机来描述整个系统。这回导致状态数目大大增加，因此需要合并一些状态，考虑一些次要的细节。

合并后的状态变迁图

7. FSM的简化

• 状态层次化
• 使用原子过程
• 使用协议变量
  可大大减少状态机的状态数。
• 隐藏内部协同事件
• 简化通道FSM
  如果n层协议采用同步通信方式，那么不管(n-1)层通道是否是缓冲通道，都可以处理成非缓冲通道；
  如果报文传送时间和延迟时间对协议机制无影响，或者只影响协议变量的值，那么非缓冲通道可处理成空通道。

8. FSM的错误模型

可达性分析：
死锁
活锁
无限分支
不可达状态

其他：
输出错
转移错
输出转移错

9. EFSM

FSM的缺点：

• 处理复杂问题时可能发生状态空间爆炸
• FSM可以很好地描述状态间地迁移特性，但无法很好地描述输入输出间地变换特性
• FSM只反映协议事件和协议状态之间地关系，不能表达其他协议元素

FSM扩展模型地目的：

• 增强FSM描述能力
• 简化描述
• 使各状态之间地变迁清晰化
• 最终提高对局部以至整个模型地描述与分析能力
• 可被用作为以后开发者描述解决方案地工具

其中，明显的缺点为：
FSM不能方便地描述对变量地操作
缺少描述任意数值的传送能力

从两个方面对FSM进行扩展：

• 变量
  如果变量的取值范围是有限的，则变量的加入并没有增加FSM的计算能力。 可以用有限状态机来描述一个取值范围有限的变量。
  优点：
  变量地引入丰富了FSM地状态变迁函数地表达能力，还可以减少FSM的状态空间

• 引入一组操纵变量地算术和逻辑操作符

三、PetriNet

Petri网是一种图形化的数学工具，适合于描述和分析并发、异步、分布式的系统，特别便于描述系统中进程或组件的顺序、并发、冲突以及同步等关系。
Petri网也是一种状态变迁模型，它允许同时发生多个状态变迁，因而Petri网是一种并发模型。可用来描述通信系统中各异步组件之间的关系。

Petri网所处的状态是由标记的分布来决定的。

1. Petri网形式化定义

Petri网的四元组

2. Petri网的状态变迁

发生变迁的条件：

• 必须有1个或多个变迁满足变迁条件
  变迁条件：
  某个变迁tj的所有输入位置中都必须有标记存在，并且当输入位置有多条弧线指向这个变迁时，该输入位置也至少具有和弧线数相等的标记数；
  所有输入位置中的标记数都必须大于或者等于该输入位置指向tj的弧线数。

• 必须发生点火
  所谓点火就是发生了一些事件(1个或多个)，而这些事件所对应的变迁满足变迁条件。

标记移动规则：

发生点火后，标记要重新分布。

• 从点火的变迁tj的所有输入位置中均取出标记，每个位置取出的标记数等于该位置指向点火的变迁tj 的弧线数；
• 然后再将标记送入tj 的所有输出位置中去，送入每个位置的标记数等于点火的tj 指向该位置的弧线数。

一个简单的例子：

图1

图2

图3

状态变迁类型：

• 顺序变迁
  只有t1点火后t2才能点火
• 并发变迁
  t1和t2可同时点火
• 互斥变迁
  t1和t2只能有一个点火。一个点火后另一个就不能再点火了。

3. PetriNet的扩充

• 基于标记和位置的扩充
  一个位置中的不同标记用不同的名字或标识号来表示——有色Petri网
• 基于输入函数和输出函数的扩充
  允许每个位置减少或增加多个标记，并再弧线上标上增加或减少的标记数
• 基于变迁的扩充
  在变迁上标明谓词和动作——谓词-动作Petri网

4. PetriNet的性质

• 行为性质 - 与初始标记量有关的性质
• 结构性质 - 与初始标记量无关的性质

行为性质：

• 可达性
• 有界性
• 活性
• 可逆性
• 可覆盖性
• 可持续性

1）可达性

• 可达的
  如果存在一系列变迁t1, t2, …, tn的发生使得Petri网的标记向量转换为Mn，则称标记向量Mn是从M0可达的 。
• 变迁的引发序列
  将M0 t1, M1 t2, M2 t3, …, tnMn称为变迁的引发序列，记为σ，或简记为σ=t1, t2, …, tn。
• 可达标记向量集
  所有可达的标记向量形成一个可达标记向量集，一般记为R(M0)。
• 引发序列集
  从M0出发的所有可能引发序列形成一个引发序列集，一般记为L(M0)。

2)有界性

• 有界性
  在一个Petri网中，如果存在一个非负整数k，使得从M0开始的任一可达标记向量中的位置p上的标记数都不超过k，则称位置p为k有界。
  如果Petri网中每一位置都是k有界的，则称该Petri网为k有界。
  有界性意味着位置中的标记数量不会无限地增加。
• 安全性
  如果位置p为1有界，则称位置p是安全的。如果Petri网中每一位置都是１有界的，则称该Petri网是安全的。

3）活性

活性：反映的是系统中无死锁的特性。

• 潜在可引发的
  在一个Petri网中，初始标记向量为M0，如果存在一个标记向量M∈R(M0)(可达标记向量集)，使得变迁t使能(满足变迁条件)，则称t是潜在可引发的。
• 变迁在M0下是活的
  如果对任何M∈R(M0)，变迁t都是潜在可引发的，则称t在标记向量M0下是活的。即从M0可达的任一标记向量出发，都可以通过执行某一变迁序列而最终引发变迁t。
• Petri网是活的
  如果所有变迁t都是活的，则称该Petri网是活的，或者称M0是网的活标识。

变迁t的活性等级划分：
L0 - 没有任何一个变迁序列可以引发变迁t，即该变迁是“死的”
L1 - 在某些变迁序列中，变迁t至少被引发一次
L2 - 在某些变迁序列中，变迁t至少被引发k次
L3 - 在某些变迁序列中，变迁t可无限次被引发
L4 - 在每个变迁序列中，变迁t至少被引发一次

4）可逆性

在一个Petri网中，如果存在一个引发序列σ=t1, t2, …, tn，使得从该Petri网的任一可达标记向量M出发可以返回到初始标记向量M0，则称该Petri网是可逆的。

5）可覆盖性

在一个Petri网中，对于标记向量M，如果存在一标记向量M′，任一位置p，都有：位置p在M′中的分量的值都大于等于该位置在M中的分量的值，则称标记向量M是可覆盖的。

6）可持续性

在一个Petri网中，如果对于任何两个满足变迁条件的变迁，其中一个变迁被引发以后，另一个变迁仍然满足变迁条件，则称该Petri网是可持续的。

7）公平性

在一个Petri 网中，对于两个变迁t1, t2，如果其中一个变迁可以引发 而另一个变迁不可引发的这种情况出现的最大次数是有界的，称这两个变迁具有有界公平关系。
如果该Petri网中，任意一对变迁都存在有界公平关系，则称该Petri网为有界公平网。

结构性质：

• 结构活性
  存在活的初始标记向量M0
• 结构有界性
  Petri对任何初始标记向量都有界
• 可重复性
  存在一个初始标记向量和一个引发序列，使得所有变迁被引发无限次，则称该Petri网为可重复；
  如果使得部分变迁被引发无限次，则称该Petri网为部分可重复。
• 相容性
  如果存在一个初始标记向量M0和一个引发序列σ∈L(M0)，使得所有变迁至少被引发一次，则称该Petri网为相容的；
  如果使得部分变迁至少被引发一次，则称该Petri网为部分相容的。
• 结构有界公平性
  对于任何初始标记向量，如果两个变迁之间总存在有界公平关系，则称这两个变迁具有结构有界公平关系；
  如果一个Petri网对于任何初始标记向量都是有界公平的，则称该Petri网为结构有界公平的 。

5. Petri网在协议描述中的应用

• 停等协议

不编号的停等协议

编号的停等协议

• 读写

  
  
  读写进程

第四章 协议形式描述语言（SDL）

SDL是基于扩展有限状态机和抽象数据类型的混合技术。SDL既可描述系统的概要设计，亦可描述系统的详细设计。

一、SDL的三种语法形式

1. 图形表示的SDL/PR

较适合于描述系统的结构和控制流

2. 用文字短语表示的SDL/PR

较适合于机器处理

3. 程序语言形式的SDL，X.250

二、SDL系统结构

1. 概述

在SDL中，整个系统由多个互连的抽象机（扩展的有限状态机FSM）所组成。
每个抽象机的动态行为由其他抽象机或环境的交互和对交互数据的操作来描述。

SDL/PR使用的主要符号：

SDL/PR使用的主要符号

2. SDL的静态结构

一个SDL应用的静态结构由系统、功能块、进程、过程和通道构成。

SDL的静态结构

1）系统

规范所描述的对象称为一个系统。
根据系统与环境之间是否有交互，将系统分为开放的和封闭的。

一个系统的规范描述由以下部分组成：
所有通道、信号(Signal)、信号表(Signal List)、预定义的数据类型与/或宏(macro)的定义；一个或多个功能块。

2）功能块

功能块含有进程，并用来构造系统。功能块通过通道互连，并通过通道连接到系统边界。
在描述功能块时，进程、过程(Procedure)、服务类型、数据类型和信号均可作为功能块描述规范的一部分。

3）进程

可保留和处理数据，数据受进程的局部变量(由该进程定义)约束。
利用信号，数据值可在进程之间传送，也可传送给环境或从环境接收。

4）通道

通道充当功能块之间以及功能块与系统边界之间传输信号的媒介。既可以是单方向的，也可以是双方向的。

在SDL中，将系统、功能块、进程等称为代理。各个代理用块图来表示，一个代理可以对应多个块图。

三、SDL对系统动态行为的描述

1. SDL的结构化概念

系统中的每一个功能块由一组进程或一组子功能块组成，进程间通过信号路由(Signal routes)或功能块的子结构(Substructure)相连接。
子功能块又可由一组进程或一组子功能块组成。这样可得到一个系统的分级多层描述：功能块树 (Tree of Blocks)

2. 动态行为描述

• 各功能块包含若干个进程，SDL系统的动态行为具体表现为各进程的实例的并发操作 (Instance，即进程的一次活动，用PId来表示) 。

• 进程的状态与动作是用扩展的FSM来建模的。
  1.进程状态的变化受外来信号激励，同时，进程也可向环境返回响应信号。
  2.一个进程可同时收到多个信号。
  SDL设置了队列以暂时存放这些信号(一般采用先进先出的方式)。
  3.进程也可自行处理保留信号。
  保留信号是指在某些状态下需等待其他信号到达并处理之后才能处理的信号。

四、SDL中的数据

在SDL中，数据的定义一般基于抽象数据类型。
“抽象数据类型”是指其定义并不描述(数据)类型是如何实现的，而仅仅描述当将操作符(Operators)应用到该类型的数值上时产生何种结果。

1. SDL预定义数据类型

SDL定义了一些预定义的数据类型，
如布尔(Boolean)、整数(Integer)、自然数(Natural)、实数(Real)、字符(Character)、字符串(Charstring)、进程标识符(PId)、时刻(Time)、持续时间(Duration)。
此外，SDL还预定义了一些产生器(Generator)，
如数组(Array)、串(String)、计时器(Timer)和幂集(Powerset)等。
这些预定义的数据类型可在任何级别上的SDL描述中使用。
用户还可用上述数据类型自行定义其他的数据类型。

2. 类

在SDL中，类(Sort) 是值的集合。集合中的元素个数可以是有限的，也可以是无限的，但不能为空。
一般来说，SDL中的数据类型定义包括三个部分：类定义，操作符(Operators)定义和等价式(Equations)定义。

1）类定义

例：Boolean类定义

Boolean类定义

• 词
  值与操作符的组合构成词

• 等价式
  给出规则，说明给定类中的哪些词表示同一个值

• 等值类
  由值相等的词所构成的集合，称为等值类。将词的集合分为多个子集。

第五章 协议验证技术

一、验证的含义

正确性
完整性
一致性

验证协议的实现 一致性测试

Verification 在功能方面验证
Validation 语法方面验证

二、验证的方法

1. 非形式化验证

主要通过遍历和代码检查

2. 形式化验证

以形式描述技术为前提，主要将形式描述技术与推理技术结合。
一方面可以获得无二义性的协议规范，另一方面可以借助计算机辅助工具来帮助实施自动或半自动验证。

• 模型检测
  基于状态搜索

• 演绎验证
  基于定理证明

1）模型检测/模型检查/模型检验

本质上是用严密的数学方法来验证设计是否满足预设的需求，从而自动化地发现设计中的错误。是一种检查给定模型是否满足某一逻辑规则的方法。

• 基本思想
  (1)用状态迁移系统(S)表示系统的行为，用模态/时序逻辑公式(F)描述系统的性质。
  (2)“系统是否具有某种期望的性质”就转化数学问题“状态迁移系统S是否是公式F的一个模型？”
  公式表示：S |= F?

• 过程描述
  1.建立模型
  2.描述系统性质
  3.验证

• 模型检测方法
  最常见方法：可达性分析、不变性分析
  特性：
  能给出反例
  自动化程度高
  问题：
  状态空间爆炸

2）演绎验证方法

定理证明方法：

• 步骤
  1.将实现方案和功能描述都转换为一种形式逻辑，如命题逻辑、一阶逻辑(First Order Logic, FOL)、高阶逻辑(Higher Order Logic, HOL)等
  2.建立公理系统，作为验证的依据，并将协议性质构造成一组代数定理
  3.根据公理系统，使用定理证明器，通过逻辑推理、逻辑归约等手段，构造证明过程，证明实现方案和功能描述等价

• 问题
  入门难，前两步难

三、协议性质

协议验证的最主要任务是检查协议是否满足规定的协议性质。

• 一般性质
• 特殊性质

也有文献将其分为安全性和活动性。
活动性体现在终止性和进展性两个方面。

1. 一般性质

• 可达性
• 没有死锁
• 没有活锁
• 弱活锁
• 时间相关的活锁（临时阻塞）
• 无状态二义性
• 有界性
• 可恢复性或自同步性
• 互斥性
• 公平性
• 终止或进展

1）可达性

协议的各种可能状态之间的可达关系。

2. 特殊性质

• 完整性
• 一致性

3. 一般性质和特殊性质

协议验证着重于一般性质
协议测试着重于特殊性质

四、可达性分析

检查协议描述中是否有不可达，死锁、未定义、活锁等协议模型错误；包括状态穷举，状态随机枚举，状态概率枚举等方法。

可达性分析是最常用的协议验证方法,它试图产生和检查协议所有或部分可达状态。

• 全局状态(Global state): 协作的协议实体以及连接这些协议实体的通道的整体状态。
• 可达状态: 指协议从初始状态开始经历有限次变迁之后可到达的状态。
  所有可达状态构成可达图

可达性分析的三个重要技术：
怎样找出所有可达状态，构成可达图。
怎样检测死锁、活锁等协议错误。
怎样解决状态空间爆炸问题。

可达性分析练习

1. 可达性分析原理：

采用穷举法检查同一层内两个或多个协议实体间所有可能的交互所产生的全局状态。
从一个给定的初始状态开始，触发所有可能的变迁(用户命令、超时、消息发送、接收等)，产生新的全局状态。
对每一个新产生的状态重复执行上述过程直到没有新的状态产生(某些变迁将导致系统返回到已产生的状态)。
对于一个给定的初始状态，这种分析能够确定协议可能产生的所有结果。

2. 可达性分析算法

• 穷尽性可达性分析算法
• 受控部分搜索算法
  1.限制深度法
  2.散开搜索法
  3.定向搜索法
  4.概率搜索法
  5.随机选择法
• 随机模拟算法

1）穷尽性可达性分析算法

穷尽性可达性分析算法

• 深度优先与广度优先
  当发现一个错误时，在广度优先算法中，必须依据从状态集合A 中得到的信息来重构从初始系统状态开始的路径。(先进先出， W中无法按执行序列保存之前的状态)；
  在深度优先算法中，一个重要的优点是，当发现错误时，算法能从初始状态开始通过一系列有效的状态转换到达错误点。无需重构从初始系统状态开始的路径，因为这个序列已被集合W中的堆栈排序中隐含定义了。(先进后出， W中按执行序列保存了之前的状态)。

先广搜索的优点：优先发现执行序列短的错误状态；
先深搜索方法的优点之一是占用存贮空间小。
假定每个状态有两个后继状态，算法执行m步之后，对于先深搜索方法，W的长度为m；而对于先广搜索方法，W的长度为2m。

2）受控部分搜索算法

一般来说，受控部分搜索算法较全局搜索方法有效和可行。但是，这种方法不能保证协议无错。通常需要执行多次才能得到比较可信的结果。

3）随机模拟算法

随机模拟/随机遍历

随机模拟算法

随机模拟算法与协议系统的大小和复杂性无关，即使是无限大的系统，也可以应用。因此，对于复杂的验证问题，这种算法也许是唯一可用的方法。

4）三种算法的比较

• 穷尽性可达性分析算法的优点在于可以证明协议中没有错误，但问题在于其应用范围有限。（系统状态数目非常大时可能发生状态空间爆炸/对于复杂的协议搜索质量会下降）
• 受控部分搜索算法的目的是证明错误地存在而不是证明没有错误。它在一定程度上能够解决空间爆炸问题。其缺点是：协议中的错误的可能位置难以预测；无法保证其状态空间大小与可用内存相匹配；有效搜索的部分状态空间大小是协议相关的，只能通过实验确定；为了寻找最优方法，需要按不同的选择策略多次验证。
• 随机模拟算法与协议系统的大小和复杂性无关，即使是无限大的系统，也可以应用。因此，对于复杂的验证问题，这种算法也许是唯一可用的方法。其缺点是没有明确的终止，无法判断是否已访问系统的所有可达状态，因此，只能发现协议中的错误，而不能证明协议中没有错误。

3. 基于可达性分析的协议错误检测

• 死锁
• 非定义的输入事件
• 无意义事件
• 活锁

4. 状态空间爆炸问题的解决

• 部分搜索算法
• 部分规范描述和验证
• 选择大的动作单元
• 分解或划分
• 按断言来分类状态

五、不变性分析

如果一个系统的某个性质能用一个确定的逻辑表达式描述，并且恒为真(不随系统的状态变化或执行序列而改变)，那么这个性质称为系统的不变性质，简称为系统不变性(system invariance)。

• 协议不变性分析的两个工作：
  1.完全正确地找出系统的不变性质
  2.验证不变性表达式是否恒为真

1. 不变性分析的途径

• 不变性证明系统（通常采用归纳法）
• 不变性监测系统

1）不变性证明系统

采用归纳法：
验证初始状态的不变性表达式是否成立；
假定某个状态的不变性成立，验证从该状态开始的所有相关事件过程中不变性是否成立。

2）不变性监测系统

借助监测软件和监测方法对模拟运行或符号执行中的协议进行不变性校验的过程称之为不变性监测。

第七章 一致性测试技术

验证一项新的协议实现，通常需要进行多项测试。一般要考虑以下四个方面：

• 一致性测试(conformance testing)
  一致性测试旨在检测所实现的协议实体(或系统)与协议规范的符合程度(而验证则是检查形式化规范的逻辑正确性)

• 互操作测试(interoperateability testing)
  检测同意协议的不同实现版本的互通能力和互操作能力

• 性能测试(performance testing)
  非功能测试，主要检测协议实体或系统的性能参数。

• 鲁棒性测试(robustness testing)
  检测协议实体或系统在各种恶劣环境下运行的能力。

一、 一致性测试与验证

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

二、 功能测试与结构测试

• 功能测试
  协议实现是否实现了协议规范的所有功能；协议实现是否可以正确地以与协议规范一致的方式拒绝错误输入。
  问题：复杂性；难以标准化。

• 结构测试
  协议实现的控制结构与规范的结构是否一致。如果二者的状态集等价并且状态转换相同，则二者具有相同的结构。
  问题：无法完全检查，常需要增加一些限制条件。

三、 一致性测试的前提

假定协议标准本身是正确的。

通过一致性测试可以给用户提供两个信息：
通过了一致性测试的协议实现，具有协议所要求的各种能力。
在具有代表性的通信实例中，被测试的协议实现的外部特性与协议标准的要求一致。

四、一致性测试要求

• 静态一致性要求
• 动态一致性要求

DCR和SCR
动态一致性是指协议规范中规定的通信实例中的协议实现所必须呈现的外部特性的组合或允许的各种选择性组合；
而静态一致性是指协议规范中为了使协议实现能够互连而定义的功能类别、功能单元的分组以及选择性功能等。

五、一致性测试级别

ISO 9646将协议一致性测试分为四级，由低到高分别为

• 基本互连测试
• 能力测试
• 行为测试
• 一致性分解测试

行为测试可分两级：
覆盖性测试：只要求测试序列历经IUT的所有变迁至少一次即可。
穷尽性测试：要求检查每个变迁的前后状态。

六、一致性测试模型

七、一致性测试流程

八、一致性测试方法

一致性测试方法决定了 测试集的产生和描述方法、测试执行系统的结构 等。
ISO 9646中定义了四种标准的抽象测试方法：

• 本地测试法(Local Mehtod)
• 分布式测试法(Distributed Method)
• 协调测试法(Coordination Mehtod)
• 远程测试法(Remote Method)。

本地测试法：

本地测试法

分布式测试法：

分布式测试法

协同测试法：

协同测试法

远程测试法：

远程测试法

上述这几种测试法是最基本的，适于单层协议测试，有许多变种，如渡船测试法(Ferry Method)、多方测试法及骑跨式(Astride)测试法等。

九、测试集

测试集包括两部分：
测试序列
测试数据

对同一测试序列的事件施加不同的测试数据(即测试事件携带不同参数)，就产生不同的测试例。一个测试序列对应多个测试例。

测试集具有层次结构：

1. 测试集由多个测试组组成。每一测试组覆盖某一类测试目的。
   比较常用的测试组划分方法是根据协议的不同状态，为每一状态的测试目的集合构造一个测试组。测试组由多个测试例组成，每一测试例针对某一测试目的。
2. 利用测试步(Test Step) ，可以将测试例模块化。所有测试步都是按照测试事件的顺序或其它较小的测试步来定义的，因此，全部测试步等效于测试事件的序列。

3. 测试事件是测试例和测试步的最小单位，是测试步内规范的基本单元。

   
   
   测试集的层次结构

十、测试表示方法

描述测试系统和IUT的行为。

通用的协议测试表示方法需满足的要求：

1. 所描述的测试集应该是系统独立的。
2. 可以描述任一协议的一致性测试集。
3. 能为测试集的设计人员提供自动或半自动支持工具以加快测试集开发过程。
4. 降低整个测试集的开发和维护费用。
5. 提高协议一致性测试集的标准化程度，以增强开放系统之间的互操作性。
6. 易于学习和掌握，对于测试操作人员而言，易于理解。

描述测试集的方法：

• SDL、ESTELLE、LOTOS
• 编程语言
• 树型记法、表型记法
  易于被测试人员理解。ISO将二者综合，提出树表组合记法TTCN。

TTCN：

TTCN提供两种表示方法：树型记法和表型记法
树型记法主要用于描述测试事件之间的时序关系，即描述协议的动态行为。
表型记法主要用于简化所有静态数据的表示，如数据类型、PDU和ASP的格式、与测试事件相关联的测试判决等等。