Fast rerouting method in MPLS networks in case of failures
The problem of nonlinearity identification in experimental data is considered with application of appropriate statistical tests. An analysis of known statistical nonlinearity test is presented that is based on Fisher relation, and a new simplified test is proposed that can be used in conditions of i...
Gespeichert in:
| Datum: | 2012 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2012
|
| Schriftenreihe: | Системні дослідження та інформаційні технології |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/50197 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Fast rerouting method in MPLS networks in case of failures / Hatamleh Hazem // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 74-79. — Бібліогр.: 3 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50197 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-501972025-02-23T17:01:44Z Fast rerouting method in MPLS networks in case of failures Швидкий алгоритм ремаршрутизації в мережах із технологією MPLS в умовах дії відмов Быстрый алгоритм ремаршрутизации в сетях с технологией MPLS в условиях отказов Hatamleh Hazem Проблемно і функціонально орієнтовані комп’ютерні системи та мережі The problem of nonlinearity identification in experimental data is considered with application of appropriate statistical tests. An analysis of known statistical nonlinearity test is presented that is based on Fisher relation, and a new simplified test is proposed that can be used in conditions of incomplete experimental or statistical data. The empirical statistical nonlinearity criterion is computed on the basis of existence of a link between the values of respective cumulative sum and sample based standard deviation. It was empirically established that there exists a close link between the proposed and existing tests in the sense of similarity of final testing results. To find the critical values of statistics that are necessary for statistical decision making with the use of the simplified test appropriate computational experiments have been fulfilled. It has also been established that the test proposed can be used successfully in conditions of complete and incomplete experimental data. The practical application of the test proposed to actual data proved the similarity of results obtained with various approaches. Роботу присвячено захисту шляхів, комутованих по мітках, у мережах MPLS від відмов обладнання, в першу чергу маршрутизаторів. Мета работи полягає в розробці швидкого алгоритму ремаршрутизації для захисту трафіка від дії відмов, який би забезпечив найкраще використання смуги пропускання та виконання вимог по забезпеченню за показниками якості сервісу. Використання для цієї мети глобальних алгоритмів потребує великого обсягу смуги пропускної спроможності, що малоприйнятне. Тому методи локальної ремаршрутизації можуть стати засобом, який ефективно вирішує цю задачу. Запропоновано алгоритм вибору резервних шляхів, який дозволяє зменшити обсяг ресурсів, що використовуються. Відмінною рисою цього запропонованого локального алгоритму ремаршрутизації від аналогічних алгоритмів є те, що він відшукує резервні тунелі з урахуванням показників якості обслуговування та працює у децентралізованому режимі. Запропонований алгоритм використовує інформацію, отриману за допомогою RSVP-повідомлень та дозволяє суттєво зменшити обсяги службової інформації в мережі. Проведені експериментальні дослідження запропонованого децентралізованого алгоритму та його порівняння з централізованим глобальним алгоритмом ремаршрутизації. Работа посвящена защите путей, коммутируемых по меткам, в сетях MPLS от отказов оборудования, в первую очередь маршрутизаторов. Цель работы состоит в разработке быстрого алгоритма ремаршрутизации для защиты трафика от действия отказов, который бы обеспечил наилучшее использование полосы пропускания и выполнение требований по показателям качества сервиса. Использование для этих целей глобальных алгоритмов требует большого объема полосы пропускной способности, что мало приемлемо. Поэтому методы локальной ремаршрутизации могут оказаться средством, которое эффективно решает эту задачу. Предложен алгоритм выбора резервных маршрутов, позволяющий уменьшить используемый объем ресурсов. Отличительной чертой предложенного локального алгоритма ремаршрутизации от аналогичных алгоритмов состоит в том, что данный алгоритм отыскивает резервные туннели с учетом показателей качества обслуживания и работает в децентрализованном режиме. Предложенный алгоритм использует информацию, полученную с помощью RSVP-сообщений, и позволяет существенно уменьшить объем служебной информации в сети. Проведены экспериментальные исследования предложенного децентрализованного алгоритма и его сравнение с централизованным глобальным алгоритмом ремаршрутизации. 2012 Article Fast rerouting method in MPLS networks in case of failures / Hatamleh Hazem // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 74-79. — Бібліогр.: 3 назв. — англ. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/50197 681.324 en Системні дослідження та інформаційні технології application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| spellingShingle |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Проблемно і функціонально орієнтовані комп’ютерні системи та мережі Hatamleh Hazem Fast rerouting method in MPLS networks in case of failures Системні дослідження та інформаційні технології |
| description |
The problem of nonlinearity identification in experimental data is considered with application of appropriate statistical tests. An analysis of known statistical nonlinearity test is presented that is based on Fisher relation, and a new simplified test is proposed that can be used in conditions of incomplete experimental or statistical data. The empirical statistical nonlinearity criterion is computed on the basis of existence of a link between the values of respective cumulative sum and sample based standard deviation. It was empirically established that there exists a close link between the proposed and existing tests in the sense of similarity of final testing results. To find the critical values of statistics that are necessary for statistical decision making with the use of the simplified test appropriate computational experiments have been fulfilled. It has also been established that the test proposed can be used successfully in conditions of complete and incomplete experimental data. The practical application of the test proposed to actual data proved the similarity of results obtained with various approaches. |
| format |
Article |
| author |
Hatamleh Hazem |
| author_facet |
Hatamleh Hazem |
| author_sort |
Hatamleh Hazem |
| title |
Fast rerouting method in MPLS networks in case of failures |
| title_short |
Fast rerouting method in MPLS networks in case of failures |
| title_full |
Fast rerouting method in MPLS networks in case of failures |
| title_fullStr |
Fast rerouting method in MPLS networks in case of failures |
| title_full_unstemmed |
Fast rerouting method in MPLS networks in case of failures |
| title_sort |
fast rerouting method in mpls networks in case of failures |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| publishDate |
2012 |
| topic_facet |
Проблемно і функціонально орієнтовані комп’ютерні системи та мережі |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50197 |
| citation_txt |
Fast rerouting method in MPLS networks in case of failures / Hatamleh Hazem // Систем. дослідж. та інформ. технології. — 2012. — № 4. — С. 74-79. — Бібліогр.: 3 назв. — англ. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT hatamlehhazem fastreroutingmethodinmplsnetworksincaseoffailures AT hatamlehhazem švidkijalgoritmremaršrutizacíívmerežahíztehnologíêûmplsvumovahdíívídmov AT hatamlehhazem bystryjalgoritmremaršrutizaciivsetâhstehnologiejmplsvusloviâhotkazov |
| first_indexed |
2025-11-24T03:28:24Z |
| last_indexed |
2025-11-24T03:28:24Z |
| _version_ |
1849640777583427584 |
| fulltext |
© Hatamleh Hazem, 2012
74 ISSN 1681–6048 System Research & Information Technologies, 2012, № 4
TIДC
ПРОБЛЕМНО І ФУНКЦІОНАЛЬНО
ОРІЄНТОВАНІ КОМП’ЮТЕРНІ СИСТЕМИ ТА
МЕРЕЖІ
УДК 681.324
FAST REROUTING METHOD IN MPLS NETWORKS
IN CASE OF FAILURES
HAZEM HATAMLEH
The problem of nonlinearity identification in experimental data is considered with
application of appropriate statistical tests. An analysis of known statistical nonlinearity
test is presented that is based on Fisher relation, and a new simplified test is pro-
posed that can be used in conditions of incomplete experimental or statistical data.
The empirical statistical nonlinearity criterion is computed on the basis of existence
of a link between the values of respective cumulative sum and sample based stan-
dard deviation. It was empirically established that there exists a close link between
the proposed and existing tests in the sense of similarity of final testing results. To
find the critical values of statistics that are necessary for statistical decision making
with the use of the simplified test appropriate computational experiments have been
fulfilled. It has also been established that the test proposed can be used successfully
in conditions of complete and incomplete experimental data. The practical applica-
tion of the test proposed to actual data proved the similarity of results obtained with
various approaches.
INTRODUCTION
Rapid growth of real-time traffic, which is transmitted via IP networks, sets not
only high demands to a quality of service, but also to network survivability. Cur-
rently, the degree of survivability in the Internet is defined only as ability finding
and installing an alternative routes in case of crash. Today MPLS is becoming
a key technology of transmission in the core network. Networks with MPLS tech-
nology — technology oriented on connections, are even more sensitive to failure.
Therefore, the development of methods of traffic protection from failures in a ser-
vice is an important task.
The goal of this paper is to develop a fast rerouting algorithm to protect traf-
fic that would provide the best use of bandwidth and performance requirements to
a quality of service (QoS).
FAST REROUTING METHOD
In networks with MPLS technology three approaches to a problem of traffic pro-
tection from failures to service one of label switched route are used.
The main point of method of global recovery (global protection) is that when
denial occurs in result of router or communication channel breakdown, the router
Fast rerouting method in mpls networks in case of failures
Системні дослідження та інформаційні технології, 2012, № 4 75
which finds failure, sends RSVP-message to a border router of region, which cal-
culates new routes for traffic, which was transmitted through the channels or
node, which failed, and redirects traffic to a new route.
The main point of method of global security (global protection) is that re-
serve routes on which traffic will be routed in the event of failure are calculated
and determined simultaneously with the main routes. When the failure is detected,
a border router immediately begins to redirect traffic to a reserve route.
The idea of fast rerouting method, which is a method of local protection, is
shown in Fig. 1.
In Fig. 1 T1 is the main label-switched (LS) route, by which traffic is passed
from router R2 to R6, T2 — the main LS-route, by which the traffic is passed
from router R7 to R9.
Let the router R4 has failed. In this case, router R3, through which routes T1
and T2 pass, reveals the lack of communication through the path R1-R4. The
router R3 finds a new route for all flows that follow through that communication
channels and establish a tunnel B1: R3-R10-R11-R5 and redirect all traffic
through that tunnel. Traffic rerouting along this tunnel was performed to add one
more label to a package with a stack labels. When a packet reaches to a node R5
this label is removed from the stack and a packet follow through the main route.
REQUIREMENTS FOR NETWORK RECOVERY METHODS
Evaluation of the recovery mechanisms of the network requires consideration of
several parameters: recovery time, size of network, bandwidth and quality of ser-
vice parameters use, etc.
Obviously, the recovery time of the global recovery method will be the
largest, because it contains failures detection time, time of failure transmission to
the border router, the calculation time and a new route establishment time.
As for recovery time in a local protection mechanism, it consists only of
time we need to pass the message about the failure to the border router. And in
fast rerouting method traffic redirection begins as soon as the router, closest to the
area, where a failure has occurred, detect it.
An important parameter when security algorithms work is the size of net-
work, as the number of nodes in the network is growing, the load to routers is also
increasing, because it is associated with the need to store additional information
about the reserve routes and of the time of route calculation is also increasing.
IP Packet
Fig. 1. Fast rerouting
Hatamleh Hazem
ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 76
For the protection algorithms (global and local) the important is reservation
of additional bandwidth that is available when the network works without inter-
ruption. The mechanism of global protection sets a reserve route that duplicates
the main route. In contrast to this mechanism, the local rerouting method can es-
tablish reserve tunnels that duplicate only a part of the route. Therefore they can
be used by all routes that pass through an area which is protected by him. In addi-
tion in local protection is possible sharing of bandwidth of the tunnel. Tunnel B1
on the Fig. 1 can be used not only to protect the traffic that passes along the route
R3-R4-R5, but also to protect areas R3-R8-R5.
For some traffic types it is important to maintain a quality of service. During
the voice transmission isn’t allowed reducing of the service quality for a long pe-
riod of time. So it is important that recovery mechanisms ensure the quality of
service.
The problem of ensuring quality of service is much more complicated when
equipment breaks down and loses part of precious resources and solving of this
problem is more complicated than when the network is working normal. Obviously,
not all types of traffic can use reserve tunnels, as there would be significantly
increased bandwidth use, that leads to overloads. That’s why, only high-traffic
routes should be protected by the protection mechanisms. To the rest of traffic, we
use the method of the global recovery.
Also in connection with the problem of guaranteeing quality of service in
MPLS networks is the notion of priority service (preemption), the main point of
which is at times, when bandwidth isn’t enough, capacity of low priority traffic
may be directed to transmit high priority traffic. Thus, all the above requirements
should be considered when restoration algorithms are developed in case of net-
work failures.
ALGORITHM FOR FINDING RESERVE ROUTES
A distinctive feature of the proposed local rerouting algorithm from the other
similar algorithms is an algorithm for finding reserve tunnels, which considers the
quality of the service indicators and works in a decentralized manner.
MPLS network is given as a graph ),( EVG = , where },{ jvV = nj ,1= is
a set of nodes — MPLS routers, )},{( srE = is the set of communication chan-
nels. Each node in a network is characterized by the intensity of processing of the
incoming packets — }{ iλ each channel is characterized by its bandwidth ca-
pacity — }{ rsµ .
Subscribers connected to the router form the input flow, which is described
as a requirements matrix of input Poisson flows of the k-th class )()( k
ij
k hH = ,
nji ,1, = , Kk ,1= , where )(k
ijh — the intensity of input flow of k-th class trans-
ferred from node i to node .j
For each type of transferred data the following indicators of QoS should be
set: the average delay — )(
Delay
KT , )(
Delay
Kσ is delay variation (jitter), the probability
of packet loss — )(
Delay
KP and the following constraints for the desired levels of
QoS should be satisfied:
Fast rerouting method in mpls networks in case of failures
Системні дослідження та інформаційні технології, 2012, № 4 77
)(
Delay
)(
Average
KK TT ≤ ,
)(
Delay
)(
Average
KK PP ≤ ,
)(
Delay
)( K
T
k
T σσ ≤ . (1)
Expressions formulas for finding the average delay, delay variation and
packed loss probability were obtained in work [1].
Assume in time t router discovered that one of his neighbors can’t answer
and he needs to redirect traffic )(k
ijh to bypass the router, which failed. Assume
that at time t router knows network status, that is, the loading of channels:
)}({)( )( tt k
rsρρ = . The loading of the channel is the ratio of volume of traffic to the
bandwidth.
1. Find conditional metrics by the formula, which is obtained in work [2]:
)()()()()(
tk
rsktl k
rs ρρ = . (2)
2. By the matrix we find the shortest path given the fact that the channels
have sufficient bandwidth capacity:
)(
),(
})1{(min
min
k
ijrsrs
sr
h
ij
>−
∈
µρ
π
. (3)
If the algorithm does not find ways, then it generates denial to service as the
network is unable to transfer this amount of data in a given time. Otherwise, pro-
ceed to step 3.
3. Distribute this flow on the found path.
4. Check of constraints (1) fulfillment. When they are fulfilled, the router es-
tablishes a LS-path, and starts the data transfer. In a different way, proceed to step
5 and try to redistribute the flows that are passing through this router.
5. Repeat steps 1–3 for finding distribution of the flows ][ )()( k
rs
k vV = , using
at the step 1 conditional metrics:
)1(
)(
)()(
+tF
k
rs ktl (4)
6. Check the condition of possible optimization of the flow distribution
:)1( +tF
∑∑
∈∈
>
Esr
rs
k
rs
Esr
rs
k
rs kvlkfl
),(
)(
),(
)( )()( . (5)
If this condition is true, then go to step 8, otherwise STOP — problem is un-
solvable at the given input parameters.
7. Find the first requirement ),( 1ji , for which the inequality (6) is valid
∑∑
∈∈
>
Esr
ij
rs
k
rs
Esr
ij
rs
k
rs kvlkfl
),(
)(
),(
)( )()( 11 , (6)
where
1ijπ — path of the requirement transmission ),( 1ji , that is used in the cur-
rent distribution ,)1( +tF min
1ijπ is the shortest path in the metrics )()( tl k
rs . The
Hatamleh Hazem
ISSN 1681–6048 System Research & Information Technologies, 2012, № 4 78
flow of the requirement packets ),( 1ji redirecting from the path min
1ijπ to path
1ijπ and find a new flow.
8. Check the performance of the conditions (1). If they are true, then it’s the
end of the second stage, else go back to step 7, choose the next request that satis-
fies the condition (1).
In a result of the algorithm performance we obtaina new route and distribu-
tion of flow of class k, which satisfies constraints (1).
RESULTS OF EXPERIMENTS
For experimental research the corresponding algorithm was implemented as part
of software kit «MPLS Net Builder». The work of decentralized local rerouting
algorithm was compared with the work of the centralized global security algo-
rithm.
Algorithms of routes protection from overloading use a significant part of
network resources, that’s not used during normal work of the network. That’s
why, an important indicator
of the work of algorithm is
the number of reserve routes
that are set to protect the
major routes from failures.
In Fig. 2 dependence of
number of the reserve tun-
nels from network size is
shown. From the Fig. 2 we
may see that for local re-
routing algorithm this de-
pendence is linear and
creates a smaller number of reserve tunnels. This means that in contrast to the
global protection algorithm, where a reserve route is created for each primary
route, in the local rerouting algorithm one reserve tunnel is created to protect each
part of the route, but due to the assumption that at in the same time the failure of
only one channel or hub may happen the sharing use of tunnels by different routes
enables total number of tunnels to be smaller.
A similar effect has sharing of throughput capacity of channels on the over-
overall throughput capacity,
that use routes. In Fig. 3 the
total bandwidth capacity
used by reserve tunnels is
shown. As the bandwidth
capacity of the tunnel in the
local rerouting algorithm is
used by the various routes,
the reserve local tunnel can
protect immediately several
different parts of the net-
work. As we can see from Fig. 3. Compatible bandwidth usage
Fig. 2. The number of reserve tunnels
Fast rerouting method in mpls networks in case of failures
Системні дослідження та інформаційні технології, 2012, № 4 79
from the presented dependence at the Fig. 2, the greater is the number of nodes in
the network, the more effective is usage of local rerouting.
Certainly, an important aspect of work of security algorithms is their ability
to maintain high quality of
service in the periods of
network equipment failures.
In Fig. 4 the curves of the
average packet delay time
with high requirements to
quality of service during
normal work of the network
equipment and in the periods
of failures when algorithm
of local rerouting or global
defense is used. As we can
see when high-priority traf-
fic is routed through a reserve route average time of delay increases, which is
evident because reserve routes aren’t optimal when compared with the main
routes. But we also can see, that due to the fact that at local rerouting total delay
time increases only by the value of delay needed to bypass a single channel or
node of main route that failed, the average time of delay increase in the local re-
routing algorithm is less than in the global protect algorithm.
CONCLUSIONS
As experimental investigations show, via program implementation the suggested
algorithm has achieved the very high degree of utility of bandwidth capacity
when compared with the centralized control method of setting paths, namely the
indicator of bandwidth capacity saving reaches the value of 5. This means that for
centralized control of reserve paths we need 5 times more bandwidth capacity
than for decentralized local rerouting algorithm. And additionally, all the re-
quirements to the level of quality of service during transfer by the new routes are
assured. The only disadvantage of this method is that the inner routers of MPLS
area may not have sufficient computational capacity, in contrast to the border
routers that perform global protection.
REFERENCES
1. Zaichenko Y.P., Ahmed A.M. Sharadka. Task distribution of flows of different
classes in the networks with MPLS technology // Journal of NTU «KPI». Avg.
Informatics, Management and Computing equipment. — 2005. — № 43. —
P. 113–123.
2. Zaichenko Y.P., Lavrinchuk O.M. Decentralized algorithm of distribution of traffic
flows in MPLS networks based on the state of channels and parameters QoS //
Journal Cherkasy State Technological University. Avg. Technical Science. —
2010. — № 2. — P. 17–27.
3. Bruce S. Davie, Adrian Farrel. MPLS: next steps. — San Francisco: Morgan Kauf-
mann, 2008. — 432 p.
Received 25.05.2011
From the Editorial Board: the article corresponds completely to submitted manuscript
Fig. 4. The average delay time of packet transfer
0,1
Failure
|