Development of an Improved Multicast Algorithm for Interpreting the Cost of Bandwidth within the Channel during Multicast using Shannon-Hartley Channel Capacity Theorem

Development of an Improved Multicast Algorithm for Interpreting the Cost of Bandwidth within the Channel during Multicast using Shannon-Hartley Channel Capacity Theorem

S. J. Soja, S. M. Sani, S. Garba and A. M. S. Tekanyi

Department of Electrical and Computer Engineering, Ahmadu Bello University, Zaria, Kaduna State, Nigeria

Abstract – This paper is based on Shannon Hartley channel capacity theorem aimed at interpreting the true cost of bandwidth within the channel during multicast. The performance of Network Coding Algorithm (NCA) was improved by considering two (packet delay and packet loss) and three (packet delay, packet loss and packet rejection) performance metrics collectively on the NCA formulated as mixed integer linear programming problem. Simulation results showed that the average cost of bandwidth decreased by 27% when two performance metrics are considered as compared to the bench mark algorithm. Similarly, as three performance metrics are considered, the average cost of bandwidth decreases by 37.1% when compared to the bench mark algorithm. Considering loss, delay and rejection of packets collectively also achieved a reduction in the average cost of bandwidth by 12.7% when compared to the NCA with two performance metrics of delay and loss of packets. It is evident from the simulation results obtained that as more performance metrics were considered, the average cost of bandwidth decreases. This indicates that the average cost of bandwidth was under estimated when number of considered metrics is lesser.

Key words: Shannon Hartley channel capacity theorem, Multicasting, Bandwidth, Network coding and Network Coding- Algorithm

1. INTRODUCTION

   In this paper the problem of bandwidth utilization during multicast over wireless network is studied. The work here is to send the same information from the source to all the receivers within the multicast group. According to [1], multicasting is the transmission of data in a group of nodes which is recognized by one and distinctive address. Multicast services allow one source to send information to a large number of receivers and it finds application in many areas such as audio conferencing, video conferencing, video-on-demand services, peer-to-peer file sharing, electronic learning, online shopping, distributed interactive simulation, software enhancement, Wireless Internet Protocol Television (IPTV), distance Education, group- oriented mobile commerce, firmware reprogramming of wireless devices, distributed database replication, etc, [2, 3]. One of the principal resources that an overlay network must manage is the access bandwidth to the internet and

   the energy consumption during multicast as nodes at different locations communicate with each other by relaying information over wireless links, which represents a major cost [4]. It requires many issues to be addressed such as bandwidth, topology, loss of packets, delay, routing, reliability, security and quality of service, before it can be fully deployed [5].

   Multicasting is a more general form of group communication than broadcast because all broadcast session can be viewed as a special case of multicast, where all nodes are within the multicast group. In network-wide broadcasting the objective is to distribute the generated data to all the nodes in the network [6]. This problem is similar to the scalability problem that arises when trying to broadcast large amounts of data to many end-users in real time, for example, live streaming on the internet [7]. The main difference is that multicast, as opposed to broadcast, is directed to a specific set of end-users. Also, broadcasting everything to everybody would violate security principles of sensitive data [8].

   Network coding helps in increasing network throughput and security by encoding several packets with single packet size length and forwarding them in a single transmission time slot [9, 10]. Minimizing the total bandwidth utilization of the links and energy consumption are the goal for all optimization problems for multicast routing algorithms.

   The authors in [10] gives a simple example that with network coding, source could multicast information at a rate approaching h to all the receivers as the symbol size approached infinity. They demonstrated how the use of network coding can maximize throughput, ensure security and reliability of messages exchanged. [11] examined the performances of two multicast algorithms over coded packet wireless network. Simulation results clearly showed that the Network Coding Algorithm (NCA) outperformed the Multicast Incremental Power Algorithm (MIPA) for cost efficient multicast. Nevertheless, more performance metrics were not considered in the development of the NCA. The problem that prompted this intensive study ever

   since is to be able to determine those factors which seriously affect the cost of bandwidth during multicast over coded packet wireless networks. Another crucial issue investigated in this paper is whether the channel capacity is truly represented in the proposed algorithm in accordance with Shannon Hartley channel capacity theorem. Therefore, there is a need to find an improvement to the proposed algorithm, the approach taken by this study is to introduce more performance parameters which affect the channel and particularly bandwidth utilization.

   Our algorithm can be viewed as an improvement of the NCA proposed by [11] were more performance metrics are collectively considered. [12] examined secured multicasting for wireless sensor networks by designing a scheme that offer three levels of security during multicast, namely; low overhead, immediate authentication, and

   practice, which is widely applied to network security, and network monitoring, multicasting and management [15]

   Network coding offers many benefits of ensuring that the security and reliability of messages exchange within the nodes, it saves bandwidth and maximized the networks throughput.

   2.2 Shannon Hartley Channel Capacity Theorems According to [16], the bandwidth of a given channel increases as the noise within the channel increases. The law is named after Claude Shannon and Ralph Hartley. ShannonHartley equation relates the maximum capacity that can be achieved over a given channel with certain noise characteristics and bandwidth. It can be expressed by the following relationship;

   resilience to node compromise attack. Still, the scheme designed was only compared with only two public key cryptography scheme and can be more vulnerable to

   C B log2 (1 S / N)

   where B is the bandwidth of the channel in Hz, S is the signal power in watts,

   (1)

   hackers.

   The aim of this research is to interpret the true cost of bandwidth utilization during multicast over wireless networks using Shannon Hartley channel capacity theorem in order to achieve the true representation of the channel.

