### Cost-Effective Resource Sharing

- **Multiplexing**

允許多個數據流(聲音、影片…)共用同一個物理通道，而不會干擾彼此

- **Demultiplexing**

多個數據流從同一物理通道出來時，進行分離的動作並引導到正確接收端


- **Synchronous Time-Division Multiplexing，STDM**

一種 multiplexing，將多個數據流依照時間片段放入通道中，按照預定的時間進行傳輸，達成分離的效果，再依據時間進行 demultiplexing

- **Frequency Division Multiplexing，FDM**

一種 multiplexing，利用不同的頻率來區分傳遞不同的資料，將傳輸的頻率帶分成子頻率帶，利用不同的子頻率帶傳出不同資料，無線網路、廣播就是運用此技術

- **Statistical Multiplexing**

與上兩個技術不同，statistical multiplexing 是動態生成所需的寬頻，而不是像上方兩個一樣固定，在需要保證QoS(服務質量)的應用中，statistical multiplexing 可以實施機制來優先考慮某些用戶或數據流(FIFO、RR)。

- **Packets vs. Messages**

數據傳輸通常使用packets或Messages來傳輸信息。packets是數據的小塊，通常包含了source和destination，以便在網絡中路由。messages是更高層次的數據，可以包含一個或多個packets。statistical multiplexing 可以根據這些packets或messages的需求來分配帶寬。

### LAN, MAN, WAN, SAN

- **LAN (Local Area Network) - 局域網**

局域網是一個用於連接位於相對較小地理區域內的設備和計算機的網絡。這些地理區域可以是辦公室、家庭、校園、或建筑內的一個特定區域。LAN 通常由以太網或Wi-Fi技術構建，用於實現在這些區域內的計算機和設備之間的本地通信。

- **MAN (Metropolitan Area Network) - 城域網**

城域網是一個用於連接位於城市或大型城市地理區域內的不同區域或據點的網絡。這些區域可以跨越數十到數百公里的範圍。城域網通常用於連接不同的分支機構、校園、或商業區域，以實現數據和通信的跨區域傳輸。

- **WAN (Wide Area Network) - 廣域網**

廣域網是一個涵蓋更大地理範圍的網絡，通常跨越城市、國家，甚至跨越全球。這些網絡連接不同地區和地點，並使用各種傳輸技術。例如：互聯網

- **SAN (Storage Area Network) - 存儲區域網絡**

SAN 是一種特殊的高速網絡，它存儲大量的數據，使用 SAN 的主要原因是 SAN 不受網絡流量，

這是因爲SAN並不是局域網的一部分，它被分割開來作爲一個單獨的網絡

### 網路的特性

- **Reliability(可靠的)**
- 完美的網路不存在
- 網路需要隱藏錯誤
- Bit的錯誤
- Packets are lost (封包遺失)
- Links 和 Node 的 failures
- Messages傳遞延遲
- Messages 以 out-of-order 的方式傳遞
- Third parties eavesdrop ( 第三方竊聽 )
- **Manageability(可管理的)**
- scaled up ( 可擴展性 ) : 用戶量增加
- Troubleshooting ( 故障排除 )
- Networks are everywhere
- Plug & Play ( 隨插即用 )
- Network technologies change anytime
- Demands of application programs change anytime ( 應用程序需求變化 )

### **Protocols (通訊協定)**

每個通訊協定通常定義了兩種interface，Service Interface 和 Peer-to-peer Interface

Service Interface (服務接口) :

Service Interface 定義了協議提供的服務或操作，以及這些操作如何被高級對象或應用程序使用。這個接口描述了協議所提供的功能，以及如何使用這些功能。高級對象或應用程序可以使用服務接口中定義的操作，以向底層的協議發出請求

Peer-to-Peer Interface (對等接口) :

Peer-to-Peer Interface 定義了協議中交換的消息的格式和含義，以及如何與對等方進行通信。這個接口描述了消息的結構、內容、協議的狀態遷移和對等方之間的通信細節。對等接口確保不同的通信對象能夠理解和解釋協議消息，以實現通信的正確和可預測。

!

- **Layering**

為了Abstraction管理複雜的網路，所以我們透過layering的方式來實現，通常使用OSI的7-layers

1. Physical Layer ( 物理層 ) ：負責處理數據的傳輸媒介，例如電纜、光纖、無線信號等。它定義了數據的傳輸速率、電壓等物理參數。
2. Data Link Layer ( 數據鏈路層 ) - point-to-point ：將數據集結成一個 frame，adaptor則負責實現 protocol ，device driver 實現 adaptor 與網路的通訊。此層處理數據的分幀、錯誤檢測和糾正，以確保數據的可靠傳輸。
3. Network Layer ( 網絡層 ) - host-to-host：負責 packet 的 routing，以確保數據從源節點傳輸到目標節點。它定義了網絡地址和路由協議，例如 IP 協議。

以上三層就可以實現所有網路 node 的功能

4. Transport Layer ( 傳輸層 ) - end-to-end ：實現了不同程式間的通訊通道，在此層傳輸的數據單位為 message。此層定義了 TCP（傳輸控制協議）和 UDP（用戶數據報協議）。
5. Session Layer ( 會話層 ) ：提供一個 name space，將相同應用程式的不同數據流 tie together，確保最後數據能聯結在一起。
6. Presentation Layer ( 表示層 ) ：負責數據的格式轉換、加密解密、數據壓縮等，以確保數據在不同系統間的互操作性。
7. Application Layer ( 應用層 ) ：是 OSI 模型的最高層，負責提供各種應用程序和服務，如電子郵件、文件傳輸、遠程訪問等。它是用戶和應用程序之間的接口。

以上四層是 run 在 Host 或 程式上，與 Switche 和 Router 無關


- **IP (Internet Protocol)**
1. 不意味著嚴格的分層：

應用程式可以自由地繞過已定義的傳輸層，直接使用IP或其他底層網絡。這意味著應用程式可以根據需要選擇不同的傳輸層協議或方式，而不受嚴格的分層約束。

2. hour-glass shape(沙漏形狀)結構：

這指的是IP協議在整個架構中扮演了關鍵角色。架構的形狀呈現出上寬下寬，中間狹窄的形態，而IP協議則擔任了整個結構的焦點。

3. 新協議的包容標準：

要正式納入這個架構中的新協議，需要具備協議規範，以及至少一個（最好是兩個）協議規範的代表性實現。這確保新協議在被採納之前經過充分的測試和實現，以確保其穩定性和可用性。

- **Socket**

一個應用程序連接到網路的點，應用程序和 network 之間的 interface ，應用程序創造了socket

定義了以下四個操作：

1. Create socket - socket()
2. Attaching socket to network - bind()
3. Sending and receiving messages through the socket - recvfrom() / sendto()
4. Closing the socket - close()

**Socket Interface**

Internet Domain : 在 Internet Domain 中，建立網路連結需要指定5 - tuples。

Protocol, Local Address(local IP), Local Port, Foreign Address(local IP), Foreign Port

Unix Domain : Unix Domain是一種在相同計算機上不同進程之間進行通信的機制，而不牽涉到網絡通信。通過本地路徑名，不同進程能夠在同一台計算機上進行 socket，而無需建立網絡連接。

