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.

[attachment=5598]

---

Multipath 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. 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 present simulation 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.

THE use of novel devices for computing and communication in highly engineered networked embedded systems such as streetlight management , reconfigurable conveyors, and critical infrastructures , presents new challenges and opportunities for monitoring and diagnostics. These systems contain a large number of nodes, with each node incorporating a tiny microcontroller, sensors, actuators, and an integrated low-power transceiver . The nodes interact in a peer-to-peer manner over low-bandwidth wireless links to achieve the application objectives. To increase the number of simultaneous interactions between the nodes in the system, the transmission range of each node is limited so that it communicates directly only with its set of immediate neighbors; such an arrangement of nodes is referred to as a mesh topology . Multihop communications are necessary in such systems to send messages from any source to any destination. For example, intermediate nodes must forward messages to a monitoring station from nodes that cannot communicate directly with the monitoring station. Routing protocols are used extensively in wired and wireless networks to support multihop communication . Such protocols construct and maintain routing tables at each node by relying on systemwide unique node identifiers. When the number of nodes is very large, such as in sensor networks, it is not feasible to use such identifiers. Several techniques, called dissemination methods, were developed at the network layer to regulate the flow of messages between nonadjacent nodes without relying on unique node identifiers or constructing routing tables using these identifiers , , . In this paper, we consider highly engineered systems comprising of nodes arranged in a regular mesh topology. We focus on methods for effectively utilizing all the shortest paths available between a pair of nodes and present results to show that effective utilization of all the available paths significantly improves the Quality of Service (QoS). In many highly engineered systems, one can assume that the nodes have fixed relative locations. Often, the systems are designed to overlay on an underlying grid. For example, in automation systems, the regions demarcated by such a grid are called zones 0; a zone is a commonly used abstraction to support the design, operation, and maintenance activities. Motivated by applications in such domains, we consider regular mesh topologies that arise by embedding the nodes in a 2D Basegrid. We show in Section 2 that several mesh topologies arise when the location in the 2D Basegrid and the transmission range of the nodes change. Because the grid coordinates can specify the nodes, the shortest paths between any pair of nodes can be locally computed. Most routing protocols select only one of the shortest paths even when multiple such paths exist. This results in reduced systemlevel QoS . We address the issue of how to effectively utilize all the shortest paths available. Since the resulting methods amount to a node making local decisions on how to distribute messages among its immediate neighbors, without having to dynamically construct any routing tables, we refer to this method of forwarding messages as dissemination in spite of the fact that nodes are identified by their global coordinates in the underlying 2D Basegrid. Because each node communicates directly with its immediate set of neighbors, there are multiple shortest paths betweenmanypairs of nodes in ameshtopology. Thenumber of such paths is limited by the relative locations of the nodes. For example, the number of shortest paths between certain pairs of nodes is one, despite the mesh topology. We define a Contour as the union of all the shortest paths between a pair of nodes and present some results to precisely characterize the structure of contours. Using this structure, we show that when messages are spread in a round-robin manner, nodes along one path in the contour will always handle more messages than the nodes along other paths in the contour. Consequently, the benefits of the multiple paths cannot be fully realized. We then present a strategy for spreading messages to neighboring nodes that effectively exploits the available shortest paths and show that our rules for spreading the messages result in a balanced loading of all the available shortest paths. We refer to this approach as Contour Guided Dissemination (CGD). CGD improves the QoS by disseminating the messages over all the available shortest paths. Typical application scenarios in which CGD will be useful are: 1) a node responding to a diagnostic query from an operator at a monitoring station, and 2) a node sending a recorded incident to a monitoring station in a surveillance application. CGD equitably disseminates the messages over all the available shortest paths in a manner that maximizes utilization of all available shortest paths. We present simulation results to demonstrate all these aspects. 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. Recent efforts have focused on exploiting multipath to improve the QoS in systems using constrained node distribution models. For example, in 2 , the nodes are distributed randomly in a unit disk. In , the nodes are distributed in a narrow strip no wider than 0. times the transmission range of a node. The multipath, multihop, approach we present in this paper also assumes a constrained distribution of the nodes, namely, nodes are on a 2DBasegrid. While there is no stochasticity in the node distribution, we precisely characterize the geometry of the shortest paths and show how to exploit it to achieve better QoS.