第九章 网络安全 (ppt).ppt_第1页
第九章 网络安全 (ppt).ppt_第2页
第九章 网络安全 (ppt).ppt_第3页
第九章 网络安全 (ppt).ppt_第4页
第九章 网络安全 (ppt).ppt_第5页
已阅读5页,还剩67页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、2020/10/26,史忠植 高级计算机网络,1,高级计算机网络,2020/10/26,史忠植 高级计算机网络,2,内容提要,9.1 网络安全概述 9.2 网络安全的级别 9.3 网络安全的策略 9.4 虚拟专用网 9.5 入侵检测 9.6 防火墙 9.7 加密 9.8 常规密码体系 9.9 公开密钥密码体制 9.10 报文的鉴别 9.11 密钥分配 9.12 公钥证书 9.13 网络安全的发展,2020/10/26,史忠植 高级计算机网络,3,9.1 网络安全概述,众所周知,作为全球使用范围最大的信息网,Internet自身协议的开放性极大地方便了各种计算机连网,拓宽了共享资源。但是,由于在

2、早期网络协议设计上对安全问题的忽视,以及在使用和管理上的无政府状态,给了众多的hacker们许多机会,使Internet自身的安全受到严重威胁,与它有关的安全事故屡有发生。对网络安全的威胁主要表现在:非授权访问、冒充合法用户、破坏数据完整性、干扰系统正常运行、利用网络传播病毒、线路窃听等方面。这就要求我们对与Internet互连所带来的安全性问题予以足够重视。,2020/10/26,史忠植 高级计算机网络,4,9.1 网络安全概述,保密性 安全协议的设计 访问控制,2020/10/26,史忠植 高级计算机网络,5,9.2 网络安全的级别,D1级 C1级 C2级 B1级 B2级 B3级 A级,2

3、020/10/26,史忠植 高级计算机网络,6,9.3 网络安全的策略, 你试图保护那些资源? 你需要保护这些资源防备那些人? 可能存在什么样的威胁? 资源如何重要? 你能够采取什么措施以合算和节时的方式保护你的财产?,2020/10/26,史忠植 高级计算机网络,7,网络操作系统的安全性能,NetWare网络操作系统 Windows NT 网络操作系统 UNIX网络操作系统,2020/10/26,史忠植 高级计算机网络,8,NetWare网络操作系统, 登录安全 NetWare登录安全需要用户输入一个有效的用户名和口令,并由此控制用户对网络的访问。 受托者 一个受托者是指对特殊的目录、文件或

4、对象有特定的控制权的一个用户或一个用户组。网络管理员可通过受托者来指定授予访问权。 权限 权限表示了一个受托者对目录、文件和对象有什么级别的访问权。权限可分为目录权限、文件权限、对象权限和属性权限。,2020/10/26,史忠植 高级计算机网络,9,NetWare网络操作系统, 继承 继承简化了为所有用户、目录、文件及对象创建相同的受托者权限分配的任务。虽然继承给管理员提供了很大的方便,但是必须小心使用继承以确保权限的适当分配。 有效权限 当一个用户开始操作时,NetWare就会计算用户对给定的目录、文件或对象的有效权限。有效权限是指用户对目录、文件或对对象实际拥有的权限。 属性 又称标志,主

5、要描述了特殊目录和文件的特性,这些属性定义了操作权限。属性在NetWare安全环境中特别重要。,2020/10/26,史忠植 高级计算机网络,10,Windows NT 网络操作系统, 登录进程 这一部分接受用户的登录请求,包括远程请求。 局部安全授权(LSA) 这部分保证任何已经登录的用户可以访问系统,局部安全授权产生访问令牌、管理策略,同时给用户提供鉴别服务。,2020/10/26,史忠植 高级计算机网络,11,Windows NT 网络操作系统,2020/10/26,史忠植 高级计算机网络,12,UNIX网络操作系统,UNIX安全涉及的主要范围是用户、用户组和文件系统。 用户和用户组 象

