科學(xué)是使人變得勇敢的最好途徑?！剪斨Z

通信網(wǎng)絡(luò)問題

在通信網(wǎng)絡(luò)中，分為主機(jī)和路由器兩部分，我們將主機(jī)分為輸入端和輸出端，則構(gòu)成的圖中有三部分：路由器、輸入端、輸出端，構(gòu)成了一個(gè)有向圖。那么，一個(gè)N*N規(guī)模的通信網(wǎng)絡(luò)，應(yīng)該怎么構(gòu)成才能達(dá)到性能最佳呢（假設(shè)N總是2的整數(shù)次冪）？

二叉樹型

二叉樹是最容易想到的構(gòu)建方法，示意圖如下：

其中，圓形表示路由器，I矩形表示輸入端，O矩形表示輸出端，從左到右分別是主機(jī)0~n的輸入、輸出端。箭頭方向表示數(shù)據(jù)流向，沒有箭頭表示數(shù)據(jù)可以雙向流動(dòng)。
二叉樹型網(wǎng)絡(luò)的性能數(shù)據(jù)如下：

logN即以2為底，N的對(duì)數(shù)。接下來(lái)我們對(duì)這些數(shù)據(jù)進(jìn)行證明。

直徑

定義：一個(gè)網(wǎng)絡(luò)的直徑是從任一個(gè)輸入端到任一個(gè)輸出端的最遠(yuǎn)路徑。
不難從圖中看出，只要是經(jīng)過最上面的路由器的路徑都是最遠(yuǎn)路徑。一個(gè)完全二叉樹，最遠(yuǎn)路徑長(zhǎng)為2（1+logN）。

路由器規(guī)模

定義：最多同時(shí)有幾個(gè)IO流流經(jīng)一個(gè)路由器的數(shù)量，就是路由器規(guī)模。
求一個(gè)網(wǎng)絡(luò)的路由器規(guī)模，實(shí)際上就是看最多有多少鏈路經(jīng)過了同一個(gè)路由器，不難看出，在上圖中，第二層路由器經(jīng)過的鏈路最多，經(jīng)過了3條輸入鏈路和3條輸出鏈路，繼續(xù)擴(kuò)展輸入端和輸出端的數(shù)量，該規(guī)模也不會(huì)增大，因此規(guī)模為3*3.

路由器數(shù)量

定義：在一個(gè)網(wǎng)絡(luò)中使用的路由器的數(shù)量。
在網(wǎng)絡(luò)中的路由器數(shù)量就是2⁰+2¹+2²+…+2^logN，化簡(jiǎn)后得2N-1.

擁擠程度

在說(shuō)明這個(gè)概念之前，我們先明確一個(gè)觀點(diǎn)：輸入端和輸入端是雙射關(guān)系。然后我們給出擁擠程度的定義。
定義：在任意雙射關(guān)系中，路徑經(jīng)過同一個(gè)路由器的數(shù)量上限稱作這個(gè)網(wǎng)絡(luò)的擁擠程度。
設(shè)輸入端i所映射的輸出端f_i=n-1-i，那么每一個(gè)輸入端的數(shù)據(jù)都會(huì)經(jīng)過最頂端的路由器，此時(shí)擁擠程度最大，達(dá)到N，因?yàn)樽疃嘁簿褪荖個(gè)主機(jī)。

二維數(shù)組型

二維數(shù)組的示意圖如下：

輸入端從上到下分別對(duì)應(yīng)主機(jī)0-3，輸出端從左到右對(duì)應(yīng)主機(jī)0-3。
二維數(shù)組型網(wǎng)絡(luò)性能如下：

直徑

不難看出，最遠(yuǎn)路徑是從I₀到O₃，長(zhǎng)為2N。

路由器規(guī)模

在網(wǎng)絡(luò)上中間的路由器規(guī)模最大，有兩條輸入鏈路和兩條輸出鏈路穿過，因此是2*2，當(dāng)網(wǎng)絡(luò)再擴(kuò)展時(shí)，該規(guī)模不變。

路由器數(shù)量

路由器數(shù)量就是N²，沒什么好解釋的。

擁擠程度

列舉任意輸入端與輸出端的映射，可以發(fā)現(xiàn)最多只有兩條路徑在同一個(gè)路由器上交匯。圖中用藍(lán)線畫出的兩條路徑在第三行第三列的路由器交匯。所以擁擠程度為2；從另一個(gè)角度講，一行只能有一個(gè)路徑，而一列也只能用一個(gè)，一行一列定位一個(gè)路由器，所以當(dāng)占據(jù)該路由器所在行和列的路徑不同時(shí)，這個(gè)路由器的擁擠程度最高，為2.

蝴蝶型

蝴蝶型將二叉樹和二維數(shù)組結(jié)合起來(lái)，實(shí)現(xiàn)了一定的性能提高。示意圖如下：

注意，在這個(gè)網(wǎng)絡(luò)中，分別給行和列進(jìn)行編號(hào)，其中列用二進(jìn)制進(jìn)行編號(hào)。這樣，就可以方便的從看起來(lái)復(fù)雜的圖中抽象出信息：

