ABSTRACT
Minimum cost of multicast is the process of finding the node transmission cost such that the total cost of bandwidth used for sending messages from source to any destination nodes is minimized. The Network Coding Algorithm(NCA) was developed using linear programming framework by considering packets delay as the only key performance metrics. This research work is based on Shannon Hartley channel capacity theorem aimed at interpreting the cost of bandwidth within the channel and this was achieved by considering more performance metrics that affect the channel. Loss and delay of packetare collectively considered and later delay, loss and rejection packet are also considered on the Network Coding Algorithm. The problem was formulated as optimization problem using mixed integer linear programming problem. Simulation results showed that the average cost of bandwidth decrease as more performance metrics are collectively considered. When two performance metrics of delay and loss are considered collectively, there was a reduction in the average cost of bandwidth used during multicast by 27%, 28.7%, 29.5%, 20.9% 18.5%, 23.8%, 21.6% and 20.9% for 20, 30, 40, 50, 60 and 70 randomly generated nodes multicasting to groups of receivers when compared with the benchmark algorithm of delay only. Similarly, considering three performance metrics (delay, loss and rejection) achieved a reduction in the average cost of bandwidth by 37.07%, 37.6%, 41.15, 29%, 30% and 35.3% for 20, 30, 40, 50, 60 and 70 randomly generated nodes multicasting to various groups of receivers as compared with benchmark algorithm. Equally, results also showed that the average cost of bandwidth for NCA with three performances parameters decreases for 12.7%, 13.6%, 16.6%, 11.1%, 16.3% and 15.1% for all the number of randomly generated nodes as compared to a situation when two performance metrics are considered. From the results obtained, it can be observed that the cost of bandwidth with 40 randomly generated nodes recorded the highest decrease in the average cost of bandwidth because the cost of multicast for NCA, INCA with two and three performance metrics tends to be linear and increase as the number of receivers increases.From these results, it could be concluded that the more performance metrics considered in the NCA, the better the true picture of the channel is represented. When interpreting the cost of bandwidth using Shannon-Hartley channel capacity theorem, the study established that the cost of bandwidth within the channel was under estimated as more performance metrics are considered.
TABLE OF CONTENTS
TITLE PAGE i
DECLARATION ii
CERTIFICATION iii
DEDICATION iv
ACKNOWLEDGEMENT v
CONTENTS ix
LIST OF FIGURES xi
LIST OF TABLES xiii
LIST OF ABBREVAITION xiv
ABSTRACT xv
CHAPTER ONE: INTRODUCTION
1.1 BACKGROUND OF THE STUDY 1
1.1.1 Multicasting Basics 5
1.1.2 Multicast Group 6
1.1.3 Multicast Goals 6
1.2 STATEMENT OF PROBLEM 7
1.3AIM AND OBJECTIVES 7 1.4 METHODOLOGY 8 1.5SIGNIFICANT OF THE RESEARCH 9 1.6DISSERTATION ORGANIZATION 9 CHAPTER TWO: LITERATURE REVIEW 2.1 INTRODUCTION 10 2.2 REVIEW OF FUNDAMENTAL CONCEPTS 10
ix
2.2.1 Techniques used for Wireless Multicasting 10 2.2.1.1 Network Coding Techniques 10 2.2.1.2 Random Linear Network Coding (RLNC) 14 2.2.1.3 Opportunistic Network Coding 16 2.2.2Optimization 16 2.2.2.1 Optimization Approaches 17 2.2.3Multicasting in wired and wireless Networks 19 2.2.4Multicast Routing 21 2.2.4.1 Shortest Path Tree Algorithm 21 2.2.4.2 Minimum cost Tree Algorithms 22 2.2.5 Multicasting in Coded Packet Networks 22 2.2.5.1 The Multicast Network Model 24 2.2.6Performance Metrics that Affects Multicast 27 2.2.7Shannon-Hartley Channel Capacity Theorem 29 2.2.8 Review of the Existing Network Coding Algorithm 30 2.2.9 The Improved Network Coding Algorithm 31 2.3 REVIEW OF SIMILAR WORKS 32 CHAPTER THREE: METHODS AND MATERIALS 3.1 INTRODUCTION 40 3.2 MATHEMATICAL MODELS FOR MINIMUM COST OF MULTICAST 40 3.2.1 Cost Optimization in Coded Packet Wireless Networks 41 3.2.2 Mixed Integer Linear Programming Formulation 42 3.3COMPARATIVE ANALYSES OF NCA AND THE INCA 50
x
3.4 INSTALLATION AND CONFIGURATION 51 3.5 SIMULATION 51 3.5.1 Simulation Parameters 52 CHAPTER FOUR: RESULTS AND DISCUSSION 4.1 INTRODUCTION 54 4.2PERFORMANCE EVALUATION OF THE TWO ALGORITHMS54 4.3 PERFORMANCE EVALAUTION OF THREE ALGORITHMS 61 CHAPTER FIVE: CONCLUSION AND RECOMMENDATION 5.1 INTRODUCTION 69 5.2 CONCLUSION 69 5.3 SIGNIFICANT CONTRIBUTION 70 5.4 LIMITATIONS 71 5.4 RECOMMENDATIONS FOR FUTURE WORK 71 REFERENCES 72
APPENDIX A: Code 80 APPENDIX B: Formation of A_Z Matrix 82 APPENDIX C: The Main Algorithm 86 APPENDIX D: The Network Coding Algorithm 89 APPENDIX E: Formation of A_Z Matrix (with three parameters) 99 APPENDIX F: Test file of the Randomly Generated Nodes by the MIPA 95
xi
CHAPTER ONE
INTRODUCTION 1.1 BACKGROUND
The process of routing messages from a source to a set of destination nodes is known as multicast (Wen & Liao, 2010). According to Xuan and Lea (2011), Multicast video streaming and video conferencing is speedily becoming a key requirement of many computer networks supporting numerous multimedia applications. In multicast, a single message is delivered to a cluster of destination in a network and this concepts has been studied for both wired and wireless networks (Lertpratchya et al., 2014). Multicast as a means of communication is an essential part of many next generation networks and there are limited numbers of network usersthat support multicast in the Internet today. This has made it necessary for applications requiring multicast services to obtain services at a higher standard. Also, according to Chopra and Mishra (2012), 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, (Han et al., 2014; Haripriya & Valluvari, 2013; Wu et al., 2014). Ashlwede et al., (2000) showed that multicasting can take place in a situation where two source nodes are simultaneously sending information to different groups of receivers by superposition. Figure 1.1 shows the basic concept of multicasting.
2
Multicast communication is a process of passing information over large networks and it saves a lot of time and resource (Annapurna et al., 2014). Wireless networks has multicast advantage that is, if data is transmitted from node i to node j, all the nodes whose distance i is lesser than j receive the data for free before reaching to the targeted recipient. One of the major challenges of wireless multicast is to be able to support a large number of users while simultaneously taking care of packets delay, packets loss, packets congestion and low feedback overhead (Wu et al., 2014). 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(Mani, 2014). This represents a major cost, and is typically the resource that constrains the number of simultaneous multicast sessions that an overlay network can effectively support(Xuan & Lea, 2011).
Multicasting over wireless networks is a significant but at the same time is a challenging goal in the field of wireless communication networks(Lun et al., 2006).
Receiving node
Receiving node
Receiving node
Internet
Transmitting node
Receiving node
Receiving node
Receiving node
Receiving node
Figure 1.1: Basic Multicasting Concept (Karaoglu & Heinzelman, 2010)
3
Itrequires 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 (Qadir et al., 2014). Providing a trade-off between stability, throughput, delay, and packet loss with reduced bandwidth requirement and less power consumption is the aim of multicasting in both wire line and wireless networks. 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(Zongpeng, 2008). In several scenarios, there is a great challenge of cost allocation with broadcasting most especially when the users are linked to a common source at a minimum cost. 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 (Jain & Mahdian, 2007).
In order to avoid sending several copies of the same message through the same link,multicast routing is used and this can be achieved by using a tree connecting the receivers to the same source. Multicasting in a larger network is always linked with many challenges such as bandwidth and energy consumption, and this is as a result of multiple users who probably have conflicting purposes (Rajkumar, 2014; Ramamoorthy, 2011). It is necessary to note that the expected cost of using any dynamic network might change due to the instability of the multicast members and other factors such as distance, location and differences in continents(Skorin-Kapov, 2001). The problem of finding node transmission cost such that the total cost is minimized as an optimization problem is referred to as minimum cost multicast (Wen & Liao, 2010). Different optimizations goals have been formulated and applied in multicast algorithms to minimize bandwidth and energy consumption, and also to
4
determine what constitutes a good multicast tree. One of such goal is providing minimum delay along the tree, which is an important factor for some multimedia applications such as real time audio and video conferencing. Minimizing the total bandwidth utilization of the links and energy consumption is the goal for all optimization problems for multicast routing algorithms(El Rouayheb et al., 2006).
In network-wide broadcasting the objective is to distribute the generated data to all the nodes in the network. 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(Lagercrantz, 2014). 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 (Lagercrantz, 2014). It would also generate unnecessary data traffic which increases the operating costs. On the other hand, the objective of multicasting is to deliver the data to a subset of the nodes in the network.
There is a multitude of ways to achieve the minimum cost, which depends mostly on the characteristics of the network being used. If routers are only able to forward packets , the weighted shortest paths to each sink are the most cost efficient way of delivering the packets (Ajibesin et al., 2013). Ad-hoc and coded packet networks supports many multicast applications such as distributed data processing, Internet telephone, interactive multimedia conferencing, and real time video broadcasting (Ramamoorthy, 2012; Rashed, 2012). A packet network is a network in which raw information bits are exchanged and most often, voice quality is affected by delay, delay jitter, packet loss and unreliable packet delivery all of which are unusual characteristics of the essential network service.
5
These characteristics lead to variations in packet delivery, which are the most significant concerns of voice over internet (Karthikeyan & Shankar, 2014). Voice over internet protocol (VoIP) is expected to impact on some of the better developments in higher education, for instance, virtual universities, personality management and so on. The fundamental process carried out in a VoIP call are, transformation of the caller‟s analog voice signal into a digital format, compression and transformation of the digital signal into discrete Internet Protocol packets, Transmission of the packets through the Internet or other IP-based network and Reverse transformation of packets into an analog voice signal for the call recipient (Karthikeyan & Shankar, 2014). A multicast group has only one source node and multiple destination nodes; each pair of nodes is connected by a logical edge with the minimum cost between the nodes (Hu & Zhang, 2013). Two models are usually associated with multicast; the node-based model and link based model. The node based model is mostly used during multicasting because single transmission can be heard by several nodes rather than using a link based model where a node transmits separately to each of its neighbors resulting in increased cost of operation (Xiong & Li, 2010). 1.1.1 Multicasting Basics
The basic modules of a multicast routing include sources, receivers, and a group having direct or indirect connections with each other and the opinion of the group is essential to the concept of multicasting. The originator of the data stream is called a „source‟ while the end-user that wishes to receive the data stream is called the „receiver‟. In multicast routing, the source is interested in transmitting its data stream to all the receivers‟ within the multicast group (Qadir et al., 2014). For point-to-
6
multipoint group communication, multicasting comes across as the most efficient means of communication(Lagercrantz, 2014). 1.1.2 Multicast Group
A multicast group is a set of nodes in the networks that share the same piece of information. It can have one or more source nodes, and more than one destination. A multicast group can be static or dynamic. Static group cannot be changed after its creation and it is frequently modeled as a Steiner tree problem. On the other hand, dynamic groups can have members added and removed at any time (Oliveira & Pardalos, 2005). 1.1.3 Multicast Goals
In wireless networks, multicasting can have various performance goals depending on what the user want. In particular it is important to provide high quality of service, cost efficient performance, and to ensure reliability and security (striegel & Manimaran, 2002). In many applications such as teleconferencing, distance learning, and online shopping exploit multicast transmissions while requiring a certain minimum quality of service for satisfactory performance (Paschos et al., 2014). In other to support such applications, a network support for scalable group-based applications with strict quality of service requirement becomes paramount. Various performance metrics (such as packet delay, delay jitter, packet loss, throughput, packet congestion e.t.c) can be used to quantify the quality of service (Wenzhong & Zhenyu, 2013). Ensuring reliability and security in multicast routing is an important goal for multicast protocols(Lagercrantz, 2014).
7
1.2 STATEMENT OF PROBLEM Bandwidth utilization during multicast over coded packet wireless networks has become an area of intensive research in trying to establish the true cost of bandwidth in order to achieve the true picture of the channel. The problem that prompted this intensive research 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 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 research by introducing more performance parameters which affect the channel and particularly bandwidth utilization. To do this, two parameters NCA is used where delay and loss of packets are considered and then that with three metrics of delay, loss and rejection of packets. These are then compared to the NCA of one parameter of delay only to be able to draw a conclusion. 1.3 AIM AND OBJECTIVES The aim of this research is the development of an improved multicast Algorithm for interpreting the cost of bandwidth within the channel using Shannon-Hartley channel capacity theoremby considering more performance metricsthat affect the channel. The objectives of the research are as follows:
i. To examine the effect oftwo and threeperformance metrics of Network Coding Algorithm onmulticasting over coded packet wireless networks.
ii. To develop an INCA by considering more performance metrics that affects the cost of bandwidth within the channel using linear programming framework.
8
iii. To establish the true picture of the channel in terms of the cost of bandwidth in accordance with Shannon Hartley channel capacity theorem when a lesser number of performance parameters are considered in the NCA.
1.4 METHODOLOGY The following methodology is adopted in carrying out this research and is itemized as follows.
i. Determination of performance metrics (packets delay, packets loss, packets congestion, packet rejection and throughput) that critically affects the cost of bandwidth during multicast over coded packet wireless network in order to know the true picture of the channel.
ii. Formulation of the problem as an optimization problem using mixed integer linear programming with suitable constraints so as to improve the performance of the Network Coding based-Algorithm for effective bandwidth utilization during multicast.
iii. Using only two and three performance metrics to improve the performance of existing network coding based-algorithm in order to determine their impact within the channel.
iv. Comparison of the performance of the existing Network Coding Algorithm with the improved Network Coding based-Algorithm using Visual studio 2010 using the same simulation patterns.
v. Validation of the performance of the improved network coding based-algorithm with the existing network Coding algorithm using Matlab 2010b.
9
1.5 SIGNIFICANT OF THE RESEARCH This research is significant in the field of Engineering because over the years, multicasting over wireless network is a great challenge due to the high rate of bandwidth consumption. When the research parameters (loss, delay and rejection of packets) are implemented and controlled in real time, the work will go a long way to minimize the consumption of bandwidth and it will also encourage group communication over the internet. This is what this research is set to achieve. 1.6 DISSERTATION ORGANIZATION Chapter one presents the general introduction. The rest of the chapters are as follows: detailed review of similar works and relevant fundamental concepts pertinent to Minimizing cost of multicast, multicast routing and techniques are presentedin Chapter Two. Mathematical models, formation of the problem as mixed integer linear programming describing the performance metrics considered are presented in Chapter Three. Chapter Four presents results, their analysis and discussions. Conclusion and recommendation are presented in Chapter Five and finally, all the references quoted in this research work and appendices are also provided at the end of the thesis.
Do you need help? Talk to us right now: (+234) 08060082010, 08107932631 (Call/WhatsApp). Email: [email protected].
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