6、Windows NT一样UNIX利用用户名和口令来识别用户。每个用户被指定到某一用户组,就能指定这些用户与用户组访问文件和目录。这是UNIX安全存在的实际问题。即为使用户能够创建其它用户,可简单允许该用户写访问口令文件。 文件系统 UNIX的文件系统类似于NT,也是以层次结构组织的。每个文件有一组简单的许可权或权限,对三类用户文件拥有者,文件拥有者组与在其它组上的用户,各不相同。可使用的许可权包括:读、写、执行。,2020/10/26,史忠植 高级计算机网络,13,网络设计及硬件,安全设备 (1)脸部特征识别设备 (2)智能卡; (3)Web站点阻断工具 (4)冗余设备,2020/10/26,

7、史忠植 高级计算机网络,14,虚拟网络,虚拟局域网 基于端口的虚拟LAN。这种VLAN是最简单的,但提供了绝大部分控制功能和安全特性。基于VLAN实际所连接的端口给VLAN分配设备。端口分配是静态的,只有管理员才能改变。 MAC地址VLAN。配置MAC地址VLAN更为复杂。VLAN 网络由一组MAC 地址组成,AutoTracker软件将这组地址转换成了一个广播域。由于是基于对MAC地址的鉴别,这种类型的VLAN是一种更安全的方案。机器在访问VLAN之前,必须先具有一个可识别的VLAN地址。,2020/10/26,史忠植 高级计算机网络,15,虚拟网络,虚拟局域网 第三层。在第三层的VLAN中

8、,管理员用不同的协议要求对不同的VLAN分配通信业务。 协议策略VLAN。这种类型的网络基于数据帧内的协议标准。比如,管理员可以在这类网络的数据帧内指明一个数据场用于确定VLAN的隶属。 多终点传输VLAN。多终点传输VLAN通过“一点对多点”或“多点对多点”的方式传输信息。这对新闻广播或电视会议之类的应用是很有用的。,2020/10/26,史忠植 高级计算机网络,16,虚拟网络,虚拟局域网 基于政策的VLAN。这类VLAN使管理员能组合应用VLAN政策以产生灵活的VLAN 。设备可以配置给不同政策条件下的VLAN 系统。网络中的每个转换器都能识别各种VLAN政策。 用户鉴别VLAN。这是一种

9、高安全性能的VLAN,它要求用户在访问网络资源之前,先要通过服务器对用户的鉴别。,2020/10/26,史忠植 高级计算机网络,17,9.4 虚拟专用网,VPN通过公用网络在多个地区之间建立了安全链路。 VPN新模型在公用INTERNET中勾划出一个“专用”网络,使不同地方的网点或子网能相互连接在一起,为企业建立了一个实实在在的WAN。这与VLAN不同,它将大型网络分成多个子网,在通过软件来管理其间的连接。 有直接式的和隧道式的两种类型的VPN。直接式的VPN使用IP寻址并通过VPN建立数据的直接控制。它加密数据,并作为基于用户而不是IP地址的鉴别。另一方面,隧道模式的VPN使用IP帧作为数据

10、包的一个隧道。这种模式的网络受到侵入,入侵者只能访问目标网络。如果是双向模式,源网络及目标网络二者都会被侵入。,2020/10/26,史忠植 高级计算机网络,18,9.5 入侵检测,2020/10/26,史忠植 高级计算机网络,19,2020/10/26,史忠植 高级计算机网络,20,异常检测模型,(1)通过将征抽取或事件到特征字符串的映射形成异常行为空间; (2)系统运行时采集可观察的事件窨并进行筛选; (3)采集到的事件与预先建好的异常行为空间中的事件比较,差异标闪准可用预先确定的阈值或某个统计量,超过则判断为攻击。,2020/10/26,史忠植 高级计算机网络,21,滥用检测模型,对用户

