異步傳輸方式交換用的交換系統及方法

2023-07-22 07:43:56 2

專利名稱：異步傳輸方式交換用的交換系統及方法
交換系統及方法本發明涉及異步傳輸方式用的交換系統及方法，更具體地說，涉及多媒體服務用異步傳輸方式交換用的交換系統及方法。本申請基於韓國專利申請No.56581/1995，現將其引入作為參考。
一般說來，多媒體服務涉及許多業務量特性(數據速率，猝發性(burstiness)等等)。另外，它服務格式要求點對點、點對多點、多點對多點配置。在一類服務中，可能是單連接和多連接。諸如公用交換電話網(PSTN)和包交換公用數據網(PSPDN)等傳統的網絡是只為用於預定格式的特定服務而設計的，它們不可能提供多媒體服務。因此，多媒體服務要求新格式的交換網絡，而各種服務的發展，從終端到交換/傳輸系統，需要進行這樣的新網絡的形成。目前，作為最適宜於提供具有像多媒體這種特性的服務，國際電信聯盟(ITU)將異步傳輸方式(ATM)用於正在進行的標準化目的。
人們提出了各種各樣的ATM交換網絡。首先，按信息傳輸通道的劃分方法分，有時分和空分。按拓樸分，有環型、總線型和網格型。按所用緩衝器的位置或用途分，有輸入緩衝型、公用緩衝型、分散緩衝型和輸出緩衝型。它們可以結合起來。
空分型ATM交換網絡結構，基本上類似榕樹結構或縱橫制網絡，具有網格形式，和路由自選擇，其中交換網絡內的信元按硬體操作為它們自己尋找它們的目的地(交換網絡的輸出埠)。
但是，這種結構必須具有緩衝器，因為它們的大部分都涉及內部阻塞。所有類型的ATM交換網絡，包括空分和時分類型，在其輸出側還都必須具有緩衝器，因為有輸出埠碰撞問題。按當輸入緩衝器用於空分交換網絡時緩衝器的操作方法，分成兩種類型，即

