DiffServ快捷服务路由算法的探讨与模拟实现

VIP免费

3.0 牛悦 2024-11-19 4 4 670.48KB 77 页 15积分

摘要

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

第一章引言

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 上提供有效的、可伸缩

的网络流量的服务区分。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

目录摘要ABSTRACT第一章引言.................................................................................................................1§1.1QoS的发展.......................................................................................................2§1.1.1BestEffort..........................................

展开>> 收起<<

DiffServ快捷服务路由算法的探讨与模拟实现.pdf

共77页,预览8页

还剩页未读，继续阅读

DiffServ快捷服务路由算法的探讨与模拟实现

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: