我發現我最近瘋狂放屁，不知道怎回事，難道是最近吃的東西不太好，或者是天氣的緣故?

　　應該是這樣的，不然我身體前一段時間體檢的時候好好的，怎麽會突然開始就瘋狂放屁了。看來這每天吃的東西想當關鍵，不能在胡亂吃了。

　　明天就要面試了，說實話，還是有一點點小小的緊張，畢竟這個工作對我來說，也是相當的不錯，離家近，工資還高。

　　如果入職的話，相當不錯。

　　今天是面試前的最後一天，我居然在網上找到了倆個同崗位的人。

　　人在面對這種倆面性事情的時候，不管哪種情況的發生，都會又開心又難過。

　　我開心的是總算找到有和我同崗位的人了，至少找到就說明了這些人不可能是關系戶，不會是那種子弟，至少我們還是有著相互競爭的同一平台，不會是那種你就想都不用想了，已經注定是人家的囊中之物。

　　難過的是居然還是有人要面試，那就是說明我這個崗位放棄的人其實並沒有多少，估計最多一倆個，甚至一倆個都沒有，只能到時候努力面試了。

　　而且這還是面試前的最後一天，我感覺我有點炸裂，難以接受這個事實，如果說早一點發現這麽多人，我就還能接受，但是最後一天，突然蹦出來這麽多人。唉，管他呢，到時候再看吧。

　　今天還認真的複習了昨天沒有複習完的，接上。

　　三、數據鏈路層

　　1.功能(要解決的問題)

　　成幀(Framing)

　　將比特流劃分成“幀”的主要目的是為了檢測和糾正物理層在比特傳輸中可能出現的錯誤，數據鏈路層功能需借助“幀”的各個域來實現

　　差錯控制(Error Control)

　　處理傳輸中出現的差錯，如位錯誤、丟失等

　　流量控制(Flow Control)

　　確保發送方的發送速率，不大於接收方的處理速率，避免接收緩衝區溢出

　　2.數據鏈路層提供的服務

　　1.無確認無連接服務( Unacknowledged )

　　接收方不對收到的幀進行確認

　　適用場景:誤碼率低的可靠信道;實時通信;

　　網絡實例:以太網

　　2.有確認無連接服務( Acknowledged )

　　每一幀都得到單獨的確認

　　適用場景:不可靠的信道(無線信道)

　　網絡實例:802.11

　　3.有確認有連接服務( Acknowledged -oriented)

　　適用場景:長延遲的不可靠信道

　　3.成幀(Framing)

　　3.1要解決的關鍵問題:如何標識一個幀的開始?

　　接收方必須能從物理層接收的比特流中明確區分出一幀的開始和結束，這個問題被稱為幀同步或幀定界

　　關鍵:選擇何種定界符?定界符出現在數據部分如何處理?

　　3.2成幀(framing)的方式

　　①帶比特填充的定界符法

　　定界符:兩個0比特之間，連續6個1比特，即01111110，0x7E

　　發送方檢查有效載荷:若在有效載荷中出現連續5個1比特，則直接插入1個0比特

　　接收方的處理:

　　若出現連續5個1比特，

　　若下一比特為0，則為有效載荷，

直接丟棄0比特;　　若下一比特為1，則連同後一比特的0，構成定界符，一幀結束

　　②物理層編碼違例

　　核心思想:選擇的定界符不會在數據部分出現

　　4B/5B編碼方案

　　4比特數據映射成5比特編碼，剩余的一半碼字(16個碼字)未使用，可以用做幀定界符

　　例如: 00110組合不包含在4B/5B編碼中，可做幀定界符

　　前導碼

　　存在很長的前導碼(preamble)，可以用作定界符

　　例如:傳統以太網、802.11

　　曼切斯特編碼/差分曼切斯特編碼

　　正常的信號在周期中間有跳變，持續的高電平(或低電平)為違例碼，可以用作定界符

　　例如:802.5令牌環網

　　4.差錯控制

　　4.1背景

　　鏈路層存在的一個問題:信道的噪聲導致數據傳輸問題

　　差錯( ):數據發生錯誤

　　丟失( lost):接收方未收到

　　亂序(out of order):先發後到，後發先到

　　重複(repeatedly delivery):一次發送，多次接收

　　解決方案:差錯檢測與糾正、確認重傳

　　確認:接收方校驗數據(差錯校驗)，並給發送方應答，防止差錯

