In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

Wireless access networks of the future could provide a variety of context-aware services with the use of sensor information in order to solve regional social problems and improve the quality of residents' lives as a part of the regional infrastructure. NerveNet is a conceptual regional wireless access platform in which multiple service providers provide their own services with shared use of the network and sensors, enabling a range of context-aware services. The platform acts like a human nervous system. Densely located, interconnected access points with databases and data processing units will provide mobility to terminals without a location server and enable secure sensor data transport on a highly reliable, managed mesh network. This paper introduces the motivations, concept, architecture, system configuration, and preliminary performance results of NerveNet.