## ch3
### TCP congestion
TCP 傳送的流程大致如下：
- 傳送端一次性發送最多 cwnd 個字節的資料。
- 等待一個 RTT（往返時延，Round Trip Time），此期間接收端可能會回傳 ACK。
- 傳送端根據收到的 ACK，結合擁塞控制演算法，動態調整 cwnd 的大小，再傳送下一批資料

$TCP\,Rate$ ~~ $\frac{cwnd}{RTT}$

$LastByteSent−LastByteAcked≤cwnd$

### TCP slow start
傳輸速率（即擁塞窗口 cwnd 的大小）會以指數級增長，直到發生第一次的丟包事件

在連線開始時，cwnd 的初始值設定為 1 MSS（最大段長，Maximum Segment Size）。
MSS 是單個 TCP 段的最大資料量

每當傳送端收到接收端的 ACK 時，cwnd 的值會增加。
- 增長方式：在每個 RTT（往返時間，Round Trip Time）內，cwnd 的值會加倍
- 第 1 個 RTT：cwnd = 1 MSS
- 第 2 個 RTT：cwnd = 2 MSS
- 第 3 個 RTT：cwnd = 4 MSS

通過對每個收到的 ACK 增加 cwnd 來實現的

當發生丟包（loss event）時，TCP 停止慢啟動，進入下一階段如擁塞避免

### Congestion Avoidance
當 cwnd 的值達到ssthresh(1/2 cwnd在timeout前的value)時
TCP 會從指數增長切換到線性增長

在loss event時，ssthresh這個變數被設定成cwnd的一半

### summary: coongestion control
1.slow start
2.congestion avoidance
3.Fast Recovery(以下)

---

避免完全返回慢啟動，快速恢復傳輸效率
- 重複 ACK：
- 若接收到 3 個重複 ACK，cwnd = ssthresh + 3 × MSS
- 重新傳輸丟失的段，繼續維持傳輸
- 新 ACK：
- 清除重複 ACK 計數，恢復正常增長，重新進入擁塞避免階段

### TCP CUBIC

#### AIMD 方法的限制
- 使用 AIMD 來探測可用帶寬，但其增長方式較慢，特別是在高帶寬、高延遲的網路
- AIMD 會以線性方式增加傳輸速率，當發生丟包時將傳輸窗口減半，導致恢復速率較低。

#### TCP CUBIC 擁塞控制算法
- W_max是發生擁塞丟包時的窗口大小（即傳輸速率）
- 在發生丟包後，傳輸窗口的恢復速度更快，但接近 W_max 時放緩，以減少擁塞風險


- K代表 TCP 窗口大小（W）達到最大窗口值（W_max）的時間點(k可以控制)

根據當前時間與K之間的距離的**三次方**來增加 W
- 距離 K 較遠時（還未接近最大窗口）：增長速度較快，快速接近 W_max。
- 接近 K 時：增長速度減緩，變得更加謹慎，以避免擁塞

### the congested bottleneck link
TCP 會不斷增加傳輸速率，直到發生丟包
丟包通常發生在網路中的瓶頸（Bottleneck Link）

#### Bottleneck Link
- Buffer通常處於接近滿的狀態
- 當傳輸速率超過瓶它的處理能力時，緩衝區溢出，導致數據包丟失

#### Delay-based TCP Congestion Control
保持sender-to-receiver pipe要保持繁忙，但不要溢出

- RTT_min
- 最小觀察到的 RTT，表示在未擁塞時網路的理想往返時延
- 幫助判斷網路當前是否處於擁塞狀態