　　定時器:發送方啟動定時器，防止丟失

　　順序號:接收方檢查序號，防止亂序遞交、重複遞交

　　4.2差錯檢驗與糾正

　　目標

　　保證一定差錯檢測和糾錯能力的前提下，如何減少冗余信息量?

　　考慮的問題

　　信道的特征和傳輸需求

　　冗余信息的計算方法、攜帶的冗余信息量

　　計算的複雜度等

　　兩種主要策略

　　檢錯碼(error-detecting code)

　　在被發送的數據塊中，包含一些冗余信息，但這些信息只能使接收方推斷是否發生錯誤但不能推斷哪位發生錯誤，接收方可以請求發送方重傳數據主要用在高可靠、誤碼率較低的信道上，例如光纖鏈路偶爾發生的差錯，可以通過重傳解決差錯問題

　　糾錯碼(error-correcting code)

　　發送方在每個數據塊中加入足夠的冗余信息，使得接收方能夠判斷接收到的數據是否有錯，並能糾正錯誤(定位出錯的位置)主要用於錯誤發生比較頻繁的信道上，如無線鏈路也經常用於物理層，以及更高層(例如，實時流媒體應用和內容分發)使用糾錯碼的技術通常稱為前向糾錯(FEC，Forward Error )

　　常用的檢錯碼包括:

　　①奇偶檢驗(Parity Check)

　　1位奇偶校驗是最簡單、最基礎的檢錯碼。

　　1位奇偶校驗:增加1位校驗位，可以檢查奇數位錯誤。

　　②校驗和(Checksum)

　　主要用於TCP/IP體系中的網絡層和傳輸層

　　③循環冗余校驗(Cyclic Redundancy Check，CRC)

　　數據鏈路層廣泛使用的校驗方法

　　CRC校驗碼計算方法

　　設原始數據D為k位二進製位模式

　　如果要產生n位CRC校驗碼，事先選定一個n+1位二進製位模式G (稱為生成多項式，收發雙方提前商定)，G的最高位為1

　　將原始數據D乘以2^n(相當於在D後面添加 n個 0)，產生k+n位二進製位模式，用G對該位模式做模2除，得到余數R(n位，不足n位前面用0補齊)即為CRC校驗碼

　　CRC校驗碼計算示例

　　D = 1010001101

　　n = 5

　　G = 110101或 G = x5 + x4 + x2 + 1

　　R = 01110

　　實際傳輸數據:101000110101110

　　④漢明碼

　　目標:以奇偶校驗為基礎，找到出錯位置，提供1位糾錯能力

　　給定n位待發送的數據，首先確定校驗位的個數k(根據2^k≥k+n+1)

　　確定校驗位在碼流中的位置，2^i，i=0，1，2，……，得到校驗位P_1，P_2，P_4，P_8，……

　　確定分組，即每個校驗位分別負責哪些數據位

　　P_1負責位置號的二進製符合XXXX1形式的數據位，即1，3，5，7，9，……

　　P_2負責位置號的二進製符合XXX1X形式的數據位，即2，3，6，7，10，……

　　P_3負責位置號的二進製符合XX1XX形式的數據位，即4，5，6，7，12，13，14，15，……

　　基於偶校驗確定每組的校驗位(0或1)

　　注:漢明碼是采用奇偶校驗的碼。它采用了一種非常巧妙的方式，把這串數字分了組，通過分組校驗來確定哪一位出現了錯誤。

　　實際的海明碼編碼的過程也並不複雜，我們通過用不同過的校驗位，去匹配多個不同的數據組，確保任何一個數據位出錯，都會產生一個多個校驗碼位出錯的唯一組合。這樣，在出錯的時候，我們就可以反過來找到出錯的數據位，並糾正過來。當只有一個校驗碼位出錯的時候，我們就知道實際出錯的是校驗碼位了。

　　5.流量控制

　　鏈路層存在的另一個問題:接收方的處理速率

　　接收方的接收緩衝區溢出

　　解決方案

　　基於反饋(feedback-based)的流量控制

　　接收方反饋，發送方調整發送速率

　　基於速率(rate-based)的流量控制

　　發送方根據內建機制，自行限速

　　6.媒體接入控制 MAC (Medium Control)子層

　　數據鏈路層分為兩個子層:

　　MAC子層:介質訪問

　　LLC子層:承上啟下(弱層)

