Optimal message dissemination problems in graphs

图中的最优消息传播问题

• 批准号: RGPIN-2015-05107
• 负责人: Harutyunyan, Hovhannes
• 金额: $ 1.31万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=676923
• 关键词: Optimal; message; dissemination; problems; graphs

Nowadays, Computer networks, from local area networks to the Internet, have become essential in many aspects of modern society. The main purpose of these networks, is to share and spread information. Efficient communication becomes particularly important when a computer network supports a distributed file or database system, where large amount of information needs to be disseminated among the computers in the network. The performance of the information dissemination often determines the efficiency of a whole network or a parallel system. Many different information dissemination problems for efficient message dissemination are considered in practical networks. Therefore, based on this differnt theoretical models for message dissemination are considered  by placing constraints on the amount of information available for each processor, number of senders and receivers, length of the message, capacity of the links and and different processors, transmission or processing delay, the number and the different type of faulty links, the number of messages, etc.  New challenges appear with the advancement of wireless and ad-hoc networks. Efficient communication in such networks require the design of message dissemination algorithms where the nodes do not have knowledge of the global network. Moreover, the nodes only have a limited knowledge of their local neighborhood. Considering the size of internet and other large-scale networks make efficient communication under the above constraints very challenging. All these problems therefore require careful mathematical analysis and algorithmic tools to overcome these challenges. My research proposal will investigate all the above research challenges. The proposed research program will be a continuation of my research work done at Concordia university since 2001. The research work will span from investigating pure combinatorial properties of the main communication parameters to efficient algorithm design and their actual implementation on commonly used interconnection networks in the literature and also extensive simulations on large practical networks generated by well-known network simulator NS-2. ***The proposed research program will investigate message dissemination problems in computer networks for parallel and distributed computing. Different parallel and distributed primitives such as routing, broadcasting, multicasting and gossiping will be considered under various information dissemination models. *** **

如今，计算机网络，从局域网到互联网，已成为现代社会的许多方面必不可少的。这些网络的主要目的是共享和传播信息。当计算机网络支持分布式文件或数据库系统时，其中大量信息需要在网络中的计算机之间传播时，有效的通信变得特别重要。信息传播的性能往往决定了整个网络或并行系统的效率。在实际的网络中，人们考虑了许多不同的信息传播问题，以实现有效的信息传播。因此，在此基础上，通过对每个处理器可用的信息量、中继器和接收器的数量、消息的长度、链路和不同处理器的容量、传输或处理延迟、故障链路的数量和不同类型、消息的数量、随着无线和自组织网络的发展，出现了新的挑战。在这样的网络中的有效通信需要设计的消息传播算法的节点不具有全球网络的知识。此外，节点仅具有其局部邻域的有限知识。考虑到互联网和其他大规模网络的规模，在上述限制下进行有效通信非常具有挑战性。因此，所有这些问题都需要仔细的数学分析和算法工具来克服这些挑战。我的研究计划将调查所有上述研究挑战。这项研究计划将是我自2001年以来在肯考迪亚大学所做研究工作的延续。研究工作将跨越从调查的主要通信参数的纯组合属性，以有效的算法设计和它们的实际实现常用的互连网络在文献中，也广泛的模拟大型实际网络所产生的知名网络模拟器NS-2。* 拟议的研究计划将调查并行和分布式计算的计算机网络中的消息传播问题。不同的并行和分布式原语，如路由，广播，组播和流言将被认为是在各种信息传播模型。*** **