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

通信规程和通信网理论基础本章主要内容8.1网络协议体系结构8.2排队论基础8.3通信网拓扑结构8.4最短径第2页,共55页，2024年2月25日，星期天8.1网络协议体系结构8.1.1通信规程和规程参考模型8.1.2业务原语8.1.3数据单元8.1.4开放系统互联参考模型8.1.5互联TCP/IP参考模型8.1.6标准化组织第3页,共55页，2024年2月25日，星期天8.1.1通信规程和规程参考模型通信规程

为进行通信中的数据交换而建立的规则、标准或约定。规程参考模型

通信规程有层次特性，大多数网络的组织都按层或级的方式来组织。第4页,共55页，2024年2月25日，星期天（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.1N层规程参考模型第5页,共55页，2024年2月25日，星期天实体(Entity)

在一个计算机系统中，任何能完成某一特定功能的进程或程序，都可称为一个“实体”。功能层(Layer)

“层”是指系统中能提供某一种或某一类服务功能集合的“逻辑构造”，一个层中可包含一个或多个实体，该层的功能依靠层中的实体执行该层的协议来体现。

协议(Protocol)

两系统中对等实体之间密切地协调工作所必须遵守的一组预定规则和约定，称为“协议”。

第6页,共55页，2024年2月25日，星期天服务（Service）及服务访问点（SAP）

服务是网络的低层向高层所提供的功能性的支持，高层利用低层的“服务”来开展工作；某一层的SAP就是上一层可以访问本层、可以得到服务的地方。

接口

接口就是相邻层之间进行信息交换必须遵守的规则。服务定义了两层之间的接口。

第7页,共55页，2024年2月25日，星期天8.1.2业务原语请求原语（REQUEST）

用户请求一种功能的原语。指示原语（INDICATION）

业务提供者请求一种功能或指示一种功能已经完成的原语。响应原语（RESPONSE）

用户表示已经完成由指示原语请求功能的原语。证实原语（CONFIRM）

业务提供者表示已完成由请求原语要求的功能的原语。第8页,共55页，2024年2月25日，星期天SAPSAP①请求④证实③响应②指示用户A用户B图8.2通信原语的使用第9页,共55页，2024年2月25日，星期天8.1.3数据单元接口数据单元（IDU）

层间传送的数据块整体，包括用户和业务提供者在业务接入点相互传送的数据。数据一部分来自对等实体，一部分来自相邻层。接口控制信息（ICI）

仅在相邻层间传送数据，用于层间互控。ICI是IDU的一个组成部分。业务数据单元（SDU）

高层的对等通信实体之间传送的数据定义为本层的SDU。第10页,共55页，2024年2月25日，星期天规程控制信息（PCI）

本层实体和对等层实体间传送的为完成本层通信规程而产生的信息。规程数据单元（PDU）

本层的SDU和本层的PCI两者的组合叫本层的PDU，可写成PDU=PCI+SDU。第11页,共55页，2024年2月25日，星期天ICISDUPDUPCIICIIDUIDUN+1层N层N-1层图8.3传送数据单元关系（a）上层向下层传送数据第12页,共55页，2024年2月25日，星期天ICISDUPDUPCIICIIDUIDUN+1层N层N-1层图8.3传送数据单元关系（b）下层向上层传送数据第13页,共55页，2024年2月25日，星期天第14页,共55页，2024年2月25日，星期天8.1.4开放系统互联参考模型应用层表示层会晤层传输层网络层链路层物理层网络层链路层物理层网络层链路层物理层应用层表示层会晤层传输层网络层链路层物理层图8.4OSI参考模型第15页,共55页，2024年2月25日，星期天物理层

提供用于建立、保持和断开物理连接的过程条件。包括规定机械的、电气的规程和功能属性。链路层

负责建立、维持和释放链路连接，实现无差错传输的功能。网络层

也称通信子层,提供SDU路由选择和交换功能，控制通信子网的工作，并关心拥塞控制、计费及异种网络的互联问题。第16页,共55页，2024年2月25日，星期天运输层