11、的行为特征与某种攻击活动的行为特征进行比较。这种方法的基本前提是对可能收集到入侵例子的行为特征进行分析和提取,并使特征尽量覆盖可能的变种攻击。然而,这种方法的有效性也由于攻击的多样性和利用合法手段进行攻击的例子的增多而显出其无能为力的一面。 另外不论哪一种入侵检测的教学模型,都同样面临一个实时和处理大量信息的难题。如要检测的信息源包括:网络包、主机事件(进程、任务等)、网络状态(流社信息等)、主机状态(机器忙闲等)。日益增多的攻击例子验证和说明入侵检测模型的局限性。,2020/10/26,史忠植 高级计算机网络,22,9.6 防火墙,防火墙是通过创建一个中心控制点来实现网络安全控制的一种技术。

12、通过在专用网和Internet之间设置路卡,防火墙监视所有出入专用网的信息流,并决定那些是可以通过的,那些是不可以的。 给防火墙下一个确切的定义如下: 防火墙是放置在两个网络之间的一组组件。这组元件共同具有下列性质: 双向通信信息必须经过防火墙 只允许本地安全策略授权的通信信息通过 防火墙本身不会影响信息的流通,2020/10/26,史忠植 高级计算机网络,23,防火墙有三种实现手段, 分组过滤:这种方法过滤掉那些未经证实的主机发来的TCP/IP分组,并拒绝内部 使用那些未经授权的服务以及与其建立连接。 IP伪装:以一个虚假的IP地址代替内部主机的IP地址,这样可以躲避外部的监视。 代理服务:

13、这种方法是通过在高层建立代理,从而在网络层完全断绝内部和外部之间的连接。,2020/10/26,史忠植 高级计算机网络,24,安全手段, 加密鉴别:为公共网络的用户提供身份检查的功能,这样企业的职员从外部也可以访问企业专用网了。 加密隧道:通过一个与Internet一样的公共媒介,在两个专用网间建立虚网络安全连接,这种方式为物理上分散的网络通过Internet,而不是租用线建立通信连接提供了可能。,2020/10/26,史忠植 高级计算机网络,25,防火墙的种类,数据包过滤防火墙 双位置网关防火墙 主机屏蔽防火墙 子网屏蔽防火墙,2020/10/26,史忠植 高级计算机网络,26,数据包过滤防

14、火墙,2020/10/26,史忠植 高级计算机网络,27,数据包过滤器,数据包过滤防火墙是最普通的防火墙,最适合于简单网络。这种方法只需简单地在Internet网关处安装一个数据包过滤路由器,并设置过滤规则阻挡协议或地址。 数据包过滤器在发送前检查每一个数据包,在将其与规则进行对比,决定什么类型的数据包是允许的,什么类型是禁止的。IP数据包过滤功能是在比IP协议更低层执行的。IP在每台主机上运行,负责将数据包送到相应的目的地。 数据包过滤路由器对IP数据包的过滤基于如下几个方面: (1)源IP地址 (2)目的IP地址 (3)TCP/UDP源端口 (4)TCP/UDP目标端口,2020/10/2

15、6,史忠植 高级计算机网络,28,数据包过滤器,数据包过滤设备检查数据包的标题,这一部分描述了连接及使用的协议。数据包过滤器基于以下条件对数据包过滤: 源及目的IP地址 源及目的的端口。这些端口表明了对TCP/UDP 的使用,如FTP、Telnet、SNMP或RealAudio。 TCP。这是一种面向连接的协议,用于绝大多数服务器,如FTP、Telnet。 UDP(用户数据报协议)。这是一种无连接协议,用于SNMP及RealAudio。 ICMP(Internet控制报文协议)。这是一种Internet的低层管理协议。 数据包是否是新的TCP/IP连接的第一个数据包或是接着的数据包。 数据包是

16、起源于某局部应用或指定用于某局部应用。 数据包是内界的还是外界的。,2020/10/26,史忠植 高级计算机网络,29,双位置网关防火墙,2020/10/26,史忠植 高级计算机网络,30,双位置网关防火墙,双位置网关防火墙可能是一种更好的方案。双位置网关配置在一个主机上设立了两个网络接口并禁止了主机的IP 移动。换句话说,双位置网关连接了两个网络。一个是内部安全网络,另一个是通过路由器连接到Internet的周边网络。这种方案完全禁止了Internet与内部网络之间的IP 传输。 双位置网关通常用于禁止访问没有得到特别允许的所有设备。例如,这种类型的防火墙可以用来分隔通信,允许从外界访问信息

17、服务器,同时禁止访问任何其他服务器。 由于存在两个域名服务器,内部主机的名字对Internet上的任何用户都是不可见的;然而,内部用户仍然可因访问全系统,甚至包括周边网上的公用服务器。,2020/10/26,史忠植 高级计算机网络,31,主机屏蔽防火墙,2020/10/26,史忠植 高级计算机网络,32,主机屏蔽防火墙,主机屏蔽防火墙比双位置防火墙具有稍多一些的灵活性。这种防火墙在路由器的被保护的一边,综合使用了数据包过滤路由器和应用网关。与双位置网关方案不同,它只需一个网络接口。在有代理服务的情况下,应用网关把Telnet(远程登录)及其他服务发送给专用系统。路由器滤除危险协议,以防这些协议

18、到达网关及专用系统。 在主机屏蔽防火墙系统中,内部网络与周边网络的分隔是逻辑上的,而不是物理上的。也就是说,数据包过滤规则仅仅用于检查Internet与网关及公用服务器之间的通信业务。 由于是逻辑的,而不是物理上的分隔,因此这种配置不允许存在错误,如果公用服务器遭到外界攻击,它可能变成一个同往内部网络的入口。,2020/10/26,史忠植 高级计算机网络,33,子网屏蔽防火墙,子网屏蔽防火墙与双位置屏蔽防火墙相似。使用这种设置,防火墙的每个构成部分都位于不同的系统中。尽管设置更复杂,但提供了更好的灵活性和更大的处理能力。 在这种配置中,两个路由器建立了一个 内部屏蔽的子网,子网中包含应用网关、

19、信息服务器、调制解调器或应限制访问的其他系统。 在这种类型的防火墙配置条件下,从Internet上不能直接访问任何系统,路由器将通信业务转给专用系统。外部路由器限制了Internet访问专用系统,并禁止了到Internet的其他通信,这些通信可能起源于不需要Internet访问的系统。内部路由器在屏蔽子网的系统之间发送通信业务。,2020/10/26,史忠植 高级计算机网络,34,子网屏蔽防火墙,2020/10/26,史忠植 高级计算机网络,35,防火墙未来趋势,第一代防火墙是数据包过滤路由器。 第二代防火墙应用和线路网关(也称代理器)。 第三代防火墙技术综合了数据包过滤与代理器系统的特点和功

20、能,以状态的多层检查(SMLI)为代表。,2020/10/26,史忠植 高级计算机网络,36,9.7 加密,2020/10/26,史忠植 高级计算机网络,37,密码系统,单密钥密码体制:单密钥密码体制又叫对称密码体制,其加密密钥与解密密钥相同,或实质上等同,即从一个易于得出另一个。 双密钥密码体制:双密钥密码体制其加密密钥与解密密钥不相同,从一个难于得出另一个。 多密钥密码体制:多密钥体制是基于非对称加密的体制。 无密钥密码体制:无密钥密码体制是一个没有特定密钥的加密体制,2020/10/26,史忠植 高级计算机网络,38,密码通信系统,2020/10/26,史忠植 高级计算机网络,39,工作

21、原理,组成员的动态特征意味着树需要定期的更新。也就是说,多播报文必须定期的发往Internet网络中的每个路由器。这就使得在大规模传送服务如在Internet上的传送问题不容忽视,而且,每个路由器必须保留关于源和组的所有状态信息。尽管这对于小网络来说不构成威胁,但是当源的数目和多播组成员大幅增加时就是一个严重的问题。,2020/10/26,史忠植 高级计算机网络,40,6.10 核心树,核心树(core-based tree, CBT)算法将建立一棵被小组中所有的发送者和接收者共享的传送树(图6.10),而不是为每一个源-组对建立一棵树。使用CBT算法时,无论报文是从那个源发出的,路由器将多信

22、道信息沿着相同的传送树来传递。 共享树途径最显著的优势是能够很好的适应大规模网络。然而,CBT可能导致在核心路由器附近的流量集中和瓶颈问题。这是因为从任意源结点发出的信息在接近核心时,都沿着相同的连接。,2020/10/26,史忠植 高级计算机网络,41,CBT,2020/10/26,史忠植 高级计算机网络,42,设计目的,(1) CBT是用于大规模网络,处理过程中只需要少量的内存和带宽资源。因为CBT不针对于源,尤其适合于多发送者的应用程序。 (2) CBT时健壮的多播路由选择算法。为了获得健壮的多播传送树,核心将放置在最佳位置。 (3)和其他多播路由选择协议比较而言,CBT协议比较简单。简

23、单性能导致性能的提高。 (4)CBT路由选择算法适度利于协议的。任何地方都可以安装,并且支持域间多信道路由选择。CBT与CBMRP有着良好的协同工作的机制,CBMRP是一种能够普遍连接不同种类的多播域的协议。,2020/10/26,史忠植 高级计算机网络,43,当一主机成为多播组的成员将执行以下步骤,(1)主机向所有连接广播一IGMP主机成员报告。 (2)附近的一个具CBT算法的路由器唤醒加入树的过程: 产生JOIN_REQUEST信息 将信息发往沿着导向组的核心路由器的路径的下一个站点。 (3)核心路由或发送路由和核心路由之间的另一路由器确认该信息。,2020/10/26,史忠植 高级计算机

24、网络,44,当一主机成为多播组的成员将执行以下步骤,(4)请求加入的信息在它穿过的路由器暂时建立加入状态,包括组、进入的接口和连出的接口。所有中间路由器处理加入请求: 确认加入请求是从那个接口接收的。 告知信加入的主机CBT传送树。 (5)临时状态如果没有接到从上游传来的确认信息,将最终超时。因为有临时加入状态,加入确认可以沿着加入请求来的路径返回。 (6)一旦加入确认到达产生加入请求的路由器,发向这个组的信息将同时发往这个新的接收者。,2020/10/26,史忠植 高级计算机网络,45,CBT,(4)请求加入的信息在它穿过的路由器暂时建立加入状态,包括组、进入的接口和连出的接口。所有中间路由

25、器处理加入请求: 确认加入请求是从那个接口接收的。 告知信加入的主机CBT传送树。 (5)临时状态如果没有接到从上游传来的确认信息,将最终超时。因为有临时加入状态,加入确认可以沿着加入请求来的路径返回。 (6)一旦加入确认到达产生加入请求的路由器,发向这个组的信息将同时发往这个新的接收者。,2020/10/26,史忠植 高级计算机网络,46,6.11路由多播选择算法KMB,理想化的多播路由选择算法应该是: 构建树时具有所想要的成本和延迟特征。 算法可以适用于广播组的成员增加的情况(如CBT),而不是每次成员增加都需要更新(如SMT)。 维护原始路由的特性。 不干扰正在进行的数据传送。 是由接收

