Efficient multicast search under delay and bandwidth constraints

The issue of a multicast search for a group of users is discussed in this study. Given the condition that the search is over only after all the users in the group are found, this problem is called the Conference Call Search (CCS) problem. The goal is to design efficient CCS strategies under delay and bandwidth constraints. While the problem of tracking a single user has been addressed by many studies, to the best of our knowledge, this study is one of the first attempts to reduce the search cost for multiple users. Moreover, as oppose to the single user tracking, for which one can always reduce the expected search delay by increasing the expected search cost, for a multicast search the dependency between the delay and the search cost is more complicated, as demonstrated in this study. We identify the key factors affecting the search efficiency, and the dependency between them and the search delay. Our analysis shows that under tight bandwidth constraints, the CCS problem is NP-hard. We therefore propose a search method that is not optimal, but has a low computational complexity. In addition, the proposed strategy yields a low search delay as well as a low search cost. The performance of the proposed search strategy is superior to the implementation of an optimal single user search on a group of users. Amotz Bar-Noy received the B.Sc. degree in 1981 in Mathematics and Computer Science and the Ph.D. degree in 1987 in Computer Science, both from the Hebrew University, Israel. From October 1987 to September 1989 he was a post-doc fellow in Stanford University, California. From October 1989 to August 1996 he was a Research Staff Member with IBM T. J. Watson Research Center, New York. From February 1995 to September 2001 he was an associate Professor with the Electrical Engineering-Systems department of Tel Aviv University, Israel. From September 1999 to December 2001 he was with AT research labs in New Jersey. Since February 2002 he is a Professor with the Computer and Information Science Department of Brooklyn College - CUNY, Brooklyn New York. Zohar Naor received the Ph.D. degree in Computer Science from Tel Aviv University, Tel Aviv, Israel, in 2000. Since 2003 he is with the University of Haifa, Israel. His areas of interests include wireless networks, resource management of computer networks, mobility, search strategies, and multiple access protocols.     

WCDMA的MBMS技术

主要介绍了基于WCDMA的MBMS技术,给出了其网络架构和技术难点,并对其应用给无线网络带来的影响作了一定深度的探讨。     

基于组播通信的交通通信网络研究

研究交通通信网络,提高网络的吞吐量和数据传输效率。针对传统的单播组网中通信发送者需要多次复制相同的数据包以满足多个接受者同时提出的数据请求,随着数据请求的增多使得发送者的通信负担加重,造成网络拥塞、吞吐量不高的问题。为了解决上述难题,提出基于组播通信的交通通信网络的组网方法。采用Mesh结构构建交通通信网络的组播模型,使得网络节点之间建立有线或无线的连接,然后利用网络编码算法实现网络间的通信,使得源点只需发送一次就可向多个终点成功传输相同的数据。实验表明,组网方法能够有效解决数据请求过多时网络吞吐量不高的问题,同时提高了数据传输的效率,取得了满意的结果。     

基于Agent的移动组播算法的优化

随着科学技术的飞速发展,作为网络信息领导者的移动通信在日常生活工作中的应用也越来越广泛,但是移动通信在应用中也会遇到很多问题,比如移动网络切换延迟现象较为普遍,组播包的丢包率比较高等等.本文针对于以上问题,分析了多种组播协议,提出了新型的基于Agent的移动组播算法,此算法可以有效地改进切换延迟和丢包率等问题.     

组播环境下IPTV快速频道切换方法

为解决组播网络中基于网际互连协议的电视(IPTV)频道切换时间过长的问题,提出一种在组播环境下IPTV快速频道切换的方法. 该方法利用终端的上传带宽,为其他终端提供快速的数据流,在短时间内充满频道切换终端播放缓存,可减少频道切换时间. 理论分析与仿真验证的结果表明,在较高频道切换频率下,该方法用不足20%的新增带宽,使频道切换时间减小到原有的15%～45%.     

网络协议电视频道快速切换研究

网络协议电视（Internet Protocol Television,IPTV）已经成为新一代网络（Next Generation Net-work,NGN）中最具潜力的应用,主要由于其具有随时随地都能发送电视节目的特性。随着IEEE 802.16d/e的规格制订,它具有高带宽及低延迟的能力,因此适合作为发送多媒体串流的服务。此外,它也提供讯号高涵盖率、行动性支持以及非视线功能。我们可以利用IEEE 802.16d/e提供发送IPTV串流的媒介,并提出一个简单但却有效的IPTV频道切换算法以维持频道切换的时间在一个可容许的范围内。提出的算法根据热门频道及个人化频道的预载,以减少因为网络传输所造成的延迟,达到快速切换频道的目的。最后,通过实验结果证实算法的效能。     