　　6.1信道分配問題

　　①時分多址接入-TDMA

　　TDMA: time multiple

　　按順序依次接入並使用信道

　　每個用戶使用固定且相同長度的時隙

　　某時隙輪到某用戶使用時，該用戶沒有數據要發送，則該時隙被閑置

　　例子: 6-user LAN， 1，3，4時隙有數據發送， 2，5，6時隙被閑置

　　②頻分多址接入-FDMA

　　FDMA: frequency multiple

　　信道總頻帶被劃分為多個相同寬度的子頻帶

　　每個用戶佔用一個子頻帶，不管用戶是否有數據發送

　　例子: 6-user LAN， 1，3，4頻帶有數據發送， 2，5，6頻帶被閑置

　　6.2多路訪問協議

　　6.2.1隨機訪問協議

　　特點:衝突不可避免

　　①ALOHA

　　純ALOHA協議

　　原理:想發就發！

　　特點:

　　衝突:兩個或以上的幀

　　隨時可能衝突

　　衝突的幀完全破壞

　　破壞了的幀要重傳

　　分隙ALOHA

　　分隙ALOHA是把時間分成時隙(時槽)

　　時隙的長度對應一幀的傳輸時間。

　　幀的發送必須在時隙的起點。

　　衝突隻發生在時隙的起點

　　②載波偵聽多路訪問協議CSMA

　　特點:“先聽後發”

　　改進ALOHA的偵聽/發送策略分類

　　非持續式CSMA

　　1.特點

　　①經偵聽，如果介質空閑，開始發送

　　②如果介質忙，則等待一個隨機分布的時間，然後重複步驟①

　　2.好處

　　等待一個隨機時間可以減少再次碰撞衝突的可能性

　　3.缺點

　　等待時間內介質上如果沒有數據傳送，這段時間是浪費的

　　持續式CSMA

　　p-持續式CSMA

　　1.特點

　　①經偵聽，如介質空閑，那麽以 p的概率發送，以(1–p)的概率延遲一個時間單元發送

　　②如介質忙，持續偵聽，一旦空閑重複①

　　③如果發送已推遲一個時間單元，再重複步驟①

　　1-持續式CSMA

　　1.特點

　　①經偵聽，如介質空閑，則發送

　　②如介質忙，持續偵聽，一旦空閑立即發送

　　③如果發生衝突，等待一個隨機分布的時間再重複步驟①

　　2.好處:持續式的延遲時間要少於非持續式

　　3.主要問題:如果兩個以上的站等待發送，一旦介質空閑就一定會發生衝突

　　4.注意

　　1-持續式是p-持續式的特例

　　6.2.2受控訪問協議

　　特點:克服了衝突

　　①位圖協議(預留協議)

　　競爭期:在自己的時槽內發送競爭比特

　　舉手示意

　　資源預留

　　傳輸期:按序發送

　　明確的使用權，避免了衝突

　　②令牌傳遞

　　令牌:發送權限

　　令牌的運行:發送工作站去抓取，獲得發送權

　　除了環，令牌也可以運行在其它拓撲上，如令牌總線

　　發送的幀需要目的站或發送站將其從共享信道上去除;防止無限循環

　　缺點:令牌的維護代價

　　③二進製倒計數協議

　　站點:編序號，序號長度相同

　　競爭期:有數據發送的站點從高序號到低序號排隊，高者得到發送權

　　特點:高序號站點優先

　　6.2.3有限競爭協議

　　利用上述二者的優勢

　　①自適應樹搜索協議(Adaptive Tree Walk )

　　在一次成功傳輸後的第一個競爭時隙，所有站點同時競爭。

　　如果只有一個站點申請，則獲得信道。

　　否則在下一競爭時隙，有一半站點參與競爭(遞歸)，下一時隙由另一半站點參與競爭

　　即所有站點構成一棵完全二叉樹。

　　6.3虛擬局域網

　　廣播域(Broadcasting Domain)

　　廣播域是廣播幀能夠到達的范圍;

　　缺省情況下，交換機所有端口同屬於一個廣播域，無法隔離廣播域;

　　廣播幀在廣播域中傳播，佔用資源，降低性能，且具有安全隱患。

　　是一個在物理網絡上根據用途，工作組、應用等來邏輯劃分的局域網絡，與用戶的物理位置沒有關系。

　　通過路由器或三層交換機進行間路由，實現間通信。

