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.