26、者驱动的。,2020/10/26,史忠植 高级计算机网络,47,问题的形式化定义,给定图 G = (V, E, c) V= 顶点集 E= 边集 c= 成本函数 c: E Z0+ ( 边 非负整数) Z-顶点集: 终结集合(有时用M表示) S-点集: 非终结集合 TO: 初始树 = s. Q : 树上顶点的优先级队列 Vt: 树上顶点 At: 树上边,2020/10/26,史忠植 高级计算机网络,48,Dijkstra最短路径算法,Begin. vV, 将v加到集合U, Distance(v) = cost(s, v) Distance(s) = 0; 从U中删除s. while U 不为空 d

27、o 具有最小距离的任何G的成员v. U=U-v. For 每个v的近邻 w , do if member(w, U) distance(w) = min(distance(w), cost(w, v) + distance(v) ); Stop.,2020/10/26,史忠植 高级计算机网络,49,Matsuyama最短成本路径启发式算法,Begin T1 : 包含任选的iZ的G的子树 . k = 1; Zk=i. 找到离 Tk 最近的i Z - Zk 在Tk 的基础上加入从Tk 到 I的最短路径建树Tk+1 k = k+1. If k p, 转T1. If k = p, 输出结论 Tp St

28、op.,2020/10/26,史忠植 高级计算机网络,50,KMB 算法,输入:图G和顶点集Z 输出:Steiner树Th 步骤: 1由G和Z建立完全有向带权图G1=(V1,E1,c1)。 2找到G1的最小生成树。 3用G中相应的最短路径替换T1中的一边,建立G的子图Gs。 4找到Gs的最小生成树Ts。 5. 如必要的话删去Ts中的边,构建Steiner树Th,使得Th中所有的叶子为Steiner点。,2020/10/26,史忠植 高级计算机网络,51,KMB算法,KMB算法最坏时间复杂度 O(|S|V|2)。成本不大于2(1-1/l)最优成本,其中 l = Steiner树的叶结点数。,20

