【免费】java基于蚁群算法路由选择可视化动态模拟(论文+开题报告+翻译+任务书+外文翻译).rar资源-CSDN文库

共13个文件

java：7个

doc：4个

txt：1个

源码

java

毕业设计

需积分: 0 18 浏览量 2023-05-18 18:06:46 上传评论收藏 1.07MB RAR 举报

该压缩包文件主要围绕“Java基于蚁群算法的路由选择可视化动态模拟”这一主题，包含了进行毕业设计所需的一系列文档，如论文、开题报告、翻译等，这是一份全面研究如何利用蚁群算法解决网络路由选择问题的资料集。让我们详细探讨蚁群算法。蚁群算法（Ant Colony Optimization, ACO）是一种仿生优化算法，源于蚂蚁在寻找食物过程中发现路径的行为。在计算机科学中，它常用于解决组合优化问题，如旅行商问题和路由选择问题。在这个特定的Java项目中，蚁群算法被用来动态模拟网络中的数据包如何通过最优路径进行传输，以达到高效、低延迟的路由选择。蚁群算法的基本思想是，每只“虚拟蚂蚁”在图中随机探索路径，并在经过的路径上留下信息素。信息素的浓度表示路径的质量，随着时间的推移，高质量的路径会积累更多的信息素，从而吸引更多的蚂蚁选择这条路径，形成正反馈机制。通过迭代更新，算法最终能找到接近全局最优解的路径。在Java编程语言中实现这个算法，意味着需要设计和实现以下几个关键部分： 1. 图结构：构建网络的抽象模型，包括节点（路由器）和边（连接）。 2. 蚂蚁类：每个蚂蚁代表一个数据包，有自己的路径选择策略。 3. 信息素更新规则：定义信息素的挥发和加强机制。 4. 路径选择策略：蚂蚁根据当前路径上的信息素浓度和距离等因素选择下一步。 5. 可视化界面：为了动态模拟，需要创建一个用户界面，展示蚂蚁的移动和路径选择过程。开题报告通常会包含以下内容：选题背景、研究意义、相关工作综述、研究目标与内容、技术路线和预期成果。在这里，可能会详细介绍蚁群算法在网络路由选择中的应用背景，以及与传统路由算法的对比。论文部分将深入探讨蚁群算法的理论基础，详细描述算法的实现过程，分析其性能，可能包括实验设计、结果展示和性能评估。此外，还会讨论算法的优缺点以及可能的改进方向。翻译部分可能包括对相关外文文献的翻译，以便更好地理解蚁群算法的最新研究进展。任务书则明确了该项目的具体任务要求和完成标准。外文翻译可能是对原版蚁群算法相关论文的翻译，以供参考和学习，帮助理解算法的原始思想和实现细节。这个压缩包提供了一个全面的研究框架，涵盖了从理论到实践，从设计到实现，再到评估和优化的整个流程，对于学习和研究蚁群算法在网络路由选择中的应用具有很高的价值。

资源推荐

资源详情

资源评论

收起资源包目录

java基于蚁群算法路由选择可视化动态模拟(论文+开题报告+翻译+任务书+外文翻译).rar （13个子文件）

java基于蚁群算法路由选择可视化动态模拟(论文+开题报告+翻译+任务书+外文翻译)

论文+程序

论文.doc 1.46MB

开题报告.doc 39KB

A new class of QoS routing strategies based on network graph reduction.pdf 275KB

毕业设计任务书.doc 34KB

java程序

SetInd.java 7KB

MapPad.java 13KB

Configer.java 5KB

Maps.java 184KB

Pheromone.java 2KB

ant.java 19KB

Antcolony.java 14KB

翻译.doc 8.03MB

额外祝福.txt 156B

A new class of QoS routing strategies based on network

graph reduction

C. Casetti

, R. Lo Cigno

, M. Mellia

, M. Munaf



,Z.Zs



ooka

Dipartimento di Elettronica, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Torino, Italy

Department of Telecommunications, Budapest University of Technology and Economics, Magyar tud



oosok k

€

oor



uutja 2,

1117 Budapest, Hungary

Received 15 October 2002; received in revised form 16 October 2002; accepted 24 October 2002

Responsible Editor: I.F. Akyildiz

Abstract

This paper discusses a new approach to QoS routing, introducing the notion of algorithm resilience (i.e., its ca-

pability to adapt to network and load modiﬁcations) as performance index of the algorithm itself.

The new approach can be summarized as Network Graph Reduction, i.e., a modiﬁcation of the graph describing the

