Dynamic Routing with Security Measures

Jagdish kapadnis
LNCT indore, (MP)
India.
[email protected]

Various threats over the Internet, including

Abstract: - Security has become one of the eavesdropping, spoofing, session hijacking,
major issues for data communication over etc. Among many well-known designs for
wired and wireless networks. Different from cryptography based systems, the IP Security
the past work on the designs of (IPSec) and the Secure Socket Layer (SSL)
cryptography algorithms and system are popularly supported and implemented in
infrastructures, we will propose a dynamic many systems and platforms. Although
routing algorithm that could randomize IPSec and SSL do greatly improve the
delivery paths for data transmission. The security level for data transmission, they
algorithm is easy to implement and unavoidably introduce substantial overheads
compatible with popular routing protocols, especially on gateway/host performance and
such as the Routing information Protocol in effective network bandwidth. For example,
wired networks and Destination-Sequenced the data transmission overhead is 5
Distance Vector protocol in wireless cycles/byte over an Intel Pentium II with the
networks, without introducing extra control Linux IP stack alone, and the overhead
Messages. An analytic study on the increases to 58 cycles/byte when Advanced
proposed algorithm is presented, and a series Encryption Standard (AES) is adopted for
of simulation experiments are conducted to encryption/decryption for IPSec
verify the analytic results and to show the
capability of the proposed algorithm.
Another alternative for security-
enhanced data transmission is to
Index Terms—Security-enhanced data dynamically route packets between each
transmission, dynamic routing, RIP, DSDV. source and its destination so that the chance
for system break-in, due to successful
1 INTRODUCTION interception of consecutive packets for a
session, is slim. The intention of security-
IN the past decades, various security enhanced routing is different from the
enhanced measures have been proposed to adopting of multiple paths between a source
improve the security of data transmission and a destination to increase the throughput
over public networks. Existing work on of data transmission In particular, Lou et a1
security-enhanced data transmission proposed a secure routing protocol to
includes the designs of cryptography improve the security of end-to-end data
algorithms and system infrastructures and transmission based on multiple path
security-enhanced routing methods. Their deliveries. The set of multiple paths between
common objectives are often to defeat each source and its destination is determined
in an online fashion, and extra control
message exchanging is needed. Bo hacek et
al. Proposed a secure stochastic routing wireless networks over existing
mechanism to improve routing security. infrastructures. These protocols shall not
Similar to the work proposed by Lou et al. a increase the number of control messages if
set of paths is discovered for each source the proposed algorithm is adopted.
and its destination in an online fashion based
on message flooding. Thus, a mass of
control messages is needed. Yang and 2 PROBLEM STATEMENTS
Papavassiliou explored the trading of the The objective of this work is to explore a
security level and the traffic dispersion. security-enhanced dynamic routing
They proposed a traffic dispersion scheme to algorithm based on distributed routing
reduce the probability of eavesdropped information widely supported in existing
information along the used paths provided networks. In general, routing protocols over
that the set of data delivery paths is networks could be classified roughly into
discovered in advance. Although excellent two kinds: distance-vector algorithms and
research results have been proposed for link-state algorithms. Distance-vector
security-enhanced dynamic routing, many of algorithms rely on the exchanging of
them rely on the discovery of multiple paths distance information among neighboring
either in an online or offline fashion. For nodes for the seeking of routing paths.
those online path searching approaches, the Examples of distance-vector-based routing
discovery of multiple paths involves a algorithms include RIP and DSDV. Link-
significant number of control signals over state algorithms used in the Open Shortest
the Internet. On the other hand, the Path First protocol are for global routing in
discovery of paths in an offline fashion which the network topology is known by all
might not be suitable to networks with a nodes. Our goal is to propose a distance-
dynamic changing configuration. Therefore, vector-based algorithm for dynamic routing
we will propose a dynamic routing to improve the security of data transmission.
algorithm to provide security enhanced data Before we proceed with further discussions,
delivery without introducing any extra our problem and system model shall be
control messages. defined.
A network could be modeled as a
graph G = (N,L) where N is a set of routers
The objective of this work is to (also referred to as nodes) in the network,
explore a security enhanced dynamic routing and L is a set of links that connect adjacent
algorithm based on distributed routing routers in the network. A path p from a node
information widely supported in existing s (referred to as a source node) to another
wired and wireless networks. We aim at the node t (referred to as a destination node) is a
randomization of delivery paths for data set of links (N1,N2)(N2,N3)……..(Ni,Nj+1)
transmission to provide considerably small
path similarity (i.e., the number of common

where s=N1,Ni+1=t, Nj N and (Nj,Nj+1)
links between two delivery paths) of two for 1<= j <=i. Let Ps,t denote the set of all
consecutive transmitted packets. The potential paths between a source node s and
proposed algorithm should be easy to a destination node t. Note that the number of
implement and compatible with popular paths in Ps,t could be an exponential
routing protocols, such as the Routing function of the number of routers in the
Information Protocol (RIP) for wired network, and we should not derive Ps;t in
networks and Destination-Sequenced practice for routing or analysis.
Distance Vector (DSDV) protocol for
Definition 1 (path similarity). Given two distance information exchanged among
paths pi and pj, the path similarity Sim(pi; neighboring nodes for the seeking of routing
pj) for pi and pj is defined as the number of paths. In many distance-vector-based
common links between pi and pj: implementations, e.g., those based on RIP,
Sim(pi; pj)=[{(Nx,Ny)|(Nx;Ny )Nx;Ny) each node Ni maintains a routing table (see
 pi (Nx;Ny) pj }] Table 1a) in which each entry is associated