实现端到端的连接控制，为端到端间提供透明的传送通道。会晤层

会晤层关心会话连接的特征。其主要功能是在建立会晤时，核实对方身份，确定何方支付费用，选择一致的通信方式等。表示层

主要功能是以一种收发双方的规程和设置都明白的方式提供一种数据传送机制。应用层

其主要任务是为用户提供直接的服务。第17页,共55页，2024年2月25日，星期天8.1.5互联TCP/IP参考模型7应用层6表示层5会话层4传输层3网络层2链路层1物理层4应用层3运输层2互联网络层1通信子网层OSITCP/IP图8.5TCP/IP参考模型第18页,共55页，2024年2月25日，星期天互联网络体系结构分为四层互联网层采用了IP协议传输层定义了TCP、UDP、ICMP等协议物理层+链路层组成通信子网层，是主机与局域网的接口第19页,共55页，2024年2月25日，星期天8.1.6标准化组织ITU国际电信联盟ANSI美国国家标准化协会ETSI欧洲电信标准化协会IETFInternet工程特别工作组IRTFInternet研究工作组ATM论坛等第20页,共55页，2024年2月25日，星期天8.2排队论基础8.2.1排队论基本概念8.2.2M/M/1排队模型8.2.3排队论中Little定理第21页,共55页，2024年2月25日，星期天排队论是通信的业务分析和性能计算的理论基础。资源的有限性和需求的随机性是排队现象的基础。要求服务的顾客和提供服务的服务员双方构成的系统通常称为排队系统。通信网中信息流和信道，传送的数据和中央处理单元，都是“顾客”和“服务员”关系。第22页,共55页，2024年2月25日，星期天8.2.1排队论基本概念排队系统的三要素

为窗口数或服务员数

第23页,共55页，2024年2月25日，星期天顾客到达率一般排队系统中顾客到达是随机的，系统内顾客数是一个随机量。顾客到达的密度和以什么样的规律到达，对系统的影响很大。前后两个顾客到达的时间间隔是个随机量。的计算平均值为平均到达间隔时间，其倒数为平均到达率，即：平均到达率是排队系统重要参数，表示平均每秒内到达的顾客数。越小，系统负载越轻。第24页,共55页，2024年2月25日，星期天系统服务率为表示服务率的参考量。服务时间也是随机变量，其统计平均值称为平均服务时间，的倒数是系统服务率，有表示一个顾客平均占用服务设施的时间，为平均每秒内顾客被服务完毕后离去的数目。第25页,共55页，2024年2月25日，星期天上式表明信息流量密度必须满足，其物理意义是单位时间内平均达到的顾客数目必须小于系统容量，否则系统中排队的顾客数目会无限制地增加。实际上排队系统的容量总是有限的。将导致系统溢出而失去某些顾客。定义：信息流量密度第26页,共55页，2024年2月25日，星期天可以求出排队系统的三个特性参数：（1）平均系统队列长度E（n）（2）平均停留时间T：假定有一个顾客到达排队系统，经过排队等待、服务好正要离开时，有N个顾客在排队，这正是该顾客平均等待期间T内到达的顾客平均数，等于T乘以平均到达率，而于是，（3）排队等待时间W等于T减去平均服务时间（即平均服务率的倒数）第27页,共55页，2024年2月25日，星期天分组分组信道分组到达率λ终端图8.8分组在终端中排队和转发第28页,共55页，2024年2月25日，星期天8.2.3排队论中Little定理Little定理 系统中的平均顾客数E(n)等于顾客平均等待时间E(T)乘以顾客平均到达率λ。 即： E(n)=E(T)λ第29页,共55页，2024年2月25日，星期天8.3通信网络拓扑结构8.3.1图论基本概念8.3.2图的矩阵表示第30页,共55页，2024年2月25日，星期天8.3.1图论基本概念图（见图8.10）

