㈠ 《計算機網路-自頂向下方法》第四章-網路層 要點
網路層的作用：實現主機到主機的通信服務，將分組從一台發送主機移動到一台接收主機。
1、轉發涉及分組在單一的路由器中從一條入鏈路到一條出鏈路的傳送。
2、路由選擇涉及一個網路的所有路由器，它們經路由選擇協議共同交互，以決定分組從源到目的地結點所採用的路徑。計算這些路徑的演算法稱為路由選擇演算法。
每台路由器都有一張轉發表，路由器通過檢查到達分組首部欄位的值來轉發分組，然後使用該值在該路由器的轉發表中索引查找。路由選擇演算法決定了插入路由器轉發表中的值。
路由選擇演算法可能是集中式的，或者是分布式的。但在這兩種情況下，都是路由器接收路由選擇協議報文，該信息被用於配置其轉發表。
網路層也能在兩台主機之間提供無連接服務或連接服務。同在運輸層的面向連接服務和無連接服務類似，連接服務需要握手步驟，無連接服務不需要握手。但它們之間也有差異：
1、 在網路層中，這些服務是由網路層向運輸層提供的主機到主機的服務。在運輸層中，這些服務則是運輸層向應用層提供的進程到進程的服務。
2、 在網路層提供無連接服務的計算機網路稱為數據報網路；在網路層提供連接服務的計算機網路稱為虛電路網路。
3、 在運輸層實現面向連接的服務與在網路層實現連接服務是根本不同的。運輸層面向連接服務是在位於網路邊緣的端系統中實現的；網路層連接服務除了在端系統中，也在位於網路核心的路由器中實現。（原因很簡單：端系統和路由器都有網路層）
虛電路網路和數據報網路是計算機網路的兩種基本類型。在作出轉發決定時，它們使用了非常不同的信息。
IP地址有32比特，如果路由器轉發表採用「蠻力實現」將對每個可能的目的地址有一個表項。因為有超過40億個可能的地址，這種選擇完全不可能（即使用二分查找也十分慢）。
我們轉發表的表項可以設計為幾個表項，每個表項匹配一定范圍的目的地址，比如有四個表項
（你可能也會考慮到，IP地址有32比特，如果每個路由器設計為只有2個表項，那麼也只需要有32個路由器就可以唯一確定這40億個地址中的一個。）
最長前綴匹配規則，是在轉發表中尋找最長的匹配項，並向與最長前綴匹配相關聯的鏈路介面轉發分組。這種規則是為了與網際網路的編址規則相適應。
1、輸入埠
「使用轉發表查找輸出埠」是輸入埠最重要的操作（當然還有其他一些操作）。輸入埠執行完這些所需的操作後，就把該分組發送進入交換結構。如果來自其他輸入埠的分組當前正在使用交換結構，一個分組可能會在進入交換結構時被暫時阻塞，在輸入埠處排隊，並等待稍後被及時調度以通過交換結構。
2、交換結構
交換結構的三種實現方式
3、輸出埠
分組調度程序 處理在輸出埠中排隊的分組
4、路由選擇處理器
</br>
</br>
IP協議版本4，簡稱為IPv4；IP協議版本6，簡稱為IPv6。
如上圖所示，網路層有三個主要的組件
1、IP協議
2、路由選擇協議
3、ICMP協議 (Internet Control Message Protocol, 網際網路控制報文協議)
</br>
不是所有鏈路層協議都能承載相同長度的網路層分組。有的協議能承載大數據報，而有的協議只能承載小分組。例如，乙太網幀能夠承載不超過1500位元組的數據，而某些廣域網鏈路的幀可承載不超過576位元組的數據。
一個鏈路層幀能承載的最大數據量叫做最大傳送單元(Maximun Transmission Unit, MTU)
所以鏈路層協議的MTU嚴格限制著IP數據報的長度。這也還不是主要的問題，問題在於發送方與目的地路徑上的每段鏈路可能使用不同的鏈路層協議，且每種協議可能具有不同的MTU。
舉個例子：假定從某條鏈路收到一個IP數據報，通過檢查轉發表確定出鏈路，並且該出鏈路的MTU比該IP數據報的長度要小。那麼如何將這個過大的IP分組壓縮進鏈路層幀的有效載荷欄位呢？
解決辦法是，將IP數據報中的數據分片成兩個或更多個較小的IP數據報，用單獨的鏈路層幀封裝這些較小的IP數據報；然後向輸出鏈路上發送這些幀。每個這些較小的數據報都被稱為片(fragment)。
路由器完成分片任務。同時，為了使得網路內核保持簡單，IPv4設計者把數據報的重組工作放到端系統中，而非放到網路路由器中。
前提：一個4000位元組的數據報(20位元組IP首部加上3980位元組IP有效載荷)到達一台路由器，且必須被轉發到一條MTU為1500位元組的鏈路上。假定初始數據報貼上的標識號為777。
這意味著初始數據報中3980位元組數據必須被分配到3個獨立的片(其中的每個片也是一個IP數據報)
IP分片：
IP地址有32比特，分為網路號和主機號。
IP地址的網路部分（即網路號）被限制為長度為8、16或24比特，這是一種稱為分類編址的編址方案。具有8、16和24比特子網地址的子網分別被稱為A、B和C類網路。
但是它在支持數量迅速增加的具有小規模或中等規模子網的組織方面出現了問題。一個C類(/24)子網僅能容納多大2^8 - 2 = 254台主機(2^8 = 256, 其中的兩個地址預留用於特殊用途)，這對許多組織來說太小了。然而一個B類(/16)子網可支持多達65534台主機，又太大了。這導致B類地址空間的迅速損耗以及所分配的地址空間的利用率低。
廣播地址255.255.255.255。當一台主機發出一個目的地址為255.255.255.255的數據報時，該報文會交付給同一個網路中的所有主機。
某組織一旦獲得了一塊地址，它就可以為本組織內的主機與路由器介面逐個分配IP地址。既可手工配置IP地址，也可以使用動態主機配置協議(Dynamic Host Configuration Protocol, DHCP)自動配置。DHCP還允許一台主機得知其他信息，如它的子網掩碼、它的第一跳路由器地址(常稱為默認網關)與它的本地DNS伺服器的地址。
由於DHCP具有能將主機連接進一個網路相關方面的自動能力，它又被稱為即插即用協議。
DHCP是客戶-伺服器協議。客戶通常是新達到的主機，它要活的包括自身使用的IP地址在內的網路配置信息。在最簡單的場合下，每個子網將具有一台DHCP伺服器。如果在某子網中沒有伺服器，則需要一個DHCP中繼代理(通常是一台路由器)，這個代理知道用於該網路的DHCP伺服器的地址。
DHCP協議工作的4個步驟：
網路地址轉換(Network Address Translation, NAT)
ICMP通常被認為是IP的一部分，但從體系結構上將它是位於IP之上的，因為ICMP報文是承載在IP分組中的。即ICMP報文是作為IP有效載荷承載的，就像TCP與UDP報文段作為IP有效載荷被承載那樣。
眾所周知的ping程序發送一個ICMP類型8編碼0的報文到指定主機。看到該回顯請求，目的主機發回一個類型0編碼0的ICMP回顯回答。大多數TCP/IP實現直接在操作系統中支持ping伺服器，即該伺服器不是一個進程。
新型IPv6系統可做成向後兼容，即能發送、路由和接收IPv4數據報，要使得已部署的IPv4系統能夠處理IPv6數據報，最直接的方式是採用一種雙棧方法。
1、鏈路狀態(Link State, LS)演算法：屬於全局式路由選擇演算法，這種演算法必須知道網路中每條鏈路的費用。費用可理解為鏈路的物理長度、鏈路速度，或與該鏈路相關的金融上的費用。鏈路狀態演算法採用的是Dijkstra演算法。
2、距離向量(Distance-Vector, DV)演算法：屬於迭代的、非同步的和分布式的路由選擇演算法。
「迭代的」，是因為此過程一直要持續到鄰居之間無更多信息要交換為止。
「非同步的」，是因為它不要求所有結點相互之間步伐一致地操作。
「分布式的」，是因為每個結點都要從一個或多個直接相連鄰居接收某些信息，執行計算，然後將其計算結果分發給鄰居。
DV演算法的方程：
其中，dx(y)表示從結點x到結點y的最低費用路徑的費用，c(x, v)是結點x到結點v的費用，結點v指的是所有x的相連結點，所以x的所有相連結點都會用minv方程計算。
（N是結點（路由器）的集合，E是邊（鏈路）的集合）
為了減少公共網際網路的路由選擇計算的復雜性以及方便企業管理網路，我們將路由器組織進自治系統。
在相同AS中的路由器全都運行同樣的路由選擇演算法，且擁有彼此的信息。在一個自治系統內運行的路由選擇演算法叫做自治系統內部路由選擇協議。
當然，將AS彼此互聯是必需的，因此在一個AS內的一台或多台路由器將有另外的任務，即負責向在本AS之外的目的地轉發分組。這些路由器被稱為網關路由器。
分為自治系統內部的路由選擇和自治系統間的路由選擇
1、網際網路中自治系統內部的路由選擇：路由選擇信息協議(Routing Information Protocol, RIP)
2、網際網路中自治系統內部的路由選擇：開放最短路優先(Open Shortest Path First, OSPF)
3、自治系統間的路由選擇：邊界網關協議(Broder Gateway Protocol, BGP)
為什麼要使用不同的AS間和AS內部路由選擇協議？
實現廣播的方法
1、無控制洪泛。該方法要求源結點向它的所有鄰居發送分組的副本。當某結點接收了一個廣播分組時，它復制該分組並向它的所有鄰居（除了從其接收該分組的那個鄰居）轉發之。
致命缺點： 廣播風暴 ，如果圖具有圈，那麼每個廣播分組的一個或多個分組副本將無休止地循環。
2、受控洪泛。用於避免廣播風暴，關鍵在於正確選擇何時洪泛分組，何時不洪泛分組。受控洪泛有兩種方法：序號控制洪泛、反向路徑轉發(Reverse Path Forwarding, RPF)
3、生成樹廣播。雖然序號控制洪泛和RPF能避免廣播風暴，但是它們不能完全避免冗餘廣播分組的傳輸。
多播：將分組從一個或多個發送方交付到一組接收方
每台主機有一個唯一的IP單播地址，該單播地址完全獨立於它所參與的多播組的地址。
網際網路網路層多播由兩個互補組件組成：網際網路組管理協議(Internet Group Management Protocol, IGMP)和多播路由選擇協議
IGMP只有三種報文類型：membership_query報文，membership_report報文，leave_group報文。
與ICMP類似，IGMP報文也是承載在一個IP數據報中。
網際網路中使用的多播路由選擇
1、距離向量多播路由選擇協議
2、協議無關的多播路由選擇協議
㈡ 計算機網路基礎知識
ping和traceroute都是基於ICMP協議進行的。 ping查詢報文的操作，通過直接ping ip或者ping 域名的方式，計算機會一直發送ICMP請求，目標收到了信息會回復ICMP信息，頭部類型8和0分別表示了發送和接收信息。
網關和路由器一般是黏在一起的，網關往往分為兩種，轉發網關和NAT（network address translate）網關。兩者區別：
路由協議：路由之間需要進行溝通從而知道你到底幫助我些什麼？路由器會維護一張路由表來記錄如下問題：
（1）目的網路：你的目的地是哪裡？
（2）出口設備：將包從哪個口扔出去？
（3）下一跳網關：下一個路由器的地址？
路由之間通過兩種演算法來構建路由器之間的網狀關系，以及相互的最短路徑。
第一種：距離矢量路由
第二種：鏈路狀態路由演算法
拓展：域名、IP、MAC 與 ARP
ARP 英文全名為：Address resolution protocol ，地址解析協議， ARP為IP與MAC提供動態映射，過程自動完成。 當PC發出通信請求時，根據協議規定，它的目的地址必然是48bit的MAC地址的。MAC並不能和IP直接去通信。那麼就需我們的ARP協議來做相應的轉換工作。
㈢ 計算機網路協議四的特點和原理
ip就是網際互聯協議，支持的有4個協議：ARP,RARP,ICMP,IGMP1.網路互連把自己的網路同其它的網路互連起來，從網路中獲取的信息和向網路發布自己的消息，是網路互連的最主要的動力。網路的互連有多種方式，其中使用最多的是網橋互連和路由器互連。1.1網橋互連的網路網橋工作在OSI模型中的第二層，即鏈路層。完成數據幀(frame)的轉發，主要目的是在連接的網路間提供透明的通信。網橋的轉發是依據數據幀中的源地址和目的地址來判斷一個幀是否應轉發和轉發到哪個埠。幀中的地址稱為「MAC」地址或「硬體」地址，一般就是網卡所帶的地址。網橋的作用是把兩個或多個網路互連起來，提供透明的通信。網路上的設備看不到網橋的存在，設備之間的通信就如同在一個網上一樣方便。由於網橋是在數據幀上進行轉發的，因此只能連接相同或相似的網路(相同或相似結構的數據幀)，如乙太網之間、乙太網與令牌環(tokenring)之間的互連，對於不同類型的網路(數據幀結構不同)，如乙太網與X.25之間，網橋就無能為力了。網橋擴大了網路的規模，提高了網路的性能，給網路應用帶來了方便，在以前的網路中，網橋的應用較為廣泛。但網橋互連也帶來了不少問題：一個是廣播風暴，網橋不阻擋網路中廣播消息，當網路的規模較大時(幾個網橋，多個乙太網段)，有可能引起廣播風暴(broadcastingstorm)，導致整個網路全被廣播信息充滿，直至完全癱瘓。第二個問題是，當與外部網路互連時，網橋會把內部和外部網路合二為一，成為一個網，雙方都自動向對方完全開放自己的網路資源。這種互連方式在與外部網路互連時顯然是難以接受的。問題的主要根源是網橋只是最大限度地把網路溝通，而不管傳送的信息是什麼。1.2路由器互連網路路由器互連與網路的協議有關，我們討論限於TCP/IP網路的情況。路由器工作在OSI模型中的第三層，即網路層。路由器利用網路層定義的「邏輯」上的網路地址(即IP地址)來區別不同的網路，實現網路的互連和隔離，保持各個網路的獨立性。路由器不轉發廣播消息，而把廣播消息限制在各自的網路內部。發送到其他網路的數據茵先被送到路由器，再由路由器轉發出去。IP路由器只轉發IP分組，把其餘的部分擋在網內(包括廣播)，從而保持各個網路具有相對的獨立性，這樣可以組成具有許多網路(子網)互連的大型的網路。由於是在網路層的互連，路由器可方便地連接不同類型的網路，只要網路層運行的是IP協議，通過路由器就可互連起來。網路中的設備用它們的網路地址(TCP/IP網路中為IP地址)互相通信。IP地址是與硬體地址無關的「邏輯」地址。路由器只根據IP地址來轉發數據。IP地址的結構有兩部分，一部分定義網路號，另一部分定義網路內的主機號。目前，在Internet網路中採用子網掩碼來確定IP地址中網路地址和主機地址。子網掩碼與IP地址一樣也是32bit，並且兩者是一一對應的，並規定，子網掩碼中數字為「1」所對應的IP地址中的部分為網路號，為「0」所對應的則為主機號。網路號和主機號合起來，才構成一個完整的IP地址。同一個網路中的主機IP地址，其網路號必須是相同的，這個網路稱為IP子網。通信只能在具有相同網路號的IP地址之間進行，要與其它IP子網的主機進行通信，則必須經過同一網路上的某個路由器或網關(gateway)出去。不同網路號的IP地址不能直接通信，即使它們接在一起，也不能通信。路由器有多個埠，用於連接多個IP子網。每個埠的IP地址的網路號要求與所連接的IP子網的網路號相同。不同的埠為不同的網路號，對應不同的IP子網，這樣才能使各子網中的主機通過自己子網的IP地址把要求出去的IP分組送到路由器上。2.路由原理當IP子網中的一台主機發送IP分組給同一IP子網的另一台主機時，它將直接把IP分組送到網路上，對方就能收到。而要送給不同IP於網上的主機時，它要選擇一個能到達目的子網上的路由器，把IP分組送給該路由器，由路由器負責把IP分組送到目的地。如果沒有找到這樣的路由器，主機就把IP分組送給一個稱為「預設網關(defaultgateway)」的路由器上。「預設網關」是每台主機上的一個配置參數，它是接在同一個網路上的某個路由器埠的IP地址。路由器轉發IP分組時，只根據IP分組目的IP地址的網路號部分，選擇合適的埠，把IP分組送出去。同主機一樣，路由器也要判定埠所接的是否是目的子網，如果是，就直接把分組通過埠送到網路上，否則，也要選擇下一個路由器來傳送分組。路由器也有它的預設網關，用來傳送不知道往哪兒送的IP分組。這樣，通過路由器把知道如何傳送的IP分組正確轉發出去，不知道的IP分組送給「預設網關」路由器，這樣一級級地傳送，IP分組最終將送到目的地，送不到目的地的IP分組則被網路丟棄了。目前TCP/IP網路，全部是通過路由器互連起來的，Internet就是成千上萬個IP子網通過路由器互連起來的國際性網路。這種網路稱為以路由器為基礎的網路(routerbasednetwork)，形成了以路由器為節點的「網間網」。在「網間網」中，路由器不僅負責對IP分組的轉發，還要負責與別的路由器進行聯絡，共同確定「網間網」的路由選擇和維護路由表。路由動作包括兩項基本內容：尋徑和轉發。尋徑即判定到達目的地的最佳路徑，由路由選擇演算法來實現。由於涉及到不同的路由選擇協議和路由選擇演算法，要相對復雜一些。為了判定最佳路徑，路由選擇演算法必須啟動並維護包含路由信息的路由表，其中路由信息依賴於所用的路由選擇演算法而不盡相同。路由選擇演算法將收集到的不同信息填入路由表中，根據路由表可將目的網路與下一站(nexthop)的關系告訴路由器。路由器間互通信息進行路由更新，更新維護路由表使之正確反映網路的拓撲變化，並由路由器根據量度來決定最佳路徑。這就是路由選擇協議(routingprotocol)，例如路由信息協議(RIP)、開放式最短路徑優先協議(OSPF)和邊界網關協議(BGP)等。轉發即沿尋徑好的最佳路徑傳送信息分組。路由器首先在路由表中查找，判明是否知道如何將分組發送到下一個站點(路由器或主機)，如果路由器不知道如何發送分組，通常將該分組丟棄;否則就根據路由表的相應表項將分組發送到下一個站點，如果目的網路直接與路由器相連，路由器就把分組直接送到相應的埠上。這就是路由轉發協議(routedprotocol)。路由轉發協議和路由選擇協議是相互配合又相互獨立的概念，前者使用後者維護的路由表，同時後者要利用前者提供的功能來發布路由協議數據分組。下文中提到的路由協議，除非特別說明，都是指路由選擇協議，這也是普遍的習慣。3.路由協議典型的路由選擇方式有兩種：靜態路由和動態路由。靜態路由是在路由器中設置的固定的路由表。除非網路管理員干預，否則靜態路由不會發生變化。由於靜態路由不能對網路的改變作出反映，一般用於網路規模不大、拓撲結構固定的網路中。靜態路由的優點是簡單、高效、可靠。在所有的路由中，靜態路由優先順序最高。當動態路由與靜態路由發生沖突時，以靜態路由為准。動態路由是網路中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由器表的過程。它能實時地適應網路結構的變化。如果路由更新信息表明發生了網路變化，路由選擇軟體就會重新計算路由，並發出新的路由更新信息。這些信息通過各個網路，引起各路由器重新啟動其路由演算法，並更新各自的路由表以動態地反映網路拓撲變化。動態路由適用於網路規模大、網路拓撲復雜的網路。當然，各種動態路由協議會不同程度地佔用網路帶寬和CPU資源。靜態路由和動態路由有各自的特點和適用范圍，因此在網路中動態路由通常作為靜態路由的補充。當一個分組在路由器中進行尋徑時，路由器首先查找靜態路由，如果查到則根據相應的靜態路由轉發分組;否則再查找動態路由。根據是否在一個自治域內部使用，動態路由協議分為內部網關協議(IGP)和外部網關協議(EGP)。這里的自治域指一個具有統一管理機構、統一路由策略的網路。自治域內部採用的路由選擇協議稱為內部網關協議，常用的有RIP、OSPF;外部網關協議主要用於多個自治域之間的路由選擇，常用的是BGP和BGP-4。下面分別進行簡要介紹。3.1RIP路由協議RIP協議最初是為Xerox網路系統的Xeroxparc通用協議而設計的，是Internet中常用的路由協議。RIP採用距離向量演算法，即路由器根據距離選擇路由，所以也稱為距離向量協議。路由器收集所有可到達目的地的不同路徑，並且保存有關到達每個目的地的最少站點數的路徑信息，除到達目的地的最佳路徑外，任何其它信息均予以丟棄。同時路由器也把所收集的路由信息用RIP協議通知相鄰的其它路由器。這樣，正確的路由信息逐漸擴散到了全網。RIP使用非常廣泛，它簡單、可靠，便於配置。但是RIP只適用於小型的同構網路，因為它允許的最大站點數為15，任何超過15個站點的目的地均被標記為不可達。而且RIP每隔30s一次的路由信息廣播也是造成網路的廣播風暴的重要原因之一。3.2OSPF路由協議80年代中期，RIP已不能適應大規模異構網路的互連，0SPF隨之產生。它是網間工程任務組織(1ETF)的內部網關協議工作組為IP網路而開發的一種路由協議。0SPF是一種基於鏈路狀態的路由協議，需要每個路由器向其同一管理域的所有其它路由器發送鏈路狀態廣播信息。在OSPF的鏈路狀態廣播中包括所有介面信息、所有的量度和其它一些變數。利用0SPF的路由器首先必須收集有關的鏈路狀態信息，並根據一定的演算法計算出到每個節點的最短路徑。而基於距離向量的路由協議僅向其鄰接路由器發送有關路由更新信息。與RIP不同，OSPF將一個自治域再劃分為區，相應地即有兩種類型的路由選擇方式：當源和目的地在同一區時，採用區內路由選擇;當源和目的地在不同區時，則採用區間路由選擇。這就大大減少了網路開銷，並增加了網路的穩定性。當一個區內的路由器出了故障時並不影響自治域內其它區路由器的正常工作，這也給網路的管理、維護帶來方便。3.3BGP和BGP-4路由協議BGP是為TCP/IP互聯網設計的外部網關協議，用於多個自治域之間。它既不是基於純粹的鏈路狀態演算法，也不是基於純粹的距離向量演算法。它的主要功能是與其它自治域的BGP交換網路可達信息。各個自治域可以運行不同的內部網關協議。BGP更新信息包括網路號/自治域路徑的成對信息。自治域路徑包括到達某個特定網路須經過的自治域串，這些更新信息通過TCP傳送出去，以保證傳輸的可靠性。為了滿足Internet日益擴大的需要，BGP還在不斷地發展。在最新的BGp4中，還可以將相似路由合並為一條路由。3.4路由表項的優先問題在一個路由器中，可同時配置靜態路由和一種或多種動態路由。它們各自維護的路由表都提供給轉發程序，但這些路由表的表項間可能會發生沖突。這種沖突可通過配置各路由表的優先順序來解決。通常靜態路由具有默認的最高優先順序，當其它路由表表項與它矛盾時，均按靜態路由轉發。4.路由演算法路由演算法在路由協議中起著至關重要的作用，採用何種演算法往往決定了最終的尋徑結果，因此選擇路由演算法一定要仔細。通常需要綜合考慮以下幾個設計目標：(1)最優化：指路由演算法選擇最佳路徑的能力。(2)簡潔性：演算法設計簡潔，利用最少的軟體和開銷，提供最有效的功能。(3)堅固性：路由演算法處於非正常或不可預料的環境時，如硬體故障、負載過高或操作失誤時，都能正確運行。由於路由器分布在網路聯接點上，所以在它們出故障時會產生嚴重後果。最好的路由器演算法通常能經受時間的考驗，並在各種網路環境下被證實是可靠的。(4)快速收斂：收斂是在最佳路徑的判斷上所有路由器達到一致的過程。當某個網路事件引起路由可用或不可用時，路由器就發出更新信息。路由更新信息遍及整個網路，引發重新計算最佳路徑，最終達到所有路由器一致公認的最佳路徑。收斂慢的路由演算法會造成路徑循環或網路中斷。(5)靈活性：路由演算法可以快速、准確地適應各種網路環境。例如，某個網段發生故障，路由演算法要能很快發現故障，並為使用該網段的所有路由選擇另一條最佳路徑。路由演算法按照種類可分為以下幾種：靜態和動態、單路和多路、平等和分級、源路由和透明路由、域內和域間、鏈路狀態和距離向量。前面幾種的特點與字面意思基本一致，下面著重介紹鏈路狀態和距離向量演算法。鏈路狀態演算法(也稱最短路徑演算法)發送路由信息到互聯網上所有的結點，然而對於每個路由器，僅發送它的路由表中描述了其自身鏈路狀態的那一部分。距離向量演算法(也稱為Bellman-Ford演算法)則要求每個路由器發送其路由表全部或部分信息，但僅發送到鄰近結點上。從本質上來說，鏈路狀態演算法將少量更新信息發送至網路各處，而距離向量演算法發送大量更新信息至鄰接路由器。由於鏈路狀態演算法收斂更快，因此它在一定程度上比距離向量演算法更不易產生路由循環。但另一方面，鏈路狀態演算法要求比距離向量演算法有更強的CPU能力和的內存空間，因此鏈路狀態演算法將會在實現時顯得更昂貴一些。除了這些區別，兩種演算法在大多數環境下都能很好地運行。最後需要指出的是，路由演算法使用了許多種不同的度量標准去決定最佳路徑。復雜的路由演算法可能採用多種度量來選擇路由，通過一定的加權運算，將它們合並為單個的復合度量、再填入路由表中，作為尋徑的標准。通常所使用的度量有：路徑長度、可靠性、時延、帶寬、負載、通信成本等。5.新一代路由器由於多媒體等應用在網路中的發展，以及ATM、快速乙太網等新技術的不斷採用，網路的帶寬與速率飛速提高，傳統的路由器已不能滿足人們對路由器的性能要求。因為傳統路由器的分組轉發的設計與實現均基於軟體，在轉發過程中對分組的處理要經過許多環節，轉發過程復雜，使得分組轉發的速率較慢。另外，由於路由器是網路互連的關鍵設備，是網路與其它網路進行通信的一個「關口」，對其安全性有很高的要求，因此路由器中各種附加的安全措施增加了CPU的負擔，這樣就使得路由器成為整個互聯網上的「瓶頸」。傳統的路由器在轉發每一個分組時，都要進行一系列的復雜操作，包括路由查找、訪問控製表匹配、地址解析、優先順序管理以及其它的附加操作。這一系列的操作大大影響了路由器的性能與效率，降低了分組轉發速率和轉發的吞吐量，增加了CPU的負擔。而經過路由器的前後分組間的相關性很大，具有相同目的地址和源地址的分組往往連續到達，這為分組的快速轉發提供了實現的可能與依據。新一代路由器，如IPSwitch、TagSwitch等，就是採用這一設計思想用硬體來實現快速轉發，大大提高了路由器的性能與效率。新一代路由器使用轉發緩存來簡化分組的轉發操作。在快速轉發過程中，只需對一組具有相同目的地址和源地址的分組的前幾個分組進行傳統的路由轉發處理，並把成功轉發的分組的目的地址、源地址和下一網關地址(下一路由器地址)放人轉發緩存中。當其後的分組要進行轉發時，茵先查看轉發緩存，如果該分組的目的地址和源地址與轉發緩存中的匹配，則直接根據轉發緩存中的下一網關地址進行轉發，而無須經過傳統的復雜操作，大大減輕了路由器的負擔，達到了提高路由器吞吐量的目標。
㈣ 計算機網路知識點
一、計算機網路概述
1.1 計算機網路的分類
按照網路的作用范圍：廣域網（WAN）、城域網（MAN）、區域網（LAN）；
按照網路使用者：公用網路、專用網路。
1.2 計算機網路的層次結構
TCP/IP四層模型與OSI體系結構對比：
1.3 層次結構設計的基本原則
各層之間是相互獨立的；
每一層需要有足夠的靈活性；
各層之間完全解耦。
1.4 計算機網路的性能指標
速率：bps=bit/s 時延：發送時延、傳播時延、排隊時延、處理時延 往返時間RTT：數據報文在端到端通信中的來回一次的時間。
二、物理層
物理層的作用：連接不同的物理設備，傳輸比特流。該層為上層協議提供了一個傳輸數據的可靠的物理媒體。簡單的說，物理層確保原始的數據可在各種物理媒體上傳輸。
物理層設備：
中繼器【Repeater，也叫放大器】：同一區域網的再生信號；兩埠的網段必須同一協議；5-4-3規程：10BASE-5乙太網中，最多串聯4個中繼器，5段中只能有3個連接主機；
集線器：同一區域網的再生、放大信號（多埠的中繼器）；半雙工，不能隔離沖突域也不能隔離廣播域。
信道的基本概念：信道是往一個方向傳輸信息的媒體，一條通信電路包含一個發送信道和一個接受信道。
單工通信信道：只能一個方向通信，沒有反方向反饋的信道；
半雙工通信信道：雙方都可以發送和接受信息，但不能同時發送也不能同時接收；
全雙工通信信道：雙方都可以同時發送和接收。
三、數據鏈路層
3.1 數據鏈路層概述
數據鏈路層在物理層提供的服務的基礎上向網路層提供服務，其最基本的服務是將源自網路層來的數據可靠地傳輸到相鄰節點的目標機網路層。數據鏈路層在不可靠的物理介質上提供可靠的傳輸。
該層的作用包括： 物理地址定址、數據的成幀、流量控制、數據的檢錯、重發 等。
有關數據鏈路層的重要知識點：
數據鏈路層為網路層提供可靠的數據傳輸；
基本數據單位為幀；
主要的協議：乙太網協議；
兩個重要設備名稱：網橋和交換機。
封裝成幀：「幀」是 數據鏈路層 數據的基本單位：
透明傳輸：「透明」是指即使控制字元在幀數據中，但是要當做不存在去處理。即在控制字元前加上轉義字元ESC。
3.2 數據鏈路層的差錯監測
差錯檢測：奇偶校驗碼、循環冗餘校驗碼CRC
奇偶校驗碼–局限性：當出錯兩位時，檢測不到錯誤。
循環冗餘檢驗碼：根據傳輸或保存的數據而產生固定位數校驗碼。
3.3 最大傳輸單元MTU
最大傳輸單元MTU(Maximum Transmission Unit)，數據鏈路層的數據幀不是無限大的，數據幀長度受MTU限制.
路徑MTU：由鏈路中MTU的最小值決定。
3.4 乙太網協議詳解
MAC地址：每一個設備都擁有唯一的MAC地址，共48位，使用十六進製表示。
乙太網協議：是一種使用廣泛的區域網技術，是一種應用於數據鏈路層的協議，使用乙太網可以完成相鄰設備的數據幀傳輸：
區域網分類：
Ethernet乙太網IEEE802.3：
乙太網第一個廣泛部署的高速區域網
乙太網數據速率快
乙太網硬體價格便宜，網路造價成本低
乙太網幀結構：
類型：標識上層協議（2位元組）
目的地址和源地址：MAC地址（每個6位元組）
數據：封裝的上層協議的分組（46~1500位元組）
CRC：循環冗餘碼（4位元組）
乙太網最短幀：乙太網幀最短64位元組；乙太網幀除了數據部分18位元組；數據最短46位元組；
MAC地址（物理地址、區域網地址）
MAC地址長度為6位元組，48位；
MAC地址具有唯一性，每個網路適配器對應一個MAC地址；
通常採用十六進製表示法，每個位元組表示一個十六進制數，用 - 或 : 連接起來；
MAC廣播地址：FF-FF-FF-FF-FF-FF。
四、網路層
網路層的目的是實現兩個端系統之間的數據透明傳送，具體功能包括定址和路由選擇、連接的建立、保持和終止等。數據交換技術是報文交換（基本上被分組所替代）：採用儲存轉發方式，數據交換單位是報文。
網路層中涉及眾多的協議，其中包括最重要的協議，也是TCP/IP的核心協議——IP協議。IP協議非常簡單，僅僅提供不可靠、無連接的傳送服務。IP協議的主要功能有：無連接數據報傳輸、數據報路由選擇和差錯控制。
與IP協議配套使用實現其功能的還有地址解析協議ARP、逆地址解析協議RARP、網際網路報文協議ICMP、網際網路組管理協議IGMP。具體的協議我們會在接下來的部分進行總結，有關網路層的重點為：
1、網路層負責對子網間的數據包進行路由選擇。此外，網路層還可以實現擁塞控制、網際互連等功能；
2、基本數據單位為IP數據報；
3、包含的主要協議：
IP協議（Internet Protocol，網際網路互聯協議）;
ICMP協議（Internet Control Message Protocol，網際網路控制報文協議）;
ARP協議（Address Resolution Protocol，地址解析協議）;
RARP協議（Reverse Address Resolution Protocol，逆地址解析協議）。
4、重要的設備：路由器。
路由器相關協議
4.1 IP協議詳解
IP網際協議是 Internet 網路層最核心的協議。虛擬互聯網路的產生：實際的計算機網路錯綜復雜；物理設備通過使用IP協議，屏蔽了物理網路之間的差異；當網路中主機使用IP協議連接時，無需關注網路細節，於是形成了虛擬網路。
IP協議使得復雜的實際網路變為一個虛擬互聯的網路；並且解決了在虛擬網路中數據報傳輸路徑的問題。
其中，版本指IP協議的版本，佔4位，如IPv4和IPv6；首部位長度表示IP首部長度，佔4位，最大數值位15；總長度表示IP數據報總長度，佔16位，最大數值位65535；TTL表示IP數據報文在網路中的壽命，佔8位；協議表明IP數據所攜帶的具體數據是什麼協議的，如TCP、UDP。
4.2 IP協議的轉發流程
4.3 IP地址的子網劃分
A類（8網路號+24主機號）、B類（16網路號+16主機號）、C類（24網路號+8主機號）可以用於標識網路中的主機或路由器，D類地址作為組廣播地址，E類是地址保留。
4.4 網路地址轉換NAT技術
用於多個主機通過一個公有IP訪問訪問互聯網的私有網路中，減緩了IP地址的消耗，但是增加了網路通信的復雜度。
NAT 工作原理：
從內網出去的IP數據報，將其IP地址替換為NAT伺服器擁有的合法的公共IP地址，並將替換關系記錄到NAT轉換表中；
從公共互聯網返回的IP數據報，依據其目的的IP地址檢索NAT轉換表，並利用檢索到的內部私有IP地址替換目的IP地址，然後將IP數據報轉發到內部網路。
4.5 ARP協議與RARP協議
地址解析協議 ARP（Address Resolution Protocol）：為網卡（網路適配器）的IP地址到對應的硬體地址提供動態映射。可以把網路層32位地址轉化為數據鏈路層MAC48位地址。
ARP 是即插即用的，一個ARP表是自動建立的，不需要系統管理員來配置。
RARP(Reverse Address Resolution Protocol)協議指逆地址解析協議，可以把數據鏈路層MAC48位地址轉化為網路層32位地址。
4.6 ICMP協議詳解
網際控制報文協議（Internet Control Message Protocol），可以報告錯誤信息或者異常情況，ICMP報文封裝在IP數據報當中。
ICMP協議的應用：
Ping應用：網路故障的排查；
Traceroute應用：可以探測IP數據報在網路中走過的路徑。
4.7網路層的路由概述
關於路由演算法的要求：正確的完整的、在計算上應該盡可能是簡單的、可以適應網路中的變化、穩定的公平的。
自治系統AS： 指處於一個管理機構下的網路設備群，AS內部網路自治管理，對外提供一個或多個出入口，其中自治系統內部的路由協議為內部網關協議，如RIP、OSPF等；自治系統外部的路由協議為外部網關協議，如BGP。
靜態路由： 人工配置，難度和復雜度高；
動態路由：
鏈路狀態路由選擇演算法LS：向所有隔壁路由發送信息收斂快；全局式路由選擇演算法，每個路由器計算路由時，需構建整個網路拓撲圖；利用Dijkstra演算法求源端到目的端網路的最短路徑；Dijkstra(迪傑斯特拉)演算法
距離-向量路由選擇演算法DV：向所有隔壁路由發送信息收斂慢、會存在迴路；基礎是Bellman-Ford方程（簡稱B-F方程）；
4.8 內部網關路由協議之RIP協議
路由信息協議 RIP(Routing Information Protocol)【應用層】，基於距離-向量的路由選擇演算法，較小的AS（自治系統），適合小型網路；RIP報文，封裝進UDP數據報。
RIP協議特性：
RIP在度量路徑時採用的是跳數（每個路由器維護自身到其他每個路由器的距離記錄）；
RIP的費用定義在源路由器和目的子網之間；
RIP被限制的網路直徑不超過15跳；
和隔壁交換所有的信息，30主動一次（廣播）。
4.9 內部網關路由協議之OSPF協議
開放最短路徑優先協議 OSPF(Open Shortest Path First)【網路層】，基於鏈路狀態的路由選擇演算法（即Dijkstra演算法），較大規模的AS ，適合大型網路，直接封裝在IP數據報傳輸。
OSPF協議優點：
安全；
支持多條相同費用路徑；
支持區別化費用度量；
支持單播路由和多播路由；
分層路由。
RIP與OSPF的對比（路由演算法決定其性質）：
4.10外部網關路由協議之BGP協議
BGP（Border Gateway Protocol）邊際網關協議【應用層】：是運行在AS之間的一種協議,尋找一條好路由：首次交換全部信息，以後只交換變化的部分,BGP封裝進TCP報文段.
五、傳輸層
第一個端到端，即主機到主機的層次。傳輸層負責將上層數據分段並提供端到端的、可靠的或不可靠的傳輸。此外，傳輸層還要處理端到端的差錯控制和流量控制問題。
傳輸層的任務是根據通信子網的特性，最佳的利用網路資源，為兩個端系統的會話層之間，提供建立、維護和取消傳輸連接的功能，負責端到端的可靠數據傳輸。在這一層，信息傳送的協議數據單元稱為段或報文。
網路層只是根據網路地址將源結點發出的數據包傳送到目的結點，而傳輸層則負責將數據可靠地傳送到相應的埠。
有關網路層的重點：
傳輸層負責將上層數據分段並提供端到端的、可靠的或不可靠的傳輸以及端到端的差錯控制和流量控制問題；
包含的主要協議：TCP協議（Transmission Control Protocol，傳輸控制協議）、UDP協議（User Datagram Protocol，用戶數據報協議）；
重要設備：網關。
5.1 UDP協議詳解
UDP(User Datagram Protocol: 用戶數據報協議)，是一個非常簡單的協議。
UDP協議的特點：
UDP是無連接協議；
UDP不能保證可靠的交付數據；
UDP是面向報文傳輸的；
UDP沒有擁塞控制；
UDP首部開銷很小。
UDP數據報結構：
首部:8B，四欄位/2B【源埠 | 目的埠 | UDP長度 | 校驗和】 數據欄位：應用數據
5.2 TCP協議詳解
TCP(Transmission Control Protocol: 傳輸控制協議)，是計算機網路中非常復雜的一個協議。
TCP協議的功能：
對應用層報文進行分段和重組；
面向應用層實現復用與分解；
實現端到端的流量控制；
擁塞控制；
傳輸層定址；
對收到的報文進行差錯檢測（首部和數據部分都檢錯）；
實現進程間的端到端可靠數據傳輸控制。
TCP協議的特點：
TCP是面向連接的協議；
TCP是面向位元組流的協議；
TCP的一個連接有兩端，即點對點通信；
TCP提供可靠的傳輸服務；
TCP協議提供全雙工通信（每條TCP連接只能一對一）；
5.2.1 TCP報文段結構：
最大報文段長度：報文段中封裝的應用層數據的最大長度。
TCP首部：
序號欄位：TCP的序號是對每個應用層數據的每個位元組進行編號
確認序號欄位：期望從對方接收數據的位元組序號，即該序號對應的位元組尚未收到。用ack_seq標識；
TCP段的首部長度最短是20B ，最長為60位元組。但是長度必須為4B的整數倍
TCP標記的作用：
5.3 可靠傳輸的基本原理
基本原理：
不可靠傳輸信道在數據傳輸中可能發生的情況：比特差錯、亂序、重傳、丟失
基於不可靠信道實現可靠數據傳輸採取的措施：
差錯檢測：利用編碼實現數據包傳輸過程中的比特差錯檢測 確認：接收方向發送方反饋接收狀態 重傳：發送方重新發送接收方沒有正確接收的數據 序號：確保數據按序提交 計時器：解決數據丟失問題；
停止等待協議：是最簡單的可靠傳輸協議，但是該協議對信道的利用率不高。
連續ARQ(Automatic Repeat reQuest：自動重傳請求)協議：滑動窗口+累計確認，大幅提高了信道的利用率。
5.3.1TCP協議的可靠傳輸
基於連續ARQ協議，在某些情況下，重傳的效率並不高，會重復傳輸部分已經成功接收的位元組。
5.3.2 TCP協議的流量控制
流量控制：讓發送方發送速率不要太快，TCP協議使用滑動窗口實現流量控制。
5.4 TCP協議的擁塞控制
擁塞控制與流量控制的區別：流量控制考慮點對點的通信量的控制，而擁塞控制考慮整個網路，是全局性的考慮。擁塞控制的方法：慢啟動演算法+擁塞避免演算法。
慢開始和擁塞避免：
【慢開始】擁塞窗口從1指數增長；
到達閾值時進入【擁塞避免】，變成+1增長；
【超時】，閾值變為當前cwnd的一半（不能<2）；
再從【慢開始】，擁塞窗口從1指數增長。
快重傳和快恢復：
發送方連續收到3個冗餘ACK，執行【快重傳】，不必等計時器超時；
執行【快恢復】，閾值變為當前cwnd的一半（不能<2），並從此新的ssthresh點進入【擁塞避免】。
5.5 TCP連接的三次握手（重要）
TCP三次握手使用指令：
面試常客：為什麼需要三次握手？
第一次握手：客戶發送請求，此時伺服器知道客戶能發；
第二次握手：伺服器發送確認，此時客戶知道伺服器能發能收；
第三次握手：客戶發送確認，此時伺服器知道客戶能收。
建立連接（三次握手）：
第一次： 客戶向伺服器發送連接請求段，建立連接請求控制段（SYN=1），表示傳輸的報文段的第一個數據位元組的序列號是x，此序列號代表整個報文段的序號（seq=x）；客戶端進入 SYN_SEND （同步發送狀態）；
第二次： 伺服器發回確認報文段，同意建立新連接的確認段（SYN=1），確認序號欄位有效（ACK=1），伺服器告訴客戶端報文段序號是y（seq=y），表示伺服器已經收到客戶端序號為x的報文段，准備接受客戶端序列號為x+1的報文段（ack_seq=x+1）；伺服器由LISTEN進入SYN_RCVD （同步收到狀態）;
第三次： 客戶對伺服器的同一連接進行確認.確認序號欄位有效(ACK=1),客戶此次的報文段的序列號是x+1(seq=x+1),客戶期望接受伺服器序列號為y+1的報文段(ack_seq=y+1);當客戶發送ack時，客戶端進入ESTABLISHED 狀態;當服務收到客戶發送的ack後，也進入ESTABLISHED狀態;第三次握手可攜帶數據;
5.6 TCP連接的四次揮手（重要）
釋放連接（四次揮手）
第一次： 客戶向伺服器發送釋放連接報文段，發送端數據發送完畢，請求釋放連接（FIN=1），傳輸的第一個數據位元組的序號是x（seq=x）；客戶端狀態由ESTABLISHED進入FIN_WAIT_1（終止等待1狀態）；
第二次： 伺服器向客戶發送確認段，確認字型大小段有效（ACK=1），伺服器傳輸的數據序號是y（seq=y），伺服器期望接收客戶數據序號為x+1（ack_seq=x+1）;伺服器狀態由ESTABLISHED進入CLOSE_WAIT（關閉等待）；客戶端收到ACK段後，由FIN_WAIT_1進入FIN_WAIT_2；
第三次： 伺服器向客戶發送釋放連接報文段，請求釋放連接（FIN=1），確認字型大小段有效（ACK=1），表示伺服器期望接收客戶數據序號為x+1（ack_seq=x+1）;表示自己傳輸的第一個位元組序號是y+1（seq=y+1）；伺服器狀態由CLOSE_WAIT 進入 LAST_ACK （最後確認狀態）；
第四次： 客戶向伺服器發送確認段，確認字型大小段有效（ACK=1），表示客戶傳輸的數據序號是x+1（seq=x+1），表示客戶期望接收伺服器數據序號為y+1+1（ack_seq=y+1+1）；客戶端狀態由FIN_WAIT_2進入TIME_WAIT，等待2MSL時間，進入CLOSED狀態；伺服器在收到最後一次ACK後，由LAST_ACK進入CLOSED；
為什麼需要等待2MSL?
最後一個報文沒有確認；
確保發送方的ACK可以到達接收方；
2MSL時間內沒有收到，則接收方會重發；
確保當前連接的所有報文都已經過期。
六、應用層
為操作系統或網路應用程序提供訪問網路服務的介面。應用層重點：
數據傳輸基本單位為報文；
包含的主要協議：FTP（文件傳送協議）、Telnet（遠程登錄協議）、DNS（域名解析協議）、SMTP（郵件傳送協議），POP3協議（郵局協議），HTTP協議（Hyper Text Transfer Protocol）。
6.1 DNS詳解
DNS（Domain Name System:域名系統）【C/S，UDP，埠53】：解決IP地址復雜難以記憶的問題,存儲並完成自己所管轄范圍內主機的 域名 到 IP 地址的映射。
域名解析的順序：
【1】瀏覽器緩存，
【2】找本機的hosts文件，
【3】路由緩存，
【4】找DNS伺服器（本地域名、頂級域名、根域名）->迭代解析、遞歸查詢。
IP—>DNS服務—>便於記憶的域名
域名由點、字母和數字組成，分為頂級域（com，cn，net，gov，org）、二級域（,taobao,qq,alibaba）、三級域（www）(12-2-0852)
6.2 DHCP協議詳解
DHCP（Dynamic Configuration Protocol:動態主機設置協議）：是一個區域網協議，是應用UDP協議的應用層協議。作用：為臨時接入區域網的用戶自動分配IP地址。
6.3 HTTP協議詳解
文件傳輸協議（FTP）：控制連接（埠21）：傳輸控制信息（連接、傳輸請求），以7位ASCII碼的格式。整個會話期間一直打開。
HTTP（HyperText Transfer Protocol:超文本傳輸協議）【TCP，埠80】：是可靠的數據傳輸協議，瀏覽器向伺服器發收報文前，先建立TCP連接，HTTP使用TCP連接方式（HTTP自身無連接）。
HTTP請求報文方式：
GET：請求指定的頁面信息，並返回實體主體；
POST：向指定資源提交數據進行處理請求；
DELETE：請求伺服器刪除指定的頁面；
HEAD：請求讀取URL標識的信息的首部，只返回報文頭；
OPETION：請求一些選項的信息；
PUT：在指明的URL下存儲一個文檔。
6.3.1 HTTP工作的結構
6.3.2 HTTPS協議詳解
HTTPS(Secure)是安全的HTTP協議，埠號443。基於HTTP協議，通過SSL或TLS提供加密處理數據、驗證對方身份以及數據完整性保護
原文地址：https://blog.csdn.net/Royalic/article/details/119985591
㈤ 計算機網路的形成要素是什麼
計算機網路的協議三要素
答：三要素是：1，語法：關於諸如數據格式及信號電平等的規定；2，語義：關於協議動作和差錯處理等控制信息；3，定時：包含速率匹配和排序等。
你還可以了解更多啊！
計算機網路
1． 關於計算機網路的定義。
答：廣義的觀點：計算機技術與通信技術相結合，實現遠程信息處理或進一步達到資源共享的系統；資源共享的觀點：以能夠相互共享資源的方式連接起來，並且各自具有獨立功能的計算機系統的集合；對用戶透明的觀點：存在一個能為用戶自動管理資源的網路操作系統，由它來調用完成用戶任務所需要的資源，而整個網路像一個大的計算機系統一樣對用戶是透明的，實際上這種觀點描述的是一個分布式系統。
2． 計算機網路的拓樸結構。
答：計算機網路採用拓樸學的研究方法，將網路中的設備定義為結點，把兩個設備之間的連接線路定義為鏈路。計算機網路也是由一組結點和鏈路組成的的幾何圖形，這就是拓樸結構。
分類：按信道類型分，分為點---點線路通信子網和廣播信道的通信子網。採用點——點連線的通信子網的基本結構有四類：星狀、環狀、樹狀和網狀；廣播信道通子網有匯流排狀、環狀和無線狀。
3． 計算機網路的體系結構
答：將計算機網路的層次結構模型和分層協議的集合定義為計算機網路體系結構。
4．計算機網路的協議三要素
答：三要素是：1，語法：關於諸如數據格式及信號電平等的規定；2，語義：關於協議動作和差錯處理等控制信息；3，定時：包含速率匹配和排序等。
5．OSI七層協議體系結構和各級的主要作用
答：七層指：由低到高，依次是物理層，數據鏈路層，網路層，傳輸層，會話層，表示層和應用層。各層作用分別是：
物理層：向上與數據鏈路層相連，向下直接連接傳輸介質。提供一些建立、維持和釋放物理連接的方法，以便能在兩個或多個數據鏈路實體間進行數據位流的傳輸。
數據鏈路層：通過差錯控制、流量控制等，將不可靠的物理傳輸信道變成無差錯的可靠的數據鏈路。將數據組成適合正確傳輸的幀形式的數據單元，對網路層屏蔽物理層的特性和差異，使高層協議不必考慮物理傳輸介質的可靠性問題。
網路層：決定數據在通信子網中的傳送路徑，控制通信子網中的數據流量並防止擁塞等，提供建立、維護和終止網路連接的手段。網路層是通信子網的最高層。
傳輸層：為源主機到目的主機提供可靠的、有效的數據傳輸，這種傳輸與網路無關，傳輸層是獨立於物理網路的。其上層協議不必了解實際網路，就可將數據安全可靠地傳送到目的地。
會話層：建立、維護和同步進行通信的高層之間的對話。服務主要是：協調應用程序之間的連接建立和中斷；為數據交互提供同步點；協調通信雙方誰可在何時發送數據；確保數據交換在會話關閉之前完成等。
表示層：把源端機器的數據編碼成適合於傳輸的比特序列，傳送到目的端後再進行解碼，在保持數據含義不變的條件下，轉換成用戶所理解的形式。
應用層：為用戶的應用進程訪問OSI環境提供服務。
6．TCP/IP協議體系結構
答：TCP/IP是一個協議系列，目前已飲食了100多個協議，用於將各種計算機和數據通信設備組成計算機網路。
TCP/IP協議具有如下特點：1，協議標准具有開放性，其獨立於特定的計算機硬體與操作系統，可以免費使用；2，統一分配網路地址，使得整個TCP/IP設備在網路中都具有惟一的IP地址。
分層：應用層（SMTP, DNS, NFS, FTP, Telnet, Others）、傳輸層（TCP,UDP）、互聯層（IP，ICMP, ARP, RARP）、主機——網路層(Ethernet, ARPANET, PDN ,Others)。
傳輸控制協議TCP：定義了兩台計算機之間進行可靠數據傳輸所交換的數據和確認信息的格式，以及計算機為了確保數據的正確到達而採取的措施。
IP協議：
7．計算機網路常用的傳輸介質及光纖傳輸的類型與特點
答：有：1，有線介質，包括雙絞線，同軸電纜，光纖；2，無線介質，包括無線電傳輸系統，紅外線，微波。
雙絞線：將兩根相互絕緣的導體按一定的規格將它們纏繞在一起製成。
同軸電纜：由兩個同心圓導中間填充絕緣材料製成。
8．計算機網路的交換技術種類和各自的特點
答：數據交換的種類有：線路交換，報文交換，分組交換（虛電路，數據報），快速交換（ATM（非同步傳輸模式），FR（幀中繼））。
線路交換：在一對需要進行通信的設備（結點）之間提供一條暫的專用的傳輸通道。工作步驟：線路建立，數據通信，電路拆除，釋放相關資源。
報文交換特點：1，在源與目的結點之間無須建立專用通道，對網路的故障適應能力較強；2，沒有建立和拆除電路的時間延遲；3，線路利用率較高，可以進行速率上的調整；4，可靠性較高；5，每個節點對報文進行全面的處理，如果傳輸出錯，要重發整個報文。
分組交換（packet switching）：傳輸的信息是報文分組，將一個長的報文分割成若干個分組來傳輸。
高速交換：ATM（非同步傳輸模式）：把線路交換跟分組交換相結合。以固定長度（53位元組：信元頭5位元組，正文48位元組）。FR（幀中繼）：採用永久虛電路，只要接收完幀的目的地址（不是指向本結點就立即轉發幀）若傳輸出錯，則給下游結點發送錯誤指示，要它終止接收，並要求上游重發該幀。
9．以數據報為例敘述交換技術的工作過程
10．CSMA/CD匯流排型網路的拓樸結構，幀結構及其基本工作過程
CSMA/CD（Carrier sense Multiple Access with Collision Detection）帶有沖突檢測的載波偵聽多路訪問。
拓樸結構：？
11．令牌環網的拓樸結構，幀結構及其基本工作過程
12．計算機網路流量控制的目的和流量控制的級別
目的：1，防止網路因過載而引起吞吐量下降和延時的增加；2，減少擁塞，避免死鎖；3，在互相競爭的用戶之間公平合理地分配資源。
四種級別：1，相鄰結點間的流量控制，2，源結點和目的結點間的流量控制；3，主機與源結點間的流量控制；4，源主機與目的主機間的流量控制。
13．關於源路由網橋的概念和工作原理（P102）
源路由網橋（IEEE802。5工作組選用的網橋，面向令牌環網）：是指源站點要提供偵傳送的路由信息，該路由信息（Routing Information）設置在該幀的頭部，用於標識幀的傳輸路徑（面向連接的網橋）。
工作原理：源站要向目的站通信前，必須尋找通向目的站的路徑（實際上是建立連接的過程：源站首先向全網廣播一個「探測幀」，該幀每經過一個網橋，網橋把自己相關路由信息寫入該探測幀，為該到達目的站時，該數據包就記錄下一張它所經過的路徑圖（路由表）。目的站會使這個探測幀返回（實際由目的站發出一個應答幀）當源站接收到應答幀時，則可以說連接已建立）。
14．關於透明網橋的概念和工作原理（P99）
所謂透明網橋是指網橋的操作過程對其埠上連接的網段上的工作站是「透明的」，換句話說，工作站用戶並不知道網橋的存在。
15．路由器的基本工作過程及其作用
基本工作過程：
A， 路由器工作在網路層，它的傳輸單位是分組（packet），又稱數據包
B， 當路由器接收到一個包時，首先進行拆包，把數據鏈路層的信息去掉，讀取網路層的信息
C， 根據包的目的地址（指向）進行：本地提交（本網是目的結點所在網路）；分組轉發（選擇轉發路由）
D，數據安全性檢查（轉發檢驗）
E， 通過安全檢查後，則進行打包，（封裝）加入數據鏈路層的信息，轉發該包。
基本功能：
1， 協議轉換
2， 路由選擇
3， 支持多協議的路由選擇
4， 流量控制
5， 分組的分段與組裝
6， 網路管理功能
（未完成）16．路由選擇演算法的分類和理想路由選擇演算法應具有的特點
路由演算法有：距離矢量演算法和鏈路狀態演算法。
距離矢量演算法：以某一參考點到達目的結點的距離作為度量的演算法。這里的距離指該路徑上所經歷的最少網關（也指路由器）數。
鏈路狀態演算法：實際上是一種「最短路徑優先」的演算法。
特點：？
17．距離向量演算法和RIP的工作過程(p110)
距離向量演算法的基本思想：以某一參考點到目的結點的距離作為演算法的度量。
RIP（routing Information Protocol）路由信息協議工作過程：1，初始化（啟動RIP協議）；2，路由表交換路由信息；3，路由表更新（最知線路優先）。（P113）
18．路由器的主機名和埠配置使用方法
配置主機名（路由器）：每台路由器主機的預設名Router。假設把它配置為路由器R2則輸入命令：
router (config) #host name Router (R2)
顯示：Router R2 (config) #
埠配置（埠地址配置）：
① Router R2 (config) # interface eithernet 0
② Router R2 (config-if) # ip address 200.111.50.1 255.255.255.0
配置埠的IP地址：200.111.50.1
相應的子網掩碼：255.255.255.0
③ Router R2 (config ) # interface serial 0 (0是串列口)
④ Router R2 (config-if)# ip address 128.120.1.1 255.255.255.0
19．奈奎斯特和香農定律原理
（離散信號的信道容量）奈奎斯特定律：C = 2 F log2 L (bps) 每秒的信道容量，信道的最大傳輸速率
C：信道容量。 F：帶寬。 L：符號的離散取值。
（連續信號的信道容量）香農定律：C = F log2 (1+S/N)
S:通過的信號平均功率。 N：雜訊（干擾信號）的功率。所謂雜訊是指干擾信號（雜訊）在所有頻率上的強度都一樣。 S/N：採用信噪比來代替。 SNR 其單位是分貝。DB
分貝值 = 10 log10 (S/N) 分貝值是可測量的。則可利用分貝值得到S/N。
20．計算機網路中常用的編碼技術
（1） 單極性不歸零編碼（NRZ）
（2） 曼徹斯特編碼（Manchester Encoding）
（3） 差分曼徹斯特編碼
21．畫圖說明頻移鍵控法的工作原理
22．PCM技術的基本工作步驟
1， 取樣：按照一定的時間間隔采樣測量模擬信號幅值
2， 量化：將取樣點測量的信號幅值分級取整
3， 編碼：將量化的結果（整數據）用二進制數表示出來
23．非同步傳輸的編碼結構
也叫「起/停方式」：每傳送1個字元（5bit/8bit）都在字元前面加入一位開始位（「0」表示使用停電平表示傳送開始），而在代碼校驗（奇/偶）後面跟隨停止位（1位，3/2位或2位，用「1」高電平表示，代表字元傳輸結束）
以ASCII碼的A字元為例（11位非同步碼結構）
A字元：41H = 1000001 編碼後：01000001111
24．HDLC的幀結構和基於比特流的傳輸控制流程規程的主要特性
HDLC(High Data Link Control)高級數據鏈路控制：基於比特傳輸的控制規程。主要特徵如下：
① 通信方式：全雙工
② 差錯控制：循環冗餘碼（CRC）
③ 同步方式：同步
④ 電碼：隨機碼（任意二進制編碼）
⑤ 信息長度：可變區
⑥ 速率：2400bps以上
⑦ 發關方式：連續發送，即發送方送出一個信息幀後，不等接收方的應答，則繼續發關隨後的幀，接收方的應答信號是利用全雙工的另一信道在它發送給發送方的信息幀的控制欄位中夾帶回「已收到某編號的信息幀」（期待接收某個編號的幀）這表明此號幀以前的信息幀已正確接收。如果發現傳輸出錯，則請求重傳該號幀及其隨後的幀。
HDLC的幀結構：
F
A
C
I
FCS
F
同步標志（01111110） 地址 控制欄位 正文 循環冗餘碼 標志
25．計算機網路中使用的循環冗餘碼校驗的工作原理
26．多路復用的基本思想和種類
多路復用原理：就是讓一條線路復用成多個子信道來使用
種類有：
1， 頻分多路復用（FDM）：分割線路的帶寬，形成多個子信道（頻度）
2， 同步時分多路復用（TDM）：分割線路的傳輸時間形成多個子信道（一個時間片）時隙
3， 統計時分多路復用（STDM）：分割線路的傳輸時間。但動不是固定給用戶分配時間片，而是需要傳送時，才給它分配時間片。
4， 波分多路復用（WOM）：光纖上使用分割的是信號光的波長
27．頻分多路復用的工作原理
28．時分多路復用的種類和各自的工作特性
29．會話層的同步方法
為了控制信息流同時能夠從軟體或操作失誤中恢復過來，會話層允許在數據中插入同步點，當出現故障時，找到故障處的前一個同步點並從該同步點進行恢復，這個過程稱為再同步。對話過程中可以插入次同步點，如果傳輸中出了故障，控制流可以退回到對話中的一個或多個次同步上進行恢復。主同步點必須被確認，次同步點不需要確認。
30．表示層的局部語法和傳送語法
局部語法：某一具體計算機所使用的語法稱為局部語法。局部語法的差異使得同一數據對象在不同的計算機中被表示成不同的比特序列。
傳送語法：符全傳送過程要求的語法。數據以傳送語法的形式在網路中傳送，發送方將符合自己局部語法的比特序列轉換成符合傳送語法的比特序列。
31．交換機的交換結構和各自的特點
交換結構有：軟體執行交換結構、矩陣交換結構、匯流排交換結構、共享存儲器交換結構。
軟體執行交換結構：藉助CPU和RAM的硬體環境，用特定的軟體來實現埠之間的幀交換。所有功能均由軟體來實現，操作靈活，但隨著端品數和增加，CPU的負擔加重。
矩陣交換：採用硬體方法進行交換。優點是利用硬體交換，結構緊湊，交換速度快，延遲時間短，缺點是隨著埠的增加，監控和管理變得困難。
匯流排交換：對匯流排的帶寬要求較高，造價高，但性能也好。
存儲交換：結構簡單、容易實現，但通過RAM操作會產生延時。
32．交換機的組成和各部分的主要作用
大多數交換器都有一塊背板，把各種板卡插在其上面，實現相應連接，交換器的主要部件包括控制、邏輯、陣列、及埠四個。
1， 控制部件：其作用是控制、管理交換器，識別連接到各埠的區域網的類型，並自動地進行交換器的測試
2， 邏輯部件：其作用是讀取輸入數據幀的目的地址，並以此目的地址與埠地址表中的內容進行比較，找出該目的地址對應的埠號，批示陣列部件按通對應的（輸出埠）矩陣開頭（來接到輸出埠）
3， 陣列部件：一旦接收到邏輯部件的指令時，啟動源埠（輸入）與目的埠（輸出）之間的交叉連接，並保持該連接直到該幀全部傳送完
4， 埠部件：可以看成一組物理介面
33．交換機的轉發率和過濾率
交換器的過濾率是在某段時間內（通常為1秒）所解釋多少幀的目的地址，這種能力稱為過濾率。
轉發率是指在某段時間內（1秒）所轉發幀的數目，稱為轉發率。
34．如何使用交換機、集線器、路由器、防火牆和常用傳輸介質組建企業網路
35．關於VLAN的定義和其主要功能（P87）
VLAN（virtual LAN）虛擬區域網：建立在物理交換機之上的，它利用軟體進行邏輯工作組的劃分和管理。
36．X．25的協議體系結構
X.25協議是CCITT關於公用數據網上以分組方式工作的DTE與DCE之間的介面標准，其功能是為公用數據網在分組交換方式下提供終端操作，它不涉及通信子網的內部結構。
層次結構：自下至上分別稱為物理級、幀級、分組級。
37．幀中繼的基本工作原理
38．ATM的協議參考模型（P141）
39．ATM交換技術的特點
特點：
（1） 採用面向連接的工作方式。
（2） 採用非同步時分多路方式
（3） 網路沒有逐段鏈路的差錯控制和流量控制。
（4） 信頭功能簡單
（5） 小的信元長度
40．ATM交換虛連接的工作過程（P132）
41．什麼是ISDN，定義了哪些設備和介面
ISDN是用來解決一些小的辦公室或撥號用戶需要比傳統電話撥號服務能提供更寬傳輸帶寬的應用，同時ISDN也可用來提供線路備份。
42．IP地址結構和子網劃分的作用
結構：每個IP地址共有32位，分為4段，以X。X。X。X表示，每個X為8位，取值為0~255。分為網路地址和主機地址兩部分，其中網路地址表示一個網路，主機地址用來表示這個網路中的一台主機。
㈥ 網路協議-- 底層網路知識詳解（從二層到三層）
網線
Hub 採取的是廣播的模式，如果每一台電腦發出的包，宿舍的每個電腦都能收到，那就麻煩了。這就需要解決幾個問題：
這幾個問題，都是第二層， 數據鏈路層 ，也即 MAC 層要解決的問題。 MAC 的全稱是 Medium Access Control ，即媒體訪問控制。控制什麼呢？其實就是控制在往媒體上發數據的時候，誰先發、誰後發的問題。防止發生混亂。這解決的是第二個問題。這個問題中的規則，學名叫 多路訪問 。
三種方式：
方式一：分多個車道。每個車一個車道，你走你的，我走我的。這在計算機網路里叫作 信道劃分 ；
方式二：今天單號出行，明天雙號出行，輪著來。這在計算機網路里叫作 輪流協議 ；
方式三：不管三七二十一，有事兒先出門，發現特堵，就回去。錯過高峰再出。我們叫作 隨機接入協議 。著名的乙太網，用的就是這個方式。
接下來要解決第一個問題：發給誰，誰接收？這里用到一個物理地址，叫作 鏈路層地址 。但是因為第二層主要解決媒體接入控制的問題，所以它常被稱為 MAC 地址 。
解決第一個問題就牽扯到第二層的網路包格式。
對於乙太網，第二層的最後面是 CRC，也就是循環冗餘檢測。通過 XOR 異或的演算法，來計算整個包是否在發送的過程中出現了錯誤，主要解決第三個問題。
這里還有一個沒有解決的問題，當源機器知道目標機器的時候，可以將目標地址放入包裡面，如果不知道呢？一個廣播的網路裡面接入了 N 台機器，我怎麼知道每個 MAC 地址是誰呢？這就是 ARP 協議 ，也就是已知 IP 地址，求 MAC 地址的協議。
ARP 是通過吼的方式（廣播）來尋找目標 MAC 地址的，吼完之後記住一段時間，這個叫作緩存。
誰能知道目標 MAC 地址是否就是連接某個口的電腦的 MAC 地址呢？這就需要一個能把 MAC 頭拿下來，檢查一下目標 MAC 地址，然後根據策略轉發的設備，這個設備顯然是個二層設備，我們稱為 交換機 。
交換機是有 MAC 地址學習能力的，學完了它就知道誰在哪兒了，不用廣播了。（剛開始不知道的時候，是需要廣播的）
當交換機的數目越來越多的時候，會遭遇環路問題，讓網路包迷路，這就需要使用 STP 協議，通過華山論劍比武的方式，將有環路的圖變成沒有環路的樹，從而解決環路問題。
在數據結構中，有一個方法叫做 最小生成樹 。有環的我們常稱為圖。將圖中的環破了，就生成了樹。在計算機網路中，生成樹的演算法叫作 STP ，全稱 Spanning Tree Protocol 。
STP 協議比較復雜，一開始很難看懂，但是其實這是一場血雨腥風的武林比武或者華山論劍，最終決出五嶽盟主的方式。
交換機數目多會面臨隔離問題，可以通過 VLAN 形成 虛擬區域網 ，從而解決廣播問題和安全問題。
對於支持 VLAN 的交換機，有一種口叫作 Trunk 口。它可以轉發屬於任何 VLAN 的口。交換機之間可以通過這種口相互連接。
ping 是基於 ICMP 協議工作的。
ICMP 全稱 Internet Control Message Protocol ，就是 互聯網控制報文協議 。
ICMP 報文是封裝在 IP 包裡面的。因為傳輸指令的時候，肯定需要源地址和目標地址。它本身非常簡單。因為作為偵查兵，要輕裝上陣，不能攜帶大量的包袱。
ICMP總結：
ICMP 相當於網路世界的偵察兵。我講了兩種類型的 ICMP 報文，一種是主動探查的查詢報文，一種異常報告的差錯報文；
ping 使用查詢報文，Traceroute 使用差錯報文。
在進行網卡配置的時候，除了 IP 地址，還需要配置一個Gateway 的東西，這個就是 網關 。
一旦配置了 IP 地址和網關，往往就能夠指定目標地址進行訪問了。由於在跨網關訪問的時候，牽扯到 MAC 地址和 IP 地址的變化，這里有必要詳細描述一下 MAC 頭和 IP 頭的細節。
路由器是一台設備，它有五個網口或者網卡，相當於有五隻手，分別連著五個區域網。每隻手的 IP 地址都和區域網的 IP 地址相同的網段，每隻手都是它握住的那個區域網的網關。
對於 IP 頭和 MAC 頭哪些變、哪些不變的問題，可以分兩種類型。我把它們稱為「歐洲十國游」型和「玄奘西行」型。
之前我說過， MAC 地址是一個區域網內才有效的地址。因而，MAC 地址只要過網關，就必定會改變，因為已經換了區域網 。
兩者主要的區別在於 IP 地址是否改變。不改變 IP 地址的網關，我們稱為 轉發網關 ；改變 IP 地址的網關，我們稱為 NAT 網關 。
網關總結：
路由分靜態路由和動態路由，靜態路由可以配置復雜的策略路由，控制轉發策略；
動態路由主流演算法有兩種， 距離矢量演算法 和 鏈路狀態演算法 。
距離矢量路由（distance vector routing）。它是基於 Bellman-Ford 演算法的。
這種演算法的基本思路是，每個路由器都保存一個路由表，包含多行，每行對應網路中的一個路由器，每一行包含兩部分信息，一個是要到目標路由器，從那條線出去，另一個是到目標路由器的距離。
由此可以看出，每個路由器都是知道全局信息的。那這個信息如何更新呢？每個路由器都知道自己和鄰居之間的距離，每過幾秒，每個路由器都將自己所知的到達所有的路由器的距離告知鄰居，每個路由器也能從鄰居那裡得到相似的信息。
每個路由器根據新收集的信息，計算和其他路由器的距離，比如自己的一個鄰居距離目標路由器的距離是 M，而自己距離鄰居是 x，則自己距離目標路由器是 x+M。
這種演算法存在的問題：
第一個問題：好消息傳得快，壞消息傳得慢。
第二個問題：每次發送的時候，要發送整個全局路由表。
所以上面的兩個問題，限制了距離矢量路由的網路規模。
鏈路狀態路由（link state routing），基於 Dijkstra 演算法。
這種演算法的基本思路是：當一個路由器啟動的時候，首先是發現鄰居，向鄰居 say hello，鄰居都回復。然後計算和鄰居的距離，發送一個 echo，要求馬上返回，除以二就是距離。然後將自己和鄰居之間的鏈路狀態包廣播出去，發送到整個網路的每個路由器。這樣每個路由器都能夠收到它和鄰居之間的關系的信息。因而，每個路由器都能在自己本地構建一個完整的圖，然後針對這個圖使用 Dijkstra 演算法，找到兩點之間的最短路徑。
不像距離距離矢量路由協議那樣，更新時發送整個路由表。鏈路狀態路由協議只廣播更新的或改變的網路拓撲，這使得更新信息更小，節省了帶寬和 CPU 利用率。而且一旦一個路由器掛了，它的鄰居都會廣播這個消息，可以使得壞消息迅速收斂。
基於兩種演算法產生兩種協議，BGP 協議和 OSPF 協議。
OSPF（Open Shortest Path First，開放式最短路徑優先） 就是這樣一個基於鏈路狀態路由協議，廣泛應用在數據中心中的協議。由於主要用在數據中心內部，用於路由決策，因而稱為 內部網關協議（Interior Gateway Protocol，簡稱 IGP） 。
內部網關協議的重點就是找到最短的路徑。在一個組織內部，路徑最短往往最優。當然有時候 OSPF 可以發現多個最短的路徑，可以在這多個路徑中進行負載均衡，這常常被稱為 等價路由 。
但是外網的路由協議，也即國家之間的，又有所不同。我們稱為 外網路由協議（Border Gateway Protocol，簡稱 BGP） 。
在網路世界，這一個個國家成為自治系統 AS（Autonomous System）。自治系統分幾種類型。
每個自治系統都有邊界路由器，通過它和外面的世界建立聯系。
BGP 又分為兩類， eBGP 和 iBGP 。自治系統間，邊界路由器之間使用 eBGP 廣播路由。內部網路也需要訪問其他的自治系統。邊界路由器如何將 BGP 學習到的路由導入到內部網路呢？就是通過運行 iBGP，使得內部的路由器能夠找到到達外網目的地的最好的邊界路由器。
BGP 協議使用的演算法是 路徑矢量路由協議 （path-vector protocol）。它是距離矢量路由協議的升級版。
前面說了距離矢量路由協議的缺點。其中一個是收斂慢。在 BGP 裡面，除了下一跳 hop 之外，還包括了自治系統 AS 的路徑，從而可以避免壞消息傳得慢的問題，也即上面所描述的，B 知道 C 原來能夠到達 A，是因為通過自己，一旦自己都到達不了 A 了，就不用假設 C 還能到達 A 了。
另外，在路徑中將一個自治系統看成一個整體，不區分自治系統內部的路由器，這樣自治系統的數目是非常有限的。就像大家都能記住出去玩，從中國出發先到韓國然後到日本，只要不計算細到具體哪一站，就算是發送全局信息，也是沒有問題的。
參考：
極客時間-趣談網路協議
極客時間-趣談網路協議
極客時間-趣談網路協議
極客時間-趣談網路協議-網關
㈦ 計算機網路通訊簡答題：擴散路由演算法原理
距離矢量演算法是向相鄰節點交換自己的路由信息，每次收到新的路由信息都需要進行計算以更新路由表，收斂速度較慢；鏈路狀態演算法是向全網節點宣告自己的鏈路狀態信息，使用洪泛的方式擴散，不需要計算直接轉發信息，收斂速度較快，但需要較大的存儲空間來記錄所有節點信息。
㈧ 計算機網路自學筆記：選路演算法
網路層必須確定從發送方到接收方分組所經過的路徑。選路就是在網路中的路由器里的給某個數據報確定好路徑(即路由)。
一 台主機通常直接與一台路由器相連接，該路由器即為該主機的默認路由器，又稱為該主機的默認網關。 每當某主機向外部網路發送一個分組時，該分組都被傳送給它的默認網關。
如果將源主機的默認網關稱為源路由器,把目的主機的默認網關稱為目的路由器。為一個分組從源主機到目的主機選路的問題於 是可歸結為從源路由器到目的路由器的選路問題。
選路演算法的目標很簡單:給定一組路由器以及連接路由器的鏈路，選路演算法要找到一條從源路由器到目的路由器的最好路徑，通常一條好路徑是指具有最低費用的路徑。
圖 G=(N，E)是一個 N 個節點和 E 條邊的集合，其中每條邊是來自 N 的一對節點。在網 絡選路的環境中，節點表示路由器，這是做出分組轉發決定的節點，連接節點的邊表示路由 器之間的物理鏈路。
一條邊有一個值表示它的費用。通常一條邊的費用可反映出對應鏈路的物理長度、鏈路速度或與該鏈路相關的費用。
對於 E 中的任一條邊(xy)可以用 c(xy )表示節點 x 和 y 間邊的費用。一般考慮的都是無向 圖，因此邊(xy)與邊(y x)是相同的並且開銷相等。節點 y 也被稱為節點 x 的鄰居。
在圖中為各條邊指派了費用後，選路演算法的目標自然是找出從源到目的間的最低費用路徑。圖 G=(N，E)中的一條路徑(Path)是一個節點的序列，使得每一對以(x1,x2)， (x2,x3)，…，是 E 中的邊。路徑的費用是沿著路徑所有邊費用的總和。
從廣義上來說，我們對 選路演算法分類的一種方法就是根據該演算法是全局性還是分布式來區分的。
.全局選路演算法： 用完整的、全局性的網路信息來計算從源到目的之間的最低費用路徑。
實際上， 具有全局狀態信息的演算法常被稱作鏈路狀態 LS 演算法， 因為該演算法必須知道網路中每條鏈路的費用。
.分布式選路演算法： 以迭代的、分布式的方式計算出最低費用路徑。通過迭代計算並與相鄰節點交換信息，逐漸計算出到達某目的節點或一組目的節點的最低費用路徑。
DV 演算法是分布式選路演算法， 因為每個節點維護到網路中的所有其他節點的費用(距離)估計的矢量。
選路演算法的第二種廣義分類方法是根據演算法是靜態的還是動態的來分類。
一： 鏈路狀態選路演算法 LS
在鏈路狀態演算法中，通過讓每個節點向所有其他路由器廣播鏈路狀態分組， 每個鏈路狀態分組包含它所連接的鏈路的特徵和費用， 從而網路中每個節點都建立了關於整個網路的拓撲。
Dijkstra 演算法計算從源節點到網路中所有其他節點的最低費用路徑.
Dijkstra 演算法是迭代演算法，經演算法的第 k 次迭代後，可知道到 k 個目的節點的最低費用路徑。
定義下列記號:
D(V)隨著演算法進行本次迭代，從源節點到目的節點的最低費用路徑的費用。
P(v)從源節點到目的節點 v 沿著當前最低費用路徑的前一節點(，的鄰居)。
N`節點子集；如果從源節點到目的節點 v 的最低費用路徑已找到，那麼 v 在 N`中。
Dijkstra 全局選路演算法由一個初始化步驟和循環組成。循環執行的次數與網路中的節點個數相同。在結束時，演算法會計算出從源節點 u 到網路中每個其他節點的最短路徑。
考慮圖中的網路，計算從 u 到所有可能目的地的最低費用路徑。
.在初始化階段 ，從 u 到與其直接相連的鄰居 v、x、w 的當前已知最低費用路徑分別初始化為 2，1 和 5。到 y 與 z 的費用被設為無窮大，因為它們不直接與 u 連接。
.在第一次迭代時， 需要檢查那些還未加到集合 N`中的節點，找出在前一次迭代結束時具有最低費用的節點。那個節點是 x 其費用是 1，因此 x 被加到集合 N`中。然後更新所有節點的 D(v)，產生下表中第 2 行(步驟)所示的結果。到 v 的路徑費用未變。經過節點 x 到 w 的 路徑的費用被確定為 4。因此沿從 u 開始的最短路徑到 w 的前一個節點被設為 x。類似地， 到 y 經過 x 的費用被計算為 2，且該表項也被更新。
.在第二次迭代時 ，節點 v 與 y 被發現具有最低費用路徑 2。任意選擇將 y 加到集合 N` 中，使得 N』中含有 u、x 和 y。通過更新，產生如表中第 3 行所示的結果。
.以此類推…
當 LS 演算法結束時，對於每個節點都得到從源節點沿著它的最低費用路徑的前繼節點， 對於每個前繼節點，又有它的前繼節點，按照此方式可以構建從源節點到所有目的節點的完 整路徑。
根據從 u 出發的最短路徑，可以構建一個節點(如節點 u)的轉發表。
二 距離矢量選路演算法 DV
LS 演算法是一種使用全局信息的演算法，而距離矢量演算法是一種迭代的、非同步的和分布式的演算法。
Bellman-Ford 方程：
設 dx(y)是從節點 x 到節點 y 的最低費用路徑的費用，則有 dx(y) = min {c(x,v) + dv(y) }
PS： 方程中的 min，是指取遍 x 的所有鄰居。
Bellman-Ford 方程含義相當直觀，意思是從 x 節點出發到 y 的最低費用路徑肯定經過 x 的某個鄰居，而且 x 到這個鄰居的費用加上這個鄰居到達目的節點 y 費用之和在所有路徑 中其總費用是最小的。 實際上，從 x 到 v 遍歷之後，如果取從 v 到 y 的最低費用路徑，該路 徑費用將是 c(x,v)+ dv(y)。因此必須從遍歷某些鄰居 v 開始，從 x 到 y 的最低費用是對所有鄰 居的 c(x,v)+dv(y)的最小值。
在該 DV 演算法中，當節點 x 看到它的直接相連的鏈路費用變化，或從某個鄰居接收到一 個距離矢量的更新時，就根據 Bellman-Ford 方程更新其距離矢量表。
三 LS 與 DV 選路演算法的比較
DV 和 LS 演算法採用不同的方法來解決計算選路問題。
在 DV 演算法中，每個節點僅與它的直接相連鄰居交換信息，但它為它的鄰居提供了從其 自己到網路中(它所知道的)所有其他節點的最低費用估計。
在 LS 演算法中，每個節點(經廣播)與所有其他節點交換信息，但它僅告訴它們與它直接 相連鏈路的費用。
·報文復雜性：
LS 演算法要求每個節點都知道網路中每條鏈路的費用，需要發送 O(nE)個消息。
DV 演算法要求在每次迭代時，在兩個直接相連鄰居之間交換報文，演算法收斂所需的時間 依賴於許多因素。當鏈路費用改變時，DV 演算法僅當在會導致該節點的最低費用路徑發生改 變時，才傳播已改變的鏈路費用。
·收效速度：
DV演算法收斂較慢，且在收斂時會遇到選路環路。DV演算法還會遭受到計數到無窮的問題。
•健壯性： 在 LS 演算法中，如果一台路由器發生故障、或受到破壞，路由器會向其連接的鏈路廣播 不正確費用，導致整個網路的錯誤。
在 Dv 演算法下， 每次迭代時，其中一個節點的計算結果會傳遞給它的鄰居，然後在下次迭代時再間接地傳遞給鄰居的鄰居。在這種情況下，DV 演算法中一個不正確的計算結果也會擴散到整個網路。
四.層次選路
兩個原因導致層次的選路策略：
•規模： 隨著路由器數目增長，選路信息的計算、存儲及通信的開銷逐漸增高。
•管理自治： 一般來說，一個單位都會要求按自己的意願運行路由器(如運行其選擇的某 種選路演算法)，或對外部隱藏其內部網路的細節。
層次的選路策略是通過將路由器劃分成自治系統 AS 來實施的。
每個 AS 由一組通常在相同管理控制下的路由器組成(例如由相同的 ISP 運營或屬於相同 的公司網路)。在相同的 AS 內的路由器都全部運行同樣的選路演算法。
在一個自治系統內運行的選路演算法叫做自治系統內部選路協議。 在一個 AS 邊緣的一台 或多台路由器，來負責向本 AS 之外的目的地轉發分組，這些路由器被稱為網關路由器
在各 AS 之間，AS 運行相同的自治系統間選路協議。