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

《通信规程和通信网理论基础课件.ppt》由会员分享，可在线阅读，更多相关《通信规程和通信网理论基础课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、通信规程和通信网理论基础第1页，此课件共55页哦本章主要内容本章主要内容n8.1 8.1 网络协议体系结构网络协议体系结构n8.2 8.2 排队论基础排队论基础n8.3 8.3 通信网拓扑结构通信网拓扑结构n8.4 8.4 最短径最短径第2页，此课件共55页哦8.1 8.1 网络协议体系结构网络协议体系结构n8.1.1 8.1.1 通信规程和规程参考模型通信规程和规程参考模型n8.1.2 8.1.2 业务原语业务原语n8.1.3 8.1.3 数据单元数据单元n8.1.4 8.1.4 开放系统互联参考模型开放系统互联参考模型n8.1.5 8.1.5 互联互联TCP/IPTCP/IP参考模型参考模

2、型n8.1.6 8.1.6 标准化组织标准化组织第3页，此课件共55页哦8.1.1 8.1.1 通信规程和规程参考模型通信规程和规程参考模型n通信规程通信规程为进行通信中的数据交换而建立的规则、标准为进行通信中的数据交换而建立的规则、标准或约定。或约定。n规程参考模型规程参考模型通信规程有层次特性，大多数网络的组织都按层或级通信规程有层次特性，大多数网络的组织都按层或级的方式来组织。的方式来组织。第4页，此课件共55页哦（N+1N+1）层实体）层实体（N N）层实体）层实体（N-1N-1）层实体）层实体（2 2）层实体）层实体（1 1）层实体）层实体N+1N+1层通信层通信实体实体N+1N+1

3、层通信层通信实体实体N N层实体层实体N N层实体层实体N-1N-1层实体层实体N-1N-1层实体层实体实际通信线路实际通信线路N N层层SAPSAP等效通信线路等效通信线路N+1N+1层层N N层层N-1N-1层层用户用户用户用户（a a）N N层通信实体级联层通信实体级联（b b）N N层通信实体级联层通信实体级联图图8.1 N8.1 N层规程参考模型层规程参考模型第5页，此课件共55页哦n实体实体(Entity)(Entity)在一个计算机系统中，任何能完成某一特定功能的进程在一个计算机系统中，任何能完成某一特定功能的进程或程序，都可称为一个或程序，都可称为一个“实体实体”。n功能层功能

4、层(Layer)(Layer)“层层”是指系统中能提供某一种或某一类服务功能集合的是指系统中能提供某一种或某一类服务功能集合的“逻辑构造逻辑构造”，一个层中可包含一个或多个实体，该层的功能依，一个层中可包含一个或多个实体，该层的功能依靠层中的实体执行该层的协议来体现。靠层中的实体执行该层的协议来体现。n协议协议(Protocol)(Protocol)两系统中对等实体之间密切地协调工作所必须遵守的一组两系统中对等实体之间密切地协调工作所必须遵守的一组预定规则和约定，称为预定规则和约定，称为“协议协议”。第6页，此课件共55页哦n服务（服务（ServiceService）及服务访问点（）及服务访问

5、点（SAPSAP）服务是网络的低层向高层所提供的功能性的支持，高层利用服务是网络的低层向高层所提供的功能性的支持，高层利用低层的低层的“服务服务”来开展工作；某一层的来开展工作；某一层的SAPSAP就是上一层可以访问就是上一层可以访问本层、可以得到服务的地方。本层、可以得到服务的地方。n接口接口接口就是相邻层之间进行信息交换必须遵守的规则。服接口就是相邻层之间进行信息交换必须遵守的规则。服务定义了两层之间的接口。务定义了两层之间的接口。第7页，此课件共55页哦8.1.2 8.1.2 业务原语业务原语n请求原语（请求原语（REQUESTREQUEST）用户请求一种功能的原语。用户请求一种功能的原

6、语。n指示原语（指示原语（INDICATIONINDICATION）业务提供者请求一种功能或指示一种功能已经完成的原业务提供者请求一种功能或指示一种功能已经完成的原语。语。n响应原语（响应原语（RESPONSERESPONSE）用户表示已经完成由指示原语请求功能的原语。用户表示已经完成由指示原语请求功能的原语。n证实原语（证实原语（CONFIRMCONFIRM）业务提供者表示已完成由请求原语要求的功能的原语。业务提供者表示已完成由请求原语要求的功能的原语。第8页，此课件共55页哦SAPSAP请请求求证证实实响响应应指指示示用户用户A A用户用户B B图图8.2 8.2 通信原语的使用通信原语的

