輸入排隊的基本思想是在輸入端解決可能的衝突問題。在交換單元的每一條入線上配置一個佇列緩衝器用來存儲信元。到達入線上的信元首先進入到其各自對應的輸入佇列中進行排隊。
基本介紹
- 中文名：輸入排隊
排隊思想,輸入排隊,性能,
排隊思想
在ATM基本交換模組中需要解決的一個最主要的問題是排隊問題。佇列的基本功能是暫時緩衝那些衝突的信元，例如傳同時去往同一出線的信元，交換單元內部為解決資源競爭問題而設計的佇列可以採用不同的策略來實現，在一個交換單元中為了解決對出線的競爭，可以根據佇列緩衝器配置的物理位置來講排隊策略分為3種：輸入排隊、輸出排隊和中央排隊。輸入排隊將佇列設定在交換單元的輸入連線埠（入線控制器）中；輸出排隊將佇列設定在交換單元的輸出連線埠（出現控制器）中；中央排隊將佇列設定在傳輸交換媒體上。這3種不同的排隊策略有著不同的實現方法和性能。
輸入排隊
輸入排隊的原理如圖所示。
在交換單元的每一條入線上配置一個佇列緩衝器用來存儲信元。到達入線上的信元首先進入到其各自對應的輸入佇列中進行排隊。所有輸入佇列均採用先來先服務的方式，以保持原有的信元順序。在每一個信元時隙（即信元的傳輸周期）中，各佇列只有對頭的信元可能得到服務，通過交換傳輸媒體被交換到其對應的目的出現上輸出。
由於信元流是統計復用的，在一個信元周期內可能會有多個佇列的隊頭信元選擇相同的目的出線。在出現這種情況時，交換單元中需要一個仲裁邏輯來決定哪一個佇列中信元能夠在當前信元時隙內得到服務，而其他信元將在各自的佇列中繼續等待，直到在以後的信元時隙中仲裁邏輯允許其傳輸。
在上圖中，交換傳輸媒體應該是一個無阻塞的信元交換傳輸網路。經過仲裁以後允許同性的信元在交換傳輸媒體中不會再出現競爭，直接被傳送到出線上輸出。這裡仲裁邏輯是必不可少的，以決定哪條入線可以得到服務。仲裁邏輯的實現方法可採用簡單的輪詢服務方式，也可採用複雜的優先權服務，或依據佇列的長度進行調度。
性能
輸入排隊最主要的缺點是存在對頭阻塞（HOL Blocking）現象。這是比較容易理解的。在一條入線上輸入佇列中快取的輸入信元，其目的出現通常情況下各不相同。如果對頭的信元因為競爭失敗而暫時無法得到服務，那么對頭信元的等待將使整個佇列中所有信元被迫等待。例如，假定某入線11的對頭信元的目的出線為O1，恰巧另一條入線I2的對頭信元的目的出線也是O1。仲裁邏輯判定入線I2首先獲得服務，入線I1上的信元則必須等待。這將導致整個入線I1的輸入佇列中的後續信元進入等待。即使I1佇列中的後續的第2個信元的目的是另外某個出線Ox，且Ox當時正處於空閒狀態，該信元也不能被服務，因為該信元牽頭的對頭信元阻擋著它的傳送。
在使用輸入佇列的交換單元中，一個信元時隙內實際通過交換傳輸媒體的信元數量p往往小於交換單元的輸入連線埠數。這是因為有可能存在某些入線，因對頭阻塞而導致在該信元時隙中不能傳送信元。
