計算機網絡（三）

（十一）路由算法

A、路由算法分類

動態路由和靜態路由

靜態路由：人工配制，路由信息更新慢，優先級高。這種在實際網絡中要投入成本大，準確但是可行性弱。

動態路由：路由更新快，自動定期更新，能夠快速及時反映網絡拓撲結構和網絡之間的費用變化。

全局信息路由和分散信息路由

全局信息路由：網絡中所有路由器都掌握整個網絡信息，拓撲結構和鏈路費用信息。這種方式在大型網絡中導致路由信息更新費用巨大，可行性不強。這種網絡下一般使用鏈路狀態路由算法。

分散信息：每個路由器僅僅只掌握與其物理線路相連的路由器以及鏈路費用，路由之間的更新也僅在鄰居路由器之間傳遞。這種網絡使用的算法為距離向量路由算法。

B、鏈路狀態路由算法

? 這種算法路由信息的更新一直在網絡中傳遞，直到所有路由器都更新完畢。

Difkstra算法是該算法的一種具體實現，現在通過下面一張圖演示該算法如何確定在一個網絡中如何確定到其他路由器的最短線路。

如上圖：u路由器是源路由器，D（v）等意為節點v到節點u的費用。P（v）意為v路由器的上一個路由器是誰，7，u就意為u到v費用為7。

第一步中列出所有其他路由器節點到u得費用，沒有直接物理連接的路由器（如y，z）表示為正無窮。

第二步，對比第一步中離u費用最低的寫入N‘，然后更新費用，可見更新后D（y）發生了變化，其到W的費用為11。

按上面步驟，最終得出了u到每個路由器的最短線路。故而得出U得最短路徑數，從而確定了u的轉發表：

可能存在的問題：震蕩（oscillations）的可能性

如上圖，根據數據轉發量確定費用，開始時C到B費用為e，C到D費用為0。其他信息看圖可得，第一次同時發送數據到A時路徑分別是：C-B-A ? ?B-A ?D-A，第二次從新判斷，B會認為B-C-D-A這條路費用為0+0+1比B-A線路更優，所以三個路由器路徑變化為圖二。同理再下一次又變為逆時針，然后順時針。

觀察上面我們可以知道，存在一種可能性，數據在到達D時，路由更新，數據又回到B，當要發送到A時，恰巧又更新了，則又轉回到D，該數據就有可能在TTL消耗完畢后丟失，無法到達目的地址。

C、距離向量路由算法

該方法每個路由僅僅關注自己附近的路由及其鄰居的路由信息即可。

Bellman-Ford方程是該算法的一個具體實現：

如上圖：當u要到達Z，u有三個鄰居路由節點X、V、W，它僅僅需要獲取他們到達Z路由器的最短費用（他們的最短費用也都是通過他們的鄰居一級一級獲得的），可見三個路由器到Z得費用分別是3，5，3，加上u到鄰居節點的費用則為4，7，8，所以對比可得最終費用為4，路線為u到x。

上面過程可以抽象出該算法的公式

向量就是路由器估計出的到其他路由器的最短路徑（費用）。

向量無窮計數問題：

如上圖：X、Y、Z三個路由器Y和Z同時要向X發送信息，下面演示線路費用變化后所引起路由更新導致的無窮更新問題：

本來：y到x，4<50+1=51 ，為4，z到x，50>1+4=5,為5。突然更新為60，y這時獲取的信息是z-x為5，z-y為1，y-x為60，所以更新y-x為6，6跟4發生變化，同步到z，z此時得知的信息為y-x為6，y-z為1，z-x為5，更新后z-x為7。然后就像下圖一樣，一直更新將近50次，才會停止。

如何避免該問題：

毒性逆轉（poisoned reverse）：如果一個節點到達某個目的的最小路徑是通過某個鄰居計算得到的，則通告給鄰居節點到達改目的的距離為無窮大。如上例，z到x的最小費用是通過y提供的y-x和y-z的費用1+4計算得到的，那么z通知y的就是z-x為正無窮。

這樣就解決了無限計算的問題。

C、分層路由

由于真實網絡是非常龐大的，不可能讓所有路由器都遵循一個路由算法，所以上面兩種算法都不可能統一在網絡實現，同時為了保證網絡自治性的要求，分層路由的思想真正被應用到internet網絡中。一批批路由器構成不同的自制系統，自制系統之間通過某些路由器互相連接，自制系統內部可以使用自己的路由算法，當涉及到和其他自制系統某個路由器的通信時，就通過自己系統跟目標路由器所在自制系統有連接的路由器獲取到達目標路由器的路徑信息，從而實現多級路由。（先在在自制系統中路由尋找到連接目標自制系統的路由器，再通過該路由器送達目標路由器）

如上圖，如果1b路由器想要發送信息到3c，那么1b首先根據1c更新到自己的信息獲得1c連接的是3c所在的自制系統，所以1b先將信息發送給1c，1c根據信息內容發送到AS3自制系統，AS3系統收到信息后根據自制系統間協議得知信息來源與去向，將信息轉發到3c。整個過程先用到自制系統內部協議，然后用到自制系統間協議，最后再用到自制系統間內部協議，所以可以看到一個分層的思想。

如果一個目標地址可以通過多個自制系統轉發到達，應該如何選擇，自制系統間協議遵循熱土豆原理，誰最快交給誰。

D、Internet網絡中的三種路由協議

