目錄

一、概述

?二、排隊策略

三、輸入排隊結構(IQ)

3.1 結構特點

3.2 改進方案? ?

四、輸出排隊結構（OQ）?

五、輸入輸出聯合排隊結構(CIOQ)

六、輸入交叉節點聯合排隊結構(CICQ)

---

一、概述

????????Crossbar是一種全連接的交換結構，由 M×N 個交叉點（Crosspoint） 組成，可實現任意輸入到任意輸出的直接互聯，常用于交換機、NoC（片上網絡）和FPGA互連。

?二、排隊策略

????????當你在晚高峰刷視頻卡頓，或是在線游戲突然延遲飆紅時，背后隱藏的其實是交換機內部的"交通堵塞"問題。數據包像車輛一樣涌入網絡設備，但資源有限——如何調度它們高效通行，而不至于堆積成"數據堵車"？

????????這個問題的核心在于排隊策略的選擇。不同的策略決定了數據包在哪里等待、如何競爭帶寬，并最終影響網絡的速度、延遲和成本。就像現實中的交通管理：

• 紅綠燈輪流放行 → 簡單但會出現"隊頭阻塞"，一個慢車卡住整條車道
• 給每個出口建專用停車場 → 零沖突但成本爆炸，如同在城市每個路口蓋巨型車庫
• 微型立交橋網絡 → 極致靈活，但設計和維護復雜度飆升
• 混合潮汐車道 → 折中方案，用少量緩沖換取性價比

????????就像現實中堵車有不同的疏導方案（比如紅綠燈、潮汐車道、高架分流），網絡世界也演化出四類經典排隊策略：

1. 輸入端排隊(IQ)?—— 所有車擠在收費站入口，先到先走，但隊頭一輛慢全隊遭殃
2. 輸出端排隊(OQ)?—— 給每個出口配專屬停車位，零沖突但需要海量硬件資源
3. 交叉點隊列(CICQ)?—— 每個路口設微型立交橋，極致靈活卻結構復雜
4. 混合排隊(CIOQ)?—— 在出入口都設緩沖帶，兼顧性價比的萬金油方案

????????想象你走進一個巨型快遞分揀站：

• 輸入排隊(IQ)：所有包裹堵在入口通道（類似早晚高峰的地鐵進站口），雖然節省了站內空間，但容易卡在隊頭。
• 輸出排隊(OQ)：包裹直接送到每個收件人的專屬貨架（像VIP通道），但需要超多工作人員和貨架空間。
• 聯合排隊(CIOQ)：入口和收件貨架都設臨時存放點（類似智能快遞柜），平衡了效率和成本。
• 交叉點排隊(CICQ)：每個傳送帶交叉口都有迷你貨籃（像蜂窩快遞柜），最智能但設備最復雜。

????????關鍵差異一句話：包裹在哪排隊？（入口？出口？還是交叉路口？）不同的選擇就像在"空間成本"和"分發效率"之間拔河！

三、輸入排隊結構(IQ)

????????輸入排隊（IQ）在Crossbar交換網絡前設置輸入緩存，數據分組先暫存于輸入端口，再經調度算法出隊，通過Crossbar傳輸至無緩存的輸出端口。其關鍵特征如下：

3.1 結構特點

????????由于Crossbar交換網絡每條輸出通道所連接的輸出端口的輸出速率是有限的，且輸出端口處和Crossbar節點不設置排隊緩存，需要在輸出端口空閑時才能讓各輸入緩存的隊列調度數據分組出隊，因此對于Crossbar網絡的單條通道來說，通道傳輸速率只需與輸出端口的輸出速率相同即可。

????????此時該結構加速比(交換結構內部速率與端口速率比值)為1，對于交換結構內部速率與緩存寫入讀取速率沒有太高要求，可擴展性較好。同時，在輸入排隊（IQ）交換結構中，仲裁器是必不可少的核心組件，其作用是為競爭同一輸出端口的數據分組分配傳輸權限。它的主要任務為：當多個輸入端口的隊列（如VOQ）都指向同一個輸出端口時（例如多個VOQ_i），必須通過仲裁機制選擇哪一個輸入端口有權發送數據，以避免數據沖突。

