17989665
Message ferrying: proactive routing in highly-partitioned wireless ad hoc networks
An ad hoc network allows devices with wireless interfaces to communicate with each other without any pre-installed infrastructure. Due to node mobility, limited radio power, node failure and wide deployment area, ad hoc networks are often vulnerable to network partitioning. A number of examples are in battlefield, disaster recovery and wide area surveillance. Unfortunately, most existing ad hoc routing protocols will fail to deliver messages under these circumstances since no route to the destination exists. In this work we propose the Message Ferrying or MF scheme that provides efficient data delivery in disconnected ad hoc networks. In the MF scheme, nodes move proactively to send or receive messages. By introducing non-randomness in a node's proactive movement and exploiting such nonrandomness to deliver messages, the MF scheme improves data delivery performance in a disconnected network. In this paper, we propose the basic design of the MF scheme and develop a general framework to classify variations of MF systems. We also study ferry route design problem in stationary node case which is shown to be NP-hard and provide an efficient algorithm to compute ferry route.
446110
Controlling the mobility of multiple data transport ferries in a delay-tolerant network
As technology rapidly progresses, more devices will combine both communication and mobility capabilities. With mobility in devices, we envision a new class of proactive networks that are able to adapt themselves, via physical movement, to meet the needs of applications. To fully realize these opportunities, effective control of device mobility and the interaction between devices is needed. In this paper, we consider the message ferrying (MF) scheme which exploits controlled mobility to transport data in delay-tolerant networks, where end-to-end paths may not exist between nodes. In the MF scheme, a set of special mobile nodes called message ferries are responsible for carrying data for nodes in the network. We study the use of multiple ferries in such networks, which may be necessary to address performance and robustness concerns. We focus on the design of ferry routes. With the possibilities of interaction between ferries, the route design problem is challenging. We present algorithms to calculate routes such that the traffic demand is met and the data delivery delay is minimized. We evaluate these algorithms under a variety of network conditions via simulations. Our goal is to guide the design of MF systems and understand the tradeoff between the incurred cost of multiple ferries and the improved performance. We show that the performance scales well with the number of ferries in terms of throughput, delay and resource requirements in both ferries and nodes.
14217231
Scheduling Tasks with Resource Requirements in Hard Real-Time Systems
This paper describes a heuristic approach for solving the problem of dynamically scheduling tasks in a real-time system where tasks have deadlines and general resource requirements. The crux of our approach lies in the heuristic function used to select the task to be scheduled next. The heuristic function is composed of three weighted factors. These factors explicitly consider information about real-time constraints of tasks and their utilization of resources. Simulation studies show that the weights for the various factors in the heuristic function have to be fine-tuned in order to obtain a degree of success in the range of 75-88 percent of that obtained via exhaustive search. However, modifying the approach to use limited backtracking improves the degree of success substantially to as high as 99.5 percent. This improvement is observed even when the initial set of weights are not tailored for a particular set of tasks. Simulation studies also show that in most cases the schedule determined by the heuristic algorithm is optimal or close to optimal.
9972438
New delay analysis in high speed networks
The implementation of bounded-delay services over integrated services networks relies admission control mechanisms that in turn use end-to-end delay computation algorithms. For guaranteed-rate scheduling algorithms such as fair queueing, delay computation based on Cruz's service curve model performs very well. Many currently deployed networks, be they packet-switched or ATM based, rely on non-guaranteed-rate disciplines, most prominently FIFO and static-priority disciplines. We show that for this class of disciplines the service curve model performs poorly. We propose the Integrated Approach as alternative to the service curve model to cluster servers for delay computation purposes, and show in a series of evaluations that this new approach outperforms approaches based on the service curve model as well as other currently used approaches.
41957109
End-to-end latency of a fault-tolerant CORBA infrastructure
This paper presents measured probability density functions (pdfs) for the end-to-end latency, of two-way, remote method invocations from a CORBA client to a replicated CORBA server in a fault-tolerance infrastructure. The infrastructure uses a multicast group-communication protocol based on a logical token-passing ring imposed on a single local-area network. The measurements show that the peaks of the pd/s for the latency are affected by the presence of duplicate messages for active replication, and by the position of the primary server replica on the ring for semi-active and passive replication. Because a node cannot broadcast a user message until it receives the token, up to two complete token rotations can contribute to the end-to-end latency seen by the client for synchronous remote method invocations, depending on the server processing time and the interval between two consecutive client invocations. For semi-active and passive replication, careful placement of the primary server replica is necessary to alleviate this broadcast delay to achieve the best possible end-to-end latency. The client invocation patterns and the server processing time must be considered together to determine the most favorable position for the primary replica. Assuming that an effective sending-side duplicate suppression mechanism is implemented, active replication can be more advantageous than semi-active and passive replication because all replicas compete for sending and, therefore, the replica at the most favorable position will have the opportunity to send first.
7097106
Hard real-time communication in multiple-access networks
With the increasing use of distributed hard real-time systems, the ability of computer networks to handle hard real-time message traffic is becoming more important. For traditional networks, maximizing the throughput or minimizing the average message delay is the most important performance criteria. In the hard real-time domain, however, concern focuses on satisfying the time constraints of individual messages. This paper examines recent developments in hard real-time communication in local area multiple-access networks. Two general strategies are used in hard real-time communication: the guarantee strategy and the best-effort strategy. In the former, messages are guaranteed to meet their deadlines during normal operation of the network. In the best-effort strategy, the network will attempt to send messages before their deadlines, but no guarantees are given. Real-time message traffic can be distinguished according to whether it is best suited for the guarantee strategy or the best-effort strategy. Although this paper concentrates on multiple-access networks, many of the concepts presented and lessons learned are also applicable to other types of networks.
7260523
Providing statistical delay guarantees in wireless networks
We study the delay performance of policed traffic to provide real-time guarantees over wireless networks. A number of models have been presented in the literature to describe wireless (radio or optical) networks in terms of the wireless channel and the underlying error control mechanisms. We describe a general framework to incorporate such models into delay guarantee computations for real-time traffic. Static-priority scheduling is considered, and two different admission control mechanisms are used to achieve the trade-off between resource utilization and admission overhead.