AscalablemethodforDCLCproblemusinghierarchicalMDPmodel资源-CSDN文库

Scalability

38 浏览量 2021-02-21 07:03:22 上传评论收藏 1.15MB PDF 举报

资源推荐

资源详情

资源评论

A scalable method for DCLC problem using hierarchical MDP model

Yue Han

⇑

, Mingwu Yao, Zengji Liu

ISN State Key Lab. of Xidian University, Xi’an 710071, China

article info

Article history:

Received 21 November 2012

Received in revised form 1 May 2013

Accepted 7 May 2013

Available online 18 May 2013

Keywords:

DCLC

MDP

Scalability

abstract

It is well known that the delay-constrained least-cost (DCLC) routing problem is NP-comp lete, hence var-

ious heuristic methods have been proposed for this problem. However, these heuristic methods have

poor scalability as the network scale increases. In this paper we propose a new method based on the

Markov Decision Process (MDP) theory and the hierarchical routing scheme to address the scalability

issue of the DCLC routing problem. We construct a new two-level hierarchy MDP model and apply an inﬁ-

nite-horizon discounted cost model to the upper level for the end-to-end inter-domain link selection.

Since the inﬁnite-horizon discounted cost model is independent of network scale, the scalability problem

is resolved. With the proposed model, we further give the algorithm of solving the optimal policy to

obtain the DCLC routing. Simulation results show that the proposed method improves the scalability

signiﬁcantly.

1. Introduction

The continuous growth in network applications with various

QoS requirements is calling for better transmission qualities than

the best effort service. These emerging applications (video, audio,

interactive multimedia, teleconferencing, etc.) have stringent QoS

requirements and pose a particular difﬁculty for the QoS routing.

For example, the delay-sensitive applications such as real-time

voice and video require the data stream to be received at the des-

tination within a certain time. Generally, the QoS requirements are

represented by constraints imposed upon the corresponding per-

formance metrics such as delay, jitter, cost, etc. The end-to-end

delay constraint is the most prominent factor of these constraints

for QoS support. In addition, the trafﬁcs generally utilize a signiﬁ-

cant amount of resources usually measured by the cost metric.

Hence the need for QoS routing is the ability to satisfy the QoS

requirements of the trafﬁcs and to better optimize resource utiliza-

tion. In this paper, we focus on the most typical delay-sensitive

routing problem which has been extensively studied in the past

decade, the delay-constrained least cost (DCLC) routing prob-

lem[1], i.e., to ﬁnd a path that has the minimal cost subject to a de-

lay constraint.

The DCLC routing plays a very important role in the ﬁeld of QoS

routing. Much work has been done to solve the DCLC problem.

However, the existing DCLC routing algorithms still have one or

more distinct drawbacks, such as high computational complexity,

high communication complexity and low success ratio to obtain

the optimal path, that seriously hinder the application of DCLC

routing to the practical network environment. Moreover, DCLC

routing has to consider not only the application to a speciﬁed net-

work size, but also the application to a larger network scale for the

scalability requirement. Therefore, we see the DCLC problem from

a completely different angle to ﬁnd a suitable solution that can

achieve 100% success ratio to obtain the optimal path with low

computational complexity, low communication complexity and

better scalability.

With the continuing growth of the network size, the existing

heuristic algorithms for DCLC routing will not work well, leading

to what is called the scalability problem. So far, the scalability

problem of DCLC routing has seldom been addressed. Therefore

our focus is to propose a feasible solution for resolving the scalabil-

ity problem of DCLC routing. We notice that the frequent advertise-

ment of routing information is the critical factor for the scalability

problem of DCLC routing. So our purpose is centered on the

decrease of the advertisement. Under the steady network and link

independence assumptions, MDP theory is appropriately employed

to compute an optimal path for the DCLC problem by means of link

by link way, which is not necessary to frequent advertise the rout-

ing information. To achieve this purpose, we rebuild a two-level

MDP model for DCLC routing, which is an effective structure of

offering better scalability. For the lower level, we adopt the ﬁnite

horizon cost MDP to determine the links of a path within a domain.

For the upper level, we adopt the inﬁnite-horizon discounted cost

MDP to determine the inter-domain links. Thus, the end-to-end

DCLC routing is determined regardless of the network size and

then the scalability problem is resolved.

http://dx.doi.org/10.1016/j.comcom.2013.05.003

