三樓的介紹（Network Layer - IP)

三樓是 Network Layer，網際網路上主要的角色是 IP (Internet Protocol)，但是其他和 IP 相關的角色也很重要，包括 ICMP、DHCP、NAT、UPnP，以及路由的協定 OSPF 和 BGP 等等。

四樓 Transport Layer 主要提供給應用層的服務是 Process-to-Process Communication，而四樓主要是利用三樓所提供的 Host-to-Host Communication 功能。

也就是說，四樓讓程序間的通訊得以實踐，而三樓讓電腦設備間的通訊得以實踐。

三樓主要提供的服務有兩個：

• Forwarding
• Routing

Forwarding 是指封包到了一個路由器上，路由器將封包往對應的輸出網路界面送的過程。Routing 則是指一個封包要從設備 A，通過超過一個的子網域（例如網際網路），最後傳到設備 B 的過程。也可以說 Forwarding 只關聯到一台路由器自己本身，Routing 則包含了整個大網路中，封包路徑上所有的路由器要通力合作，才能完成的演算法。

三樓絕對可以說是網際網路的骨幹，理解這些核心概念，應該是挺有意義的。

IP 位址 (IP Address)

IP 協定目前有兩個主要的版本，Version 4 和 Version 6，本文撰寫時，主流依然是 IPv4，我們先來討論它，晚一點再來看一下 IPv6。

IPv4 的位址為 32 位元的數值，常用的表示法是 xxx.xxx.xxx.xxx，也就是四個數字，中間用三個點隔開，每個數字介在 0 到 255 之間，也就是 8 bits 的長度，四個數字因此就是 32 bits。不管表示法為何，骨子裡，IP 位址就是一個 32 位元數值。

起初 1981 年 IP 在制定時，IP 位址是有分類別的，總共有 5 類，分別如下：

• Class A 起始IP: 0.0.0.0；   結束IP: 127.255.255.255；  大小: 2^24
• Class B 起始IP: 128.0.0.0； 結束IP: 191.255.255.255；  大小: 2^16
• Class C 起始IP: 192.0.0.0； 結束IP: 223.255.255.255；  大小: 2^8
• Class D 起始IP: 224.0.0.0； 結束IP: 239.255.255.255
• Class E 起始IP: 240.0.0.0； 結束IP: 255.255.255.255

比較常見的是 Class B 和 Class C 大小的網路，所以你現在還會聽到有些人說：「這個網路是 Class C 的網路」類似這樣的說詞，這說詞不完全正確，因為通常說的人只是單純指網路的大小而言，實際分 Class 的網路還需要考慮起始 IP 位址和結束 IP 位址是否符合。例如說這個辦公室的網路大小是 Class C，也就是網路的 IP 數量有 2^8 = 256 個。因為到 1993 年後直到現今，IP 分配的方法已經不再使用分 Class 的方式來配置，而是用稱為 Classless Inter-Domain Routing (CIDR) 的方式來配置，只是到如今 Class 的說法還會被拿來形容網路的大小而已。

CIDR 位址是用 xxx.xxx.xxx.xxx/prefix 來表示一個子網域的所有位址，例如 192.168.0.0/24 可能代表一個小型辦公室的子網域位址，Prefix 24 代表 32 位元的數值中，前面 24 位元都固定，只有後面剩下來的（32 - 24 = 8 位元）才允許變動，而允許變動的部份，也就是這個子網域內，所有設備可以擁有的 IP 位址，例如：
192.168.0.1
192.168.0.2
...
192.168.0.255

也有人稱 Prefix 為 Net ID，稱後面剩下來的部份 (32 - Prefix)，以上例而言為 8，為 Host ID。在一個子網域裡面，設備的 Net ID 都相同，只有 Host ID 會不同。

