數(shù)據(jù)通信笫十三講-交換機(jī)(編輯修改稿)
2025-08-31 17:03 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 口到來(lái)的負(fù)載服從 Bernoulli分布，每個(gè)時(shí)槽有一個(gè)分組到來(lái)的概率為 p。 ? 到來(lái)的分組的目的端口的選擇也是完全獨(dú)立的，所有目的端口被選中的概率相同，即在給定時(shí)槽內(nèi)一個(gè)給定的輸入端口有一個(gè)到某目的端口的分組的概率為 p/N – 對(duì)于某一個(gè)目的端口，在一個(gè)時(shí)槽內(nèi)有 i個(gè)分組到達(dá)該目的端口的概率為 P(i)： iNiiN NpNpiP C ??? )1()()(? 假設(shè)有 i個(gè)分組到達(dá)某一目的端口，所以對(duì)于一個(gè)給定目的端口，在一個(gè)時(shí)槽內(nèi)分組被丟失的平均個(gè)數(shù) A為： ? 對(duì)于一個(gè)給定的目的端口，在一個(gè)時(shí)槽內(nèi)到達(dá)的分組的目的端口正好就是該端口的概率為 N p/N＝ p。因此對(duì)于一個(gè)給定目的端口，分組的丟失率等于分組丟失的平均數(shù)除以到達(dá)分組數(shù) p： ?????NKiiPKiA1)()(?????NKiL iPKipP1)()(1? 丟失概率為： ? 如果 p=1，即總是有分組到來(lái)時(shí)的丟失率為： ? 當(dāng) K大于 8時(shí)丟失率為 O(106)，已經(jīng)達(dá)到一個(gè)相對(duì)較小的值，正是這點(diǎn)導(dǎo)致了Knockout交換機(jī)的出現(xiàn) ?????? ???? ???? KiippKL ipepKKepP0 !1)1(!?????? ???? ???? KiL ieKKeP011!1)1(!Knockout交換機(jī)（續(xù)） ? Knockout交換機(jī)有 N條廣播總線，每個(gè)輸入端口連接到相應(yīng)的總線上，每個(gè)輸出端口通過(guò)一個(gè)總線接口連接到所有的廣播總線上。 N個(gè)輸入 1 2 N 總線接口 N個(gè)輸出 Knockout交換機(jī)（續(xù)） ? 總線接口負(fù)責(zé)從 N個(gè)廣播總線上選擇最多 K個(gè)屬于該輸出端口的分組，選擇時(shí)要求采取公平的策略： – 分組過(guò)濾器從 N個(gè)廣播總線上選擇那些屬于本端口的分組 – 集中器選擇最多 K個(gè)分組，其他分組被丟棄 – 移位緩沖區(qū)由一個(gè)移位器和 K個(gè)單獨(dú)的 FIFO分組緩沖區(qū)組成 ? 移位器的作用是為了保證 K個(gè)分組緩沖區(qū)的 FIFO順序 ? 從集中器來(lái)的最多 K個(gè)分組通過(guò)移位器按順序輪流進(jìn)入到分組緩沖區(qū)中，輸出端口也按照順序輪流從緩沖區(qū)中選擇分組傳輸。 1 2 N 集中器 1 2 L 移位器 1 2 L 信元緩沖區(qū) 輸出 來(lái)自于 N 個(gè)廣播總線 信元過(guò)濾器 Knockout交換機(jī)（續(xù)） ? 集中器要求能夠從最多 N個(gè)分組中公平地選擇 K個(gè)分組。 – 最基本部件是一個(gè) 2 2的競(jìng)爭(zhēng)交換單元 ? 其功能是讓兩個(gè)競(jìng)爭(zhēng)者決定贏家和輸家，交換單元輸出的左邊是贏家，右邊為輸家，如圖 (a)所示 ? 圖（ b）給出了該競(jìng)爭(zhēng)交換單元的實(shí)現(xiàn)，只需要檢查左邊輸入端的比特值，如果為邏輯 1，則左邊的輸入被交換到贏家輸出端口，右邊的輸入被交換到輸家輸出端口，如果為邏輯 0，則右邊的輸入被交換到贏家窗口，而左邊輸入則不進(jìn)行交換。 贏家 輸家 （ a） 贏家 輸家 （ b） 1 贏家 輸家 0 Knockout交換機(jī)（續(xù)） ? 集中器除了交換單元外還包括延遲單元（用 D表示） – 延遲單元只有一個(gè)輸入和輸出，其主要功能是實(shí)現(xiàn) 1比特的延遲。 ? 集中器采用了類似于錦標(biāo)賽的思想 – 首先競(jìng)爭(zhēng)者通過(guò) 2 2交換單元兩兩競(jìng)爭(zhēng)來(lái)選取一個(gè)贏家， – 接著除了剛才的第一個(gè)勝者之外所有競(jìng)爭(zhēng)者再進(jìn)行一次錦標(biāo)賽來(lái)選出另外一個(gè)勝者。 – 除了前面兩個(gè)勝者之外的其他所有競(jìng)爭(zhēng)者繼續(xù)選出另外一個(gè)勝者，這個(gè)過(guò)程持續(xù)下去，直到選擇了 K個(gè)勝者為止。 – 競(jìng)爭(zhēng)過(guò)程中如果出現(xiàn)奇數(shù)個(gè)競(jìng)爭(zhēng)者的情況時(shí)，通過(guò)延遲單元等待從前面一個(gè)部分的競(jìng)爭(zhēng)中淘汰下來(lái)的競(jìng)爭(zhēng)者，同時(shí)延遲單元也用來(lái)保證所有的輸出都在同一個(gè)時(shí)刻完成。 D 1 2 3 4 輸出 輸入 D D D D D D D D D D D D D Knockout交換機(jī)（續(xù)） ? Knockout交換機(jī)的復(fù)雜性為 O（ N2） – 當(dāng) N比較大時(shí)，集中器的交換單元個(gè)數(shù)接近于 N K – 分組過(guò)濾器的個(gè)數(shù)為 N – 移位緩沖區(qū)的設(shè)計(jì)與 N無(wú)關(guān) – 每個(gè)輸出端口都有
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1