An extended depth-first-search (EDFS) algorithm is proposed to solve the multi-constrained path (MCP) problem in quality-of-service (QoS) routing, which is NP-Complete when the number of independent routing constraints is more than one. EDFS solves the general k-constrained MCP problem with pseudo-polynomial time complexity O(m^2_ {EN} + N2), where m is the maximum number of non-dominated paths maintained for each destination, E And N are the number of links and nodes of a graph, respectively. This is achieved by deducing potential feasible paths from knowledge of previous explorations, without re-exploring finished nodes and their descendants in the process of the DFS search. One unique property of EDFS is that the tighter the constraints are, the better the performance it can achieve, w.r.t. both time complexity and routing success ratio. This is valuable to highly dynamic environment such as wireless ad hoc networks in which network topology and link state keep changing, and real-time or multimedia applications that have stringent service requirements. EDFS is an independent feasible path searching algorithm and decoupled from the underlying routing protocol, and as such can work together with either proactive or on-demand ad hoc routing protocols as long as they can provide sufficient network state information to each source node. Analysis and extensive simulation are conducted to study the performance of EDFS in finding feasible paths that satisfy multiple QoS constraints. The main results show that EDFS is insensitive to the number of constraints, and outperforms other popular MCP algorithms when the routing constraints are tight or moderate. The performance of EDFS is comparable with that of the other algorithms when the constraints are loose.

Publications:

Z. Li and J.J. Garcia-Luna-Aceves, ''Finding Multi-Constrained Feasible Paths By Using Depth-First Search'', Wireless Networks Journal (ACM/WINET, Springer). Accepted for publication.
Z. Li and J.J. Garcia-Luna-Aceves, ''Solving the Multi-Constrained Path Selection Problem by Using Depth First Search'', the Second International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine'2005), August 22-24, 2005, Orlando Florida, USA.

Distributed approach

The distributed multi-constrained routing (DMR) protocol is proposed for the distributed computation of constrained paths for QoS routing. DMR exploits distance vectors to construct a logical shortest multipath (LSM) for each destination with regard to a given optimization metric, from which a set of non-dominated paths are locally derived at each node, and as such is able to find feasible paths as well as optimize the utilization of routing resources. DMR operates in line with the hop-by-hop, connectionless routing model assumed in the IP Internet, and maintains instantaneous loop freedom. Nodes running DMR need not maintain a global view of network state (topology and resource information), and routing updates are sent only to neighboring nodes. This is in sharp contrast with all previous approaches, which rely on complete or partial network state made available at each node for constrained path selection, which incurs excessive communication overhead in large networks and is hard to achieve in practice.

Publication:

Z. Li and J.J. Garcia-Luna-Aceves, "Loop-Free Constrainted Path Computation For Hop-by-Hop QoS Routing", Computer Networks (Elsevier) Journal, Accepted for publication.
Z. Li and J.J. Garcia-Luna-Aceves, ''A Distributed Approach for Multi-Constrained Path Selection and Routing Optimization'', the Third International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine'2006), August 7-9 2006, Waterloo, Ontario, Canada.

QoS routing in wireless networks

We propose the bounded ad-hoc QoS routing – BAQR, a hybrid approach in which the on-demand seeking of multi-constrained feasible paths is bounded within a logical searching domain, which is enforced based on the proactive, traffic-driven signaling of the constrained metric being considered. BAQR diffuses throughout the network estimates of the distance (i.e., the constrained metric) for each known node, and proactively updates such estimates using a label based signaling algorithm – LBR. The actual route discovery is on-demand performed in which non-duplicate route request (RREQ) messages are further forwarded only if the relaying nodes stay within an ellipse that takes the source and destination nodes as the foci. Simulations using Qualnet show that BAQR is an efficient approach to solving constrained routing problems in ad hoc networks.

KEY DISTRIBUTION AND MANAGEMENT

Symmetric cryptographic primitives are preferable in designing security protocols for mobile ad hoc networks (MANETs) because they are computationally affordable for resource-constrained mobile devices forming a MANET. Most proposed key-distribution and key-agreement schemes for symmetric cryptosystem assume services from on-line centralized authorities, or require the interaction between communicating parties. However, the presence of a centralized authority violates the ad hoc definition of MANETs, and interactive schemes require the routing of the ad hoc network to be established before the key agreement, which is difficult to ensure in a mobile ad hoc network (MANET). We propose a new non-interactive key agreement and progression (NIKAP) scheme for MANETs, which does not require an on-line centralized authority, can establish and update pairwise shared keys between any two nodes in a non-interactive manner, is configurable to operate synchronously (S-NIKAP) or asynchronously (A-NIKAP), and is able to provide differentiated security services w.r.t. specified security policies. As the name implies, NIKAP is especially valuable to scenarios in which shared secret keys are desired to be computed without negotiation between nodes over insecure channels, and need to be updated frequently.