另外有一個名詞叫做 Netmask，其實就是代表該子網域的 Prefix，只是用 IP 位址的方式表示而已，例如 Prefix 24 的子網域，其 Netmask 為 255.255.255.0。你可以把 Netmask 想像為一個 32 bits 數值，其從 most significant bit 開始算起的 24 個 bits 都是 1，其餘為 0，則可得 255.255.255.0。同樣道理，如果 Prefix 是 16，則 Netmask 為 255.255.0.0。

另外有幾個特殊的 CIDR 位址，包括 127.0.0.1/8 代表本機端，也就是說這個 CIDR 位址會傳送資料到你自己的電腦。192.168.0.0/16、172.16.0.0/12，以及 10.0.0.0/8 這三個 CIDR 位址保留給為私有網路（Private Network）使用。關於私有網路，我們等會看 NAT 的時候會提到它。

三樓的廣播

通常一個子網域內都會有一個廣播位址，該位址會保留給廣播功能使用，也就是當某設備要廣播封包給該子網域內的所有人的時候，就會使用廣播位址。

每個子網域的廣播位址算法為 OR(NOT(Netmask), CIDR)，例如 192.168.0.0/24 的網域，欲求其廣播位址，先對 255.255.255.0 做 NOT 運算，得到 0.0.0.255，再將 0.0.0.255 與 192.168.0.0 做 OR 運算，得到 192.168.0.255，這就是該子網域的廣播位址。以上運算都是 Bitwise 運算。

還有一個特殊的 IP 位址也是廣播位址，它是 255.255.255.255，它代表了「這個子網域」，路由器看到這個封包，便不會路由出所在的子網域。

實務上，三樓的廣播通常只允許發生在路由協定裡面，因此我們無法透過指定目的 IP 為某個子網域的廣播位址，而妄想可以將封包傳遞給該子網域的每一台設備。

一般我們碰到的三樓廣播，其實都是配合二樓 Data Link Layer 的廣播來運作，這種情況下，IP 位址都會是 255.255.255.255，路由器不會理它，是透過同時將二樓的 MAC 位址設定為 FF:FF:FF:FF:FF:FF 才能夠在「這個子網域」裡頭達到廣播的效果。

Forwarding

當路由器收到來自某個網路介面卡的封包時，它會查看該封包的 IP 表頭，取得表頭中的目的地 IP 資訊，並且對照自己的路由表 (Routing Table/Forwarding Table)，決定將封包送網哪一個輸出介面卡。

一個路由表的例子如下：
Kernel IP routing table
Destination     Gateway         Genmask         Flags   MSS Window  irtt Iface
0.0.0.0         0.0.0.0         0.0.0.0         U         0 0          0 ppp0
168.95.98.254   0.0.0.0         255.255.255.255 UH        0 0          0 ppp0
192.168.56.0    0.0.0.0         255.255.255.0   U         0 0          0 vboxnet0
192.168.57.0    0.0.0.0         255.255.255.0   U         0 0          0 vboxnet1

我們只要看 Destination、Genmask，以及 Iface 這三個欄位就可以了。Genmask 欄位就等同於 Netmask，也等同於網域的 Prefix。當一個封包進來的時候，路由器會看該封包的目的地 IP，將此 IP 和 Genmask 做 Bitwise AND 運算，如果算出來等於 Destination，就會往該 Iface 送。如果有多個符合的項目，則會往最大的 Prefix 那裡送，也就是往最多 1（或說最多 255，以上表為例）的 Genmask 那個項目的 Iface 送。

通常 Genmask 為 0.0.0.0 的都為預設路由，因為 AND 結果出來一定為全 0，所以一定符合，但是 Prefix 一定為最小值 0。

實作上，路由器會透過將路由表建成二元搜尋樹，或者其他的資料結構，來加速路由速度。例如將 Genmask 和 Destination 先 Bitwise AND，然後將 32 bits 中，從 least significant bit 開始算起的連續 0 去掉，得到一些長度不一的 01 字串 (或看作 bit vectors)，將這些字串從 most significant bit 開始做成二元搜尋樹。當封包進來時，將封包的目的 IP 位址拿來在搜尋樹比對，選擇最長的批配，即為輸出界面。