RIP協議（自制系統內的距離向量路由算法）

該協議的RIP路由表通過一個應用層進行管理，名為route-d（daemon），RIP報文會周期性地封裝到UDP數據報中進行發送。數據報形式如下：

其自帶毒性逆轉技術當自己路由表中路由信息發生變化時會及時通知相鄰路由更新路由表，如果長時間沒有收到某個路由的最新通告則判讀該路由鏈路失效。

OSPF（自制系統內部的鏈路狀態路由算法）

其采用一種開放的公眾可用的協議，采用鏈路狀態路由算法，把一些路由器分成一個LS分組，組內路由和組之間路由進行擴散，利用Dijkstra算法計算最短路由路徑，形成完整了網絡拓撲結構圖。

OSPF報文是直接裝在IP數據報中的。

其優點如下：

安全，OSPF報文可以使用認證機制，防止惡意入侵。
允許同時使用多條相同費用的路徑（RIP只能選擇一條）
集成了多播協議可以進行單播路由和多播路由
其支持大規模的AS（自制系統）分層。

BGP（邊界網關協議，自制系統之間的協議標準）

該協議是將多個小的自制系統連接為一個大的整體的Internet互聯網的關鍵。

該協議提供了一種手段，讓自制系統的邊界網絡路由器能夠互相通知自己所能到達的子網（eBGP），同時也允許自制系統的邊界路由器向自制系統內部通知獲取到的其他自制系統所能到達的子網信息（iBGP）以達到自制系統中主干路由器選擇合適的邊界路由器去發送消息到正確的子網。

兩個BGP路由器之間傳遞消息需要建立一個BGP會話，該會話通過TCP協議來建立和保持連接，同時兩個BGP路由器之間交換的是去往不同目的子網的前綴信息，是具體的路徑。

在相互通報能夠到達的子網路徑時，BGP路由器會盡可能將網絡進行聚合，即網絡前綴的使用。

BGP報文有四種類型：

OPEN，與另一個路由器建立連接，并驗證發送方。
UPDATE，通告新路徑，當路徑發生變化，更新彼此路徑信息。
KEEPLIVE：在沒有更新的情況下，確保連接的正確和未斷開，需要發送該類型報文，同時也用于對OPEN報文的確認。
NOTIFICATION，當接收到報文有差錯時，發送該類型報文到對方，同時也用于關閉連接。

BGP報文中兩個重要屬性：

AS-PATH（AS路徑）：包含前綴通告所有經過的AS序列。
NEXT-HOP（下一跳）：開始一個AS-PATH的路由接口，指向下一個AS，下一跳可以同時存在多個鏈路。

BGP路由器的輸入策略：

同一個邊界路由器可能會獲得來自其他路由器的多條路徑到達同一個子網，這時會根據自己路由器的輸入策略來決定選用那條路徑來傳遞信息。

通常情況下，默認接收策略為選擇最短的AS-PATH，和根據熱土豆路由原則，先看到誰就直接拋給誰。當然也可以自定義策略，例如有些網絡路徑經過其他國家等敏感網絡，則將該條路徑pass。

運營商網絡和用戶（客戶）網絡：

E、AS間和AS內采用不同協議的好處（分層的好處）

不同的自制系統可以指定不同的路由策略，管理網絡信息如何被路由，單一管理，無需策略決策。

層次化的路由使上層路由器僅僅需要關注自制系統的邊緣路由器或者子網，大大縮小了路由表的大小，減少了路由更新的流量占用，同時也適應了大規模互聯網的要求。

實現了性能優先和策略優先。

七、數據鏈路層

（一）數據校驗和查錯

經常見到的糾錯和差錯方法有：漢明碼、奇偶校驗碼、校驗和、CRC（循環冗余校驗碼）等等。

（二）多路訪問協議

A、信道劃分（channel partitioning）MAC協議

我們前面提到的多路復用技術就是這里信道劃分協議的一部分，多路復用技術分為多種類型，包括TDMA（時分多路復用技術）FDMA（頻分多路復用技術）、CDMA（碼分多路復用技術）等等。

這種信道劃分協議，將固定頻率或者時隙分給不同的主機使用，在網絡壓力小的時候，有一部分主機沒有信息的傳遞就會出現頻率空閑，帶寬利用率不足。

但是在網絡壓力大時，每個主機都會用自己的頻段傳遞消息，這就讓網絡得到充分利用，效率比較高。

B、隨機訪問（random access）MAC協議

這種協議沒有規定誰來使用，信道不劃分，會有沖突產生，同時也必須有沖突處理機制，保證當沖突發生時，能夠及時處理沖突（比如重新發送等等）。

典型的隨機訪問協議有：時隙（sloted）ALOHA、ALOHA、CSMA、CSMA/CD、CSMA/CA等

時隙（sloted）ALOHA協議

如上圖，這種協議分成多個時隙，每個節點都可一在任何一個時隙開始時發送信息，當某個節點發送消息與其他節點發送信息沖突時就會以概率P，等待在下一個時隙重新發送（因為是概率P，所以存在下一個時隙沒有發送的可能性）。

優點：

單個節點活動時，可以沒有多路復用技術那樣空出多個時隙的情況，可以一個節點占用所有時隙發送數據和信息。
高度分散化，每個節點接入發送消息時，僅僅需要保證是在時隙開始時發送數據，在時隙結束前發送完畢數據即可。