### **Internet Performance**

- Latency(Delay) = Propagation + transmit + queue

Propagation = 距離(m) / 光速

Transmit = size (bit數量) / bandwish (bps每秒傳輸bit數)

Hint: One bit transmission => propagation is important
Hint: Large bytes transmission => bandwidth is important



- **RTT**

在網絡通信中，為了充分利用網絡帶寬，發送方需要盡量保持管道（網絡鏈路）充滿數據，以減少通信時的等待時間。發送方在發送數據之後，需要等待一個來回時延（Round-Trip Time，RTT）來接收來自接收方的響應。要確定發送方在等待接收響應期間需要發送多少位元組的數據，可以使用以下公式：

**Sender Bytes to Transmit = RTT x Bandwidth**

**`Sender Bytes to Transmit`** 是發送方需要在等待response發送的bit數。

**`RTT`** 從發送方發送到接收方並回到發送方所需的时间（毫秒為單位）。

**`Bandwidth`** 每秒可以傳輸的 bit 數（bps為單位）。

在pipe中的bit數被稱為 ”in flight”，即使 receiver 要終止傳送，也會把管道內的資料接收完。

Throughput = TransferSize / TransferTime
TransferTime = 1 / Bandwidth x TransferSize

### Link ( 連線 )

- **Link Capacity and Shannon-Hartley Theorem**

Q : C = Bxlog2(1+S/N), C = 3000 x log2(1001) = 30kbps.

How can we get 56kbps?

將 SNR 提高到 35 dB（S/N = 3162），則可以計算通道容量如下： C = 3000 * log2(1 + 3162) ≈ 56 kbps

- **Link 的分類**

會依照連線的的介質來區分，例如：銅線(DSL)、光纖(長距離、家庭)、空氣(無線網路)…等

會依照不同的頻率來區分，以下為波長計算：

wavelength（λ） = Speed of light ( c ) / Frequency ( f )

以銅線頻率300Hz為例計算波長：

( 2/3 ) * ( 3 X 10^8 ) / 300 = 667 * 10^3


- 將2進制data傳入信號稱為**encoding**



NRZ（Non-Return-to-Zero）是一種數位信號編碼方式，

問題1：Baseline Wander

接收器在處理 NRZ 信號時，會以觀察到的信號的平均值當作區分0和1，如果長期接收到大量的0或是1會影響平均值，造成判斷0或1時不準確。

問題2 : Clock recovery

我們必須確保接收端和發送端的clock是同步的，不同步的話接收端無法正確decode訊號，因此需要 Frequent transition from high to low or vice versa，這樣才可以精確地做clock recovery，若是沒有電位的變化來同步clock，則會導致clock drift

NRZI ( Non-Return-to-Zero Inverted ) : 解決NRZ電位持續不變的問題

解法：發送端在每個clock cycle進行電位改變來encode 1, 電位不變encode 0，雖然可以解決連續1造成的問題，卻無法解決連續0的問題

Manchester Encoding : 主要目的是將Clock與Data合併在一起，以實現時鐘同步和數據的可靠傳輸

解法：將clock和data做XOR，它在每個時鐘周期內交替從低電平到高電平，形成一個低/高（low/high）的信號對，這個信號對被視為一個時鐘周期。

0: low→ high transition
1: high→ low transition

問題1 : 每個數據位的開始和結束都伴隨著信號的過渡（低→高或高→低）。這樣的編碼方式確保了時鐘同步，但同時Doubles the rate at signal transitions。

問題2 : Baud Rate

信號變化的速率稱為Baud Rate，上面問題1造成Baud Rate變得很高，另外信號變化的頻率變高也代表，實際傳送的速率是Baud Rate的一半，因為每個數據位需要兩個信號過渡（開始和結束），因此信號過渡的頻率加倍，但每個過渡僅對應一個數據位。


4B/5B encoding :

插入額外bit確保不會出現連續0或1，將4 bit插入變為5 bit，雖然傳送速率下降，但只下降了80%，4B/5B 編碼確保不會出現超過三個連續的 0


### Framing ( 偵同步 )

在network中我們關注的是**packet-switched** network (packet called frames at this level)，

我們不關注bit streams，Adaptor幫助兩個node去交換frame。

運作方式：

A node告訴自己的Adaptor希望傳送給B node，此時會將memory中的一個frame傳送出去，

B node接收到後將frame存入memory中，確定sequence of bits的起始點和結束點，以此來形成一個frame是Adaptor的主要工作

**Byte-oriented Protocols，將frame視作bytes的集合，而不是bits的集合**

- **BISYNC ( Binary Synchronous Communication ) - sentinel approach ( 標記法 )**

使用特定的frame開始和結束標誌來確定frame的邊界

- SYN ( Synchronize ): frame of start
- SOH ( Start of Header )：frame的header開始。
- STX ( Start of Text )：標誌文本（數據）的開始。
- ETX ( End of Text )：標誌文本的結束。
- DLE ( Data Link Escape )：用於轉義或逃逸字符，以處理特殊字符。
- CRC ( Cyclic Redundancy Check )：用於檢測傳輸中的錯誤。


- **PPP ( Point-to-Point Protocol ) - sentinel approach ( 標記法 )**

使用特殊的標記字符來表示frame的開始和結束。使用一個特殊的 "Start of Text" 字符，通常被稱為 "Flag"，二進制表示是 01111110。

- Address, Control : default number
- Protocol : 決定是IP / IPX
- Payload : 實際數據(通常是1500 bytes)
- CRC : 用於檢測傳輸中的錯誤。


- **DDCMP ( Digital Data Communication Protocol ) - Byte-counting approach**

使用 Byte-counting approach 來確定frame的邊界，frame開始由count字段來標識，這個字段指示了frame中有多少字節，但如果count字段受到毀損，就會**Framing error，**所以Byte-counting approach雖然簡便，但是要注意毀損問題。


**Bit-oriented Protocol**

- **HDLC Protocol : High Level Data Link Control**

Beginning and Ending Sequences : 0 1 1 1 1 1 1 0

是一個Bit Stuffing機制的protocol。

發送方：

連續傳輸五個連續的1時，且不是在嘗試傳送特殊的 "01111110" 序列時，傳送方會在傳送下一個bit之前插入一個0。這樣做的目的是防止接收方錯誤地將連續的1視為frame的結束標記。

接收方：

當接收到五個連續的1時，接收方會檢查下一個bit。如果下一個bit是0，則該比特是被 "stuffed"（填充）的。

當接收到六個連續的1時，01111110代表結束標記。01111111代表全錯，須把資料丟棄。


### Error Detection ( 錯誤偵測 )

electrical interference 和 thermal noises 等原因，bit error可能會被引入到frame中。當接收方檢測到錯誤時，通常有兩種主要方法來處理這些錯誤：

- **Detecting Error :**

當接收方檢測到frame中存在錯誤時，它會通知發送方，告知消息已損壞，並要求發送方重新發送該消息。基本想法是在frame中加入redundant information，以此來判別是否錯誤。

12,000 bit 數據的frame僅需要 32 bit 的 CRC