　　類型

　　基於端口的

　　基於MAC地址的

　　基於協議的

　　基於子網的

　　6.4無線局域網

　　無線局域網(Wireless Local Area ，):指以無線信道作為傳輸介質的計算機局域網

　　基礎架構模式(Infrastructure)

　　分布式系統(DS)

　　訪問點(AP)

　　站點(STA)

　　基本服務集(BSS)

　　擴展服務集(ESS)

　　站點之間通信通過AP轉發

　　自組織模式(Ad hoc)

　　站點(STA)

　　獨立基本服務集(IBSS)

　　站點之間直接通信

　　共享同一無線信道

　　無線局域網需要解決的問題

　　1.有限的無線頻譜帶寬資源

　　通道劃分、空間重用

　　提高傳輸速率，解決傳輸問題

　　提高抗干擾能力和保密性

　　2.共享的無線信道

　　介質訪問控制方法(CSMA/CA)

　　可靠性傳輸、安全性

　　3.組網模式管理

　　BSS構建、認證、關聯

　　移動性支持(漫遊)

　　睡眠管理(節能模式)

　　四、網絡層

　　1.網絡層概述

　　網絡層在數據鏈路層提供的兩個相鄰端點之間的數據幀的傳送功能上，進一步管理網絡中的數據通信，將數據設法從源端經過若乾個中間節點傳送到目的端，從而向運輸層提供最基本的端到端的數據傳送服務。

　　2.網絡層關鍵功能

　　路由(控制面)

　　選擇數據報從源端到目的端的路徑

　　核心:路由算法與協議

　　轉發(數據面)

　　將數據報從路由器的輸入接口傳送到正確的輸出接口

　　網際協議

　　3.1 IPv4協議及其相關技術

　　3.1.1基本概念

　　IPv4協議，網際協議版本4，一種無連接的協議，是互聯網的核心，也是使用最廣泛的網際協議版本，其後繼版本為IPv6

　　協議執行兩個基本功能

　　尋址(addressing)

　　分片()

　　3.1.2 IPv4數據報格式

　　版本: 4bit，表示采用的IP協議版本

　　首部長度: 4bit，表示整個IP數據報首部的長度

　　區分服務: 8bit，該字段一般情況下不使用

　　總長度: 16bit，表示整個IP報文的長度，能表示的最大字節為2^16-1=65535字節

　　標識: 16bit， IP軟件通過計數器自動產生，每產生1個數據報計數器加1;在ip分片以後，用來標識同一片分片

　　標志: 3bit，目前只有兩位有意義。

　　MF，置1表示後面還有分片，置0表示這是數據報片的最後1個;

　　DF，不能分片標志，置0時表示允許分片

　　片偏移: 13bit，表示IP分片後，相應的IP片在總的IP片的相對位置

　　生存時間TTL(Time To Live):8bit，表示數據報在網絡中的生命周期，用通過路由器的數量來計量，即跳數(每經過一個路由器會減1)

　　協議:8bit，標識上層協議(TCP/UDP/ICMP…)

　　首部校驗和:16bit，對數據報首部進行校驗，不包括數據部分

　　源地址:32bit，標識IP片的發送源IP地址

　　目的地址:32bit，標識IP片的目的地IP地址

　　選項:可擴充部分，具有可變長度，定義了安全性、嚴格源路由、松散源路由、記錄路由、時間戳等選項

　　填充:用全0的填充字段補齊為4字節的整數倍

　　3.1.3數據報分片

　　分片原因

　　數據報長度大於傳輸鏈路的MTU

　　MTU(Maximum Unit)，最大傳輸單元

　　鏈路MTU

　　路徑MTU (Path MTU)

　　分片策略

　　允許途中分片:根據下一跳鏈路的MTU實施分片

　　不允許途中分片:發出的數據報長度小於路徑MTU(路徑MTU發現機制)

　　重組策略

　　途中重組，實施難度太大

　　目的端重組(互聯網采用的策略)

　　重組所需信息:原始數據報編號、分片偏移量、是否收集所有分片

　　IPv4分片策略

　　IPv4分組在傳輸途中可以多次分片

　　源端系統，中間路由器(可通過標志位設定是否允許路由器分片，DF標志位)

　　IPv4分片只在目的IP對應的目的端系統進行重組

　　IPv4分片、重組字段在基本IP頭部

　　標識、標志、片偏移

