Optimal message dissemination problems in 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. *** **