測得的吞吐量（Measured Throughput）：
$\text{Measured Throughput} = \frac{\text{# of bytes sent in last RTT interval}}{\text{RTT_measured}}$

當前窗口大小（cwnd）的理想吞吐量(非擁塞吞吐量)：
$\text{Uncongested Throughput} = \frac{\text{cwnd}}{\text{RTT_min}}$

---

- 如果測得的吞吐量接近非擁塞吞吐量
- 表明網路尚未擁塞，線性增加cwnd
- 如果測得的吞吐量遠低於非擁塞吞吐量
- 表明網路可能處於擁塞狀態，緩衝區開始累積或鏈路過載。
- 線性減少cwnd

### Explicit Congestion Notification
ECN是一種在網路中傳遞擁塞的機制，它通過網路路由器和協議層的標記(flag)來告知傳輸端存在的擁塞，而不依賴於丟包來指示擁塞
- ECN 使用 IP 頭部的兩個位元（ToS 字段中的 ECN 位） 來表示網路的擁塞狀態
- TCP 協議中使用 TCP 標頭的 C 和 E 位來處理和回應這些擁塞標記

### TCP Fairness
當有 K 個 TCP 連接 同時共享同一條帶寬為 R 的瓶頸鏈路（Bottleneck Link）時，每個連接的平均速率應為$\frac{R}{K}$

公平的理想條件
- 所有 TCP 連接的往返時延（RTT）相同。
- 網路中只有固定數量的 TCP 連接。
- 所有連接遵循擁塞避免（Congestion Avoidance）規則。

#### UDP and Fairness
- UDP 缺乏擁塞控制機制，因此不會減少傳輸速率，即使網路擁塞，UDP 仍會繼續以恒定速率發送，丟包是可接受的，但可能導致其他 TCP 連接的性能下降
- UDP 可能破壞公平性

#### 並行 TCP 連接
- 打開多個並行的 TCP 連接，以加快數據傳輸
- 每個 TCP 連接都會各自分配一部分bandwidth
- 應用程序可以通過創建更多的 TCP 連接來獲得更大的帶寬，影響公平性

# CH4

資料封裝與解封裝
- 在發送端，將傳輸層的段（segment）封裝成數據包（datagram），然後交給鏈路層。
- 在接收端，從鏈路層接收數據包，解封裝後交給傳輸層

### Router
- 檢查數據包的標頭（header）：
- 分析 IP 標頭中的欄位（如目標地址）來決定如何轉發數據包。
- 數據包轉發：
- 根據路由表，將數據包從輸入端口轉發到適當的輸出端口，確保數據包按照端到端路徑傳輸。

## Network layer
分成 data plane 和 control plane
### data plane
- 本地功能（Local)
- data plane 是每個路由器內部的功能，
- Per-Router Function
- 主要任務是根據數據包的標頭信息，決定datagram如何從router的 input port 傳到 output port

### control plane
- network-wide logic
- 決定datagram從來源host傳遞到目的地host的路徑
- 法1: traditional routing alogrithms(由router執行)
- 法2: software-defined networking(SDN) (由遠端的server執行)


### Two key network-layer functions
- forwarding:
將packets從router's input link 送往合適的router's output link
- routing:
決定packets從來源到目的地的路線
### Per-router control plane
每個routers互相收集彼此的資訊，每個routers在各自的利用routing algorithm來計算出local forwarding table。
### Software-Defined Networking (SDN) control plane
藉由遠端的控制器來計算forwarding table, 並且安裝在每個router上
### Network service model
網路層服務模型定義了不同數據流類型（單個數據包或數據流）的服務需求

針對單個數據包的服務
- 保證交付
- 有延遲保證的交付(時間壓力)

針對數據流的服務
- 按順序交付
- 保證最低帶寬(遊戲之類的)
- 限制數據包間隔的變化(需要均勻流量的應用)

A

## What’s inside a router

### Router architecture overview
通用路由器的高階視圖:
- routing, management control plane(software) 須花較多時間
- forwarding data plane(hardware) 非常快速

### Input port function

Decentralize Switching:
- 每個輸入端口獨立處理數據包的查詢與轉發，而非將此工作交給集中式的路由處理器
- 利用header去forwarding table尋找適合的output port
- 假如datagrams到達的速率大於forwarding到switch fabric的速率，就會發生queueing

### Destination-based forwarding
(圖在給三小)
- 僅根據數據包的 目標 IP 地址 進行查詢和轉發(傳統)
- 根據destination IP address 去forward

#### Longest prefix matching
就lex
在查表時，要選取destination IP address的 prefix 與表中項目中相符合最長的那一項。
(圖我就不放了，去看簡報的ex應該很好懂)
通常使用ternary content addressable memories (TCAMs)來執行
與傳統記憶體不同，TCAM 可以基於內容而非地址執行搜索
### Generalized Forwarding
定義： 可以基於數據包標頭中的任意字段進行轉發決策，而不僅僅依賴目標地址。
應用： 更靈活，適合應用於新型網路架構（如 SDN，軟體定義網路）。

### Switching fabrics
將 packet 從 input link 傳輸到合適的 output link
- switching rate
- ptk從輸入轉移到輸出的速率

假設每個input port的傳輸速率是R，今天有N個input link，則理想的switching rate是N\*R
#### 三個主要類型
#### Switching via memory
- 最初的generation router(第一代路由器)
- 由CPU直接控制有switching功能的tracditional computer(決定output link)
- packet 被複製到系統內存
- 速度會被memory bandwidth限制
#### Switching via bus
- 數據包從輸入端口的記憶體被傳送到shared bus。
- bus將數據包轉發給輸出端口，輸出端口的記憶體接收並處理數據包
- input port會在封包加一個標籤，指定要傳送出去的output port
- 由shared bus傳到每個output port，output port判斷該標頭是不是指自己，是的就保留，不是則捨棄。
- 同一時間只有一個封包可以跨過bus

**Bus Contention**
- 當多個輸入端口同時嘗試使用bus時，導致延遲
- bandwidth限制了數據包的轉發速率

#### Switching via interconnection network
- 利用棋盤式交換結構(crossbar switch)，若有N個輸入埠、N個輸出埠，會由2N條匯流排(N條水平、N條垂直)形成此結構，而交換結構控制器可以決定那些是斷開或閉合，此結構便可以實現同一時間轉送多個封包的功能。
- multistage switch
- nxn switch from multiple stages of smaller switches
- 將大型交換網絡分解為多個較小的交換階段

**Exploiting Parallelism**
- 將datagram切分為固定長度的數據單元（Cells），以便在交換網絡中高效傳輸
- 切分後的cell通過交換網絡傳輸，在出口處重新組裝成完整的datagram
- 支持多個數據流的並行傳輸，充分利用交換結構的帶寬
### Input port queuing
- 當switch fabric的速度比input port傳入的速度慢，input port就會發生queuing 甚至是 loss。
- queueing delay and loss due to input buffer overflow
- head-of-the-line(HOL) blocking : 排在前面的datagram無法傳送，整個隊列中的其他數據包也會被阻塞，無法向前移動
### Output port queuing
- 當今天datagram到達output port的速率大於output link的transmission rate，則會需要先將datagram buffer(緩衝)起來
- 如果緩衝區滿了，可能會丟失datagram
- Drop Policy
- 當緩衝區已滿時，需要確定應該丟棄哪些數據包(優先級)
- Scheduling discipline : 當多個數據包在緩衝區中等待時，必須決定哪些數據包應該優先發送(擁有優先權的人可以享受到更好的效能)。
- queueing (delay) and loss due to output port buffer overflow


### Buffer Management
Drop:當buffer滿的時候
- tail drop : drop掉正準備到達的packet(tail尾巴)
- priority: 依優先的順序drop甚至是remove掉在output port buffer的packet

Marking:
router可以將congestion(壅塞)的訊號標記在packet，讓host知道(ECN、RED)

### Packet Scheduling
決定該要先send哪個在buffer上的封包

#### FCFS
first come, first served(First-in-first-out)
#### Priority
- 進入buffer(queue)時會先分類
- 任何header裡的資訊都可以成為分類的依據
- 會優先傳送優先權高的封包
- 如果兩個封包來自同一個優先權分類，則用FCFS決定誰先傳
#### Round Robin(RR)
- 進入buffer(queue)時會先分類
- 任何header裡的資訊都可以成為分類的依據
- 到達的數據流同樣根據類別分類並放入不同的隊列中。
- 會輪流的傳送每一個分類的封包
#### Weighted Fair Queueing(WFQ)
- 進入buffer(queue)時會先分類
- 任何header裡的資訊都可以成為分類的依據
- 原理跟round robin很像，一樣都會輪流傳送每一個class的封包，差別在於每個class都有自己的權重
- 會根據每個class的權重($\frac{w_i}{\sum_j w_j}$)大小來決定這個class被輪到後一次可以傳送多少的封包]
- 保證基本的bandwidth

