Ahybridlinkprotectionschemeforensuringnetworkserviceavailabilityinlink-stateroutingnetworks资源-CSDN文库

135 浏览量 2021-02-08 12:42:06 上传评论收藏 999KB PDF 举报

A hybrid link protection scheme for ensuring network service availability in link-state routing networks 互联网在全球范围内扮演着越来越关键的角色，无论是个人活动还是商业活动都对其依赖度越来越高。随着实时、延迟敏感和任务关键性应用的出现，对互联网服务提供商（ISP）提出了更为严格的网络可用性要求。然而，在出现链路故障时，常见的域内链路状态路由协议通过全局交换链路状态广播和重新计算路由表来响应，这不可避免地会造成故障后显著的转发中断。因此，许多互联网骨干网络采用了无环准则（Loop-Free Criterion, LFC）方法来应对单个网络组件故障的场景。无环准则（LFC）方法的优势在于其固有的简单性，但这种方法的代价是让某些故障场景未得到保护。为了在不增加显著额外开销的情况下，实现与LFC相同的完整故障覆盖，提出了一种新的链路保护方案——混合链路保护（Hybrid Link Protection, HLP），以实现具有故障恢复能力的路由。与以往的方案相比，HLP能够以更高效的方式确保高网络可用性。HLP分为两个阶段实施：第一阶段提供了一种基于LFC的高效方法，即MNP-e（Modified Next-Hop Protection with efficient LFC）。该算法的复杂度小于Dijkstra算法，并且可以提供与LFC相似的网络可用性。MNP-e方案的核心在于对传统网络路径保护方法的改进，它能够减少备份路径的使用数量，并尽可能缩短备份路径的长度，从而减少网络中的拥塞点和潜在的单点故障。第二阶段提供基于MNP-e的备份路径保护（Backup Path Protection, BPP）。这里只需要保护最少数量的链路，并使用特殊的路径和数据包头部，以满足网络可用性的要求。BPP的设计是基于对网络拓扑结构的深入分析，它通过对网络中的关键链路进行识别，并预先计算出故障时的备份路径，确保在网络中任何链路故障发生时，能够快速地将流量切换到预先计算好的备份路径上，从而最小化服务中断的时间。研究人员还评估了这些算法在广泛的相关拓扑结构上的性能表现，包括真实的和合成的网络拓扑。实验结果显示，所提出的混合链路保护方案能够在保持高网络可用性的同时，有效地减少故障恢复时间并降低因故障而导致的数据包丢失数量。此研究部分由国家重点研发计划（No.2018YFB1800401）和国家自然科学基金（No.***）等项目支持，这为研究提供了资金和资源保障。总而言之，该研究提出的混合链路保护方案通过两个阶段的策略，一方面通过改进的LFC方法保证了网络的基本可用性，另一方面利用备份路径保护策略增强了网络的故障恢复能力。这种结合了传统技术和现代网络设计理念的方法，展示了在保证网络服务高可用性的同时，也能对网络资源进行有效管理和利用。这对于未来互联网尤其是大型互联网骨干网络的设计、实施和维护具有重要参考价值和现实意义。

资源推荐

资源详情

资源评论

Creative Commons Attribution-NonCommercial (CC BY-NC).

This is an Open Access article distributed under the terms of Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0)

which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided that the original work is properly cited.

46 JOURNAL OF COMMUNICATIONS AND NETWORKS, VOL. 22, NO. 1, FEBRUARY 2020

A Hybrid Link Protection Scheme for Ensuring

Network Service Availability in Link-state Routing

Networks

Haijun Geng, Han Zhang, Xingang Shi, Zhiliang Wang, Xia Yin, Ju Zhang, Zhiguo Hu, and Yong Wu

Abstract: The internet is playing an increasingly crucial role in

both personal and business activities. In addition, with the emer-

gence of real-time, delay sensitive and mission-critical applications,

stringent network availability requirement is put forward for inter-

net service providers (ISPs). However, commonly deployed intra-

domain link-state routing protocols react to link failures by glob-

ally exchanging link state advertisements and recalculating rout-

ing table, inevitably causing signiﬁcant forwarding discontinuity

after a failure. Therefore, the loop-free criterion (LFC) approach

has been widely deployed by many ISPs for coping with the single

network component failure scenario in large internet backbones.

The success of LFC lies in its inherent simplicity, but this comes

at the expense of letting certain failure scenarios go unprotected.

To achieve full failure coverage with LFC without incurring signif-

icant extra overhead, we propose a novel link protection scheme,

hybrid link protection (HLP), to achieve failure resilient routing.