2. NETWORK CODING TECHNIQUES

   2.1 Random Linear Network coding

   To the best of our knowledge, Network coding was first proposed by [10] and it entails the transmission, encoding and re-encoding of messages arriving at nodes inside the network, such that the transmitted messages can be decoded at their final destinations [13]. It finds application in real networks where packets are subject to random loss and delay. The interest in Network coding increase as new applications are discovered in both theory and real time situation [14]..

   N is the total noise of the channels in watts and C is channel capacity.

   The bandwidth B is directly proportional to the noise N and hence, considering more parameters leads to an incease in the bandwidth of the channel [17]. The significant of equation 1 is to interpret the true picture of the channel as more noise or performance metrics are considered within the channel.

   2.3 Mathematical Model and Problem Formulation Consider a directed network G = (V, E), where V is a set of nodes and E is a set of directed links, V G and E G

   denote the number of nodes and links in the network. s V is the source node, M V be a set of nodes involved in a group communication and M is called multicast group with each node M as a group

   member. Each node v is assigned a cost v and a delay

   v which are assumed to be nonnegative integers [18]. Given a set of nodes n and a cost Cij associated with node i to j (1 i j n) . To find the minimum cost of the sub graph G denoted by G is defined by [19] as:

   G =

   vEH

   v

   (2)

   Figure 1: Basic Network Coding [10]

   The delay of a path P in Graph G, denoted by P is defined as:

   As an example, consider a network multicasting two data

   bits, b1 and b2, from the source as shown in Figure 1. With the help of network coding, it is possible to multicast two

   P =

   vEP

   i

   (3)

   bits b1 and b2 from one source S to destination nodes Y and

   Z. Channels GH, HY, HW and WZ carry bit b1 and channels GI, JZ, JW, and WY carry the bit b2. Channels WX, XY, XZ carry the exclusive-OR b1 b2 and the node Y receives b1 and b1 b2, from which b2 can be decoded. Also, the node Z can decode the bit b1 from b2 and b1 b2 and this encoding scheme has been implemented in

   where i is the delay encountered by the packets i on a

   given link during multicast

   The problem can be formulated as a mixed integer programming where the optimization objectives are usually defined in terms of minimizing the cost of a multicast tree, and the cost in question is the bandwidth used, packet loss,

   packet rejection and packet delay serves as the constraints [20, 21]. The objective function is defined [22] as:

   n