### Network Neutrality(網路中壢)(應該不會考)


## IP: the Internet Protocol



(考了送他，大概)
(又在騙)

### IP addressing
- 32-bit identifier 標識每個連接到網絡的主機或路由器的接口（Interface）
- interface : host或router與physical link的連接點
- router通常有多個interfaces
- host通常有一個或兩個interfaces(乙太+無線網路)

考過

### Subnet(子網)
裝置與裝置間的interface不需要經由中間路由器就能相連的裝置
- subnet part : 在相同subnet的裝置，IP address有相同的high order bits
- host part : 有自己獨有的low order bits
將router或host的interface分離，分離出的那塊孤立的區塊就是subnet

### CIDR(Classless InterDomain Routing )
用來靈活地分割和分配 IP 地址
address中subnet部分的長度是隨意的
address format: a.b.c.d/x, x是subnet部分的長度
a.b.c.d -> Ipv4
x 是子網中用於標識網絡的位數

例子：200.23.16.0/23
/23 表示前 23 位是子網部分，後 9 位是主機部分。(binary)

> 我是不是在做筆記嘛[name=BendTail ]

#### 如何得到IP address?
- 由系統管理員在設定檔中 hard-coded (e.g., /etc/rc.config in UNIX)(static)
- DHCP 動態主機配置協議

