7协议工程之协议实现技术.ppt

第七章协议实现技术,7.1概述计算机网络各层协议实现结果的集合形成计算机网络软件和硬件。计算机网络软件和计算机操作系统密切相关，它往往是操作系统的一部分，计算机网络硬件和计算机硬件系统密切相关，它是计算机I/O系统的一部分。图7.1为DECDNA在VAX/VMS中的实现结构。DNA（DigitalNetworkArchitecture）是DECVAX/VMS之中实现后软件和硬件的总称为DECNET/VMS。,第七章协议实现技术,第七章协议实现技术,DNA的物理层和数据链路层协议实现于网络适配器（deviceadaptor）中，DECnet/VMS包括许多网络适配器，即DNA支持许多种低层通信协议。DNA的网络层和传输层协议主要实现于伪驱动程序NETDRIVER中，它和网络适配器的设备驱动程序(devicedriver)接口。DNA的高层协议以网络目标模块形式或实用程序的形式实现，DECnet/VMS包括许多这样的目标模块（object）和实用程序(utility)，这表示它向用户提供丰富的网络服务。这里，NETDRIVER和devicedriver是VMS内核一部分，DNA高层和VMS的文件系统，作业调度，用户登陆（login）等密切联系，网络适配器是VAX硬件系统的一部分，计算机网络各层协议在其它机器和操作系统中实现形式和实现结构都类似于DECnet/VMS。,第七章协议实现技术,计算机网络协议是复杂的协议，将它们付诸实现更是一个复杂的技术过程，这是因为计算机网络硬件和软件与计算机硬件操作系统的关系非常密切的原故。一个计算机网络的研制要经历下述七步工作。(1)网络体系结构的制定网络体系结构（NetworkArchitecture）的制定包括许多决策工作：网络支持哪些通讯线路和局域网？向用户提供哪些网络服务？网络划分成多少层？各层的协议功能是什么？各层协议规范和服务规范是什么？,第七章协议实现技术,(2)实现环境的研究实现环境指计算机的机型和运行的操作系统。实现环境的研究是协议实现者必须进行的一项工作，这包括计算机硬件结构和I/O总线的详细了解，操作系统结构和操作系统服务的详细了解等等。(3)实现结构的设计在(1)和(2)的工作完成之后，协议设计者就可以着手网络实现结构设计。实现结构的设计包括一系列的决策工作：哪几层协议在网络适配器中实现，哪几层协议在操作系统中实现？操作系统的网络软件划分成几个进程，每个进程实现哪几层协议？如果几层协议在同一个进程实现时，各层协议之间怎样相互调用？为了提高网络软件执行效率和连接响应速度应采用哪些措施等等。,第七章协议实现技术,(4)各层协议实体之间通讯机制设计当n层协议和(n-1)层协议在不同的进程或驱动程序之间实现时，n层协议实体和n-1层协议实体之间通讯必须借助操作系统服务来实现。当n层协议和(n-1)层协议在同一个进程或驱动程序之内实现时，两层协议实体之间通讯可直接借助于程序设计语言(c,pascal)来实现。(5)数据缓冲方案的设计协议数据单元PDU(protocoldataunit)在各层协议实体之间的传递是通过缓冲器来实现的。数据缓冲方案的设计包括一系列的决策工作：缓冲器中的数据怎样传递？是否采用共享缓冲器方案？缓冲器定义多大？缓冲器怎样分配管理？缓冲器的分配管理怎样对网络流控制和交通拥塞控制施加影响等等。,第七章协议实现技术,(6)各层协议代码的产生协议代码可分为两部分：与实现环境相关的协议代码和独立于实现环境的协议代码。前者必须由协议实现者手工完成，后者可手工完成也可以借助形式语言的编辑程序（如ESTELLEcompiler）自动产生。(7)网络软件的调试由于网络软件的分布性，异步性和实时性，传统的静态调试工具是不适应的，因此设计者必须研制多种动态调试工具以提高网络软件调试效率。这些调试工具包括各种模拟环境，闭环测试软件，PDU追踪，时间标签，事件记录等。,第七章协议实现技术,限于篇幅，本章只讨论(4)、(5)、(6)步骤的有关问题，首先介绍协议代码半自动生成技术，然后讨论上下层协议实体之间通讯的实现方法，最后讨论数据缓冲技术。如果我们掌握了第(4)和第(5)步的设计方法，那么与实现环境相关的协议代码就可以手工完成了。计算机网络研制工作中第（1）、（2）、（3）和（7）步工作的讨论请参见文献资料42和34。,第七章协议实现技术,7.2协议代码半自动生成技术协议代码半自动生成技术试图将协议规范文本（用ESTELLE、LOTOS等语言描述)直接转换成协议代码（c.pascal等程序设计语言）。如果所产生的代码不需要人工修改就可以编译成机器可执行的程序，这是最理想的。但由于计算机网络软件和操作系统结合紧密，这实际上是不现实的。由协议规范直接转换的协议代码只能占全部代码的一部分，约50%左右33，这部分代码称之为独立于实现环境的代码，另外一部分代码由于和实现环境相关，必须由手工完成。协议代码的这种生成方法称之为协议代码的半自动生成技术。关于协议代码半自动生成技术是否值得深入研究的问题，人们尚有不同的看法。然而，半自动生成技术显然有如下一些好处：,第七章协议实现技术,（1）利用同一个翻译程序从同一个协议规范中产生的协议代码总是一致的，它不随协议实现者的不同而不同。这就是说，所有协议实现者都能够获得一份相同的协议代码。虽然这一部分协议代码只占总代码的50%左右，但它包括协议的主体部分。它确定了协议的所有逻辑关系，因此它为协议的不同实现版本的互连提供了良好的基础。（2）协议规范的更新修改不会给协议实现者带来太多的麻烦，它只要重新运行一次翻译程序就可以了。（3）由此减少手工编程的错误，缩短网络软件的开发周期，提高网络软件可维护性。,第七章协议实现技术,目前，世界上已开发了多种协议代码半生成软件，它们大都基于ESTELLE，LOTOS和SDL语言，翻译后的协议代码大都为C代码。下面简单介绍EDS（EstelleDevelopmentSystem）中协议代码半自动生成的基本过程33，它将协议代码半自动生成过程分为四步。,ESTELLE半自动生成过程可用图7.2表示，图中.e表示类型为.e的文件，.m表示类型为.m文件。,f,第七章协议实现技术,1.协议规范的预处理用形式描述语言描述的协议规范中往往存在许多没有具体数值的符号定义。例如用ESTELLE描述的AB协议中（参见第四章4.2.4)，常数low,high,retran-time未给出具体数值，预处理要求实现者给出具体数值。又例如，在ESTELLE:描述的AB协议中，数据类型定义U一data一type是含糊的(它用表示)，这要求协议实现者给出它的具体定义（如定义为stringofcharacters）。预处理要做的工作包括原语primitive的标识等工作。预处理的第二项重要工作是将协议规范文本(.e)分割成三个文件：模块描述文件(.m)，实现描述文件(.i)和格式描述文件(.f)。模块描述文件即为原协议规范中的模块头定义和模块体定义。实现描述文件将原协议规范中有关各模块的性质定义，模块之间组织关系描述，模块之间通讯机制描述等全局性内容抽取出来，形成一个描述整个协议的框架文件。格式描述文件完整地描述模块之间报文交换的格式，它也是从原协议规范文件中抽出来的。,第七章协议实现技术,2.翻译预处理后的协议规范直接送入ESTELLEcompiler翻译，翻译包括语法校对、C代码生成等工作。对模块体文件，翻译结果是对应于每一个ESTELLE模块体产生一个C代码的模块头文件(headfile)和一个C代码的模块体文件(bodyfile)。模块头文件包含模块体内所有数据结构和变量（如交互点ip和ep、队列等）。模块体文件包含模块体内所有函数、过程的代码，除模块体原有的函数和过程定义之外，模块体的每一个转换都翻译成过程。,第七章协议实现技术,第七章协议实现技术,第七章协议实现技术,3.手工程序的编写凡是与系统相关的部分（通讯机制、缓冲器管理、文件访问、访问控制等等)必须由协议实现者根据实现环境手工编写。4.执行代玛的产生上述所有C程序文件编译后链接成一个或几个系统可执行的文件，每个可执行的文件对应于一个进程或用户启动的实用程序。,第七章协议实现技术,7.3模块通讯的实现方法ESTELLE模块之间的通讯的实现很大程度上依赖于操作系统所提供的服务。在VAX/VMS环境中，如果两个模块体分别用两个进程实现，那么VMS所提供的进程通讯服务就成为模块通讯实现的基础。VAX/VMS提供的进程通讯机制包括邮箱、共享存贮区、事件、共享文件，其中邮箱是常用的通讯方法。,第七章协议实现技术,邮箱是VMS的一种伪设备，用户程序通过标准的QIO服务就可以读写邮箱。邮箱名是系统逻辑符号，为所有进程所认识。当多个进程对名字相同的邮箱进行读写时，它们实际上就进行通讯。下面列出有关邮箱服务和c语言调用。（1）定义邮箱名$DESCRIPTOP(mbx_name,”MBX_NAME”);mbx_name为放置邮箱名字符串MBX_NAME的变量。,第七章协议实现技术,(2)定义邮箱通道intmbx_ch;mbx_ch为32位的长字，它放置邮箱通道号。(3)创建邮箱通道sys$crembx(1,VMS系统服务crembx创建一个邮箱（如果该邮箱不存在），并赋于一个通道号，经b转发，它的类别就为b。这是最简单的分类法，但不能解决间接死锁问题。,第七章协议实现技术,报文分类的第二种方法是按照报文已走过的链路数或到达目的结点之前还需走过的链路数进行，前者称之为后向链分类法，后者称之为前向分类法。按照前向链分类法，到达目的结点之前还要走n条链路的报文为n类报文，n类报文逻辑上放入n队列。1类报文的目的结点就是邻近结点。按照这种方法对报文分类从根本上消除了图7.8所示的输入队列环路，因此不会发生间接死锁。图7.9中，各个输出端口逻辑上有三个队列q1，q2，q3。q1放1类报文（到达目的结点的链路数为1），q2放2类报文，q3放3类报文。当图7.8所示的情况出现时（各个结点的q2的长度已到达限额），死锁不会出现，这是因为B能接收A从q2发出的报文，并将报文放入B的q1队列（A中的2类报文到达B后变成1类报文）。如果假定B的q1队列也已到达限额，但由于B将q1队列中的报文发往C之后，C总是能接收目的结点就是C的报文（B的q1队列很快就会倒空）死锁就不会出现。,第七章协议实现技术,图7.9前向链分类法,第七章协议实现技术,3.交通流量控制接收缓冲区的分配管理与网络报文流量控制有关，或者说某些交通流量控制算法是通过接收缓冲器的分配管理来实现的。其中最常用的做法是对不同类别的报文实行优先级别控制（优先界别高的报文可获得多的接收缓冲器），以提高网络流通量，减少交通堵塞发生率。例如，当采用前向链分类法时，如果使类别低的报文优先级别高（即1类报文优先于2类报文）就能使接近于目的结点报文尽快离开网络，避免交通堵塞。,第七章协议实现技术,7.5协议并行处理技术随着数据通讯速率的提高，计算机网络各层协议的执行速度也必须提高。例如，当数据传输速率为1Gbps（1000Mbps）时，如果传输层的平均报文长度为128字节，那么它每秒要处理一百万个报文。如果每个报文的处理要花费50条指令（不包括CRC校验），那么传输层协议处理器的速度应大于50Mips。如果传输层报文包含CRC码，处理器速度要更高（约100Mips）。MIPS-MillionInstructionsPerSecond每秒百万条指令,第七章协议实现技术,提高协议执行速度的办法之一是协议并行处理技术，即用多个CPU并行执行某层协议。文献【14】以传输层协议为例，定义了三种粒度（grains）不同的协议并行处理;粗粒度（coarsegrain）并行，中粒度（mediumgrain）并行和细粒度（finegrain）并行。按粗粒度并行处理协议时，协议实体按功能划分成多个任务，各个任务分配给不同的CPU处理。例如，传输层协议可划分成联接处理，数据接收处理。数据发送处理等多个任务。如果协议功能划分更细一点（如图3.16描述的ISOTP4数据发送模型那样），这些任务可分配给更多的CPU执行。,第七章协议实现技术,按中较度并行处理协议时，多个输人报文分配给多个CPU处理。输入报文在多个CPU中分配的方法有两种:随机分配和轮循分配。对于随机分配方法，当一个输入报文来到时，如果处理器池子中有空闲的处理器，则随机地占用一个处理器处理该报文；如果处理器池子中没有空闲的处理器，该报文则进人等待队列。对于轮循分配法，输人报文轮询分配法，输入报文按先后次序轮循地分配给多个处理器。例如，设处理器池子有5个CPU，第1号报文分配给CPU1，第2号报文分配给CPU2，第6号报文分配CPU1，按细粒度并行处理协议时。多个处理器同时处理一个报文。例如，多个处理器同时分析处理一个报文头时，每个处理器分析报文头的一个字段。,第七章协议实现技术,粗粒度并行处理易于实现，这是因为各个任务界限清晰，相关性小。但粗粒度并行度小，速度提高有限。细粒度可获得很高并行度，但实现困难。中粒度并行处理技术兼有两者优点，值得人们深人研究。,第七章协议实现技术,作为例子，图7.10示出传输层报文发送的并行模型，图7.11示出传输层报文接收的并行模型。图7.10中，会晤层交给传输层的报文流（TSDU流）按轮循法则分配绘m个处理器（P1，P2，Pm），并放在各个处理器的局部存贮器队列（q1，12，qm）中。报文发出之后，它进入Rctran队列。由处理器R负责报文的重发。图7.11中，网络层交给传输层的输人报文流（TPDU流）按轮循的方法分配给n个处理器（P1，P2，Pn），并放在各个处理器的局部存贮器队列（q1，q2，qn）中。正确的报文收到之后产生一个ACK信息放人ACK队列。处理器Q专门负责发送入ACK报文。图7.10和图7.11只是一个传输层协议并行处理的模型，将它们付诸实现还必须解决以下一些问题。,图7.10传输层报文发送并行模型图7.11传输层报文接收并行模型,第七章协议实现技术,第七章协议实现技术,1发送窗口问题RTD（RoundTimeDelay）指报文从一个传愉层协议实体到另外一个传愉层协议实体之间来回传送一次的延迟时问，它是传愉层窗口流控制的重要参数。当两台机器距1000千米时，RTD近似于10ms。在数据传输1Gbps时，一个长度为512字节的报文只需4us传送时间，这意味着发送方可在RTD=10ms时间内连续发生2500个报文。如果要最大限度地利用高速数据信道，那么发送窗口应大于2500。,第七章协议实现技术,如此大的发送窗口会带来什么问题呢?首先，传输层协议实休必须要有足够的存贮空间容纳2500个报文，在认可报文来到之前，它们都停留在Retran队列中。其次每个报文设置一个超时时钟。那么传愉层需要2500个定时器口如果超时时间设定为1ms，每个超时时钟要耗费3条指令，那么专门负责定时器的处理器的速度必须大于10Mips。另外一个问题，按照传输层协议，如界某个报文有错，它后面的所有报文都重发（极端下，2500个报文都重发，这将大大降低信道的利用率。,第七章协议实现技术,2报文处理时间差异问题虽然报文按轮询方法分配给各个处理器，但由于报文内容的差异，报文处理时间长度差异就会很大（例如，连接报文的处理时间比正常数据报文的处理时间