Source / Channel / Line coding
source coding: 主要的目的是為了壓縮資料,減少儲存空間並增加資料在頻道中傳遞的效率,適合用在傳輸影像、聲音、影片,通常發生在application layer
channel coding: 主要用於錯誤修復,會在資料上加入額外的位元(也讓資料變的更安全),發生在link & physical layer,修復方式有三種
- ARQ - Automatic Repeat-reQuest : 接收端在收到資料後回覆已"收到正確的資料",但是有設計逾時時間(time-out),目的是為了達到可靠的傳輸,如果沒收到回覆則發放端會再發一次或者放棄(若一直傳不到)
- FEC - Forward Error Correction: 解決資料暴衝造成的錯誤,但會增加延遲時間,做法是把封包順序打亂,使得資料暴衝不會對連續的資料內容造成無法修復的錯誤
- Block codes: 在每一區段(block,一段資料)之後都放上檢查用的位元
此法使用 m-bit (dataword) to n-bit (codeword) group,將原本的資料轉換為設計好的 code, m-bit → generator → n-bit → checker → m-bit
接收到 codeword 後會檢查有沒有錯誤(用 parity bit),錯誤的話即丟棄 - CRC - Cyclic Redundancy Check: 雙方用同個除數,接收到 codeword 後皆比較其餘數是否相同來判斷資料是否正確(下面有一段會再提)
line:將數位資料轉換成訊號、避免基線漂移、非同步、直流電造成的偏差(baseline wandering p.73, loss of sync - p.69, DC component - p.74)
PCM encoder: 類比訊號→取樣→PAM訊號→量化→量化訊號→編碼→數位訊號
各種同步
- NRZ - non-return-to-zero: 位元若為1則給予一正電壓,位元0則為0電壓
- NRZ-L - non-return-to-zero level: 位元為1則給予一正電壓,0則給一負電壓
*長時間的0或1會造成非同步 - NRZ-S - non-return-to-zero space: 遇到位元0就改變電壓
- NRZ-I: non-return-to-zero inverted: 遇到位元1就改變電壓
- RZ - return-to-zero: 位元1為正電壓,0為負電壓,在週期的一半時就回至0電壓,可保持同步但需要兩倍的頻寬(和NRZ比)
各種 modulation (binary *-shift keying)
- BASK(amplitude): 位元1的時候振幅較大
- BFSK(frequency): 位元1時頻率高
- BPSK(phase): 位元改變時即改變相位180度
- DBPSK(differential-): 遇到1即改變相位180度
m-PSK 的衛星圖
均勻的將 M 個點分布在一個圓上,每點以 log M 個位元表示
QAM - Quadrature Amplitude Modulation
QAM 是 ASK 和 PSK 的結合,不僅改變了振幅,也改變了相位
因為用一個訊號表元了多個位元,所以可以達到更高的傳輸速率
QAM 至少需要2種振幅和2種相位才能表示
若能組合出2^N種表示法就可以用來表示N個位元的資料
QAM 和 QPSK 一樣,相位的改變都是90度(因為要在衛星圖上放4個點,另有圓形和正方形兩種表示法
各種QAM的畫法見投影片235頁
各種多工法
- Time-Division Multiplexing(TDM): 各頻道間輪流使用資源
- Frequency--Division Multiplexing(FDM): 依頻率區分各頻道 *頻道間頻率不可重疊
- Wavelength-Division Multiplexing(WDM): 依波長 *常用於光纖傳輸用
用不同頻率的光來傳輸,因為資料傳輸率較雙絞線快很多所以可以一起送很多使用者的資料 - Code Division Multiple Access(CDMA): 依編碼
- Spatial Multiplexing(SM): 實體空間的隔離
Framing
資料是以封包來進行傳遞的,包含了標頭(header)的控制資訊(目的地、協定、錯誤偵測碼...)及資料內容(payload)
實際傳輸時會把封包弄成位元流,收到時會把位元流轉換成封包
Addressing
Link-layer address,以一串數字代表一個 host 的身份
這項資訊被包含在封包的標頭之中,用來表明目的地和發送端
Error control
因為實體層傳輸時會發生錯誤,所以要能偵測錯誤
偵測到錯誤時接收端必須丟掉它或要求重送
有線網路的錯誤率較低,所以重送的機制只出現在高階網路層(如 TCP)
對無線網路,因錯誤率較高,所以發送端會等接收端告訴他接收正確,若逾時未收到則會重傳一次
Flow control
若發送端發送的速度比接收端所能接收的速度還快,則接收端在 buffer 滿了之後就得要求重送,但是這樣就浪費了網路的資源,所以設計了一制度可以讓接收端叫發送端發慢一點
方法:
- 停下來等一等
- sliding window: 只要沒有收到回覆的 frame 沒有超過 N 個發送端就可以一直送
- PAUSE frame: full-duplex 可用,發送一數字,叫發送端等那個時間
- back pressure: half-duplex 可用,叫閘道在送出資料之前先確認 buffer 有足夠的空間
Medium access control
當有很多個 host 都要在一共享的媒介上傳輸資料時,必須有一個好的仲裁機制來決定現在要由哪一個傳送資料
一個好的仲裁機制必須要能做到在各 host 間能達到公平性並維持傳輸媒介的使用率(不要讓它閒置)
- contention-based approach
(a) ALOHA: 所有節點隨意傳(不管它),發生碰撞時因此降低效能
(b) slotted ALOHA: 一樣隨意傳,但是只能在每單位時間的開頭傳送出去
(c) Carrier sense: 傳之前先看有沒有人在傳,但可能會發生兩點一起要傳資料的情形(hidden node problem)
(d) 發生碰撞時所有人都先不要送
(e) 若碰撞未及時發現效率就會很差
(f) CSMA/CD(carrier sense multiple access with collision detection): 發生碰撞時 CSMA/CD 會佔據(jam)線路,並等待一隨機時間(backoff time)後才重送
接收時: 開始接收→接收到完→看有無碰撞(有則重來)→來源是否認識(否則重來) - contention-free approach
(a) round-robin: 每個人傳一 token,傳到的才可以送資料
(b) reservation-based: 在傳資料前先預約這個頻道下來
Error detection code
checksum: 發送端將資料的加總一起傳送出去,接收端則是確認總和正確,此法只用在 IP/TCP/UDP 等較高層的網路,用來檢查節點錯誤
發送端演算法:
將資料切成16個位元大
加總所有資料(一補數加法)
將此和取補數後即得 checksum
接收端演算法:
sum = 0;
while( hasMoreWord() )
sum += NextWord();
while( sum >> 16 != 0 )
sum = ( sum >> 16 ) + ( sum & 0x0000FFFF );
sum 取1補數
sum &= 0x0000FFFF;
sum = 0 的話就對了
CRC(見上面也有說明)
發送端傳送一個除以2個的位元流,接收端拿來除看看是否有餘數(沒餘數才對)
用在 link layer,有無線網路均可用
硬體實作容易,但軟體難
假設有M個位元要送,則傳送M+K個位元出去,其中K個位元(叫做FCS,frame check sequence)是讓整個M+K個位元可以被某個數整除
接收端就看這M+K個位元能不能被此數整除即可
*41頁的二進位除法自己除,這裡不講了,相信大家都會
PPP 協定的關聯
HDLC ---> PPP ===> NCP
===> LCP
PPP --- PPPoE
---> INHERITED FROM ===> PART OF --- RELATED TO
PPP的組成
- Encapsulation: 包含多個協定
- LCP: data-link connection
- NCP: network-layer
PPP over Ethernet(PPPoE)
因為現在 ADSL 等的發達,ISP 希望可以對個別使用者收費,所以 LAN 中每個使用者可以和 PPPoE 伺服器連線(AC,access concentrator),就像撥接服務一樣,而每個使用者都會被分到一個 IP (或許會需要密碼)
- Discovery stage: 使用者搜尋 AC,建立連線,然後如同一般 PPP
- PPP session stage: 如同一般PPP,但是以網路線連接
當LCP終止PPP時,PPPoE也會被拆掉
Topology(請配合投影片113頁的圖)
- bus: 大家在同條線上
- star: 大家各拉一條線出來
MAC address
At data-link layer. 包裝資料、傳輸接收,以及 medium access management 用
Self-Learing
橋接器在一開始的時候不知道某個 MAC address 要從哪個 port 傳送出去,但經過一段時間之後橋接器會慢慢建好一張表,之後要傳送時查詢這張表就可以了
Virtual LAN
可以讓管理員在不更動網路拓撲的實體連接的情形下進行管理,即可以藉著指定給不同的 port 給各個 VLAN 來讓它們好像實體各自獨立的
因為多點傳送和廣播可以送到某個固定的 VLAN 上,所以可節省流量
因為封包有其目的地 port,所以不會有 frame 不知道要去哪(消耗頻寬及可能被監聽)
VLAN & Subnet
在第二層的 switch 上設定 VLAN
Subnet 在第三層, host 可以不用路由器就傳送封包,用相同的 prefix 來判斷
Routing
用路由協定來找從來源到目的地的路徑
每次都是查表然後再傳給下一個點(hop)
IP 安全性
存取控制、安全(加密)、入侵偵測
第4章16頁的圖自己看,畫不上來了
NAT
network address translation,用 NAT router 來換位置
有一個表是用來查的
外界看到的IP位置就被換了,用此路由來轉換
basic NAT: 讓具私人IP的host可以存取公共網路(指定開放IP給它們),取代原有IP
NAPT 因為前法中,一個HOST就要一個IP,可能不夠用的情形下就讓多個共用一個IP,用transport layer identifier來區分
Classful IP address
A~E classes. 每一個各有若干個 network、host 可以用,看欄位多長
A: 7, 24 (bit in length), 0 (prefix)
B: 14, 16, 10
C: 21, 8, 110
D: multicast, 1110
E: reserved, 1111
Classless~
Classful 沒有效率(大小不合用)
CIDR(Classless InterDomain Routing): a.b.c.d/x
x = prefix len
Packet forwarding
如果在同子網路裡就直接送到該目的地,不然就送到預設的路由器
用 ( hostIP ^ destIP ) & SubnetMask == 0 判斷(0就在同個裡面)
當收到封包時,可繼續送往目的地,(HOP)
若是送給自己的,就往上層送去
若是送往子網路的,直接送到目的地(挑符合最長的)
TOS(type of service)
說明想要得到的服務
前3位元說明了優先性,後4位元說明想要達成的目標(performance metrics),如最大吞吐量、最小延遲、最低成本、安全性...
Fragmentation offset
8位元長,這個 offset 是以8位元組來計量的
Time-to-Live(TTL)
記載一個封包最多只能經過幾個路由器,到達限制後封包就丟掉
traceroute
看封包傳送的路徑,可看IP及各路由,最多30個
有逾時及無法抵達目的地兩種錯誤
IP Fragmentation & Reassembly
當 IP 超過 MTU 時就會傳不過去(太大),就要切成小部份
只在接收端才組合起來
有個 more bit 說明還有沒有下一個, offset 是以8位元組為單位來算的
IPv6
標頭有40位元,內容可有多達65535個位元,標頭如以下
version: = 6
traffic class: TOS in IPv4 (bit 4~11)
flow label: bit 12~31, 用來辨認是否為一起流出來的封包
payload length: 32~47
next header: 48~55,辨別上層協定或next extension header(導向下一個extension header)
hop limit: 56~63, TTL in IPv4
scource addr.
destination addr.
位置標示法: 八個16位元長的數,以冒號隔開
連續的0可以換成一對冒號代替
IPv4:
version, header length, TOS, packet length, identifier, flags, fragmentation offset, TTL, upper layer protocol, header checksum, source /destination addr.
傳送對象數目
unicast: 一對一傳
multicast: 一對多傳(只傳一次,很多人可收到)
broadcast: 一對每個傳(只傳一次,很多人可收到)
anicast: 一對multicast裡的其中一個傳
<3
回覆刪除