總結一下，Forwarding 就是路由器將封包對照路由表轉送到對應的網路界面的功能。

一般電腦在三樓的設定，主要是設定 IP 位址、Netmask，以及閘道器 (Gateway)，閘道器就是該子網域連結到其他子網域，或者說連結到外部網路的第一台路由器。

設定的方法有手動設定，也有常見的動態 IP 設定，也就是我們接下來要介紹的 DHCP。

DHCP (Dynamic Host Configuration Protocol)

DHCP 是區域網路內相當常用的協定，以下只介紹概念，請看附圖：

這是 Wireshark 抓取 DHCP 的四個封包，我們假設 Server-Client 架構，網路內有一個 DHCP Server，當有 Client 連上網路的時候，Client 一開始沒有任何 IP 設定，於是 Client 送出 DHCP Discover 封包，你可以想像，Client 根本不知道這個封包應該送給誰，所以這個封包的目的 IP 位址為廣播位址 255.255.255.255，來源 IP 位址為 0.0.0.0，圖上沒有顯示，但實際上 DHCP 是走 UDP 協定，因此有來源通訊埠和目的通訊埠兩項資料，來源 Port 是 68，目的 Port 是 67。

第二個封包 DHCP Offer 是 Server 送回給 Client，當 Server 收到前一個廣播封包之後，Server 會回應 Offer 給 Client，其中包含了給 Client 的 IP 設定、Netmask、以及 Gateway 等相關資訊，另外也包含了 DNS 伺服器等資訊。Client 收到 Offer 後，並不代表 Client 一定會採用，Client 如果願意接下這個 Offer，就送出第三個封包 DHCP Request，代表它想要採用，此時此刻 Client 還沒有正式得到 IP 的設定資訊，所以你可以看到 Client 還是使用廣播位址。

Server 接著送出第四個封包 DHCP ACK，其中也包含了租借時間 (Lease Time)，允許 Client 使用這些 IP 多少時間，通常從幾個小時到幾天都有可能。

就是因為有 DHCP，所以無線基地台才可以如此順利的運作，因為行動裝置到哪裡，就只要使用 DHCP 取得該處的 IP 即可上網，DHCP 是隨插即用的協定，相當方便。

從安全的角度來看，DHCP 封包許多資料是廣播的，要監聽或欺騙都是有可能的，便利性與安全性常常是天平的兩端。

NAT (Network Address Translation)

IPv4 的位址只有 32 位元，最多也只有四十億左右的 IP 位址可以使用，在不夠用的前提下，除了使用新版的  IPv6 以外，另一項技術為此而生，就是 NAT。

NAT 運用私有網路的概念，想像一個 SOHO 族，跟中華電信租用了一個 IP，姑且說它是 1.1.1.1，SOHO 族家裡有三台電腦要上網，連印表機和網路硬碟在內，總共有五個裝置要上網，難道 SOHO 族因此要再去租用四個 IP 嗎？

靠著一台介在外部網際網路和家中所有裝置中間的 NAT 裝置，就可以解決這個問題了。一般家用的 NAT 裝置被稱為 IP 分享器。在它上面可以設定對外網際網路是從中華電信租來的 IP，對內可以設定子網域為 192.168.0.0/24，這只是舉例，可以使用任何私有網路 (Private Network) 的子網域，包括 192.168.0.0/16、172.16.0.0/12，以及 10.0.0.0/8 這些網域範圍內的子網域都可以使用。

NAT 裝置通常會透過 DHCP 自動分配 IP 位址給內部的上網裝置，當上網裝置要連線出去的時候，NAT 裝置會根據網路四樓的資訊 {來源 IP、來源 Port、目的 IP、目的 Port} 來建立對應表，將其內部私有 IP 換成自身的對外 IP，並與外界建立連線，當外界傳回資料時，憑藉著這個對應表，將目的 IP 再換成內部的私有 IP，並且傳遞給原先的電腦裝置。