Where Nx and Ny are two nodes in the with a tuple(t;WNit, Nexthop), where t,
network. WNi;t, and Nexthop denote some unique
destination node, an estimated minimal
The path similarity between two paths is cost to send a packet to t, and the next node
computed based on the algorithm of along the minimal-cost path to the
Levenshtein distance destination node, respectively.

Definition 2 (the expected value of path With the objective of this work in the
similarity for any two consecutive randomization of routing paths, the routing
delivered packets). Given a source node s table shown in Table 1a is extended to
and a destination node t, the expected value accommodate our security-enhanced
of path similarity of any two consecutive dynamic routing algorithm. In the extended
delivered packets is defined as follows: routing table (see Table 1b), we propose to
associate each entry with a tuple (t;WNit;
❑
CNt ;HNit). CNit is a set of node candidates
E[Sims,t]= ∑ ❑sim(pi,pj).prob(pi/pj for the Nexthop . where one of the Nexthop
∀ pi, pj Pst  
candidates that have the minimal cost is
).prob(pi).
marked. HNit , a set of tuples, records the
where Ps,t is the set of all possible history for packet deliveries through the
node Ni to the destination node t. Each tuple
transmission paths between a source node s
(Nj; hNj )in HNit is used to represent that Ni
and a destination node t. Prob(pj|pi) is the previously used the node hNj as the nexthop
conditional probability of using pj for to forward the packet from the source node
delivering the current packet, given that pi is Nj to the destination node t. Let Nbri and
used for the previous packet. Prob(pi) is the wNi;Nj denote the set of neighboring nodes
probability of using pi for delivering the for a node Ni and the cost in the delivery of
previous packet. a packet between Ni and a neighboring node
Nj, respectively. Each node Ni also
The purpose of this research is to propose a Maintains an array in which each entry
dynamic routing algorithm to improve the corresponds to a neighboring node Nj  Nbri
security of data transmission. and contains the cost wNi,Nj for a packet
delivery.
3 SECURITY-ENHANCED DYNAMIC
ROUTING The proposed algorithm achieves
considerably small path similarity for packet
3.1 Notations and Data Structures deliveries between a source node and the
The objective of this section is to propose a corresponding destination node. However,
distance-vector based algorithm for dynamic the total space requirement would increase
routing to improve the security of data to store some extra routing information. The
transmission. We propose to rely on existing size of a routing table depends on the
topology and the node number of a network Consider the delivery of a packet with the
under discussions. In the worst case, we destination t at a node Ni. In order to
have a fully connected network. For each minimize the probability that packets are
entry in the routing table shown in Table 1b, eavesdropped over a specific link, a
the randomization process for packet deliveries
shown in Procedure 1 is adopted. In this
process, the previous nexthop hs (defined
in HNit of Table 1b) for the source node s is
identified in the first step of the process (line
1). Then, the process randomly picks up a
neighboring node in CNit excluding hs
as the nexthop for the current packet
transmission. The exclusion of hs for the
nexthop selection avoids transmitting two
consecutive packets in the same link, and the
randomized pickup prevents attackers from
easily predicting routing paths for the
coming transmitted packets.
Procedure 1 RANDOMIZEDSELECTOR
Additional spaces required for recording the (s, t, pkt)
set of node candidates (as shown in the third 1: Let hs be the used nexthop for the
column of Table 1b) and for recording the Previous packet delivery for the source
routing history (as shown in the fourth Node s.
column of Table 1b) are O(|N|). Because 2: if hs  CNi t then
there are |N| destination nodes at most in 3: if |CNit | > 1 then
each routing table, the additionally required 4: Randomly choose a node x from {CNit _
spaces for the entire routing table for one hs} as a nexthop, and send the packet pkt
node are O(|N|2) Since the provided to the node x.
distributed dynamic routing algorithm 5: hs <-x, and update the routing table of Ni.
(DDRA) is a distance-vector-based routing 6: else
protocol for intra domain systems, the 7: Send the packet pkt to hs.
number of nodes is limited, and the network 8: end if
topology is hardly fully connected. Hence, 9: else
the increase of the total space requirement is 10: Randomly choose a node y from CNit as
considerably small. However, the impact of a nexthop and send the packet pkt to the
the space requirement on the search time Node y.
will be analyzed in the following section. 11: hs<- y, and update the routing table of
Ni.
3.2 A Distributed Dynamic Routing 12: end if
Algorithm
The DDRA proposed in this paper consists The number of entries in the history record
of two parts: for packet deliveries to destination nodes is |
1) A randomization process for packet N| in the worst case. In order to efficiently
deliveries and look up the history record for a destination
2) Maintenance of the extended routing node, we maintain the history record for
table. each node in a hash table. Before the current
packet is sent to its destination node, we 2: Add the entry (t(wNi,Nj+WNj;t); CNit
must randomly pick up a neighboring node ={Nj};HNt=. ø
excluding the used node for the previous 3: else if (wNi;Nj +WNj;t)<WNi;t then
packet. Once a neighboring node is selected, 4: CNit<-{Nj} and Nj is marked as the
by the hash table, we need O(1) to determine Minimal-cost nexthop.
whether the selected neighboring 5: WNi ;t <-(wNi;Nj +WNj;t)
node for the current packet is the same as 6: for each node Nk Nbri except Nj do
the one used by the previous packet. 7: if WNk;t <WNi;t then
Therefore, the time complexity of searching 8: CNi t CNi t U{Nk}
a proper neighboring node is O(1). 9: end if
10: end for
3.2.2 Routing Table Maintenance 11: Send (t,WNi;t)to each neighboring node
Let every node in the network be given a Nk  Nbri.
routing table and a link table. We assume 12: else if (wNi,Nj +WNj,t)>WNi;t then
that the link table of each node is 13: if (Nj  CNit ) then
constructed by an existing link discovery 14: if Nj was marked as the minimal-cost
protocol, such as the Hello protocol in. On nexthop then
the other hand, the construction and 15: WNi,t<-MINNkNbri (wNi,Nk +WNk,t)
maintenance of routing tables are revised 16: CNit
based on the well-known Bellman-Ford 17: for each node Nk  Nbri do
algorithm and described as follows: 18: if WNk;t <WNi;t then
19: CNi<- CNi t U{Nk}
Initially, the routing table of each node (e.g., 20: end if
the node Ni) consists of entries 21: end for
{(Nj,WNi,Nj, CNiNj={Nj},HNiNj=ø)}, where 22: Send (t,WNi.;t) to each neighboring node
Nj  Nbri and WNi,Nj =wNi,Nj . By exchanging Nk Nbri.
distance vectors between neighboring nodes, 23: else if WNj,t >WNi.t then
the routing table of Ni is accordingly 24: CNi t <-CNit U{Nj}
updated. Note that the exchanging for 25: end if
distance vectors among neighboring nodes 26: else if (Nj  CNit ) ^ (WNj,t <WNi,,t)
can be based on a predefined interval. The then
exchanging can also be triggered by the 27: CNit<- CNi,t –{Nj}
change of link cost or the failure of the 28: end if
link/node. In this paper, we consider cases 29: end if
when Ni receives a distance vector from a
neighboring node Nj. Each element of a First, for the elements that do not exist in the
distance vector received from a neighboring routing table, new entries for the
node Nj includes a destination node t and a corresponding destination nodes will be
delivery cost WNj,t from the node Nj to the inserted (lines 1 and 2). Otherwise, wNi;Nj
destination node t. The algorithm for the +WNj;t is compared with WNi ;t saved in the
maintenance of the routing table of Ni is routing table of Ni, and the following four
shown in Procedure 2, and will be described cases are considered:
below. 1. (wNi,Nj +WNj;t )<WNi,t The corresponding
Procedure 2 DVPROCESS(t;WNj;t) minimal cost is updated in the routing table,
1: if the destination node t is not in the and Nj is marked as the minimal-cost
routing table then nexthop. Any neighboring node Nk which
has an estimated packet delivery cost from developed for the proposed algorithm and
Nk to t (i.e., WNk;t) no more than was verified against the experimental
(wNi;Nj+WNj;t) joins the candidate set CNit . results. A series of simulation experiments
It is to aggressively include more candidates were conducted to show the capability of the
for the Nexthop to t with reasonable packet proposed algorithm, for which we have very
delivery cost (i.e., WNk;t <WNi;t). Compared to encouraging results. We must point out that
the Bellman-Ford algorithm, more than one the proposed algorithm is completely
neighboring node can be selected as the orthogonal to the work based on the designs
nexthop candidates in this step (lines 6-10) of cryptography algorithms and system
to accommodate multiple packet-delivery infrastructures. Our security enhanced
paths to the destination node t. Also, the dynamic routing could be used with
selection policy described above can prevent cryptography- based system designs to
the algorithm from generating the routing further improve the security of data
loops, and the proof will be shown in transmission over networks.
Theorem 1.
2. (wNi;Nj +WNj;tÞ)>WNi ;t, and Nj is in the set REFERENCES
CNit of nexthop candidates (lines 13-25). [1] Chin-Fu Kuo, “Dynamic routing with
Based on whether Nj is marked as the security consideration” IEEE Network, 2009
minimal-cost nexthop in the routing table of [2] G. Apostolopoulos, V. Peris, P. Pradhan,
Ni, the following two cases are further and D. Saha, “Securing Electronic
considered. . Nj was marked as the minimal- Commerce: Reducing the SSL Overhead,”
cost Nexthop (lines 14-22). For all IEEE Network, 2000.
neighboring nodes of Ni, the minimal cost to [3] S. Bohacek, J.P. Hespanha, K. Obraczka,
the destination node t is recomputed J. Lee, and C. Lim, “Enhancing Security via
according to the distance vectors received Stochastic Routing,” Proc. 11th Int’l Conf.
from the neighboring nodes. Also, the Computer Comm. and Networks (ICCCN),
nexthop candidates for the destination node t 2002.
are reselected, and the selection policy is the [4] D. Collins, Carrier Grade Voice over IP.
same as lines 7-9 for Case 1. . Nj was not McGraw-Hill, 2003.
marked as the minimal-cost Nexthop (lines [5] T.H. Cormen, C.E. Leiserson, and R.L.
23 and 24). If WNj;t >WNi;t, Nj is removed Rivest, Introduction to Algorithms. MIT
from CNi t Press, 1990.
. [6] M. Faloutsos, P. Faloutsos, and C.
3. (wNi;Nj+WNj;t )>WNi;t, and Nj is not in the set Faloutsos, “On Power-Law Relationships of
CNit of Nexthop candidates (lines 26 and the Internet Topology,” Proc. ACM
27). If WNj;t<WNi ;t,Nj is inserted into CNit SIGCOMM’99, pp. 251-262, 1999.
4. Otherwise, nothing is done. [8] I. Gojmerac, T. Ziegler, F. Ricciato, and
4 CONCLUSION P. Reichl, “Adaptive
This paper has proposed a security-enhanced Multipath Routing for Dynamic Traffic
dynamic routing algorithm based on Engineering,” Proc. IEEE
distributed routing information widely Global Telecommunications Conf.
supported in existing networks. The (GLOBECOM), 2003.
proposed algorithm is easy to implement and [9] C. Hopps, Analysis of an Equal-Cost
compatible with popular routing protocols, Multi-Path Algorithm, Request for
such as RIP and DSDV, over existing comments (RFC 2992), Nov. 2000.
infrastructures. An analytic study was