- Cyclic Redundancy Check ( CRC ) : DDCMP, HDLC 中運用到，透過多項式運算，生成一個校驗碼，它附加到消息中。接收方也執行相同的多項式運算，以檢查接收到的消息是否包含錯誤。
- Two Dimensional Parity : BISYNC中運用到，是based on one-dimensional parity，就是在byte的第八位添加 1 來達到讓 byte 中的 1 數量為奇數或偶數。Two-dimensional parity。 Two Dimensional Parity則對每個frame中包含的每個字節進行類似的計算。這導致整個frame的一個額外的奇偶校驗字節，除了每個字節的奇偶校驗位之外。二維奇偶校驗的優點是它能夠檢測所有1位、2位和3位錯誤，以及大多數4位錯誤。這使得它能夠提供較強的錯誤檢測。這種方法通常用於提高傳輸的可靠性，特別是在需要高度可靠性的應用中。


- Checksum : IP Protocol中運用到，把傳送的所有word相加計算，並且稱作checksum。接收方也做一樣的計算，比較兩個的總和是否有不同。計算方式是16-bit ones complement arithmetic，然後取ones complement(反碼，對每個位數進行反轉)，假設(-5) + (-3)


- **Correcting Error :**

這種方法用於不僅檢測錯誤，還能夠自動修復它們的情況。當接收方檢測到frame中存在錯誤時，它會使用特定的錯誤檢測和修復算法來試圖重建或修復消息。

### **Reliable Transmission**

CRC是用來偵錯的，雖然有些error code可以自己修復error，但因為成本太高，所以通常會選擇再進行一次傳輸。為了實現可靠傳輸，link-level會使用兩個機制，分別是**Acknowledgements(ACK)** 和 **Timeouts，**
這兩個機制加起來稱作**Automatic Repeat Request (ARQ)**

1. **Acknowledgements(ACK)**

是一個小的control frame，裡面僅包含header，當發送方確定接收方已收到control frame，就會發送本來的frame。

2. **Timeouts**

一個預設的等待時間，如果超過稱為timeout，會再發送一次control frame

上述的兩個機制構成了一個Protocol：

**Stop and Wait Protocol**

1. 當發送方傳輸一個frame後，它會停止並等待接收方的確認（ACK），確保接收方已經成功接收了該幀。
2. 如果一定時間內未收到確認，則發送方會timeout，然後重新傳送原始的frame。這是為了確保即使發生丟失或錯誤，數據也能被正確傳送。

**Stop and Wait Protocol** 會遇到的問題：

ACK再回傳給發送方時遺失，造成發送方重新發送 frame，接收方誤以為這是第二個 frame

解法：用 1-bit sequence number (0 or 1)，可以根據序號判斷這是不是重複傳送的frame
此Protocol的缺點：每次只能發送一個frame後等待，造成pipe無法被填滿

**Sliding Window Protocol**

Sliding Window Protocol解決了上面的問題，發送方對每一個frame分配一個SeqNum(序號)作為標示，

發送方主要由三個變數組成：

- Sending Window Size ( SWS ) : 這是發送方可以同時傳送的 unacknowledged frame 的上限數量。這個值通常由協議規定，控制發送方的窗口大小。
- Last Acknowledgement Received ( LAR ) : last acknowledgement 上的 SeqNum，作用是給發送方確認對方有收到哪些 frame。
- Last Frame Sent ( LFS ) : 最後一個發送的 frame 的 SeqNum 。


Hint : 發送方每收回一個 acknowledgement 就會將 LAR 往右移，每發出一個 frame 會有一個相應 timer 開始計時，timeout 掉會重新發送這個 frame，也因此這個 Protocol 需要 buffer 住最多 SWS 量的 frame，方便重新發送。

接收方主要由三個變數組成：

- Receiving Window Size ( RWS ) : 接收方可以容忍的帶有 out-of-order 的 frame 數量。
- Largest Acceptable Frame ( LAF ) : 接收方可接受的最大的 SeqNum。
- Last Frame Received ( LFR ) : 接收方上一個收到的 frame 的 SeqNum。


接收方接到 frame 會有以下操作：

1. SeqNum ≤ LFR 或 SeqNum > LAF，則丟棄該 frame
2. LFR < SeqNum ≤ LAF，則接受該 frame。現在接收方需要決定是否發送一個 ACK。
3. 接收方確認 **SeqNumToAck**，表示尚未確認的最大SeqNum，

即所有SeqNum≤ SeqNumToAck 的 frame 均已收到。

4. 接收方確認對 SeqNumToAck 的接收。這種確認被稱為 **cumulative**。
5. 接收方重新設定變數 :

LFR = SeqNumToAck

LAF = LFR + RWS

6. 假設有兩個 frame 8 & frame 9 已經到達，但是 frame 7 還沒到達，則SeqNumToAck 就不會更新為 9 ，除非 7 已經到達。

**Sliding Window Protocol** 會遇到的問題：

當 timeout 時，傳輸中的 data 會減少，因為發送方 window 會卡住。當 packet loss 時，這種方案不再能 keeping the pipe full。如果要注意到丟包所花費的時間越長，問題就會變得越嚴重。也就是說，當未收到確認時，發送方持續將數據發送到網絡中，而當最終收到確認時，已經有多個包處於傳輸中，其中一些可能已經丟失。這導致了更多的重傳和網絡擁塞。

解法如下：

1. Negative Acknowledgement ( NAK ) : frame 6 沒到 frame 7 先到達時，發送 NAK 回去告訴發送方，但這不必要，因為 timeout 機制已經存在。
2. Additional Acknowledgement : frame 6 沒到 frame 7 先到達時，發送方做重複確認的動作，針對還沒拿到 ACK 的frame。會增加複雜度。
3. Selective Acknowledgement : 接收方僅確認它已經接收的 frame，而不是最高編號的frame。接收方僅確認frame 7，發送方知道 frame 6 丟失。這種方法可以幫助keep pipe full，但可能需要更多的複雜性。

**ISSUE 1 :** 如何決定 window size ?

SWS = Delay X Bandwidth

RWS can be anything :

RWS = 1，receiver 不用 buffer，也不會 out of order

RWS = SWS， The receiver can buffer frames that the sender transmits

**ISSUE 2 :** 有限的 Sequence Number 會遇到的問題

1. 3 bit 只能包含 0～7，超過就要 wrap around( 又從0開始 )。那我們該如何區分相同Sequence Number但不同輪的 frame 呢 ?

Ans : 確保 SWS ≤ MaxSeqNum (跟沒講差不多)

2. 假設 Sequence Number 是 0~7，發送方發了一個 0～6 的 frame，接收方也收到了，結果回傳 ACK 的時後沒傳成功，發送方誤以為失敗就繼續傳 0～6， 這時接收方想要的是 7～5( 6 個 frame )，所以發送方又傳了0～6之間的 frame ，接收方以為那是他要的資料，就出錯了。

Ans : If RWS = SWS, SWS < ( MaxSeqNum + 1 ) / 2

**Sliding Window Protocol 擔任的角色**

- Reliable Delivery：確保資訊傳送過程不會消失，反覆確認並恢復
- Ordered Delivery：用 SeqNum 確保每個 frame 的順序
- Flow Control : 用 window size 確保發送方的傳送速率不會超過接收速率