Compared to previous schemes, HLP ensures high network avail-

ability in a more efﬁcient way. HLP is implemented in two stages.

Stage one provides an efﬁcient LFC based method (MNP-e). The

complexity of the algorithm is less than that of Dijkstra’s algo-

rithm and can provide the similar network availability with LFC.

Stage two provides backup path protection (BPP) based on MNP-e,

where only a minimum number of links need to be protected, using

special paths and packet headers, to meet the network availabil-

ity requirement. We evaluate these algorithms in a wide spread of

relevant topologies, both real and synthetic, and the results reveal

Manuscript received November 7, 2018; approved for publication by

Mubashir Husain Rehmani, Division III Editor, November 8, 2019.

This work is partially supported by the National Key Research and Devel-

opment Program of China (No.2018YFB1800401), the National Natural Sci-

ence Foundation of China (No.61702315), Open Foundation of State Key Lab-

oratory of Networking and Switching Technology (Beijing University of Posts

and Telecommunications)(SKLNST-2018-1-19), the National Natural Science

Foundation of China (No.61872226) and the Natural Science Foundation of

Shanxi Province, China (No.201701D121052).

H. Geng is with the School of Software Engineering, Shanxi University, Open

Foundation of State Key Laboratory of Networking and Switching Technology,

email: ghj123025449@163.com.

H. Zhang is with the School of Cyber Space and Technology, Beihang Uni-

versity, email: zhhan@buaa.edu.cn.

X. Shi and Z. Wang are with the Institute for Network Sciences and Cy-

berspace, Tsinghua University, and Beijing National Research Center for In-

formation Science and Technology, email: {shixg, wzl}@cernet.edu.cn.

X. Yin is with the Department of Computer Science and Technology, Tsinghua

University, and Beijing National Research Center for Information Science and

Technology, email: yxia@tsinghua.edu.cn.

J. Zhang is with the School of Software Engineering, Shanxi University, Open

Foundation of State Key Laboratory of Networking and Switching Technology,

email: zj4090@139.com.

Z. Hu is with the School of Computer and Information Technology, Shanxi

University, email: huzhiguotj@sxu.edu.cn.

Y. Wu is with the School of Software Engineering, Shanxi University,

email: wuyong@sxu.edu.cn.

Z. Wang is the corresponding author.

Digital Object Identiﬁer: 10.1109/JCN.2019.000056

that HLP can achieve high network availability without introduc-

ing conspicuous overhead. HLP not only needs around 10% time of

that of full protection, but also provides full protection capabilities

that full protection provide.

Index Terms: Incremental shortest path ﬁrst, loop-free, multipath

routing, network availability, network link failure

I. INTRODUCTION

ITH the rapid development of the internet, more and

more mission-critical and real-time applications, such as

VoIP and video streaming, raise stringent network availability

requirement [1], [2]. Unfortunately, network availability is of-

ten reduced by unexpected failures as well as routine opera-

tions [3]. Traditional routing algorithms, such as open shortest

path ﬁrst (OSPF) and Intermediate system-to-intermediate sys-

tem (IS-IS), are mostly concerned with ﬁnding shortest paths

towards each destination, and thus cannot provide good connec-

tivity under frequent network failures. On detecting a failure,

they start a global link-state advertisement and then recompute

routes, inevitably causing network outage [4], [5]. This high-

lights the need for mechanisms that possess fast and efﬁcient

recovery capability [6]–[9].

Two categories of solutions are proposed to deal with this

problem. The ﬁrst category uses reactive methods to acceler-

ate the convergence of link-state routing protocol through tuning

several parameters [10]. However, the risk of introducing insta-

bility in the network makes it less attractive, especially in the

face of frequent momentary link failures. The other one adopts

proactive schemes which compute backup paths in advance, so

that packets can be forwarded over those precompute paths after

the detection of a link failure. Existing proactive schemes can

be further divided into two sub-categories, by whether special

cooperation/signaling between routers are required for packet

forwarding. Cooperation-free schemes compute multiple next-

hops for each destination, and each router independently selects

an appropriate next-hop for standard packet forwarding, where

care must be taken such that the induced forwarding paths must

be loop-free. The beneﬁt is that they can provide not only re-

dundant backup links, but also other features such as load bal-

ancing and high throughput, while the problem is, they often

can only protect a limited number of links. For example, recent

studies [11] show that almost 40% links cannot be protected by

loop free alternates (LFA) [12], a scheme adopted by the IP

fast-reroute (IPFRR) [13] framework. The other sub-category

