The Design and Implementation of a Non-Blocking Planar Multicast Switch Architecture Providing Self-Routing Capability

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

NSC98-2221-E019-068

Translated Name/計畫中文名

具自由路能力之非阻塞全平面群播交換結構之設計與實作

Project Coordinator/計畫主持人

Haw-Yun Shin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Department of Computer Science and Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=1920825

Year

2009

Start date/計畫起

01-08-2009

Expected Completion/計畫迄

31-07-2010

Bugetid/研究經費

588千元

ResearchField/研究領域

資訊工程--硬體工程

具自由路(Self-routing)能力之交換網路僅需依封包內之來源及目的位址便可控制交換元(Switch element)而正確抵達至輸出端，而不需預先連線建立演算法的計算。 Banyan 網路雖可實現自由路，但其會發生阻塞。在Banyan 網路之前加上一排序網路構成的Batcher Banyan 網路可以實現非阻塞具自由路能力之交換網路，但排序網路成本過高。本計畫提出一種具自由路能力的新型架構的平面式交換網路(Planar Switching Network)，簡稱為2DPSN。2DPSN 僅需將編碼後的輸出入位址做一次互斥或運算，即可得到輸入至輸出端路徑，連線演算法之複雜度為O（1）。 2DPSN 具有規則性的排列架構，且所有交換元間之接線皆可在二維平面完成，因此，若建置於光交換機中，不會發生光導管跨越(crossover)的情形，可大大降低串音干擾的發生，若建置在電子式交換機中，由於接線簡單及交換元規則的排列，在積體電路的佈局上極易實現。此種交換網路使用較少數目的交換元，具有無阻塞的特性，因此，在許多應用領域中可以取代縱橫式網路(Crossbar Network)。 2DPSN 存在許多等價(equivalent)之交換網路。將2DPSN 之交換元移動後所形成之交換網路，若交換能力及交換網路特性與2DPSN 皆相同，則稱之與2DPSN 等價。本計畫擬證明出所有平面交換網路的數目，及2DPSN 演化成其它平面交換網路的規則，同時研究出一種通用型態的連線建立演算法用於演化出的平面交換網路，使得與2DPSN 有相同交換能力。為滿足下一世代通訊網路的需求，交換機必須具有廣播(broadcast)及群播 (multicast)能力，為使2DPSN 具有廣播及群播的能力,我們將2DPSN 之交換元擴展成為具有直行、交換、左廣播、右廣播的功能。具有廣播及群播的能力的2DPSN 我們稱之為 2DBPSN。本計畫擬提出具自由路功能之2DBPSN，僅需將編碼後的輸出群組位址與輸入位址做互斥或運算，即可得到輸入至輸出端群播路徑。為改善2DPSN 交換網路所需交換元數目及交換延遲時間，本計畫提出「三維平面交換網路」，簡稱3DPSN。3DPSN 以2DPSN 為模組以三層連接方式組合而成，其所需交換元的總數遠小於Clos 網路之所需。本計畫擬於3DPSN 中研究其連線建立演算法，利用2DPSN 中O（1）之連線演算法，預期能提出一複雜度非常低，甚至可用於3DPSN 自由路的連線演算法。同時本計畫也提出「具群播功能之三維平面交換網路」，簡稱3DBPSN，以改善 2DBPSN 交換網路所需交換元數目及交換延遲時間。本計畫也擬對2DPSN 及3DPSN 應用於光交換機之各種效能分析，包括串音 (Crosstalk)之分析、信號衰減之分析、所需交換元數目之分析及最大Crossover 之分析，並與現有光交換機架構進行比較。同時也對於2DBPSN 與3DBPSN 用於光交換網路之可行性評估與效能分析。當2DPSN、3DPSN、2DBPSN、3DBPSN 及其衍生出之平面交換網路完成分析後，本計畫將以SoC 平台實現所提之平面交換網路架構及連線建立演算法，以證明其擴充性及正確性，並以硬體自動產生封包對其做實際效能量測。當2DPSN 及3DPSN 完成量測及正確性驗證後，本計畫擬開放2DPSN 及3DPSN 之IP(Intellectual Property)原始碼供學術單位使用，並計畫將其製作成IC。 A new type of Planar Switching Network, called 2DPSN, is proposed in our proposal. 2DPSN is provided with a regular architecture and no wire crossover between the switching elements. Applying 2DPSN to the optical switching network, the crosstalk interference can be restrained due to no waveguide crossover. 2DPSN with a regular switch fabric and a very simple hardwire circuit can be implemented in VLSI easily. 2DPSN is with non-blocking property just like the Crossbar network but requires less switching element. Therefore, Crossbar may be replaced by 2DPSN in many fields. The self-route capacity that the connection of a switching network can be determined by the packet only depends on the source and destination information in the packet header will be provided to 2DPSN. Only one operation of XOR, O(1) connection complexity, is needed to determine the connection. There are many planar switching networks equivalent to 2DPSN. Aswitching network of which switching capacity and switching property is the same as 2DPSN is called equivalent to 2DPSN. In our proposal, we will show that all the planar switching networks can be evolved from 2DPSN and investigate the general connection setup algorithm for all the planar switching networks. Again, for fulfilling the Internet service requirement in the next generation, the switching network should be provided with the capacities of multicast and broadcast. Based on 2DPSN architecture, we propose a multicast switching network, called 2DBPSN. A self-route capacity to setup multicast connection is also studied here. To reduce the connection delay and the total number of switching elements in 2DPSN, we develop the architecture of 3D planar switching network, called 3DPSN. 3DPSN is the special case of Clos network, however, the requirement of number of switching element are less than Clos due to the module architecture in 3DPSN is to use 2DPSN. We will study the self-route connection setup algorithm in 3DPSN. In addition, 3DBPSN and its connection setup algorithm are also studied to improve the connection delay and the total number of switching elements in 2DBPSN. We will analyze the performance that applies 2DPSN, 3DPSN, 2DBPSN and 3DBPSN to the applications of optical switching network. The crosstalk interference, signal attenuation, number of switching elements and number of crossovers are analyzed and then to be compared with presented optical switching networks. As complete the performance analyses and the proofs of connection setup algorithms of 2DPSN, 3DPSN, 2DBPSN and 3DBPSN, we will implement those switching fabrics on SoC to show the correctness and scalability and to measure the real performance such as packet delay, throughput and connection rearranged probability. The IP (Intellectual Property) source code of proposed switching network will be opened to the academic research. Finally, we expect that the proposed switching networks are implemented in SoC.

Keyword(s)

無阻塞交換網路
平面交換網路
群播交換
高密度分波多工
光交換機
自由路
SoC
Non-blocking Switching Network
Planar Multicast Switching Network
Multicast switch
Self-routing
Optical Switching Network
SoC

DSpace CRIS

The Design and Implementation of a Non-Blocking Planar Multicast Switch Architecture Providing Self-Routing Capability

Details

Description