　　IPv6分片機制有較大變化(見IPv6部分的介紹)

　　注:分組(packet)與幀(frame)的關系

　　3.1.4 IP協議功能及報頭字段總結

　　網絡層基本功能

　　支持多跳尋路將IP數據報送達目的端:目的IP地址

　　表明發送端身份:源IP地址

　　根據IP頭部協議類型，提交給不同上層協議處理:協議

　　其它相關問題

　　數據報長度大於傳輸鏈路的MTU的問題，通過分片機制解決:標識、標志、片偏移

　　防止循環轉發浪費網絡資源(路由錯誤、設備故障…)，通過跳數限制解決:生存時間TTL

　　IP報頭錯誤導致無效傳輸，通過頭部機校驗解決:首部校驗和

　　3.2 IP地址

　　3.2.1概述

　　IP地址，網絡上的每一台主機(或路由器)的每一個接口都會分配一個全球唯一的32位的標識符

　　將IP地址劃分為固定的類，每一類都由兩個字段組成

　　網絡號相同的這塊連續IP地址空間稱為地址的前綴，或網絡前綴

　　IP地址共分為A、B、C、D、E五類，A類、B類、C類為單播地址

　　IP地址的書寫采用點分十進製記法，其中每一段取值范圍為0到255

　　IP特殊地址

　　3.2.1子網劃分

　　子網劃分()，在網絡內部將一個網絡塊進行劃分以供多個內部網絡使用，對外仍是一個網絡

　　子網( )，一個網絡進行子網劃分後得到的一系列結果網絡稱為子網

　　子網掩碼( mask )，與 IP地址一一對應，是32 bit的二進製數，置1表示網絡位，置0表示主機位

　　子網劃分減少了 IP地址的浪費、網絡的組織更加靈活、便於維護和管理

　　3.2.3無類域間路由

　　將32位的IP地址劃分為前後兩個部分，並采用斜線記法，即在IP地址後加上“/”，然後再寫上網絡前綴所佔位數

　　一個 CIDR地址塊可以表示很多地址，這種地址的聚合常稱為路由聚合(route )，也稱為構成超網()

　　聚合技術在中大量使用，它允許前綴重疊，數據包按具體路由的方向發送，即具有最少IP地址的最長匹配前綴

　　注:當路由器收到一個IP數據包時，它會將數據包的目的IP地址與自己本地路由表中的所有路由表進行逐位(Bit-By-Bit)對比，直到找到匹配度最長的條目，這就是最長前綴匹配機制。(路由比對之前會用相應路由的目的網絡掩碼進行邏輯與運算，再拿結果與路由路徑比對)

　　3.3 DHCP動態主機配置協議

　　DHCP:動態主機配置協議

　　當主機加入IP網絡，允許主機從DHCP服務器動態獲取IP地址

　　可以有效利用IP地址，方便移動主機的地址獲取

　　工作模式:客戶/服務器模式( C/S)

　　基於 UDP工作，服務器運行在 67號端口，客戶端運行在 68號端口

　　DHCP客戶從UDP端口68以廣播形式向服務器發送發現報文()

　　DHCP服務器廣播發出提供報文(DHCPOFFER)

　　DHCP客戶從多個DHCP服務器中選擇一個，並向其以廣播形式發送DHCP請求報文(DHCPREQUEST)

　　被選擇的DHCP服務器廣播發送確認報文(DHCPACK)

　　3.4 ARP地址解析協議

　　背景

　　網絡設備有數據要發送給另一台網絡設備時，必須要知道對方的網絡層地址(即IP地址)。IP地址由網絡層來提供，但是僅有IP地址是不夠的，IP數據報文必須封裝成幀才能通過數據鏈路進行發送。數據幀必須要包含目的MAC地址，因此發送端還必須獲取到目的MAC地址。通過目的IP地址二獲取的MAC地址的過程是由ARP(Address )協議來實現的。

　　注:因為下層協議是通過MAC地址來確定各自身份的，所以下層發送必須要MAC地址

　　IP與 MAC地址

　　ARP協議工作過程

　　A已知B的IP地址，需要獲得B的MAC地址(物理地址)

　　如果A的ARP表中緩存有B的IP地址與MAC地址的映射關系，則直接從ARP表獲取

　　如果A的ARP表中未緩存有B的IP地址與MAC地址的映射關系，則A廣播包含B的IP地址的ARP query分組

