Information Technology Reference
In-Depth Information
If the topology of the network is as complex as the Internet, the dynamics of
rerouting will be more complicated. A single initial failure may lead to lots of
'virtually cut' and 'automatically restored' links, causing a cascade of instabili-
ties. To better understand the process and the effect of this type of failure, we
propose a model to study it. As shown in Fig. 2, our model for cascading failures
in inter-domain routing system consists of three interconnected components, and
iterates along with time. One iteration indicates a step in the cascades.
Initial failure
Congested links
Constructing
topology
Actual topology
Virtual topology
Inter-domain
routing
Load of each
link
Routing policy
Capacity of
each link
Evaluating
link state
Congested links
Fig. 2. Model for cascading failures in inter-domain routing system
Constructing Topology. The first component is to construct a virtual topol-
ogy from the actual topology, initial failure and congested links. We present the
actual topology as an annotated undirected graph G =( V,E ), where V is the
set of all ASes in the inter-domain routing system, and E is the set of AS links
annotated with their relationships, which include provider-customer, customer-
provider and peer-peer. Since BGP is a policy-based routing protocol and AS
relationship is the essential factor to set routing policy, it is important to take
this information into account. The initial failure is the disconnection of an AS
link e ini
E at the first place that triggers follow-up instabilities. Congested
links, denoted as E con ( t )
E , are AS links disconnected by the overload of traf-
fic on them at a certain time t . Therefore, the virtual topology G ( t )=( V,E ( t ))
is the set of ASes and links that are available to exchange routing messages un-
der those failures at time t , i.e., E ( t )= E
E con ( t ). It is worth noting
that the removal of e ini is perpetual while the removal of E con ( t )istemporal.
E con ( t ) changes according to different states of links at different time.
e ini
\{
}\
Inter-domain Routing. The second component is to simulate inter-domain
routing process. The propagation of routing messages is constrained by virtual
topology and controlled by routing polices. According to economic considera-
tions of ASes, there are some common points of routing polices summarized
by previous research [6]. For import polices, if a BGP router receives routes
 
Search WWH ::




Custom Search