Constrained path computation for QoS routing in computer networks.

摘要

In this thesis, we investigate new algorithms and methodologies that facilitate the computation of multi-constrained path for QoS routing in wired and wireless networks.; First, we present the extended depth-first-search (EDFS) algorithm that solves the general k-constrained multi-constrained path (MCP) problem with pseudo-polynoinial 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. EDFS is a centralized algorithm requiring global network state (topology and resource information) maintained at each source, and has the unique property that the tighter the constraints are, the better the performance it can achieve, w.r.t. both time complexity and routing success ratio.; Second, we propose the fully distributed multi-constrained routing (DMR) protocol that addresses both constrained path computation and resource optimization problems for QoS routing. DMR operates in line with the hop-by-hop, connectionless routing model assumed in the IP Internet, and need not to maintain a global view of the network state at each node. This is in sharp contrast with all previous approaches, which rely on complete or partial network state made available at each node for path selection subject to multiple constraints, which may incur excessive communication overhead in large networks and is hard to achieve in practice.; Third, we present the ellipse-bounded ad-hoc routing (eBAR), a new ondemand routing scheme for wireless ad hoc networks where non-duplicate route request (RREQ) messages are further forwarded only if the relaying node stays within an ellipse that has the source and destination nodes as the foci. This is achieved by the traffic-driven, destination-initiated signaling of estimates of the distance to each active destination (i.e., data sinks).; Last, we investigate key distribution and secure routing issues in rnulti-hop wireless networks. We present a new non-interactive key agreement and progression (NIKAP) scheme that 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 has the ability to provide differentiated security services w.r.t. the given security policies.; This thesis includes research work that have been previously published in [29, 25, 26, 27, 30, 31, 32, 28, 33]; and coauthored with Prof. J.J. Garcia-Luna-Aceves.