3. RESULTS AND DISCUSSION

   3.1 Simulation Setup

   The performance of the INCA algorithm was evaluated by

   Min (q)=

   (i, j )V

   cij yij (i. j) V ,i j

   (4)

   simulation. The INCA was implemented on visual studio

   Subjected to:

   ij iai j

   C C (i, j) A, ai i

   j

   ( p) 400 (i. j) V ,i j

   (5)

   (6)

   2010 and simulation was carried out for 20, 30, 40, and 50 randomly generated nodes multicasting to different groups of receivers. The standard parameters used for the simulation are shown in Table 1.

   Parameter	Value
   No. of random nodes	20, 50
   Value of packet delay	400
   Value of Packet loss	4
   Value of rejected packets	8
   Groups of receivers	2-10

   TABLE 1: STANDARD SIMULATION PARAMETERS

   (l) 4; i Source, i j (i, j) V

   n

   (7)

   p(r) 8; i Source, i j (i, j) V

   (8) yij 0 ;

   y1

   i Source,

   i v / s

   (9)

   where Cij = the cost of the bandwidth,

   yij = the distance from one node to the other,

   (i, ai )

   j = the arc originating in node I with the lowest cost,

   q = the bandwidth (the cost) to be minimize

   p = packet delay

   l = packet loss

   r = packet rejection

   In formulating the problem, it is assume that packet loss is less than equal to four (4) decibel, packets delay to be less than 400ms and the number of packet rejection is eight (8) [1].

   2.4 The Improved Network Coding Algorithm

   The INCA considers more performance metrics such delay, loss and rejection of packets rejection and it can be applied to two and three performance metrics respectively. The INCA was proposed in such a way that it can be applied to two or more performance metrics collectively. The value of packet delay was increased to 400ms to enhance efficient packet delivery. This also takes care of other delays such nodal processing delay, which deals with the physical characteristics of the path a packets traversed, delay on the process of transmission which is a function of link capacity, delay along the route, and queuing delay which depend on the traffic load along the path. These delay lead to bandwidth consumption during multicast and on the other hand, packet loss is also critical because when sending packets from the source to receivers, there are cost associated with them, and if they do not get to their destinations, there is additional cost involves in resending the packets again. So, a negligible value of the packet loss is set to be less than or equal to four (4) in such a way that the cost of lost packets within this range is tolerated and packet rejection to be less than equal to 8.

   This simulation pattern were use in order to reach a decision with the one used by the NCA which serves as a benchmark.

   Table 2: Costs of Bandwidth for 20 Randomly Generated Nodes Multicasting to Groups of Receivers

   Number of receivers	Cost of Bandwidth during Multicast
   	Network INCA with INCA with coding two three Algorithm parameters parameters
   2 3 4 5 6 7 8 9 10	1.0710 4.0521 3.6518 3.9777 4.0871 5.9811 7.6331 8.3482 8.5710	0.3405 1.5047 1.6769 2.2611 3.2449 4.9350 5.5823 6.2030 8.4356	0.1571 1.4453 1.5297 1.2306 2.4076 4.3894 5.4192 5.9324 7.2994

   Number of receivers	Cost of Bandwidth during Multicast
   	Network Coding Algorithm	INCA with two parameters	INCA with three Parameters
   2	0.9663	0.7506	0.2555
   3	2.5024	1.6129	1.0598
   4	3.4126	2.0116	1.6066
   5	4.9163	2.8540	2.8184
   6	5.6603	4.3289	4.3147
   7	6.5861	5.9323	5.0145
   8	7.7031	6.4192	6.2312
   9	8.4885	6.9220	6.0914
   10	8.7075	7.8556	7.0058

   Table 3: Costs of Bandwidth for 50 randomly generated nodes multicasting to Groups of Receivers

   Figure 2: Cost of Bandwidth during Multicast for 20 Randomly Generated Nodes.

   Figure 3: Cost of Bandwidth during Multicast for 50 Randomly Generated

   Nodes.

   From Figures 2 and 3, it can be observed that the average cost of bandwidth decrease as more performance metrics is considered. For example in Figure 2, there is a reduction in the avearage cost of bandiwdth used during multicast when two performance metrics are considered by 27% when compared to the benchmark algorithm. Similarly, considering loss, delay and rejection of packets collectively lead to the reduction in the average cost of bandwidth by 37.1% when compared to the benchmark algorithm. Equally, considering packet loss, packet delay and packet rejection collectively also achieved a reduction in the average cost of bandwidthused during multicast by 12.7% when compared to the NCA with two metrics.

4. CONCLUSION

This paper examined the performance of NCA and INCA with two and three metrics aimed at interpreting Shannon Hartley channel capacity theorem of bandwidth. As more performance parameters are applied on the NCA the average cost of bandwidth within the channel decreases during multicast for all the numbers of randomly generated nodes. From the simulation results obtained, we conclude that the average cost of bandwidth presented was under estimated when number of considered metric is lesser. All

