基于交换式以太网的容错原子广播研究

论文摘要

随着计算机及网络技术的日益发展,分布式系统或并行计算环境及应用得到了越来越多的重视与研究。分布式系统或并行计算环境常需要可靠的广播通信来保证分布式进程间的相互通信与协作,如分布式数据库、容错的分布式目录服务等。 可靠的广播通信在分布式系统中发挥着必不可少的作用,在过去的数十年间,提出了多种可靠广播算法,并在可靠广播算法的基础上发展出了顺序广播算法、容错的广播算法和原子广播算法等。 由于可靠广播通信在计算机及网络应用领域的重要性,出现和提出了多种适用于不同环境和条件下的可靠广播算法,如适用于并行集群计算中集合通信的可靠广播算法,适用于超立方体网络体系结构的可靠广播算法和适用于移动Ad hoc无线局域网的可靠广播算法等。 与此同时,以太网的交换技术也得到了突飞猛进的提高,出现了可编程交换机、第三层交换和四层交换等。交换式以太网以其传统的共享式以太网所不具备的优势,应用范围得到了不断的扩大。现在交换式以太网被越来越多地运用到过程控制、工业自动化和其他支持高带宽的实时通信应用中去。 在交换式以太网中,为了解决“广播风暴”这一在二层数据网络中存在弊端,IEEE制定了802.1d的分布式生成树算法,定义了MAC层路由方式。运行生成树算法的由交换机组成的通信系统会组成一个生成树动态拓扑结构,该拓扑结构使局域网内任意两个交换机之间不存在回路,以防止由此产生的局域网广播风暴。 本文提出一种新的基于交换式以太网体系结构的容错原子广播算法,主要利用运行生成树协议的交换机维护的有关系统中交换机的树型动态拓扑结构信息,进行基于树型拓扑的逻辑令牌环的维护和令牌传递。以批广播和批应答的方式来降低单个进程广播和广播确认占用的通信系统带宽,从而向上层应用提供容错的原子广播。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 论文选题以研究意义
• 1.2 国内外研究现状
• 1.3 论文研究的主要内容
• 1.4 小结
• 2 分布式系统与分布式系统通信
• 2.1 分布式系统
• 2.2 分布式系统通信
• 2.3 小结
• 3 广播算法研究
• 3.1 可靠广播算法
• 3.2 容错广播算法
• 3.3 原子广播算法
• 3.4 小结
• 4 交换式以太网
• 4.1 交换式以太网
• 4.1.1 交换式以太网的特点
• 4.1.2 以太网交换机的工作原理
• 4.1.3 以太网交换机的发展
• 4.2 可编程交换机
• 4.3 LLC逻辑链路控制子层
• 4.4 生成树协议（SPT:spanning tree protocol）
• 4.4.1 以太网交换机体系结构
• 4.4.2 生成树算法
• 4.4.3 生成树算法研究
• 4.5 小结
• 5 令牌环协议
• 5.1 令牌环网
• 5.2 令牌总线网
• 5.3 小结
• 6 树的遍历
• 6.1 树型拓扑和二叉树
• 6.2 二叉树遍历
• 6.3 小结
• 7 基于交换式以太网的容错原子广播
• 7.1 系统模型
• 7.2 基本思想
• 7.3 FAB
• 7.4 消息类型
• 7.5 拓扑结构
• 7.6 逻辑令牌环配置
• 7.6.1 逻辑令牌环配置
• 7.6.2 TCM
• 7.6.3 TCM传递
• 7.6.4 TCM的计算
• 7.6.5 TCM传递的伪代码描述
• 7.7 令牌传递
• 7.7.1 广播消息（BM）：
• 7.7.2 令牌：
• 7.7.3 A／D字段：
• 7.7.4 令牌更新：
• 7.8 小结
• 8 算法实现
• 8.1 结点xFAB
• 8.2 终端的通信子系统
• 8.3 算法描述
• 8.4 小结
• 9 广播的容错原子性证明
• 9.1 广播原子性证明
• 9.2 容错的证明
• 9.2.1 系统错误类型
• 9.2.2 容错
• 9.3 小结
• 10 算法性能分析
• 11 结论与展望
• 11.1 总结
• 11.2 下一步工作
• 致谢
• 参考文献
• 附录