of schemes compute, for a link to protect, a multi-hop repair

1229-2370/19/$10.00

 2019 KICS

HAIJUN GENG et al.: A HYBRID LINK PROTECTION SCHEME FOR ENSURING ... 47

path that is agreed by all routers on that path. Thus special co-

operation mechanisms have to be employed to reroute packets

along that path. All these proactive schemes introduce consid-

erable computation overhead, while only the latter sub-category

can provide full coverage for a large network, at the cost of ad-

ditional cooperation cost.

In this paper, we propose a novel scheme called hybrid link

protection (HLP), which meets the network availability require-

ment without inducing signiﬁcant overhead by extending and

combining the two kinds of proactive schemes above. HLP con-

sists of two stages. Stage one provides MNP-e, where a highly

efﬁcient incremental shortest path ﬁrst (i-SPF) based algorithm

is proposed to help a node ﬁnd all the LFC next-hops for each

destination, both locally and independently. Based on the ex-

isting work on this research area, we for the ﬁrst time pro-

pose an algorithm whose complexity is less than that of Dijk-

stra algorithm and without degrading the network availability of

LFC. Then, in stage two, based on the argument that uneven

link failure probability or importance should be taken into ac-

count, backup path protection (BPP) selects a minimum number

of links according to the network availability requirement, and

computes the corresponding multi-hop backup paths to protect

them. In this way, HLP can attain the beneﬁts of both kinds of

schemes mentioned above, and achieves them with much less

overhead. In this way, HLP can attain the beneﬁts of both kinds

of schemes mentioned above, and achieves them with much less

overhead.

Our main contributions are summarized as follows:

• We propose HLP to effectively protect failed links. HLP can

provide full network protection in a very efﬁcient way.

• We design MNP to compute multiple loop-free next-hops for

link protection, where only a single SPT need to be con-

structed on each router. This, both in theory and practice,

is much faster than existing algorithms that need to construct

multiple SPTs.

• We design MNP-e (an extension of MNP) to compute mul-

tiple loop-free next-hops for link protection, theoretical anal-

ysis indicates that the computation complexity of MNP-e is

less than that of constructing a shortest path tree, and MNP-

e can provide the similar network availability with LFC. We

theoretically prove the correctness of MNP-e algorithm.

• We argue that different link failures have different contribu-

tion to the network availability, and propose BPP to protect

a minimal number of links to meet the network availability

requirement.

• We evaluate the performance of our algorithm against other

link protection schemes in a uniﬁed framework, using both

real and synthetic topologies with different network availabil-

ity requirements. Compared with other solutions, HLP can not

only ensure good network availability, but also cannot intro-

duce conspicuous overhead.

• These advantages make HLP a good candidate for both tra-

ditional telecommunication networks andemerging complex

networks that require failure repair and load balancing in a

highly dynamic environment.

The remainder of this paper is organized as follows. Section II

introduces the related works. Section III presents the details

of HLP’s architecture. Section IV describes the MNP-e and its

properties in detail. Section V introduces BPP. Section VI eval-

uates MNP-e and HLP in a variety of network topologies, and

ﬁnally Section VII concludes the paper.

II. RELATED WORKS

Nowadays, network failures have become routine events

rather than exceptions. Many schemes have been proposed to

deal with this problem from different aspects, from physical

level methods such as optical routing protection, to IP level ap-

proaches.

IETF has drafted a framework named IPFRR [12]–[14],

which aims to provide fast recovery from network failures. The

basic idea is that, when a node detects the failure of a link di-

rectly connected to itself, it can immediate switch to backup

paths that are speciﬁcally computed for this failure. Based on

this basic framework, current solutions fall into two categories.

The ﬁrst category computes multiple next-hops for each desti-

nation such that, even if routers independently select them in a

hop-by-hop manner for detouring the failed links, loop-free can

still be guaranteed, and thus packet routing/forwarding can be

done as usual, i.e., no further cooperation or signaling mecha-

nisms are needed. The second category compute a multi-hop

repair path for any link to be protected, and requires explicit co-

operation/signaling between routers to ensure packets are indeed

routed along this path when necessary.

Firstly, we will describe some schemes that can provide hop-

by-hop loop-free routing are applicable in IPFRR (i.e., in the

ﬁrst category). Equal-cost multipath routing (ECMP) [15] al-

lows packets to be forwarded along multiple paths of equal

cost, which can be speciﬁcally tuned by network operators.

However, ECMP cannot offer good reliability since it is lim-

ited to cases where equal cost paths exist. Loop-free alter-

nate (LFA) [12] proposes several basic criteria for selecting