the performance metrics affecting the channel and bandwidth are not exhaustively considered, so the limit of the impact on the avearage cost of bandwidth is not reach. Future work will consider four or five performance metrics on the NCA to see the impact of these metrics on bandwidth consumption during multicast. The use of packets network has resulted in proffering many solutions to problems during multicast because of its reliability, security and resilience to node compromise and attacks.

REFERENCES

1. K. Chopra, and A. Mishra, Packet Rejection Based on Packet Rank for Congestion Control, management, vol. 1, no. 3, 2012.

2. E. Haripriya, and K. R. Valluvari, A Network survey and a Comparative Study of Multicast Routing Techniques in Disconnected Adhoc, International journal of scientific research engineeering & Technology vol. 2, no. 4, pp. 237-241, 2013.

3. F. Wu, Y. Sun, Y. Yang, K. Srinivasan, and N. B. Shroff, Constant Delay and Constant Feedback Moving Window Network Coding for Wireless Multicast: Design and Asymptotic Analysis, arXiv preprint arXiv:1404.3438, 2014.

4. K. Mokhtarian, and H.-A. Jacobsen, "Minimum-delay overlay multicast." pp. 1771-1779.

5. J. Qadir, A. Baig, A. Ali, and Q. Shafi, Multicasting in cognitive radio networks: Algorithms, techniques and protocols, Journal of Network and Computer Applications, vol. 45, pp. 44-61, 2014.

6. S. Bongyong, "Multicast communications within a wireless communications network," Google Patents, 2013.

7. D. Jiang, W. Li, and Z. Chen, "An Algorithm of Minimum Energy Multicast Based on Network Coding." pp. 1-4.

8. H. Lagercrantz, "Multicasting in an online gaming system," Google Patents, 2014.

9. K. Jain, and M. Mahdian, Cost sharing, Algorithmic game theory, pp. 385-410, 2007.

10. R. Ahlswede, N. Cai, S. Y. R. Li, and , and R. W. Yeung, Network information flow. Information Theory, Theory, IEEE Transactions on, vol. 46, no. 4, pp. 1204-1216, 2000.

11. A. A. Ajibesin, N. Ventura, H. A. Chan, A. Murgu, and O. K. Egunsola, "Performance of Multicast Algorithms Over Coded Packet Wireless Networks." pp. 596-600.

12. D. M. Mani, Secure Multicasting for Wireless Sensor Networks,

    IJCSNS, vol. 14, no. 11, pp. 70, 2014.

13. Bassoli R, Hugo Marques, Jonathan Rodriguez, Kenneth W. Shum, and R. Tafazolli, Network Coding Theory: A Survey, IEEE COMMUNICATIONS SURVEYS & TUTORIALS,, vol. 15, no. 4, 1950-1978, 2013.

14. C. Fragouli, and E. Soljanin, Network coding fundamentals: Now Publishers Inc, 2007.

15. S. Y. Li, R. W. Yeung, and N. Cai, Linear network coding, Information Theory, IEEE Transactions on, vol. 49, no. 2, pp. 371- 381, 2003.

16. C. E. Shannon, Communication in the Presence of Noise., Proc. IRE, vol. 37, no. 1, pp. 10-21, 1949.

17. C. E. Shannon, A Mathematical theory of Communication, Proc. IRE, vol. 27, pp. 379-423, 1948.

18. J. Cheriyan, and B. Laekhanukit, Approximation Algorithms for Minimum-Cost k-(S,T) Connected Digraphs, SIAM Journal on Discrete Mathematics, vol. 27, no. 3, pp. 1450-1481, 2013.

19. H. Ackermann, H. Ralglin, and B. Valcking, On the impact of combinatorial structure on congestion games, Journal of the ACM (JACM), vol. 55, no. 6, pp. 25, 2008.

20. L. S. Lasdon, Optimization theory for large systems: Courier Corporation, 2013.

21. J. Lee, and S. Leyffer, Mixed integer nonlinear programming: Springer Science & Business Media, 2011.

22. S. Bongyong, H. Gill, M. Gurelli, and R. A. Attar, "Multicasting within a wireless communications system," Google Patents, 2014.