《高级计算机网络演示课件ppt.ppt》由会员分享，可在线阅读，更多相关《高级计算机网络演示课件ppt.ppt（72页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 高级计算机网络高级计算机网络精1内容提要内容提要9.1 9.1 网络安全概述网络安全概述 9.2 9.2 网络安全的级别网络安全的级别 9.3 9.3 网络安全的策略网络安全的策略 9.4 9.4 虚拟专用网虚拟专用网 9.5 9.5 入侵检测入侵检测 9.6 9.6 防火墙防火墙 9.7 9.7 加密加密9.8常规密码体系常规密码体系9.9公开密钥密码体制公开密钥密码体制9.10报文的鉴别报文的鉴别9.11 9.11 密钥分配密钥分配 9.12 9.12 公钥证书公钥证书 9.13 9.13 网络安全的发展网络安全的发展 精29.1 9.1 网络安全概述网络安全概述众众所所周周知知，作作为
2、为全全球球使使用用范范围围最最大大的的信信息息网网，InternetInternet自自身身协协议议的的开开放放性性极极大大地地方方便便了了各各种种计计算算机机连连网网，拓拓宽宽了了共共享享资资源源。但但是是，由由于于在在早早期期网网络络协协议议设设计计上上对对安安全全问问题题的的忽忽视视，以以及及在在使使用用和和管管理理上上的的无无政政府府状状态态，给给了了众众多多的的hackerhacker们们许许多多机机会会，使使InternetInternet自自身身的的安安全全受受到到严严重重威威胁胁，与与它它有有关关的的安安全全事事故故屡屡有有发发生生。对对网网络络安安全全的的威威胁胁主主要要表表
3、现现在在：非非授授权权访访问问、冒冒充充合合法法用用户户、破破坏坏数数据据完完整整性性、干干扰扰系系统统正正常常运运行行、利利用用网网络络传传播播病病毒毒、线线路路窃窃听听等等方方面面。这这就就要要求求我我们们对对与与InternetInternet互互连连所所带带来的安全性问题予以足够重视。来的安全性问题予以足够重视。精39.1 9.1 网络安全概述网络安全概述保密性保密性安全协议的设计安全协议的设计访问控制访问控制精49.2 9.2 网络安全的级别网络安全的级别 D1D1级级 C1C1级级 C2C2级级 B1 B1级级 B2 B2级级 B3 B3级级 A A级级精59.3 9.3 网络安全
4、的策略网络安全的策略你试图保护那些资源？你试图保护那些资源？你需要保护这些资源防备那些人？你需要保护这些资源防备那些人？可能存在什么样的威胁？可能存在什么样的威胁？资源如何重要？资源如何重要？你你能能够够采采取取什什么么措措施施以以合合算算和和节节时时的的方方式式保保护护你你的的财财产产？精6网络操作系统的安全性能网络操作系统的安全性能NetWare网络操作系统网络操作系统WindowsNT网络操作系统网络操作系统UNIX网络操作系统网络操作系统精7NetWareNetWare网络操作系统网络操作系统登录安全登录安全NetWareNetWare登登录录安安全全需需要要用用户户输输入入一一个个有
5、有效效的的用用户户名名和和口令，并由此控制用户对网络的访问。口令，并由此控制用户对网络的访问。受托者受托者一一个个受受托托者者是是指指对对特特殊殊的的目目录录、文文件件或或对对象象有有特特定定的的控控制制权权的的一一个个用用户户或或一一个个用用户户组组。网网络络管管理理员员可可通通过过受托者来指定授予访问权。受托者来指定授予访问权。权限权限权权限限表表示示了了一一个个受受托托者者对对目目录录、文文件件和和对对象象有有什什么么级级别别的的访访问问权权。权权限限可可分分为为目目录录权权限限、文文件件权权限限、对对象象权限和属性权限。权限和属性权限。精8NetWareNetWare网络操作系统网络操
6、作系统 继承继承继继承承简简化化了了为为所所有有用用户户、目目录录、文文件件及及对对象象创创建建相相同同的的受受托托者者权权限限分分配配的的任任务务。虽虽然然继继承承给给管管理理员员提提供供了了很很大大的的方方便便，但但是是必须小心使用继承以确保权限的适当分配。必须小心使用继承以确保权限的适当分配。有效权限有效权限当当一一个个用用户户开开始始操操作作时时，NetWareNetWare就就会会计计算算用用户户对对给给定定的的目目录录、文文件件或或对对象象的的有有效效权权限限。有有效效权权限限是是指指用用户户对对目目录录、文文件件或或对对对象实际拥有的权限。对象实际拥有的权限。属性属性又又称称标标
7、志志，主主要要描描述述了了特特殊殊目目录录和和文文件件的的特特性性，这这些些属属性性定定义义了操作权限。属性在了操作权限。属性在NetWareNetWare安全环境中特别重要。安全环境中特别重要。精9Windows NT Windows NT 网络操作系统网络操作系统登录进程登录进程 这一部分接受用户的登录请求，包括远程请求。这一部分接受用户的登录请求，包括远程请求。局部安全授权（局部安全授权（LSALSA）这这部部分分保保证证任任何何已已经经登登录录的的用用户户可可以以访访问问系系统统，局局部部安安全全授授权权产产生生访访问问令令牌牌、管管理理策策略略，同同时时给给用用户户提提供供鉴别服务。
8、鉴别服务。精10Windows NT Windows NT 网络操作系统网络操作系统精11 UNIXUNIX网络操作系统网络操作系统UNIX安全涉及的主要范围是用户、用户组和文件系统。安全涉及的主要范围是用户、用户组和文件系统。用户和用户组用户和用户组象象WindowsNT一一样样UNIX利利用用用用户户名名和和口口令令来来识识别别用用户户。每每个个用用户户被被指指定定到到某某一一用用户户组组，就就能能指指定定这这些些用用户户与与用用户户组组访访问问文文件件和和目目录录。这这是是UNIX安安全全存存在在的的实实际际问问题题。即即为为使使用用户户能能够够创建其它用户，可简单允许该用户写访问口令文
9、件。创建其它用户，可简单允许该用户写访问口令文件。文件系统文件系统UNIX的的文文件件系系统统类类似似于于NT，也也是是以以层层次次结结构构组组织织的的。每每个个文文件件有有一一组组简简单单的的许许可可权权或或权权限限，对对三三类类用用户户文文件件拥拥有有者者，文文件件拥拥有有者者组组与与在在其其它它组组上上的的用用户户，各各不不相相同同。可可使使用用的的许许可可权包括：读、写、执行。权包括：读、写、执行。精12网络设计及硬件网络设计及硬件安全设备安全设备（1）脸部特征识别设备脸部特征识别设备（2）智能卡智能卡；(3）WebWeb站点阻断工具站点阻断工具（4）冗余设备）冗余设备 精13 虚拟网
10、络虚拟网络虚拟局域网虚拟局域网 基基于于端端口口的的虚虚拟拟LANLAN。这这种种VLANVLAN是是最最简简单单的的，但但提提供供了了绝绝大大部部分分控控制制功功能能和和安安全全特特性性。基基于于VLANVLAN实实际际所所连连接接的的端端口口给给VLANVLAN分分配配设设备备。端端口口分分配配是是静静态态的的，只只有有管理员才能改变。管理员才能改变。MACMAC地地址址VLANVLAN。配配置置MACMAC地地址址VLANVLAN更更为为复复杂杂。VLAN VLAN 网网络络由由一一组组MAC MAC 地地址址组组成成，AutoTrackerAutoTracker软软件件将将这这组组地地
11、址址转转换换成成了了一一个个广广播播域域。由由于于是是基基于于对对MACMAC地地址址的的鉴鉴别别，这这种种类类型型的的VLANVLAN是是一一种种更更安安全全的的方方案案。机机器器在在访问访问VLANVLAN之前，必须先具有一个可识别的之前，必须先具有一个可识别的VLANVLAN地址。地址。精14 虚拟网络虚拟网络虚拟局域网虚拟局域网 第第三三层层。在在第第三三层层的的VLANVLAN中中，管管理理员员用用不不同同的的协协议议要求对不同的要求对不同的VLANVLAN分配通信业务。分配通信业务。协协议议策策略略VLANVLAN。这这种种类类型型的的网网络络基基于于数数据据帧帧内内的的协协议议标
12、标准准。比比如如，管管理理员员可可以以在在这这类类网网络络的的数数据据帧帧内内指指明一个数据场用于确定明一个数据场用于确定VLANVLAN的隶属。的隶属。多多终终点点传传输输VLANVLAN。多多终终点点传传输输VLANVLAN通通过过“一一点点对对多多点点”或或“多多点点对对多多点点”的的方方式式传传输输信信息息。这这对对新新闻闻广广播或电视会议之类的应用是很有用的。播或电视会议之类的应用是很有用的。精15 虚拟网络虚拟网络虚拟局域网虚拟局域网 基基于于政政策策的的VLANVLAN。这这类类VLANVLAN使使管管理理员员能能组组合合应应用用VLANVLAN政政策策以以产产生生灵灵活活的的V
13、LAN VLAN。设设备备可可以以配配置置给给不不同同政政策策条条件件下下的的VLAN VLAN 系系统统。网网络络中中的的每每个个转转换换器器都都能能识别各种识别各种VLANVLAN政策。政策。用用户户鉴鉴别别VLANVLAN。这这是是一一种种高高安安全全性性能能的的VLANVLAN，它它要要求求用用户户在在访访问问网网络络资资源源之之前前，先先要要通通过过服服务务器器对对用用户户的鉴别。的鉴别。精169.4 9.4 虚拟专用网虚拟专用网VPN通过公用网络在多个地区之间建立了安全链路。通过公用网络在多个地区之间建立了安全链路。VPN新新模模型型在在公公用用INTERNET中中勾勾划划出出一一
14、个个“专专用用”网网络络，使使不不同同地地方方的的网网点点或或子子网网能能相相互互连连接接在在一一起起，为为企企业业建建立立了了一一个个实实实实在在在在的的WAN。这这与与VLAN不不同同，它它将将大大型型网网络络分分成成多多个个子子网，在通过软件来管理其间的连接。网，在通过软件来管理其间的连接。有有直直接接式式的的和和隧隧道道式式的的两两种种类类型型的的VPN。直直接接式式的的VPN使使用用IP寻寻址址并并通通过过VPN建建立立数数据据的的直直接接控控制制。它它加加密密数数据据，并并作作为为基基于于用用户户而而不不是是IP地地址址的的鉴鉴别别。另另一一方方面面，隧隧道道模模式式的的VPN使使
15、用用IP帧帧作作为为数数据据包包的的一一个个隧隧道道。这这种种模模式式的的网网络络受受到到侵侵入入，入入侵侵者者只只能能访访问问目目标标网网络络。如如果果是是双双向向模模式式，源源网网络络及及目目标标网网络络二二者都会被侵入。者都会被侵入。精179.5 9.5 入侵检测入侵检测精18精19异常检测模型异常检测模型 （1 1）通通过过将将征征抽抽取取或或事事件件到到特特征征字字符符串串的的映映射射形成异常行为空间；形成异常行为空间；（2 2）系系统统运运行行时时采采集集可可观观察察的的事事件件窨窨并并进进行行筛筛选；选；（3 3）采采集集到到的的事事件件与与预预先先建建好好的的异异常常行行为为空
16、空间间中中的的事事件件比比较较，差差异异标标闪闪准准可可用用预预先先确确定定的的阈阈值值或或某某个统计量，超过则判断为攻击。个统计量，超过则判断为攻击。精20滥用检测模型滥用检测模型对对用用户户的的行行为为特特征征与与某某种种攻攻击击活活动动的的行行为为特特征征进进行行比比较较。这这种种方方法法的的基基本本前前提提是是对对可可能能收收集集到到入入侵侵例例子子的的行行为为特特征征进进行行分分析析和和提提取取，并并使使特特征征尽尽量量覆覆盖盖可可能能的的变变种种攻攻击击。然然而而，这这种种方方法法的的有有效效性性也也由由于于攻攻击击的的多多样样性性和和利利用用合合法法手手段段进进行行攻攻击击的的例
17、例子子的的增增多多而而显显出出其无能为力的一面。其无能为力的一面。另另外外不不论论哪哪一一种种入入侵侵检检测测的的教教学学模模型型，都都同同样样面面临临一一个个实实时时和和处处理理大大量量信信息息的的难难题题。如如要要检检测测的的信信息息源源包包括括：网网络络包包、主主机机事事件件（进进程程、任任务务等等）、网网络络状状态态（流流社社信信息息等等）、主主机机状状态态（机机器器忙忙闲闲等等）。日日益增多的攻击例子验证和说明入侵检测模型的局限性。益增多的攻击例子验证和说明入侵检测模型的局限性。精219.6 9.6 防火墙防火墙防防火火墙墙是是通通过过创创建建一一个个中中心心控控制制点点来来实实现现
18、网网络络安安全全控控制制的的一一种种技技术术。通通过过在在专专用用网网和和Internet之之间间设设置置路路卡卡，防防火火墙墙监监视视所所有有出出入入专专用用网网的的信信息息流流，并并决决定定那那些些是是可可以以通通过过的的，那那些些是是不不可以的。可以的。给防火墙下一个确切的定义如下：给防火墙下一个确切的定义如下：防防火火墙墙是是放放置置在在两两个个网网络络之之间间的的一一组组组组件件。这这组组元元件件共共同同具具有有下列性质：下列性质：双向通信信息必须经过防火墙双向通信信息必须经过防火墙只允许本地安全策略授权的通信信息通过只允许本地安全策略授权的通信信息通过防火墙本身不会影响信息的流通防
19、火墙本身不会影响信息的流通精22防火墙有三种实现手段防火墙有三种实现手段分分组组过过滤滤：这这种种方方法法过过滤滤掉掉那那些些未未经经证证实实的的主主机机发发来来的的TCP/IP分分组组，并并拒拒绝绝内内部部使使用用那那些些未未经经授授权权的的服服务务以以及及与与其建立连接。其建立连接。IP伪伪装装：以以一一个个虚虚假假的的IP地地址址代代替替内内部部主主机机的的IP地地址址，这样可以躲避外部的监视。这样可以躲避外部的监视。代代理理服服务务：这这种种方方法法是是通通过过在在高高层层建建立立代代理理，从从而而在在网络层完全断绝内部和外部之间的连接。网络层完全断绝内部和外部之间的连接。精23安全手
20、段安全手段加加密密鉴鉴别别：为为公公共共网网络络的的用用户户提提供供身身份份检检查查的的功功能能，这这样样企企业业的的职职员员从从外外部部也也可可以以访访问问企业专用网了。企业专用网了。加加密密隧隧道道：通通过过一一个个与与InternetInternet一一样样的的公公共共媒媒介介，在在两两个个专专用用网网间间建建立立虚虚网网络络安安全全连连接接，这这种种方方式式为为物物理理上上分分散散的的网网络络通通过过Internet,Internet,而而不是租用线建立通信连接提供了可能。不是租用线建立通信连接提供了可能。精24防火墙的种类防火墙的种类 数据包过滤防火墙数据包过滤防火墙 双位置网关防火
21、墙双位置网关防火墙 主机屏蔽防火墙主机屏蔽防火墙 子网屏蔽防火墙子网屏蔽防火墙精25数据包过滤防火墙数据包过滤防火墙精26数据包过滤器数据包过滤器数数据据包包过过滤滤防防火火墙墙是是最最普普通通的的防防火火墙墙，最最适适合合于于简简单单网网络络。这这种种方方法法只只需需简简单单地地在在InternetInternet网网关关处处安安装装一一个个数数据据包包过过滤滤路路由由器，并设置过滤规则阻挡协议或地址。器，并设置过滤规则阻挡协议或地址。数数据据包包过过滤滤器器在在发发送送前前检检查查每每一一个个数数据据包包，在在将将其其与与规规则则进进行行对对比比，决决定定什什么么类类型型的的数数据据包包是
22、是允允许许的的，什什么么类类型型是是禁禁止止的的。IPIP数数据据包包过过滤滤功功能能是是在在比比IPIP协协议议更更低低层层执执行行的的。IPIP在在每每台台主主机机上运行，负责将数据包送到相应的目的地。上运行，负责将数据包送到相应的目的地。数据包过滤路由器对数据包过滤路由器对IPIP数据包的过滤基于如下几个方面：数据包的过滤基于如下几个方面：(1)(1)源源IPIP地址地址 (2)(2)目的目的IPIP地址地址 (3)(3)TCP/UDPTCP/UDP源端口源端口(4)(4)TCP/UDPTCP/UDP目标端口目标端口精27数据包过滤器数据包过滤器数数据据包包过过滤滤设设备备检检查查数数据
23、据包包的的标标题题，这这一一部部分分描描述述了了连连接接及及使使用用的的协协议议。数据包过滤器基于以下条件对数据包过滤：数据包过滤器基于以下条件对数据包过滤：源及目的源及目的IPIP地址地址源源及及目目的的的的端端口口。这这些些端端口口表表明明了了对对TCP/UDP TCP/UDP 的的使使用用，如如FTPFTP、TelnetTelnet、SNMPSNMP或或RealAudioRealAudio。TCPTCP。这这是是一一种种面面向向连连接接的的协协议议，用用于于绝绝大大多多数数服服务务器器，如如FTPFTP、TelnetTelnet。UDPUDP（用用户户数数据据报报协协议议）。这这是是一一
24、种种无无连连接接协协议议，用用于于SNMPSNMP及及RealAudioRealAudio。ICMPICMP（InternetInternet控制报文协议）。这是一种控制报文协议）。这是一种InternetInternet的低层管理协议。的低层管理协议。数据包是否是新的数据包是否是新的TCP/IPTCP/IP连接的第一个数据包或是接着的数据包。连接的第一个数据包或是接着的数据包。数据包是起源于某局部应用或指定用于某局部应用。数据包是起源于某局部应用或指定用于某局部应用。数据包是内界的还是外界的。数据包是内界的还是外界的。精28双位置网关防火墙双位置网关防火墙精29双位置网关防火墙双位置网关防火
25、墙双双位位置置网网关关防防火火墙墙可可能能是是一一种种更更好好的的方方案案。双双位位置置网网关关配配置置在在一一个个主主机机上上设设立立了了两两个个网网络络接接口口并并禁禁止止了了主主机机的的IP IP 移移动动。换换句句话话说说，双双位位置置网网关关连连接接了了两两个个网网络络。一一个个是是内内部部安安全全网网络络，另另一一个个是是通通过过路路由由器器连连接接到到InternetInternet的的周周边边网网络络。这这种种方方案案完完全禁止了全禁止了InternetInternet与内部网络之间的与内部网络之间的IP IP 传输。传输。双双位位置置网网关关通通常常用用于于禁禁止止访访问问没
26、没有有得得到到特特别别允允许许的的所所有有设设备备。例例如如，这这种种类类型型的的防防火火墙墙可可以以用用来来分分隔隔通通信信，允允许许从从外外界界访访问问信息服务器，同时禁止访问任何其他服务器。信息服务器，同时禁止访问任何其他服务器。由由于于存存在在两两个个域域名名服服务务器器，内内部部主主机机的的名名字字对对InternetInternet上上的的任任何何用用户户都都是是不不可可见见的的；然然而而，内内部部用用户户仍仍然然可可因因访访问问全全系系统统，甚至包括周边网上的公用服务器。甚至包括周边网上的公用服务器。精30 主机屏蔽防火墙主机屏蔽防火墙精31 主机屏蔽防火墙主机屏蔽防火墙 主主机
27、机屏屏蔽蔽防防火火墙墙比比双双位位置置防防火火墙墙具具有有稍稍多多一一些些的的灵灵活活性性。这这种种防防火火墙墙在在路路由由器器的的被被保保护护的的一一边边，综综合合使使用用了了数数据据包包过过滤滤路路由由器器和和应应用用网网关关。与与双双位位置置网网关关方方案案不不同同，它它只只需需一一个个网网络络接接口口。在在有有代代理理服服务务的的情情况况下下，应应用用网网关关把把TelnetTelnet（远远程程登登录录）及及其其他他服服务务发发送送给给专专用用系系统统。路路由由器器滤滤除除危危险险协协议议，以以防防这这些些协议到达网关及专用系统。协议到达网关及专用系统。在在主主机机屏屏蔽蔽防防火火墙
28、墙系系统统中中，内内部部网网络络与与周周边边网网络络的的分分隔隔是是逻逻辑辑上上的的，而而不不是是物物理理上上的的。也也就就是是说说，数数据据包包过过滤滤规规则则仅仅仅仅用用于检查于检查InternetInternet与网关及公用服务器之间的通信业务。与网关及公用服务器之间的通信业务。由由于于是是逻逻辑辑的的，而而不不是是物物理理上上的的分分隔隔，因因此此这这种种配配置置不不允允许许存存在在错错误误，如如果果公公用用服服务务器器遭遭到到外外界界攻攻击击，它它可可能能变变成成一一个个同往内部网络的入口。同往内部网络的入口。精32子网屏蔽防火墙子网屏蔽防火墙 子子网网屏屏蔽蔽防防火火墙墙与与双双位
29、位置置屏屏蔽蔽防防火火墙墙相相似似。使使用用这这种种设设置置，防防火火墙墙的的每每个个构构成成部部分分都都位位于于不不同同的的系系统统中中。尽尽管管设设置置更更复复杂杂，但提供了更好的灵活性和更大的处理能力。但提供了更好的灵活性和更大的处理能力。在在这这种种配配置置中中，两两个个路路由由器器建建立立了了一一个个 内内部部屏屏蔽蔽的的子子网网，子子网网中中包包含含应应用用网网关关、信信息息服服务务器器、调调制制解解调调器器或或应应限限制制访访问问的其他系统。的其他系统。在在这这种种类类型型的的防防火火墙墙配配置置条条件件下下，从从InternetInternet上上不不能能直直接接访访问问任任何
30、何系系统统，路路由由器器将将通通信信业业务务转转给给专专用用系系统统。外外部部路路由由器器限限制制了了InternetInternet访访问问专专用用系系统统，并并禁禁止止了了到到InternetInternet的的其其他他通通信信，这这些些通通信信可可能能起起源源于于不不需需要要InternetInternet访访问问的的系系统统。内内部部路路由器在屏蔽子网的系统之间发送通信业务。由器在屏蔽子网的系统之间发送通信业务。精33子网屏蔽防火墙子网屏蔽防火墙精34防火墙未来趋势防火墙未来趋势 第一代防火墙是数据包过滤路由器。第一代防火墙是数据包过滤路由器。第第二二代代防防火火墙墙应应用用和和线线路
31、路网网关关（也称代理器）。（也称代理器）。第第三三代代防防火火墙墙技技术术综综合合了了数数据据包包过过滤滤与与代代理理器器系系统统的的特特点点和和功功能能，以以状状态态的的多多层检查（层检查（SMLISMLI）为代表。为代表。精359.7 9.7 加密加密精36密码系统密码系统单单密密钥钥密密码码体体制制：单单密密钥钥密密码码体体制制又又叫叫对对称称密密码码体体制制，其其加加密密密密钥钥与与解解密密密密钥钥相相同同，或或实实质质上上等等同同，即即从一个易于得出另一个。从一个易于得出另一个。双双密密钥钥密密码码体体制制：双双密密钥钥密密码码体体制制其其加加密密密密钥钥与与解解密密钥不相同，从一个
32、难于得出另一个。密密钥不相同，从一个难于得出另一个。多多密密钥钥密密码码体体制制：多多密密钥钥体体制制是是基基于于非非对对称称加加密密的体制。的体制。无无密密钥钥密密码码体体制制：无无密密钥钥密密码码体体制制是是一一个个没没有有特特定密钥的加密体制定密钥的加密体制精37密码通信系统密码通信系统精38工作原理工作原理组组成成员员的的动动态态特特征征意意味味着着树树需需要要定定期期的的更更新新。也也就就是是说说，多多播播报报文文必必须须定定期期的的发发往往InternetInternet网网络络中中的的每每个个路路由由器器。这这就就使使得得在在大大规规模模传传送送服服务务如如在在InternetI
33、nternet上上的的传传送送问问题题不不容容忽忽视视，而而且且，每每个个路路由由器器必必须须保保留留关关于于源源和和组组的的所所有有状状态态信信息息。尽尽管管这这对对于于小小网网络络来来说说不不构构成成威威胁胁，但但是是当当源源的的数数目目和和多多播播组组成成员员大大幅幅增增加加时就是一个严重的问题。时就是一个严重的问题。精396.10 6.10 核心树核心树核核心心树树（core-based core-based tree,tree,CBTCBT）算算法法将将建建立立一一棵棵被被小小组组中中所所有有的的发发送送者者和和接接收收者者共共享享的的传传送送树树(图图6.10)6.10)，而而不不
34、是是为为每每一一个个源源-组组对对建建立立一一棵棵树树。使使用用CBTCBT算算法法时时，无无论论报报文文是是从从那那个个源源发发出出的的，路路由由器器将将多信道信息沿着相同的传送树来传递。多信道信息沿着相同的传送树来传递。共共享享树树途途径径最最显显著著的的优优势势是是能能够够很很好好的的适适应应大大规规模模网网络络。然然而而，CBTCBT可可能能导导致致在在核核心心路路由由器器附附近近的的流流量量集集中中和和瓶瓶颈颈问问题题。这这是是因因为为从从任任意意源源结结点点发发出出的的信信息息在在接近核心时，都沿着相同的连接。接近核心时，都沿着相同的连接。精40CBTCBT精41设计目的设计目的
35、(1)(1)CBTCBT是是用用于于大大规规模模网网络络，处处理理过过程程中中只只需需要要少少量量的的内内存存和和带带宽宽资资源源。因因为为CBTCBT不不针针对对于于源源，尤尤其其适适合于多发送者的应用程序。合于多发送者的应用程序。(2)(2)CBTCBT时时健健壮壮的的多多播播路路由由选选择择算算法法。为为了了获获得得健健壮的多播传送树，核心将放置在最佳位置。壮的多播传送树，核心将放置在最佳位置。(3)(3)和和其其他他多多播播路路由由选选择择协协议议比比较较而而言言，CBTCBT协协议议比较简单。简单性能导致性能的提高。比较简单。简单性能导致性能的提高。(4)(4)CBTCBT路路由由选
36、选择择算算法法适适度度利利于于协协议议的的。任任何何地地方方都都可可以以安安装装，并并且且支支持持域域间间多多信信道道路路由由选选择择。CBTCBT与与CBMRPCBMRP有有着着良良好好的的协协同同工工作作的的机机制制，CBMRPCBMRP是是一一种种能能够够普遍连接不同种类的多播域的协议。普遍连接不同种类的多播域的协议。精42当一主机成为多播组的成员当一主机成为多播组的成员将执行以下步骤将执行以下步骤 (1)(1)主机向所有连接广播一主机向所有连接广播一IGMPIGMP主机成员报告。主机成员报告。(2)(2)附附近近的的一一个个具具CBTCBT算算法法的的路路由由器器唤唤醒醒加加入入树树的
37、过程：的过程：产生产生JOIN_REQUESTJOIN_REQUEST信息信息 将将信信息息发发往往沿沿着着导导向向组组的的核核心心路路由由器器的的路路径的下一个站点。径的下一个站点。(3)(3)核核心心路路由由或或发发送送路路由由和和核核心心路路由由之之间间的的另另一一路由器确认该信息。路由器确认该信息。精43当一主机成为多播组的成员当一主机成为多播组的成员将执行以下步骤将执行以下步骤 (4)(4)请请求求加加入入的的信信息息在在它它穿穿过过的的路路由由器器暂暂时时建建立立加加入入状状态态，包包括括组组、进进入入的的接接口口和和连连出出的的接接口口。所所有有中中间路由器处理加入请求：间路由器
38、处理加入请求：确认加入请求是从那个接口接收的。确认加入请求是从那个接口接收的。告知信加入的主机告知信加入的主机CBTCBT传送树。传送树。(5)(5)临临时时状状态态如如果果没没有有接接到到从从上上游游传传来来的的确确认认信信息息，将将最最终终超超时时。因因为为有有临临时时加加入入状状态态，加加入入确确认认可可以沿着加入请求来的路径返回。以沿着加入请求来的路径返回。(6)(6)一一旦旦加加入入确确认认到到达达产产生生加加入入请请求求的的路路由由器器，发向这个组的信息将同时发往这个新的接收者。发向这个组的信息将同时发往这个新的接收者。精44CBTCBT (4)(4)请请求求加加入入的的信信息息在
39、在它它穿穿过过的的路路由由器器暂暂时时建建立立加加入入状状态态，包包括括组组、进进入入的的接接口口和和连连出出的的接接口口。所所有有中中间路由器处理加入请求：间路由器处理加入请求：确认加入请求是从那个接口接收的。确认加入请求是从那个接口接收的。告知信加入的主机告知信加入的主机CBTCBT传送树。传送树。(5)(5)临临时时状状态态如如果果没没有有接接到到从从上上游游传传来来的的确确认认信信息息，将将最最终终超超时时。因因为为有有临临时时加加入入状状态态，加加入入确确认认可可以沿着加入请求来的路径返回。以沿着加入请求来的路径返回。(6)(6)一一旦旦加加入入确确认认到到达达产产生生加加入入请请求
40、求的的路路由由器器，发向这个组的信息将同时发往这个新的接收者。发向这个组的信息将同时发往这个新的接收者。精456.116.11路由多播选择算法路由多播选择算法KMBKMB理想化的多播路由选择算法应该是：理想化的多播路由选择算法应该是：构建树时具有所想要的成本和延迟特征。构建树时具有所想要的成本和延迟特征。算算法法可可以以适适用用于于广广播播组组的的成成员员增增加加的的情情况况（如如CBTCBT），而而不不是是每每次次成成员员增增加加都都需需要要更更新新（如如SMTSMT）。）。维护原始路由的特性。维护原始路由的特性。不干扰正在进行的数据传送。不干扰正在进行的数据传送。是由接收者驱动的。是由接收
41、者驱动的。精46问题的形式化定义问题的形式化定义给定图给定图G=(V,E,c)V=顶点集顶点集E=边集边集c=成本函数成本函数c:EZ0+(边边非负整数非负整数)Z-顶点集顶点集:终结集合终结集合(有时用有时用M表示表示)S-点集点集:非终结集合非终结集合TO:初始树初始树=s.Q:树上顶点的优先级队列树上顶点的优先级队列Vt:树上顶点树上顶点At:树上边树上边 精47Dijkstra最短路径算法Begin.v V,将将v加到集合加到集合U,Distance(v)=cost(s,v)Distance(s)=0;从从U中删除中删除s.whileU不为空不为空do具有最小距离的任何具有最小距离的任
42、何G的成员的成员v.U=U-v.For每个每个v的近邻的近邻w,doifmember(w,U)distance(w)=min(distance(w),cost(w,v)+distance(v);Stop.精48 Matsuyama最短成本路径启发式算法BeginT1:包含任选的包含任选的iZ的的G的子树的子树.k=1;Zk=i.找到离找到离Tk最近的最近的i Z-Zk在在Tk的基础上加入从的基础上加入从Tk到到I的最短路径建树的最短路径建树Tk+1k=k+1.Ifkp,转转T1.Ifk=p,输出结论输出结论TpStop.精49 KMB 算法输入：图输入：图G和顶点集和顶点集Z输出：输出：Ste
43、iner树树Th步骤：步骤：1由由G和和Z建立完全有向带权图建立完全有向带权图G1=（V1，E1，c1）。）。2找到找到G1的最小生成树。的最小生成树。3用用G中相应的最短路径替换中相应的最短路径替换T1中的一边，建立中的一边，建立G的子图的子图Gs。4找到找到Gs的最小生成树的最小生成树Ts。5.如如必必要要的的话话删删去去Ts中中的的边边，构构建建Steiner树树Th，使使得得Th中中所所有有的叶子为的叶子为Steiner点。点。精50KMBKMB算法算法 KMBKMB算算法法最最坏坏时时间间复复杂杂度度 O O（|S|V|S|V|2 2）。成本不大于成本不大于2 2（1-1/1-1/l
44、 l）最优成本，其中最优成本，其中l=l=SteinerSteiner树的叶结点数。树的叶结点数。精51KMB算法的工作过程精52KMB算法的工作过程精53成本建模成本建模W(e,i):边边e上波长为上波长为 i的成本。的成本。如果边如果边e上上 i值不确定值不确定w值为无穷。值为无穷。cv(p,q):v结点上波长从结点上波长从 p变为变为 q的代价。的代价。如果如果v结点上波长不能从结点上波长不能从 p变为变为 qcv值为无穷。值为无穷。Ifp=q,cv(p,q)=0。C(T)=v Tw(p(v),v),(v)+v T-sCp(v)(p(v),(v)，其中其中p(v)是树中是树中v点的父母。
45、点的父母。精54虚主干 虚虚主主干干是是基基本本图图中中的的一一棵棵树树，用用作作建建立立多多播播树树的的模模板板，也也就就是是说说，扩扩展展为为虚虚主主干干的的结结点点具具有有最最大大可可能能性性变变为为多多播播树树中中的的一一部部分分。如如果果一一个个结结点点有有越越多多的的路路径径穿穿过过它它，就就有有越越大大的的可可能能成成为为多多播播树树的的一一部部分分。定定义义点点v vi i 的的权权重重 W(vW(vi i)=穿穿越越 v vi i的的最最短短路路径径的的数数目目，以以权权重重作作为为是是否否吸吸收收一一个个结点为虚主干的重要标准结点为虚主干的重要标准精55建立虚主干的步骤 （
46、1 1）找到图）找到图 G G中所有结点对的最短路径。中所有结点对的最短路径。（2 2）给图）给图 G G中的所有结点赋权值。中的所有结点赋权值。（3 3）找到主干结点集合）找到主干结点集合F F。（4 4）为主干结点集合建立完全图。为主干结点集合建立完全图。（5 5）在完全图上找到最小生成树。）在完全图上找到最小生成树。（6 6）把把最最小小生生成成树树上上的的边边转转化化为为图图G G上上相相应应的的最最短短路径。路径。（7 7）执执行行最最小小生生成成树树算算法法，去去除除不不必必要要的的结结点点和和连连接，获得虚主干。接，获得虚主干。精56VTDM 路由选择算法 1.1.建立虚主干。建
47、立虚主干。2.2.往多播组中加入一结点：往多播组中加入一结点：建立该结点到已建立的虚主干之间的最短路由。建立该结点到已建立的虚主干之间的最短路由。虚主干到源的路由已经建立起来了。虚主干到源的路由已经建立起来了。把结点加入多播组。把结点加入多播组。3.3.从多播组中去除一结点：从多播组中去除一结点：先从多播组中移出该结点。先从多播组中移出该结点。如果是叶子结点，从多播树中去掉该叶子。如果是叶子结点，从多播树中去掉该叶子。如果该结点没有下属结点，剪除多余的枝干。如果该结点没有下属结点，剪除多余的枝干。精57增加结点(加入结点 B)第一步第一步:如果结点如果结点B B在虚主干上，指定它为结点在虚主干
48、上，指定它为结点A A，转到第二步。转到第二步。否否则则找找到到B B到到虚虚主主干干的的最最短短路路由由，把把最最短短路路由由中中不不属属于于多多播播树树的那部分加入多播树中。的那部分加入多播树中。设虚主干上沿最短路径离设虚主干上沿最短路径离B B最近的点为最近的点为A A。第二步第二步:如果如果A A已经在多播树上，转到第三步。已经在多播树上，转到第三步。否否则则，把把从从A A到到源源结结点点的的路路由由不不在在多多播播树树上上的的那那部部分分加加入入多多播播树中。树中。第三步第三步:把结点把结点B B加入多播树中。加入多播树中。精58模拟结果 定定义义平平均均失失效效率率=使使用用算算
49、法法A的的树树成成本本/使使用用算算法法B的的树树成本。成本。将将VTDM与与动动态态贪贪心心法法(DG)，最最短短路路径径法法(SP)比比较较。对对于于结结点点数数增增加加的的平平均均失失效效率率，VTDM大大大大优优于于SP，优优于于DG。对对于于多多播播组组的的规规模模增增大大的的平平均均失失效效率率，VTDM在在大大规规模模组组中中大大大大优优于于SP，优优于于DG。对对于于多多播播树树中中结结点点的的最最大大度度(也也就就是是数数据据复复制制的的份份数数)，VTDM大大大大小小于于SP，小于小于DG。精596.13 限界最短多播算法BSMA BSMA算算法法使使多多播播树树的的成成本
50、本最最小小化化，并并且且保保证证所所有有的的延延迟迟小小于于预预先先设设定定的的界界限限。BSMA的的可可行行领领域域是是所所有有延延迟迟受受限的限的Steiner树。树。先先简简要要的的描描述述一一下下BSMA的的步步骤骤：首首先先用用Dijkstra最最短短路路径径算算法法构构建建最最小小延延迟迟Steiner树树T0，在在可可行行的的区区域域内内不不断断的重复更新的重复更新T0以获的更低的代价。以获的更低的代价。精60BSMA成本函数的定义 使用驱动成本使用驱动成本沿路径的连接成本的总和最小化。沿路径的连接成本的总和最小化。拥塞驱动成本拥塞驱动成本沿路径的最大连接成本最小化。沿路径的最大