### Ethernet ( 乙太網路 )

是過去40年來最成功的區域網絡技術之一，它使用了 CSMA/CD ( Carrier Sense Multiple Access with Collision Detection ) 的技術，此技術讓一組 nodes可以共享 link， Carrier Sense 可以偵測 link 是否忙碌， Collision Detection 可以偵測自己傳送的 frame 是否和其他 node 發生碰撞。

乙太網的 root Protocol 是 ALOHA，用於支持夏威夷群島之間的通信。在ALOHA中，傳輸媒體是大氣，而在以太網中，傳輸媒體是同軸電纜，連線方式參考下圖：

Transceiver 檢測到空閒回發送訊號給host，

Transceiver 連結 Adaptor(網卡)，Adaptor插入主機來使用，Protocol 是在 Adaptor實現。

乙太網之間的連接則需要透過 Repeater。兩個 host 之間不能超過4個 Repeater，會造成訊號過弱 (下圖)。



在乙太網路中，任何訊號被 Host 放上去，任何連到乙太網路的人都可以收到，並且是雙向傳遞的，

Repeaters 會將訊號放到外部網段 ( outgoing segments )，Terminators 會放在 segments 的尾端，防止信號重複反射。

**New Technologies**

10Base2 技術 :

10 代表 10 Mbps， Base 代表電纜用 baseband system，2 代表電纜線不超過200m。
>1 Mbps: 1 x $10^6$ bits/second = 1 x $2^{20}$ bits/sec

10BaseT 技術 :

T 代表電纜不超過100m，目前常見是由multiway repeater ( Hub ) 配置多個點對點的連結


Hint : Hub 和 Switch的差別
* Hub 會把接收到的數據傳輸給每個 Host，不管接多少node，同一時間只有一個node能傳封包，效能低
* Switch 可以發送到特定LAN內的特定MAC位址，最多可同時傳 N/2 個封包，效能佳

**Access Protocol**

是一個演算法叫做 **Ethernet’s Media Access Control (MAC)**，是在 Adaptor 上實作的。

它傳送的 Frame 是以下格式：

- Preamble (64bit)：讓接收方進行信號(cycle)同步用
- Address (48bit each) : 發送方和接受方地址
- Packet type (16bit): : 作為 demux key ，為了辨識 higher level protocol
- Data (up to 1500 bytes) : 最少要46bytes for detect collision
- CRC (32bit) : 不多說，前面有看懂這應該不用講


**Address**

- 每個乙太網路的 Adaptor 都有一個專屬的 address，並不是每個Host一個，它會被燒錄在ROM(Read only memory)內，它的呈現方式如下(前導0省略，例 : 08會顯示0) :

8 : 0 : 2b : e4 : b1 : 2

00001000 00000000 00101011 11100100 10110001 00000010
每四個bit代表一個數字，8個bit做分隔，16進制會以冒號做分隔。

為了確保address不會被重複利用，製造商會被規定前24位(24bit prefix)，

例：AMD = 8:0:20

- 傳送到乙太網路上的 frame，會被每個 Adaptor接收到，Adaptor 會依照 frame上的address來辨別說要發給哪個 Host。如果address是全1 (unicast address)，代表這是要發給所有人的 broadcast address。 但如果只有第一個bit是 1，代表這是multicast address，Host可以自己寫程式決定 Adaptor要接受哪些multicast address。

**結論**

Adaptor 會接收到所有的 frame，並且依照以下規則看是否接受並發給Host：

1. frame address destination 是自己的 address
2. frame address 是 broadcast address
3. frame address 是 multicast address 並且已經被 Adaptor 監聽
4. Adaptor 在 promiscuous mode(混雜模式)

**Transmitter Algorithm**

- 基本機制
- adaptor 有 frame 要發送，line 是閒置就會直接發送，沒有的話就等到閒置為止
- 傳輸data限制最高1500 bytes，會讓傳輸的時間可以固定
- 乙太網路被稱做 **1-persistent protocol**(1代表機率百分之百)，因為當 Adaptor發現線路一閒置，它就會立即發送，但 **1-persistent protocol** 會有問題是，如果有兩個 Adaptor 都想發送，這就會造成**colliding** (碰撞)。

因此衍伸出 **P-persistent**(ALOHA在用)。當偵測到有**empty slot**(將時間切分成多個slot，每個slot代表一次完整傳輸所要的時間)，會以機率P發送 frame，以 (1-p) 的機率延後，

- Collision detection (碰撞偵測)
- 當乙太網路偵測到碰撞發生，它會發送一個32 bit 的jamming sequence (干擾序列 )，然後停止發送本來的frame，所以碰撞發生它至少會發送一個 96 bits 的數據(64-bit preamble + 32-bit jamming sequence)。但兩個 Adaptor farther apart，較晚發覺碰撞，則會傳輸超過 96 bits。

最慘的情況是兩個 host 在乙太網路的 opposite ends(兩端)，要確保兩個發生碰撞至少需要512 bits(14 bytes of header + 46 bytes of data + 4 bytes of CRC).

- 情境：A、B兩人同時想發 frame，A在 time t 發送 frame，此時 link latency 為 d，因此 B 在 t + d 時接收到 frame 並發現有 Collision，此時 B 才發送 32-bit jamming sequence，而回送到 A 時，A 必須持續傳送 t + 2d 的時間才能發覺。


- 在一個2500m (最長) 的乙太網路中，兩個Adaptor最多需要傳送512bits來確認是否collision， 所以在 10 Mbps傳輸速度的乙太網路中，round trip delay (來回的時間)會是51.2us
- 當 Adaptor 發現 collision 時，它會暫停一段時間再重新傳送，而每次失敗它的暫停時間就會加倍，稱做 **Exponential Backoff**

**Exponential Backoff詳細運作：**

Adaptor 一開始會設定 delays 是 0 或51.2us (k=0, 1)，當 collision 發生時，它會隨機設定成 0 或 51.2us 或 102.4us 或 153.6us (k=0, 1, 2, 3)，以此類推，下次 k = 0, 1, 2, 3, 4, 5, 6, 7。所以其實加倍的是k不是實際上的時間，只是有可能變成加倍

**乙太網路總結**

- 在 lightly loaded 的情況下表現最好，heavy loads 會導致浪費資源在 collisions。
- 大部分乙太網路的 host 要少於200，比1024這個上限少很多。
- round-trip delay 比較接近 5 us 而不是 51.2 us.
- 乙太網路容易管理與維護(easy to administer and maintain.)，沒有Switch怕壞掉，也不用一直更新 routing and configuration tables
- 很容易增加新的 host，也不貴

</br>

### Switching and Forwarding

Switch 的主要工作是接收來自它連結的 link 的 packets，然後將 packets 傳送給別的Link，因此才稱做 " switching and forwarding “，根據 OSI 架構定義，這是 network layer (IP Switch) 的主要工作

**運用到的技術：**

- Store-and-Forward Switches：

Switch 接收到 frame 後會先儲存起來，而不是直接傳送到 Host，儲存後會進行錯誤檢測和處理，但會造成一些延遲。

- Bridges and Extended LANs：

Bridges 會連結多個 LAN，讓網路更加龐大。