3.2 改進方案? ?

????????輸入排隊結構在輸入緩存只有單個先入先出(FIFO：First?In?First?Out)隊列時，會存在排頭阻塞(Head of Line，HOL)阻塞問題，當端口數較多時，會嚴重降低交換容量，比如所有輸出端口均勻分布的Bernoulli業務下，該結構只有58 .6％的吞吐率。

????????對于該問題，可以通過虛擬輸出隊列(Virtual Output Queue，VOQ)技術在輸入緩存處按照輸出端口設置隊列，以區別不同去向的數據分組。不過因為要區分多個隊列，類似于共享緩存結構，為了保障隊列之間的公平性，也自然要為每個隊列分配一定的緩存，如果端口數提升導致劃分隊列數增多，那么每個輸入端口處對于緩存資源的要求也會變高。

四、輸出排隊結構（OQ）?

????????輸出排隊（Output Queuing, OQ）是交換結構中的另一種典型設計，其核心思想是將排隊緩存移至輸出端口，而輸入端口和Crossbar內部無緩存。該結構雖然直觀且性能優異，但面臨嚴苛的硬件需求。

????????輸出排隊結構(OQ)在輸出端口處設置排隊緩存，輸入的數據分組先經過Crossbar交換網絡交換到對應輸出端口，然后再進入緩存排隊。由于該結構在輸入處和Crossbar網絡內部均不設置排隊緩存，當所有N個輸入端口同時輸入去向相同輸出端口的分組時，為保證此時不出現分組丟失，輸出排隊處的接收帶寬需要達到輸入端口的至少N倍線速(輸入端口速率相同)，即加速比需要達到N。可以看出，本質上這種結構還是共享緩存，只不過是將單通道的共享緩存拆成了多條通道、分布式的共享緩存交換，自然也就繼承了共享緩存的缺點。

五、輸入輸出聯合排隊結構(CIOQ)

????????輸入輸出聯合排隊結構（CIOQ）通過同時在輸入端口和輸出端口設置緩存，并采用具有有限加速比（1 < s < N）的Crossbar網絡，有效平衡了輸入排隊（IQ）和輸出排隊（OQ）的優缺點。?

????????輸入端的虛擬輸出隊列（VOQ）解決了HOL阻塞問題，同時輸出端的緩存以較低的加速比（如s=2）吸收突發流量，避免了OQ的N倍加速比需求，在保證接近100%吞吐率的同時顯著降低了硬件實現復雜度。然而，CIOQ的調度算法需要同時處理輸入和輸出端口的隊列狀態，使得算法復雜度較高，尤其在大規模系統中，集中式或分布式調度可能帶來較高的時延與資源開銷，對FPGA等可編程硬件的實現提出了挑戰。盡管如此，CIOQ仍是當前高性能交換架構的主流選擇，尤其在數據中心和核心路由器中，通過優化調度策略（如iSLIP或貪心匹配）和硬件加速手段，能夠較好地權衡性能、成本與可擴展性。

六、輸入交叉節點聯合排隊結構(CICQ)

????????輸入交叉節點聯合排隊結構(CICQ)是輸入排隊(IQ)和交叉節點帶緩存排隊(Crosspoint Queued，CQ)的結合，與輸入排隊的區別主要是在交叉節點上設置了用于排隊的一定數量緩存。該結構在交叉開關矩陣的每個交匯點部署獨立緩存，使得輸入和輸出調度完全解耦，輸入端可采用簡單的輪詢調度，而輸出端則可選擇更高效的匹配算法，這種分布式架構尤其適合多片FPGA協同實現。隨著端口數增加，輸入隊列和交叉點緩存的總容量與端口數N的平方成正比，帶來較高的硬件資源開銷，但得益于輸入/輸出調度的解耦設計，系統整體時延和吞吐率性能在大規模交換場景中仍具有優勢，成為可擴展交換架構的重要實現方式之一。