03-05-2011, 11:31 AM
Abstract
Security has become one of the major issues for data communication over wired and wireless networks. Different from thepast work on the designs of cryptography algorithms and system infrastructures, we will propose a dynamic routing algorithm that couldrandomize delivery paths for data transmission. The algorithm is easy to implement and compatible with popular routing protocols,such as the Routing Information Protocol in wired networks and Destination-Sequenced Distance Vector protocol in wireless networks,without introducing extra control messages. An analytic study on the proposed algorithm is presented, and a series of simulationexperiments are conducted to verify the analytic results and to show the capability of the proposed algorithm.Index Terms—Security-enhanced data transmission, dynamic routing, RIP, DSDV
INTRODUCTION
IN the past decades, various security-enhanced measureshave been proposed to improve the security of datatransmission over public networks. Existing work onsecurity-enhanced data transmission includes the designsof cryptography algorithms and system infrastructures andsecurity-enhanced routing methods. Their common objectivesare often to defeat various threats over the Internet,including eavesdropping, spoofing, session hijacking, etc.Among many well-known designs for cryptographybasedsystems, the IP Security (IPSec) [23] and the SecureSocket Layer (SSL) [21] are popularly supported andimplemented in many systems and platforms. AlthoughIPSec and SSL do greatly improve the security level for datatransmission, they unavoidably introduce substantial overheads[1], [7], [13], especially on gateway/host performanceand effective network bandwidth. For example, the datatransmission overhead is 5 cycles/byte over an IntelPentium II with the Linux IP stack alone, and the overheadincreases to 58 cycles/byte when Advanced EncryptionStandard (AES) [10] is adopted for encryption/decryptionfor IPSec [7].Another alternative for security-enhanced data transmissionis to dynamically route packets between each sourceand its destination so that the chance for system break-in,due to successful interception of consecutive packets for asession, is slim. The intention of security-enhanced routingis different from the adopting of multiple paths between asource and a destination to increase the throughput of datatransmission (see, e.g., [8] and [9]). In particular, Lou et al.[14], [15] proposed a secure routing protocol to improve thesecurity of end-to-end data transmission based on multiplepathdeliveries. The set of multiple paths between eachsource and its destination is determined in an onlinefashion, and extra control message exchanging is needed.Bohacek et al. [2] proposed a secure stochastic routingmechanism to improve routing security. Similar to the workproposed by Lou et al. [14], [15], a set of paths is discoveredfor each source and its destination in an online fashionbased on message flooding. Thus, a mass of controlmessages is needed. Yang and Papavassiliou [25] exploredthe trading of the security level and the traffic dispersion.They proposed a traffic dispersion scheme to reduce theprobability of eavesdropped information along the usedpaths provided that the set of data delivery paths isdiscovered in advance. Although excellent research resultshave been proposed for security-enhanced dynamic routing,many of them rely on the discovery of multiple pathseither in an online or offline fashion. For those online pathsearchingapproaches, the discovery of multiple pathsinvolves a significant number of control signals over theInternet. On the other hand, the discovery of paths in anoffline fashion might not be suitable to networks with adynamic changing configuration. Therefore, we will proposea dynamic routing algorithm to provide securityenhanceddata delivery without introducing any extracontrol messages.The objective of this work is to explore a securityenhanceddynamic routing algorithm based on distributedrouting information widely supported in existing wiredand wireless networks. We aim at the randomization ofdelivery paths for data transmission to provide considerablysmall path similarity (i.e., the number of common linksbetween two delivery paths) of two consecutive transmittedpackets. The proposed algorithm should be easy toimplement and compatible with popular routing protocols,such as the Routing Information Protocol (RIP) for wirednetworks [16] and Destination-Sequenced Distance Vector(DSDV) protocol for wireless networks [20], over existinginfrastructures. These protocols shall not increase thenumber of control messages if the proposed. An analytic study will be presented for theproposed routing algorithm, and a series of simulationstudy will be conducted to verify the analytic results and toshow the capability of the proposed algorithm.The rest of this paper is organized as follows: Section 2formally defines the problem under investigation. InSection 3, we propose a security-enhanced dynamic routingalgorithm to randomize the data delivery paths. An analyticstudy on the proposed algorithm is conducted. Section 4summarizes our experimental results to demonstrate thecapability of the proposed algorithm. Section 5 is theconclusion.
2 PROBLEM STATEMENT
The objective of this work is to explore a security-enhanceddynamic routing algorithm based on distributed routinginformation widely supported in existing networks. Ingeneral, routing protocols over networks could be classifiedroughly into two kinds: distance-vector algorithms andlink-state algorithms [11]. Distance-vector algorithms relyon the exchanging of distance information among neighboringnodes for the seeking of routing paths. Examples ofdistance-vector-based routing algorithms include RIP andDSDV. Link-state algorithms used in the Open ShortestPath First protocol [19] are for global routing in which thenetwork topology is known by all nodes. Our goal is topropose a distance-vector-based algorithm for dynamicrouting to improve the security of data transmission. Beforewe proceed with further discussions, our problem andsystem model shall be defined.A network could be modeled as a graph G ¼ ðN;LÞ,where N is a set of routers (also referred to as nodes) in thenetwork, and L is a set of links that connect adjacent routersin the network. A path p from a node s (referred to as asource node) to another node t (referred to as a destinationnode) is a set of links ðN1;N2ÞðN2;N3Þ _ _ _ ðNi;Niþ1Þ, wheres ¼ N1, Niþ1 ¼ t, Nj 2 N, and ðNj;Njþ1Þ 2 L for 1 _ j _ i.Let Ps;t denote the set of all potential paths between a sourcenode s and a destination node t. Note that the number ofpaths in Ps;t could be an exponential function of the numberof routers in the network, and we should not derive Ps;t inpractice for routing or analysis.Definition 1 (path similarity). Given two paths pi and pj, thepath similarity Simðpi; pjÞ for pi and pj is defined as thenumber of common links between pi and pj:Simðpi; pjÞ ¼ ðNx;NyÞjðNx;NyÞ 2 pi ^ ðNx;NyÞ 2 pj _ _ ____;where Nx and Ny are two nodes in the network.The path similarity between two paths is computedbased on the algorithm of Levenshtein distance [12].Definition 2 (the expected value of path similarity for anytwo consecutive delivered packets). Given a source node sand a destination node t, the expected value of path similarityof any two consecutive delivered packets is defined as follows:E½Sims;t_ ¼ X8pi;pj2Ps;tSimðpi; pjÞ _ ProbðpjjpiÞ _ ProbðpiÞ;where Ps;t is the set of all possible transmission paths betweena source node s and a destination node t. ProbðpjjpiÞ is theconditional probability of using pj for delivering the currentpacket, given that pi is used for the previous packet. ProbðpiÞis the probability of using pi for delivering the previouspacket.The purpose of this research is to propose a dynamicrouting algorithm to improve the security of data transmission.We define the eavesdropping avoidance problem asfollows:Given a graph for a network under discussion, a source node,and a destination node, the problem is to minimize the pathsimilarity without introducing any extra control messages, andthus to reduce the probability of eavesdropping consecutivepackets over a specific link.
3 SECURITY-ENHANCED DYNAMIC ROUTING
3.1 Notations and Data Structures
The objective of this section is to propose a distance-vectorbasedalgorithm for dynamic routing to improve thesecurity of data transmission. We propose to rely on existingdistance information exchanged among neighboring nodes(referred to as routers as well in this paper) for the seeking ofrouting paths. In many distance-vector-based implementations,e.g., those based on RIP, each node Ni maintains arouting table (see Table 1a) in which each entry is associatedwith a tuple ðt;WNi ;t;NexthopÞ, where t, WNi;t, and Nexthopdenote some unique destination node, an estimated minimalcost to send a packet to t, and the next node along theminimal-cost path to the destination node, respectively.With the objective of this work in the randomization ofrouting paths, the routing table shown in Table 1a isextended to accommodate our security-enhanced dynamicrouting algorithm. In the extended routing table (seeTable 1b), we propose to associate each entry with a tupleðt;WNi ;t; CNit ;HNit Þ. CNit is a set of node candidates for thenexthop (note that the candidate selection will be elaboratedin Procedure 2 of Section 3.2), where one of thenexthop candidates that have the minimal cost is marked.HNit , a set of tuples, records the history for packet deliveriesthrough the node Ni to the destination node t. Each tupleðNj; hNj Þ in HNit is used to represent that Ni previouslyused the node hNj as the nexthop to forward the packetfrom the source node Nj to the destination node t. Let Nbriand wNi;Nj denote the set of neighboring nodes for anode Ni and the cost in the delivery of a packet between Niand a neighboring node Nj, respectively. Each node Ni alsomaintains an array (referred to as a page link table) in which eachentry corresponds to a neighboring node Nj 2 Nbri andcontains the cost wNi;Nj for a packet delivery.
Download full report
http://ntur.lib.ntu.edu.tw/bitstream/246...8/1/15.pdf
Security has become one of the major issues for data communication over wired and wireless networks. Different from thepast work on the designs of cryptography algorithms and system infrastructures, we will propose a dynamic routing algorithm that couldrandomize delivery paths for data transmission. The algorithm is easy to implement and compatible with popular routing protocols,such as the Routing Information Protocol in wired networks and Destination-Sequenced Distance Vector protocol in wireless networks,without introducing extra control messages. An analytic study on the proposed algorithm is presented, and a series of simulationexperiments are conducted to verify the analytic results and to show the capability of the proposed algorithm.Index Terms—Security-enhanced data transmission, dynamic routing, RIP, DSDV
INTRODUCTION
IN the past decades, various security-enhanced measureshave been proposed to improve the security of datatransmission over public networks. Existing work onsecurity-enhanced data transmission includes the designsof cryptography algorithms and system infrastructures andsecurity-enhanced routing methods. Their common objectivesare often to defeat various threats over the Internet,including eavesdropping, spoofing, session hijacking, etc.Among many well-known designs for cryptographybasedsystems, the IP Security (IPSec) [23] and the SecureSocket Layer (SSL) [21] are popularly supported andimplemented in many systems and platforms. AlthoughIPSec and SSL do greatly improve the security level for datatransmission, they unavoidably introduce substantial overheads[1], [7], [13], especially on gateway/host performanceand effective network bandwidth. For example, the datatransmission overhead is 5 cycles/byte over an IntelPentium II with the Linux IP stack alone, and the overheadincreases to 58 cycles/byte when Advanced EncryptionStandard (AES) [10] is adopted for encryption/decryptionfor IPSec [7].Another alternative for security-enhanced data transmissionis to dynamically route packets between each sourceand its destination so that the chance for system break-in,due to successful interception of consecutive packets for asession, is slim. The intention of security-enhanced routingis different from the adopting of multiple paths between asource and a destination to increase the throughput of datatransmission (see, e.g., [8] and [9]). In particular, Lou et al.[14], [15] proposed a secure routing protocol to improve thesecurity of end-to-end data transmission based on multiplepathdeliveries. The set of multiple paths between eachsource and its destination is determined in an onlinefashion, and extra control message exchanging is needed.Bohacek et al. [2] proposed a secure stochastic routingmechanism to improve routing security. Similar to the workproposed by Lou et al. [14], [15], a set of paths is discoveredfor each source and its destination in an online fashionbased on message flooding. Thus, a mass of controlmessages is needed. Yang and Papavassiliou [25] exploredthe trading of the security level and the traffic dispersion.They proposed a traffic dispersion scheme to reduce theprobability of eavesdropped information along the usedpaths provided that the set of data delivery paths isdiscovered in advance. Although excellent research resultshave been proposed for security-enhanced dynamic routing,many of them rely on the discovery of multiple pathseither in an online or offline fashion. For those online pathsearchingapproaches, the discovery of multiple pathsinvolves a significant number of control signals over theInternet. On the other hand, the discovery of paths in anoffline fashion might not be suitable to networks with adynamic changing configuration. Therefore, we will proposea dynamic routing algorithm to provide securityenhanceddata delivery without introducing any extracontrol messages.The objective of this work is to explore a securityenhanceddynamic routing algorithm based on distributedrouting information widely supported in existing wiredand wireless networks. We aim at the randomization ofdelivery paths for data transmission to provide considerablysmall path similarity (i.e., the number of common linksbetween two delivery paths) of two consecutive transmittedpackets. The proposed algorithm should be easy toimplement and compatible with popular routing protocols,such as the Routing Information Protocol (RIP) for wirednetworks [16] and Destination-Sequenced Distance Vector(DSDV) protocol for wireless networks [20], over existinginfrastructures. These protocols shall not increase thenumber of control messages if the proposed. An analytic study will be presented for theproposed routing algorithm, and a series of simulationstudy will be conducted to verify the analytic results and toshow the capability of the proposed algorithm.The rest of this paper is organized as follows: Section 2formally defines the problem under investigation. InSection 3, we propose a security-enhanced dynamic routingalgorithm to randomize the data delivery paths. An analyticstudy on the proposed algorithm is conducted. Section 4summarizes our experimental results to demonstrate thecapability of the proposed algorithm. Section 5 is theconclusion.
2 PROBLEM STATEMENT
The objective of this work is to explore a security-enhanceddynamic routing algorithm based on distributed routinginformation widely supported in existing networks. Ingeneral, routing protocols over networks could be classifiedroughly into two kinds: distance-vector algorithms andlink-state algorithms [11]. Distance-vector algorithms relyon the exchanging of distance information among neighboringnodes for the seeking of routing paths. Examples ofdistance-vector-based routing algorithms include RIP andDSDV. Link-state algorithms used in the Open ShortestPath First protocol [19] are for global routing in which thenetwork topology is known by all nodes. Our goal is topropose a distance-vector-based algorithm for dynamicrouting to improve the security of data transmission. Beforewe proceed with further discussions, our problem andsystem model shall be defined.A network could be modeled as a graph G ¼ ðN;LÞ,where N is a set of routers (also referred to as nodes) in thenetwork, and L is a set of links that connect adjacent routersin the network. A path p from a node s (referred to as asource node) to another node t (referred to as a destinationnode) is a set of links ðN1;N2ÞðN2;N3Þ _ _ _ ðNi;Niþ1Þ, wheres ¼ N1, Niþ1 ¼ t, Nj 2 N, and ðNj;Njþ1Þ 2 L for 1 _ j _ i.Let Ps;t denote the set of all potential paths between a sourcenode s and a destination node t. Note that the number ofpaths in Ps;t could be an exponential function of the numberof routers in the network, and we should not derive Ps;t inpractice for routing or analysis.Definition 1 (path similarity). Given two paths pi and pj, thepath similarity Simðpi; pjÞ for pi and pj is defined as thenumber of common links between pi and pj:Simðpi; pjÞ ¼ ðNx;NyÞjðNx;NyÞ 2 pi ^ ðNx;NyÞ 2 pj _ _ ____;where Nx and Ny are two nodes in the network.The path similarity between two paths is computedbased on the algorithm of Levenshtein distance [12].Definition 2 (the expected value of path similarity for anytwo consecutive delivered packets). Given a source node sand a destination node t, the expected value of path similarityof any two consecutive delivered packets is defined as follows:E½Sims;t_ ¼ X8pi;pj2Ps;tSimðpi; pjÞ _ ProbðpjjpiÞ _ ProbðpiÞ;where Ps;t is the set of all possible transmission paths betweena source node s and a destination node t. ProbðpjjpiÞ is theconditional probability of using pj for delivering the currentpacket, given that pi is used for the previous packet. ProbðpiÞis the probability of using pi for delivering the previouspacket.The purpose of this research is to propose a dynamicrouting algorithm to improve the security of data transmission.We define the eavesdropping avoidance problem asfollows:Given a graph for a network under discussion, a source node,and a destination node, the problem is to minimize the pathsimilarity without introducing any extra control messages, andthus to reduce the probability of eavesdropping consecutivepackets over a specific link.
3 SECURITY-ENHANCED DYNAMIC ROUTING
3.1 Notations and Data Structures
The objective of this section is to propose a distance-vectorbasedalgorithm for dynamic routing to improve thesecurity of data transmission. We propose to rely on existingdistance information exchanged among neighboring nodes(referred to as routers as well in this paper) for the seeking ofrouting paths. In many distance-vector-based implementations,e.g., those based on RIP, each node Ni maintains arouting table (see Table 1a) in which each entry is associatedwith a tuple ðt;WNi ;t;NexthopÞ, where t, WNi;t, and Nexthopdenote some unique destination node, an estimated minimalcost to send a packet to t, and the next node along theminimal-cost path to the destination node, respectively.With the objective of this work in the randomization ofrouting paths, the routing table shown in Table 1a isextended to accommodate our security-enhanced dynamicrouting algorithm. In the extended routing table (seeTable 1b), we propose to associate each entry with a tupleðt;WNi ;t; CNit ;HNit Þ. CNit is a set of node candidates for thenexthop (note that the candidate selection will be elaboratedin Procedure 2 of Section 3.2), where one of thenexthop candidates that have the minimal cost is marked.HNit , a set of tuples, records the history for packet deliveriesthrough the node Ni to the destination node t. Each tupleðNj; hNj Þ in HNit is used to represent that Ni previouslyused the node hNj as the nexthop to forward the packetfrom the source node Nj to the destination node t. Let Nbriand wNi;Nj denote the set of neighboring nodes for anode Ni and the cost in the delivery of a packet between Niand a neighboring node Nj, respectively. Each node Ni alsomaintains an array (referred to as a page link table) in which eachentry corresponds to a neighboring node Nj 2 Nbri andcontains the cost wNi;Nj for a packet delivery.
Download full report
http://ntur.lib.ntu.edu.tw/bitstream/246...8/1/15.pdf