- Cell Switching：

數據被分割成小的 Cell ( 53 bytes ) 才進行傳送，通常會運用在 ATM (Asynchronous Transfer Mode) 網路。

Hint : ATM 網路是把傳送 bytes 固定在 53 的小單元傳送方式，並且傳送單元可以以不同的速度進行傳送，可以提供高寬頻和低延遲的通信，適用在串流(YT、Netflix)

- Segmentation and Reassembly :

數據被切分成小的段落進行傳送，等到了目標位址後才進行重組。

**設備**

- **Bridge**

Bridge 是位於 link layer (第二層) 的設備，用來連結不同的 LAN


- **Switch**
- Switch 是位於 link layer (第二層) 的設備，也是用來連結多個 same types 網路 (LAN)，可以實現multi-input multi-output，可同時從多個端口接收 frame，並同時發送到多個端口。
- **Broadcast Domain**： Switch 上每個端口可以分別做廣播，端口 A 的廣播不會影響到端口 B 的設備，並且各個端口之間的廣播不相通。
- Switch 就是 multiport 的 Bridges

- **Hub (build LANs)**

Hub位於Physical layer (第一層)，會有 **Collision Domain**，當不同 Host 同時要發送訊息會有Collision 的發生。

- **Router(路由器) / IP Switch**
- 位於Network layer (第三層)，路由器根據目標IP地址發送封包，實現不同網路間的數據交換。
- **Isolate Broadcast Domains** : 路由器能夠隔離廣播域，通常每个接口形成一个獨立的廣播域，從而減少廣播流量


**Star Topology ( 星型拓樸 )**

一種加入到 point-to-point link、 bus (乙太網路)、Ring (802.5 and FDDI)的新技術，


性質：

- 單一 Switch 因為接口的限制，而有 Host 連結數的上限，但如果有多個 Switch 則可以不受這個限制。Hosts 利用 point-to-point links 連結 Switch ，從而建構 large geographic scope 的網路。想加入新的 Host 只需要將它連結到 Switch 上，並不會干擾其他 Host 的性能。
- 上述提到不影響其他 Host 只有在利用 Switch 做連結，在傳統的 shared media network (Ethernet) 因為共享電纜，同時發送資料是會產生 Collision ，使用 Switch 則不受此限制，只要 Switch 的容量足夠，每個 Hosts 可以 transmit at the full link speed (bandwidth)。


**Switch 的連結**

- Switch 要如何決定該把 packet 放在哪個 output port ?

它會在 packet 的 header 找到 identifier，實際操作有以下三個方法

- **Datagram ( Connectionless ) approach**

這個方法不需建立持久連線，只需看封包上的 header 來決定派送地址。

每個 packet 上包含 enough information 讓 Switch 可以知道它該把此封包送往哪裡，簡單來說就是完整的 destination address。

一開始 Switch會建立一個 forwarding table ( routing table )

>scale小的話可以用人工生成table，scale大的話則配合Routing protocol自動生成

**Datagram 特點**

- Host 可以隨時隨地發送 packet，因為 Switch 可以 immediately forwarded (假設你有正確的 forwarding table )。
- 發送方無法得知 network 是否能傳送數據，或 destination host 能否接收數據 ( 有沒有在run )。
- 每個 packet 都是 forwarded independently ，所以不同的 packet 可能發送路徑完全不一樣。
- Switch or link failure 可能不影響發送，會自動找到可以的路徑，還會update the forwarding table 很厲害吧。

- **Virtual circuit ( Connection-oriented ) approach**

是一種常見的 packet switching 技術，主要概念是使用**virtual circuit( VC )**，需要在發送方和接收方建立虛擬連結，其實虛擬連結就是一種路徑，封包走這路徑就可以到目的位置，也可以稱做 **connection-oriented model。**

重點： Two-stage process 1. Connection setup 2. Data Transfer

**Connection setup**

1. 在發送方和接收方建立 connection state
2. 每一個封包通過的 Switch 都會有個表叫 **VC table** ，**VC table** 的項目有以下：
1. Virtual Circuit Identifier (VCI)：packet 的 header 會攜帶這個 Identifier， Switch 就用這個欄目對照它是否有建立連結
2. Incoming interface : VC 最後到達的接收方 Switch 的接口 ( 讓交換機知道派到哪個Host )
3. Outgoing interface : VC 從發送方的 Switch 要離開的接口
4. Potentially different VCI : packet 在傳送的過程中，可能因為不同 Switch 的 VCI 不同，而被傳送過程中遇到的 Switch 修改掉 VCI，所以這個欄目用來多存幾個不同的 VCI，防止被改來改去認不出來
3. 為了確保 VCI 是和別人是沒有重複的 ( uniquely identifies the virtual connection )，當經過一個 Switch 的時候，進出和出來的 VCI 通常會長得不一樣，VCI 並不是一個 global 的 ID，只對 given link 有意義。所以我們只要確保在這次的 Link 中，這個 VCI 沒被用到就好，不用管 global。

**兩種主要的 connection state 方法**

1. **Network Administrator will configure the state :**

由 Network Administrator 來管理狀態 (建立連接)，這是一個 permanent (永久) 的virtual circuit，建立後如果 Administrator 不主動刪除此連結會一直存在，因此叫做 **PVC**。被視為一個long-lived VC。

實作：

Administrator 想要建立一個 VC 從 Host A 到 Host B。


它會先給這個連接一個還沒用過的 VCI 值，假設 5 被選擇做為連結Host A 到 Switch 1 的 VCI 值，11 被選擇做為連結Switch 1 到 Switch 2 的 VCI 值，所以 Switch 1 的表會如下：


Switch 2 和 Switch 3 的表如下 :


所以在開始傳送之前，每一個 Switch 都會建立好各自的 VC table，只要一開始 Host A 把 VCI 值寫進 Header 裡面，之後開始傳送時就會按表操課，VCI 值在傳送中也會一直切換如下表 :

所以 Host B 看到Outgoing VCI = 4 就知道是從 Host A 送來的封包

但在現實中，面對大量的 Switch 要管理這些 VC tables 其實負擔很大，所以還是會使用 **signaling** 來建立永久連結，但這些 signaling 是由 administrator 進行控制，所以算是 PVC 的一種，而不是下面提到的 SVC，下面那種 signaling 是由 Host 發出。

2. **A host can send messages into the network to cause the state to be established :**

Host 發出 messages 說要建立 state，這被稱做 signaling，產生的 virtual circuit 被稱做 switched。因此叫做 **SVC**， Host 可以自己決定這種 VC 的設置和刪除，不用 Administrator 。

建立連結實作：

Host A 會先發送一個 setup message 到 network 上，message 中包含了目標 Host B 的完整 destination address，setup message 會一路到達 Host B，透過路徑中經過的 Switch 建立 connection state，一路上的 Switch 就會知道透過哪個接口 output 出去能抵達Host B，假設每個 Switch 都知道 topology 去找到如何到達 Host B。

透過 setup message 來建立連線，一開始我們只會在 VC table 上紀錄 Incoming 接口和 incoming VCI，而 incoming VCI 是由到達端 Switch 自己決定的，以下圖為例， Switch 1 將 incoming VCI 設為 5， Switch 2 將 incoming VCI 設為 11，最終到達 Host B。