Publications:

Z. Li and J.J. Garcia-Luna-Aceves, "Non-Interactive Key Distribution Protocols and Their Applications to Security in Wireless Mesh Networks", Security in Wireless Mesh Networks (Y. Zhang, J. Zheng and H. Hu, Eds.). To be published by Auerbach Publications, CRC Press.
Z. Li and J.J. Garcia-Luna-Aceves, ''New Non-Interactive Key Agreement and Progression (NIKAP) Protocols and Their Applications to Security in Ad Hoc Networks", the 2005 International Workshop on Wireless and Sensor Networks Security (WSNS'2005), held in conjunction with MASS'2005, November 7-10, Washington DC, USA.

SECURE AD HOC ROUTING

We present the Ad-hoc On-demand Secure Routing (AOSR) protocol, which uses pairwise shared keys between pairs of mobile nodes and hash values keyed with them to verify the validity of the path discovered. The verification processes of route requests and route replies are independently executed while symmetrically implemented at the source and destination nodes, which makes AOSR easy to implement and computationally efficient, compared with prior approaches based on digital signing mechanisms. By binding the MAC address (physical address) with the ID of every node, we propose a reliable neighbor-node authentication scheme to defend against complex attacks, such as wormhole attacks. An interesting property of AOSR is the "zero" communication overhead caused by the key establishment process, which is due to the exploitation of a Self-Certified Key (SCK) cryptosystem. Analysis and simulation results show that AOSR effectively detects or thwarts a wide range of attacks to ad hoc routing, and is able to maintain high packet delivery ratios, even when considerable percentage nodes are compromised.

Publications:

Z. Li and J.J. Garcia-Luna-Aceves, ''Non-Interactive Key Establishment in Mobile Ad Hoc Networks", Ad Hoc Networks (Elsevier) Journal. Accepted for publication.
Z. Li and J.J. Garcia-Luna-Aceves, ''Enhancing The Security Of On-demand Routing in Ad Hoc Networks'', the 4th International Conference on AD-HOC Networks and Wireless (AdhocNow'2005), LNCS 3738, pp. 164-177, October 6-8 , 2005, Cancun, Mexico.
Z. Li and J.J. Garcia-Luna-Aceves, "A Secure Reactive Ad Hoc Routing Protocol", the 3rd IEEE Latin American Network Operations and Management Symposium (LANOMS' 2003), September 4-6, Iguassu Falls, Brazil.

EFFICIENT BROADCASTING IN WIRELESS NETWORKS

Broadcasting is a simple and effective technique for the dissemination of information in wireless ad hoc networks. However, without damping redundant transmissions, naive broadcasting is prone to losing performance, also wastes scarce battery and bandwidth of wireless nodes. Existing improvements to the basic broadcasting suffer from poor scalability, considerable control overhead or fragile resilience to topology dynamics. We propose a new broadcasting scheme called DPNH (Dominant Pruning with No Hellos), which exploits data traffic to rebuild the neighborhood topology at each node, and implements an enhanced Greedy Cover heuristic to distributively determine the multi-point relays (MPRs) that should rebroadcast packets. DP-NH does not spend resources on sending and processing designated control packets, and computes MPRs for efficient broadcasting only when the network carries traffic. Simulations show that DP-NH avoids the cost and performance loss incurred by such proactive signaling of neighbor information as periodic Hellos, and retains the same merits as that of prior approaches based on dominant-pruning heuristics.

VERIFICATION OF SECURE ROUTING PROTOCOLS

Significant efforts have been made to secure routing functionality, which is the essential component of today's network architecture. However, little work has been done to formally study their effectiveness and correctness. Formal analysis is crucial to the design of secure routing protocols because we need correct and unambiguous specification of newly devised protocol for real implementation afterwards. In this paper, we present an approach to achieve that goals, and illustrate the validity of our approach by formalizing a specific secure DV(distance vector) routing protocol, through which necessary assumptions for the security countermeasures are clearly stated, logical inconsistences are detected and corrected through step-by-step analysis, and its effectiveness and correctness are formally verified and proven. This is achieved by combining complementary verification techniques: Formal logic for cryptographic protocols (to analyze the security/effectiveness properties), and Model checker for communication protocols(to validate the correctness properties). We show how our method can help us find ambiguities and logic inconsistencies in protocol design, and improve them to achieve a more trustable, precise and error-free specification based on the analytical results.