All-to-all (ATA) reliable broadcast is the problem of reliably distributing information from every node to every other node in point-to-point interconnection networks. A good solution to this problem is essential for clock synchronization, distributed agreement, etc. We propose a novel solution in which the reliable broadcasts from individual nodes are interleaved in such a manner that no two packets contend for the same link at any given time-this type of method is particularly suited for systems which use virtual cut-through or wormhole routing for fast communication between nodes. Our solution, called the IHC Algorithm, can be used on a large class of regular interconnection networks including regular meshes and hypercubes. By adjusting a parameter /spl eta/ referred to as the interleaving distance, we can flexibly decrease the link utilization of the IHC algorithm (for normal traffic) at the expense of an increase in the time required for ATA reliable broadcast. We compare the IHC algorithm to several other possible virtual cut-through solutions and a store-and-forward solution. The IHC algorithm with the minimum value of /spl eta/ is shown to be optimal in minimizing the execution time of ATA reliable broadcast when used in a dedicated mode (with no other network traffic).
展开▼
机译:全面(ATA)可靠广播是在点对点互连网络中将信息从每个节点可靠地分发到每个其他节点的问题。一个良好的解决方案对于时钟同步,分布式协议等至关重要。我们提出了一种新颖的解决方案,其中对来自各个节点的可靠广播进行交织,使得在任何给定时间都没有两个数据包争用同一条链路,这种类型的方法特别适用于使用虚拟直通或虫洞路由来实现节点之间快速通信的系统。我们的解决方案称为IHC算法,可用于包括常规网格和超立方体在内的一大类常规互连网络。通过调整称为交错距离的参数/ spleta /,我们可以灵活地降低IHC算法(对于正常流量)的链路利用率,但以增加ATA可靠广播所需的时间为代价。我们将IHC算法与其他几种可能的虚拟直通解决方案以及存储转发解决方案进行了比较。当在专用模式下使用(无其他网络流量)时,最小值为/ spl eta /的IHC算法在最小化ATA可靠广播的执行时间方面表现出最佳。
展开▼