現在要開始告訴發送端它的 downstream neighbor 是誰，從 Switch 3 開始回填 outgoing 接口和 outgoing VCI，一路回填到 Host A，最終完成 VC 的連線。


刪除連結實作：

當 Host A 不再需要傳送資料到 Host B，Host A 會傳送一個 teardown message 到 switch 1，switch 1 就會刪除 relevant entry接著把 teardown message 向後傳，最終到達 Host B，若之後 VCI為 5 的封包想傳送，會直接被丟掉。

**Virtual circuit 的特點**

- 要等待連結的建立( connection request 要送到目標位址 )，所以至少會有一個 RTT of delay
- Connection request 有 host B 的完整地址 ( 可能很大 )，但在一般的 data packet 只有一個很小的 identifier for link。所以除了第一次 Connection request 送完後，之後傳輸時的 header 就不用這麼大，這是比 datagram 還要好的原因
- 缺點是，如果固定好的路徑上有 Switch 壞掉，那整個連線就掰了，需要重新建聯結，刪除舊的 VC table
- 在一開始 connection request 發送階段，是和 routing algorithm 走的方式差不多

**Virtual circuit 的好處**

- Host 在 send data 之前，他就有很多資訊，例 : 一條實際的路線，並且receiver is willing to receive data
- 可以在建立連結後 allocate resources

**VC 的實際應用 - X.25 network**

當 VC 一建立起來時，每個連線會被分配到 Buffer (接收方還沒接收的暫存區)，每個 VC 連線 nodes 之間使用的通訊協議是 sliding window protocol，這個協議會 flow control 以確保傳送的數據量不會超過 Buffer，如果發現 Buffer 不夠時，則 reject connection request。

**Datagram V.S. Virtual Circuit**

Datagram 沒有 connection establishment phase，並且每一個 packet 傳送都是獨立的，傳送路徑也會不同。而且 Datagram 不同的封包彼此之間會競爭 buffer， VC 則沒有這個問題，若是 buffer 空間不夠，一開始連接根本不會建立。

**最流行的VC技術應用 - Frame Relay 和 ATM**

1. Frame Relay :
Frame Relay 的技術主要是應用在 VPN 上，透過公共網路建議安全的私人聯結
2. ATM ( Asynchronous Transfer Mode )
- Connection-oriented packet-switched network
- packets 也被稱作 cells ( 5 byte header + 48 byte payload )
- 使用 Fixed length 的 packets，方便硬體之間傳輸 (設計更簡化，允許同時處理多個數據 )
- **User-Network Interface (UNI) : User 和 ATM 網路之間的通訊規範**
- Host-to-switch format ( Host 到 Switch 的數據格式 )
- GFC : Generic Flow Control - 控制流量用
- VCI : Virtual Circuit Identifier - 辨識用 ID
- Type: 顯示這個數據包是甚麼類型 ( Management 、Congestion Control、 Data Transfer **)**
- CLP : Cell Loss Priority - 數據包丟失優先級，假如要丟掉封包，看要先丟哪個封包
- HEC : Header Error Check (CRC-8) - 用於檢測 header 是否有錯


- **Network-Network Interface (NNI) : 網路和網路之間的通訊規範**
- Switch-to-Switch format ( Switch到 Switch 的數據格式 )
- GFC becomes part of VPI field - GFC 被合併到 VPI ( virtual path identifier ) 內，以協調網路間的流量控制。
- **Source Routing**

一開始發送方就決定好了發送路徑，不靠演算法，是一種很少見的方式。

Host 會提供所有傳送封包時 network topology 的資訊。
</br>
- **Source Routing**
一開始發送方就決定好了發送路徑，不靠演算法，是一種很少見的方式。Host 會提供所有傳送封包時 network topology 的資訊。

### Bridges and LAN Switches
**Bridges and LAN Switches**
- 一種用於在共享媒體區域網（例如Ethernets）之間轉發數據包的交換機類別，被稱為LAN switches，也稱為Bridges。

- 假設您想要連接一對以太網，一種方法是在它們之間放置一個中繼器( repeater )，這可能會超出以太網的物理限制。
- 另一種方法是在兩個以太網之間放置一個節點，讓該節點將幀從一個以太網轉發到另一個以太網，這種節點稱為橋接器( Bridge )，由一個或多個橋接器連接的一組區域網通常被稱為擴展區域網( Extended LAN )。

**Simplest Strategy for Bridges**
- 接收區域網框架（LAN frames）並將它們轉發到所有其他輸出端口，是早期橋接器使用的方法。

**Learning Bridges**
- 注意到橋接器無需轉發其接收到的所有框架


當來自host A寄給host B的frame進入port 1時，Bridge無需將該frame轉發到port 2，Bridge透過以下方法自動學習這些信息。
- 每個Bridge檢查其接收到的所有框架中的源地址。
- 記錄Bridge上的信息並建立表格。
- 當Bridge首次啟動時，此表格為空，entry會隨著時間的推移而添加。
- 每個entry都與一個timeout相關聯，在指定的時間段後，Bridge會丟棄entry，以防止主機從一個網絡移動到另一個網絡的情況。

如果switch收到一個寄給目前不在表格中的主機的frame，則將該frame轉發到所有其他端口。

### Switched Ethernet
若frame的目標地址尚未存在於任何switch的轉發表中，有可能被永遠地轉發。

Switched Ethernet（或擴展區域網）為何會形成迴圈？
- 由多個管理員管理的網絡： 當網絡由多個管理員管理時，例如橫跨組織的多個部門，可能沒有單一的人了解整個網絡的完整配置。
- 可能無人知曉的迴圈： 添加可能導致迴圈的交換機，而沒有任何人知曉，將導致迴圈形成。
- 為提供冗餘性而內建迴圈： 有時為了在故障時提供冗餘性，可能會在網絡中內建迴圈。

解決方案:
分散生成樹（Distributed Spanning Tree）算法。這是一種用於防止網絡中循環的協議，通過在網絡中選擇一棵樹，關閉可能導致循環的連接，確保有效數據傳輸。生成樹協議（Spanning Tree Protocol，STP）是一種常用的生成樹算法。

### Spanning Tree Algorithm (老師只講觀念，不會考)
Radia Perlman在Digital公司開發，一種由一組交換器使用的協議，用於就特定擴展區域網達成一致的生成樹，IEEE 802.1規範基於這種算法。

每個switch決定哪些端口願意和不願意轉發frame，在某種程度上，通過從拓撲中刪除端口，使網絡減小為非循環樹，甚至可能整個switch都不參與轉發frame。

#### 前置作業:
- 每個交換機都有一個唯一的標識符,例如，S1、S2、S3，依此類推。
- 最初每個交換機都認為自己是根，標識自己為根並給出到根的距離為0。
- 用(Y,d,X) 表示來自節點 X 的配置消息，其中它聲稱距離根節點 Y 為 d。點到點之間的距離為1。

#### 規則:

新的配置信息優於當前記錄的信息，如果：

- 它標識了一個標識符更小的根，或者
- 它標識了一個具有相同標識符但距離更短的根，或者
- 根的標識符和距離相等，但發送配置消息的橋樑標識符更小。

