01-07-2010, 04:35 PM
Multi-path Dissemination in Regular Mesh Topologies
Abstract:
Mesh topologies are important for large-scale peer-to-peer systems that use low-power transceivers. The Quality of Service (QoS) in such systems is known to decrease as the scale increases. We present a scalable approach for dissemination that exploits all the shortest paths between a pair of nodes and improves the QoS. Despite the presence of multiple shortest paths in a system, we show that these paths cannot be exploited by spreading the messages over the paths in a simple round-robin manner; nodes along one of these paths will always handle more messages than the nodes along the other paths.
Algorithm / Technique used:
Uniform Spreading Algorithm.
Algorithm Description:
The first strategy we consider for spreading messages over all shortest paths will be called Uniform Spreading. This is a straightforward strategy where the source, as well as each intermediate node along every path in the contour, sends successive messages in a round-robin fashion to all its immediate neighbors in the contour. We present this algorithm and show that the nodes along one of the paths will always handle more messages than the nodes along other paths whenever this strategy is used.
Existing System:
We study wireless network routing algorithms that use only short paths, for minimizing latency, and achieve good load balance, for balancing the energy use. We consider the special case when all the nodes are located in a narrow strip with width at most ˆš3/2 ‰ˆ 0.86 times the communication radius. We present algorithms that achieve good performance in terms of both measures simultaneously. In addition, our algorithms only use local information and can deal with dynamic change and mobility efficiently.
Proposed System:
We characterize the set of shortest paths between a pair of nodes in regular mesh topologies and derive rules, using this characterization, to effectively spread the messages over all the available paths. These rules ensure that all the nodes that are at the same distance from the source handle roughly the same number of messages. By modeling the multihop propagation in the mesh topology as a multistage queuing network, we results from a variety of scenarios that include page link failures and propagation irregularities to reflect real-world characteristics. Our method achieves improved QoS in all these scenarios.
Modules:
1. Network Module
2. Uniform Spreading
3. Loading in Spreading
4. Optimal Spreading
5. Routing Protocol
Module Description:
1. Network Module
Client-server computing or networking is a distributed application architecture that partitions tasks or workloads between service providers (servers) and service requesters, called clients. Often clients and servers operate over a computer network on separate hardware. A server machine is a high-performance host that is running one or more server programs which share its resources with clients. A client also shares any of its resources; Clients therefore initiate communication sessions with servers which await (listen to) incoming requests.
2. Uniform Spreading
Spreading messages over all shortest paths will be called Uniform Spreading. This is a straightforward strategy where the source, as well as each intermediate node along every path in the contour, sends successive messages in a round-robin fashion to all its immediate neighbors in the contour. We present this algorithm and show that the nodes along one of the paths will always handle more messages than the nodes along other paths whenever this strategy is used.
3. Loading in Spreading
Uniform spreading is achieved when all the nodes in the contour execute the Uniform Spreading algorithm. To characterize the effects of this algorithm, we first define what we call rows in a contour.
4. Optimal Spreading
An algorithm for spreading the messages so that all the available paths are effectively utilized. Recall that a row is a collection of nodes in the contour that are at the same distance from the source. Let w be the number of nodes in a row of a contour. We refer to w as the width of the row. If the source sends M messages and if every node in every row handles messages, then we can say that the spreading is the best in the sense that all available paths are effectively used. This is the criterion of optimality that we choose. We will show that the algorithm presented in this section is optimal in this sense.
5. Routing Protocol
Routing protocols used in traditional wired and wireless networks are based on shortest path algorithms such as the Bellman-Ford algorithm and Dijkstraâ„¢s algorithm. Similar protocols have been reported for ad hoc, wireless, and mobile networks. The QoS achieved in these systems has also been studied. The dissemination method we describe in this paper is somewhat similar to a gradient dissemination scheme with the cost metric being the deviation from evenness of load distribution on all available shortest paths.
Hardware Requirements:
¢ System : Pentium IV 2.4 GHz.
¢ Hard Disk : 40 GB.
¢ Floppy Drive : 1.44 MB.
¢ Monitor : 15 VGA Colour.
¢ Mouse : Logitech.
¢ RAM : 256 MB.
Software Requirements:
¢ Operating system : - Windows XP Professional.
¢ Coding Language : - Java.
¢ Tool Used : - Eclipse.