链 图中没有重复的边序列，在链中每条边只能出现一次。径 径是一个图中既无重复边，又无重复节点的边序列。环 环是起点与终点为同一节点的链，即闭链。树 树有n个端，n-1条边的联结图（图内任何两个端之间至少有一条径）。生成树是覆盖联结图所有端的树。第31页,共55页，2024年2月25日，星期天v1v2v3v1v2v3v1v2v3（a）（b）（c）图8.10各种图的几何表示e1e3e4e2e2e1e4e3第32页,共55页，2024年2月25日，星期天(e1,e3,e5,e4,e2)为链(e1,e3,e5)为径v1v5v4v3v2e1e4e3e2e5e6图8.11图的链、径、环第33页,共55页，2024年2月25日，星期天8.3.2图的矩阵表示图可与矩阵一一对应。邻接阵 邻接阵表示图中节点与节点之间的关系。即：C=[cij]n*n

cij=1若vi到vj有边0若vi到vj无边第34页,共55页，2024年2月25日，星期天v1v5v4v3v2e1e4e3e2e5e6图8.12图的矩阵表示e7第35页,共55页，2024年2月25日，星期天C阵的幂其中，式中各项可以是0或1，要使，必有，即到有边，到也有边。因而到有一条长为2的径。径长表示这条径中的边数。由此可知：若则就是到的径长为m的径数。第36页,共55页，2024年2月25日，星期天8.4最短径8.4.1无约束条件最小生成树（Prim法）8.4.2节点间最短径8.4.3所有节点间最短路径算法第37页,共55页，2024年2月25日，星期天8.4.1无约束条件最小生成树一个联结图G如果本身不是一棵树，在满足一定条件下至少存在一棵树是最小生成树。寻找最小生成树是一个常见的优化问题。已知联结图G有n个节点，节点间距离为，如果和间无连接，。求最小生成树的问题即是求n-1条边的权的和最小的联结子图问题。可分为两种情况：一种是无约束条件的情况，另一种是有约束条件情况。求无约束条件最短主树的算法:（1）顺序取节点的普列（Prim）算法，简称P算法；（2）顺序取边的克鲁斯格尔（Kruskal）算法，简称K算法。第38页,共55页，2024年2月25日，星期天普列算法（P算法）步骤

第39页,共55页，2024年2月25日，星期天例8.1v1v2v3v4v55242310图8.13最短主树的算法14第40页,共55页，2024年2月25日，星期天树枝总长为v1v2v3v4v5223图8.14最短主树1第41页,共55页，2024年2月25日，星期天P算法从开始到终止共n-1步，每步须对个中的节点与个中的节点间的距离进行比较，求出最小者。可见第步中要做次比较，由此可得出P算法计算量为：这是的数量级。第42页,共55页，2024年2月25日，星期天8.4.2节点间最短径当通信拓扑结构已被确定，寻找站间最短径问题有两种情况，求指定节点到其他节点的最短径及求任意两节点间最短径。指定节点至其他端最短径算法：给定图G，已知所有边的权，指定节点至其他节点的最短径可用迪克斯恰算法（E.Dijkstra），简称D算法。D算法把节点集分为两组，一组称为置定点集，另一组称为未置定点集，每点逐步赋予标定值。对于未置定点，所赋的值是暂时的，随算法进展而调整。第43页,共55页，2024年2月25日，星期天迪克斯恰算法（D算法）第44页,共55页，2024年2月25日，星期天例8.2用D算法计算最短径和它径长vsv5v4v3v61.515.64.00.55.01.2图8.15最短径长的计算6.73.12.0v19.2v2第45页,共55页，2024年2月25日，星期天VsV1V2V3V4V5V6置定值最短径长0∞0.5∞2222∞1.51.5∞∞1.71.7∞∞9.79.78.48.48.4∞∞∞5.55.55.1VsV1V3V4V2V6V5ws=0w1=0.5w3=1.5w4=1.7w2=2w6=5.1w5=8.4第46页,共55页，2024年2月25日，星期天若要找出各最短径的路由，可查表中暂置值变更情况。从第二行起都没有变更，所以都是从来的边，即。这一列在后变更一次，则路由是。这一列值在和后均变更，路由是