通信规程和通信网理论基础.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层通信层通信实体

3、实体N+1N+1层通信层通信实体实体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)在一个计算机系统中，任何能完成某一特定功能的进程或程在一个计算机系统中，任何能完成某一特定功能的进程或程序，都可称为一个序，都可称为一个“实体

4、实体”。n功能层功能层(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

7、8.2 通信原语的使用通信原语的使用现在学习的是第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-

9、1层层图图8.3 8.3 传送数据单元关系传送数据单元关系（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表示层表示层主要功能是以一种收发双方的规程和设置都明白的方式主要功能是以一种收发双方的规程和设置都明白的方式提供一种数据传送机制。提供一种数据

12、传送机制。n应用层应用层其主要任务是为用户提供直接的服务。其主要任务是为用户提供直接的服务。现在学习的是第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

13、、UDP、ICMP等协议等协议n物理层物理层+链路层组成通信子网层，是主机与链路层组成通信子网层，是主机与局域网的接口局域网的接口现在学习的是第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 排队论

14、基础排队论基础n8.2.1 8.2.1 排队论基本概念排队论基本概念n8.2.2 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页系统服务率系统服务率为表示服务率的参考量。服务时间为表示服务率的参考量。服务时间 也是随机变量，也是随机变量，其统计平均值称为平均服务时间其统计平均值称为平均服务时间 ，的倒数是的倒数是系统服务率系统服务率 ，有，有 表示一个顾客平均占用服务设施的时间，表示一个顾客平均占用服务设施的时间，为平均为平

17、均每秒内顾客被服务完毕后离去的数目。每秒内顾客被服务完毕后离去的数目。现在学习的是第25页，共55页上式表明信息流量密度上式表明信息流量密度 必须满足必须满足 ，其物理意义，其物理意义是单位时间内平均达到的顾客数目是单位时间内平均达到的顾客数目 必须小于系统容量必须小于系统容量 ，否则系统中排队的顾客数目会无限制地增加。实际上排队系统否则系统中排队的顾客数目会无限制地增加。实际上排队系统的容量总是有限的。的容量总是有限的。将导致系统溢出而失去某些顾客。将导致系统溢出而失去某些顾客。定义：信息流量密度定义：信息流量密度 现在学习的是第26页，共55页可以求出排队系统的三个特性参数：可以求出排队系

18、统的三个特性参数：（1 1）平均系统队列长度平均系统队列长度E E（n n）（2 2）平均停留时间平均停留时间T T：假定有一个顾客到达排队系统，经过假定有一个顾客到达排队系统，经过排队等待、服务好正要离开时，有排队等待、服务好正要离开时，有N N个顾客在排队，这正是该个顾客在排队，这正是该顾客平均等待期间顾客平均等待期间T T内到达的顾客平均数，等于内到达的顾客平均数，等于T T乘以平均到乘以平均到达率，达率，而而 于是，于是，（3 3）排队等待时间排队等待时间W W等于等于T T减去平均服务时间（即平均服务率减去平均服务时间（即平均服务率的倒数的倒数 ）现在学习的是第27页，共55页分组分

19、组分组分组信道信道分组到达率分组到达率终端终端图图8.8 8.8 分组在终端中排队和转发分组在终端中排队和转发现在学习的是第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 图的矩阵表

20、示图的矩阵表示现在学习的是第30页，共55页8.3.1 8.3.1 图论基本概念图论基本概念n图图（见图（见图8.10）n链链图中没有重复的边序列，在链中每条边只能出现一次。图中没有重复的边序列，在链中每条边只能出现一次。n径径径是一个图中既无重复边，又无重复节点的边序列。径是一个图中既无重复边，又无重复节点的边序列。n环环环是起点与终点为同一节点的链，即闭链。环是起点与终点为同一节点的链，即闭链。n树树树有树有n个端，个端，n-1条边的条边的联结图联结图（图内任何两个端之间至少有（图内任何两个端之间至少有一条径）。生成树是覆盖联结图所有端的树。一条径）。生成树是覆盖联结图所有端的树。现在学习

21、的是第31页，共55页v1v2v3v1v2v3v1v2v3（a）（b）（c）图图8.10 8.10 各种图的几何表示各种图的几何表示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邻接阵邻接阵邻接阵表示图中节点与节点之间的关系。邻接阵表示图中节

22、点与节点之间的关系。即：即：C=cC=cijij n*nn*nc cijij=1 1 若若v vi i到到v vj j有边有边0 0 若若v vi i到到v vj j无边无边现在学习的是第34页，共55页v1v5v4v3v2e1e4e3e2e5e6图图8.12 8.12 图的矩阵表示图的矩阵表示e7现在学习的是第35页，共55页nC C阵的幂阵的幂其中其中 ，式中各项可以是，式中各项可以是0 0或或1 1，要使，要使 ，必有，必有 ，即，即 到到 有边，有边，到到 也有也有边。因而边。因而 到到 有一条长为有一条长为2 2的径。径长表示的径。径长表示这条径中的边数。由此可知：若这条径中的边数。

23、由此可知：若 则则 就是就是 到到 的径长为的径长为m m的径数。的径数。现在学习的是第36页，共55页8.4 8.4 最短径最短径n8.4.1 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如果本身不是一棵树，在满足一定条件下至少如果本身不是一棵树，在满足一定条件下至少存在一棵树是最小生成树。寻找最小生成树是一个常见的优

24、化存在一棵树是最小生成树。寻找最小生成树是一个常见的优化问题。问题。已知联结图已知联结图G有有n个节点，节点间距离为个节点，节点间距离为 ，如果如果 和和 间无连接，间无连接，。求最小生成树的问题即。求最小生成树的问题即是求是求n-1条边的权的和最小的联结子图问题。可分为两种情况：条边的权的和最小的联结子图问题。可分为两种情况：一种是无约束条件的情况，另一种是有约束条件情况。一种是无约束条件的情况，另一种是有约束条件情况。求无约束条件最短主树的算法求无约束条件最短主树的算法:（1）顺序取节点的）顺序取节点的普列（普列（Prim）算法）算法，简称，简称P算法算法；（2）顺序取边的）顺序取边的克鲁

25、斯格尔（克鲁斯格尔（Kruskal）算法）算法，简称，简称K算法算法。现在学习的是第38页，共55页n普列算法（普列算法（P P算法）步骤算法）步骤 现在学习的是第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步，每步须对步，每步须对 个个 中的节点中的节点与与 个个 中的节点间的距离进行比较，求出最小者。中的节点间的

26、距离进行比较，求出最小者。可见第可见第 步中要做步中要做 次比较，由此可得出次比较，由此可得出P P算法算法计算量为：计算量为：这是这是 的数量级。的数量级。现在学习的是第42页，共55页8.4.2 8.4.2 节点间最短径节点间最短径当通信拓扑结构已被确定，寻找站间最短径问题有两种情况，当通信拓扑结构已被确定，寻找站间最短径问题有两种情况，求指定节点到其他节点的最短径及求任意两节点间最短径。求指定节点到其他节点的最短径及求任意两节点间最短径。指定节点至其他端最短径算法指定节点至其他端最短径算法：给定图：给定图G，已知所有边的权，已知所有边的权 ，指定节点，指定节点 至其他节点的最短径可用迪克

27、斯恰算法至其他节点的最短径可用迪克斯恰算法（E.Dijkstra），简称），简称D算法。算法。D算法把节点集分为两组，一组称为置定点集算法把节点集分为两组，一组称为置定点集 ，另一组，另一组称为未置定点集称为未置定点集 ，每点逐步赋予标定值。对于未，每点逐步赋予标定值。对于未置定点，所赋的值是暂时的，随算法进展而调整。置定点，所赋的值是暂时的，随算法进展而调整。现在学习的是第43页，共55页n迪克斯恰算法（迪克斯恰算法（D D算法）算法）现在学习的是第44页，共55页例例8.2 8.2 用用D D算法计算最短径和它径长算法计算最短径和它径长vsv5v4v3v61.515.64.00.55.01

28、.2图图8.15 8.15 最短径长的计算最短径长的计算6.73.12.0v19.2v2现在学习的是第45页，共55页VsV1V2V3V4V5V6置定值置定值最短径长最短径长0 00.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）次比较求最小值，共有）次比较求最

30、小值，共有3（n-k）-1次运算，总运算量为：次运算，总运算量为：计算复杂性为计算复杂性为 量级。量级。现在学习的是第48页，共55页8.4.3 8.4.3 所有节点间最短路径算法所有节点间最短路径算法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页