network before the routing path is computed, in order to exclude from the path selection over-congested portions of the

network. This solution leads to a class of two-step routing algorithms, where both steps are simple, hence allowing

eﬃcient implementation.

Simulation experiments, run on randomly-generated topologies and traﬃc patterns, show that these routing algo-

rithms perform consistently better than both the standard Minimum Hop algorithm and those QoS-based algorithms

based on the same metrics but not using the notion of Network Graph Reduction.

Keywords: QoS routing; Routing algorithms; MPLS

1. Introduction

Dynamic, QoS-based routing received consid-

erable attention in recent years [1–7], especially

considering the diﬃculty in predicting Internet

traﬃc patterns and the consequent impossibility to

properly plan and dimension the network.

The core of any QoS-based routing algorithm is

a network-status-dependent cost function that is

used to ﬁnd the optimal (or at least a suitable)

route across the network by solving an optimiza-

tion problem. In particular, given the best-eﬀort

nature of the current Internet where elastic data

ﬂows are in the majority, the most commonly used

metric aims at the maximization of either network

utilization or user throughput. Several proposals

introduced cost functions, algorithms and proto-

cols that give them advantages over traditional,

This work was supported in part by the Italian Ministry for

University and Scientiﬁc Research through the PLANET-IP

Project. A preliminary version of this paper was presented at

IEEE Infocom 2002 in New York.

Corresponding author.

E-mail address: munafo@polito.it (M. Munaf



oo).

PII: S 1 389-12 8 6 ( 0 2 ) 0 04 1 4 - 0

Computer Networks 41 (2003) 475–487

www.elsevier.com/locate/comnet

topology-based algorithms such as the Minimum

Hop (MH)

presently used in TCP/IP networks

[8,9]. For example in [1], the authors introduce the

bottleneck bandwidth as a metric and then deﬁne

the maximization of user throughput as optimi-

zation target. Similarly, in [2,3] the authors study

how to improve the throughput of high-bandwidth

traﬃc, such as large ﬁle transfers, in a network

where resources are fairly shared among connec-

tions. Their ﬁndings, obtained by simulation, show

that, at high loads, a MH routing algorithm

maximizes network and user performance; for

low-congested networks, instead, they propose an

algorithm, named Minimum Distance (MD)

routing, which oﬀers better performance. However

they are unable to provide an algorithm that

merges the two behaviors. Researchers focused

their attention upon other aspects of QoS routing,

namely protocol overhead [5,7], implementation

issues [4,6], impact of update policies [5].

A major drawback, however, aﬀects all QoS-

based routing algorithms. The cost function at the

core of the algorithms tries to ﬁnd portions of the

network where resources are under-utilized and

exploits them to the beneﬁt of connections that

would otherwise cross a congested portion of the

network. In doing so, as shown in [11] for the case

of simple alternate routing, the algorithm ends up

consuming more resources than MH routing does,

hence, in case of heavy congestion, QoS-based

routing wastes resources and performs poorly

compared with MH. A formal proof of this ob-

servation can be found in [10]. The extension of

this property to TCP/IP networks is not straight-

forward, since ﬂows often exhibit a greedy, elastic

behavior, using up the available bandwidth. MH

routing has been already conjectured to be as-

ymptotically optimal as the load q oﬀered to the

network tends to inﬁnity, and many simulation

results conﬁrm this intuition [2,3,13,16]. We stress

at this point that the poor performance of QoS-

based routing at high loads is not due to the sub-

optimality of the used algorithms, but is rooted in

the locality of the routing decision. Whenever a

call is routed, the given cost function is minimized/

maximized for the current state of the network,

necessarily disregarding the future network evo-

lution. Under heavy load, the overall network

beneﬁt does not coincide with the cost function of

a single call, hence the minimization of the one

does not lead to the maximization of the other.

In the light of the above discussion, the draw-

back of QoS routing in the Internet is clear:

whatever is gained at low or medium network

loads, it is paid for at high network loads. What is

needed to solve this problem is a resilient algo-

rithm that allows the migration of a QoS-based

routing algorithm to MH routing as q grows large.

The problem is that q is typically not known to the

routing algorithm, not even in the case of cen-

tralized routing algorithms.

The contribution of this paper lies in the iden-

tiﬁcation and deﬁnition of a class of routing algo-

rithms, named Network Graph Reduction (NGR),

whose performance encompasses that of QoS-

based routing algorithms at light and medium

loads, and the optimality of MH routing at high