a proper next-hop, including loop-free criterion (LFC), node

protection condition (NPC) and downstream criterion (DC), to

guarantee loop-freeness. However, naively verifying these crite-

ria requires multiple shortest-path trees (SPT), and the cost in-

creases proportionally to the degree of a node (one SPT for each

neighbor). Routing deﬂection [16] relaxes DC by taking nodes

two hops away into account, at the cost of greater implemen-

tation complexity. TBFH [17] achieves faster computation by

tightening DC, but still needs to construct multiple SPTs. Per-

mutation Routing [18], [19] treats routers as a sequence of re-

sources, and creates permutations of these resources that of-

fer several forwarding alternatives, where each permutation is

equivalent to a SPT and the time complexity is proportional to

the number of permutations they want. Several algorithms [20]–

[22] compute a directed acyclic graph (DAG) for each destina-

tion to avoid loops, so in a network with |V | nodes, their time

complexity is in the order of |V | times the cost of computing a

single DAG, which is already more complicated than computing

a SPT. More next-hops can be found at the cost of increasingly

sophisticated DAGs, but there is no guarantee to ﬁnd an alternate

next-hop for each destination (or each link). FIR [21] improves

the protecting capability against a single link failure by com-

puting different alternates for packets from different incoming

ports, at the cost of an increased computation overhead, and a re-

48 JOURNAL OF COMMUNICATIONS AND NETWORKS, VOL. 22, NO. 1, FEBRUARY 2020

stricted scenario, i.e., only for protecting a link. In [23], authors

show that improving LFA failure case coverage is feasible with-

out touching the physical topology and the forwarding paths in

any ways, or requiring any new features from the IP data and the

control planes that are essentially ﬁxed by what is available in

commercial network gear today. FIFR++ approach [24] employ

progressive link metric increments in conjunction with FIFR and

proves that FIFR++ is loop-free while protecting against single

link failures. Authors in [25] present DMPA-e by incorporat-

ing hop count, a topology dependent metric. However, DMPA-e

cannot achieve full failure coverage against single network com-

ponent failures. Then, we will describe some schemes that uses

explicit cooperation/signaling schemes to route packets along a

multi-hop repair path. Multi-topology routing [26], [27] com-

pute multiple routes based on backup network topologies tai-

lored for speciﬁc failures, either by removing the corresponding

links or by increasing their associated weights. Routers can con-

trol which topology the routers should be employed by chang-

ing additional bits in the packet header. Path splicing [28]

creates a set of slices for the network based on random link-

weight perturbations, and end system can control which slices

the routers should use by embedding control bits in packet head-

ers. Node/link-independent conﬁgurations of a topology are also

computed to make the routing resilient under any single link

fault [29].

The capability, as well as the complexity, of these algorithms

is proportional to the number of alternative conﬁgurations they

want to employ. Failure-carrying packets (FCP) [30] carries link

failure information in the IP packet header to allow routers to

diagnose problems and select alternate paths. However, this

scheme also requires considerable overhead to ﬁnd the new

working path when receiving a packet carrying root-cause fail-

ure messages. Not-via [14] proposes a framework to use special

not-via addresses to provide link protection by such multi-hop

paths. Authors in [31] propose the scheme to cope with single

network component failure in segment routing networks. Au-

thors in [32] propose how to deploy LFA into software deﬁned

networks (LFASDN). And they suggest to build an augmented

fat-tree topology which allows LFA to protect against all single

link and node failures. TOD [4] proposes tunneling on demand

(TOD) to handle one or dual link failures, but needs an addi-

tional signaling protocol to establish tunnels. Authors in [33]

presented the STATIC-ROUTING-RESILIENCY problem and

explored the power of static fast failover routing in a variety of

models. And also the schemes can provide resiliency against k-1

failures, with limited path stretch. A few studies [11], [34] com-

pare the computation complexity and network protection capa-

bility of the above two categories of schemes. Since both of them

need intensive computation, it is argued that not-via address is

better, in the sense that it provides higher network protection

coverage [34]. In this paper, we focus on protection schemes

that (1) are computationally efﬁcient, (2) provide high network

protection coverage, and (3) preserve as much as possible the

beneﬁts that multiple next-hop solutions have, such as no co-

operation/signaling and load balancing. Therefore, we propose

a novel link protection scheme, hybrid link protection (HLP),

D is average node degree of the network.

m is the number of slice.

to achieve failure resilient routing. Our previously published

paper [35] gives some preliminary ideas about HLP. HLP is im-

plemented in two stages. Stage one performs a multipath rout-

