文档介绍：声明
本人声明,所呈交的学位论文是在导师的指导下独立完成的。论文中取得的研究成果除加以标注和致谢的地方外,不包含其他人已经发表或撰写过的研究成果,也不包括本人为获得其它学位而使用过的材料。与我共同工作过的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。
作者签名: 日 期:
学位论文版权使用授权书
本学位论文作者和指导教师完全了解沈阳建筑大学有关保留、使用学位论文的规定:即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权沈阳建筑大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。(如作者和导师同意论文交流,请在下方签名;否则视为不同意。)
作者和导师同意网上交流的时间为作者获得学位后:
不限□ 半年□ 一年□ 一年半□ 两年□作者签名: 导师签名:
日 期: 日 期:
第一章绪论
研究的背景和意义
随着互联网的飞速发展,计算机网络己经逐步地深入到工业、农业、商业、医学、教育等生活的各个领域,影响并改变着我们日常的生活方式。由于网络用户数量持续呈指数性增长[1],不同用户对不同的多媒体应用有着不同的服务质量[2] (Quality of Service,QoS) 要求。用户越来越多地提出了包括多媒体通信在内的综合服务要求,如视频会议、视频点播、IP 可视电话、远程教育、虚拟现实等,由于这些应用都要求“现场网络直播”,不能容忍画面的过多“抖动”,对数据包的到达时间有严格的要求。当然,在不影响画面质量的情况下也大都能容忍一定程度的信息丢失和错误。这就对网络提出了不同于数据应用的服务质量要求,要求网络应能根据用户的要求来分配和调度资源,能提供端到端的 QoS 控制和保证。
然而,当今的(IPv4 标准)只提供“尽力而为(best-effort)”服务[3],不保证 QoS。在这种服务模型下,所有的业务流公平地竞争网络资源,路由器对所有的 IP 包都采用先来先处理(e First Service,FCFS)的工作方式,它尽最大努力将 IP 包送达目的地,这很适合 Email、FTP、型对网络的资源缺乏有效的分配和管理,当网络负载较轻时,各个应用得到的传输服务质量尚可,随着用户数目的增多,网络的负载也将增加。此时,各种应用的行为表现为无序地竞争网络资源,造成网络资源的不合理占用,各种应用各为其利,其结果是服务质量互相恶化;另外,“尽力而为”服务的传输质量没有很严格的保证,表现为端到端时延、数据报丢失率等性能随着网络负载的变化而波动,极不适合实时业务的传输。上一些主要应用的业务特征及其 QoS 需求[4]如表 1-1 所示。
显然,现有的尽力传送服务已无法满足各种应用对网络传输质量的不同要求,需要 提供多种服务质量类型的业务,而“尽力而为”的服务仍将提供给那些只需要连通性的应用。在此背景下,QoS 这一概念被提出,并且针对此概念,各种保障网络 QoS 的技术、算法也应运而生。
目前网络研究主要通过两个途径提高 QoS,一个是节点控制;另一个是整网或局部网络控制。节点控制在单节点或单链路完成,主要控制业务对单节点共享资源的占用,包括共享的链路、缓存区、处理器资源。节点控制主要的策略包括:业务流整形、业务调度、节点缓冲区管理。整网或局部网络控制通常通过对路由与信令的控制达到对业务流或业务连接在网络中传输的直接控制。很多支持 QoS 的研究侧重于调度、拥塞控制和资源预留, 而对 QoS 路由的研究相对较少。QoS 路由选择的任务就是从源端到目的端找到一条具有足够资源的路径来满足端到端服务质量,包括收集网络状态信息并不断更新信息,以及根据已有信息为新的连接请求选择一条合适的路由。一个路由算法的性能主要取决于信息收
集的好坏。一个优化的 QoS 路由选择策略是实现 QoS 保证的关键之一,也是目前关于
QoS 的一个重要的研究方向。本文主要研究方向为 QoS 路由选择策略的优化,解决的 QoS 路由选择问题是多约束受限单播路由问题,这里的多约束受限表现在带宽、时延、时延抖动等,由于该问题是 NP-C 问题,本文用遗传算法和蚁群算法来求解。
综上所述,研究 QoS 路由选择问题具有较高的理论意义和实际价值。
表 1-1 主要应用的业务特征
应用业务特征 QoS 需求
电子邮件/文件传输/远程终端
数据量小、批量文件的传输
容许时延;带宽需求低;尽力而为传送
HTML 网页浏览 一些序列小的、突发的
文件传输
容许适当的延时;带宽需求低;尽力而为传送
客户/服务器电子商务
基于 IP 协议的语音实时音频
许多小的双向传输 对时延、丢失率敏感;带宽需求适当;必须
可靠传送
连续或变化的传输 对时延、抖动非常敏感;带