loads. The goal is obtained by reducing the graph

that describes the network topology, and applying

a suitable metric to the reduced graph. Results are

reported showing both the elementary properties of

the algorithm, and its behavior in randomly gen-

erated topologies, both with uniform and non-

uniform, time-varying traﬃc.

The rest of the paper is organized as follows.

Section 2 provides a general description of the

NGR algorithm, along with implementation is-

sues. Section 3 presents the network and traﬃc

models used in the simulation presented in Section

4, in which the performance of the NGR algorithm

is compared to the one of classic QoS routing al-

gorithms, both in simple network scenarios, and in

more complex ones. Finally, conclusions and fu-

ture work are discussed in Section 5.

2. NGR routing algorithms

Routing can be formalized as the problem of

ﬁnding a suitable set of edges connecting two

nodes in a directed graph. QoS routing relies on

the deﬁnition of a suitable edge metric w, which

In this paper we refer to the MH algorithm as a special case

of the Shortest Path, in which all links have unitary costs.

476 C. Casetti et al. / Computer Networks 41 (2003) 475–487

depends on the networks status, and of a cost

function cðÞ, which should be minimized/maxi-

mized, yielding the optimal route selection under

speciﬁc network conditions. As discussed in the

Introduction, however, all metrics and cost func-

tions that try to maximize network utilization or/

and user throughput suﬀer from the same draw-

back: as the network load increases (q !1) their

performance drops below that of a simple MH

algorithm. Finding metrics that let the path selec-

tion process converge to MH routing as q in-

creases seems to be a hard problem. As shown in

[16] the elastic nature of the Internet traﬃc just

worsens the problem. The diﬃculty of ﬁnding a

suitable metric lies in the fact that the goal of such

a metric should change with the network load,

making the problem not easily tackled by a stan-

dard minimization approach.

Indeed, we can look at the routing problem

from a slightly modiﬁed perspective. Instead of

trying to ﬁnd adaptive metrics, the same metric

that works well for light loads can be applied at

high loads to a reduced graph that only contains

uncongested links, i.e., links whose load is under a

given threshold. Since the reduced graph may not

be connected, i.e., no path may exist from a source

to a destination, the minimum-hop path should

always be included as possible solution of the

routing problem. Thus, as the oﬀered load q

grows, all links become congested and the algo-

rithm necessarily chooses the minimum-hop path.

While the direct measure (or evaluation) of q is a

complex task, the identiﬁcation of single congested

links is extremely easy, so that, overall, the meth-

odology is simple and its implementation straight-

forward.

This key idea leads to the deﬁnition of the NGR

strategy which can be applied to any existing QoS

routing algorithms.

2.1. Formal description

For the purpose of providing a formal de-

scription of the class of NGR algorithms in their

most general form, we use a standard graph theory

formalism. Thus, we refer to a generic network as

a directed graph G ¼ðV; EÞ, where V is the set of

vertices (nodes, in our case), and E is the set of

edges (links).

A path pðv

; v

Þ of length

n ¼jjpðv

; v

Þjj is deﬁned as a sequence of n distinct

edges e

joining v

and v

, where v

; v

2 V, e

2 E,

pðv

; v

Þ¼fe

; e

; ...; e

A set P

is deﬁned as the set of all paths ex-

isting between any two distinct vertices of G, i.e.,

¼fpðv

; v

Þjv

; v

2 V; v

6¼ v

g. Each link is

assigned a weight w using any metric that com-

bines topological, physical or traﬃc-related char-

acteristics of that link. To each path p a cost cðpÞ is

assigned using a combination of the weights of its

links. Following this, an order relation  in the set

is established among paths, and we will refer to

a path p

as ‘‘lighter than’’ p

if p

 p

holds.

The NGR algorithm operates two subsequent

alterations upon the path set P

, and applies se-

lection criteria on the resulting subset:

• Step 1: the ﬁrst alteration transforms the di-

rected graph G into G

¼ðV; E

Þ, E

 E, select-

ing only those links whose weight satisﬁes a

Cut-oﬀ criterion C (e.g., if w represented the link

capacity, ‘‘slower’’ links could be discarded

from path selection if w < w

, where w

is the

smallest acceptable capacity); as a result, the

path set P

is reduced to P

after removing

those paths containing cut-oﬀ links;

• Step 2: let P

be the set including one mini-

mum-hop path from each source to each desti-

nation. In case more than one minimum-hop

path exist from the same source to the same des-

tination, one at random is selected.

The second

alteration transforms the path set P

into

