Information Technology Reference
In-Depth Information
to the same destination from different neighbours, it prefers route from cus-
tomer over those from peer then from provider. Metrics such as path length and
other BGP attributes are used in route selection if the preference is the same
for different routes. This policy is known as
customer-prefer
. For export polices,
an AS does not transmit trac between any of its providers or peers, which
is called
valley-free
property. Under these circumstances, connectivity does not
mean reachability in the inter-domain routing system. In our model, we assume
that all ASes follow customer-prefer and valley-free polices, and simulate route
selections from any source to any destination. Since the inter-domain trac from
source to destination follows the AS path in BGP route, the more AS paths an
AS link participates in, the more trac load the link will transmit. Moreover,
the size of source and destination AS should be taken into account. Because
large AS usually generates more trac load. In this paper, we use the number
of IPs that an AS announces to assess the size of the AS. Therefore, the load on
an AS link is formulated as
L
e
=
u,w∈V
σ
uw
(
e
)
·
ϕ
(
u
)
·
ϕ
(
w
)
u,w∈V
σ
uw
·
(1)
ϕ
(
u
)
·
ϕ
(
w
)
The summation is over all ASes in
V
.
σ
uw
(
e
) denotes the total number of AS
paths between
u
and
w
that pass through AS link
e
.
σ
uw
denotes the total
number of AS paths between
u
and
w
.
ϕ
(
u
)and
ϕ
(
w
) denote the number of IPs
that
u
and
w
have. The value of load is normalized into [0, 1]. Accordingly, we
could calculate the load on any AS link at any time, denoted as
L
e
i
(
t
).
Evaluating Link State.
The next is to evaluate whether an AS link is con-
gested. The capacity of a link is the maximum load it can handle. We assume
that the capacity
C
e
of link
e
is proportional to its initial load
L
e
(0), i.e.,
C
e
=(1+
α
)
·
L
e
(0)
(2)
where
α
0 is the tolerance parameter of the network [1]. If the load on an
AS link increases and becomes larger than its capacity, the link is congested.
The
KEEPALIVE
messages spoken by BGP routers at two ends of link will be
dropped along with data packets. As a result, those BGP routers assume that
the link is disconnected and end the BGP session between them. Hence we treat
congested links as 'virtual cuts' of the network. Meanwhile, if the load on previous
congested link decreases below its capacity, the link will 'automatically restore'
and be capable of exchanging routing messages again. The current comparison
of load and capacity determines congested state of AS link at the next time step
in cascades, i.e.,
≥
∀
e
i
∈
E
con
(
t
+1)
,L
e
i
(
t
)
>C
e
i
.
3 Assessing Survivability under the Model
To assess survivability of inter-domain routing system under this cascading
model, the first step is to characterize the survivability quantitatively. In this pa-
per, we propose two different metrics to measure the survivability from different
perspectives.