Project supported by the National Natural Science Foundation of China (Nos.

61001129, 61179002), the State Key Laboratory Foundation (No.

9140c5302010802).

⇑

Corresponding author. Tel.: +86 029 88201008.

E-mail address: yueh2000_8@163.com (Y. Han).

Computer Communications 36 (2013) 1310–1316

Contents lists available at SciVerse ScienceDirect

Computer Communications

journal homepage: www.elsevier.com/locate/comcom

This paper is organized as follows. We start with the related

works about the solutions for the DCLC problem in Section 2 and

present a detailed description of our proposed hierarchical MDP

model for DCLC routing in Section 3. In Section 4, we give the

method of solving the optimal policy for the proposed MDP model.

We then analyze the performance via simulations in Section 5.We

conclude this paper in Section 6.

2. Related works

In this section we give a brief review of the different routing

algorithms for the DCLC problem proposed in previous literatures.

The DCLC routing has been formulated in [1]. It is a cost optimiza-

tion problem subjected to the delay constraint. Due to the

NP-complete property, the DCLC routing cannot be solved in poly-

nomial time. Heuristic algorithms have been proposed to tackle

this problem. The earliest work is accredited to Hassin’s two

opti-

mal approximation algorithms with the costs less than 1 þ

times

the optimal solution[1]. Although these algorithms are efﬁcient in

ﬁnding feasible paths, they have high computational complexity.

Widyono proposed a Constrained Bellman-Ford (CBF) algorithm

[2] that solves the DCLC problem by a breadth-ﬁrst search method,

but the worst-case computational complexity grows exponentially

with the network size. In [3], two algorithms based on the short-

est-path method are proposed. These heuristic algorithms of which

one is centralized and the other is distributed are both polynomial.

Cheng proposed an iterative k-shortest path algorithm that can

achieve 100% success ratio in ﬁnding the optimal path with very

low computational complexity[4]. However, the performance of

the algorithms in [3,4] highly depends on the k parameters and

they only obtain near optimum paths for larger k values with high

computational complexity. Gang proposed an enhancing

approx-

imation algorithm with the optimal linear scaling factor[5], but it is

still impractical for real-time network application in a large scale

network.

To solve the DCLC problem in polynomial time, the combined

path heuristic algorithms have attracted much attention by con-

necting shortest-path sections to ﬁnd the optimal path. A type of

combined path heuristic algorithm, called Delay Constrained Uni-

cast Routing (DCUR) algorithm [6] has been introduced to alleviate

the computational complexity which is always within 10% from

the optimal CBF, but it has Oðn

Þ communication complexity. Sim-

ilar to DCUR, Liu and Xiao proposed two heuristic algorithms in

[7,8]. However, Kim presents an example of the incorrectness of

DCUR in [9]. It is shown that the path selected by DCUR is not

the optimal path because the cost of the optimal path is smaller

than the cost of the path selected by DCUR.

Another type of combined path heuristic algorithms are

Lagrange Relaxation based Aggregate Cost (LARAC) algorithms pro-

posed in [10,11]. The method in [10] linearly combines cost and

delay while the method in [11] suggests nonlinear combinations.

As a further development of [11], Feng proposed a heuristic algo-

rithm [12] in which a nonlinear function of delay and cost plays

a critical role. Although these algorithms have low computational

complexity and low communication complexity, they fail to ﬁnd

the optimal solution with reasonable possibility and have a much

higher cost in certain cases. In recent years, some new progresses

have been made on the basis of DCUR and LARAC in [13–15]. These

methods provide some improvements to the original DCUR and

LARAC, but they still have poor scalability. In fact, the scalability

problem is a long-standing problem for DCLC routing, that is,

although the existing DCLC routing algorithms work well at speci-

ﬁed network sizes, they will fall into trouble as the network size

grows. The study of DCLC routing algorithms for improving the sca-

lability is still an open issue.

This paper provides an alternative method for DCLC routing in

which the scalability problem is mainly involved. The proposed

method is able to work well regardless of the network size. In addi-

tion, compared with the previous DCLC routing methods, the com-

putational complexity, the communication complexity and the

total cost during the path selection are also considered in the pro-

posed method. Furthermore, the proposed method is always capa-

ble of ﬁnding the optimal routing as long as it exists. Therefore our

proposed method is able to work well in the practical network

environment and especially suitable for DCLC routing to achieve

