Information Technology Reference
In-Depth Information
Reachability.
The virtually cut links entailed by overload could be plentiful
at a certain time. On this incomplete topology regarding to the actual one, we
wonder if the routing system is still able to find paths for any pair of source
and destination. Hence, as shown in Eqn. (3), we define a metric
reachability
,
denoted as
R
to measure this capability of the inter-domain routing system.
R
(
t
)=
u,w∈V
χ
uw
(
t
)
N
(3)
·
(
N
−
1)
where
χ
uw
(
t
) is equal to 1 if there exist a path from
u
to
w
at time
t
.Otherwise,
it is equal to 0.
N
is the total number of ASes in the Internet, i.e.,
N
=
|
V
|
.
Higher reachability indicates higher survivability of the routing system.
Rerouting Messages.
The most essential task for a routing system of net-
works is to make routing decisions. However, if large amounts of paths need to
be rerouted around faulty links, large amounts of BGP messages will be gen-
erated, sent and processed. In this case, the computational load on a router's
CPU increases dramatically, possibly exceeding the capacity of processors, then
weakening the system's ability of routing. So we propose the number of
rerout-
ing messages
that received by
core ASes
at a given time to measure how the
cascading failures affect every critical ASes in the Internet. We identify the core
ASes by sorting the amount of trac load that every transit AS transmits for
other ASes, then selecting the top one percent ASes to form the core AS set
V
c
.
In the Internet, most ASes are stub ASes rather than transit ASes. They are
not our targets for this study. The number of rerouting messages received by
u
(
u
∈
V
c
) is defined as
RM
u
(
t
)=
w∈V
δ
uw
(
t
−
1
,t
)
·
ρ
(
w
)
(4)
where
δ
uw
(
t −
1
,t
) is the number of paths from
u
to
w
that are different at
t −
1
and
t
. In our model, paths are rerouted only due to changes of virtual topology.
ρ
(
w
) is the number of IP prefixes in
w
. Since in BGP, the routing messages
are generated regarding to every IP prefix. The more prefixes an AS has, the
more routing messages it will generate when paths targeted to it need to be
rerouted. The distribution of
RM
wrt. every AS in core AS set reveals different
effects of the failure on different AS. Generally speaking, more rerouting messages
indicates lower survivability of the inter-domain routing system.
In our model, many factors could affect the survivability of the inter-domain
routing system. In this paper, we focus on analysing the tolerance parameter
α
and the initial failure of link
e
ini
. First of all, we examine the relationship
between survivability and capacity of AS links to evaluate under what condition
a global instability of the Internet will emerge. Secondly, we divide the initial
failure as intentional attack and random breakdown, and further analyse the
difference of survivability of inter-domain routing system under these two kinds
of initial failures.
