2014年1月15日 星期三

計算機網路期末筆記

這篇是計算機網路期末考範圍的筆記


Source / Channel / Line coding


source coding: 主要的目的是為了壓縮資料,減少儲存空間並增加資料在頻道中傳遞的效率,適合用在傳輸影像、聲音、影片,通常發生在application layer

channel coding: 主要用於錯誤修復,會在資料上加入額外的位元(也讓資料變的更安全),發生在link & physical layer,修復方式有三種
  1. ARQ - Automatic Repeat-reQuest : 接收端在收到資料後回覆已"收到正確的資料",但是有設計逾時時間(time-out),目的是為了達到可靠的傳輸,如果沒收到回覆則發放端會再發一次或者放棄(若一直傳不到)
  2. FEC - Forward Error Correction: 解決資料暴衝造成的錯誤,但會增加延遲時間,做法是把封包順序打亂,使得資料暴衝不會對連續的資料內容造成無法修復的錯誤
  3. Block codes: 在每一區段(block,一段資料)之後都放上檢查用的位元
    此法使用 m-bit (dataword) to n-bit (codeword) group,將原本的資料轉換為設計好的 code, m-bit → generator → n-bit → checker → m-bit
    接收到 codeword 後會檢查有沒有錯誤(用 parity bit),錯誤的話即丟棄
  4. CRC - Cyclic Redundancy Check: 雙方用同個除數,接收到 codeword 後皆比較其餘數是否相同來判斷資料是否正確(下面有一段會再提)

line:將數位資料轉換成訊號、避免基線漂移、非同步、直流電造成的偏差(baseline wandering p.73, loss of sync - p.69, DC component - p.74)
PCM encoder: 類比訊號→取樣→PAM訊號→量化→量化訊號→編碼→數位訊號

各種同步


  1. NRZ - non-return-to-zero: 位元若為1則給予一正電壓,位元0則為0電壓
  2. NRZ-L - non-return-to-zero level: 位元為1則給予一正電壓,0則給一負電壓
    *長時間的0或1會造成非同步
  3. NRZ-S - non-return-to-zero space: 遇到位元0就改變電壓
  4. NRZ-I: non-return-to-zero inverted: 遇到位元1就改變電壓
  5. RZ - return-to-zero: 位元1為正電壓,0為負電壓,在週期的一半時就回至0電壓,可保持同步但需要兩倍的頻寬(和NRZ比)


各種 modulation (binary *-shift keying)


  1. BASK(amplitude): 位元1的時候振幅較大
  2. BFSK(frequency): 位元1時頻率高
  3. BPSK(phase): 位元改變時即改變相位180度
  4. 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頁

各種多工法


  1. Time-Division Multiplexing(TDM): 各頻道間輪流使用資源
  2. Frequency--Division Multiplexing(FDM): 依頻率區分各頻道 *頻道間頻率不可重疊
  3. Wavelength-Division Multiplexing(WDM): 依波長 *常用於光纖傳輸用
    用不同頻率的光來傳輸,因為資料傳輸率較雙絞線快很多所以可以一起送很多使用者的資料
  4. Code Division Multiple Access(CDMA): 依編碼
  5. Spatial Multiplexing(SM): 實體空間的隔離

Framing


資料是以封包來進行傳遞的,包含了標頭(header)的控制資訊(目的地、協定、錯誤偵測碼...)及資料內容(payload)
實際傳輸時會把封包弄成位元流,收到時會把位元流轉換成封包

Addressing


Link-layer address,以一串數字代表一個 host 的身份
這項資訊被包含在封包的標頭之中,用來表明目的地和發送端

Error control


因為實體層傳輸時會發生錯誤,所以要能偵測錯誤
偵測到錯誤時接收端必須丟掉它或要求重送

有線網路的錯誤率較低,所以重送的機制只出現在高階網路層(如 TCP)
對無線網路,因錯誤率較高,所以發送端會等接收端告訴他接收正確,若逾時未收到則會重傳一次

Flow control


若發送端發送的速度比接收端所能接收的速度還快,則接收端在 buffer 滿了之後就得要求重送,但是這樣就浪費了網路的資源,所以設計了一制度可以讓接收端叫發送端發慢一點
方法:
  1. 停下來等一等
  2. sliding window: 只要沒有收到回覆的 frame 沒有超過 N 個發送端就可以一直送
  3. PAUSE frame: full-duplex 可用,發送一數字,叫發送端等那個時間
  4. back pressure: half-duplex 可用,叫閘道在送出資料之前先確認 buffer 有足夠的空間

Medium access control


當有很多個 host 都要在一共享的媒介上傳輸資料時,必須有一個好的仲裁機制來決定現在要由哪一個傳送資料
一個好的仲裁機制必須要能做到在各 host 間能達到公平性並維持傳輸媒介的使用率(不要讓它閒置)
  1. 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)後才重送
    接收時: 開始接收→接收到完→看有無碰撞(有則重來)→來源是否認識(否則重來)
  2. 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的組成

  1. Encapsulation: 包含多個協定
  2. LCP: data-link connection
  3. NCP: network-layer


PPP over Ethernet(PPPoE)


因為現在 ADSL 等的發達,ISP 希望可以對個別使用者收費,所以 LAN 中每個使用者可以和 PPPoE 伺服器連線(AC,access concentrator),就像撥接服務一樣,而每個使用者都會被分到一個 IP (或許會需要密碼)
  1. Discovery stage: 使用者搜尋 AC,建立連線,然後如同一般 PPP
  2. PPP session stage: 如同一般PPP,但是以網路線連接
    當LCP終止PPP時,PPPoE也會被拆掉

Topology(請配合投影片113頁的圖)


  1. bus: 大家在同條線上
  2. 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裡的其中一個傳

1 則留言: