04-12-2012, 04:06 PM
MULTI CAST ROUTING IN THE WIRELESS MESH NETWORKS
MULTI CAST ROUTING.doc (Size: 89.5 KB / Downloads: 21)
Abstract:
There exist two fundamental approaches to multicast routing: shortest path trees (SPTs) and minimum cost trees (MCTs). The SPT algorithms minimize the distance (or cost) from the sender to each receiver, while the MCT algorithms minimize the overall cost of the multicast tree. Due to the very large scale and unknown topology of the Internet, computing MCTs are used for multicast routing in the Internet is a very complex problem. As a result, the SPT approach is the more commonly used method for multicast routing in the Internet, because they are easy to implement and give minimum delay from the sender to each receiver, a property favored by many real-life applications. In Wireless Mesh Networks there number of nodes in its functional topology. The topology of the network has the number of nodes in its structure. This held’s MCT as a valuable one in multicast routing in WMNs. This paper describes about simulation-based performance comparison of SPTs and MCTs in WMNs using the performance metrics such
as packet delivery ratio, end-to-end delay, and traffic impacts on unicast flows in the same network
INTRODUCTION:
Wireless mesh networks (WMNs) are being developed actively and deployed widely for a variety of applications, such as public safety, environment monitoring, and citywide wireless Internet services. They have also been evolving in various forms (e.g., using multiradio/channel systems) to meet the increasing capacity demands. WMNs has the functional structure with number of nodes, network base stations, backbone coverage area and some concepts such as
multicast routing in the network structure.
Multicast is a form of communication that delivers information from a source to a set of destinations simultaneously in an efficient manner; the messages are delivered over each link of the network only once and only duplicated at branch points, where the links to the destinations split. Important applications of multicast include distribution of financial data, billing records, software, and newspapers; audio/video conferencing; distance education; and distributed interactive games. Although multicast is required to support many important applications, research on multicasting in WMNs is still in its
infancy. In this article we address one of the most essential
issues of multicast in WMNs − routing. There are two fundamental multicast routing approaches: shortest path trees (SPTs) and minimum cost trees (MCTs).
EXPLANATION OF THE ROUTING:
Figure 1 shows an example of a multicast group having four receivers and the three different routing trees constructed using the shortest path tree, the minimum Steiner tree, and the minimum number of transmissions tree algorithms. The example illustrates the typical characteristic of each kind of tree. Assuming that the cost of every edge is one unit, the SPT provides the shortest average path length (2.25 hops); the MST has the lowest cost (5 units); the MNT contains the least number of forwarding nodes (2 nodes), and requires the least number of transmissions per packet (3 transmissions/packet, including the transmission by the source S). Some authors demonstrated that the problem of computing MNTs is NP-complete and proposed enhanced heuristics to approximate such trees. The presented experimental results that show that the MNT algorithm offers the least number of transmissions compared with the MST and the SPT algorithms. On the other hand, the mean path lengths given by the MST and the MNT algorithms are longer than that by the SPT algorithm, as expected. However, the presented experimental results do not indicate how the multicast groups perform in terms of packet loss rate (or packet delivery ratio) − the true performance measure of a multicast session – or end-to-end delay − an important performance metric for real-time multicast applications such as distribution of stock quotes, distributed interactive games and tele conferencing.
SIMULTION PARAMETERS:
Our simulation models a medium-size network of 100 wireless routers uniformly distributed over a 2000m x 2000m area, and a large network of 300 wireless routers, over a 3000m x 3000m area. We will use the term “wireless router” and “node” interchangeably in this article. There are no network partitions throughout the simulation. The edge cost or the cost of each wireless link is assumed to be one. Assume that each sender or receiver is connected to a different wireless router. (In practice, there can be many hosts communicating with a wireless router, e.g., to form a wireless local area network). The sender and the receivers of
a multicast group was selected randomly, and the same sender and receivers and the same network configuration were used for all three algorithms (MST, MNT and SPT) in order to obtain a fair comparison. All receivers joined a multicast group at the beginning and stayed until the whole group terminated. The sender of a multicast group transmits at a constant bit rate specified for each experiment. The data packet size excluding the header size is 512 bytes. The size of the queue at every node is 50 Kbytes. The packets in a queue are scheduled on a first-in-first-out basis. We did not implement flow or congestion control in order to test the network performance under very high loads. Each experiment executed for 600 seconds of simulated time.
AVERAGE PATH LENGTHS:
The set of experiments simulated different multicast groups by varying the number of receivers from 20 to 80. Each multicast group has one source. The graph in Figure 2 shows the average path lengths of the trees constructed by the three algorithms to be compared. The results confirm that the MST and MNT algorithms produce longer paths than the SPT algorithm in all cases. Furthermore, the larger the network, the wider the difference gap. For instance, in the case of 40 receivers, the MST/MNT average path length is about 20% longer than the SPT average path length in the network of 100 nodes, but about 40% longer in the network of 300 nodes.
MULTICAST PERFORMANCE:
When examining a multicast group with one source and 20 receivers in the networks of 100 nodes and 300 nodes, respectively. When the traffic load is light (under 30 packets/sec), the performance of the SPT, the MST and the MNT is comparable with respect to packet delivery ratio. When the traffic load is moderate or high, the SPT outperforms the MST and the MNT in all cases, and the difference can be significant.
For example, when the traffic load is 60 packets/s, the PDRs
of the SPT, the MST and the MNT are 97%, 85%, and 92%,
respectively. The reason is due to longer path lengths of the
MST and the MNT. The longer the path a packet has to travel, the higher its chance of getting damaged or lost due to collision and/or congestion, especially under high traffic load. The average end-to-end delays incurred by the SPTs are also the lowest thanks to shorter source-to-destination paths. For example, when the traffic load is 50 packets/s, the average end to- end delays given by the SPT and the MNT are 11ms and 15ms, respectively; in other words, the SPT average end-to en delay is about 36% lower. The MST provides the highest average end-to-end delay in this case. In the larger network of 300 nodes, the performance differences between the SPT and the MST/MNT are even more efficient. The examination of the multicast groups of other sizes – from 10 to 80 receivers. In general, given the same network size and the same set of other parameters, as the number of receivers in a multicast group increases, the performance gap between the SPT and the MST/MNT becomes narrower; but the SPTs still perform better than (or, in a small number of cases, similarly to) the MSTs/MNTs in terms of packet delivery ratio and end-to-end delay.
DISCUSSIONS AND FUTURE WORK
The simulations are based on IEEE 802.11 CSMA/CA medium access control because this is a widely accepted radio technique for WMNs. Other types of WMNs that are being] considered or standardized include 802.15 and 802.16. Since 802.16 uses TDMA (Time Division Multiple Access), and 802.15, a combination of TDMA and CSMA/CA, our future work is to extend this study to these types of networks. We assume that all transmissions of a multicast group take place on one channel. Although multi-channel mesh networks have been studied extensively in order to enhance the overall network throughput, currently there are no effective multichannel protocols for multicast communications, and designing such a protocol is not a trivial task either. (Different multicast groups can use different channels though, as long as no channel switching is required for multicast transmissions. Our results are still valid when the multicast groups and unicast flows to be studied are on the same channel.) Finally, one of the current consensuses regarding WMNs is that they should be small to medium in size (compared with the Internet). The reason is that in 802.11-based networks the throughput of a flow decreases rapidly as its path length increases. (An 802.16 mesh is even less scalable, able to support only around 100 subscribers due to centralized scheduling message structures.)
CONCLUSION:
The quantified performance differences of minimum cost trees and shortest path trees in WMNs. Our simulation results show that SPTs offer significantly better performance to multicast flows than MCTs such as MSTs and MNTs. The average packet delivery ratio given by SPTs is higher by up to 24%, and the SPT average end-to-end delay is up to 120% lower in our experiments. The only drawback of SPTs is that when the multicast sending rate is high SPTs cause more packet losses to other flows than MCTs. The reason is that in a SPT typically more nodes are involved in the data forwarding task compared with a MCT. However, SPTs cause only 1% to 3.5% more packet loss to unicast flows than MCTs in our experiments, and only when the multicast traffic load is high. Under light or moderate traffic, SPTs and MCTs have similar effects on other flows in the network. In our opinion, the high multicast performance gains of SPTs out weights the above drawback. It is much easier to design a reliable transport protocol for unicast communications than for multicast communications in wireless multi-hop networks. Several TCP-based protocols have been proposed for reliable data delivery for unicast flows in wireless ad-hoc networks [13], which could be applied to WMNs. However the problem of reliable multicast in wireless ad-hoc networks still remains unsolved. Although several reliable multicast protocols have been proposed for the Internet (e.g., SRM, RMP, RMTP, NORM and ALC, their applicability to and efficiency in WMNs have not been studied.