一种求解QoS约束组播路由问题的遗传算法*

针对多维QoS约束的组播路由问题,提出了一种基于遗传算法的解决方案QCMRA-GA(GA of QoS Constraints Multicast Routing Algorithm).该算法对经典遗传算法的三大算子进行了重新设计,有效地克服了遗传算法的早熟现象.对染色体进行Prufer树型编码,可以避免回路的产生,并根据编码特性,进行基于叶子节点和Steiner节点的解空间压缩,提高了算法的收敛速度.实验表明QCMRA-GA的正确性和效率性.     

一种基于网络编码的组播路由算法

网络编码是2000年提出的一种新算法,其主要优点是使组播传输速率能达到理论上限值.介绍了传统组播路由算法的局限性,分析了现有网络编码算法的优点和不足,在某个改进的网络编码数学模型上,提出了一种静态分布式分层网络编码SDLNC算法(Static Distributed Layered Network Coding).模拟实验表明,该算法可以显著提高组播路由的数据传输速率.     

Multicast routing in mobile ad hoc networks by using a multiagent system

Multicast routing in mobile ad hoc networks (MANETs) poses several challenges due to inherent characteristics of the network such as node mobility, reliability, scarce resources, etc. This paper proposes an Agent Based Multicast Routing Scheme (ABMRS) in MANETs, which uses a set of static and mobile agents. Five types of agents are used in the scheme: Route manager static agent, Network initiation mobile agent, Network management static agent, Multicast initiation mobile agent and Multicast management static agent. The scheme operates in the following steps: (1) to identify reliable nodes; (2) to connect reliable nodes through intermediate nodes; (3) to construct a backbone for multicasting using reliable nodes and intermediate nodes; (4) to join multicast group members to the backbone; (5) to perform backbone and group members management in case of mobility. The scheme has been simulated in various network scenarios to test operation effectiveness in terms of performance parameters such as packet delivery ratio, control overheads and group reliability. Also, a comparison of proposed scheme with MAODV (Multicast Ad hoc on-demand Distance Vector) protocol is presented. ABMRS performs better than MAODV as observed from the simulation. ABMRS offers flexible and adaptable multicast services and also supports component based software development.     

An Online Algorithm for the Dynamic Maximal Dense Tree Problem

Abstract. The Online Maximal Dense Tree problem is as follows: given a weighted directed graph and a source node, users issue online requests for connection to the source node. A request can either be accepted or rejected (the admission control decision). If the connection request is accepted, it must be connected to the source or to a node previously connected to the source (the routing decision). The objective is to maximize the total number of connections while keeping the connection density , i.e. the ratio of accepted requests to the weight of the spanning tree, sufficiently high. The primary motivation for the Maximal Dense Tree problem is the Online Capacitated Multicast admission control and routing problem. In the Online Capacitated Multicast problem, we are given a communication network with limited link capacities and a set of signal source nodes. Users generate online requests for connection to the signal sources, and the network administrator has to make the admission control and routing decisions. The goal of the network administrator is to maximize the total number of users connected subject to the network capacity constraints. The Online Maximal Dense Tree problem is also faced by a cable TV operator who wishes to connect as many customers as possible while keeping down the amount of wiring per customer. Informally, the Online Maximal Dense Tree algorithm must ``gamble' on certain geographic areas, connecting nodes which are unprofitable to start with, in the hope that eventually enough requests will arrive in its vicinity to make the investment profitable. In this paper we present a randomized online algorithm for the Maximal Dense Tree problem that guarantees acceptance of a (1- ɛ) factor of the requests accepted by the optimum offline algorithm with the expectation of density being at most polylogarithmically lower than that of the offline algorithm. This yields an online capacitated multicast algorithm whose throughput is only poly-logarithmically lower than that of the optimum offline algorithm. Previous work on multicast routing and maximal dense tree problems either made probabilistic assumptions or resulted in linear performance gaps with the offline algorithm. Attempts to solve the Online Maximal Dense Tree problem have also lead to the development of the first polylogarithmic approximation algorithms for the k -MST and the Prize Collecting Salesman problems [AABV].