ing algorithm, which is similar to the paper [16]. However, the

time complexity of the stage one increases proportionally to the

degree of a node, which makes it impractical to deploy on the

internet. Therefore, we improved the stage one of HLP in our

published paper [36]. In [36], stage one provides an efﬁcient

LFC based method (MNP). The time complexity of MNP does

not depend on the degree of the calculating router. However,

MNP cannot compute all the feasible backup next-hops which

are conformed to LFC. This paper mainly concerns on how to

overcome the drawbacks of [35] and [36]. In this paper, we for

the ﬁrst time propose an algorithm (MNP-e) in the stage one

whose complexity is less than that of Dijkstra algorithm and

without degrading the network availability of LFC. A compari-

son of several existing fast reroute solutions and ours are sum-

marized in Table 1.

III. OVERVIEW OF HYBRID LINK PROTECTION

A. Network Model

We ﬁrst explain the basic network model used in this pa-

per. We represent the network by a undirected connected graph

G = (V, E), where V and E are respectively the set of nodes

and links in the network. Each link (u, v) ∈ E has a cost

L(u, v), and is further characterized by a failure probability

r(u, v). L(u, v) = ∞ if u and v are not neighbors, and the link

failure events are statistically independent of each other. We use

to denote the shortest path tree rooted at node c, D(T

, x)

to denote the descendants of node x (x is included) in the T

(c, x) is a shortest path tree rooted at node c when the edge

(c, x) ∈ T

change its weight to −L(c, x). D(T

(c, x), x) to de-

note the descendants of node x (x is included) in the T

(c, x).

The main objective of HLP is to achieve high network avail-

ability by efﬁciently protecting links. We formally deﬁne the

network availability A(G) as follows, and use it as a main met-

ric to evaluate the protection capability of different schemes.

The end-to-end availability of a source-destination (s-d) pair

is deﬁned as the probability that the packets can be correctly

forwarded from s to d. Assume that there exist n different for-

warding paths from s to d, the ith which is denoted by p

(s, d).

We also use P

(s, d) to represent the set of links on the p

(s, d).

Further, let the event that p

(s, d) works be denoted by A

(s, d),

whose probability can be expressed as [37]:

P (A

) =

∀(m,n)∈P

(s,d)

r(m, n). (1)

According to the Inclusion-Exclusion principle [38], the end-

to-end availability of a source-destination pair can be expressed

as:

A(s, d) =

k=1

(−1)

(k−1)

, (2)

where S

denote the sum of the probabilities that a unique set of

k paths from s to d are simultaneously working, which is further

expressed as [37]:

剩余14页未读，继续阅读

评论收藏

内容反馈

weixin_38670065

粉丝: 4
资源: 923

A hybrid link protection scheme for ensuring network service ava...

最新资源

A hybrid link protection scheme for ensuring network service ava...

A Constrained Shortest Path Scheme for Virtual Network Service Management

A Sociability-Based Routing Scheme for Delay-Tolerant Networks

A probabilistic position-based routing scheme for delay-tolerant networks

A-PUF-FSM-Binding-Scheme-for-FPGA-IP-Protection-and-Pay-per-Device-Licensing.pdf

A cognitive p-persistent CSMA scheme for spectrum sharing based cognitive radio networks

A Preprocessing Scheme for High-Cardinality Categorical Attributes

Cisco Press - OSPF Network Design Solutions, 2nd Edition

A Hybrid Key Management Scheme for WSNs Based on PPBR and a Tree-Based Path Key Establishment Method

Modified anti-windup scheme for PID controllers

[elearnica.ir]-A_hybrid_protection_scheme_based_o_Protection

OBOF: A protection scheme for survivable fiber-wireless broadband access network

A simple location propagation scheme for mobile sink in wireless sensor network

A monotone finite element scheme for convection-diffusion equations.pdf

On Multihop Communications For In-Vehicle Internet Access Based

Cognitive Radio Networks

Cloud and Fog Computing in 5G Mobile Networks-IET(2017).pdf

CFR: A cooperative link failure recovery scheme in software-defined networks

SMACK - A SMart ACKnowledgment__ Scheme for Broadcast Messages in Wireless Networks

RFC10xx 内容,分析与详解

A unified scheme for adaptive stroke-based rendering.pdf

A Novel MIMO-STBC Scheme for Inter-Vehicle Communications at Intersection.

CorSegRec: A Topology-Preserving Scheme for Extracting Fully-Con

计算机网络第六版答案

HDLBR: A name-independent compact routing scheme for power-law networks

最新资源