FAR_A_fault-avoidance_routing_method_for_data_center_networks_with_regular_topology.pdf

乐呵呵

9页

10次

2024-03-01

免费下载

FAR: A Fault-avoidance Routing Method for Data Center

Networks with Regular Topology

Yantao Sun

School of Computer and Information Technology

Beijing Jiaotong University

Beijing 100044, China

ytsun@bjtu.edu.cn

Min Chen

School of Computer Science & Technology

Huazhong University of Science and Technology

Wuhan 430074, China

minchen@ieee.org

Bin Liu

ZTE Inc.

19 East Huayuan Road

Beijing 100191, China

liu.bin21@zte.com.cn

Shiwen Mao

Department of Electrical and Computer

Engineering

Auburn University

Auburn, AL 36849 USA

smao@ieee.org

ABSTRACT

With the widely deployed cloud services, data center net-

works are evolving toward large-scale and multi-path net-

works, which cannot be supported by conventional routing

methods, such as OSPF and RIP. To alleviate this issue,

some new routing methods, such as PortLand and BSR, are

proposed for data center networks. However, these routing

methods are typically designed for a speciﬁc network ar-

chitecture, and thus lacking adaptability while complex in

fault-tolerance. To address this issue, this paper propos-

es a generic routing method, named fault-avoidance routing

(FAR), for data center networks that have regular topolo-

gies. FAR simpliﬁes route learning by leveraging the regu-

larity in a topology. FAR also greatly reduces the size of

routing tables by introducing a novel negative routing table

(NRT) at routers. The operations of FAR is illustrated by

an example Fat-tree network and the performance of FAR

is analyzed in detail. The advantages of FAR are veriﬁed

through extensive OPNET simulations.

Keywords

Data Center Network; Routing Method; Regular Topology;

Fault-Avoidance Routing; Negative Routing Table

1. INTRODUCTION

In recent years, with the rapid development of cloud com-

puting technologies, the widely deployed cloud services, such

as Amazon EC2 and Google search, bring about huge chal-

lenges to data center networking (DCN)

.Today’sdatacen-

ters (DCs) require large-scale networks with higher internal

bandwidth and lower transfer delay, but conventional net-

works cannot meet such requirements due to limitations in

their network architecture.

In recent years, some new network architectures have been

proposed for data centers [1][2]. These network architec-

tures can support more than tens of thousands of servers

with very high internal bandwidth, and some of them can

In this paper, depending on the context, DCN represents

data center network and data center networking interchange-

ably.

be used to construct non-blocking networks, such as Fat-tree

[3], BCube [4] and MatrixDCN [5]. To connect large num-

bers of servers, many switches or servers with routing func-

tionality are used in a DCN. For example, to accommodate

27,648 servers, a Fat-tree network requires 2,880 switches,

each of which has 48 switching ports. It is unlikely that

generic routing protocols such as OSPF and IS-IS can be

scaled to support several thousands of routers [6], so some

speciﬁc routing protocols are proposed for these architec-

tures. These speciﬁc routing protocols have better perfor-

mance than the generic routing protocols, because they are

delicately designed according to the topological feature of

the network architecture.

In the future, an extra-large-scale DCN may be composed

of several heterogeneous networks, and each network em-

ploys a diﬀerent architecture [7]. Several network architec-

tures coexist in a DC. From the cost-eﬀective point of view,

a desirable routing device should have agility for supporting

various mainstream network architectures and the related

routing protocols, which enables the reuse of the routing

device when the architecture is changed. But in fact, the

proposed routing algorithms for various architectures are so

diﬀerent, which causes diﬃculty to renovate a routing de-

vice to support multiple existing routing protocols. Further-

more, these routing methods have poor compatibility with

the current routing protocols, since the structure and query

method of their routing table, fault-tolerance and routing

mechanism are all diﬀerent with current routing protocols.

It’s a challenging issue to implement these speciﬁc routing

protocols through modifying the current routing protocols.

In addition, to deal with link failures, these speciﬁc routing

methods of new network architectures introduce complicat-

ed fault-tolerance mechanisms, which makes these routing

methods more complex [3] [4].

In this paper, to address the problems above, we propose

a generic routing method, named fault-avoidance routing

(FAR) method, for DCN. Not limited by a speciﬁc type of

network architecture, this routing method can be used in

any network architectures with regular topologies.

FAR consists of three components, i.e., link state learning

unit, routing table building unit and routing table query-

ing unit. In the link state learning unit, FAR exchanges link

181

Authorized licensed use limited to: ZTE CORPORATION. Downloaded on April 18,2024 at 02:35:12 UTC from IEEE Xplore. Restrictions apply.

failures among routers to establish a consistent knowledge of

the entire network. In this stage, the regularity in topology

is exploited to infer failed links and routers. In the routing

table building unit, FAR builds up two routing tables, i.e., a

basic routing table (BRT) and a negative routing table (N-

RT), for each router according to the network topology and

link states. In the last component, routers forward incoming

packets by looking up the two routing tables. The matched

entries in BRT minus the matched entries in NRT are the

ﬁnal route entries to be used for an incoming packet.

FAR simpliﬁes the computing of routing tables by lever-

aging the regularity in topology and decreases the size of

routing tables by introducing the NRT at routers. As op-

posed to the existing routing methods, FAR has the follow-

ing advantages:

• Each router is only conﬁgured one IP address, which

greatly simpliﬁes the conﬁguration of a data center

network.

• By leveraging the regularity in topology, FAR avoids

the problem of network convergence and reduces the

complexity of calculating routes. The time of calcu-

lating routes is shortened to hundreds of milliseconds

from tens of seconds for typical DCN scenarios.

• By introducing NRT, FAR decreases the size of rout-

ing tables. In a DC that contains tens of thousands

of severs, FAR routing tables only have tens of route

entries.

• FAR has good adaptability. It can be used in many

kinds of network topologies after slight modiﬁcations.

The main contributions of this paper are three-fold: 1)

propose a generic routing framework for the DCN with a

regular topology; 2) introduce the negative routing table to

routing methods, which can reduce the size of routing tables;

3) give a performance analysis and a thorough simulation

study of FAR with OPNET.

The remainder of this paper is organized as follows. Sec-

tion 2 introduces the related research on routing for DCN.

Section 3 presents the framework of FAR routing and uses a

Fat-tree network to illustrate the operations of FAR. Section

4 analyzes the performance of FAR. Section 5 veriﬁes FAR

routing through OPNET simulations. Section 6 concludes

for this paper.

2. RELATED WORK

RIP and OSPF are the two generic routing protocols that

are widely applied for interior (intra-domain) routing. As

a distance-vector based algorithm, RIP works ﬁne only for

small-size network, as it uses a hop count of 15 to denote in-

ﬁnity and has the slow convergence or count-to-inﬁnity prob-

lem, which makes it unsuitable for large networks. OSPF

addresses all RIP shortcomings and thus is better suited for

modern large, dynamic networks. But in really large conﬁg-

urations, the huge number of router updates–that ﬂow be-

tween routers–can become an issue. In very large OSPF net-

works, topology convergence can be delayed, while routers

exchange link-state messages, update databases, and recal-

culate routes. To address this issue, an OSPF network is

divided into many areas and each area calculate routes in-

dependently. But in practice, it is very diﬃcult to divide a

data center network, such as a Fat-tree network, into mul-

tiple OSPF areas, so OSPF is not suitable to a large-scale

data center network.

To support large data center networks, some layer-2 rout-

ing methods were proposed. In these layer-2 switching meth-

ods, such as TRILL[8] and Cisco’s FarbricPath[9], some layer-

3 routing technologies are applied for Ethernet frames’ for-

warding in layer-2 network. TRILL is an IETF standard

that is used in devices called RBridges (routing bridges) or

in TRILL Switches, which provide multi-path forwarding for

Ethernet frames. In TRILL, RBridges compute the shortest

path and equal-cost paths in layer 2 by using TRILL IS-IS,

which is a link-state routing protocol similar to IS-IS routing

protocol. MAC-in-MAC encapsulated packets are forwarded

to the destination host via the switched network comprising

RBridges. FabricPath is a similar but private technology

provided by Cisco.

Another layer-2 routing solution is SEATTLE, which us-

es a link-state routing protocol to establish a routing path

between switches [10]. Unlike TRILL, SEATTLE uses the

global switch-level view provided by a link-state routing pro-

