[發(fā)明專利]輸入緩沖交換機(jī)

無效

• 申請(qǐng)?zhí)枺?/td>: 200680006089.6
• 申請(qǐng)日: 2006-02-21
• 公開（公告）號(hào): CN101142792A
• 公開（公告）日: 2008-03-12
• 發(fā)明（設(shè)計(jì)）人: 特奧多魯斯·J·J·丹特涅;羅納德·里特曼;圣地亞哥·岡薩雷斯·佩斯塔納;尼克·布特;伊沃·J－b·F·阿丹
• 申請(qǐng)（專利權(quán)）人: NXP股份有限公司
• 主分類號(hào): H04L12/56
• 分類號(hào): H04L12/56
• 代理公司: 中科專利商標(biāo)代理有限責(zé)任公司
• 代理人: 朱進(jìn)桂

背景技術(shù)

網(wǎng)絡(luò)是以靈活的方式將多個(gè)系統(tǒng)耦合在一起的實(shí)際結(jié)構(gòu)。例如，這種網(wǎng)絡(luò)可以是局域網(wǎng)，用于將任意個(gè)數(shù)的計(jì)算機(jī)系統(tǒng)彼此耦合。此外，出現(xiàn)了NoC(芯片上網(wǎng)絡(luò))，作為用于在IP塊(知識(shí)產(chǎn)權(quán)塊)之間的未來芯片上互連的可能解決方案。IP塊是具有一些特定功能(例如，CPU、存儲(chǔ)器、DSP)的模塊。網(wǎng)絡(luò)包括至少一個(gè)路由器、以及彼此通信的多個(gè)功能單元或塊。與其它解決方案(例如總線)相比，這種網(wǎng)絡(luò)在塊數(shù)增加時(shí)易于縮放。

功能單元優(yōu)選經(jīng)由網(wǎng)絡(luò)接口與路由器耦合。網(wǎng)絡(luò)接口提供了至少兩個(gè)主要功能：(i)將塊本身的協(xié)議轉(zhuǎn)換為適于網(wǎng)絡(luò)的協(xié)議(網(wǎng)絡(luò)協(xié)議)，以及(ii)向通信提供額外的通信屬性和/或服務(wù)(例如，QoS、流控制)。直接與路由器連接的塊將必須自己實(shí)現(xiàn)所有這些功能。在另一方面，網(wǎng)絡(luò)可以包括模塊，如存儲(chǔ)控制器，用于自己提供這些功能。對(duì)于與網(wǎng)絡(luò)協(xié)議通信的公共管理和存儲(chǔ)器的管理會(huì)有利于存儲(chǔ)器的存取速率。

在網(wǎng)絡(luò)中，路由器必須管理可能彼此阻塞的多個(gè)數(shù)據(jù)業(yè)務(wù)流。例如，由于緩沖器輸出處的業(yè)務(wù)量等待后面的路由器的接受、或者由于兩個(gè)輸入想要進(jìn)入相同的輸出(競(jìng)爭(zhēng))，所以緩沖器輸出處的業(yè)務(wù)量可能會(huì)被阻塞。

已知多種排隊(duì)策略用于緩沖被阻塞的業(yè)務(wù)量。這些策略是：輸入排隊(duì)、路由器的每個(gè)輸入具有一個(gè)隊(duì)列。

輸出排隊(duì)。路由器的每個(gè)輸出具有用于來自每個(gè)輸入的數(shù)據(jù)的單獨(dú)隊(duì)列。

虛擬輸出排隊(duì)。每個(gè)輸入具有用于以每個(gè)輸出為目的地的數(shù)據(jù)的單獨(dú)隊(duì)列。

輸入隊(duì)列具有以下缺點(diǎn)：由于所謂線頭(HOL)阻塞而使吞吐量相對(duì)較低。當(dāng)隊(duì)列前端的數(shù)據(jù)正在等待傳輸至輸出時(shí)出現(xiàn)HOL阻塞。這進(jìn)而阻塞了隊(duì)列中其它數(shù)據(jù)的傳輸，即使這些其它數(shù)據(jù)具有自由輸出作為目的地。

該問題通過輸出排隊(duì)和虛擬輸出排隊(duì)來克服。然而，這兩種解決方案需要大量存儲(chǔ)器來實(shí)現(xiàn)隊(duì)列。

多輸入排隊(duì)是嘗試?yán)糜邢薮鎯?chǔ)量獲得合理吞吐量的解決方案。由于存儲(chǔ)器是芯片上的稀缺資源，所以這對(duì)于芯片上網(wǎng)絡(luò)尤其重要。在多輸入排隊(duì)的情況下，每個(gè)輸入具有多個(gè)隊(duì)列。到達(dá)輸入的業(yè)務(wù)量根據(jù)其目的地在隊(duì)列上分布。通過Kolias，C.和Kleinrock，L.的“Throughput?analysis?of?multiple?input?queuing?in?ATM?switches”描述了分布輸入業(yè)務(wù)量的已知方式。在MASON，L.和Casaca，A.(Eds.)：Broadband?communications(Chapman&Hall，London，UK，1996)，pp.382-393中提出了根據(jù)所謂奇偶規(guī)則在第一和第二隊(duì)列上分布業(yè)務(wù)量。該規(guī)則將以奇數(shù)編號(hào)的隊(duì)列為目的地的分組分配給第一隊(duì)列，以及將具有偶數(shù)編號(hào)的目的地的分組分配給第二隊(duì)列。以這種方式，具有奇數(shù)編號(hào)的目的地的流不會(huì)阻塞具有偶數(shù)編號(hào)的目的地的流。多輸入排隊(duì)需要明顯小于輸出排隊(duì)或虛擬輸出排隊(duì)的存儲(chǔ)量，而與(單個(gè))輸入排隊(duì)相比，吞吐量仍然顯著提高。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種用于網(wǎng)絡(luò)的路由器，其進(jìn)一步提高了吞吐量而不會(huì)增加存儲(chǔ)器需求。

根據(jù)本發(fā)明，該目的通過權(quán)利要求1來實(shí)現(xiàn)。

根據(jù)本發(fā)明的措施基于以下觀察。

路由器的吞吐量取決于可以傳輸數(shù)據(jù)的輸入個(gè)數(shù)。如果每次數(shù)據(jù)分組可以從每個(gè)輸入傳輸至輸出，則吞吐量為1。如果平均起來，數(shù)據(jù)分組可以從Ni輸入中的n個(gè)傳輸至輸出，則吞吐量是n/Ni。通過可以傳輸?shù)姆纸M片段的加權(quán)平均來計(jì)算吞吐量。

為此，將路由器的狀態(tài)定義為矩陣O，其中，O＝{o_ij}，o_ij指示作為輸入Ii處的隊(duì)列j的HOL分組的目的地的輸出。吞吐量$T=\underset{n=1}{\overset{N_i}{\mathrm{\Σ}}}{p}_n\frac{n}{N_i}$，其由

p_n是將n/Ni的分組傳輸至輸出的狀態(tài)出現(xiàn)的概率。