#### DHCP(Dynamic Host Configuration Protocol)(為應用層的協定)
目的:可讓想加入網路的host被server動態地分配IP address

當host加入網路，主機動態地從 DHCP 服務器獲取 IP 地址

動態分配能讓同個IP可以不同時地分配給不同的host，因為可以將IP分配可以當下有需要的人，而不是IP永遠固定給某一台不是隨時在上網的host，這能減輕IP位置不夠的問題。
大部分 DHCP server 是被建置在router內，服務router所連接的子網路。
:::spoiler 反服版
小朋友們，你們知道哪裡有DHCP服務器嗎?
不知道欸，好想知道喔，快點告訴我!
我是DHCP服務器!(喊聲:DHCP服務器)，我這裡剛好有一組IP地址，你有要用嗎?
好啊，謝謝你，你真是我最好的朋友，那我就用這個IP地址囉!
好的，你拿去用吧!
> 精神狀態相當美麗[name=BendTail ]
:::

DHCP 還可傳遞IP位址外的資訊:

- 離client最近的router的IP位址
- DNS server的name跟IP位址
- network mask(indicating network versus host portion of address)

- DHCP 的請求消息被多層協議封裝：
- DHCP 封裝在 UDP 中。
- UDP 封裝在 IP 中。
- IP 再封裝在 Ethernet 中（以太網框架）

一層一層封裝，再一層一層解封裝，透過UDP傳遞

#### 如何獲得 IP 地址的子網部分
從提供者 ISP 的地址空間中獲得分配
ISP會有很大的IP量可以分配



**ISP這部分我看不太懂**
> 對不起[name=匹眼 ]


### Hierarchical Addressing : Route Aggregation
- 階層式地址分配
- IP 地址是分層分配的，從大的 ISP 分配到小的子網或組織

- 路由聚合
- ISP 將多個子網的地址匯總成更大的地址塊，對外只廣播這個總的地址塊
- 不用存儲每個子網的路由

最長前綴MATCH有用了

ICANN 會分配IP位址給5個regional registries(RRs)(區域網路註冊機構，是管理世界上某特定地區Internet資源的組織)
IPV4已經不夠用，但可以藉由NAT可以暫時解決IP位址不夠的問題。
而IPV6有128個bit，為未來將設法普及的定址方法，短時間內應該不會出現位址不夠分配的問題。

### NAT (network address translation)
NAT，能讓在區域網路內的所有裝置共同使用一個IPv4(Internet Protocol version 4)的IP位址來對外界做連線，只是分不同的source port
優點
- 只需要跟ISP租用一個IP，就能使私人區域網路能跟網際網路連線
- 當區域網路內更改了其中一個host的IP位址，不需要告知外界
- 如果換了另一家ISP的服務(換了IP)，也不用改變區域網路裡的IP位址
- 可以讓外界無法直接地存取區域網路裡的裝置，對網路安全有幫助
#### 實現
- Outgoing Datagrams
- 當資料包從內部網路發送至外部網路時，NAT 路由器會將每個資料包的來源 IP 位址和port改成用戶被ISP分配到的IP address，並產生出一個新的port number
- 外部伺服器接收請求時會將回應發送到該 NAT 位址與對應的埠號
- 記錄轉換表（NAT Translation Table)
- NAT 路由器需要在「NAT 翻譯表」中記錄下
- (內部來源 IP 位址, port) 對應的 (NAT 外部 IP 位址, 新port)。
- 這樣可以確保當回應資料包進入時，NAT 路由器知道將其轉發回正確的內部設備

- Incoming Datagrams（傳入資料包）
- 當外部伺服器回傳資料包時，位址為 (NAT 公共IP 位址, 新port)。
- NAT 路由器會查詢翻譯表，將該資料包的目標 IP 位址和埠號轉換回原來的 (內部來源 IP 位址, 埠號)，並將資料包發送回內部設備

NAT的爭議
- router"應該"只處理網路層的功能
- IP位址短缺問題應該由IPv6解決
- 違背end-to-end原則
- client無法連接在NAT區域網路裡的server
- 之所以NAT還是一直被使用，是因為NAT已經廣泛應用在我們的家裡或是各個機構中

