通信规程和通信网理论基础.ppt

1 第八章 通信规程和通信网理论基础 何小其 本章主要内容 n8.1 网络协议体系结构 n8.2 排队论基础 n8.3 通信网拓扑结构 n8.4 最短径 8.1 网络协议体系结构 n8.1.1 通信规程和规程参考模型 n8.1.2 业务原语 n8.1.3 数据单元 n8.1.4 开放系统互联参考模型 n8.1.5 互联TCP/IP参考模型 n8.1.6 标准化组织 8.1.1 通信规程和规程参考模型 n通信规程 为进行通信中的数据交换而建立的规则、标 准或约定。 n规程参考模型 通信规程有层次特性，大多数网络的组织都 按层或级的方式来组织。 （N+1）层实体 （N）层实体 （N-1）层实体 （2）层实体 （1）层实体 N+1层通信 实体 N+1层通信 实体 N层实体N层实体 N-1层实体N-1层实体 实际通信线路 N层SAP 等效通信线路 N+1层 N层 N-1层 用户用户 （a）N层通信实体级联（b）N层通信实体级联 图8.1 N层规程参考模型 n实体(Entity) 在一个计算机系统中，任何能完成某一特定功能的进 程或程序，都可称为一个“实体”。 n功能层(Layer) “层”是指系统中能提供某一种或某一类服务功能集合 的“逻辑构造”，一个层中可包含一个或多个实体，该层的 功能依靠层中的实体执行该层的协议来体现。 n协议(Protocol) 两系统中对等实体之间密切地协调工作所必须遵守的 一组预定规则和约定，称为“协议”。 n服务（Service）及服务访问点（SAP） 服务是网络的低层向高层所提供的功能性的支持，高 层利用低层的“服务”来开展工作；某一层的SAP就是上一 层可以访问本层、可以得到服务的地方。 n接口 接口就是相邻层之间进行信息交换必须遵守的规则。 服务定义了两层之间的接口。 8.1.2 业务原语 n请求原语（REQUEST） 用户请求一种功能的原语。 n指示原语（INDICATION） 业务提供者请求一种功能或指示一种功能已经完 成的原语。 n响应原语（RESPONSE） 用户表示已经完成由指示原语请求功能的原语。 n证实原语（CONFIRM） 业务提供者表示已完成由请求原语要求的功能的 原语。 SAPSAP 请求 证实 响应 指示 用户A用户B 图8.2 通信原语的使用 8.1.3 数据单元 n接口数据单元（IDU） 层间传送的数据块整体，包括用户和业务提供者在业 务接入点相互传送的数据。数据一部分来自对等实体，一 部分来自相邻层。 n接口控制信息（ICI） 仅在相邻层间传送数据，用于层间互控。ICI是IDU的 一个组成部分。 n业务数据单元（SDU） 高层的对等通信实体之间传送的数据定义为本层的 SDU。 n规程控制信息（PCI） 本层实体和对等层实体间传送的为完成本层 通信规程而产生的信息。 n规程数据单元（PDU） 本层的SDU和本层的PCI两者的组合叫本层的 PDU，可写成PDU=PCI+SDU。 ICISDU PDU PCI ICI IDU IDU N+1层 N层 N-1层 图8.3 传送数据单元关系 （a）上层向下层传送数据 ICISDU PDU PCI ICI IDU IDU N+1层 N层 N-1层 图8.3 传送数据单元关系 （b）下层向上层传送数据 8.1.4 开放系统互联参考模型 应用层 表示层 会晤层 传输层 网络层 链路层 物理层 网络层 链路层 物理层 网络层 链路层 物理层 应用层 表示层 会晤层 传输层 网络层 链路层 物理层 图8.4 OSI参考模型 n物理层 提供用于建立、保持和断开物理连接的过程条件。包 括规定机械的、电气的规程和功能属性。 n链路层 负责建立、维持和释放链路连接，实现无差错传输的 功能。 n网络层 也称通信子层,提供SDU路由选择和交换功能，控制通 信子网的工作，并关心拥塞控制、计费及异种网络的互联 问题。 n运输层 实现端到端的连接控制，为端到端间提供透明的传送 通道。 n会晤层 会晤层关心会话连接的特征。其主要功能是在建立会 晤时，核实对方身份，确定何方支付费用，选择一致的通 信方式等。 n表示层 主要功能是以一种收发双方的规程和设置都明白的方 式提供一种数据传送机制。 n应用层 其主要任务是为用户提供直接的服务。 8.1.5 互联TCP/IP参考模型 7应用层 6表示层 5会话层 4传输层 3网络层 2链路层 1物理层 4应用层 3运输层 2互联网络层 1通信子网层 OSITCP/IP 图8.5 TCP/IP 参考模型 n互联网络体系结构分为四层 n互联网层采用了IP协议 n传输层定义了TCP、UDP、ICMP等协议 n物理层+链路层组成通信子网层，是主机 与局域网的接口 8.1.6 标准化组织 nITU 国际电信联盟 nANSI 美国国家标准化协会 nETSI 欧洲电信标准化协会 nIETF Internet工程特别工作组 nIRTF Internet 研究工作组 nATM论坛等 8.2 排队论基础 n8.2.1 排队论基本概念 n8.2.2 M/M/1排队模型 n8.2.3 排队论中Little定理 n排队论是通信的业务分析和性能计算的理 论基础。 n资源的有限性和需求的随机性是排队现象 的基础。 n要求服务的顾客和提供服务的服务员双方 构成的系统通常称为排队系统。 n通信网中信息流和信道，传送的数据和中 央处理单元，都是“顾客”和“服务员”关系 。 8.2.1 排队论基本概念 n排队系统的三要素 为窗口数或服务员数 顾客到达率 一般排队系统中顾客到达是随机的，系统内顾客数是 一个随机量。顾客到达的密度和以什么样的规律到达， 对系统的影响很大。 前后两个顾客到达的时间间隔 是个随机量。 的计算 平均值 为平均到达间隔时间，其倒数为平均到达率， 即： 平均到达率是排队系统重要参数，表示平均每秒内到达 的顾客数。 越小，系统负载越轻。 系统服务率 为表示服务率的参考量。服务时间 也是随机变量， 其统计平均值称为平均服务时间 ， 的倒数是 系统服务率 ，有 表示一个顾客平均占用服务设施的时间， 为平均 每秒内顾客被服务完毕后离去的数目。 上式表明信息流量密度 必须满足 ，其物理意义 是单位时间内平均达到的顾客数目 必须小于系统容量 ， 否则系统中排队的顾客数目会无限制地增加。实际上排队系统 的容量总是有限的。 将导致系统溢出而失去某些顾客。 定义：信息流量密度 可以求出排队系统的三个特性参数： （1）平均系统队列长度E（n） （2）平均停留时间T：假定有一个顾客到达排队系统，经过 排队等待、服务好正要离开时，有N个顾客在排队，这正是该 顾客平均等待期间T内到达的顾客平均数，等于T乘以平均到 达率， 而 于是， （3）排队等待时间W等于T减去平均服务时间（即平均服务率 的倒数 ） 分组 分组 信道 分组到达率终端 图8.8 分组在终端中排队和转发 8.2.3 排队论中Little定理 nLittle定理 系统中的平均顾客数E(n)等于顾客平均 等待时间E(T)乘以顾客平均到达率。 即： E(n)= E(T) 8.3 通信网络拓扑结构 n8.3.1 图论基本概念 n8.3.2 图的矩阵表示 8.3.1 图论基本概念 n图（见图8.10） n链 图中没有重复的边序列，在链中每条边只能出现一次。 n径 径是一个图中既无重复边，又无重复节点的边序列。 n环 环是起点与终点为同一节点的链，即闭链。 n树 树有n个端，n-1条边的联结图（图内任何两个端之间至 少有一条径）。生成树是覆盖联结图所有端的树。 v1 v2 v3 v1 v2 v3 v1 v2 v3 （a）（b） （c） 图8.10 各种图的几何表示 e1 e3 e4 e2e2 e1 e4 e3 n(e1,e3,e5,e4,e2)为链 n(e1,e3,e5)为径 v1 v5v4 v3 v2 e1 e4 e3 e2 e5 e6 图8.11 图的链、径、环 8.3.2 图的矩阵表示 n图可与矩阵一一对应。 n邻接阵 邻接阵表示图中节点与节点之间的关系。 即：C=cijn*n cij= 1 若vi到vj有边 0 若vi到vj无边 v1 v5 v4 v3 v2 e1 e4 e3 e2 e5 e6 图8.12 图的矩阵表示 e7 nC阵的幂 其中 ，式中各项可以是0或1，要使 ，必有 ，即 到 有边， 到 也有 边。因而 到 有一条长为2的径。径长表示 这条径中的边数。由此可知：若 则 就是 到 的径长为m的径数。 8.4 最短径 n8.4.1 无约束条件最小生成树（Prim法） n8.4.2 节点间最短径 n8.4.3 所有节点间最短路径算法 8.4.1 无约束条件最小生成树 一个联结图G如果本身不是一棵树，在满足一定条件下至少 存在一棵树是最小生成树。寻找最小生成树是一个常见的优化 问题。 已知联结图G有n个节点，节点间距离为 ， 如果 和 间无连接， 。求最小生成树的问题即 是求n-1条边的权的和最小的联结子图问题。可分为两种情况 ： 一种是无约束条件的情况，另一种是有约束条件情况。 求无约束条件最短主树的算法: （1）顺序取节点的普列（Prim）算法，简称P算法； （2）顺序取边的克鲁斯格尔（Kruskal）算法，简称K算法。 n普列算法（P算法）步骤 例8.1 v1 v2v3 v4 v5 5 2 4 2 3 10 图8.13 最短主树的算法 1 4 n树枝总长为 v1 v2v3 v4 v5 2 2 3 图8.14 最短主树 1 P算法从开始到终止共n-1步，每步须对 个 中的节点 与 个 中的节点间的距离进行比较，求出最小者。 可见第 步中要做 次比较，由此可得出P算法 计算量为： 这是 的数量级。 8.4.2 节点间最短径 当通信拓扑结构已被确定，寻找站间最短径问题有两种情况， 求指定节点到其他节点的最短径及求任意两节点间最短径。 指定节点至其他端最短径算法：给定图G，已知所有边的权 ，指定节点 至其他节点的最短径可用迪克斯恰算法 （E.Dijkstra），简称D算法。 D算法把节点集分为两组，一组称为置定点集 ，另一组 称为未置定点集 ，每点逐步赋予标定值。对于未 置定点，所赋的值是暂时的，随算法进展而调整。 n迪克斯恰算法（D算法） 例8.2 用D算法计算最短径和它径长 vs v5 v4 v3 v6 1.5 15.6 4.0 0.5 5.0 1.2 图8.15 最短径长的计算 6.7 3.12.0 v1 9.2 v2 VsV1V2V3V4V5V6置定值最短径长 0 0.5 2 2 2 2 1.5 1.5 1.7 1.7 9.7 9.7 8.4 8.4 8.4 5.5 5.5 5.1 Vs V1 V3 V4 V2 V6 V5 ws=0 w1=0.5 w3=1.5 w4=1.7 w2=2 w6=5.1 w5=8.4 若要找出各最短径的路由，可查表中暂置值变更情况。 从第二行起都没有变更，所以都是从 来的边，即 。 这一列在 后变更一次，则路由是 。 这一列值在 和 后均变更，路由是 。 这一列值在 后改变，此时 已置定，路由为 D