7、使用第9页，此课件共55页哦8.1.3 8.1.3 数据单元数据单元n接口数据单元（接口数据单元（IDUIDU）层间传送的数据块整体，包括用户和业务提供者在业务接层间传送的数据块整体，包括用户和业务提供者在业务接入点相互传送的数据。数据一部分来自对等实体，一部分来自入点相互传送的数据。数据一部分来自对等实体，一部分来自相邻层。相邻层。n接口控制信息（接口控制信息（ICIICI）仅在相邻层间传送数据，用于层间互控。仅在相邻层间传送数据，用于层间互控。ICIICI是是IDUIDU的一个组的一个组成部分。成部分。n业务数据单元（业务数据单元（SDUSDU）高层的对等通信实体之间传送的数据定义为本层的

8、高层的对等通信实体之间传送的数据定义为本层的SDUSDU。第10页，此课件共55页哦n规程控制信息（规程控制信息（PCIPCI）本层实体和对等层实体间传送的为完成本层通信本层实体和对等层实体间传送的为完成本层通信规程而产生的信息。规程而产生的信息。n规程数据单元（规程数据单元（PDUPDU）本层的本层的SDUSDU和本层的和本层的PCIPCI两者的组合叫本层的两者的组合叫本层的PDUPDU，可写成可写成PDU=PCI+SDUPDU=PCI+SDU。第11页，此课件共55页哦ICISDUPDUPCIICIIDUIDUN+1N+1层层N N层层N-1N-1层层图图8.3 8.3 传送数据单元关系传

9、送数据单元关系（a a）上层向下层传送数据）上层向下层传送数据第12页，此课件共55页哦ICISDUPDUPCIICIIDUIDUN+1N+1层层N N层层N-1N-1层层图图8.3 8.3 传送数据单元关系传送数据单元关系（b b）下层向上层传送数据）下层向上层传送数据第13页，此课件共55页哦第14页，此课件共55页哦8.1.4 8.1.4 开放系统互联参考模型开放系统互联参考模型应用层应用层表示层表示层会晤层会晤层传输层传输层网络层网络层链路层链路层物理层物理层网络层网络层链路层链路层物理层物理层网络层网络层链路层链路层物理层物理层应用层应用层表示层表示层会晤层会晤层传输层传输层网络层网

10、络层链路层链路层物理层物理层图图8.4 OSI8.4 OSI参考模型参考模型第15页，此课件共55页哦n物理层物理层提供用于建立、保持和断开物理连接的过程条件。包括规提供用于建立、保持和断开物理连接的过程条件。包括规定机械的、电气的规程和功能属性。定机械的、电气的规程和功能属性。n链路层链路层负责建立、维持和释放链路连接，实现无差错传输的功负责建立、维持和释放链路连接，实现无差错传输的功能。能。n网络层网络层也称通信子层也称通信子层,提供提供SDUSDU路由选择和交换功能，控制通信子路由选择和交换功能，控制通信子网的工作，并关心拥塞控制、计费及异种网络的互联问题。网的工作，并关心拥塞控制、计费

11、及异种网络的互联问题。第16页，此课件共55页哦n运输层运输层实现端到端的连接控制，为端到端间提供透明的传送通道。实现端到端的连接控制，为端到端间提供透明的传送通道。n会晤层会晤层会晤层关心会话连接的特征。其主要功能是在建立会晤会晤层关心会话连接的特征。其主要功能是在建立会晤时，核实对方身份，确定何方支付费用，选择一致的通信方时，核实对方身份，确定何方支付费用，选择一致的通信方式等。式等。n表示层表示层主要功能是以一种收发双方的规程和设置都明白的方式提主要功能是以一种收发双方的规程和设置都明白的方式提供一种数据传送机制。供一种数据传送机制。n应用层应用层其主要任务是为用户提供直接的服务。其主要

12、任务是为用户提供直接的服务。第17页，此课件共55页哦8.1.5 8.1.5 互联互联TCP/IPTCP/IP参考模型参考模型7应用层应用层6表示层表示层5会话层会话层4传输层传输层3网络层网络层2链路层链路层1物理层物理层4应用层应用层3运输层运输层2互联网络层互联网络层1通信子网层通信子网层OSITCP/IP图图8.5 TCP/IP 8.5 TCP/IP 参考模型参考模型第18页，此课件共55页哦n互联网络体系结构分为四层互联网络体系结构分为四层n互联网层采用了互联网层采用了IP协议协议n传输层定义了传输层定义了TCP、UDP、ICMP等协议等协议n物理层物理层+链路层组成通信子网层，是主