tocol to form a one-hop DHT. The DHT stores IP to MAC

mapping and MAC to host location mapping of each host in

switches. SEATTLE converts an ARP request to a unicast-

based message to obtain a destination host’s MAC address

and destination switch that the destination host is connect-

ed to, and then forwards packets to the destination switch.

At last the destination switch forwards packets to the desti-

nation host.

SPAIN [11] and NetLord [12] demonstrate a new think-

ing about layer-2 interconnection based on existing switch

devices in an arbitrary topology. Within these methods, a

set of paths is pre-computed oﬄine for each pair of source-

destination hosts by exploiting the redundancy in a given

network topology. Then, these paths are merged into a set

of trees, and each tree is mapped onto a separate VLAN. In

this way, a proxy application is installed on the hosts, and

the proxy chooses several VLAN paths transmitting packet-

s to the destination host. The advantage of this method is

that multipath is implemented, and routing load is balanced

on multiple paths in an arbitrary topology. Its drawbacks

are inﬂexibility to changes in topology and the modiﬁcations

to hosts.

Besides these generic routing algorithms, researchers pro-

posed some specialized routing algorithms for some special

network architectures. These routing algorithms leverage

the regularity in the topology, so they have higher eﬃciency

on route computing and packet forwarding.

BCube[2] is a sever-centric network architecture in which

servers are responsible for both computing service and rout-

ing function. In BCube, a source routing protocol called

BSR is deployed on servers. BSR has the abilities of load

balance and fault-tolerance. When a new ﬂow comes, the

source sends probe packets over multiple parallel paths and

selects the best path according to probe responses. In gen-

eral, using a source routing protocol in a large-scale network

may result in too much network overhead and too long con-

nection time.

Fat-tree [3] uses two-level routing tables to spread out-

going traﬃc on multiple equal cost paths. When making

a routing decision, a switch looks up a main routing table

ﬁrstly. If no route is hit, then the switch looks up a s-

mall secondary table. To implement fault-tolerance in rout-

182

Authorized licensed use limited to: ZTE CORPORATION. Downloaded on April 18,2024 at 02:35:12 UTC from IEEE Xplore. Restrictions apply.

FAR: A Fault-avoidance Routing Method for Data Center

Networks with Regular Topology

Yantao Sun

School of Computer and Information Technology

Beijing Jiaotong University

Beijing 100044, China

ytsun@bjtu.edu.cn

Min Chen

School of Computer Science & Technology

Huazhong University of Science and Technology

Wuhan 430074, China

minchen@ieee.org

Bin Liu

ZTE Inc.

19 East Huayuan Road

Beijing 100191, China

liu.bin21@zte.com.cn

Shiwen Mao

Department of Electrical and Computer

Engineering

Auburn University

Auburn, AL 36849 USA

smao@ieee.org

ABSTRACT

With the widely deployed cloud services, data center net-

works are evolving toward large-scale and multi-path net-

works, which cannot be supported by conventional routing

methods, such as OSPF and RIP. To alleviate this issue,

some new routing methods, such as PortLand and BSR, are

proposed for data center networks. However, these routing

methods are typically designed for a speciﬁc network ar-

chitecture, and thus lacking adaptability while complex in

fault-tolerance. To address this issue, this paper propos-

es a generic routing method, named fault-avoidance routing

(FAR), for data center networks that have regular topolo-

gies. FAR simpliﬁes route learning by leveraging the regu-

larity in a topology. FAR also greatly reduces the size of

routing tables by introducing a novel negative routing table

(NRT) at routers. The operations of FAR is illustrated by

an example Fat-tree network and the performance of FAR

is analyzed in detail. The advantages of FAR are veriﬁed

through extensive OPNET simulations.

Keywords

Data Center Network; Routing Method; Regular Topology;

Fault-Avoidance Routing; Negative Routing Table

1. INTRODUCTION

In recent years, with the rapid development of cloud com-

puting technologies, the widely deployed cloud services, such

as Amazon EC2 and Google search, bring about huge chal-

lenges to data center networking (DCN)

.Today’sdatacen-

ters (DCs) require large-scale networks with higher internal

bandwidth and lower transfer delay, but conventional net-

works cannot meet such requirements due to limitations in

their network architecture.

In recent years, some new network architectures have been

proposed for data centers [1][2]. These network architec-

tures can support more than tens of thousands of servers

with very high internal bandwidth, and some of them can

In this paper, depending on the context, DCN represents

data center network and data center networking interchange-

ably.

be used to construct non-blocking networks, such as Fat-tree

[3], BCube [4] and MatrixDCN [5]. To connect large num-

bers of servers, many switches or servers with routing func-

tionality are used in a DCN. For example, to accommodate

27,648 servers, a Fat-tree network requires 2,880 switches,

each of which has 48 switching ports. It is unlikely that

generic routing protocols such as OSPF and IS-IS can be

scaled to support several thousands of routers [6], so some

speciﬁc routing protocols are proposed for these architec-

tures. These speciﬁc routing protocols have better perfor-

mance than the generic routing protocols, because they are

delicately designed according to the topological feature of

the network architecture.

In the future, an extra-large-scale DCN may be composed

of several heterogeneous networks, and each network em-

ploys a diﬀerent architecture [7]. Several network architec-

tures coexist in a DC. From the cost-eﬀective point of view,

a desirable routing device should have agility for supporting

various mainstream network architectures and the related

routing protocols, which enables the reuse of the routing

device when the architecture is changed. But in fact, the

proposed routing algorithms for various architectures are so

diﬀerent, which causes diﬃculty to renovate a routing de-

vice to support multiple existing routing protocols. Further-

more, these routing methods have poor compatibility with

the current routing protocols, since the structure and query

method of their routing table, fault-tolerance and routing

mechanism are all diﬀerent with current routing protocols.

It’s a challenging issue to implement these speciﬁc routing

protocols through modifying the current routing protocols.

In addition, to deal with link failures, these speciﬁc routing

methods of new network architectures introduce complicat-

ed fault-tolerance mechanisms, which makes these routing

methods more complex [3] [4].

In this paper, to address the problems above, we propose

a generic routing method, named fault-avoidance routing

(FAR) method, for DCN. Not limited by a speciﬁc type of

network architecture, this routing method can be used in

any network architectures with regular topologies.

FAR consists of three components, i.e., link state learning

unit, routing table building unit and routing table query-

ing unit. In the link state learning unit, FAR exchanges link

181

Authorized licensed use limited to: ZTE CORPORATION. Downloaded on April 18,2024 at 02:35:12 UTC from IEEE Xplore. Restrictions apply.

failures among routers to establish a consistent knowledge of

the entire network. In this stage, the regularity in topology

is exploited to infer failed links and routers. In the routing

table building unit, FAR builds up two routing tables, i.e., a

basic routing table (BRT) and a negative routing table (N-

RT), for each router according to the network topology and

link states. In the last component, routers forward incoming

packets by looking up the two routing tables. The matched

entries in BRT minus the matched entries in NRT are the

ﬁnal route entries to be used for an incoming packet.

FAR simpliﬁes the computing of routing tables by lever-

aging the regularity in topology and decreases the size of

routing tables by introducing the NRT at routers. As op-

posed to the existing routing methods, FAR has the follow-

ing advantages:

• Each router is only conﬁgured one IP address, which

greatly simpliﬁes the conﬁguration of a data center

network.

• By leveraging the regularity in topology, FAR avoids

the problem of network convergence and reduces the

complexity of calculating routes. The time of calcu-

lating routes is shortened to hundreds of milliseconds

from tens of seconds for typical DCN scenarios.

• By introducing NRT, FAR decreases the size of rout-

ing tables. In a DC that contains tens of thousands

of severs, FAR routing tables only have tens of route

entries.

• FAR has good adaptability. It can be used in many

kinds of network topologies after slight modiﬁcations.

The main contributions of this paper are three-fold: 1)

propose a generic routing framework for the DCN with a

regular topology; 2) introduce the negative routing table to

routing methods, which can reduce the size of routing tables;

3) give a performance analysis and a thorough simulation

study of FAR with OPNET.

The remainder of this paper is organized as follows. Sec-

tion 2 introduces the related research on routing for DCN.

Section 3 presents the framework of FAR routing and uses a

Fat-tree network to illustrate the operations of FAR. Section

4 analyzes the performance of FAR. Section 5 veriﬁes FAR

