Optimal message dissemination problems in graphs

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

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.