13、机链路层组成通信子网层，是主机与局域网的接口与局域网的接口第19页，此课件共55页哦8.1.6 8.1.6 标准化组织标准化组织nITU ITU 国际电信联盟国际电信联盟nANSI ANSI 美国国家标准化协会美国国家标准化协会nETSI ETSI 欧洲电信标准化协会欧洲电信标准化协会nIETF InternetIETF Internet工程特别工作组工程特别工作组nIRTF Internet IRTF Internet 研究工作组研究工作组nATMATM论坛等论坛等第20页，此课件共55页哦8.2 8.2 排队论基础排队论基础n8.2.1 8.2.1 排队论基本概念排队论基本概念n8.2.2

14、 M/M/18.2.2 M/M/1排队模型排队模型n8.2.3 8.2.3 排队论中排队论中LittleLittle定理定理第21页，此课件共55页哦n排队论排队论是通信的业务分析和性能计算的理是通信的业务分析和性能计算的理论基础。论基础。n资源的有限性和需求的随机性是排队现象资源的有限性和需求的随机性是排队现象的基础。的基础。n要求服务的顾客和提供服务的服务员双方要求服务的顾客和提供服务的服务员双方构成的系统通常称为构成的系统通常称为排队系统排队系统。n通信网中信息流和信道，传送的数据和中通信网中信息流和信道，传送的数据和中央处理单元，都是央处理单元，都是“顾客顾客”和和“服务员服务员”关关

15、系系。第22页，此课件共55页哦8.2.1 8.2.1 排队论基本概念排队论基本概念n排队系统的三要素排队系统的三要素 为窗口数或服务员数为窗口数或服务员数 第23页，此课件共55页哦顾客到达率顾客到达率 一般排队系统中顾客到达是随机的，系统内顾客数是一般排队系统中顾客到达是随机的，系统内顾客数是一个随机量。顾客到达的密度和以什么样的规律到达，一个随机量。顾客到达的密度和以什么样的规律到达，对系统的影响很大。对系统的影响很大。前后两个顾客到达的时间间隔前后两个顾客到达的时间间隔 是个随机量。是个随机量。的计算的计算平均值平均值 为平均到达间隔时间，其倒数为平均到达率，为平均到达间隔时间，其倒数

16、为平均到达率，即：即：平均到达率是排队系统重要参数，表示平均每秒内到达平均到达率是排队系统重要参数，表示平均每秒内到达的顾客数。的顾客数。越小，系统负载越轻。越小，系统负载越轻。第24页，此课件共55页哦系统服务率系统服务率为表示服务率的参考量。服务时间为表示服务率的参考量。服务时间 也是随机变量，也是随机变量，其统计平均值称为平均服务时间其统计平均值称为平均服务时间 ，的倒数是的倒数是系统服务率系统服务率 ，有，有 表示一个顾客平均占用服务设施的时间，表示一个顾客平均占用服务设施的时间，为平均为平均每秒内顾客被服务完毕后离去的数目。每秒内顾客被服务完毕后离去的数目。第25页，此课件共55页哦

17、上式表明信息流量密度上式表明信息流量密度 必须满足必须满足 ，其物理意义，其物理意义是单位时间内平均达到的顾客数目是单位时间内平均达到的顾客数目 必须小于系统容量必须小于系统容量 ，否则系统中排队的顾客数目会无限制地增加。实际上排队系统否则系统中排队的顾客数目会无限制地增加。实际上排队系统的容量总是有限的。的容量总是有限的。将导致系统溢出而失去某些顾客。将导致系统溢出而失去某些顾客。定义：信息流量密度定义：信息流量密度 第26页，此课件共55页哦可以求出排队系统的三个特性参数：可以求出排队系统的三个特性参数：（1 1）平均系统队列长度平均系统队列长度E E（n n）（2 2）平均停留时间平均停

18、留时间T T：假定有一个顾客到达排队系统，经过假定有一个顾客到达排队系统，经过排队等待、服务好正要离开时，有排队等待、服务好正要离开时，有N N个顾客在排队，这正是该个顾客在排队，这正是该顾客平均等待期间顾客平均等待期间T T内到达的顾客平均数，等于内到达的顾客平均数，等于T T乘以平均到乘以平均到达率，达率，而而 于是，于是，（3 3）排队等待时间排队等待时间W W等于等于T T减去平均服务时间（即平均服务率减去平均服务时间（即平均服务率的倒数的倒数 ）第27页，此课件共55页哦分组分组分组分组信道信道分组到达率分组到达率终端终端图图8.8 8.8 分组在终端中排队和转发分组在终端中排队和转