缺點：

因為沒有分配時隙，所以當有兩個或以上節點占用同一個時隙發送數據時，就會產生沖突引起沖突恢復機制，浪費空間和時隙。
每個節點必須擁有相同的時鐘，保證時隙轉換的一致性。
節點也許能遠小于分組傳輸時間檢測到沖突。

考慮到沖突機制，這種協議經過計算，利用率最高能能夠達到0.37。

ALOHA協議

與上面協議不同該協議更加自由，因為沒有時隙劃分，所以任何節點都可以在任何時間開始發送數據，這樣同樣也就更容易產生沖突。

沒有時隙劃分，在沖突處理上可能會浪費更多時間，所以該協議的最大利用率要小于上面協議，僅有0.18.

CSMA(載波監聽多路訪問協議）（carrier sense multiple access）

為了防止沖突發生造成的帶寬性能浪費，所以該協議有檢測沖突的機制，每個節點在發送消息之前都會首先監聽信道，收到信道未被占用的返回包后才開始發送幀，根據監聽方式不同又分為三種不同的CSMA協議：

1-堅持CSMA，發現被占用一直保持監聽狀態，知道沒有占用后，發送幀。
非堅持CSMA，發現占用后，就解除監聽狀態。
P-堅持CSMA，發現占用后，隔一段時間后再次檢測占用情況。

當然，這樣也無法保證沖突的發生，因為鏈路的長度原因，當兩個節點同時檢測到鏈路未被占用，就同時發送消息，這樣就導致沖突的產生，所以該協議無法控制這種沖突的產生和解決。而且沖突發生后即意味著兩方發送的數據幀都失效，繼續傳送會浪費帶寬。

CSMA/CD

該協議增加了沖突檢測機制，在發送數據幀的同時也發送沖突檢測幀，當探測到有數據沖突后即刻終止數據發送，減少信道（帶寬）浪費。

沖突檢測原理，一般每個節點發送的數據幀都會有最大信號強度，當檢測到這個信號強度遠超最大值時，就可以判斷是多個數據幀疊加產生沖突的情況，從而終止數據發送，節省信道資源。

正是這一原理，所以有線局域網絡容易檢測到沖突產生，無線局域網絡因為信號會產生衰減，故難以通過上面方式監測出信號沖突問題。

要注意的問題：

存在上圖情況，當節點A和節點B同時準備發送數據，都監測到自己鏈路中沒有產生數據流，A的數據開始發送，就在快到達B時，被B監測到，那么A的沖突檢測觸發，為了保證A節點沖突恢復機制正常執行，數據幀的長度必須大于兩個節點之間的最大傳輸時延，不然A節點在收到沖突信息時，已經開始發送下一條數據，中間的沖突檢測也就沒有用處了。

C、輪轉訪問MAC協議

這種協議的出現是為了取上面兩類協議的長處，揚長避短，保證在網絡壓力大或者小的情況下，都能夠有不錯的表現。

輪詢：

在一個網絡中，主節點依次詢問從節點是否要發送數據幀，如果需要，就開始發送，沒有被詢問的從節點無法發送數據幀。

存在問題：輪詢時的確認和詢問數據幀會產生額外開銷、存在等待延遲、單點故障（主機宕機）

令牌傳遞

在一個環形網絡中，僅有一個令牌（特殊的數據幀），只有拿到令牌的主機（節點）才能夠進行數據幀的發送。

存在問題：

令牌傳遞產生的開銷、單點故障（環路上某個節點拿到令牌后宕機，令牌無法傳遞），等待延遲，當令牌傳遞出后，若恰好有發送消息需求，則需要等待令牌輪轉一周。

（三）MAC地址與ARP協議

A、MAC地址

IP地址是網絡層用來唯一標識網絡節點的地址，MAC是數據鏈路層唯一標識一個節點的地址，通常由48位bit標識，每個節點（網卡）都有一個唯一的MAC地址，數據鏈路層的數據幀尋址需要用到MAC地址。

MAC地址都處在一個平面，地址是唯一的，可攜帶，在任何一個地方都是唯一的。

IP地址具有層次性和地域性，同一個網卡，可能地點不同其對應的IP地址就不同，處于不同自制系統中IP地址一樣有可能不同。

B、ARP協議

每個網絡中的節點都需要共同維護一個ARP表，表中記錄了IP地址和MAC地址的映射關系，節點之間通過ARP協議，來更新和維護ARP表。

表結構：ttl是過期時間，一般是20min，當時間到后該條對應關系就會失效。

在同一自制系統中，MAC地址的獲取。

設網絡中有設備A、B、C、現在A要發送消息到C對應IP，但是A只知道C對應的IP地址，鏈路封裝的數據幀需要MAC地址，這時候先檢查A自身是否有對應關系，如果沒有，就利用ARP協議向本自制系統中的節點發送廣播消息，（廣播地址為全1，FF-FF-FF-FF-FF-FF）C在收到后，發現IP是對應自己，就根據ARP協議向A發送自己IP對應的MAC地址，A獲取后添加到ARP表中，就可以進行數據幀發送了。

跨自制系統的MAC地址確定

如上圖：當A要發送數據到B時，中間跨越自制系統，首先明確知道B的IP地址，A的IP地址和MAC地址。

首先A根據默認網關IP信息，通過ARP協議向路由器詢問默認網關的MAC地址，獲取MAC地址后，將數據幀封裝發送到路由器左端（默認網關）。

默認網關收到后，鏈路層移交網絡層，網絡層根據目的B的IP地址確認輸出端口MAC地址，同時廣播該目的IP地址，B收到后根據ARP協議反饋自身MAC地址到路由器右端（輸出端口），路由器鏈路層獲取到B的MAC地址后封裝數據幀，并發送。

數據到達B后，經過鏈路層解析，網絡層獲取的數據仍然是源主機的IP和自己的IP地址。（當然路由器會在局域網接入互聯網時修改網絡層數據報中源IP地址信息，這里沒有考慮路由器修改IP的情況）。

（四）以太網結構和所用協議

A、以太網結構

上世紀90年代中期前流行總線結構，如下圖（現多被淘汰）：

因為多臺機器共用一個總線（bus），所以當同時有兩臺設備發送數據時就存在沖突的可能性，像這樣在同一個總線上，公用一個總線互相同時發送數據會產生沖突的區域我們稱為沖突域。

星型結構：

中間通過一臺交換機（鏈路層設備）連接到一塊，因為每臺主機單獨擁有一個沖突域，所以不存在常理上的沖突現象。

B、以太網的特點

因為是鏈路層網絡，所以其具有以下特點：

無連接，發送幀的網卡和接收幀的網卡間沒有握手的過程。（傳輸層有做，這里沒必要）
不可靠，接收網卡不會向發送網卡進行確認，當有幀發生錯誤就會直接被丟掉，丟失幀引起的錯誤由上層處理。（傳輸層協議有做，這里也沒必要）

C、CSMA/CD（以太網采用協議）和二進制指數退避算法

描述協議過程，NIC是網卡的意思（可以理解為以太網節點之間的接口）

NIC從網絡層接收數據報，創建數據幀。
NIC監聽信道，直到信道空閑，停止監聽，并發送數據幀同時開始監聽
如果NIC發送完整個幀，并且沒有檢測到其他節點有數據發送（數據沖突產生），則NIC確認數據幀發送成功！
如果NIC檢測到其他節點發送和傳輸數據，則終止發送，同時發送堵塞信號（加強沖突幀的信號強度，讓其他節點盡早發現）
終止發送后，就根據二進制指數退避算法，等待一些時間，該算法跟沖突發生次數有關，沖突發生次數越多代表網絡壓力越大，等待時間越長。下面是算法大概過程：
???????
連續沖突次數超過16次后，一般認為網絡出現問題，報告上層處理。

D、以太網數據幀結構

preamble，前導碼，用來時鐘同步，第七個字節是10101010，第八個字節是10101011。

dest address 目的MAC地址；source address 源MAC地址；

type，指明數據鏈路層封裝的上層什么協議類型的數據，如IP協議等。?

data數據項，為了保證數據同步數據最小是（46字節），因為CSMA/CD協議的關系。

CRC（4B）：循環冗余編碼

（五）以太網交換機

A、什么是以太網交換機？有什么特點？

它是鏈路層設備，負責儲存-轉發以太網數據幀，其可以向一個或者多個MAC地址轉發數據幀。

它對于主機節點是透明的，主機感受不到交換機的存在。所以交換機也是即插即用的設備。

因為對于計算機節點是透明的，所以它當中用來確定轉發目的的轉發表，是通過自學習的方式完成的。

每個主機獨享一個鏈路直接連接交換機，交換機能夠對數據幀進行緩存。

交換機支持全雙工通信，每個連接到交換機上的主機都是一個沖突域，交換機具有沖突隔離的作用。

B、交換機的自學習過程

上面的交換機是剛剛連接到鏈路中的，這時A主機要向A‘主機發送數據，交換機如何完成自學習過程？

首先，交換機收到A（MAC地址）發送過來的數據幀，自學習開始，因為之前沒有收到過A的數據幀，所以交換機將A的MAC信息及對應端口記錄到交換表中（還會設置一個過期時間）。

因為同樣不知到A’對應地址的端口，所以交換機采用泛洪的方式，發送給所有連接到該交換機的所有設備，等到A‘收到消息，進行應答時，就可以被交換機學習到了，能夠記錄下A’對應端口。

C、交換機的幀過濾/轉發

當交換機收到數據后，會首先記錄MAC地址及其對應端口信息，然后利用目的主機MAC地址檢索交換表，檢查的結果會有三種情況：

情況一，目的主機和源主機的MAC地址相同，都接在交換機的同一端口，則該數據幀會被認為無需交換機參與即可實現傳遞，該數據幀會被直接丟棄。

情況二，交換表中還沒有數據幀要發送到的MAC地址對應端口，則采用泛洪方式發送到除源端口外其他所有端口。

情況三，如果找到目的MAC地址對應端口，則直接轉發到對應端口即可。

D、層次化交換機結構

在真實的局域網環境中，往往通過多個交換機連接，組成一個較大的局域網，當然這個大的局域網中的交換機都是同樣的自學習邏輯，與單個交換機并無二致。

我們可以進一步將眼光放高，看一看我們所謂子網，其實就是一個交換機構成的網絡（以太網、局域網），通過一臺路由器連接到ISP（服務商網絡），再接入互聯網：

因為在這個由交換機構成的范圍中，其中任何一臺主機發送一條廣播數據幀，都會被所有其他主機收到，所以我們可以稱該子網為一個廣播域。

E、對比路由器和交換機

路由器是網絡層設備，轉發依據是網絡層分組首部；交換機是鏈路層設備，檢測的是數據幀首部。

二者都使用轉發表，采用儲存-轉發模式對數據進行轉發；

路由器利用路由算法，根據路由協議計算出路由表，依據IP地址進行轉發。

交換機是自學習，對于主機是透明的，轉發表是自己構建的，不需要主機主動參與。

下圖是各種網絡層設備的對比圖：

直通傳輸就是指，不進行儲存，數據到達后直接進行處理（丟棄或者轉發），交換機和網橋通過一些設計是可以做到的。

F、VLAN（虛擬以太網）

有時候我們會遇到在同一個子網中，有不同部門的局域網，因為一個子網是一個廣播域，當我們需要僅將數據幀在一個部門中轉發時，就需要用到路由器或者VLAN技術，分別使用的是不同層的網絡設備來實現，路由器不必多言，僅看VLAN。

所謂VLAN就是利用一些上層軟件，將交換機的不同端口設置為一個分組，當同一個分組中有一個端口要進行廣播消息時，僅能夠在該分組中轉發數據。

因為是軟件設計的方法，所以不同端口之間也可以自由加入VLAN或者切換VLAN，這樣就實現了一個部門之間的廣播消息轉發。如下圖，一個顏色是一個VLAN分組。

那么不同交換機的同一組VLAN的數據如何進行轉發，每個交換機會留一個端口，專門用來連接交換機，這樣就實現了不同交換機之間相同VlAN的互通。

G、802.1q協議

與802.1協議的數據幀結構不同，該協議增加了4個字節用來處理VlAN技術中數據幀在交換機中轉發時數據端口的標識問題，增加的結構包含數據幀的VLAN ID信息，這樣就避免了多個VLAN之間轉發數據幀時的識別問題。具體結構如下圖：

兩個字節用來標識所用的協議、兩個字節用來標識控制信息：12bit用來儲存VLAN ID 信息、3bit用來記錄該數據幀的優先級。

（六）PPP協議（Point-to-point protocol）

是一種點對點鏈路控制協議，因為是點對點，是一對一的，所以不需要MAC多路分用技術。

A、該協議實現功能

組幀：將網絡層的數據報封裝到數據鏈路層的數據幀中，可以同時承載網絡層的協議分組，可以向上層實現分用（多路分解）。
比特透明傳輸：數據域必須承載任何比特模式。
差錯檢測：無糾正，一把交給傳輸層和網絡層來做，因為鏈路層都是一條線路先到先得。
連接活性檢測：檢測、并向網絡層通知鏈路失效。
網絡層地址協商：端節點可以學習和配置彼此網絡地址，以適應網絡環境尋址。

B、幀結構

首尾兩個字節是用來確定幀開始和幀結束的標志字節。

第二個和第三個字節暫時還未被采用，因為是點對點的所以第二個和第三個字節都沒有被采用。一般都是全1。

protocol，指定上層網絡層所使用的協議，不是固定的1字節或者2字節，字節數的確定需要通信雙方共同協商決定。

info，用來封裝上層網絡層數據報文，長度根據網絡層數據大小來定。

check，CRC數據校驗位，2字節或者4字節（雙方協商決定）。

C、數據透明傳輸實現

如何判斷標志位的數據不作為數據接收，如果有數據位跟標志位數據相同該如何正確識別數據位和標志位？

數據域中允許包含標志模式<01111110>,在數據的字節<01111101>和<01111110>前面添加額外字節<01111101>

規定出現下面情況，分別對應不同數據字節：

如果是單個<01111101>則表示一個填充字節。
連續兩個字節<01111101>則第一個會被丟棄，第二個就作為數據接收。第二個是<01111110>也會作為數據接收。
單個字節<01111110>,則代表是幀開始或者結束的標志字節。

所謂填充字節就是數據在傳輸過程中，根據協議添加進網絡層數據幀中的字節，如下圖：

（七）無線局域網

現在經常使用的是IEEE 802.11標準下的無線局域網，802.11有很多版本，每個版本在是否頻分多路復用方面有不同，具體見下表：

物理層中，802.11b使用的是直接序列擴頻技術（DSSS），在這種標準網絡下，所有主機使用相同的碼片序列，因此，不能進行頻分多路復用。

OFDM是正交頻分多路復用技術，在這種網絡中的主機使用相互正交的碼片序列，因此具有信道分配的作用，支持多用戶同時上網。

無線局域網有兩種類型：

不同無線主機通過基站連接到互聯網（基礎設施網絡模式）
不同主機直接無線互聯（自組網模式）

A、訪問點（AP access point）、基本服務集（BSS basic service set）

訪問點就是基礎設施網絡模式中的基站的代稱。

因為有不同基站，每個基站對應很多個無線主機，這一個基站和這些無線主機就構成一個基本服務集。

B、802.11AP關聯：被動掃描與主動掃描

被動掃描

各AP發送信標幀（基站定期向范圍內發送的信息，包括自己的IP地址和物理地址，以及已經連接的無線主機信息）
主機收到后，向選擇的AP發送關聯請求幀。
AP向主機（H1）發送關聯響應幀，確認無線主機和自己的連接。

主動掃描

主機（H1）主動廣播請求幀/
收到主機發送的請求幀后，則會向AP發送探測響應幀，響應主機
主機再次向選擇的AP發送關聯請求幀。
收到后，AP在權限允許的情況下，發送關聯響應幀。

C、CSMA/CA（802.11使用協議）

因為是CSMA協議，同樣每個無線主機或者AP在發送數據之前都要對信道進行監聽，如果有沖突就放棄發送，等待無沖突后發送，但是無法像CSMA/CA那樣在發送數據的時候檢測沖突的發生，因為無線信號在發送后就會產生衰減，無法從多個信號疊加產生大信號強度的特征中判斷沖突產生。同樣隱藏信號站也會引發沖突檢測不到的情況，假設三臺主機，A、B、C，A和B都能和C通暢通信，但是A和B之間就存在障礙物，A和B雖然物理距離近，但還是無法發送消息。

所以CSMA/CA協議采用應答方式判斷數據幀是否發送成功，接收方在收到數據后必須在規定時間內給出應答信號，負責發送方就認為數據幀發送沖突導致接收失敗。

同樣在幀聽到信道沒有數據發送后，發送方還要等待DIFS段時間，接收方在返回ACK幀時也應該等待一段時間，這些等待時間的長短代表著不同數據幀的優先級。

D、CA（如何避免沖突？）

發送方會先向接收方發送一段特殊的非常小的數據幀（RTS request?to send），用來探測沖突。

接收方在收到RTS后，會向所有節點廣播CTS（clear to send）幀作為RTS的響應。向其其非發送端節點發送是為了，通知他們不要發送，已經有人要發送數據了。

這樣就消除了隱藏站的影響，避免了數據沖突。

E、802.11網絡中數據結構

這里為什么有三個地址，我們重點搞清楚這個問題。

其實很簡單，因為發送方和接收方中間肯定要經過一個基站（AP），通過基站轉發信息到另一個接收方，故三個地址分別是發送方地址（源地址），基站地址、接收方地址（目的地址）

不同端的幀的三個地址對應不同，見下圖：

???????

1代表是，0代表否。

八、物理層

（一）數據通信基礎

A、通信過程圖示

信源：將消息轉化為信號的設備，例如計算機。

發送設備：將信源產生的信號進行適當變換的裝置，變化后能夠在合適的信道中傳輸，主要包括編碼和調制的過程。

信道：信號傳輸通道，如物理介質。

噪聲：指在數據（信號）傳輸過程中，自然界對其產生的干擾。

接收設備：完成發送設備反變換，從信道信號中還原出原始發送信號。

信宿：信號終點，將信號再次轉換為人能夠識別的消息。

B、數據通信術語

數據：傳送消息的實體。

信號：數據的電氣或者電磁表示。

“模擬的”：指參數值是連續的，更接近真實的信號。

“數字的”：對現實世界連續信號的采樣取值，參數的取值是離散的。

碼元：信號基本單元（如波形等）。

頻帶：信號頻率范圍（最高頻率-最低頻率）。

帶寬：常用信號頻率范圍（有效帶寬，在實際應用中經常使用帶寬，一些帶寬可能存在，但信號過弱，采用較少。

數據通信方式：單工（單向傳輸線路）、半雙工（輪流進行的雙向傳輸）、全雙工（同時進行的雙向傳輸）

并行通信和串行通信：并行通信指信道中一次傳遞多個bit，串行通信指信道一個bit一個bit傳輸。

C、異步通信與同步通信

異步通信：發收雙方采用不同時鐘，各自時鐘會存在一定誤差。

發送方和接收方為了防止誤差過大，所以一般一個字符（7bit）或一個字節傳輸，來保證個字節傳輸完成后，有一段時間來修正時鐘誤差。

在沒有數據發送時，線路保持低電平，當有信息傳輸時，變為高電平，第一個時鐘周期的高電平為起始，不計作數據，信號開始發送過程中，接收方按自己時鐘接收數據，每次接收數據都會產生誤差，如果一直接收的話，誤差過大會導致接收方接收遲緩數據丟失等問題，所以每個連續時間發送數據不能持續時間過長。

同樣當數據發送結束后變為低電平，等待下一次數據（字節）的發送。

異步通信的優缺點：簡單，發收雙方不用有復雜時鐘同步步驟，但是每個字節都會有時間間隔，數據傳輸效率低，信道空閑時間大。

同步通信：發收雙方使用同一個時鐘，時刻保持時鐘同步

為了保持時鐘同步常見做法是，每次發送數據時都帶上時鐘同步信息，接收方接收到后先同步時鐘再進行消息接收。

優缺點：信道充分利用效率更高，接收方需要時間成本同步時鐘。

D、模擬信號與數字信號

模擬信號是人或自然事物常表達的信號，多是連續的，如聲音信號。

數字信號，是電腦為了處理自然信號，每隔一段時間采樣轉化為數字信號的離散的信號（數據）。

如下圖，展示了兩種信號的不同點：模擬信號通常在信源階段，數字信號是發送設備轉換后的信號。

PCM（一種典型的信源編碼技術）

信源編碼就是將模擬信號轉換為數字信號的過程。

PCM分為三個步驟，如下圖：

采樣：就是得到原始信號在一系列時間點上的采樣值，如上圖的第二行。

量化：就是將采樣數據，做近似處理使數據更規范和易處理（以損失精度為代價），例如將3.2等小數全部抽象為整數，方便處理。

編碼：將量化后的數據進行一定的二進制數據對應，就像上圖倒數第二行，每個量化后結果用三個bit表示3就是011，編完后轉換成數字信號在信道發送。

接收方在接收到數字信號后，會進行還原，但是因為在發送方轉化過程中不可避免存在誤差，所以還原后的模擬信號，肯定和源信號有差異。就拿音樂來作比方，音質好的音樂，因為其轉化過程中采樣密度大，所以誤差小，更接近真實聲音。

（二）物理介質

分為導引型傳播介質（以來具體物質條件傳播），和非導引型傳播介質（無線電等依賴介質較多，無法界定固定介質）

導引型傳輸介質

A、架空明線

就是直接將電線架設在空中，一般用于戰時等條件簡陋，情況緊急等情況下，因為空中架設的電纜，容易收到外界電磁場的干擾，人為破壞，以及噪聲干擾等等，導致信號傳輸質量差，效率低。

B、雙絞線

雙絞線就是以兩根電線為一對，相互纏繞在一塊，多對再集合到一塊的物理傳輸介質。?

雙絞線有兩種類型，如下圖：

無屏蔽雙絞線：在絕緣層和最外層之間沒有屏蔽層，多被采用，因為屏蔽層是金屬材質，制造成本和技術要求更高，同時維修成本也高。

屏蔽雙絞線：隔絕性更好，更抗干擾，但是因為制造成本高，帶來優化小，很少被采用。

C、同軸電纜

現今多用在電視網絡的機頂盒上，同軸電纜又分為基帶型和頻帶型，現在機頂盒多是頻帶型。

Internet網絡中很少采用同軸電纜，同軸電纜結構如下：

D、光纖

多被網絡傳輸采用，具有傳播速度快，效率高等特點。

其傳播原理就是利用光的反射。

分為兩種類型：多模光纖和單模光纖兩類，結構如下：

左邊這類因為鉛芯較粗，所以光從不同角度入射后，反射所經歷的路程較長，中間因為光的折射所產生的損耗就越大，傳播速度相對較慢，但是制造成本相對低。

右邊采用更細的鉛芯，外模也采用單一模，所以光在傳播過程中是不斷進行全反射，速度更快，損耗更小，傳播更遠，但因為鉛芯較細，技術要求高，成本高。

非導引型傳輸介質

A、地波傳播

頻率較低（大約2MHz以下）的電磁波趨于延地球表面傳播

有一定繞射能力（地球是圓的，繞射就是一直沿著地面走）

在低頻段，地波傳播距離可以超過數百米甚至數千公里。

B、天波傳播

因為電離層的發現，所謂電離層是說在距離地表60-400KM的高度（這里電離層的厚度和高度都會變化）存在，能夠反射頻率較高的電磁波（2-30MHz）。

電離層的密度和厚度隨時間隨機變化。

利用這一原理，電磁波可以被傳遞到10000KM以上。

電離層就像一面大鏡子直接反射信號，只需一次。

C、視線傳播

頻率高于30MHz的電磁波將被穿透電離層，不會被反射回來。

沿地面繞射能力弱，空間上直接走直線。

通常是點對點無障礙的點對點直線傳播。

也可以通過中繼站，或者衛星等中繼設備，通過多次直線傳播實現遠距離非直線傳播。

D、常見非導引型波頻用途范圍表：

（三）信道和信道容量

A、信道

信道有廣義與狹義之分，如下圖：

上圖是細化的數據通信過程。

狹義信道就是指傳輸介質

廣義的信道，可以講視角繼續拉遠，放在調制器上看，調制器和解調器就構成調制信道。同理將眼光放在譯碼器和編碼器之間就是編碼信道。

恒參信道

各種有線信道和部分無線信道（如微波視線傳播鏈路、衛星鏈路等）。

理想的恒參信道是無失真傳輸信道。

對信號幅值產生固定的衰減，對信號輸出產生固定時延。

隨參信道傳輸特性

許多無線信道都是隨參信道，如隨著電離層不斷改變而參數不斷改變的天波信道。

信號衰減隨時間隨機變化。

存在多徑傳播現象。

信號傳輸時延隨時間隨機變化。

B、信道容量

信道容量就是指信道無差錯傳輸信息的最大平均信息速率。

下面直接展示兩種信道容量計算公式：

?（四）基帶信號基礎

A、相關概念

信源發出的原始電信號就是基帶信號。

模擬基帶信號：模擬信源。數字基帶信號：數字信源。

基帶信號往往包含較多的低頻成分，甚至有直流成分。

直接在信道中傳送基帶信號稱為基帶傳輸。

實現基帶傳輸的系統稱為基帶傳輸系統。

在信道中直接傳輸數字基帶信號，稱為數字基帶傳輸系統，相應的系統稱為數字基帶傳輸系統。

B、數字基帶傳輸系統

基帶信號比較適合在具有低通特性的有線信道中傳輸，通常不適合在無線信道中直接傳輸。

信道的傳輸特性會引起波形失真，并會受噪聲影響。

信道中的信號傳輸一定距離后，信號質量就會有所下降，甚至出現傳輸誤碼現象。

C、幾種信號碼元

單極不歸零碼

這種碼型僅有1和0，不歸零是指每個碼周期，可以全部是高脈沖或者低脈沖。高脈沖和無脈沖，代表數據，極易產生，但是不適合長距離傳輸。

雙極不歸零碼

這種碼型，有正脈沖，負脈沖，但是沒有0。分別代表0或1。

單極歸零碼

有正脈沖和0脈沖，分別代表0或者1。

碼元不為零的時間占一個碼元周期的百分比稱為占空比。（虛線內是一個碼元周期），在一個周期內，信號最后都必須歸零。

雙極歸零碼

有正脈沖和負脈沖，每次脈沖之后在一個周期內的最后一定也要歸零。中間每次歸零可以作為時鐘同步信號。

差分碼

差分碼又稱相對碼。

在兩個周期變化時，如果發生電平跳變就表示1，沒有就表示零（例子）

AMI碼（信號交替反轉碼）

該碼是為了滿足實際信號傳輸用上面的基本碼元對基帶傳輸系統所帶來的損害，例如單極不歸零碼有可能在很多個周期都是1，這樣就容易造成高電平累積，破壞設備。

所以要使用該碼元避免。

規定碼中的0編碼為AMI 傳輸碼中的0（0電平）。信號碼中的1交替編碼為AMI的+1（正脈沖）和-1（負脈沖）。

代表1的+1和-1代表1，這樣就能避免高電平堆積，還可以表示出多個1的數據傳輸情況。

雙相碼（曼徹斯特碼、差分曼徹斯特碼）

曼徹斯特（Manchester）碼

雙向碼只有正負兩種電平，每個bit在傳輸的持續時間中間時刻要進行電平跳變。例如在一個bit傳輸周期內（兩個虛線之間），在這個周期的中間時刻，信號從高電平到低電平這個bit就表示0。

因為雙向碼用了兩個脈沖表示一個bit，所以傳輸效率較低，早期的10Mbps的以太網就是用的這個曼徹斯特碼。

差分曼徹斯特碼

跟曼徹斯特碼很像，差分雙相碼的每個比特周期的中間時刻也要進行電平跳變，但是這個跳變僅僅用于時鐘同步。

早期的令牌環網就采用的是此種碼型。

利用每個bit周期的開始處是否存在跳變來表示編碼信息：如開始處無跳變則表示0，有跳變則表示1。如下圖：

???????nBmB

將n位二進制信息碼作為一組，映射成m位的二進制新碼組，其中m>n。

因為m>n,所以2^m個新碼組中，只會用到2^n個，可以多出來（2^m-2^n)個碼。

