• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Peer-to-peer networking and applications >Sparse structures for searching and broadcasting algorithms over internet graphs and peer-to-peer computing systems
【24h】

Sparse structures for searching and broadcasting algorithms over internet graphs and peer-to-peer computing systems

机译：用于通过Internet图和对等计算系统搜索和广播算法的稀疏结构

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In a broadcasting problem, a message is sent from a source to all the other nodes in the network. Blind flooding is a classical mechanism for broadcasting, where each node retransmits received message to all its neighbors. Despite its important advantages, an increase in the number of requests or the network size or density produces communication overheads that limit the scalability of blind flooding, especially in networks with dynamic topologies. Theoretically optimal solution is based on minimal spanning trees (MST), but its construction is expensive. We discuss here protocols based on local knowledge and newly proposed sparse structures. In weighted RNG (Relative Neighborhood Graph), messages are forwarded only on links which are not the ‘longest’ in any triangle. In weighted RNGQ, messages are forwarded to links which are not the longest in any triangle or quadrangle. Each node constructs weighted MST based on its 2-hop knowledge. Weighted LMST (Localized LMST) preserves only edges that are selected by both endpoints, and messages are forwarded on these links. Any available metric, such as delay, reliability, reputation etc. can be used as weight. Analysis and simulation show that weighted RNG performs better than existing Flooding and Rumor Mongering (or Gossip) schemes. The parameterless weighted LMST, MST, RNG and RNGQ (RNG over Quadrangle) based broadcasting schemes are compared, showing overall advantage for LMST. We also hint that a number of existing protocols can be simplified by applying concept from this article.
机译：在广播问题中，消息从源发送到网络中的所有其他节点。盲洪是广播的一种经典机制，其中每个节点将接收到的消息重新发送到其所有邻居。尽管具有重要优势，但请求数量或网络大小或密度的增加都会产生通信开销，从而限制盲目泛洪的可伸缩性，尤其是在具有动态拓扑的网络中。从理论上讲，最佳解决方案基于最小生成树（MST），但其构建成本很高。我们在这里讨论基于本地知识和新提出的稀疏结构的协议。在加权RNG（相对邻域图）中，仅在不是三角形中“最长”的链接上转发邮件。在加权RNGQ中，消息被转发到不是任何三角形或四边形最长的链接。每个节点都基于其2跳知识构造加权MST。加权LMST（本地化LMST）仅保留两个端点选择的边缘，并且消息在这些链接上转发。任何可用的度量标准（例如延迟，可靠性，信誉度等）都可以用作权重。分析和仿真表明，加权RNG的性能要优于现有的Flooding and Rumor Mongering（或八卦）方案。比较了无参数加权LMST，MST，RNG和RNGQ（四边形上的RNG）广播方案，显示了LMST的总体优势。我们还暗示可以通过应用本文中的概念来简化许多现有协议。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号