¼ P

[ P

; the new subset is built from

(i) the paths belonging to P

and (ii) the mini-

mum-hop paths between any two nodes in V,

even if their links were discarded in the ﬁrst step.

Finally, the decision on how to route packets

between a source and a destination is made by ap-

plying the order relation  to the path subset of P

joining source and destination, and picking the path

In this paper we interchangeably use the terms ÔedgesÕ and

ÔlinksÕ and the terms ÔverticesÕ and ÔnodesÕ.

It is possible to optimize the P

set, for example using

load-balancing criteria.

C. Casetti et al. / Computer Networks 41 (2003) 475–487 477

that turns out to be the lightest according to the cost

metric deﬁned by the QoS routing algorithm.

2.2. NGR-MD and NGR-WS algorithms

In a broad sense the NGR methodology can be

coupled with any metric and cost function. In or-

der to exemplify this property, we considered the

application of this methodology to two algorithms

already proposed in the literature, which were

shown to oﬀer good performance [1,2]:

Widest-shortest (WS): for each source–destina-

tion pair, the algorithm determines all the paths

with the minimum-hop count; if more than one

such path exist, it breaks the tie by choosing the

one with the largest available bandwidth [1];

Minimum distance (MD): for each source–des-

tination pair, the path is chosen which mini-

mizes the sum on each link of the inverse of

the equal bandwidth share [2].

To help the reader, we report a simple de-

scription of the above algorithms, using the nota-

tion introduced in this paper.

• WS path weight computation: a weight w

associ-

ated to a generic link l is computed as

¼ b

; ð1Þ

where b

is an estimate of the currently avail-

able bandwidth on link l;

The set of paths among which the path P

chosen is restricted to the minimum-hop paths, i.e.,

¼ffp

ðv

; v

Þj jjp

ðv

; v

Þjj 6 jjp

ðv

; v

Þjj 8j g

; v

g: ð2Þ

Then, the cost cðp

Þ of path p

is deﬁned as follows:

cðp

Þ¼min

l2p

g; ð3Þ

and the ordering relation is such that p

 p

cðp

Þ > cðp

Þ (i.e., p

is lighter than p

if its avail-

able bandwidth is larger than p

Õs).

• MD path weight computation: a weight w

asso-

ciated to a generic link l is computed as

þ 1

; ð4Þ

where C

is the link capacity and n

is an esti-

mate of the number of active ﬂows currently

routed over link l.

The cost cðp

Þ of path p

is then deﬁned as fol-

lows:

cðp

Þ¼

l2p

; ð5Þ

and the ordering relation is such that p

 p

cðp

Þ < cðp

Þ.

To implement the NGR algorithms, we deﬁne

the following:

Cut-oﬀ criterion C : a link is discarded if its utili-

zation is found to be above a given threshold W

, i.e.,

> W

: ð6Þ

Combining NGR and C with either the MD or

WS QoS algorithms we obtain the NGR-MD and

NGR-WS algorithms.

In the rest of the paper, we assume W

¼ 1, i.e.,

if a link shows a 100% utilization, it is discarded by

the Cut-oﬀ criterion.

2.3. Implementation issues

After deﬁning the algorithms, we are interested

in the viability of a consistent hop-by-hop imple-

mentation, in which routing decisions taken at an

upstream node are not liable to be superseded by

downstream nodes ﬁnding a locally-optimal al-

ternative to the path chosen earlier by upstream

nodes. As formally proved in [12], the WS algo-

rithm does not belong to the class of algorithms

that allow a consistent hop-by-hop implementa-

tion, while the MD algorithm can be implemented

in a hop-by-hop fashion while preserving consis-

tency. If we combine the NGR methodology

described above with those algorithms, is the hop-

by-hop implementation property preserved? Un-

fortunately, the answer is negative. The proof in

case of the NGR-MD metric is by counter-exam-

ple, while NGR-WS cannot be considered since

the WS criterion itself is not implementable hop-

by-hop. Consider the simple directed graph in Fig.

1, consisting of ﬁve links, a, b, c, d, z, each labeled

with its own weight, i.e., w

¼ 10, w

¼ 5, w

¼ 2,

¼ 2 and w

¼ 2. Let us consider the problem of

478 C. Casetti et al. / Computer Networks 41 (2003) 475–487

评论收藏

内容反馈

m明月Java3

粉丝: 2w+
资源: 153

java基于蚁群算法路由选择可视化动态模拟(论文+开题报告+翻译+任务书+外文翻译).rar

最新资源