圖1的專用緩衝器和圖藝所示的共享緩衝器。通常，主要使用專用緩衝器。這樣的分散緩衝器類型的優點是它們的操作容易。但是，他們的缺點是，交換網絡的各個埠用的緩衝器是固定的，這樣業務量(信元)不能整個地分散到交換網絡的埠。如果分布不均，如圖1所示，任何一個埠都可能出現輸入數據溢出。
在ATM交換網絡中，輸入埠和輸出埠之間的內部路徑具有單路徑或多路徑結構。如圖1所示，輸入埠X和輸出埠Y之間單元開關的輸出路徑可以是(1)、(2)和(3)。這裡，在單路徑的情況下，如圖3所示，可能出現內部阻塞，這會由於信元損失而使其性能下降。圖3表示8*8單路徑榕樹網絡。在該圖中，提出了一個通過從輸入埠X到輸出埠Y及從輸入埠W到輸出埠Z的信元傳輸路徑傳輸信元的例子。在這種情況下，在單元開關的第二級信元碰撞，從而造成內部阻塞。單路徑交換網絡儘管有內部阻塞，但是，內部路由選擇簡單，操作容易。在多路徑交換網絡的情況下，內部阻塞的機率小，但是，多路徑的路由選擇控制過於複雜，幾乎無法應用在大量的開關上。這是由於交換網絡的路由選擇控制速度達不到信元的傳輸速度。
如圖2所示，如果多路徑空分交換網絡是用共享緩衝器作為其輸入緩衝器來實現，就能消除分散緩衝器類型引起的輸入數據溢出。圖4表示內部具有8位並行結構的公用存儲器交換網絡的一個例子。如圖4所示，公用存儲器(時分)交換網絡完成交換的結構簡單，其交換的概念與傳統交換系統相同。但是，在其傳輸速度為數百Mb/s的ATM中，儘管是並行傳輸，卻無法實現大容積交換網絡，因為傳輸速度遠遠大於存儲器的操作速度。按照目前的半導體技術，可以實現的最大交換網絡尺寸是在8*8，如果是8位並行數據傳輸的話。
如上所述，傳統ATM技術在至今已研製和建議的ATM交換網絡中，在時分/空分、緩衝器用法、單路徑/多路徑之中，選擇易於實現的的方式。但是，傳統ATM交換網絡有著下列問題。
在時分的情況下，其能力由於可以購到的商售存儲器存取時間的限制而受到限制。例如，在8位並行ATM交換網絡中，所製造的交換網絡尺寸是4-8個埠。
第二，對於多路徑的交換網絡，從輸入埠到輸出埠路由選擇的路徑是多重的，使得每一次呼叫都需要對此進行分析，以免在交換網絡中造成內部阻塞。但是，這個方法涉及的控制算法過於複雜，當交換網絡尺寸增大時無法實現。
第三，在輸入緩衝器用為每個輸入埠分配的專用緩衝器實現的情況下，按照輸入業務量的特性，緩衝器溢出的機率增大，使服務質量由於信元丟失而下降。另外，緩衝器利用效率太低，以至要像共享緩衝器方式那樣滿足性能要求，緩衝器的成本就要增大。
因此，本發明的一個目的是提供一種用於多媒體服務的異步傳輸方式交換用的交換系統和方法。
本發明的另一個目的是提供一種空分交換系統和方法，以便通過採用共享輸入緩衝器和具有單路徑提高異步傳輸方式交換系統的交換速度。
本發明的再一個目的是提供一種通過實現多路由選擇網絡消除內部阻塞的裝置和方法。
本發明還有一個目的是提供一種在異步傳輸方式交換系統中通過實現信元拷貝網絡處理多媒體信息用的裝置和方法。
本發明再有一個目的是提供一種通過分析異步傳輸方式交換系統信元輸出路徑，並將其反饋來防止輸出埠競爭的交換系統及方法。
本發明還有一個目的是提供一種在異步傳輸方式交換系統中交換的信元的式樣結構。
為了實現本發明的目的，提供一種實現異步傳輸方式交換網絡用的裝置，該裝置包括輸入緩衝器，用來儲存輸入信元；輸入交換網絡，由預定尺寸逆榕樹網絡單元開關構成，並具有輸入埠和輸出埠，輸出埠連接在各輸入緩衝器之間，輸入交換網絡完成取與加功能，其中信元輸入數向著從輸入埠到輸出埠的方向相加，而輸入緩衝器的地址按相加的信元數向著從輸出埠到輸入埠的方向傳輸，輸入交換網絡按照取與加功能的計算結果，在輸入緩衝器內對輸入信元進行傳輸和儲存；拷貝交換網絡，由預定尺寸逆榕樹網絡單元開關構成，並具有連接到輸入緩衝器的輸入埠，拷貝交換網絡完成取與加功能，其中信元拷貝數向著從輸入埠到輸出埠的方向相加，而拷貝索引對應於所拷貝的信元數，向著從輸出埠到輸入埠的方向傳輸，拷貝交換網絡按照取與加功能的計算結果，從輸入緩衝器拷貝和傳輸信元輸出；反饋交換網絡，由預定尺寸逆榕樹網絡單元開關構成，並具有連接到拷貝交換網絡的輸入埠，反饋交換網絡接收信元反饋，並保持它們直至下一個信元周期；路由選擇表，用來儲存翻譯用的數據和替換信元路由選擇用的數據；路由選擇/反饋控制器，用來從拷貝交換網絡接收信元輸出，和從反饋交換網絡接收信元反饋，參考路由選擇表對輸入信元和反饋信元進行路由選擇-控制，並反饋在輸出埠碰撞的信元；路由選擇交換網絡，其中多個由預定尺寸的縱橫制單元開關構成的交換網絡並行連接，該開關對信元輸入進行交換-輸出；信元分割器，它連接到路由選擇開關的輸入埠，分割器對網絡數進行路由選擇、並將它們傳輸到路由選擇交換網絡的數目進行分割；以及信元合併器，它連接到路由選擇交換網絡的輸出埠，合併器將從路由選擇交換網絡輸出埠分割和輸出的的信元進行合併和輸出。
實現異步傳輸方式交換網絡的方法取決於如何操作不同的元件(方式)或使用哪個元件。在本發明中，提出了具有共享輸入緩衝器和單路徑的空分交換網絡。本發明採用空分方法實現，原因是時分存儲器存取速度有限的根本問題。在單路徑交換網絡中出現內部阻塞的情況下，其性能下降。但是，在本發明中，設置多個路由選擇網絡，以保證達到100％的性能。另外，本發明使用共享輸入緩衝器，使得所有輸入埠共享該緩衝器。因此，輸入緩衝器的利用效率高達100％，而即使緩衝器像分散緩衝器一樣大，信元丟失率也會下降。因此，本發明屬於空分、網格式、以及輸入/輸出混合緩衝器。為了防止內部阻塞和輸出埠競爭，本發明既將緩衝器用於輸入階段，又用於輸出階段。
參閱下面更詳細的描述，結合附圖進行考慮，就能更加明了本發明，從而更全面地評價本發明及其許多附帶的優點。在附圖中，相近的參照號表示相同或相近的組件，其中圖1表示具有專用於其輸出埠的緩衝器的空分多路徑交換網絡的結構；圖2表示具有其輸出埠共享的緩衝器的空分多路徑交換網絡的結構；圖3表示單路徑交換網絡(例如，8*8榕樹網絡)的一個例子，其中出現了內部阻塞；圖4表示公共存儲器交換網絡的一個例子；圖5表示ATM交換系統的結構；圖6表示按本發明圖5實現的ATM交換網絡的配置；圖7A表示圖6輸入網絡的一個例子，該網絡由規模為1024*1024逆榕樹網絡構成；圖7B表示一個例子，其中圖7A的單元開關由規模為32*32的逆榕樹網絡構成；圖8A以規模為8*8的輸入網絡為例，表示取與加功能的第一步，其中從輸入網絡輸入的信元數相加；圖8B以規模為8*8的輸入網絡為例，表示取與加功能的第二步，其中輸入緩衝器的地址從輸入緩衝器傳輸；圖8C以規模為8*8的輸入網絡為例，表示取與加功能後，傳輸信元的步驟；圖9A表示在規模為1024*1024的輸入網絡上完成取與加功能的步驟；圖9B表示在規模為1024*1024的輸入網絡上完成信元傳輸功能的步驟；圖10A以規模為8*8的輸入網絡為例，表示圖6輸入緩衝器的結構；圖10B表示圖10A所示輸入緩衝器的概念結構；圖11A以規模為8*8的拷貝網絡為例，表示完成取與加功能第一步的程序，其中在拷貝網絡中加上信元拷貝的數目；圖11B以規模為8*8的拷貝網絡為例，表示完成取與加功能第二步的程序，其中將在拷貝網絡中傳輸拷貝索引；圖12以規模為1024*1024的拷貝網絡為例，表示完成取與加功能的程序，其中將在拷貝網絡中加上信元拷貝的數目並傳輸拷貝索引；圖13A是示意圖，說明在規模為8*8的拷貝網絡中，取與加功能之後拷貝信元的功能；圖13B表示在規模為8*8的拷貝網絡中，圖13A的步驟之後下一步信元拷貝的步驟，以便解釋取與加功能之後拷貝信元的功能；圖14表示在規模為1024*1024的拷貝網絡中拷貝當前輸入的信元的步驟，以便解釋取與加功能之後拷貝信元的功能；圖15表示圖6規模為1024*1024的反饋網絡的配置；圖16表示圖6四個並行路由選擇網絡的配置；圖17A表示以榕樹網絡的類型形成的路由選擇網絡的例子；圖17B表示按本發明的縱橫制類型的路由選擇網絡的例子；圖18表示按本發明的信元分割器、路由選擇網絡和信元合併器的結構；圖19表示圖6路由選擇表的結構和信元頭的轉換；圖20A表示ATM UNI信元頭的結構；圖20B表示ATM UNI信元頭的結構；圖21表示按本發明在ATM交換網絡中傳輸的信元頭的結構；圖22A以16*16的路由選擇網絡為例，表示路由選擇網絡防止內部阻塞的功能；圖22B表示圖22A防止內部阻塞的步驟；圖23以1024*1024的路由選擇網絡為例，表示在路由選擇網絡中防止輸出埠競爭的功能；圖24A以16*16的路由選擇網絡為例，表示在路由選擇網絡中防止輸出埠競爭的功能；圖24B表示在圖24A中防止輸出埠競爭的步驟；圖25以1024*1024的路由選擇網絡開關為例，表示通過路由選擇網絡在輸出埠儲存信元的步驟；圖26以32*32的榕樹網絡開關為例，表示按本發明榕樹網絡單元開關的結構；圖27以32*32的逆榕樹網絡開關為例，表示按本發明逆榕樹網絡單元開關的結構；圖28以32*32的縱橫制開關為例，表示按本發明縱橫制單元開關的結構。
圖5表示一個ATM交換網絡系統。本發明的最佳實施例提出一個ATM網絡組件的ATM交換系統用的ATM開關陣列(switchfabric)(下文稱作ATM交換網絡或交換網絡)。在本發明中，假定ATM交換網絡的規模為1024*1024。
如圖5所示，ATM交換系統主要包括用戶/中繼線接口、ATM交換網絡和呼叫/連接處理器。
用戶/中繼線接口連接用戶或中繼線鏈路，並為ATM信元在ATM交換系統內的交換完成各種功能。在ATM交換系統中採用53位元組的信息傳輸單元稱的所謂」信元」，即使在ATM交換系統中交換也是以信元為單位完成的。
ATM交換網絡完成交換功能和多投(Multicast)功能，以便將輸入信元傳輸到它們打算達到的目的地。信元的目的地的信息(路由標記)在建立呼叫時由呼叫/連接處理器確定，並傳輸到用戶/中繼線連接器。在輸入到用戶/中繼線接口的信元的欄位中，根據目的地的信息，為每個信元寫上與路由選擇有關的信息。按照所寫的信息，在ATM交換網絡中完成自動路由選擇，這就是交換功能。多投是一種在將信元從一個傳輸側傳輸到至少兩個接收側的情況下完成的功能，要求處理器根據需要複製多個信元。呼叫/連接處理器涉及呼叫/連接管理(信令…)、路由選擇控制、操作/維護(OAM)及資源管理。控制/維護部分完成整體操作控制和交換系統的管理，諸如通過處於用戶/中繼線接口較低級的處理器之間的內部通信完成的呼叫建立/釋放、ATM功能及整個系統的維護。
如圖6所示，按本發明的ATM交換系統的ATM交換網絡具有輸入網絡、拷貝網絡、反饋網絡、路由選擇網絡、完成它們的功能的外圍邏輯、由存儲器構成的輸入緩衝器及空分開關。
現以規模為1024*1024的ATM交換網絡為例，探討該種網絡及其功能的實現。形成諸如輸入、拷貝、反饋及路由選擇等交換網絡的各個子網絡是由規模為32*32的單元開關組成的。輸入網絡和反饋網絡使用逆榕樹網絡。拷貝網絡使用榕樹網絡。路由選擇網絡可以採用各種不同的交換網絡，但在考慮到容易實現及性能，這裡採用不會引起內部阻塞的縱橫制(X-匯流排(bar))。
本發明的ATM交換網絡的結構分成輸入網絡12、拷貝網絡32、反饋網絡52和路由選擇網絡63。每一個網絡均由規模為32*32的單元開關分兩級組成。這裡，輸入網絡12和反饋網絡52的單元開關採用逆榕樹網絡。拷貝網絡32的單元開關採用榕樹網絡，而路由選擇網絡63的單元開關採用縱橫制網絡。當圖6的ATM交換網絡以1024*1024的規模形成時，榕樹網絡和逆榕樹網絡即使在32*32規模的單元開關分成兩級時，還能保持其性能。但是，縱橫制網絡就不能保持內部不阻塞。在這種情況下，在路由選擇網絡63內部可能造成阻塞，而其性能下降。為了克服這一點，在本發明中使用了多個路由選擇網絡，例如4個63a-63d。
在圖6中，在網絡12，32，52和63的前端使用了信元同步器11，31，51和62，因為在位和信元的水平要求同步。同步之所以需要，是因為信元輸入到各個網絡的輸入速度是160Mb/s，而網絡又可能被放置在不同的物理位置。
參見圖6，在各個網絡12，32，52和63的輸入級32*32單元開關處使用信元同步器1，31，51和62。信元同步器完成160Mb/s位同步和信元同步。
輸入網絡12使用1024*1024逆榕樹網絡，並由64個單元開關(32*32逆榕樹網絡)組成。輸入網絡12連接在信元同步器11與輸入緩衝器20之間，完成輸入信元的取與加的功能，和將輸入信元存入輸入緩衝器20的功能。
輸入緩衝器(輸入隊列)20儲存著從輸入網絡12輸出的輸入信元。輸入緩衝器20的大小取決於輸入埠的大小和輸入信元的大小。(1024埠*x信元＝xxx信元)。
拷貝網絡32採用1024*1024榕樹網絡，並由64個單元開關(32*32榕樹網絡)組成。拷貝網絡32連接在信元同步器31和路由選擇/反饋控制器41之間，完成信元的取與加的功能和信元拷貝功能。
反饋網絡52採用1024*1024逆榕樹網絡，並由64個單元開關(32*32逆榕樹網絡)組成。反饋網絡52連接在信元同步器51和路由選擇/反饋控制器41之間，完成信元反饋的取與加功能和信元拷貝功能。
路由選擇表42存儲著信元在ATM交換中的路由選擇信息(VPIs/VCIs，路由標記)。路由選擇/反饋控制器41從拷貝網絡32和反饋網絡52接收信元，並參考路由選擇表42中的路由選擇信息控制信元輸入的路由選擇。路由選擇/反饋控制器41的路由選擇控制完成向輸入信元頭提供路由選擇信息(VPI/VCI)和自動路由選擇標記。反饋控制完成ATM交換網絡內部阻塞和輸出埠競爭。
信元分割器51完成將拷貝網絡32和反饋網絡52輸出的信元的分割功能。在本發明中，信元分割器61分割輸入信元並將其傳輸到多個路由選擇網絡，以便防止ATM交換網絡發生內部阻塞和輸出埠的競爭。在本發明中假定採用4個路由選擇網絡63a-63d。路由選擇網絡由縱橫制1024*1024縱橫制網絡和64個單元開關(32*32縱橫制網絡)組成。路由選擇網絡完成自動路由選擇。信元合併器64將路由選擇網絡63a-63d輸出的信元存儲在埠的輸出緩衝器並將其輸出。
下面將參見圖6描述各個網絡的結構和功能。
輸入網絡12完成取與加的功能，其中用來存儲由輸入埠輸入的信元的輸入緩衝器20受控由各輸入埠共享。按照取與加的功能，輸入埠所有的輸入信元都接收它們要被儲存的輸入埠2的地址，並按此地址在輸入網絡之後儲存在輸入緩衝器20中。輸入緩衝器20是共享緩衝器，而非專用緩衝器，使得它們有著優異的利用效率，並在突發業務量的環境下非常有效。儲存在輸入緩衝器20中的信元按其儲存順序傳輸到拷貝網絡32。在交換操作中，有一種情況限制從輸入緩衝器20傳輸到拷貝網絡32的信元數目。在前一個信元周期中拷貝的信元數目超過了拷貝網絡32的能力時，或者要反饋的信元目前正在反饋網絡52中時，就會出現這種現象。
拷貝網絡32用來提供廣播或多投服務。如果從輸入緩衝器20接收的信元是廣播或多投信元時，需要多少，拷貝網絡32就拷貝多少信元。在這裡，信元的拷貝數在信元頭中以(最小值，最大值)的形式指出。在信元分割方式下，在拷貝網絡中用的拷貝信元的算法參考這個值。該最小值和最大值是由取與加的結果和拷貝網絡32中各信元要求的拷貝數計算的。在這裡，若拷貝的信元數目超過拷貝網絡32的能力，超過的信元取出並相加，不從輸入緩衝器20讀出，而在下一個信元周期中，輸入回拷貝網絡。
反饋網絡52用來將在同一信元周期中通過路由選擇網絡63所需信元，而不是在通過路由選擇網絡63時不引起內部阻塞或輸出埠競爭的信元反饋回去。反饋的信元和下一信元周期中通過拷貝網絡32接收的信元一起，經過通過路由選擇網絡63的步驟。這裡，路由選擇/反饋控制器41控制，使反饋的信元具有優先權。反饋網絡52在反饋網絡的輸入階段，每個埠一個信元用一個緩衝器，以便使反饋的信元延遲一個信元周期。
路由選擇/反饋控制器41由路由選擇控制器和反饋控制器組成。路由選擇/反饋控制器41的路由選擇控制器，完成像轉換信元頭等將通過路由選擇網絡63的信元的路由選擇標記相加的功能，和信元路由選擇功能。路由選擇標記用在自動路由選擇中，其中這些信元通過硬體經由路由選擇網絡尋找欲往的輸出埠。信元頭轉換是一種對輸入信元頭進行轉換的功能，使得從它自己的節點輸出的信元頭信息用於下一個節點的路由選擇。諸如路由選擇標記、信元頭轉換信息等與路由選擇有關的值，由圖5的呼叫/連接控制器更新，只要呼叫/連接未被置位，並被儲存在路由選擇表42中，直到相應的呼叫/連接被釋放為止。
路由選擇/反饋控制器41的反饋控制器在路由選擇網絡63內，完成防止信元由於內部阻塞或輸出埠競爭而造成的丟失的功能。每個信元周期都完成反饋控制功能，而不能通過路由選擇網絡63的信元被送回反饋網絡52。每個信元周期，都對所有的埠計算通過路由選擇網絡63的信元數目。這個數值表明在路由選擇網絡63a-63d內，未受內部阻塞或輸出埠競爭影響而傳輸的信元數目。這裡，內部阻塞意味著在內部通道內出現了碰撞，即使信元輸入到該網絡並要求不同輸出埠也是如此。輸出埠競爭意味著，輸入的信元在輸出埠發生碰撞，即使它們傳輸未遇內部阻塞，但輸入信元要求相同的輸出埠。
信元分割器61將信元分送到路由選擇網絡63a-63d，以便在通過路由選擇網絡63的信元按照反饋控制輸入時，不引起內部阻塞和輸出埠競爭。
信元真正完成交換是在路由選擇網絡63內。由拷貝網絡32和反饋網絡52輸入的信元由硬體自動進行路由選擇，並通過路由選擇網絡63傳輸到要求的輸出埠。這裡，所用的1024*1024路由選擇網絡是一種形式，其中32*32 X-bar網絡作為單元開關分成兩級。這種路由選擇網絡並非無阻塞網絡，因而會由於交換網絡中的內部阻塞而輸性能下降。因此，在本發明中形成4個並聯的路由選擇網絡63a-63d，以提高ATM交換網絡的輸入/輸出路徑，並在信元輸入路由選擇網絡63之前完成反饋控制，以消除內部阻塞。這能防止交換網絡性能下降。雖然從路由選擇網絡清除了內部阻塞，但是由於輸出埠競爭ATM交換網絡的性能被限制在58％。相應地，如果路由選擇網絡63是並聯和由多個形成，並有反饋控制，ATM交換網絡消除了內部阻塞，再加上對輸出埠競爭的控制，交換性能就接近100％。用32*32單元開關形成1024*1024規模的路由選擇網絡63a-63d，增加了硬體的數量，在輸入網絡的輸入埠與輸出埠之間有多條路徑。因此1024個埠在信元路由選擇上難於控制。
信元合併器64把從路由選擇網絡63a-63d輸出的信元儲存在輸出緩衝器中，並將它們以預定的速度輸出。所用的輸出緩衝器，與輸入緩衝器相比效率非常低，因為不象輸入緩衝器，緩衝器是各個輸出埠專用的。
從現在開始，將詳細描述輸入網絡12、拷貝網絡32、反饋網絡52和路由選擇網絡63。假定在本發明中，ATM交換網絡的規模是1024*1024。因此，諸如取與加功能、信元拷貝和路由選擇等全部功能必須是針對整個1024*1024網絡完成的，而不是針對單元交換網絡。本發明的ATM交換網絡，由輸入網絡12、拷貝網絡32、反饋網絡52和路由選擇網絡63。在這些網絡中，輸入信元在它們最後輸出之前，必須至少通過其中的3個網絡。在具體地解釋ATM交換網絡的整個操作的同時，將它分成輸入網絡12、拷貝網絡32、反饋網絡52和路由選擇網絡63。
當信元儲存在輸入緩衝器20時，為了有效地利用輸入緩衝器20，輸入網絡完成取與加的功能以及信元傳輸。信元傳輸是由1024*1024逆榕樹網絡完成的。取與加功能可以用逆榕樹網絡實現，因為在概念上它有著與逆榕樹網絡相同的結構。但是，取與加功能用獨立於逆榕樹網絡的硬體來實現的，因為它並不要求整個逆榕樹網絡，而且不準備像輸入網絡12那樣地傳輸信元。如圖7A所示，為了硬體較易實現，輸入網絡12由32*32逆榕樹網絡的單元開關分兩級組成。32*32逆榕樹網絡具有如圖7B所示的結構。下面將說明輸入網絡的詳細功能。
按照輸入網絡12的取與加功能，信元本身儲存的緩衝器地址這樣設置，使得ATM交換網絡輸入埠接收的全部信元順序地儲存在輸入緩衝器20中。這裡，緩衝器地址這樣設定，使得輸入緩衝器20為全部的輸入埠共享。在分配緩衝器20地址的過程中，需要有一位用來指示輸入埠是否有活性信元，和若干位用來寫輸入緩衝器的地址。這些類型的信息寫在信元頭上。對於每一個信元周期，取與加功能以管線的形式進行，同時進行信元傳輸功能。第n個周期的輸入信元的取與加功能在第n+1周期完成。在第n周期完成第n+1周期輸入的信元的取與加功能。
圖8A和8B以6個輸入信元，輸入緩衝器指針為0，對應在8*8規模的網絡中單投為例，表示輸入的信元儲存入輸入緩衝器20的過程。輸入緩衝器指針代表當前周期儲存信元的輸入緩衝器20的起始地址。下面參閱圖8A和8B，描述完成輸入網絡12的取與加功能的第一和第二步。
首先，參閱圖8A，取與加功能的第一步，就是說，從輸入埠將信元加到輸出埠的過程，進行如下。這裡，該開關元件指的是剛才的元件。
在輸入到較高的輸入埠的信元出現在輸入網絡12的2*2元件的第一級的情況下，不管較低的輸入埠是否接收到一個信元，都將數字」1」寫在元件的寄存器上。輸入到第一級元件較高和較低輸入埠的信元相加，準備送到較低的輸出埠。這個值輸入到與第二級元件連接的元件上。
和第一級一樣，對於輸入到第二級的元件，輸入到較高輸入埠的信元個數寫在該元件的寄存器上，而輸入到較高和較低輸入埠的信元相加，然後送到較低的輸出埠。這個值輸入到與第三級元件連接的元件上。
同樣在第三級。對於輸入到該元件的信元，將輸入到較高輸入埠的信元個數寫在該元件的寄存器上，而輸入到較高和較低輸入埠的信元相加，然後送到較低的輸出埠。
在上述過程之後，如圖8A所示，信元輸入相加的結果輸出到最後一級的最低的埠。這個最後的值加到輸入緩衝器20的指針寄存器值上，其結果存回到輸入緩衝器指針寄存器上。這個值指示下一個信元周期輸入緩衝器的起始地址。在圖8A的例子中，前一步的指針值假定為0，6個信元是新輸入的，所以指針的值更新為6。
第二，參閱圖8B，取與加功能的第二步，就是說，從輸出埠到輸入埠的輸入緩衝器20的地址傳輸過程進行如下。
在前一信元周期中儲存的指針值」0」由最後一級的最低一個輸出埠輸入，並通過較高的輸入埠傳輸給第二級的元件。通過較低的輸入埠，將傳輸的值加到取與加功能第一步寫在該元件寄存器上的值上，並送往第二級元件。
第二級元件將從第三級接收到的值通過較高的輸入埠傳輸到第一級元件。通過較低的輸入埠，將傳輸來的值加到在取與加功能第一步寫入該元件寄存器的值上，並送往第一級元件。
在第一級元件中，從第二級接收來的值傳輸到較高的輸入埠。這個值加到在取與加功能第一步寫入該元件寄存器的值上，並送往較低的輸入埠。
在上述過程之後，所有輸入埠的信元都接收儲存它們的輸入緩衝器20的地址。從這些信元輸入的輸入埠的最高埠起，這些信元順序地接收到它們的輸入緩衝器地址0，1，2，3，4和5，因為在圖8B中輸入的信元個數是6。圖8A和8B表示當實現的輸入網絡是8*8時，在第一步中信元個數相加的過程和在第二步中輸入緩衝器的傳輸過程。圖9A表示在規模為1024*1024的輸入網絡中取與加功能的第一和第二步。
第三，在取與加功能的第一和第二步之後，信元傳輸的完成如圖8C所示。參閱圖8C，輸入網絡12信元傳輸按下列方式進行，使得所有的信元都從取與加功能得到存儲它們的輸入緩衝器地址，然後將它們用作這些信元通過逆榕樹網絡的輪轉(Rounding)標記。在這裡，對於輪轉標記，在取與加功能得到的位流並不是不加改變地使用的，而是將其位順序加以改變，以使輸入的信元在逆榕樹網絡中能夠沒有內部阻塞地通過。若取與加功能的結果是(b1，b2和b3)，則在逆榕樹網絡中的輪轉標記順序變為(b3，b2和b1)。圖8C描述了按上述方法產生的輪轉標記通過輸入網絡將信元存入輸入緩衝器的過程。
圖8C表示當輸入網絡規模為8*8時，按照通過完成取與加功能操作的輸入緩衝器地址傳輸信元的過程。圖9B表示在規模為124*1024的輸入網絡12中，信元的傳輸過程。
第二，將解釋輸入緩衝器20(輸入隊列)的配置和操作。輸入緩衝器20儲存著通過輸入網絡12傳輸來的信元，具有圖10A所示的配置。圖10A表示在8*8個開關的情況下輸入緩衝器20的配置。圖10B表示圖10A所示的輸入緩衝器20的概念結構。
在圖10B中，底部指針指著儲存新輸入的信元的輸入緩衝器20地址的起始位置。項部指針指著正要讀出的在輸入緩衝器20儲存的信元的地址的起始位置。圖10A表示形成輸入緩衝器20的先進先出(FIFO)存儲器的地址順序。如圖10A所示，所有輸入埠共享全部FIFO，而每一個埠並不使用預定的FIFO。為了共享該緩衝器，輸入網絡完成取與加功能作為前步操作。輸入到ATM交換網絡的信元儲存在輸入緩衝器20中，然後順序讀出，以便每個信元周期傳輸給拷貝網絡。
第三，將解釋拷貝網絡32的配置和操作。拷貝網絡32完成取與加功能和拷貝功能，以達到拷貝信元的目的。在一個信元周期中拷貝網絡32拷貝的信元最大數目是根據拷貝網絡32的容量決定的。在這裡，如果拷貝的信元數目超過了拷貝網絡的容量，則超過的信元在第二個信元周期拷貝。在這裡，可以將準備拷貝的一部分信元分割出來，並拷貝過去。在這種情況下，假定分割出來剩下的信元在下一個信元周期中拷貝。拷貝網絡32的取與加功能使用與輸入網絡12所用的相同的硬體完成。為了完成它們的拷貝功能，採用了榕樹網絡。完成上述功能的拷貝網絡32的細節如下。
第一，解釋拷貝網絡32的取與加功能。向所有輸入到各個輸入埠的信元提供拷貝信元數的功能是由拷貝網絡32的取與加功能完成的。完成取與加功能所要求的信元頭需要有一位表示信元拷貝數，並有數位寫著拷貝的信息。由取與加功能得到的信息被控制來完成通過拷貝算法完成實際的拷貝功能。這個拷貝信息是利用各個信元的拷貝數和整個信元的拷貝數，以(最小值，最大值)的形式形成的。
圖11A和11B表示8*8逆榕樹網絡，目的是解釋拷貝網絡32的取與加功能。在圖11A和11B中，假定在拷貝索引指針為0時，信元輸入到8個埠中，而在各個埠要求信元拷貝數為3，2，2，3，1，2，3，2。在這裡，信元拷貝數包括它本身(拷貝源信元)。拷貝索引指針指出在前一步的信元周期中信元反饋數，並且每個信元周期由反饋網絡52更新。這個數目是一個保留的數目，以便使在前一步的信元周期能夠首先通過路由選擇網絡63a-63d進行信元反饋。信元拷貝數的最大值是埠總數減去信元保留數所得的數目。
拷貝網絡32的取與加功能如下。
圖11A表示對從拷貝網絡32輸入埠拷貝到輸出埠的信元數進行累加時的取與加功能的第一步。拷貝的信元數累加的完成過程如下。
若有一個信元輸入到拷貝網絡的第一級2*2元件較高輸入埠，無論較低的輸入埠是否接收到信元，要求的信元拷貝數是寫在該元件的寄存器的。對輸入到第一級元件較高和較低的輸入埠的拷貝信元數進行求和，並送往較低的輸出埠。這個值輸入到與第二級連接的元件上。在第二級同樣地對這個輸入到該元件的值(指出信元的數目)完成與第一級相同的過程。在第三級完成與上述相同的過程。經過上述過程之後，對所有信元輸入所要求的信元拷貝數求和，並輸出到最後一級較低的埠。這個值在拷貝網絡32的下一個信元周期的取與加功能中並不用作指針。每一個信元周期拷貝索引指針都用反饋網絡接收到的值更新。
圖11B表示將拷貝索引從拷貝網絡32輸出埠傳輸到輸入埠的取與加功能的第二步。拷貝索引的傳輸操作完成如下。
在第三級最低的元件上，儲存在拷貝索引指針的值(例如」0」)加到在取與加過程第一步元件寄存器中的值上，並通過較低的輸入埠送往第二級元件。指針」0」通過輸入埠不加改變地傳輸給第二級元件。
第二級元件將從第三級輸入的值通過輸入埠傳輸到第一級。不管較低的輸入埠，傳輸的值加在取與加過程第一步寫入該元件寄存器中的值上，並送往第一級元件。
第一級元件將第二級接收到的值傳輸到較高的輸入埠，將該值加在第一步寫入元件寄存器的值上，並將結果送往較低的輸入埠。
經過上述過程之後，所有的信元都接收拷貝網絡的輸入埠數，由該拷貝網絡將根據它本身要求的信元拷貝數最後為各個信元拷貝的信元輸出。在圖11B中，從最高端的信元開始，這些信元接收0，3，5，7，10，11，13，16。
在一個信元周期中，信元拷貝數的最大值就是拷貝網絡的埠數。因此，在圖11B的例子中，最多只能拷貝8個信元。相應地，對於輸入第一、第二和第三埠的信元可以要求多少就拷貝和傳輸多少信元。但是，對於第四埠只能傳輸它自己，而剩下的在地下一個信元周期中進行拷貝和傳輸。這種情況稱作」分割」，在此過程中，一個信元要求的信元拷貝分幾個信元周期完成。在圖11B中，(3)是信元分割在下一個信元周期中輸入到拷貝網絡32的最高埠。這是為了防止分割的信元依次被分割。在圖11B中，拷貝數打了點的信元在下一個信元周期輸入，因為它超過了拷貝網絡32最大拷貝數。從前一信元周期中包括反饋信元的信元拷貝最大值減去信元反饋數而得到的值，是在一個信元周期中實際能夠拷貝的最大容量。
如前面解釋的，圖11A和11B表示8*8拷貝網絡的一個例子。如在這些附圖中，拷貝網絡32的取與加功能完成從輸入埠到輸出埠拷貝的信元數求和的第一步和將求和所得的信元拷貝索引從輸出埠傳輸到輸入埠的第二步。圖12表示規模為1024*1024的拷貝網絡32的取與加功能的第一和第二步。在圖12中，實線指示信元拷貝數的求和過程，就是說，取與加功能的前向周期。虛線表示拷貝索引的傳輸過程，就是說，取與加功能的後向周期。
在拷貝網絡32中，取與加功能之後，完成信元的拷貝。圖13A表示規模為8*8的拷貝網絡32當前(第n)步中的信元拷貝。圖13B表示規模為8*8的拷貝網絡32下一(第n+1)步中的信元拷貝。
信元拷貝就是取與加功能之後拷貝從拷貝網絡32輸入的信元。在拷貝網絡32中完成信元拷貝的值，是根據完成取與加功能而獲得的拷貝索引計算出來的。給每個輸入拷貝網絡32的各個信元算出數值，並寫入信元頭中。然後，信元拷貝算法所用的信元拷貝信息指出最小值和最大值，並通過信元頭加以傳輸。在這裡，從取與加功能獲得的拷貝索引成了最小值，而拷貝數加上拷貝索引得到的值變成最大值。在拷貝網絡32為N*N的情況下，拷貝信息(最小值和最大值)分別由log2N位組成。在1024*1024的拷貝網絡的情況下，拷貝信息要求10位。利用拷貝信息的這個值，8*8榕樹網絡中所完成的信元功能示於圖13A，為了便於解釋信元拷貝，將信元拷貝信息表達為[(min.1，min.2，min.3)，(max.1，max.2，max.3)]。
如圖13A所示，在拷貝網絡32的第一階段，信元拷貝信息[(min.1，min.2，min.3)，(max.1，max.2，max.3)]中的第一位min.1和max.1加以比較。若它們不等，則拷貝該信元，並送往兩個輸出埠。輸出的信元在第二階段經歷同樣的過程，小第二階段中，對所用的信元拷貝信息控制如下。
-輸出到較高鏈路的信元的信元拷貝信息(min.2，min.3)，(1，1)-輸出到較低鏈路的信元的信元拷貝信息(0，0)(max.2，max.3)，(1，1)若min.1和max.1相等，則不拷貝輸入信元，而這種情況又分成兩類，其值為0或1。在這裡，信元拷貝信息調整為拷貝信息(min.2，，，min.3)，(max.2，max，，，3)，兩者都不包括第一位。
-在0的情況下，信元傳輸到較高的輸出鏈路。
-在1的情況下，信元傳輸到較低的輸出鏈路。
在第二階段，從第一階段輸入的信元像第一階段一樣經歷同樣的過程，然後，對第三階段所用的信元拷貝信息調整如下。
-在完成信元拷貝的情況下，傳輸到較高鏈路的信元的信元拷貝信息(min.3，1)-在完成信元拷貝的情況下，傳輸到較低鏈路的信元的信元拷貝信息(min.3，max.3)-在不拷貝信元的情況下，信元拷貝信息(min.2，max.3)在最後階段，完成如同上述的過程，要求多少，就拷貝多少信元，並在最後信元拷貝網絡輸出階段從較高的鏈路順序輸出。
圖13B表示在下一個信元周期拷貝在拷貝網絡32的最高埠在前一信元周期進行的分割而剩餘的信元的過程。在當前信元周期中產生的分割的信元和拷貝數儲存在分割信元緩衝器，然後為了對它們進行拷貝，在下一個信元周期中輸入到拷貝網絡32的最高輸出埠。在圖13B，(1)是前一(第n)信元周期中被分割的信元，在第n+1信元周期輸入最高的埠。在第n+1信元周期分割的信元像(2)一樣存回分割的信元緩衝器。
拷貝網絡32的信元拷貝以這樣的方式完成，即從通過完成取與加功能獲得的拷貝索引中獲得信元拷貝信息，然後拷貝輸入信元拷貝信息的信元。圖14表示當拷貝網絡32以1024*1024的規模形成時，在拷貝網絡32中拷貝信元的過程。
反饋網絡52用與輸入網絡12相同的硬體形成的。圖15表示規模為1024*1024的反饋網絡52。反饋網絡將輸入的信元存入反饋緩衝器，然後依次地不留間隔地將信元從反饋網絡32的較高輸出埠輸出。反饋緩衝器是一個信元大小，每個埠一個，位於前方階段，供一個信元周期用。如圖15所示，在下一個信元周期中，當通過反饋網絡52的信元輸入路由選擇網絡63a-63d時，這並未增加傳輸的優先權。這個過程和取與加功能以及信元傳輸進輸入網絡12一樣。在反饋網絡52中，在取與加功能中緩衝器指針對於每一個信元周期總是從0開始的。在這裡，準備反饋的信元，由路由選擇/反饋控制器41為每個信元周期選擇的。關於反饋的信息，是根據反饋控制功能每個信元周期計算一次的。當在路由選擇/反饋控制器41中完成反饋控制功能時，只有那些不會由於輸出埠競爭而丟失的信元，才被輸入到路由選擇網絡63a-63d中。反饋網絡52魅信元周期提供拷貝網絡32的取與加功能用的指針。
路由選擇網絡63作成多個，目的是防止輸出埠競爭。在本發明中，假定具有分成兩級的32*32X-bar網絡的1024*1024的網絡，是由4個並聯的路由選擇網絡63a-63d構成的。若縱橫制(X-bar)網絡用於路由選擇網絡63，則儘管單元開關所用的硬體數量比榕樹網絡大，但交換性能卻是非常有效。因此，將縱橫制網絡用於路由選擇網絡63。圖17A表示由榕樹網絡構成的路由選擇網絡的一個例子。圖17B表示由縱橫制網絡構成的路由選擇網絡的一個例子。下表1表示由榕樹網絡或由縱橫制網絡構成路由選擇網絡這兩種情況引起的差異。若1024*1024網絡用規模為32*32的單元開關形成，如圖17A和17B所示，單元開關在這兩種情況下在概念上都具有相同結構，而不是內部結構和性能。
表1方式 榕樹網絡型 X-bar型 備註項目單元裝置32*32榕樹網絡 32*32縱橫制網絡單元裝置性能阻塞 無阻塞單元裝置 320個交點1024個交點的複雜性 (Nlog2N)x23(N2)N埠數單元裝置為單晶片 是是單元裝置之間shuffle full shuffle full shuffle路由選擇方式 自動路由選擇 自動路由選擇路由選擇網絡乘數 4平面 4平面(1024*1024) -在突發業務量下交換性能高達85％高達99.9％ -HOL BL soft(1024*1024) 應用其他 內部網絡應用 要求路由選擇網絡用的單元開關在本發明中，假定路1024*1024由選擇網絡63如圖16所示的方式形成，使用4個路由選擇網絡，以提高ATM交換網絡的性能。按照圖16所示的路由選擇網絡63a-63d的模擬結果，應該指出，在對輸入緩衝器20和輸出緩衝器(未示出)進行控制的同時，對路由選擇網絡的內部阻塞和輸出埠競爭進行控制，信元處理吞吐量為95％，並接近100％。
若路由選擇網絡63用多個並聯的方式形成，信元分割和信元合併必須與路由選擇同時完成。為此，信元分割器62和信元合併器64一起使用。信元分割器62用來將信元分布到路由選擇網絡63a-63d，而信元合併器64將從路由選擇網絡63a-63d到達各自輸出埠的信元進行合併。
下面聯繫整個結構解釋路由選擇。圖18表示信元分割器62和信元合併器64連同路由選擇網絡63a-63d的配置。受路由選擇/反饋控制器41內的路由選擇控制器的內部阻塞控制和輸出埠競爭控制的信元，被分割器62分割，並傳輸到路由選擇網絡63a-63d。在這裡，信元按路由選擇網絡63a-63d的內部阻塞控制和輸出埠競爭控制，順序地被分配到4個路由選擇網絡。輸入的信元自動路由選擇到路由選擇網絡63a-63d的輸出埠，並且傳輸到路由選擇網絡的同一個輸出埠的多個信元儲存到信元合併器64的輸出緩衝器，然後順序地將其輸出。
如圖18所示，信元分割器62將輸入到各個埠的信元分配到路由選擇網絡63a-63d，使得它們在不發生內部阻塞和輸出埠競爭的情況下進行傳輸。信元分割信息是從輸出埠競爭的防止和路由選擇網絡內部阻塞防止中得到。
如圖18所示，信元合併器64將輸出到路由選擇網絡63a-63d的同一個埠的多個信元儲存到信元合併器64的輸出緩衝器，然後順序地將它們傳輸出去。由路由選擇網絡63a-63d輸出的信元由選擇器儲存在輸出緩衝器內，以便在它們進行串/並轉換之後順序地選擇激活的信元。在這裡，激活的信元指的是它們實際上被傳輸到輸出埠。完成串/並轉換為了降低硬體的驅動速度。從路由選擇網絡63a-63d輸出的信元是160Mb/s的串行數據，當它們同時輸出時必須提高其速度。但是，現在，它很難用目前的硬體實現。
下面將參閱路由選擇表描述路由選擇/反饋控制器41的路由選擇控制。路由選擇控制包括路由選擇標記的加上和信元頭的轉換。路由選擇標記用來將所有的信元通過路由選擇網絡63a-63d傳輸到各自的輸出埠。在這裡，路由選擇標記是從諸如路由表42等與路由選擇有關的信息，利用虛擬路徑識別器(VPI)/虛擬通道識別器(VCI)和輸入埠識別器獲得。只要要求呼叫，儲存在路由表42中的路由選擇標記就被圖5的呼叫/連接控制處理器更新，並在此同時在一個信元周期內完成路由選擇控制1024/n信元。
信元頭轉換就是將路由選擇後並通過ATM交換網絡傳輸到其他節點的信元轉換成其他節點進行路由選擇用的信息。這個信息含有信元頭的VPI/VCI、有效負載類型識別器(PTI)和信元丟失優先權(CLP)。
從現在開始，將描述路由表42和信元格式。路由表42用來儲存信元的路由選擇信息，只要呼叫/連接被設置，圖5的呼叫/連接控制處理器就將路由選擇信息存入路由表42，而其狀態一直保持到它被釋放為止。路由表42具有圖19所示的結構。如圖9所示，路由表42包括路由選擇標記和各個信元用的信元頭轉換信息。信元的路由選擇標記是參照信元頭的單投連接識別器(VPI/VCI)、多投連接識別器和拷貝順序號。路由表42的特定結構和內容應與ATM交換網絡內部所用的信元頭的結構及功能以及特定的路由選擇方式聯繫起來研究。
ATM交換網絡的交換系統所用的信元頭結構是像圖20A和20B那樣形成。在這裡，圖20A表示ATM用戶/網絡接口(UNI)的信元頭。圖20B表示ATM網絡節點接口(NNI)中的信元頭。
本發明建議，ATM交換網絡的信元頭結構用在圖21的結構。在圖21所示的信元頭結構中，A是用來儲存一位的區域，指示信元是否激活。S/M/B(singlecast/multicast/broadcast，單投/多投/廣播)是由2位組成，是儲存指示單投、多投和廣播服務的位的區域。copy Info.(拷貝信息)由20位組成，是一個儲存信元拷貝信息的區域，它指示信元拷貝要求的最小值和最大值。MCN(multicast copy number多投拷貝數)由10位組成，是一個儲存指示信元拷貝數信息的區域。IPI/SRT(Input port ID/self-routing tag，輸入埠識別器/自動路由選擇標記)由10位組成，是一個儲存識別呼叫由之輸入並在路由選擇控制之後提供路由選擇標記的交換網絡輸入埠的信息的區域。VPI，8位，是一個儲存虛擬路徑識別信息的區域。VCI，16位，是一個儲存虛擬通道識別信息的區域。PTI，3位，是一個儲存有效負載類型識別信息的區域。CLP，1位，是一個儲存信元丟失優先權信息的區域。HEC(header error control，頭差錯控制)8位，是一個儲存頭差錯控制信息的區域。
下面將利用圖21說明內部交換網絡用的信元頭中所加的各種類型的信息。
首先，位A指示信元是否激活。S/M/B指示在單投、多投和廣播服務中，該信元屬於哪一種。Copy info.欄位指示信元拷貝要求的信息(最小值、最大值地址)。MCN用來區別多重信元拷貝。將拷貝的信元加以區分，就可以使它們各自的路由選擇控制得以完成，因為它們被傳輸到不同的目的地。IPI/SRT是識別信元由之輸入並在路由選擇控制之後提供路由選擇標記的交換網絡輸入埠的欄位。交換中使用的信元頭示於圖20A和20B，各種標準信元頭轉換功能是在ATM UNI和ATM NNI接口完成的。
下面將描述路由選擇網絡63防止內部阻塞行輸出埠競爭的方法。這個功能由路由選擇/反饋控制器41完成。基本上，這兩種功能都能完滿地完成，但是，可以按照交換網絡的性能要求選擇性地使用它們之中的一個。尤其是，可以僅僅選擇防止內部阻塞或輸出埠競爭，或者兩種功能同時使用。但是，為了得到更好的性能，兩種功能都應該完成。這是因為，即使使用了多重路由選擇網絡，並完成輸入埠控制，如果路由選擇網絡63沒有內部阻塞(控制)，交換性能還是要降低，同樣地，即使防止了路由選擇網絡的內部阻塞，有輸出埠競爭也是如此。在本發明中，兩種功能一起完成。首先完成路由選擇網絡63的內部阻塞防止，然後利用該結果完成輸出埠競爭的防止。在輸出埠競爭防止之前，先消除路由選擇網絡的內部阻塞。
路由選擇/反饋控制器41的反饋控制器計算在一個信元周期之前經受路由選擇網絡內部阻塞和輸出埠競爭的信元數。若該值超過在一個信元周期內能夠無內部阻塞和輸出埠競爭地通過的信元數，超過的信元數反饋到反饋網絡52，而不輸入到路由選擇網絡63。傳輸到反饋網絡52的信元，在反饋網絡52延時一個信元周期之後，在下一個信元周期中回去與輸入路由選擇網絡63的信元競爭。在這裡，反饋的信元控制得被首先傳輸，以便在ATM服務的虛擬連接內保持信元傳輸的順序。完成優先權控制，使得輸入到路由選擇網絡63較高埠的信元具有優先權。按照該功能，被允許傳輸到路由選擇網絡63的信元，被傳輸到信元分割器62，而這些信元被分散到路由選擇網絡63a-63d。下面將詳細地解釋各種功能。
首先，描述路由選擇網絡63內部阻塞的防止。路由選擇網絡63並非無阻塞網絡，因為1024*1024路由選擇網絡63是分兩級由32*32X-bar單元開關形成的。由於路由選擇網絡63的內部阻塞，這使交換性能惡化，故要求路由選擇網絡63有防止內部阻塞的功能。
在圖22A中，兩個路由選擇網絡63是用16*16個具有4*4單元開關的路由選擇網絡63並聯形成。在該圖中，位於第一級的元件被指定為源組(SG)，位於第二級的目的元件是目的組(DG)。
為了防止內部阻塞，各個開關元件都需要一個表，用來儲存信元要求哪個輸出埠。該表分成及格區域，分別對應各個目的元件。已經分開的區域再分割成對應於輸出埠數的區域。圖22A表示在路由選擇網絡像圖22A那樣形成時，完成防止內部阻塞的過程。
參考圖22B，說明防止內部阻塞的過程。在第一級的開關元件(SG)中，所述輸入需要的輸出埠的位置被分成目的組和輸出埠號，它們被寫入表中。
對於該表的各行要求同樣的DG的信元數超過2時，從各該行的第一個信元開始，只有兩個被給予輸入許可(ack)，而其餘都不被給予輸入許可。這一功能之後，許可多少，就讓多少信元輸入路由選擇網絡63，並由信元分割器62分布到路由選擇網絡63a-63d。
從現在起，將解釋防止輸出埠競爭的功能。
若在同一信元周期中有多個信元要求路由選擇網絡63的同一個輸出埠，這些信元在輸出埠上發生碰撞，從而引起信元丟失。為了防止這一點，在這些信元輸入路由選擇網絡63之前必須完成輸出埠競爭的防止。本發明的ATM交換網絡使用4個路由選擇網絡63a-63d，使得在路由選擇網絡63a-63d沒有內部阻塞的情況下有4個2信元同時到達同一個輸出埠。圖23表示在規模為1024*1024的路由選擇網絡63中控制輸出埠競爭的概念。如圖23所示，輸出埠競爭在概念上與防止路由選擇網絡63內部阻塞具有相同的結構和功能。
圖24A和24B舉例說明利用4*4單元開關的16*16路由選擇網絡63，用於計算輸出埠競爭的信元數的功能。在利用圖24A所示的路由選擇網絡63的情況下，兩個信元可能同時傳輸到同一個輸出埠。在圖24A的例子中，像圖22A和22B那樣獲得路由選擇網絡63防止內部阻塞的結果，不用來計算輸出埠競爭的信元數。
參閱圖24A和24B，計算輸出埠競爭的信元數的過程分成3步。
第一步SG元件內完成。
第一級單元開關元件寫入表中，而同時輸入的信元要求的輸出埠用目的元件和輸出埠號表示。
在第一級元件中，寫入表中的輸出埠目的地傳輸到相應的目的元件。
第二步在DG元件中完成。
在目的元件中，把從第一級元件接收的四個值存入其固有的表中。要求輸出到同一個埠的信元的數目不應當超過在4個步驟中受控制的有限的數目(在圖24A中最大為2)。
在該表的第一行中，對信元的數目求和，並且，直至求和結構的值不超過2的輸入許可才被示出。如果向具體埠的輸出請求至少是2並且只能輸出它們中的一個，那麼，把它變成1，並且用輸入許可表示(第一步)。
在第二行中，對於每一個輸出埠區、對在第一行輸入許可的數目求和，並且，直至求和的值不超過2時才示出輸入許可(第二步)。
在第三行中，對第一和第二行進行所述兩個步驟(第三步)。
在第四行中，對第一、第二和第三進行所述兩個步驟(第四步)。
在所述四個步驟之後，把所述結果輸送到對應的SG。把計算結果的第一行送到SG1，第二行送到SG2，第三行送到SG3以及第四行送到SG4。在所述SG元件中進行所述第三步。
接收來自目的元件的所述結果的SG允許把要求同一個輸出埠的信元中像被許可的那樣多的信元被輸入到路由網絡63，並且把其餘的信元輸入到反饋網52。
下面將說明信元分割。
在進行避免內部阻塞和外部競爭的操作時，利用所述結果來控制輸入到路由網絡63的信元，藉助於信元分割器62來分配被許可輸入到路由網絡63的信元，以便不引起內部阻塞和輸出埠競爭。就輸入到路由網絡63的各個埠的信元而言，在出現內部阻塞和輸出埠競爭的信元中，被許可輸入的信元的數目和並行的路由網絡63的數目一樣多。只有相當於許可輸入的信元數目的那些信元，才被順序地分配到路由網絡63a-63d。
圖25說明把從路由網絡63輸出的信元存入輸出緩衝器中的過程。下面將參考圖25描述所述輸出緩衝器的功能。
所述輸出緩衝器用於在同一個信元周期、同時接收從路由網絡63a-63d的同一個埠輸出的那些信元。為第一個輸出埠分配專用的緩衝器。因此，這種緩衝器的使用效率低於被所有埠共用的輸入緩衝器20的使用效率。
下面將描述單元開關的結構。
隨著交換網絡的容量變大，諸如本發明的ATM交換網絡的空分交換網絡急劇地增加硬體的數量。在實施大容量交換網絡時，把它分成用小容量的硬體製造的單元開關。此外，應當考慮把這些單元開關組合成整體的交換網絡的方法，並且，為了提高經濟效益，必須這樣設計所述交換網絡，以便把單元開關的種類減至最少、以及易於硬體的實施。為此，所述單元開關必須具有模件性。如果所述單元開關具有模件性，那麼，能夠進行整體交換網絡的規則裝配，並且其硬體的實施變得容易。如果所述單元開關不具有模件性，那麼，這些單元開關之間就不存在一致性，並且，必須使用許多具有不同結構的單元開關。這使所述交換網絡的整體結構複雜化。為了所述單元開關的規則裝配，在交換網絡的級聯中，需要ATM交換網絡的輸入埠的混洗(shuffle)。
下面將描述實施單元開關的方法。
本發明的ATM交換網絡由輸入網絡12、拷貝網絡32、反饋網絡52和路由網絡63構成。對於輸入網絡12和反饋網絡52，使用榕樹網絡。對於拷貝網絡32，使用逆榕樹網絡。對於路由網絡63，使用縱橫制網絡。這裡，通過改變榕樹網絡的輸入和輸出方向來產生逆榕樹網絡。所述榕樹網絡具有以下三個特徵。第一、在輸入埠和輸出埠之間存在單通道。第二，存在從一個輸入埠到所有輸出埠的各通道。第三，在輸入埠輸出埠之間不存在通道。
當如在本發明中那樣構成1024×1024的榕樹網絡或者逆榕樹網絡時，單元開關的容量必須是32×32，並且，兩級必須保持網絡的特性。在1024×1024的ATM交換網絡的結構中，如果未使用32×32的單元開關(在以下情況下，即，擴展到像使用16×16或者64×64的網絡的縱模製網絡)，那麼，所述整體交換網絡不能具有榕樹網絡或者逆榕樹網絡的所述特徵。這樣就不能得到所述ATM交換網絡的優點，並且難於控制所述網絡。
所述整體交換網絡的硬體的數量確定於所述單元開關的容量。在本發明中，考慮到當前的半導體技術、PCB的信號處理速度、以及輸入輸出引腳的數量，把單元開關的容量確定為32×32。圖26示出具有32×32的容量的榕樹網絡的結構。32×32的榕樹網絡具有32個輸入埠和輸出埠，並且由五級構成。每一級由16個2×2的元件構成。圖27示出32×32的逆榕樹網絡的結構。所述32×32的逆榕樹網絡是通過把圖26的32×32的榕樹網絡的輸入埠和輸出埠反向使用而得到的。
作為路由網絡63的單元開關的32×32的縱橫制網絡具有如圖28中的結構，並且，是一種無阻塞開關，不像榕樹網絡或者逆榕樹網絡那樣。
如上所述，本發明的ATM交換網絡具有如下的效果。首先，輸入緩衝器是所有輸入埠公用的，因此所述緩衝器被有效地利用。其次，避免了所述緩衝器的溢出，從而避免了信元的損失。第三，未把信元密集地存儲在專用的緩衝器中，從而把信元的傳輸延遲減至最小。第四，能夠進行具有極好的性能的高速度的信元交換。第五，能夠用相同的結構實施輸入網絡，拷貝網絡，和反饋網絡。第六，雖然所述交換網絡是單通道的，但是，由於使用多個交換網絡而具有多通道性能。從而消除了在多通道交換網絡的通道控制中遇到的困難。
因此，應當明白，本發明不限於這裡公開的。預期用來實現本發明的作好方式的具體實施例，應該說，除了像所附的權利要求書中限定那樣，本發明不限於本說明書中所描述的特定的實施例。
權利要求
1.用來實施異步傳輸方式交換網絡的裝置，其特徵在於所述裝置包括用來存儲輸入信元的輸入緩衝器，輸入開關網絡，它由預定尺寸的逆榕樹單元開關構成，並且具有輸入埠和輸出埠，所述輸出埠連接在所述各輸入緩衝器之間，所述輸入開關網絡執行取和加功能，其中，把輸入的信元的數目直接地從輸入埠加到輸出埠，並且，根據所加的信元的數目而把輸入緩衝器的地址直接地從輸出埠傳輸到輸入埠，所述輸入開關網絡根據由取和加功能計算的結果而傳輸輸入信元並且把它們存入所述輸入緩衝器中，路由選擇表，用來存儲用於翻譯和替換信元路由數據的數據，路由控制器，用來接收所述輸入緩衝器的信元，並且參考所述路由選擇表而對信元的輸出進行路由控制，路由開關網絡，其中，多個由預定尺寸的縱橫制單元開關構成的開關網絡並聯連接，所述開關對信元輸入進行轉換輸出，信元分割器，它連接到所述路由開關的輸入埠，所述分割器把信元路由輸出分割成所述路由網絡數，並且，把它們傳輸到所述路由開關網絡，以及信元合併器，它連接到所述路由開關網絡的輸出埠，所述合併器把從所述路由開關網絡的輸出埠分割和輸出的信元合併和輸出。
2.用來實施異步傳輸方式交換網絡的裝置，其特徵在於所述裝置包括用來存儲輸入信元的輸入緩衝器，輸入開關網絡，它由預定尺寸的逆榕樹單元開關構成，並且具有輸入埠和輸出埠，所述輸出埠連接在所述各輸入緩衝器之間，所述輸入開關網絡執行取和加功能，其中，把輸入的信元的數目直接地從輸入埠加到輸出埠，並且，根據所加的信元的數目而把輸入緩衝器的地址直接地從輸出埠傳輸到輸入埠，所述輸入開關網絡根據由取和加功能計算的結果而傳輸輸入信元並且把它們存入所述輸入緩衝器中，拷貝開關網絡，它由預定尺寸的逆榕樹單元開關構成，並且具有連接到所述輸入緩衝器的輸入埠，所述拷貝開關網絡執行取和加功能，其中，把拷貝的信元的數目直接地從輸入埠加到輸出埠，並且，把與所拷貝的信元數目相對應的拷貝索引直接地從輸出埠傳輸到輸入埠，所述拷貝開關網絡根據由取和加功能計算的結果而拷貝和傳輸從所述輸入緩衝器輸出的信元，路由選擇表，用來存儲用於翻譯和替換信元路由數據的數據，路由控制器，用來接收從所述拷貝開關網絡輸出的信元，並且參考所述路由選擇表而對信元的輸出進行路由控制，路由開關網絡，其中，多個由預定尺寸的縱橫制單元開關構成的開關網絡並聯連接，所述開關對信元輸入進行轉換輸出，信元分割器，它連接到所述路由開關的輸入埠，所述分割器把信元路由輸出分割成所述路由網絡數，並且，把它們傳輸到所述路由開關網絡，以及信元合併器，它連接到所述路由開關網絡的輸出埠，所述合併器把從所述路由開關網絡的輸出埠分割和輸出的信元合併和輸出。
3.用來實施異步傳輸方式交換網絡的裝置，其特徵在於所述裝置包括用來存儲輸入信元的輸入緩衝器，輸入開關網絡，它由預定尺寸的逆榕樹單元開關構成，並且具有輸入埠和輸出埠，所述輸出埠連接在所述各輸入緩衝器之間，所述輸入開關網絡執行取和加功能，其中，把輸入的信元的數目直接地從輸入埠加到輸出埠，並且，根據所加的信元的數目而把輸入緩衝器的地址直接地從輸出埠傳輸到輸入埠，所述輸入開關網絡根據由取和加功能計算的結果而傳輸輸入信元並且把它們存入所述輸入緩衝器中，拷貝開關網絡，它由預定尺寸的逆榕樹單元開關構成，並且具有連接到所述輸入緩衝器的輸入埠，所述拷貝開關網絡執行取和加功能，其中，把拷貝的信元的數目直接地從輸入埠加到輸出埠，並且，把與所拷貝的信元數目相對應的拷貝索引直接地從輸出埠傳輸到輸入埠，所述拷貝開關網絡根據由取和加功能計算的結果而拷貝和傳輸從所述輸入緩衝器輸出的信元，反饋開關網絡，它由預尺寸的單元開關構成，並且具有連接到所述拷貝開關網絡的輸入埠，所述反饋開關接收反饋的信元並且保持它們、直到下一個信元周期，路由選擇表，用來存儲用於翻譯和替換信元路由數據的數據，路由/反饋控制器，用來接收從所述拷貝開關網絡輸出的信元以及從所述反饋開關網絡反饋的信元，並且參考所述路由選擇表而對輸入的信元和反饋的信元進行路由控制，以及反饋在輸出埠衝突的信元，路由開關網絡，其中，多個由預定尺寸的縱橫制單元開關構成的開關網絡並聯連接，所述開關對信元輸入進行轉換輸出，信元分割器，它連接到所述路由開關的輸入埠，所述分割器把信元路由輸出分割成所述路由網絡數，並且，把它們傳輸到所述路由開關網絡，以及信元合併器，它連接到所述路由開關網絡的輸出埠，所述合併器把從所述路由開關網絡的輸出埠分割和輸出的信元合併和輸出。
4.用於異步傳輸方式交換系統的信元交換方法，其特徵在於所述方法包括以下步驟根據輸入的信元的輸入次序而順序地轉換和存儲輸入的信元，使得所有輸入埠共用輸入緩衝器，分析存儲在所述輸入緩衝器中的信元的標題，以便確定是否對它們進行拷貝，轉換待拷貝的信元，並且按照預定的數目對它們進行拷貝，參考路由選擇表，確定反饋信元和輸入信元的路由，並且反饋在輸出埠衝突的信元，在下一個信元周期中轉換和存儲所述反饋的信元，以及轉換被進行路由控制的信元、從而避免內部阻塞和輸出埠競爭。
5.異步傳輸方式交換系統的內部信元標題結構，其特徵在於所述結構包括用來存儲表示信元是激活的還是非激活的比特的區域，用來存儲表示單通道(singlecast)、多通道(multicast)和廣播服務的比特的區域，用來存儲表示需要拷貝的信元的最少數目和最大數目的信元拷貝信息的區域，用來存儲表示待拷貝信元的數目的信息的區域，用來在路由控制之後存儲用於識別開關網絡的存入所述信元的輸入埠並且提供路由標記的信息的區域，用來存儲假通道識別信息的區域，用來存儲假信道識別信息的區域，用來存儲有效負載類型識別信息的區域，用來存儲信元損失優先權信息的區域，以及用來存儲標題誤差控制信息的區域。
全文摘要
異步傳輸方式交換網絡的交換網絡和方法包括輸入緩衝器；執行取和加功能的輸入開關網絡；執行取和加功能的拷貝開關網絡；接收反饋的信元並保持它們直至下一個信元周期；存儲用於翻譯和替換信元路由數據的數據的路由選擇表；參考路由表對輸入信元和反饋信元進行路由控制的路由/反饋控制器；轉換-輸出信元輸入信號的路由開關網絡；把信元路由輸出信號分割成路由網絡數並把它們傳輸到路由開關網絡；合併和輸出路由開關網絡輸出埠的信元的信元合併器。
文檔編號H04L12/56GK1156367SQ9611798
公開日1997年8月6日 申請日期1996年12月24日 優先權日1995年12月26日
發明者宋德永 申請人:三星電子株式會社