### IPv6
32 bit IPV4快用完了
改128 bit 的IPV6
新增動機:
- 固定的40-byte的header，加速了forwarding
- 可以讓其他網路層做流量處理

#### Transition from IPv4 to IPv6
不是所有的router都更新成使用IPv6的版本，
**tunneling**:
將IPv6的datagram放入IPv4 datagram裡的payload欄位中，在IPv4的routers中做傳遞。(封包放在封包內做傳遞)

廣泛用於4G/5G中，因為4G/5G是使用IPv6

大約1/3支援IPv6

## Generalized Forwarding, SDN

- Forwarding Table（轉發表）
- 每台路由器包含一張轉發表，又稱為Flow Table。
- 該表儲存了一系列匹配條件（如 IP 位址、端口號等）和相應的操作。
- Match Plus Action 模式：
- 當封包到達時，路由器根據封包header（如來源位址、目的位址、協議類型等）進行匹配。
- 根據匹配結果採取相應的操作。

- destination-based forwarding : forward based on dest. IP位址
- generalized forwarding :
其他的header資訊都可以作為下一個行動的依據
可以做很多其他的動作 : drop/copy/modify/log packet
### Flow table abstraction
flow : 由封包header field value定義，可以是在link layer, network layer, transport layer裡所定義的值
- generalized forwarding : simple packet-handling rules
- match : pattern values in packet header fields(看網路層、鏈結層或傳輸層的headers裡一項或是多項的值是否match)
- actions : 將match的packet進行drop, forward, modify或是send matched packet to controller的動作。
- priority : 當多個規則同時匹配時，使用優先級來區分
- counters : 可以算總共用了多少的bytes或packets(計算user的用量)，監控流量或進行流量統計
### OpenFlow:flow table entries
OpenFlow，一種位於data link layer的protocol，能夠控制switch或router的forwarding plane，藉此改變packets所走的網路路徑。

透過match+action實現了不同裝置的功能
- Router
- match : longest destination IP prefix
- action : forward out a link(轉發連結)
- Firewall
- match : IP address and TCP/UDP port numbers
- action : permit or deny
- Switch
- match : destination MAC address
- action : forward or flood
- NAT
- match : IP address and port
- action : rewrite address and port

## Middleboxes
A Middlebox 是指位於來源主機與目的主機之間的中介裝置，其功能超越標準 IP 路由器的常規傳輸功能，會對數據流進行處理和修改。它不僅負責傳輸，還可能增強安全性或優化流量控制
最初：專有（封閉）硬體解決方案

- 逐漸將 “whitebox” hardware 應用在 OPEN API
- 擺脫專有（封閉）硬體解決方案
- via match+action 可編程 local action
- 軟體創新/差異化
- SDN(Software-Defined Networking):在private/public cloud中進行集中控制和配置管理
- network functions virtualization (NFV):
- 將網路功能 (如路由、防火牆、NAT) 軟體化，部署在虛擬化平台上而非專有硬體上
- 實現於 Whitebox 硬體上

將所有東西塞到IP層
Three cornerstone beliefs:
- simple connectivity
- IP protocol: that narrow waist
- intelligence, complexity at network edge
### The end-end argument
一些網路功能可以implemented in network, or at network edge

# CH5
### Per-router control plane
每個routers互相收集彼此的資訊，每個routers在各自的利用routing algorithm來計算出local forwarding table。
### Software-Defined Networking (SDN) control plane
藉由遠端的控制器來計算forwarding table, 並且安裝在每個router上
## Routing protocols
- 決定來源端到目的地的經過network of routers的good paths
- path : 封包從來源主機到目的主機所經過的一系列路由器
- good : 最少的cost，最快，最不雍塞
分類
- Static (靜態)：
路由更新頻率低，僅在拓撲變更時手動或延遲更新。
- Dynamic (動態)：
路徑根據拓撲變化快速更新，並會定期進行更新或根據連結成本變動進行調整。
- Global (全域)：
所有路由器都有完整的網路拓撲及連結成本資訊。
典型演算法：Link State (連結狀態) 演算法。
- Decentralized (分散式)：
路由器僅知道與相鄰節點的連結成本，並透過與鄰居交換資訊來計算路徑。
典型演算法：Distance Vector (距離向量) 演算法
## Dijkstra’s Link-State Routing Algorithm
- centralized : 每個node都知道網路中所有link的cost(成本)
- 藉由link state broadcast實現
- 所有node擁有的資訊是一樣的
- 計算從單一節點 (source) 到所有其他節點的最短成本路徑(least cost paths)
會給予所有的node forwarding table
- iterative : 經過k個迴圈，可以得到到k個目的地的最小成本路徑
- 
實作自己看