#### Example:

**Step1** 當電源剛恢復到擁有以下網絡架構的情況，所有交換機將首先宣稱自己是根。

**Step2** 考慮節點S3的活動。

- S3 receives (S2, 0, S2)
- Since 2 < 3, S3 accepts S2 as root
- S3 adds 1 to the distance advertised by S2 (0) and sends (S2, 1, S3) to S5
- Meanwhile S2 accepts S1 as root because it has the lower id and it sends (S1, 1, S2) toward S3
- S5 accepts S1 as root and sends (S1, 1, S5) to S3
- **S3 accepts S1 as root** and it notes that both S2 and S5 are closer to the root than it is, but S2 has the smaller ID, so it remains on S3’s path to the root, this leaves S3 with active ports

**Step3** 根據每個節點重複做step2

#### Note:
- host A與host B可能不是透過最短路徑做溝通。
- 由於是動態更新的緣故(Dynamic)，即使系統穩定後，根交換機仍然定期發送配置消息，其他交換機繼續轉發這些消息，當一個交換機失效時，下游交換機將不會收到配置消息。等待一定的時間後，它們將再次宣稱自己是根，演算法重新啟動。

### Internetworking
* **Internetwork**：隨意地把幾個不同type的網路透過Router等設備互通
* **Internet**：指每天在用的網際網路


<font size=4>**IP Service Model**</font>
* **Packet Delivery Model**：
* **Connectionless** model 傳輸資料
* **Best-effort** (盡力傳輸)，但不可靠，可能面臨到：
* packets 遺失
* packets 傳送會 out of order
* packets 會重複傳輸
* 長時間延遲
* 盡可能地讓路由器找到最快的傳輸路徑
* IP 被設計為適用於各種不同類型的網路和鏈路，它==可以在不同的物理介質上運行==，包括有線和無線網路

* **Global Addressing**：識別網路中所有主機的方法，每個主機在網路中具有唯一的標識，以便它們可以相互識別和進行通信
* IP address 就是 internet host 的地址

**Packet Format**
* 幾個重要的內容
* Version：IP 規格版本﹐目前多為 IPv4
* Length：資料封包中的 bytes 數（包括 header）
* Ident：識別碼 (ID)。每一個IP封包都有一個 16bit 的唯一識別碼，可從 OSI 和 TCP/IP 的網路層級知識裡面知道﹕當程式產生的數據要通過網路傳送時﹐都會在傳送層被拆散成封包形式發送﹐當封包要進行重組的時候﹐這個 ID 就是依據了
* Fragment offset：被切割的 IP 封包在原本封包裡面的 offset，用來重組
* Time to Live：為了避免無用的封包佔用網路資源，因此設計了一個 **TTL** 值，預設通常都是128 or 64，此參數的意義是封包每經過一個網路設備，TTL值就會減1，直到TTL值為0，封包就會被丟棄，才不會造成找不到目的地的IP封包會一直在網路上傳輸，佔用了網路的資源
* Protocol：常用的為TCP(0x06)或者UDP(0x17)封包協定
* Header Checksum：用來確認傳輸資料的正確與否
* Data：TCP or UDP封包的內容

### IP Fragmentation and Reassembly ( IP分段與重組 )：

- **MTU（最大傳輸單元）：**
- 每個網路都有其最大傳輸單元，表示可以傳輸的最大資料封包大小
- 例如，Ethernet 的 MTU 通常為 1500bytes，而 FDDI 的 MTU 為 4500bytes ( 所以FDDI要透過乙太網路傳送的話就要切成3個封包 )

- **分段策略：**
- 當路由器收到要透過具有（MTU < 資料封包）的網路轉送的資料封包時，路由器中就會發生分段 (Fragmentation)
- 重組 (Reassembly) 是在 receiving host 上完成的
- 所有分段具有相同的識別碼（Ident 欄位）
- 分段的資料封包各自獨立
- IP不會從遺失的分段中恢復。
- 每個IP資料封包都為它要經過的每個 physical network 重新封裝 (re-encapsulated )。
- Re-encapsulated 是用來描述在網路通訊中，當資料封包透過不同的網路層協定或實體網路傳輸時，將資料包重新包裝或封裝的過程。這是確保資料包在不同網路環境中正確傳輸的操作

- **Path MTU discovery**：
- Path MTU discovery 是一種機制，對於確定封包在通過互聯網時可以採用的最大MTU。這有助於避免分段並提高網路效能。


* 下圖 ( a ) 為原 IP 封包，( b ) 為分割成3段 IP 封包 F1,F2,F3
* Flags = 1 代表後面還有段，Flags = 0代表沒有了
* Offset 預設是以 8 bytes為單位，所以在下圖可知 F1 有 512bytes 的資料量，因此偏移量為 512/8=64
 &ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;&ensp;
### Global Addresses
#### 特點
- 具唯一性
- hierarchical (分層) = network + host
- 40億個IP地址，其中一半是A類，四分之一是B類，八分之一是C類，十六分之一是D類（多播），以最高位元進行識別。

#### 格式(以(a)為例)
- 126個(2^7- 2)A類網路,0跟127被保留。
- 2^24- 2(reserved)個host

#### Dot notation
- Class A : **10**.3.2.4
- Class B : **128.96**.33.81
- Class C : **192.12.69**.77

(粗體字為network part)
#### Internet可能包括
- 少量的廣域網路、一些規模較小的校園網路，以及大量的局域網

### IP Datagram Forwarding
- Forwarding : 從輸入接收封包並將其發送到適當輸出的過程。( 參考 table 決定送哪 )
- Routing : 建立表格的過程，使得能夠確定封包的正確輸出。( 生產 table 的方式通常為自動生成，人工生成成本高 )

#### IP Datagram Forwarding的特點
- 每個datagram都包含Destination IP地址。
- IP地址的network部分唯一標識互聯網中的單個physical network。
- 所有共享相同網路部分的主機和路由器都連接到同一個physical network。
- 互聯網的每個physical network都至少有一台路由器，該路由器還連接到至少一個其他physical network。

#### Strategy
- 每個datagram都包含destination's address
- 如果直接連接到目標網絡，則轉發到目標主機;如果沒有，則轉發到某個路由器。
- 在forwarding table(轉發表)中，根據network number(網路號碼) 對應到 next hop(如下表)。
- 每個主機都有一個預設的Router，且每個Router都含有一個forwarding table。


#### Hierarchical addressing(分層位址)有助於提高大型網路的scalability(可擴展性)
- Router包含forwarding tables，裡頭僅列出一組network numbers，而不是網路中所有節點的IP地址。

舉例來說，R2在一個four-entry table中存儲了連接到網路的所有主機所需的信息，即使每個physical network上有超過100個主機。

### Subnetting(子網)
為何需要Subnetting :
- 地址分配效率低下 : 一個僅有兩個節點的網路使用了整個 C 類網路位址，因此浪費了 252 個實際可用的位址，而一個有略多於 254 個主機的 B 類網路浪費了超過 64,000 個位址。
- 將每個physical network分配一個network number的缺點包括：
- 快速使用完IP地址空間。
- 使用的network number越多，forwarding tables的大小就越大。

