广域网的超量分形等级结构.pdfVIP

广域网的超星分形等级结构 陈发堂 周宗放扬春德 (重庚邮电学院基础部，重庆490065) 摘要 随着国际化趋势的发展，广域同理论的研究显得越来越重要，本文提出了广域 同舶超星分形结构理{鲁，井讨论其生长、发展的过程，最后，给出谈结构模型的实捌．该 结构模型将是描述互连广域同结构的重要工具． 1引言 并行处理和通信是解决大量科学、技术及实际生活问题的高效自然的方式，其根本问题 是选择恰当的结构以实现多处理机或通信系统中节间的有效互连。现已有大量的文献提出 并讨论了各种各样的互连网络，如总线型、环形结构、纵横式连接、完全图结构、网络结构、 n一立方体、间接n一立方体和混洗交换等，这些网络都是为满足某些特定要求而构造出来的 局域罔结构。超星形(Hyperstar)结构首先是由美籍乌克兰专家马歌尔·阿·诺可夫 (Mikhail．A．Rakov)提出的一种节点优化互连的新方法，该结构也是一种局域网结构。本 文将对其理论基础及生成方法做进一步的讨论。 广域网又称远程，在地理上可跨越很大的距离，可以跨国、跨洲，甚至覆盖全世界。但其 拓扑结构通常都是用局域网结构来代替，例如，我国光纤干线的八横、八纵等。讫今为止，还 没有专门的广域罔的拓扑结构。 广域同的典型例子就是因特网，其形成有一个逐步生长发展的过程，它起源于1969年 Research 美国国防部的ARPANET(AdvancedProjects Network)，现已发展成为 Agency 一个国际大网络。这种生长发展过程由于受到非线性机制的作用，呈现出明显的分形特征。 本文提出的超星分星结构对这种特征进行了客观的描述，它将对广域网的拓扑结构理论研 究提供一种方法。 2超星形结构 超星形(Hyperstar)结构实际上是一类正则图，可根据完全差集(或循环差集)来构造， 完全差集是组合设计中的一种特殊类型的对称设计。 定义1．1(见文献[2])设S一“，％…，如)是一个目元集，Bl，岛，…，鼠是它的b 个子集或b个无重排列，则族占一{B。，B：，…，鼠)就称为5上一个区组设计，S为该设计的 基集，且(1≤f≤6)称为该设计的区组，S的诸元素的一种确定的安排称为S上的一个组合 设计． 定义1．2设e={B。，B：，…，风)是集S上的一个医组设计，如果B满足： 1)1B，I是一个不依犊于J的常数^(称为容量)(1≤j≤6)； 一—了 一一——————__—疆} 广域同的超星丹形等级结构 37 2)对S的任一元s，吉s的B中子集的个数是不依赖于s的常数； 3)对S的任一个二元子集{＆，S，)，包含该子集的B的子集的个数是一个不依赖于S。 和S，的常数^。 Block Incomplete 则称B是集S上的一个平衡不完全区组设计(BIBD(Balanced Design)，简称为(6，口，r，^，^)一设计，6，口，r，^，卅末为这个设计的参数。 特别当6一口，r=k时称为对称的平衡不完全区组设计，记为o，^，^)一设计。一种特殊 类型的对称设计是所谓的循环对称设计，用五表示模”的剩余类环，i表示整数n所在剩 余类，剜完全差集的定义E8为： 定义1．3设 D一{：。，五，…，孔) 是乙的一个^元子集，如果对每一刁∈Z。，丑≠o，恰有D中^个有序对(二。，面)使得 一d—i。一二， Set)，称” 则称D为z，的一个(”，k，^)一完全(或循环)差集PDS(『Perfect西f，硫encP =^一l为该循环差集的阶。