better scalability with the fast network expansion.

3. The proposed hierarchical MDP model for DCLC routing

Generally, the scalability problem in current DCLC routing algo-

rithms may derive from two aspects. First, the amount of informa-

tion used to describe the network state may increase dramatically

with the increasing expansion of network scale. Second, the deter-

ministic network information is used to compute a feasible path. It

is these two factors that make the transmission and storage of net-

work state information more difﬁcult. So it becomes impossible to

maintain up-to-date network state information as the network

scale increases. Then the path selection is seriously affected by

the out-of-date information or information loss and hence may

be inaccurate and unreliable. It is desirable to deal with the scala-

bility problem from these two aspects. The hierarchical routing

[16] and the probabilistic routing [17] are two effective ways to

improve the scalability of routing selection from the above two

related directions, respectively. So far, however, they have never

been used in DCLC routing.

In this paper, we propose a new method which combines the

hierarchical routing with the probabilistic routing to address the

scalability issue of DCLC routing. The new method introduce the

MDP theory [18] for the DCLC problem and a two-level MDP

model is rebuilded for the new hierarchical DCLC routing. MDP

was originally employed to compute a state dependent routing

in connection-oriented networks (e.g., circuit-switched network

and ATM network). Since the real-time state information of the

entire network was required, the state dependent routing was

computationally infeasible. So it was generalized to use the

link-dependent analysis to specify an optimal routing policy.

However, due to the huge number of the link states for the

incoming calls, the computational complexity is tremendous. To

obtain a feasible computational complexity, the link indepen-

dence assumption is applied by decomposing the routing into a

set of links. This assumption implies that a packet arrival carried

on an n-link path is decomposed into n independent packet arriv-

als at each single link.

So far, MDP have never been used in a connectionless-oriented

network (e.g., IP network) for the routing purpose. Since the

hop-by-hop routing is considered in IP network, the link selection

decisions are made locally at each node based only on the incom-

ing packet. Consequently, on the assumption that the network is

steady, the link independence assumption is reasonable and feasi-

ble in IP network. Under the link independence assumption, the

link state is only dependent on the adjacent links and the adver-

tisement amount of the link state information is decreasd. In view

of the above-mentioned analysis and the fact that the network

environment of the DCLC routing is IP network, the assumption

that the link state is independent Markov chains is satisﬁed and

the introduction of the MDP theory is with justiﬁcation. To meet

scalability requirement, we improve the traditional MDP-based

routing by adapting it to a hierarchical form from the original ﬂat

form. Next we describe the MDP theory ﬁrst and then propose our

MDP-based hierarchical DCLC routing algorithm.

Y. Han et al. / Computer Communications 36 (2013) 1310–1316

1311

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38538312

粉丝: 11
资源: 927

A scalable method for DCLC problem using hierarchical MDP model

FastSlam:A Scalable Method

Conv-DBN for Scalable Unsupervised Learning of Hierarchical Representations

A Scalable Arch for Effic QoS to cater IMS Serv for Handheld on android

Scalable Algorithms for Big Data and Network Analysis

21-KDD-Scalable Hierarchical Agglomerative Clustering

3D Pose Estimation and 3D Model Retrieval for Objects in the Wild

chord-a scalable peer-to-peer lookup service for internet applications

Writing scalable server applications using IOCP

Docker for Data Science: Building Scalable and Extensible Data Infrastructure

A scalable web crawler framework for Java..zip

A robust and scalable chat application built using Next JS, Sock

陈天奇xgb论文《XGBoost: A Scalable Tree Boosting System》

2017 SecureML：A system for scalable privacy-preserving machine learning.pptx

Scalable Infrastructure for Distributed Sensor Networks

Building Serverless Web Applications Develop scalable web apps using 无水印原版pdf

A scalable EE_HEMT based large signal model for multi-finger AlGaN_GaN HEMTs ……

Practical Tips for Using MySQL as a Scalable Key-Value Store

Scalable Modified Kneser-Ney Language Model Estimation语言模型PPT

A framework for efficient and scalable execution of domain-specific templates on.pdf

BigchainDB: A Scalable Blockchain Database

Scalable Private Membership Test Using Trusted Hardware

Discretized Streams _ A Fault-Tolerant Model for Scalable Stream Processing

SecureML: A System for Scalable Privacy-Preserving Machine Learn

最新资源