routing through OPNET simulations. Section 6 concludes

for this paper.

2. RELATED WORK

RIP and OSPF are the two generic routing protocols that

are widely applied for interior (intra-domain) routing. As

a distance-vector based algorithm, RIP works ﬁne only for

small-size network, as it uses a hop count of 15 to denote in-

ﬁnity and has the slow convergence or count-to-inﬁnity prob-

lem, which makes it unsuitable for large networks. OSPF

addresses all RIP shortcomings and thus is better suited for

modern large, dynamic networks. But in really large conﬁg-

urations, the huge number of router updates–that ﬂow be-

tween routers–can become an issue. In very large OSPF net-

works, topology convergence can be delayed, while routers

exchange link-state messages, update databases, and recal-

culate routes. To address this issue, an OSPF network is

divided into many areas and each area calculate routes in-

dependently. But in practice, it is very diﬃcult to divide a

data center network, such as a Fat-tree network, into mul-

tiple OSPF areas, so OSPF is not suitable to a large-scale

data center network.

To support large data center networks, some layer-2 rout-

ing methods were proposed. In these layer-2 switching meth-

ods, such as TRILL[8] and Cisco’s FarbricPath[9], some layer-

3 routing technologies are applied for Ethernet frames’ for-

warding in layer-2 network. TRILL is an IETF standard

that is used in devices called RBridges (routing bridges) or

in TRILL Switches, which provide multi-path forwarding for

Ethernet frames. In TRILL, RBridges compute the shortest

path and equal-cost paths in layer 2 by using TRILL IS-IS,

which is a link-state routing protocol similar to IS-IS routing

protocol. MAC-in-MAC encapsulated packets are forwarded

to the destination host via the switched network comprising

RBridges. FabricPath is a similar but private technology

provided by Cisco.

Another layer-2 routing solution is SEATTLE, which us-

es a link-state routing protocol to establish a routing path

between switches [10]. Unlike TRILL, SEATTLE uses the

global switch-level view provided by a link-state routing pro-

tocol to form a one-hop DHT. The DHT stores IP to MAC

mapping and MAC to host location mapping of each host in

switches. SEATTLE converts an ARP request to a unicast-

based message to obtain a destination host’s MAC address

and destination switch that the destination host is connect-

ed to, and then forwards packets to the destination switch.

At last the destination switch forwards packets to the desti-

nation host.

SPAIN [11] and NetLord [12] demonstrate a new think-

ing about layer-2 interconnection based on existing switch

devices in an arbitrary topology. Within these methods, a

set of paths is pre-computed oﬄine for each pair of source-

destination hosts by exploiting the redundancy in a given

network topology. Then, these paths are merged into a set

of trees, and each tree is mapped onto a separate VLAN. In

this way, a proxy application is installed on the hosts, and

the proxy chooses several VLAN paths transmitting packet-

s to the destination host. The advantage of this method is

that multipath is implemented, and routing load is balanced

on multiple paths in an arbitrary topology. Its drawbacks

are inﬂexibility to changes in topology and the modiﬁcations

to hosts.

Besides these generic routing algorithms, researchers pro-

posed some specialized routing algorithms for some special

network architectures. These routing algorithms leverage

the regularity in the topology, so they have higher eﬃciency

on route computing and packet forwarding.

BCube[2] is a sever-centric network architecture in which

servers are responsible for both computing service and rout-

ing function. In BCube, a source routing protocol called

BSR is deployed on servers. BSR has the abilities of load

balance and fault-tolerance. When a new ﬂow comes, the

source sends probe packets over multiple parallel paths and

selects the best path according to probe responses. In gen-

eral, using a source routing protocol in a large-scale network

may result in too much network overhead and too long con-

nection time.

Fat-tree [3] uses two-level routing tables to spread out-

going traﬃc on multiple equal cost paths. When making

a routing decision, a switch looks up a main routing table

ﬁrstly. If no route is hit, then the switch looks up a s-

mall secondary table. To implement fault-tolerance in rout-

182

Authorized licensed use limited to: ZTE CORPORATION. Downloaded on April 18,2024 at 02:35:12 UTC from IEEE Xplore. Restrictions apply.

of 9

免费下载

goldendb paper

关注

评论