DiffServ快捷服务路由算法的探讨与模拟实现
VIP免费
目 录
摘 要
ABSTRACT
第一章 引言................................................................................................................. 1
§1.1 QoS 的发展 ....................................................................................................... 2
§1.1.1 Best Effort................................................ 2
§1.1.2 IntServ/RSVP ............................................. 3
§1.1.3 IP over ATM .............................................. 4
§1.1.4 三种 QoS 模式比较 ........................................ 4
§1.1.5 MPLS 多协议标签交换..................................... 5
§1.2 DiffServ 模式 .................................................................................................... 6
§1.2.1 区分服务的基本思想和组件 ................................ 6
§1.2.2 区分服务的主要优点 ...................................... 8
§1.2.3 本文结构 ................................................ 9
第二章 问题描述........................................................................................................11
§2.1 基于 EF PHB 的Premium Service 快捷服务 .................................................11
§2.1.1 背景 ................................................... 11
§2.1.2 区分服务中的逐跳行为 ................................... 11
§2.1.3 区分服务的基本服务类型 ................................. 12
§2.1.4 Premium Service 快捷服务 ................................. 13
§2.2 快捷服务流量在 DiffServ 中的影响 ............................................................. 14
§2.3 DiffServ 系统下逐跳的最优路由 .................................................................. 16
§2.3.1 逐跳的最短路由 Shortest-Path Routing ....................... 16
§2.3.2 Premium 流量的路由问题和带宽预留 ....................... 17
§2.3.3 快捷服务的最优路由问题 ................................. 19
§2.3.4 经典 Dijkstra 算法的主要思想 .............................. 20
§2.4 网络模型 ......................................................................................................... 22
§2.4.1 相关概念的设定 ......................................... 23
§2.4.2 最优的快捷服务路由问题描述 ............................. 24
§2.4.3 相关的网络理论基础 ..................................... 24
§2.4.4 最优快捷服务路由问题是 NP-难度的 ........................ 28
第三章 逐跳路由算法与分析................................................................................... 30
§3.1 Widest-Shortest-Path Algorithm (WSP)算法.................................................. 30
§3.1.1 预留带宽的引入 ......................................... 30
§3.1.2 WSP 算法............................................................................................... 30
§3.2 Bandwidth-inversion Shortest-Path Algorithm (BSP)算法............................. 32
§3.2.1 权重函数和预留带宽的结合 ............................... 32
§3.2.2 BSP 算法 ............................................... 32
§3.2.3 BSP 算法的不足 ......................................... 33
§3.3 基于逐跳的快捷服务路由问题的解决算法 ................................................. 34
§3.3.1 对BSP 算法中权重函数的改进 ............................. 35
§3.3.2 新的常量因子的提出 ..................................... 36
§3.3.3 EBSP 算法以及分析 ...................................... 38
§3.3.4 MEBSP 算法的分析及进一步改进的方向 .................... 39
第四章 网络模拟平台及模拟模型建立 .................................................................. 42
§4.1 网络模拟概述 ................................................................................................. 42
§4.1.1 网络模拟复杂性和难点 ................................... 43
§4.1.2 网络模拟器简介以及特点 ................................. 43
§4.2 OPNET 网络模拟平台 ................................................................................... 44
§4.2.1 OPNET 网络模拟软件介绍................................. 44
§4.2.2 OPNET Modeler 网络模拟环境架设 ......................... 45
§4.3 网络模拟模型的建立 ..................................................................................... 46
§4.3.1 算法的程序实现 ......................................... 46
§4.3.2 建立模型 ............................................... 48
第五章 网络模拟结果和分析................................................................................... 51
§5.1 模拟一 ............................................................................................................. 51
§5.2 模拟二 ............................................................................................................. 54
§5.3 模拟三 ............................................................................................................. 58
第六章 相关的研究工作........................................................................................... 64
第七章 结束语........................................................................................................... 66
§7.1 结论 ................................................................................................................. 66
§7.2 后续研究工作 ................................................................................................. 67
参考文献 ....................................................................................................................... 69
在读期间公开发表的论文和承担科研项目及取得成果............................................ 73
一、 发表的论文 ..................................................................................................... 73
二、 科研项目 ......................................................................................................... 73
致 谢 ....................................................................................................................... 74
摘 要
区分服务（DiffServ）是 IETF 目前比较看好的 IP QoS 标准之一。在区分服务
模型中，快捷服务流具有最高的优先级别。在区分服务网络中，关于快捷服务的
路由解决方案不但对快捷服务流本身的传输性能有重要影响，对其它服务类型流
也具有较大的影响。因此，对于快捷服务的路由解决方案的研究具有相当重要的
意义。目前，基于 QoS 的路由算法研究已经逐渐成为最近几年网络研究的一个热
点方向，特别是最近两年，涌现了一些关于各种在不同网络环境和条件下的 QoS
路由算法，而且已经开始尝试在实际应用中付诸实现。本文的主要目的是对区分
服务网络模型中的最优网络路由方案进行比较、分析、研究和探讨，并提出新的
评价和设想，为今后进一步的工作奠定良好的基础；同时对当今的网络模拟方法
进行一定的研究，对所探讨的路由算法解决方案以及所提出的相关判断通过网络
模拟进行了实现和验证。
在当今互联网中，普遍采用的是基于最短跳数的路由解决方法，其相关的路
由算法在具有网络服务质量要求的区分服务网络中已经无法满足需要。本文对区
分服务网络环境下寻找快捷服务的最优路由方案的相关问题进行了系统的研究，
对所涉及的相关理论知识进行了较详细的探讨，例如：区分服务模式、区分服务
模式下快捷服务流的特点、逐跳最短路径路由、快捷服务流的带宽预留、在基于
逐跳的网络环境中路由的无回路、对瓶颈连接的冗余带宽的最大化等等。
为了更好地说明问题，本文对所要讨论的网络模型进行了阐述，并对文中所
用到的相关术语、定义和定理进行了描述；同时以经典的 Dijkstra 最短路径算法
为基础，对当前颇有影响的几个路由算法进行了研究和探讨，如 WSP、BSP、EBSP
等等，对它们的特点和优劣性进行了阐述和比较，其中，着重对 EBSP 算法进行
了研究，对该算法中的参数的设置提出了新的判断、设想，同时对算法进行了一
定的修正，并将修正算法命名为 MEBSP，MEBSP 算法可为今后对算法的进一步
改进、完善指出了可行的方法。最后对当前的网络模拟仿真方法进行了一定的总
结和阐述，在此基础上，构建了自己的网络模拟平台，设计了若干个网络模拟模
型，对文中所叙述的几种算法分别进行了模拟仿真实现，对网络模拟结果进行了
分析，并通过调整算法中的相关参数，初步验证了本文所提出的判断和设想。
关键词：服务质量保证, 区分服务, 快捷服务, Dijkstra, 路由算法
ABSTRACT
Internet traffic and the volume of Internet multimedia applications are increasing,
hence forcing us to investigate new concepts and paradigms in the high-performance
Quality of Service(QoS) routing. In order to provision better end-to-end QoS, DiffServ
scheme has been proposed as a cost-effective solution. The Differentiated Services
approach to providing quality of service in networks employs a small, well-defined set
of building blocks from which a variety of aggregate behaviors may be built. A small
bitpattern in each packet, in the IPv4 ToS octet or the IPv6 Traffic Class octet, is used
to mark a packet to receive a particular forwarding treatment, or per-hop behavior, at
each network node.
In DiffServ networks, traffic is classified into three service classes:
premium,assured and best-effort. The premium class traffic has the highest priority in
comparison to other classes of traffic. The routing algorithms used by the premium
class traffic, due to the high priority afforded to that traffic, may have a significant
impact not only on the premium class traffic itself, but on all other classes of traffic as
well. The shortest hop-count routing scheme, used in current Internet, turns out to be
no longer sufficient in DiffServ networks. By combining service differentiation and
QoS routing together, the high-priority premium traffic should be transmitted in an
efficient manner with low negative influences to other low-priority traffic.
This paper studies the problem of finding optimal routes for the premium-class
traffic in a DiffServ domain, such that : no forwarding loop exists in the entire network
in the context of hop-by-hop routing; and the residual bandwidth on bottleneck links is
maximized. This problem is called the optimal premium-class routing problem. This
problem is NP-hard factly.
Then, the paper formally define a network model , and Based on this model, give a
more formal description of some assumptions in the problem. Some fundamental
definitions and theorems are presented by the network model. which will be used later
to prove the correctness of route algorithms.
To handle the optimal premium-class routing problem, this paper firstly analyze
the strength and weaknesses of three existing algorithms (Widest-Shortest-Path
algorithm , Bandwidth-inversion Shortest-Path algorithm and the Enhanced
Bandwidth-inversion Shortest-Path algorithm). Second, based on the Enhanced
Bandwidth-inversion Shortest-Path algorithm, we propose a novel heuristic
algorithm.We will name it as Modified Enhanced Bandwidth-inversion Shortest-Path
algorithm,by replacing 2 in EBSP with the factor θ in MEBSP.This paper will prove
theoretically the correctness of the new algorithm, i.e., I will show that it is consistent
and loop-free. The paper will point the the future work about MEBSP algorithm,too.
The extensive simulations in different network environments show clearly that the
new algorithm performs better when routing the premium traffic in complex,
heterogeneous networks.In this paper , I will show my three simulation model,whose
results will validate my view very well.
Keywords: QoS, DiffServ, Premium Service, Dijkstra, routing algorithm
1
第一章 引言
IP 网络从一开始就被设计成一个通用的，可以共享的通信基础模式，随着
Internet 的兴起和发展，网络已经逐渐成为我们生活、学习、工作的一个不可缺少
的重要工具和组成部分。当前，Internet 正在向一个多业务数据网络演进，互联网
上的的网络服务和网络应用程序正在以惊人的速度成倍增长，如何增强网络的流
量控制和服务质量 QoS（Quality of Services），正成为当前网络新技术研究前沿的
一个热门话题。而其中的关键技术之一就是 QoS(Quality of Service)。
传统的 IP 网络只提供"尽力而为"的数据传输能力。随着网络上主机数量的不
断增加，网络服务的需求将超过网络提供的能力，从而造成传输时延变化（抖动）、
传输时延过大甚至引起分组丢失，也就是说出现了网络拥塞。网络拥塞对一些
Internet 应用（如电子邮件，文件传输和 Web 应用）一般不会造成太大影响，但
对传输时延要求比较苛刻的实时应用（如多媒体业务）及大多数双向通信业务（如
电话业务）却是不能容忍的。
当然，我们可以通过增加网络带宽来缓解网络拥塞，但这样做并不能消除拥
塞。当两条容量极高的光缆汇聚到第三条光缆上时，仍会造成拥塞。此外由于交
换机和路由器的接口速率与网络的带宽相比仍很低，当数据到达接口的速率超过
接口转发的速率时，拥塞也会发生。并且需要大带宽的新业务不断涌现，当这些
业务量猛增的时候，拥塞将是难以避免的。甚至在一个负载相对较轻的 IP 网络上，
传输迟延也能累积到影响实时应用的程度。为了在 Internet 上提供有质量保证的
服务，必须制订有关服务数量和服务质量水平的规定。规定中需要在网络方面增
加一些协议，对具有严格时延要求的业务和能够容忍迟延、抖动和分组丢失的业
务进行分类，同时采用多种分组调度机制和算法对这些业务进行处理，这就是 QoS
机制的职责。也就是说，QoS 机制不是用来增加网络带宽，而是通过最优化的使
用和管理网络资源使其尽可能满足多种业务的需求。
通过 QoS，运营商或用户能够对网络上传输的视音频流等对实时性要求较高
的数据提供优先服务，从而保证较低的延迟。当前，IETF 建议了多种协议来实现
QoS 支持，包括集成服务、资源预留协议(RSVP)、区分服务(DiffServ)、多协议
标签交换(MPLS)以及业务流量工程(Traffic Engineering)等。今天，特别是在近几
年，有关 DiffServ 的理论和实践研究发展很快。DiffServ（Differentiated Services）
体系结构，是 IETF 组织提出的一种网络流量控制管理模式，作为 Internet 骨干网
络上的一种廉价的可靠的 QoS 解决方案，它能在 Internet 上提供有效的、可伸缩
的网络流量的服务区分。
DiffServ 快捷服务路由算法的探讨与模拟实现
2
§1.1 QoS 的发展
为了更好地理解本文所探讨的内容，在这里有必要首先介绍和回顾一下 QoS
的发展。自从 1972 年世界上第一封电子邮件成功发送以来，各种各样种类繁多的
服务都迁移到了 IP 网络上，这不但导致网络流量的飞速膨胀，更重要的是，这么
多的网络应用需要更多的网络服务来支持。
随着基于互联网的各种增值业务如雨后春笋般纷纷涌现，IP 网正逐步向多业
务承载网络发展。市场细分带来了对中高端用户实现差异化服务的要求，使得以
互联网接入服务为主收入的经营格局，向以增值应用、内容管理、个性化服务的
经营方向过渡。在此情况下，如何在 IP 网络上保证用户信息传输的质量就成为一
个不容忽视的重要问题。种种迹象表明，QoS（服务质量）已经成为网络基础研
究的一个重点、未来 IP 网络发展的关键技术，未来运营商的竞争也将集中在 QoS。
在IETF 的RFC 文档[6]中有对一个理想的 QoS 必须要提供的功能的简单描述
“the activity to give guarantee that every flow is protected from all external effects in
a way that the quality always satisfies the predefined requirements”。
§1.1.1 Best Effort
在区分服务出现以前，传统的 Internet 上的基本 QoS 模式是尽力而为服务 BE
（Best Effort），在这种模式下，网络将尽其所能，努力地传送尽可能多的数据包
以便满足网络通讯的需要，所有的业务流被"一视同仁"地公平地竞争网络资源，
路由器对所有的 IP 包都采用先来先处理（First Come First Service FCFS）的工作
方式，它尽最大努力将 IP 包送达目的地。但对 IP 包传递的可靠性、延迟等不能
提供任何保证，也就是说，不保证这些网络数据传输都能成功。这很适合 Email、
Ftp、WWW 等业务，但这同时也意味着通讯很容易造成数据的无序传输和数据丢
失，并有可能导致数据传输的不可预期的延迟。
随着互联网的高速增长，IP 业务也得到了快速增长和多样化。特别是随着多
媒体业务的兴起，计算机已经不是单纯的处理数据的工具，而是越来越贴近生活，
计算机的交互越来越实时和生动，这对计算机互联网络也就相应地提出了更高的
要求。对那些有带宽、延迟、延迟抖动等特殊要求的应用来说，现有的“尽力而
为”的服务显然是不够的。尽管由于网络技术的发展，网络带宽以及网络速度都
得到了极大的提高，但需要通过网络传输的数据却也几乎以与网络发展速度相同
的速度增加，甚至超过网络发展的速度，这使得网络带宽与网络速度依然是一个
瓶颈问题。同时，近年来发展起来的一些新的应用（如多媒体应用，组播应用等）
不仅增加了网络流量，更因为这些应用改变了以往互联网上的流量性质，因而它
们需要全新的服务要求。由于不具备服务质量保障特性，不能预留带宽，不能限
第一章 引言
3
定网络时延，因此，目前的因特网无法支持许多新的应用，如远程教学、远程手
术、远程会议和学术交流等，特别是在实时网络环境下，尽力而为的这些弊病无
法满足 Internet 飞速发展的需求，这在客观上要求有新的 QoS 模型来替代 BE。
§1.1.2 IntServ/RSVP
随着网络技术的进一步发展，网络界先后提出了集成服务（IntServ）和 IP for
ATM 。IntServ WG 成立于 1993 年末，该工作组的主要任务是定义一套最小的通
用标准以把 Internet 转变成一个性能优越的集成服务的网络通讯系统，其主要思
想是通过在网络路径上保留资源，以实现端到端的 QoS 控制，因此信号传输的状
态信息必须要保留到每一跳的节点上，这其中，信号传输所用的资源保留协议被
称为 RSVP，[1]中有 RSVP 的相关叙述,所以这种模式也被称为 IntServ/RSVP 模
式。
Int-Serv/RSVP 服务模型在 IETF RFC1633 中进行了定义。RFC1633 将资源
预留协议 RSVP 作为 IntServ 结构中的主要信令协议。其基本思想就在于以资源预
留的方式来实现 QoS 保障，RSVP 是其核心部分。RSVP 是主机用来从应用程序
获得特定的 QoS 的一种控制协议，完成综合服务需要定义的呼叫接纳控制功能和
资源预留功能。端点应用程序利用 RSVP 消息向网络提出完成数据传送必须保留
的网络资源（如带宽及缓冲区大小等），同时也确定沿传送路径的各个节点传输处
理策略，从而对每个业务流实现逐个控制。
在服务层次上，IntServ/RSVP 提供了 3 种级别的业务：
1) 端到端的质量保证型服务（Guaranteed Service）：保证带宽、限制延迟、
无丢包。
2) 可控负载型服务（Controlled－Load Service）：类似于在当前的一个负载
较轻网络中实现的尽力而为业务的服务质量。
3) 尽力而为的服务（Best Effort Service）：类似当前 Internet 在提供的尽力而
为的服务。
在结构层次上，IntServ/RSVP 服务模型主要由四个部分构成：信令协议 RSVP，
接入控制器（admission control routines），分类器（classifier）以及包调度器（packet
scheduler）。
在实现层次上，综合服务需要所有路由器在控制路径上处理每个流的信令消
息，并维护每个流的路径状态和资源预留状态，在数据路径上执行流的分类、调
度和缓冲区管理。具体而言，资源预留协议 RSVP 负责逐跳（hop-by-hop）地建
立或者拆除每个流的资源预留软状态（soft state），也即建立或拆除数据传输路径；
接入控制器将决定是否接受一个资源预留请求，其根据是链路和网络节点的资源
使用情况以及 QoS 请求的具体要求；分类器则对传输的数据包进行分类成传输
流， IntServ 常用的分类器是多域（Multi-Field，MF）分类器，当路由器接收到
摘要：
展开>>
收起<<
目录摘要ABSTRACT第一章引言.................................................................................................................1§1.1QoS的发展.......................................................................................................2§1.1.1BestEffort..........................................
相关推荐
-
跨境电商商业计划书模版VIP免费
2025-01-09 27 -
跨境电商方案范文VIP免费
2025-01-09 14 -
创业计划书VIP免费
2025-01-09 18 -
xx生鲜APP计划书VIP免费
2025-01-09 12 -
跨境电商创业园商业计划书(盈利模式)VIP免费
2025-01-09 8 -
跨境电商计划书VIP免费
2025-01-09 13 -
绿色食品电商平台项目计划书VIP免费
2025-01-09 22 -
农产品电子商务商业计划书VIP免费
2025-01-09 9 -
农村电商平台商业计划书VIP免费
2025-01-09 13 -
生鲜商城平台商业计划书VIP免费
2025-01-09 21
作者：牛悦
分类：高等教育资料
价格：15积分
属性：77 页
大小：670.48KB
格式：PDF
时间：2024-11-19
