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 生成的大型实际网络的广泛模拟。 ***拟议的研究计划将研究计算机网络中并行和分布式计算的消息传播问题。在各种信息传播模型下将考虑不同的并行和分布式原语，例如路由、广播、多播和八卦。 ** **