對外界來說，看不到 NAT 裝置內部的網路，只看到 NAT 裝置本身，對內部來說，連線到外界也絲毫沒有阻礙，這就是 NAT 的好處。

NAT 裝置因為必須轉換 IP 位址，所以通常必須是閘道器 (Gateway)，也就是子網域連外的第一個路由器。也就是說，NAT 裝置通常會是路由器，且通常都支援 DHCP。

有一些人反對 NAT 的使用，反對的主要理由可能如下：
1. 四樓的 Port 資訊目的是為了程序間的通訊 (Process-to-Process Communication)，不應該被拿來達成設備間的通訊 (Host-to-Host Communication)。
2. 路由器應該乖乖待在三樓，不應該偷看四樓的資料。
3. NAT 裝置一定會介入，每一條內部網路端點與外部網路端點的所有通訊，違反點對點直接通訊的原則。
4. 我們應該使用 IPv6 來解決 IP 位址不夠的問題。

此外，因為 NAT 的緣故，所以某些 P2P (Peer to Peer) 軟體也無法直接連線於內部網路，因為內部網路是私有 IP，無法透過網際網路路由到任何私有 IP，因此當 P2P 軟體想要主動連線到內部時，就會被 NAT 擋在外面，NAT 裝置內的通訊對照表，通常是由內部啟動連線才開始建立的。解決這個 P2P 問題的辦法是透過反向連線，或是 UPnP，或者是第三方 Relay。這樣的 P2P 問題，我們常常稱呼為 NAT Traversal 問題。

UPnP (Universal Plug and Play)

UPnP 其實是第七樓的東西，它原則上是由內部私有網路的電腦啟動，和該子網域的 NAT 裝置說：「請幫我事先開一個對照規則，讓某某外部 IP 和通訊埠，可以對應到我的某某內部 IP 和通訊埠。」當然前提是 NAT 裝置和內部該電腦的應用軟體都要支援 UPnP 才行。

透過 UPnP，可以解決 P2P 無法直接與內部網路建立連線的問題。

IPv4 表頭

IPv4 的封包表頭最小為 20 個位元組，如下圖：

00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
Version				IHL				Differentiated Services								Total length
Identification																Flags			Fragment offset
TTL								Protocol								Header checksum
Source IP address
Destination IP address
Options and padding :::