29、20/10/26,史忠植 高级计算机网络,52,KMB算法的工作过程,2020/10/26,史忠植 高级计算机网络,53,KMB算法的工作过程,2020/10/26,史忠植 高级计算机网络,54,成本建模,W (e, i ): 边e上波长为i的成本。 如果边e上i值不确定w值为无穷。 cv(p , q ): v结点上波长从p变为q的代价。 如果v结点上波长不能从p变为q cv值为无穷。 If p = q, cv(p , q ) =0。 C(T) = v T w(p(v), v), (v) +v T-s C p(v) ( (p(v), (v), 其中p(v) 是树中v点的父母。,2020/10/

30、26,史忠植 高级计算机网络,55,虚主干,虚主干是基本图中的一棵树,用作建立多播树的模板,也就是说,扩展为虚主干的结点具有最大可能性变为多播树中的一部分。如果一个结点有越多的路径穿过它,就有越大的可能成为多播树的一部分。定义点vi 的权重 W(vi) = 穿越 vi的最短路径的数目,以权重作为是否吸收一个结点为虚主干的重要标准,2020/10/26,史忠植 高级计算机网络,56,建立虚主干的步骤,(1)找到图 G中所有结点对的最短路径。 (2)给图 G中的所有结点赋权值。 (3)找到主干结点集合F。 (4)为主干结点集合建立完全图。 (5)在完全图上找到最小生成树。 (6)把最小生成树上的边

31、转化为图G上相应的最短路径。 (7)执行最小生成树算法,去除不必要的结点和连接,获得虚主干。,2020/10/26,史忠植 高级计算机网络,57,VTDM 路由选择算法,1. 建立虚主干。 2. 往多播组中加入一结点: 建立该结点到已建立的虚主干之间的最短路由。 虚主干到源的路由已经建立起来了。 把结点加入多播组。 3. 从多播组中去除一结点: 先从多播组中移出该结点。 如果是叶子结点,从多播树中去掉该叶子。 如果该结点没有下属结点,剪除多余的枝干。,2020/10/26,史忠植 高级计算机网络,58,增加结点 (加入结点 B),第一步: 如果结点B在虚主干上,指定它为结点A,转到第二步。 否

32、则找到B到虚主干的最短路由,把最短路由中不属于多播树的那部分加入多播树中。 设虚主干上沿最短路径离B最近的点为A。 第二步: 如果A已经在多播树上,转到第三步。 否则,把从A到源结点的路由不在多播树上的那部分加入多播树中。 第三步: 把结点B加入多播树中。,2020/10/26,史忠植 高级计算机网络,59,模拟结果,定义平均失效率 = 使用算法A的树成本/使用算法B的树成本。 将VTDM与动态贪心法 (DG), 最短路径法 (SP)比较。对于结点数增加的平均失效率,VTDM大大优于SP, 优于DG。对于多播组的规模增大的平均失效率,VTDM在大规模组中大大优于SP, 优于DG。对于多播树中结

33、点的最大度 (也就是数据复制的份数),VTDM大大小于 SP,小于DG。,2020/10/26,史忠植 高级计算机网络,60,6.13 限界最短多播算法BSMA,BSMA算法使多播树的成本最小化,并且保证所有的延迟小于预先设定的界限。BSMA的可行领域是所有延迟受限的Steiner树。 先简要的描述一下BSMA的步骤:首先用Dijkstra最短路径算法构建最小延迟 Steiner 树 T0,在可行的区域内不断的重复更新T0以获的更低的代价。,2020/10/26,史忠植 高级计算机网络,61,BSMA成本函数的定义,使用驱动成本 沿路径的连接成本的总和最小化。 拥塞驱动成本 沿路径的最大连接成

34、本最小化。 连接成本函数 将连接的成本和连接的使用联系起来。 连接延迟函数 连接上排队、传输、散播的延迟。 目标延迟限界函数 (DDF) 从源到每个目的站点沿途的延迟的上界。,2020/10/26,史忠植 高级计算机网络,62,优化Steiner树的方法,用Dijkstra最短路径算法构建最小延迟Steiner树T0的方法在前面已经介绍过了。怎样在可行的区域内不断的优化T0,使最后获得的树的成本最小呢。这里要用到路径交换法,优化Tj 获得Tj+1步骤如下: 从Tj中选择路径 p Tj = Tj1 + Tj2 p 从图 G 中选取不在 Tj中的新路径 ps 替代从 Tj中删除的路径。 Tj+1

35、= Tj1 + Tj2 ps. Tj+1 满足延迟受限。,2020/10/26,史忠植 高级计算机网络,63,超边,首先从 Tj 获得 Tj/,树Tj/ 含源结点,所有的目标结点和所有度大于2的中继结点。Tj/ 的边称为超边,在超边的两个端结点之间的所有结点,都是度为2的转送结点。每条超边都是 Tj 中交换的候选路径,2020/10/26,史忠植 高级计算机网络,64,BSMA具体算法,初始化所有超边为无标记。 第一步:在所有无标记边中, BSMA 选中最高成本的超边 Ph 。 将Ph 和另一条成本低一些的超边交换,得到的树延迟受限。 以下两种情况必有一种发生: 1.延迟限界的最短路径与 Ph

36、相同。 标记超边,转第一步。 2.延迟限界的最短路径不同于Ph. 替换 删除所有的超边的记号。 转到第一步。 当所有超边都被标记后算法停止。,2020/10/26,史忠植 高级计算机网络,65,BSMA 动态递增,BSMA 动态递增的计算子树 Tj1 和 Tj2之间的k条最短路径。当构成延迟限界树的最短路径找到后决定K,以下两个条件满足的时候,最短路径递增构建停止: 1. 新发现的最短路径和刚删除的等长。 2. 新发现的最短路径使新树不超过延迟限界。 扩展的Dijkstra算法用于构建两子树间的最短路径,而不是两点之间的最短路径。在Tj1中,一个伪源结点s与所有结点相连。在Tj2中,一个伪目标d所有结点

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论