1引言Banyan網絡是ATM交換網絡最具代表性的網絡之一。單純的Banyan網絡內部阻塞率非常，無法直接用于ATM交換。為了解決內部阻塞問題，有人提出對折疊加和排序兩種改良措施，但這兩種措施都是以增加悶珞的級數為代價的，會增加信元通過網絡的時延。而如果將網絡改造成單側折疊式的，那么可以防止上述問題。這樣不僅能夠有效地降低阻塞率，而且還可以降低一局部信元的時延。ATM技術由于能攜帶多種信息和媒體而日益受到人們的重視。和網一樣，交換機構是AIM技術的一個重要組成局部，它也可以分為時分和空分兩種。時分交換由于所有的信元都會集到一條總線上，數據吞吐量必然受到總線速率的限制。要進一步擴大交換容量，唯有將空分交換和時分交換結合起來。小容量的空分交換網絡可以由一個M條人線、N條出線的矩陣形交換單元構成。當某人線上的信息要轉送到某出線上時，就把這個人線和出線之間的交叉開關接通；不需要連接時，交叉開關就斷開。這種單級網絡．任意兩個人線和出線可隨時接通，不存在內部阻塞現象。但是在這種交換矩陣中，交叉點的數目隨端口數目的增加以平方速率增加，很快就會到達不可容忍的地步。因此通常當端口數目較多時，一般不采用單個交換單元，而是采用多級互聯網絡來完成交換功能。在相同的人線和出線的情況下，多級互聯網絡可以有效地減少交叉點的數目。在多級互聯網絡中，Banyan網絡是比擬典型的網絡之一，它控制簡單，構造規那么，因此一提出來，就受到人們的重視。2Banyan網絡的結構及其特性Banyan網絡采用2×2交換單元，它有兩種連接狀態：平行連接和交叉連接，如圖1所示。平行連接時。入端0和出端0’連接，人端l和出端1’連接；交叉連接時，入端0和出端1’連接，人靖1和出端0’連接。Banyan網絡的構造是非常規那么的：4個2×2的交換單元連接起來，可以得到一個4個人端、4個出端的二級網絡；12個這樣的交換單元連接起來可以得到一個8個人端、8個出端的三級網絡i32個交換單元連接起來可以構成一個l6個人端、l6個出靖的四級網絡。圖2給出了一個四級Banyan網絡，可看出它是由二級、三級Banyan網絡遞歸構成的。1〕平行連接2〕交夏連接圖-1-Banyan網絡的兩種連接狀態仿造上述方法可以推出，假設要用兩個N條入線、N條出線的交換網絡構成一個2N條人線、2N條出線的交換網絡，只要再加上N個2×2交換單元，把第一個N×N交換網絡的N條入線分別與新加的N個2×2交換單元的某一出線相連，把另一個N×N交換網絡上的N條人線與增加的N個2×2交換單元上的另一條出線相連即可。Banyan網絡構造規那么，便于擴充。它之所以受到重視還因為它具有自選路由特性．這就是說它不需要路由變換表，而可以根據信元攜帶的地址信息，自行找到要轉接的出線端口。由Banyan網絡的構造規那么可知．一個N×N的Banyan網絡共有M級，并且N=2M。如果把每個交換單元每側的兩個端口依次編號為0和1，那么從人端i到j出端的連接通路，所經過的各級交換單元的出靖號碼是一個位的二進制數字，可以證明這個二進制數字正好是出線，的地址。利用這個特性，如果把出線的編號(即出線地址)以二進制形式送到交換單元，那么每一級上的2×2交換單元只需要根據這個地址中的某一位就可以判別應將其送往哪一個出端上，當所有地址被讀完，信元就已經被送到相應的出線上了，這個性質就叫做自選路由特性。利用自選路由特性，交換單元的控制局部不需要安排復雜的路由變換表，可以做得十分簡單。圖-2-8×8的3級banyan網絡1.樹型結構特性：從banyan的任一輸入端口引出的一組通路形成了2分支樹，級數越多，分支越多，級數k=㏒2N，N=總入線數/出線數，即2k=N。2.單通路特性：banyan的任一入端到任一出端之間，具有1條且僅有一條通路。3.自選路由特性：自選路由，即是給定出線地址，不用外加控制命令，就可選到出線?？梢允褂脤诔龆颂柕亩M制碼的選路標簽來自動選路。在每個到來的信元進入MIN〔多級互連網絡〕之前加上路由標簽(routingtag)，MIN中各級SE〔交換單元〕就按照路由標簽中相應的路由信息來確定其出線，直到最后一級SE自行選路后就可到達所需的出端。即是給定出線地址，不用外加控制命令，就可選到出線?？梢允褂脤诔龆颂柕亩M制碼的選路標簽來自動選路。4.可擴展性：Banyan的構成具有一定的規律，可以采用有規那么的擴展方法將較小容量的Banyan擴展成較大規模。已有N×N的Banyan網絡，需構成2N×2N的Banyan網絡，那么可用2組N×N，再加上一組N個2X2交換單元構成。第一組的N×N的N條出線分別與N個2×2交換單元的某一入線相連，第二組的NXN的N條出線分別與N個2×2交換單元的另一入線相連。5.內部阻塞性：在沒有出線沖突時，縱橫開關陣列是沒有內部阻塞的。但上面討論的Banyan網絡那么是有內部阻塞的。Banyan網絡不僅有內部阻塞，而且這種內部阻塞隨著陣列級數的增加而增加。內部阻塞是在2×2交叉連接單元的兩個入線要向同一個出線上發送信元時產生的。從Banyan網絡的自選路由特性可以知道，任何一條人線到任何一條出線之間只有一條路由，這是因為通路所經過的各級交換單元都是按照目的地址來選擇出端號碼的，它只有一種選擇。因此當兩對人線、出線之間的通路發生碰撞時，就會產生內部阻塞，在圖2上標出了從人端0100到出端0ll0和從人端0l10到出端0100時通路發生碰撞的情況。由于Banyan網絡在任一對人線、出線之間只有一條路由，因此它的內部阻塞是非常高的，極端時候可以到達50％。顯然要使Banyan網絡應用于實際當中，必須解決它的內部阻塞問題。在這方面，典型的方案有兩種：一種是把一個級Banyan網絡對折疊加，使其級數增加到2M+1，那么總能找到任一條人線到任一條出線的通路；另一種是Banyan網絡前面添加一個排序網絡，對各人端到出端的連接進行排序，那么彼此所經過的路由不會重疊，因此也就不會發生內部阻塞。Banyan網絡的這兩種改良方法，從消除內部阻塞方面來說是非常成功的，它們都把內部阻塞降到了0。但是它們都是通過增加網絡單元數到達目的的，這樣做不僅會增加網絡的復雜性，而且會增加信元通過網絡的時延．尤其是不適宜傳送對信元敏感的信息，而AIM技術的本意就是要將多種信息綜合到一個網絡進行傳輸交換。如果將網絡改造成單側折疊式的，那么可以防止上述問題。在單側折疊式網絡中。每一對人線和出線之間都有多條可供利用的路徑。這樣就能大大減少信元碰撞的時機，從而使內部阻塞率降低。這種網絡還有一個優點，即通路不一定需要經過網絡的全程，根據人線和出線的相對位置，信元可在不同級的交換單元上反應回來，因此有些信元的時延還會降低。在單側折疊式Banyan網絡中，交換單元的內部鏈路應該工作在雙向模式，也就是要求每條人線和出線應該既能接收，又能發送。這一點并不難實現。在一個普通的4×4的交換單元中，安排其中的一半交換單元在一個方向上作2×2交換，而另一半在相反方向上作2×2交換，即可構成一個2×2的雙向交換單元。3單側折疊式Banyan網絡的構造方法及其特點我們知道，目前在網中獲得廣泛應用的并不是無阻塞網絡．而是有阻塞網絡。這是因為，在效勞質量允許的情況下，有阻塞網絡比無阻塞網絡能夠節約大量的交叉點數。以一個三級網絡為例，在10萬條人線，10萬條出線情況下，構造無阻塞網絡需要的交叉點數大約為4×108個；而在系統話務量為20000erl的情況下，構造內部阻塞率小于l0-100的有阻塞網絡那么需要2×108。個交叉點，比前者節約了大約一半的交叉點數。可見，只要內部阻塞率足夠低，有阻塞網絡比無阻塞網絡更經濟實用。在ATM交換網絡中，采用有阻塞網絡同樣能夠到達降低網絡復雜性的目的。下面所說的單側折疊式網絡就是有阻塞的，它是通過在人線和出線之間提供多條路徑，來降低信元的碰撞時機。和單純的Banyan同相比，這種方法，不僅保存了自選路由特性，而且當兩個終端建立連接時，根據它們的相對位置不一定需經過網絡的全程。利用選種雙向交換單元構成的Banyan網連接方法和原來類似，只是所有的輸入端口和輸出端口均位于網絡的左側。在單側折疊式網絡中，建立一條人線到一條出線的通路，可以不經過網絡的全程，根據人線和出線的相對位置，通路可在第l級、第2級或者最后一級反應回來對于圖2所示的網絡，將每個端口的編號用4位二進制數XYZW表示。通過比擬人線X1Y1Z1W1和出X2Y2Z2W2的地址就可以決定通路從哪級反應。當X1≠X2時，通路在第4級反應由于從第4級的哪一個交換單元都能找到連接到指定輸出端口的通路．所以從人線到第4級的通路可自由尋找，即所經過的交換單元可以選擇0、l任一條連接到下一級的空閑出線。但因為輸出端口是固定的，所以在從反應級向輸出端口建立通路時，要根據出線地址指定選擇交換單元的出線號。當X1=X2、Y1≠Y2時，通路的反應點在第3級，此時從人線到第3級的通路是自由選擇；從第3級到出線的路由是指定選擇。當X1=X2=、Y1≠Y2時，通路的反應點在第2級，此時從人線到第2級的通路是自由選擇；從第2級到出線的路由是指定選擇。當X1=X2、X1=X1、Y1=Y2、Z1≠Z2時，通路的反應點在第l級，此時只要在第l級的交換單元上，根據出線號碼，指定選擇一次即可。和原來的Banyan網絡相比，這種網絡也不需要路由變換表。在自由選擇時，所經過的交換單元可任意選擇一條連接到下一級的空閑出線；在指定選擇時，交換單元可以根據出端地址的二進制形式依次選擇相應的出線。由于建立通路時，從人線到反應級之間的路由是自由選擇的，因此它在輸入端口和輸出端口之間可能有多條通路，且通路數隨著反應級的深入而增加，通路數L與反應級位置K的關系是：L=2K-1，圖中示出了從端口10410到端口1010的2條通路。在這種多徑網絡中，對于給定的輸入，可以存在幾條不同的路徑到達預期的輸出端，因此有利于降低信元的碰撞時機，減少內部阻塞率。單側折疊式還有一個特點，即從人線到出線的連接可不經過網絡的全程。對一些聯系比擬密切的線對，位置可安排近一些，這樣就能有斂地降低信元通過網絡的時延。這種單向折疊式網絡的擴充比擬方便。當業務流量增大，需要擴充ATM交換機的規模時，原有的連線不需要變動．只需要將最后一級交換單元的出線和新增加的交換單元相連即可。在圖2中同時示出了網絡由二級到三級、四級擴充方法。如果網絡到達了預期最大規模，最后一級交換單元的端口就可以全部和前一級相連，這樣該級采用的交換單元端口數量可以只為原來的～半。例如對于圖2所示的四級網絡，第一、二、三級各需要8個4×4的交換單元，第四級需要8個2×2的交換單元，網絡可完成的交換容量為16×16端口。4解決內部阻塞的其它方法由于Banyan網絡有內部阻塞的性質，解決內部阻塞是能否能讓此網絡應用于實際的關鍵，可以有以下方法：1.內部阻塞是在2X2交換單元的兩條入線要向同一個出線上發送信元時產生的，最壞情況下概率為50%，假設減少入線上的信息量，就可減少阻塞的概率，故可通過適當限制入線上的信息量或加大緩沖存儲器來減少內部阻塞。2.可以通過增加多級交換網絡的級數來消除內部阻塞。已有證明，假設要完全消除NXN的banyan網絡的內部阻塞，至少需要2log2N