如果一個(gè)路由器的坐標(biāo)是（b₀，…，b_l，…，b_logN，l），那么這個(gè)路由器可以連接（b₀，…，?b_l，…，b_logN，l+1）和（b₀，…，b_l，…，b_logN，l+1）。其中b₀到b_logN是列的各個(gè)二進(jìn)制位。例如（1，0，0，0）可以連接到（0，0，0，1）和（1，0，0，1）。

蝴蝶型網(wǎng)絡(luò)的性能數(shù)據(jù)如下：

直徑

該網(wǎng)絡(luò)的所有路徑長(zhǎng)度都相同，都是2+logN。

路由器規(guī)模

對(duì)于圖中1,2列的節(jié)點(diǎn)，有兩條輸入鏈路和兩條輸出鏈路，因此規(guī)模為2*2.

路由器數(shù)量

行列相乘即可，數(shù)量為N（1+logN）。

擁擠程度

該網(wǎng)絡(luò)的擁擠程度證明較復(fù)雜，但可以證明當(dāng)logN為偶數(shù)時(shí)，擁擠程度為N^1/2；當(dāng)logN為奇數(shù)時(shí)，擁擠程度為（N/2） ^1/2。

benes型

將蝴蝶型稍加改進(jìn)，即得到benes型網(wǎng)絡(luò)：

benes型網(wǎng)絡(luò)的性能如下：

直徑

benes型網(wǎng)絡(luò)的直徑與蝴蝶型類似，為1+2logN。

路由器規(guī)模

和蝴蝶型網(wǎng)絡(luò)相同，為2*2.

路由器數(shù)量

直接將行列相乘即可，為2NlogN。

擁擠

我們用歸納法證明benes型網(wǎng)絡(luò)中任意一個(gè)路由器的擁擠程度為1，假設(shè)P（n）：網(wǎng)絡(luò)中包含n臺(tái)主機(jī)時(shí)命題成立。

基礎(chǔ)步驟：證明P（2¹）。n=2時(shí)，網(wǎng)絡(luò)如下：

不論怎樣將輸入端映射到輸出端，四個(gè)路由器的擁擠程度都為1，因此P（2）=T。
歸納步驟：假設(shè)P（2ⁱ）=T。首先我們要弄清2ⁱ的網(wǎng)絡(luò)如何擴(kuò)展到2ⁱ⁺¹的網(wǎng)絡(luò)。注意我們的示例圖：

圖中用藍(lán)色框和黃色框框住的部分就是當(dāng)主機(jī)數(shù)量為4時(shí)的路由器網(wǎng)絡(luò)，因此從2ⁱ到2ⁱ⁺¹就是將2個(gè)2ⁱ網(wǎng)絡(luò)拼在一起，再將首尾各加一列路由器。由于我們假設(shè)P（2ⁱ）成立，因此綠色框中的路由器擁擠程度一定為1，而首尾兩列路由器擁擠程度也為1，因此只需考慮第1列和第4列路由器。
為了讓第1列擁擠程度為1，某些特定對(duì)的輸入端不能將數(shù)據(jù)發(fā)送到同一個(gè)顏色的框中。例如，如果000輸入端和100輸入端都將數(shù)據(jù)送入藍(lán)色框，那么他們一定會(huì)送到同一臺(tái)路由器；同理，對(duì)于第4列來(lái)說(shuō)，某些特定對(duì)的輸出端的數(shù)據(jù)也不能來(lái)自同一個(gè)顏色的框，例如000號(hào)輸出端和100號(hào)輸出端不能都來(lái)自藍(lán)框。有了這些特定數(shù)字主機(jī)之間的關(guān)系，我們可以構(gòu)造一個(gè)圖：
假設(shè)輸入端與輸出端之間的映射關(guān)系為：f₀=1，f₁=5，f₂=4，f₃=7，f₄=3，f₅=6，f₆=0，f₇=2，那么該圖可以構(gòu)造成：

如果兩個(gè)節(jié)點(diǎn)相鄰，那么他們不能將數(shù)據(jù)發(fā)送到同一個(gè)框中；藍(lán)色線說(shuō)明他們的輸入端可能鏈接同一個(gè)路由器，紅色線說(shuō)明他們的輸出端可能鏈接同一個(gè)路由器。于是，這個(gè)問題演變成一個(gè)涂色問題。下面是一種解法：0，2，3，5涂藍(lán)色，即他們將數(shù)據(jù)送入藍(lán)色框內(nèi)；1，4，6，7涂黃色，即他們將數(shù)據(jù)送入黃色框內(nèi)。通過這種方式，可以發(fā)現(xiàn)第1列和第4列的所有路由器都只有一條路徑經(jīng)過，擁擠程度為1.□

我是霜_哀，在算法之路上努力前行的一位萌新，感謝你的閱讀！如果覺得好的話，可以關(guān)注一下，我會(huì)在將來(lái)帶來(lái)更多更全面的知識(shí)講解！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-488415.html

到了這里，關(guān)于MIT6.024學(xué)習(xí)筆記（三）——圖論（2）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！