O(n²) complexity
more efficient implementations possible: O(nlogn)

### discussion
每個router都需要broadcast自己的link state資訊給其他 n router
### route oscillation(震盪性)
- 如果將流量擁塞設為link cost，則會發生震盪的情形。
- 當cost依賴於流量時，路徑計算會因不同流量條件發生變化

## distance vector

### Bellman-Ford Example
each node

以下三點重複循環:
等待local link cost的改變或是鄰居傳來新的DV
根據鄰居傳來的DV重新計算自己的DV
如果重新計算的DV有改變，則會通知並傳給鄰居
最多做|節點數|-1次鬆弛

實作自己看

#### cost change

每個節點是iterative與不同步的，他們各自的迭代取決於:
- local link cost的改變
- 鄰居傳來新的，改變過後的DV

每個節點也是分散式與self-stopping:
- node只會在必要的時候(自己DV有更新的時候)通知自己的鄰居自己的改變
- node假如沒有收到通知，就不會有動作(action taken)

cost突然由
大變小，是可以順利正常運作的
小變大，可能會造成無限loop(分散式的問題)

由於Z的DV告訴Y只需5就能到X，Y就會更新自己的DV(Y到X走Z，花6)，
Z會再由Y更改自己的DV(Z到X改成7)，…無限循環，count-to-infinity
### 比較LS跟DV
- complexity:
- LS : n router, O(n²)
- DV : 每個router收斂的時間不同
- speed of convergence(收斂):
- LS : 有可能會震盪，但一定會收斂
- DV : 每個node收斂時間都不同
- 可能有無限循環的問題
- count-to-infinity的問題
- robustness(穩健性，可靠度):

- LS
- 可能會broadcst到不正確的link cost
- 每個router都只計算自己的table
- DV
- 可能會傳遞不正確的最短路徑資訊
- 錯誤可能會藉由鄰居交換慢慢傳開

## intra-ISP routing : OSPF
目前的路由研究都太過理想化了
- all routers identical
- network “flat"(沒有層次結構)
- 但是router間有差異有層次

現在的路由器已經太多了，根本沒辦法儲存所有的目的地到routing table中
routing table exchange would swamp links

- 方法:可將routers匯集至“autonomous systems” (AS) 自治系統 (a.k.a. domains)

#### intra-AS (aka "intra-domains")域內路由:

- 在同一個自治系統內進行路由
- 所有在AS裡的router只能跑同一個 intra-domain protocol(intra-domain protocol)
- 在不同AS的router可以跑不同的intra-domain routing protocol
- gateway router : 在所屬的AS的邊緣，連接其他AS的router

#### inter-AS (aka "inter-domain")域間路由:
- 在不同自治系統之間進行路由
- gateways perform inter-domain routing (as well as intra-domain routing)

被intra 與 inter-AS routing 演算法配置的forwarding table :
- intra-AS routing 決定在AS裡的destination
- inter-AS & intra-AS 決定外部的destination

**自治系統內（Intra-AS）常見的路由協議**
### OSPF(Open Shortest Path First) routing
- Open : 公開的
- 使用link-state
- 每個router都會廣播自己的OSPF link-state給所有在AS裡的routers
- 直接在 IP 層廣播這些鏈路狀態更新信息
- 可有多種的link costs，如參考bandwidth或是delay
- 每個router都會有完整的topology，利用Dijkstra’s去計算forwarding table
- security:所有OSPF訊息都經過身份驗證（防止惡意入侵

#### Hierarchical(階層式的OSPF) OSPF
two-level hierarchy: local area, backbone.
- link-state只廣播(flood)在area中或是backbone中
- 每個node只有自己area的topology
- 對於其他區域，僅知道如何轉發到達它們的方向，而非topology

area border routers:
- 統整在area中與目的地的距離，廣播到backbone中

local routers:
- 廣播 LS in area only
- 計算在area中的路由
- 經由area border router去跟外界傳遞封包

boundary router:
- 連接其他AS的router

## routing among ISPs: BGP(Border Gateway Protocol)
可讓subnet去告訴其他網路說 "I am here"
EBGP (Exterior BGP):
跟neighboring AS交換訊息用
IBGP (Interior BGP):
跟自己AS內部的router交換訊息用
determine “good” routes to other networks based on reachability information and policy