　　在局域網上的所有節點都可以接收到ARP query

　　B接收到ARP query分組後，將自己的MAC地址發送給A

　　A在ARP表中緩存B的IP地址和MAC地址的映射關系

　　超時時刪除

　　路由到另一個局域網

　　A創建IP數據包(源為A、目的為E)

　　在源主機A的路由表中找到路由器R的IP地址223.1.1.4

　　A根據R的IP地址223.1.1.4，使用ARP協議獲得R的MAC地址

　　A創建數據幀(目的地址為R的MAC地址)

　　數據幀中封裝A到E的IP數據包

　　A發送數據幀，R接收數據幀

　　3.5網絡地址轉換(NAT)

　　定義

　　網絡地址轉換(NAT)用於解決IPv4地址不足的問題，是一種將私有(保留)地址轉化為公有IP地址的轉換技術

　　私有IP地址:

　　A類地址:10.0.0.0–10.255.255.255

　　B類地址:172.16.0.0–172.31.255.555

　　C類地址:192.168.0.0–192.168.255.255

　　NAT工作機制

　　出數據報:外出數據報用 NAT IP地址(全局)，新port #替代源IP地址(私有)， port #

　　NAT轉換表:每個(源IP地址， port #)到(NAT IP地址，新port #)映射項

　　入數據報:對每個入數據報的地址字段用存儲在NAT表中的(源IP地址， port #)替代對應的(NAT IP地址，新port #)

　　NAT根據不同的IP上層協議進行NAT表項管理

　　TCP，UDP，ICMP

　　傳輸層TCP/UDP擁有16-bit端口號字段

　　所以一個WAN側地址可支持60，000個並行連接

　　NAT的優勢

　　節省合法地址，減少地址衝突

　　靈活連接

　　保護局域網的私密性

　　3.6 ICMP:互聯網控制報文協議

　　ICMP:互聯網控制報文協議

　　ICMP允許主機或路由器報告差錯情況和提供有關異常情況的報告

　　由主機和路由器用於網絡層信息的通信

　　ICMP報文攜帶在IP數據報中: IP上層協議號為1

　　ICMP報文類型

　　ICMP差錯報告報文

　　終點不可達:不可達主機、不可達網絡，無效端口、協議

　　ICMP詢問報文

　　回送請求/回答(ping使用)

　　ICMP報文格式

　　ICMP報文的前 4個字節包含格式統一的三個字段:類型、代碼、檢驗和

　　相鄰的後四個字節內容與ICMP的報文類型有關

　　ICMP報文類型及功能

　　4.路由算法

　　路由算法須滿足的特性:

　　正確性

　　簡單性

　　魯棒性

　　穩定性

　　公平性

　　有效性

　　根據路由算法是否隨網絡的通信量或拓撲自適應劃分

　　靜態路由選擇策略(非自適應路由選擇)

　　動態路由選擇策略(自適應路由選擇)

　　4.1距離向量路由

　　算法基本思想

　　每個節點周期性地向鄰居發送它自己到某些節點的距離向量;

　　當節點x接收到來自鄰居的新DV估計，它使用B-F方程更新其自己的DV :

　　Dx(y)← minv{c(x，v)+ Dv(y)} for each node y? N

　　上述過程迭代執行，Dx(y)收斂為實際最小費用 dx(y)

　　距離向量算法特點:迭代的、分布式的

　　每次本地迭代由下列引起:本地鏈路費用改變、鄰居更新報文

　　分布式:各節點依次計算，相互依賴

　　注:路由器隻掌握物理相連的鄰居以及鏈路費用

　　算法過程

　　路由器啟動時初始化自己的路由表

　　初始路由表包含所有直接相連的網絡路徑，距離均為0

　　路由器周期性地向其相鄰路由器廣播自己知道的路由信息

　　相鄰路由器可以根據收到的路由信息修改和刷新自己的路由表

　　路由器經過若乾次更新後，最終都會知道到達所有網絡的最短距離

　　所有的路由器都得到正確的路由選擇信息時網絡進入“收斂”(convergence)狀態

　　特殊情況考慮

　　計數到無窮問題(The Count-to-Infinity Problem)

　　好消息傳播快，壞消息傳播慢，是距離向量路由的一個主要缺點

　　4.2鏈路狀態路由

　　注:所有路由器掌握完整的網絡拓撲和鏈路費用信息

　　算法過程

　　鏈路狀態(Link State)路由可分為五個部分:

　　發現鄰居，了解他們的網絡地址;

　　設置到每個鄰居的成本度量;

　　開銷/度量/代價:

　　自動發現設置或人工配置

　　度量:帶寬、跳數、延遲、負載、可靠性等

　　常用度量:鏈路帶寬(反比)

　　例如:1-Gbps以太網的代價為1，100-Mbps以太網的代價為10

　　可選度量:延遲

　　發送一個echo包，另一端立即回送一個應答

　　通過測量往返時間RTT，可以獲得一個合理的延遲估計值

　　構造一個分組，分組中包含剛收到的所有信息;

　　構造鏈路狀態分組(link state packet，LSP)

　　發送方標識

　　序列號

　　年齡

　　鄰居列表

　　將此分組發送給其他的路由器;

　　每個LSP分組包含一個序列號，且遞增

　　路由器記錄所收到的所有(源路由器、序列號)對

　　當一個新分組到達時，路由器根據記錄判斷:

　　如果是新分組，洪泛廣播

　　如果是重複分組，丟棄

　　如果是過時分組，拒絕

　　計算到其他路由器的最短路徑。

　　Dijkstra算法示例

　　D(k):從計算節點到目的節點k當前路徑代價

　　p(k):從計算節點到目的節點k的路徑中k節點的前繼節點

　　距離向量和鏈路狀態算法比較

　　網絡狀態信息交換的范圍

　　DV:鄰居間交換

　　LS:全網擴散

　　網絡狀態信息的可靠性

　　DV:部分道聽途說

　　LS:自己測量

　　4.3層次路由

　　產生原因

　　過於龐大的路由表存儲、查找困難，路由信息交互開銷高

　　現實情況:

　　地址分配往往是隨機的，難以進行高效的地址聚合

　　每個網絡的網絡管理員有自己的管理方法和思路，並不希望每個路由器都干涉本網絡內部的地址分配等問題

　　層次路由可以解決:

　　網絡擴展性問題:當網絡擴大時，控制路由表條目和路由表存儲空間的增長

　　管理的自治問題:網絡管理員可以控制和管理自己網絡的路由

　　基本思路

　　互聯網由大量不同的網絡互連，每個管理機構控制的網絡是自治的

　　自治系統(AS，Autonomous System)

　　一個管理機構控制之下的網絡

　　一個AS內部通常使用相同的路由算法/路由協議，使用統一的路由度量(跳數、帶寬、時延…)

　　不同的AS可以使用不同的路由算法/路由協議

　　每個AS有一個全球唯一的ID號:AS ID

　　自治系統內的還可以進一步劃分層次:私有自治系統或區域

　　效果

　　4.4廣播路由

　　廣播(Broadcasting):源主機同時給全部目標地址發送同一個數據包

　　實現方法

　　①給每個主機單獨發送一個數據包

　　效率低、浪費帶寬

　　Server需要知道每個目的地址

　　②多目標路由(multi- routing)

　　在需要轉發的路由器線路複製一次該數據報

　　網絡利用率高

　　Server依然需要知道所有的目的地址

　　注:以上方法難以實現

　　③泛洪(flooding)

　　一種將數據包發送到所有網絡節點的簡單方法

　　將每個進入數據包發送到除了進入線路外的每條出去線路

　　用途

　　保證性:一種有效廣播手段，可確保數據包被傳送到網絡中每個節點

　　魯棒性:即使大量路由器被損壞，也能找到一條路徑(如果存在)

　　簡單性:僅需知道自己的鄰居

　　無控制的泛洪

　　實現廣播最顯而易見的技術

　　環路可能導致廣播風暴

　　路由器可能收到多個副本

　　節點需要跟蹤已泛洪的數據包以阻止洪泛

　　即使利用跳數來限制，也會出現成倍爆炸

　　解決方法:受控制的泛洪(每個路由器進行有選擇的泛洪)

　　序號控制泛洪

　　逆向路徑轉發

　　④生成樹(spanning tree)

　　源節點向所有屬於該生成樹的特定鏈路發送分組

　　改進了逆向路徑轉發

　　沒有環路

　　最佳使用帶寬

　　最少副本，消除了冗余分組

　　一個路由器可以不必知道整顆樹，只需要知道在一顆樹中的鄰居即可

　　路由協議

　　5.1路由選擇協議RIP

　　概述

　　路由選擇協議RIP( Routing )是基於距離矢量算法的協議

　　使用跳數衡量到達目的網絡的距離

　　RIP認為一個好的路由就是它通過的路由器的數目少，即“距離短”

　　RIP允許一條路徑最多只能包含 15個路由器

　　RIP協議的基本思想

　　僅和相鄰路由器交換信息

　　路由器交換的內容是自己的路由表

　　周期性更新:30s

　　工作過程

　　初始化

　　周期性更新

　　小結

　　RIP協議的特點

　　算法簡單，易於實現

　　收斂慢

　　需要交換的信息量較大

　　RIP協議的適用場合

　　中小型網絡

　　RIP協議的防環路機制

　　觸發更新

　　毒性反轉

　　水平分割

　　其他

　　5.2 BGP-外部網關路由協議

　　路由協議

　　內部網關協議 IGP:有 RIP和、OSPF、ISIS等多種具體的協議

　　外部網關協議 EGP:目前使用的協議就是 BGP

　　邊界網關協議BGP (Border Gateway )

　　目前互聯網中唯一實際運行的自治域間的路由協議

　　BGP功能

　　eBGP:從相鄰的AS獲得網絡可達信息

　　iBGP:將網絡可達信息傳播給AS內的路由器

　　基於網絡可達信息和策略決定到其他網絡的“最優”路由

　　BGP會話:兩個BGP路由器通過TCP連接交換BGP報文

　　通告到不同網絡前綴的路徑，即路徑向量協議

　　BGP路徑通告

　　AS2的路由器2c從AS3的路由器3a接收到路徑AS3， X

　　根據AS2的策略，AS2的路由器2c接受路徑AS3， X，通過iBGP傳播給AS2的所有路由器

　　根據AS2策略，AS2的路由器2a通過eBGP向AS1的路由器1c通告從AS3的路由器3a接收到路徑AS2， AS3， X

　　路由器可能會學到多條到達目的網絡的路徑:

　　AS1的路由器1c從2a學到路徑AS2， AS3， X

　　AS1的路由器1c從3a學到路徑AS3， X

　　由策略，AS1路由器1c可能選擇路徑AS3， X，並在AS1中通過iBGP通告路徑

　　6.路由器的工作原理

　　6.1路由器概述

　　路由器是互聯網最主要的網絡設備，包含2個核心功能

　　控制層:運行各種路由協議:BGP、OSPF、RIP，學習去往不同目的的轉發路徑:路由表

　　數據層:根據上述路由表，將收到的IP分組轉發到正確的下一跳鏈路

　　6.2路由器控制層

　　路由器可同時運行多個路由協議

　　路由器也可不運行任何路由協議，隻使用靜態路由和直連路由

　　路由管理根據路由優先級，選擇最佳路由，形成核心路由表

　　控制層將核心路由表下發到數據層， 形成轉發表(FIB)

　　若存在多個“去往同一目的IP前綴”的不同類型路由，路由器根據優先級選擇最佳路由

　　優先級數值越小，優先級越高

　　6.3路由器數據層

　　路由器中IP報文轉發核心功能

　　鏈路層解封裝，IP頭部校驗

　　獲取報文目的IP地址

　　用目的IP地址，基於最長前綴匹配規則查詢轉發表

　　查詢失敗，丟棄報文

　　查詢成功

　　獲取轉發出接口和下一跳IP地址

　　IP頭部“TTL”字段值減1，重新計算IP頭部“校驗和”

　　重新進行鏈路層封裝，發送報文

　　注:普通IP報文轉發過程中，路由器不查看傳輸層及以上層協議的內容

　　IP報文在路由器轉發前後的變化

　　鏈路層封裝更新，IP頭部“TTL”減1，IP頭部“校驗和”更新

　　數據報在不同硬件單元的處理

　　報文輸入的接口卡

　　鏈路層解封裝

　　轉發表查詢(該工作在輸入接口卡處理)

　　通過交換結構將報文排隊發往目的接口卡(發送過快將產生擁塞)

　　交換結構

　　從輸入接口卡發往輸出接口卡

　　報文輸出的接口卡

　　從交換結構接收報文(排隊進行後續處理，到達太快將產生擁塞)

　　鏈路層封裝

　　從輸出接口發送報文

　　這個大概就是今天複習的，還是蠻多的，希望今天複習的，到明天都可以用的到。