国产成人超清在线视频,国产高清永久免费,国产最新超碰97上传无码,超碰国产人人草人人爽

對于廣播，我相信在現(xiàn)實生活中我們時常都能接觸到，例如學校一言不合就響起了校歌，搞的全校人都能夠聽到，想假裝沒聽到都不行。

假如我們把學校比作一個局域網(wǎng)的話，某臺主機發(fā)起了一個廣播，意味著局域網(wǎng)內的其他所有主機都會收到這個廣播，那發(fā)起廣播的主機是如何選擇路徑來給其他主機發(fā)送廣播分組的呢？考慮下面由幾個節(jié)點組成的網(wǎng)絡：

假如節(jié)點 R1 要做一個廣播給 R2, R3, R4 發(fā)廣播分組，顯然，一種很簡單的方法就是 R1 給 R2、R3、R4 三個節(jié)點分別發(fā)一次廣播分組，這意味著 R1 一共要發(fā)送三次同樣的廣播分組。

途中不同箭頭的顏色表示 R1 給不同的節(jié)點發(fā)廣播分組。

大家想一個問題：這種發(fā)送方式合理嗎？

是的，這種發(fā)送方式在實現(xiàn)上很簡單，源節(jié)點（R1）每次帶上目的節(jié)點的地址，然后發(fā)送給它就行了。

不過這種方式在效率上是極低的，例如，R1 發(fā)送的這三個廣播分組都會經(jīng)過同一段鏈路（R1-R2這段鏈路），而且 R2 要是再連接上 n 個節(jié)點的話，代表著這 R1 需要再發(fā)送 n 次廣播分組，這 n 個報文也會經(jīng)過同一段鏈路。

解決方法

為了解決這個問題，我們或許可以這樣做：R1 把廣播分組發(fā)給它的鄰居節(jié)點 R2，然后 R1 就不管了，R2 再把報文發(fā)送給它的所有鄰居節(jié)點 R3、R4 （除了從其接收該分組的那個鄰居 R1）。

顯然這種方式也是挺不錯的，R1 只發(fā)送了一次廣播分組，而且 R1-R2 這段鏈路也不會出現(xiàn)同一個廣播分組重復經(jīng)過的情況。

廣播風暴

不過，這種給所有鄰居節(jié)點發(fā)送廣播分組的方式夠優(yōu)雅嗎？

看下面的一個網(wǎng)絡組成：

按照剛才的方法，R1 會給 R2 發(fā)送廣播分組，接著 R2 會給 R3、R4 發(fā)送廣播分組。剛才我們說過，收到廣播分組的節(jié)點會給它的所有鄰居發(fā)送報文（除了從其接受到該報文的那個鄰居）。

所以這個時候 R3 會給 R4 發(fā)送廣播分組文，而 R4 接收到 R3 的廣播分組之后，R4 會給 R2 發(fā)送廣播分組，R2 收到 R4 的廣播分組之后 ，也會給 R3 再次發(fā)送廣播分組…..

如果節(jié)點中形成了一個圈，那么就會像上面那樣，節(jié)點之間不停發(fā)送廣播分組，這時網(wǎng)絡上充斥著大量重復的廣播分組，將會嚴重影響資源的利用。

我們也把這種情況稱之為廣播風暴。

控制廣播風暴

因此，我們必須想出某種策略來控制這種廣播風暴。

一種很簡單的方法，就是給這一份廣播分組做一個標記。例如，源節(jié)點（發(fā)起廣播的節(jié)點）可以將其地址以及廣播序號放入這個廣播分組中，然后發(fā)送給它的所有鄰居節(jié)點，每個節(jié)點會維護它已經(jīng)收到的、轉發(fā)的源地址和廣播分組的序號列表。

當節(jié)點收到一個廣播分組時，會檢查這個廣播分組是否之前接收過（可以通過源地址、報文序號來檢查），如果接收過，就把該廣播分組丟棄；否則，把該廣播分組接收，且向所有鄰居節(jié)點轉發(fā)。

例如對于下面由 7 個節(jié)點組成的網(wǎng)絡：

如果節(jié)點 A 要做一個廣播，那么 A 就會給其鄰居節(jié)點 B、C 發(fā)一份廣播分組，B、C 也會給其的鄰居節(jié)點發(fā)送一個廣播分組。意味著 B 會給 C、D 發(fā)送廣播分組，而 C 也會給 B、E、F 發(fā)送一份廣播分組：

當 B 收到 C 發(fā)給它的報文時，B 檢測到已經(jīng)有了該報文，所以 B 會丟棄 C 發(fā)送給它的廣播分組，C 也一樣會丟棄 B 發(fā)送給它的廣播分組。圖中青色的箭頭代表該廣播分組會被丟棄。

從圖中不難看出，就算節(jié)點之間形成了圈，也不會出現(xiàn)節(jié)點之間循環(huán)轉發(fā)的情況。

雖然該方法簡單 ，但確實有效控制了廣播風暴，當然，這只是控制廣播風暴的方法之一，實際上還有其他方法，在此我就不說了。

生成樹廣播

雖然上面那種方法有效控制了廣播風暴，但也存在著很多冗余廣播分組（那些被丟棄的廣播分組就是冗余的廣播分組）。

如果可以，我想讓每個節(jié)點僅接收一次廣播分組，也不用考慮丟棄廣播分組，所以理想的情況應該是這樣：

有沒有一種方法，可以讓廣播分組像上面這種情況來傳送呢？請大家看下面一個圖：

如果把節(jié)點當作一個圖的頂點，大家觀察下左邊的圖與右邊的圖有什么聯(lián)系。

右邊的圖不就是左邊圖的生成樹嗎？(學了這么多年的生成樹，終于用到了)，如果我們給每一段鏈路加上相應的費用，那么我們最理想的情況就是找到一顆最小生成樹。

所以，我們最理想的情況就是讓廣播報文在最小生成樹的路徑中傳送，于是 ，我們現(xiàn)在的問題就是找出這些節(jié)點組成的網(wǎng)絡中的最小生成樹。

那么，如何構造一顆生成樹呢？下面提供一種基于中心某個中心的方法來建立一顆生成樹。注意，是生成樹，不是最小生成樹。

該方法是這樣的：我們先選出一個中心節(jié)點，然后其他節(jié)點向這個中心節(jié)點發(fā)送加入樹報文，加入樹報文經(jīng)過的路徑，都會被嫁接到生成樹上。例如對于這個網(wǎng)絡結構：

我們選擇 E 為中心點，然后其他節(jié)點給 E 發(fā)送加入樹報文：

1. F 節(jié)點給 E 發(fā)送加入樹報文，此時 E-F 鏈路成為初始生成樹，如下圖（紅色路徑表示生成樹）。

2. 接著 B 給 E 發(fā)送加入樹報文，假設 B 經(jīng)過的路徑是 B->D->E。此時路徑 B-D-E 也加入了生成樹。

注：D 不用再發(fā)送加入樹報文了，因此它此時已經(jīng)在生成樹里了。

3. 接著 C 給 E 發(fā)送加入樹報文，C-E 加入生成樹。

4. 接著，A 給 E 發(fā)送報文，假設 A 選擇的路徑是 A->C->E。不過當 A 的報文到達 C 之后，由于原本 C-E 就在生成樹里面了，所以 A 的報文不用經(jīng)過 C-E，A-C 就加入到生成樹了。

5. 最后 G 通過 D 加入生成樹。

到此，生成樹構建完畢，此時生成樹如下：

然后在廣播的時候，就可以沿著這條路徑來轉發(fā)復制廣播報文了。