java基于蚁群算法路由选择可视化动态模拟.zip

后端

1.25MB

18 需要积分: 1

立即下载

资源介绍:

这是“java 基于蚁群算法路由选择可视化动态模拟”，仅供学习参考，请勿商用。

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

资源文件列表:

java基于蚁群算法路由选择可视化动态模拟.zip 大约有14个文件

readme.pdf 52.77KB
论文+程序/A new class of QoS routing strategies based on network graph reduction.pdf 275.4KB
论文+程序/java程序/
论文+程序/java程序/ant.java 18.72KB
论文+程序/java程序/Antcolony.java 14.5KB
论文+程序/java程序/Configer.java 4.88KB
论文+程序/java程序/MapPad.java 13.35KB
论文+程序/java程序/Maps.java 184.04KB
论文+程序/java程序/Pheromone.java 1.74KB
论文+程序/java程序/SetInd.java 6.94KB
论文+程序/毕业设计任务书.doc 33.5KB
论文+程序/翻译.doc 8.03MB
论文+程序/开题报告.doc 38.5KB
论文+程序/论文.doc 1.46MB