19、发第28页，此课件共55页哦8.2.3 8.2.3 排队论中排队论中LittleLittle定理定理nLittleLittle定理定理系统中的平均顾客数系统中的平均顾客数E(n)E(n)等于顾客平均等于顾客平均等待时间等待时间E(T)E(T)乘以顾客平均到达率乘以顾客平均到达率。即：即：E(n)=E(T)E(n)=E(T)第29页，此课件共55页哦8.3 8.3 通信网络拓扑结构通信网络拓扑结构n8.3.1 8.3.1 图论基本概念图论基本概念n8.3.2 8.3.2 图的矩阵表示图的矩阵表示第30页，此课件共55页哦8.3.1 8.3.1 图论基本概念图论基本概念n图图（见图（见图8.10）

20、n链链图中没有重复的边序列，在链中每条边只能出现一次。图中没有重复的边序列，在链中每条边只能出现一次。n径径径是一个图中既无重复边，又无重复节点的边序列。径是一个图中既无重复边，又无重复节点的边序列。n环环环是起点与终点为同一节点的链，即闭链。环是起点与终点为同一节点的链，即闭链。n树树树有树有n个端，个端，n-1条边的条边的联结图联结图（图内任何两个端之间至少有（图内任何两个端之间至少有一条径）。生成树是覆盖联结图所有端的树。一条径）。生成树是覆盖联结图所有端的树。第31页，此课件共55页哦v1v2v3v1v2v3v1v2v3（a）（b）（c）图图8.10 8.10 各种图的几何表示各种图的

21、几何表示e1e3e4e2e2e1e4e3第32页，此课件共55页哦n(e1,e3,e5,e4,e2)(e1,e3,e5,e4,e2)为链为链n(e1,e3,e5)(e1,e3,e5)为径为径v1v5v4v3v2e1e4e3e2e5e6图图8.11 8.11 图的链、径、环图的链、径、环第33页，此课件共55页哦8.3.2 8.3.2 图的矩阵表示图的矩阵表示n图可与矩阵一一对应。图可与矩阵一一对应。n邻接阵邻接阵邻接阵表示图中节点与节点之间的关系。邻接阵表示图中节点与节点之间的关系。即：即：C=cC=cijij n*nn*nc cijij=1 1 若若v vi i到到v vj j有边有边0 0

22、 若若v vi i到到v vj j无边无边第34页，此课件共55页哦v1v5v4v3v2e1e4e3e2e5e6图图8.12 8.12 图的矩阵表示图的矩阵表示e7第35页，此课件共55页哦nC C阵的幂阵的幂其中其中 ，式中各项可以是，式中各项可以是0 0或或1 1，要使，要使 ，必有，必有 ，即，即 到到 有边，有边，到到 也有边。也有边。因而因而 到到 有一条长为有一条长为2 2的径。径长表示这条的径。径长表示这条径中的边数。由此可知：若径中的边数。由此可知：若 则则 就是就是 到到 的径长为的径长为m m的径数。的径数。第36页，此课件共55页哦8.4 8.4 最短径最短径n8.4.1

23、 8.4.1 无约束条件最小生成树（无约束条件最小生成树（PrimPrim法）法）n8.4.2 8.4.2 节点间最短径节点间最短径n8.4.3 8.4.3 所有节点间最短路径算法所有节点间最短路径算法第37页，此课件共55页哦8.4.1 8.4.1 无约束条件最小生成树无约束条件最小生成树 一个联结图一个联结图G G如果本身不是一棵树，在满足一定条件下至少如果本身不是一棵树，在满足一定条件下至少存在一棵树是最小生成树。寻找最小生成树是一个常见的优化存在一棵树是最小生成树。寻找最小生成树是一个常见的优化问题。问题。已知联结图已知联结图G有有n个节点，节点间距离为个节点，节点间距离为 ，如果如果

24、 和和 间无连接，间无连接，。求最小生成树的问题即。求最小生成树的问题即是求是求n-1条边的权的和最小的联结子图问题。可分为两种情况：条边的权的和最小的联结子图问题。可分为两种情况：一种是无约束条件的情况，另一种是有约束条件情况。一种是无约束条件的情况，另一种是有约束条件情况。求无约束条件最短主树的算法求无约束条件最短主树的算法:（1）顺序取节点的）顺序取节点的普列（普列（Prim）算法）算法，简称，简称P算法算法；（2）顺序取边的）顺序取边的克鲁斯格尔（克鲁斯格尔（Kruskal）算法）算法，简称，简称K算法算法。第38页，此课件共55页哦n普列算法（普列算法（P P算法）步骤算法）步骤 第