可以從2^m個碼中優選出2^n個碼作為有效碼，其余碼可以作為禁用碼，可以用于檢錯。

快速以太網，多采用這種編碼（4B5B）

（五）頻帶信號基礎

A、相關概念

基帶信號具有低通特性，可以在具有低通信道中進行傳輸。

許多帶通信道（如無線信道）不具有低通特性，因此不能在這些信道中直接傳輸基帶信號。只能利用基帶信號去調制對應的載波信號將基帶信號所攜帶的信息傳送出去。（說白了，就是無線方式是波的形式，數字電平信號無法傳輸，故要利用載波器，將基帶信號轉換為載波信號，這樣信息就可以通過無線波的形式進行傳遞。）

利用模擬基帶信號調制載波，稱為模擬調制。利用數字基帶信號調制載波，稱為數字調制。

數字調制就是利用數字基帶信號控制（或影響）載波信號的某些特征參量。

下圖展示了基帶信號轉換為載波信號在信道中傳播的過程。

頻帶傳輸系統通常選用正弦波信號作為載波：

由a來控制波的形式，a可以為0或者1（數字信號的基本bit數據形式）

二進制數字調制分為三種方式：

二進制幅移鍵控（2ASK）：通過數字信號，影響基本波頻的幅度來承載不同信息。
二進制頻移鍵控（2FSK）：通過數字信號，影響基本波頻的頻率來承載不同信息。
二進制相移鍵控（2PSK）：通過數字信號，影響基本波頻的方向來承載不同信息。

