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

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