(圖片來源：http://www.networksorcery.com/enp/protocol/ip.htm)

只挑我覺得重要的介紹，值得關注的是第二行的 Identification, Flags, Fragment offset，以及第三行的 TTL 和 Protocol。

通常 Options 欄位為空，所以 IPv4 表頭常常為 20 bytes。

TTL 是 Time To Live 欄位，一般常見值為 64、128，或者 256，封包在每經過 1 個路由器，這個值就會減一，避免封包無止盡的在網路上路由不到最後目的地。

Protocol 欄位註明上層的協定為何，可以參考 Linux 系統內的 /etc/protocols 這個檔案，常見的值有 6、17，和 1，分別代表 TCP、UDP，以及 ICMP。ICMP 雖然也是三樓的成員，但是它實際上是被封裝在 IP 封包之內。

Identification, Flags, 和 Fragment offset 是實作封包切割的功能。通常網路受限於硬體，有一個最大傳輸單位 Maximum Transmission Unit (MTU)，例如 Ethernet 硬體的 MTU 為 1500 bytes，如果封包最大值超過這個值，就必須要進行封包切割。

想像一個情況，當一個路由器接收到從某網路界面來的封包，大小為 1500 bytes，然後路由器需要將封包轉送到另一對外網路界面，但該網路界面的 MTU 只有 500 bytes，這個時候該怎麼辦呢？答案就是路由器會進行封包的切割動作。一般的情況下，切割動作都是在路由器中完成，所有的還原工作都在最後接收資料的端點設備完成。

Identification 就是切割封包的 ID，舉例來說，假設有一 IP 封包大小為 4000 bytes，扣掉 IP 表頭 20 bytes，內部資料還有 3980 bytes，假設初始 IP 封包的 ID 為 909，則該封包會被切割成以下三個封包：
ID: 909, Flags: MF bit on, Fragment offset: 0, Length: 1480+20 bytes
ID: 909, Flags: MF bit on, Fragment offset: 185, Length: 1480+20 bytes
ID: 909, Flags: MF bit off, Fragment offset: 370, Length: 1020+20 bytes

三個封包的 ID 都會一樣，Flags 裡面有關鍵的兩個 bits，一個是 MF (More Fragments)，代表「我後面還有人！」，所以前兩個封包都要設為 MF bit on，最後一個封包設為 off，第二個封包 offset 數值為 185，其值需要乘以 8，185 * 8 = 1480，因此第二個封包會從 offset 1480 byte 的位置繼續往下接，同理第三個封包 offset 為 370 (370 * 8 = 2960)，然後加上第三個封包的 1020 bytes，總共是 3980 bytes。

Flags 裡面第二個關鍵的 bit 是 DF (Don't Fragment)，代表註明此封包不要切割。如果註明封包不要切割 (DF bit on)，但是還是碰到上述的狀況，這個時候路由器因為不能切割，就會傳送 ICMP 封包給來源 IP，且 ICMP Type = 3 Code = 4，代表 Destination Unreachable (Datagram is too big, and DF is on)。

IPv6 表頭

IPv6 的表頭並不比 IPv4 複雜，事實上還精簡了幾個欄位，如下圖：

00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
Version				Traffic Class								Flow Label
Payload Length																Next Header								Hop Limit
Source address :::
Destination address :::
Data :::

(圖片來源：http://www.networksorcery.com/enp/protocol/ipv6.htm)

IPv6 的表頭固定為 40 bytes，Source IP address 和 Dest IP address 各佔 16 bytes，然後兩行欄位，一行 4 bytes，所以共 40 bytes。沒有 Options 了。

從最前面相同的 Version 欄位可以判斷此封包是 IPv4 或 IPv6。
Traffic Class 類似 IPv4 的 Differentiated Services，用來註明一些如即使影音，或者有特殊優先順序需求的封包。

IPv6 和 IPv4 的差異如下：
1. IP 位址變大
2. 固定長度為 40 bytes。
3. 加入了 Flow 的概念，可以設定某些應用是某些 Flow，因此路由器可以優先處理這同一個 Flow 的系列封包。
4. 不允許封包切割了，所有沒有 Fragment 相關的欄位。
5. 沒有 Checksum，減輕路由器負擔，因為 IPv4 的 TTL 每次減一都要重新算 Checksum，都是路由器的額外負擔。
6. 沒有 Options 或 Protocol，IPv6 透過 Next Head 指派下一個表頭的類別，例如 TCP 或 UDP，當然還可以繼續指定 IPv6 表頭為 Next Head，以此達到 Options 的效果。

IPv4 到 IPv6

嘆息一下，這個轉換超級久的，看起來還要好幾年才會慢慢轉過去（或者不會？！）。

基本上有兩種方式轉換，一種是 Dual Stack，另一種是 Tunnelling，以下只介紹觀念。

Dual Stack 就是支援 IPv6 的機器，也同時支援 IPv4，透過 DNS 來判別欲連線的目的端是否支援 IPv6，例如詢問 DNS AAAA 紀錄，如果對方有 IPv6，則可使用 IPv6。

但是有可能在路由的過程中，會經過只支援 IPv4 的路由器，這個時候可以透過 Tunnelling 的技術，Tunnel 就是在支持 IPv6 的路由器，要傳給下一個路由器的時候，預先知道該路由器是否支援 IPv6，如果不，就將原先的 IPv6 封包裝在 IPv4 封包裡頭，等到了對方網路，對方電腦或者對方外部的路由器，將其解包，再把原先的 IPv6 封包原封不動的繼續傳過去。被包在 IPv4 的那一段路徑，就類似隧道一樣，因此叫 Tunnelling。

ICMP (Internet Control Message Protocol)

ICMP 基本的功能是用來傳遞三樓除錯和管理的訊息，我們將只介紹觀念。

ICMP 封包中，關鍵的是兩個欄位，Type 和 Code，不同的 ICMP Type 代表不同的類型訊息，常見的 Type 有：

• 3: Destination unreachable
• 8: Echo request
• 0: Echo reply
• 11: TTL expired

其中 Type 3 還透過另一個欄位 Code 更細分原因，例如常見的 Code 有：

• 1: Host unreachable
• 3: Port unreachable
• 4: Packet too big, and DF is on

ICMP 最常見的應用軟體有兩個，一個是 ping，另一個是 traceroute。ping 透過送出 ICMP Type 8 封包，並且接收方傳回 Type 0 封包，傳送方以此計算封包中間的 Round-Time Trip 時間有多少，並且確認從傳送方到接收方的 IP 封包是否可被正確路由，以及接收方是否有回應。

traceroute 透過傳送 n 個封包，第 1 個封包 TTL = 1，第 2 個封包 TTL = 2，依此類推，因為 TTL 每經過一個路由器就會減一，當減到 0 的時候，路由器就會發回來 Type 11 的封包，從路由器發回來的封包，我們可以得到路由器的來源 IP，因此透過這種手法，我們可以取得一個封包路徑中，所有路由器的 IP 位址，前提是路由器都有乖乖地回應 ICMP Type 11，有些路由器會身兼防火牆功能，完全阻斷 ICMP 封包，或者未開啟通訊埠的封包。traceroute 傳送的 n 個封包，每一個封包的目的 IP 都是一樣的，都是最終的接收方。

traceroute 通常是使用 UDP 協定，並且軟體會選擇一個值較高的目的通訊埠，期待所選擇的通訊埠是對象接收方所沒有開啟監聽的通訊埠。這樣一來，當傳送方收到 ICMP Type 3 Code 3 的封包，就代表傳到底了，這就是我們的目的對象所傳來的 ICMP，否則路由器應該要傳送 Type 11 才對。

也有的 traceroute 軟體版本支援 TCP 協定，原理類似，只是這個時候軟體會刻意選擇一個比較常見的目的通訊埠，這裡和 UDP 不同，這裡的目的是為了要通過路徑中間的防火牆，期待選擇一個防火牆會讓行的目的通訊埠。當傳到底的時候，接收方也不再是傳 Type 3 回來，而是傳 SYN-ACK 回來（因為我們用 TCP 是傳 SYN 過去），這時只要傳個 TCP RST 封包過去，取消連線即可。

IP 的協定比較繁雜，以上所介紹的都是常用到的 IP 技術觀念，接下來我們要來探索一下 IP 所提供的另一個服務 Routing。

Routing

Routing 服務的目的在於使網際網路可以連線互通，使網網互連，因此你可以知道，路由器扮演這網網互連的角色，如果沒有這項服務，整個網際網路將不存在。

Routing 主要是透過路由器彼此的互動，來修改路由器內的路由表，你可以想像路由器內部有兩隻程式，一隻負責修改正確的路由表，提供 Routing 服務，另一隻負責照表操課，有封包進來，就照表轉送封包，提供 Forwarding 的服務。

路由 (Routing) 除了手動設定以外，主要是依靠路由演算法來自動化所有過程。

路由演算法主要有兩種，一種是 Link State 演算法，另一種是 Distance Vector 演算法。目前實務上使用的都是這兩種演算法加上一些變形。

你可以知道，如果有任何協定牽涉到演算法，那個協定一定相對複雜許多，我這裡說的演算法，是指特別被提出在演算法領域討論的著名演算法，例如 Shortest Path 演算法。廣義來說，所有做事的規則和順序組合，都可以說是演算法。

我沒有機會實際操作 OSPF 或 BGP 等路由協定，只能就理論上來介紹。

Link State 演算法

Link State 演算法是透過 Dijkstra's Algorithm 來計算最短路徑，它把整個網路對應到圖學上，路由器就是「點」，路由器和路由器之間的連線就是「線」，所有的點和線的集合表示一個「圖」，每條線有權重，代表通過該線所需的花費。這個演算法的前提是，整個網路的所有路由器必須擁有全部的「圖」資訊（點、線、以及線的花費）。

假設以下變數：
N：所有點的集合
C(x, v)：點 x 到點 v 的花費，x 與 v 相鄰。
u：本身點，也就是起始點。
D(v)：代表從點 u 到點 v 的路徑整體花費。
P(v)：代表從點 u 到點 v 的最短路徑中，離 v 最近的那個點，也就是 v 的鄰居。
N'：當前已經算得最短路徑的點所成的集合。

演算法一直跑到當 N' = N 的時候，即完成。

演算法如下：
Initialization:
    N' = {u}
    For every vertex v in N,
        If v is a neighbour of u, D(v) = C(u, v), P(v) = u
        Else, D(v) = ∞ (infinity)

Loop until N' == N:
    Find a vertex w not in N', and D(w) is the minimum
    Add w to N'
    For each neighbour vertex v of w, and v is not in N'
        If D(w) + C(w, v) < D(v), D(v) = D(w) + C(w, v), and P(v) = w

這個演算法又簡潔又有效率。從效率上來看，關鍵在於迴圈，起始的 Initialization 跑了 N 次，第二個迴圈 Loop 會跑 N - 1 次，而內部的搜尋 w 動作第一次跑 N - 1 個點，第二次跑 N - 2 個點，依此類推，最後只要跑 1 個點，所以所需時間為 (N-1)N/2，可推得整體時間耗費 O(N^2)。

Distance Vector 演算法

Distance Vector (DV) 是一個分散式的演算法，它不像 LS (Link State) 一樣，每個路由器都需要整體的全部資訊，DV 是一個透過和鄰居交換訊息得到的最佳解的演算法。

關鍵在於 Bellman-Ford Equation：
Du(y) = Minv { C(u, v) + Dv(y) }

其中，Dx(y) 代表從點 u 到點 y 的整體最小花費，Minv 代表針對所有 u 的鄰居點 v 做一個找最小值 (Minimum) 的運算，C(u, v) 代表點 u 到點 v 的花費。

這代表一件事：要求得點 u 到點 y 的最小花費，可以先在 u 所有鄰居中找到一個點 v，而點 v 到點 y 的花費加上點 u 到點 v 的花費是最小的。好吧，不知道這樣會不會容易理解一點？

演算法如下：
Initialization
    For each vertex y in N,
        If y is a neighbour of u, Du(y) = C(u, y)
        Else, Du(y) = ∞ (infinity)

Loop until forever
    Wait until (a link cost changed or a neighbour sent me its D)
    For each vertex y in N,
        Du(y) = Minv { C(u, v) + Dv(y) }
    If Du changed, send Du to all my neighbours

這個演算法會進入無窮迴圈中等待，神奇的是，如果沒有意外，一段時間後這個演算法會收斂 (Convergence)，然後每個路由器就擁有最短路徑資訊了！

DV 演算法的問題在於，當某路由器傳出錯誤的資訊時，可能會發生迴圈路由或 Count-to-infinity 問題，進而影響整個網路。而 LS 演算法當遇到路由器傳出錯誤資訊時，只會影響到和該路由器有關的路線而已。且你可以很明顯的看到，LS 一定會收斂，DV 則很難說。

但是 LS 需要每個點擁有全部的資訊，這一點在整個大網際網路裡，幾乎不可能作到。

Autonomous Systems (AS)

實際上，整個網際網路是透過上述兩種路由演算法組合使用，來達成路由的目的。基本觀念就是把網路分成許多的自主系統，在自主系統內透過 LS 來跑（也有些透過 DV），系統和系統彼此之間透過 DV 來跑。這樣的自主系統我們稱作 Autonomous Systems (AS)。

在 AS 內部，透過 Intra-AS Routing Protocol 來完成路由設定，AS 之間的溝通，就依靠 Inter-AS Routing Protocol 來完成。

AS 通常是以組織或公司為單位，例如一個 ISP公司本身自成為一個 AS，也可能一家公司會按照公司政策，將旗下單位分割成數個 ASs。

Open Shortest Path First (OSPF)

OSPF 協定主要使用 LS 演算法，因此你可以知道，它大多被歸類於 Intra-AS Routing Protocol，屬於 AS 內部在使用的協定。

OSPF 透過三樓的廣播來作到讓全部路由器取得整體拓樸資訊，值得注意的是，我們前面提過，三樓的廣播通常只有在路由協定裡面被使用，一般使用者常見的網路廣播都是二樓的廣播。

OSPF 提供幾個功能：
1. 資訊認證，這部份透過雜湊技術例如 MD5 來實作
2. 允許多條等值路徑，一般最短路徑演算法在找到一條最短路徑後，便會中止尋找其他路徑，OSPF 允許有多條最短路徑同時存在。
3. 支援 Multicast。
4. 支援階層式管理架構。

OSPF 內的階層觀念乃是這樣，首先整個網路可以分為幾個區域 (Area)，每個區域都有一個以上的區域邊界路由器，另外還有唯一一個特殊的骨幹區域 (Backbone)，此骨幹區域包含所有的邊界路由器（因此邊界路由器至少被同時兩個以上的區域包含著），透過這樣區域的架構，來實現階層式的管理。

Border Gateway Protocol (BGP)

BGP 是扮演三樓最關鍵的角色，也就是 AS 之間的路由通訊。它類似 DV 演算法的作法，但是加入許多政策和管理的考慮，主要傳遞路由資訊給相關路由器，並且根據政策選擇最後的路徑。

在 BGP 中，主要的 AS 都有一個代號，稱為 Autonomous System Number (ASN)，ASN 就像 IP 位址一樣，是需要向國際組織 (ICANN) 或地方授權組織註冊的。

BGP 相當複雜，或許要有機會參與國際型 ISP 的核心工作，才有機會真的了解它。

Multicast

我們上述除了單點的傳輸以及廣播傳輸以外，尚未提及另外一種三樓可能有的傳輸方式，那就是 Multicast，它是透過 Internet Group Management Protocol (IGMP)，以及其他的 Multicast Routing Protocols 來實作。你可以想像 Multicast 是三樓的多方通話機制，有點像是虛擬的聊天室，透過支援 Multicast 的數台路由器，以及想加入聊天室的端點設備來組成一個多方通話空間。

IGMP 定義網路端點設備，與其閘道器（子網域內的路由器）之間的通訊，IGMP 有三種訊息，分別是 query、report，以及 leave，基本上是路由器會問它所連接的端點設備：「有人要加入這個群組嗎？」或是「加入這個群組的人還要繼續加入嗎？」，端點設備可以選擇加入、退出，或者是不理會而被自動退出。

Multicast Routing Protocols 基本上有兩種演算法，一種是中央集權式，一群路由器選出一個中央點之後，從中央點去建立一個共享的路由路徑，然後所有參與的路由器都透過此單一路由路徑來達成 Multicast 的功能。另一種是各自為政型，每個路由器自己想辦法解決，然後再與其它路由器溝通傳輸。

Multicast 的實際應用並不普及（別問我如何定義普及？），因此和它相關的網路安全議題也不多，我們在此只介紹概念。

到此，我們將三樓大致介紹完了，雖然多屬於概念性介紹，但是還算完整，和三樓有關的網路技術，應該比較常見的，都在我們的介紹之中了。