B、二進制數字調試

二進制幅移鍵控（2ASK）

利用二進制基帶信號控制載波信號幅值變化：

s(t)代表基帶信號，cos(2πft)代表原始載波信號。

下面一張圖展示基帶信號、載波信號、和幅值受影響變化后的再信道中傳輸的信號。

可見，原始載波信號在遇到基帶信號中的0時，頻帶幅度就直接被壓為0了。這樣不同幅度就代表了不同的信號0或者1。

二進制頻移鍵控（2FSK）

利用二進制基帶信號控制載波信號頻率變化：

二進制基帶信號為bn，載波信號還是cos(2πft)，但是里面f（頻率參數）會根據基帶信號不同采用兩種頻率f1和f2。

下圖展示，基帶信號信息被載波信號攜帶的過程。

上圖觀察發現，當基帶信號為1時，載波信號采用頻率較高的載波，當為0時載波信號采用頻率低的載波。通過不同頻率來區分出了基帶信號的二進制信息。

二進制相移鍵控（2PSK）

利用二進制基帶信號控制載波信號相位變化。

這里增加了一個變量?ψ代表給原始波增加的幅度（控制波的升降轉換，如果加上π，則方向會變），bn代表基帶信號分為兩種情況，當為0時無變化，為1時也無變化，一旦1到0（或者0到1）時，就會加上或者減去π，導致波本來的方向改變。這種就將通過波方向（頻幅短暫變化）來改變相同波所承載的信息。下圖展示相移鍵控載波信號承載信息的過程：