25、39页，此课件共55页哦例例8.18.1v1v2v3v4v55242310图图8.13 8.13 最短主树的算法最短主树的算法14第40页，此课件共55页哦n树枝总长为树枝总长为v1v2v3v4v5223图图8.14 8.14 最短主树最短主树1第41页，此课件共55页哦P P算法从开始到终止共算法从开始到终止共n-1n-1步，每步须对步，每步须对 个个 中的节点中的节点与与 个个 中的节点间的距离进行比较，求出最小者。中的节点间的距离进行比较，求出最小者。可见第可见第 步中要做步中要做 次比较，由此可得出次比较，由此可得出P P算法算法计算量为：计算量为：这是这是 的数量级。的数量级。第42

26、页，此课件共55页哦8.4.2 8.4.2 节点间最短径节点间最短径当通信拓扑结构已被确定，寻找站间最短径问题有两种情况，当通信拓扑结构已被确定，寻找站间最短径问题有两种情况，求指定节点到其他节点的最短径及求任意两节点间最短径。求指定节点到其他节点的最短径及求任意两节点间最短径。指定节点至其他端最短径算法指定节点至其他端最短径算法：给定图：给定图G，已知所有边的权，已知所有边的权 ，指定节点，指定节点 至其他节点的最短径可用迪克斯恰算法至其他节点的最短径可用迪克斯恰算法（E.Dijkstra），简称），简称D算法。算法。D算法把节点集分为两组，一组称为置定点集算法把节点集分为两组，一组称为置定

27、点集 ，另一组，另一组称为未置定点集称为未置定点集 ，每点逐步赋予标定值。对于未，每点逐步赋予标定值。对于未置定点，所赋的值是暂时的，随算法进展而调整。置定点，所赋的值是暂时的，随算法进展而调整。第43页，此课件共55页哦n迪克斯恰算法（迪克斯恰算法（D D算法）算法）第44页，此课件共55页哦例例8.2 8.2 用用D D算法计算最短径和它径长算法计算最短径和它径长vsv5v4v3v61.515.64.00.55.01.2图图8.15 8.15 最短径长的计算最短径长的计算6.73.12.0v19.2v2第45页，此课件共55页哦VsV1V2V3V4V5V6置定值置定值最短径长最短径长0 0

28、0.50.52 22 22 22 21.51.51.51.51.71.71.71.79.79.79.79.78.48.48.48.48.48.45.55.55.55.55.15.1VsV1V3V4V2V6V5w ws s=0=0w w1 1=0.5=0.5w w3 3=1.5=1.5w w4 4=1.7=1.7w w2 2=2=2w w6 6=5.1=5.1w w5 5=8.4=8.4第46页，此课件共55页哦若要找出各最短径的路由，可查表中暂置值变更情况。若要找出各最短径的路由，可查表中暂置值变更情况。从第二行起都没有变更，所以都是从从第二行起都没有变更，所以都是从 来的边，即来的边，即 。

29、这一列在这一列在 后变更一次，则路由是后变更一次，则路由是 。这一列值在这一列值在 和和 后均变更，路由是后均变更，路由是 。这一列值在这一列值在 后改变，此时后改变，此时 已置定，路由为已置定，路由为第47页，此课件共55页哦D算法在第算法在第k步时，做（步时，做（n-k）次加法及（）次加法及（n-k）次比较，）次比较，更新各点暂置值，再做（更新各点暂置值，再做（n-k-1）次比较求最小值，共有）次比较求最小值，共有3（n-k）-1次运算，总运算量为：次运算，总运算量为：计算复杂性为计算复杂性为 量级。量级。第48页，此课件共55页哦8.4.3 8.4.3 所有节点间最短路径算法所有节点间最

30、短路径算法n弗洛埃德算法（弗洛埃德算法（F F算法）算法）第49页，此课件共55页哦例例8.3 计算图计算图8.15所有两点间最短路径。把图中的所有两点间最短路径。把图中的 写成写成 。第50页，此课件共55页哦第51页，此课件共55页哦第52页，此课件共55页哦从从 和和 可找到任何两点间最短径长和路由。例如从可找到任何两点间最短径长和路由。例如从 到到 的最短径长是的最短径长是8.4。从。从R阵找到阵找到 ，经，经 转接。转接。再看再看 就是要经就是要经 转接，则路由是转接，则路由是 。F算法的运算量为算法的运算量为 数量级。数量级。第53页，此课件共55页哦作业作业n习题习题1 1n习题习题4 4第54页，此课件共55页哦第55页，此课件共55页哦