新增address/routing hierarchy結構的另一級別：子網
- 降低分配的總network number數量。
- 將單一IP的network number分配給多個physical networks，這些現在被稱為子網的網路。
- 子網應該靠近彼此。
- 遠處的Router只能選擇到達任何子網的一條路徑。
- 適用於每個都擁有多個physical networks的大型校園或企業。
- 例如：140.116.xx.xx，看到"140.116"就知道要送去成大


關於子網路遮罩:
- 子網遮罩定義了對A類和B類地址的主機部分進行可變劃分的規則。
- IP地址和子網遮罩的位元AND操作定義了子網號碼。
- 子網僅在within site(站點內)可見。

Destination IP 與對應的子網遮罩做AND運算產生的D1若與SubnetNum一樣，則根據NextHop做應對:
- NextHop若為interface，直接將datagram傳送到目標地址。
- NextHop若不是interface，則傳送到NextHop(a Router)


注意事項：
- 如果沒有匹配項，會使用預設路由器。
- 可以在一個physical network上放置多個子網。
- 子網對於互聯網的其餘部分是不可見的。
- 校園外的路由器將網絡集合視為單個網絡（例如，128.96）。
- 校園內的路由器需要能夠將數據包正確路由到相應的子網。
- 互聯網的不同部分看到的路由信息可能並不完全相同。

### Classless Addressing(無類別位址配置) 又稱Supernetting(超網址)
Classless Inter-Domain Routing(CIDR)（無類別域間路由）是一種應對互聯網中兩個擴展方面的技術：
1. backbone routing table(主幹路由表)的增長，隨著需要存儲越來越多的network numbers。
2. 32位元地址空間的潛在枯竭，以及地址分配效率低下的問題。

這些問題是由於具有A、B和C類地址的IP地址結構引起的，它強制我們以三個非常不同大小的固定大小的區塊分配網路地址空間：

- 一個僅有兩個主機的網路需要一個C類地址，而地址分配效率為2/255 = 0.78。
- 一個需要256個主機的網路需要一個B類地址，而地址分配效率為256/65535 = 0.39。

IP地址空間枯竭的焦點集中在Class B的network numbers的枯竭上，解決方案如下:
- 對任何要求Class B地址的Autonomous System (AS)說“NO”，給予他們適當數量的Class C地址，除非它們能夠證明需要接近64K地址。
- 對於至少有256個主機的任何AS，我們可以保證地址空間利用率至少為50%。

上述解決方案同樣存在問題 : 路由器的存儲需求過大。

總歸來說，CIDR的價值在於 :
- 平衡減少路由器需要知道的路由數量的渴望，以及有效分配地址的需求。
- 使用Agregate routes(聚合路由)
- 使用forwarding table中的single entry告訴路由器如何到達許多不同的網路
- 打破了地址類別之間的嚴格界限。

實例 :
考慮一個具有16個Class C網路號碼的自治系統（AS）。與隨機分配16個地址不同，我們可以分配一個連續的Class C地址區塊。假設我們分配了Class C網路號碼從192.4.16到192.4.31。該範圍內所有地址的前20位都相同（11000000 00000100 0001）。我們已經創建了一個20位的網路號碼（介於Class B網路號碼和Class C號碼之間）。需要分配具有共同前綴的Class C地址區塊。慣例是在前綴後面放上一個/X，X代表前綴的位元長度。例如，對於所有網路從192.4.16到192.4.31的20位前綴，表示為192.4.16/20。

路由協議必須理解network number可能是任意長度的，用一對單一的形式<長度，值>表示network number，所有路由器都必須理解CIDR地址分配。


#### IP Forwarding Revisited(IP重新轉發)

- 在單個路由器的轉發表中找到171.69（一個16位前綴）和171.69.10（一個24位前綴），存在前綴的重疊，一些地址可能匹配多個前綴。
- 一個目標地址為171.69.10.5的數據包明顯匹配這兩個前綴。規則基於“最長匹配優先”原則，即在這種情況下是171.69.10。目標地址為171.69.20.5的數據包將匹配171.69而不是171.69.10。

#### Address Translation Protocol (ARP)
- 將IP地址映射到physical addresses
- 目標主機
- NextHop(下一跳)路由器
- 技術
- 在IP地址的主機部分編碼physical addresses
- 基於表格的方法(table-based)
- ARP (Address Resolution Protocol)
- IP到physical addresses綁定的表格（ARP cache/table）
- 如果表格中沒有IP地址，則進行廣播請求
- 目標機器用其physical addresses回應
- 表項在沒有刷新的情況下被丟棄（15分鐘）

#### ARP Packet Format


#### Host Configurations
- 以太網地址由制造商配置，並且它們是唯一的。
- 在給定的互聯網絡上，IP地址必須是唯一的，同時還必須反映互聯網絡的結構。
- 大多數主機操作系統提供手動配置主機的IP信息的方法。
- 手動配置的缺點：
- 在大型網絡中配置所有主機需要大量工作。
- 配置過程容易出錯。
- 需要Automated Configuration(自動化配置)過程。

#### Dynamic Host Configuration Protocol (DHCP)

- DHCP伺服器負責向主機提供配置信息
- 每個管理區域至少有一個DHCP伺服器
- DHCP伺服器維護一個available addresses(可用地址)的池

新啟動或連接的主機向一個特殊的IP地址（255.255.255.255）發送DHCPDISCOVER消息，DHCP中繼代理向DHCP伺服器單播該消息並等待回應。


DHCP Frame Format


#### Internet Control Message Protocol (ICMP)

- 定義了一組錯誤訊息，當路由器或主機無法成功處理IP資料報時，這些訊息將被發送回源主機
- 由於link /node故障，目標主機無法到達
- 重組過程失敗
- TTL（生存時間）已達到0（以防止資料報永遠循環）
- IP標頭檢查和失敗
- ICMP-Redirect（control message）
- 從路由器發送到源主機
- 攜帶更好的路由信息
- Ping (debugging tool)
- 使用ICMP回應訊息來確定節點是否可達和存活。
- Traceroute (debugging tool)
- 使用一種稍微不直觀的技術來確定一組路由器。

#### Virtual Networks and Tunnels
- Virtual Private Network (VPN)
- Physical link : 虛擬線路
- Virtual Circuit : Frame relay(幀中繼）、ATM
- IP Tunnel :
- 一對實際上被任意數量的網路分隔的節點之間的虛擬點對點連結
- 在隧道的入口路由器內部創建，通過提供隧道遠端路由器的IP地址
- 它將封裝數據包在一個IP數據包（IP-in-IP）內

#### Types of VPNs
- Point-to-point VPN
- 提供一個設備對私有網路的遠程訪問
- Site-to-site
- 建立一個虛構的橋樑，就好像將兩個私有網路直接連接在一起一樣。

#### Virtual Networks and Tunnels
一個穿越整個互聯網的隧道，下圖為R1到R2的隧道，並分配了虛擬接口號碼為0。

創建通道的原因:
- 安全性
- Mbones (multicast backbone)
- 傳輸除IPv4網絡之外的協議的數據包

缺點:
- 增加數據包的長度 : 浪費頻寬
- Fragmentation : 影響性能