الگوریتم اکتشافی سریع و کارآمد برای تاخیر و تنوع در مسئله درخت محدود چند کاربره

More and more multicast communications are becoming real-time. In real-time communications, messages must be transmitted to their destination nodes within a certain amount of time; otherwise the messages will be rendered futile. To support real-time multicast communications, computer networks have to guarantee an upper bound on the end-to-end delay from the source node to each of the destination nodes. This is known as the multicast end-to-end delay problem[10]. On the other hand, if the same message fails to arrive at each destination node at the same time, there will probably arise inconsistency or unfairness problem among users. This is related to the multicast delay variation problem[10]. Our research subject in the present paper is concerned with the minimization of multicast delay variation under the multicast end-to-end delay constraint. The problem is first defined and discussed in Ref. [10]. They have proved it to be an NP-complete problem and proposed a heuristic algorithm for it called DVMA (Delay Variation Multicast Algorithm). In this paper, we find that in spite of DVMA's smart performance in terms of multicast delay variations, its time complexity is as high as O(klmn4). It is strongly believed that such a high time complexity does not fit in modern high-speed computer network environment. Therefore, we will present an alternative heuristic algorithm with a much lower time complexity O(mn2) and with a satisfactory performance. Computer simulations also testify that our algorithm is both fast and efficient.

With the advancement in computer network technology, the applications of computer networks are becoming diverse, such as videoconferencing and on-line activities: shopping, game playing, and stock market screening and exchange. The new growth in network applications has boosted new requirements in communication modes, one of which is the provision of multicast communications [1], [5], [7] and [10]. In order to satisfy such a demand, several well-developed multicast routing protocols have been proposed to elevate the efficiency of network resources, including Distance-Vector Multicast Routing Protocol, Multicast Extensions to Open Shortest Path First, and Protocol-Independent Multicast [7]. Before transmitting multicast messages, most multicast routing protocols will establish a set of multicast paths called a multicast tree for efficiently transmitting the messages to individual destination nodes. The overall performance of a multicast routing protocol will largely depend on the efficiency of its multicast tree. Therefore, how to build an efficient multicast tree has become an important research topic in multicast communications. There has been plenty of literature dwelling on ways to establish competent multicast trees [7]. One of the most often considered multicast trees is referred to as the minimum cost multicast tree. (Every link in the multicast tree has a nonnegative cost. The cost of the multicast tree is defined as the sum of the costs of all the links in the entire multicast tree.) The minimum-cost multicast tree is also known as the Steiner tree [4], and finding such a tree is a famous NP-complete problem [6]. In real-time communications, messages must be transmitted to their destination nodes within a certain amount of time; otherwise the messages will be nullified. Videoconferencing and on-line game playing, for example, must receive fresh images and sounds. Even if the image or voice delays only several seconds, the user will become impatient. Another real-time demand is found in on-line stock market exchange, which tolerates absolutely no time delay in message transmissions or commercial transactions. To support real-time multicast communications, computer networks have to guarantee an upper bound on the end-to-end delay from the source node to each of the destination nodes. This is known as the multicast end-to-end delay problem[10]. Suppose that the same message fails to arrive at each destination node at the same time. Inconsistency or unfairness problems will arise among users. For example, in a distributed database system, if the workstations receive the same message asynchronously, their calculation results may be incongruous. Another possible dispute is found in on-line video gaming where several game participants connected with a game server do not receive the images and messages simultaneously. Third, in on-line shopping, if the messages are received among purchasers at a drastically asynchronous pace, the prospective buyers will lose faith and turn off. These are all related to the multicast delay variation problem[10]. The above examples reveal the command that the delay variation among all the paths from a source node to each of the destination nodes has to be kept within a definite limit. Our research subject is concerned with the minimization of multicast delay variation under multicast end-to-end delay constraint. To be more specific, given a computer network, a source node, and a set of destination nodes, the mission is to find a multicast tree (namely a set of multicast paths) with the source node as the ‘root’ and the destination nodes as the ‘leaves’ so that the multicast end-to-end delay between the source node and each of the destination nodes may fall within a tolerable range, and the multicast delay variation among the destination nodes may be the smallest. As shown in Fig. 1, there are two paths between source node vs and destination node v1. Their end-to-end delays are 16 and 21, respectively. There are also two paths between source node vs and destination node v2. Their end-to-end delays are 19 and 10, respectively. If we merely consider multicast end-to-end delay constraint and set the permitted upper bound to be 19, then the selected path between vs and v1 should be that with delay 16, and the selected path between vs and v2 should be that with delay 10. Suppose, only the minimization of multicast delay variation rather than multicast end-to-end delay constraint is considered. The selected path from vs to v1 then should be that with delay 21; the selected path from vs to v2 should be that with delay 19. The resulted multicast delay variation is 2, which is also the optimum value. Finally, if the multicast delay variation is to be minimized under multicast end-to-end delay constraint, and the permitted upper bound of the multicast end-to-end delay is set to be 19, the selected path from vs to v1 should be that with delay 16; the selected path from vs to v2 should be that with delay 19. The resulted multicast delay variation is 3, which is the optimum value under our multicast end-to-end delay constraint.The issue first defined and discussed in Ref. [10] is that of minimizing multicast delay variation under multicast end-to-end delay constraint. The authors referred to this problem as the delay- and delay variation-bounded multicast tree (DVBMT) problem. They have proved it to be an NP-complete problem and proposed a heuristic algorithm called DVMA (Delay Variation Multicast Algorithm). In Ref. [11] we have further proved that unless NP is equal to P, the DVBMT problem does not have any ε_approximation algorithm, where ε is a constant. Therefore, for the time being, the best way to evaluate any heuristic algorithm for the DVBMT problem is through computer simulations. In this paper, we find that in spite of DVMA's smart performance in terms of the multicast delay variation, which was demonstrated by computer simulations [2] and [10], its time complexity is as high as O(klmn4), where in the worst case, the maximum value that parameters k and l can take is equal to the maximum number of paths of delay at most Δ (Δ denotes the given multicast end-to-end delay constraint) between any two nodes in the computer network; m represents the number of destination nodes, while n represents the number of nodes in the computer network. We strongly believe that such a high time complexity does not fit in modern high-speed computer network environment. Therefore, our paper presents an alternative heuristic algorithm with a much lower time complexity O(mn2) along with a satisfactory performance. Computer simulations verify our claim that our algorithm is both fast and efficient. The rest of the paper is organized as follows. In Section 2, the definition and complexity of the DVBMT problem are given. In Section 3, a fast and efficient heuristic algorithm with its analysis in time complexity is proposed. In Section 4, a comparison will be made among the performances of the Shortest Path Tree Algorithm, the Minimum Spanning Tree Algorithm, the Steiner Tree Algorithm, DVMA, and our heuristic algorithm. Lastly, Section 5 concludes the whole research.

In this paper, we discuss the DVBMT problem, which has been proved to be NP-complete and possessed a heuristic algorithm DVMA [10]. In spite of DVMA's smart performance in terms of the multicast delay variation, its time complexity is as high as O(klmn4). We strongly believe that such a high time complexity does not fit in modern high-speed computer network environment. Therefore, based on the ideas from CBT and the minimum delay path algorithm, we have presented an alternative heuristic algorithm DDVCA with a much lower time complexity O(mn2) and with a satisfactory performance. Computer simulations also evaluate our algorithm in terms of multicast delay variations, multicast end-to-end delays and execution time. The simulation results show that our algorithm performs very well in all the three aspects.