計算機網路_CH4

26 April 2020

Network Layer

  • 分成三大部分:
    1. IP protocol
    2. routing algorithm
    3. ICMP error handle
  • 收來自TCP layer的資料把他encapsulate
  • 接收端收到來自router的資料後，把header extract傳給上層TCP layer
  • 每個host,router都有此層，負責forward data(router通常沒有TCP/application layer)
  • Forwarding : router收到封包時，應該要傳給其他router給receiver(單一的router行為)
  • Routing : routing algorithm,決定封包路徑，下一步要傳給哪個router，是決定封包在整個網路中透過哪種路徑傳給RECEVIER
  • Routing table : router裡面的一個table，當封包傳進來時，會判斷封包的header對應routing table的哪個位置，就會知道要送給哪個router(Forwarding),table由routing algorithm決定,
  • longest prefix match:routing table的對應是看最長的那個對應

Router 構造

  1. input port:實體曾資料傳進來，在這裡進行routing table 比對，主要分三個部分
    • line termination:接收實體層bit資料
    • data link processing
    • lookup forwarding:在這裡做table比對，因為比對要一點時間，如果一次多個封包來會queue起來，另外如果兩個封包爭取同一個switch fabric也會依個先queue起來，等另一個傳完才傳

  1. switching fabric:連接input port和output port，當input port比對完封包要送到哪後透過switching fabric傳給特定output port

    • via memory: 透過routing processor來決定到哪個output port,先把input port資料寫進memory，等到比對完(在processor or input port做)之後再把資料copy到output port

    • bus:資料透過bus傳給output port(沒有memory,routing processor),每個output port 都會收到，但只有正確的那個output port會留資料，其他output port會把封包丟掉，會受到bus bandwidth影響

    • crossbar:假設N個input,output port，那總共需要2N個bus，並且是唯一可以平行傳封包的機制(A->X B->y使用不同bus沒衝突)

  1. output port:接收fabric傳進來的封包後往外(這裡的queue和input port的queue若overflow就是一般講的router drop packet)

  1. routing processor:負責執行routing protocol,維持、更新routing table，透過PCI bus傳送給input port routing table，input port就可在本地端進行比對
  • 補充 : Head-of-the-line blocking:因為input port一次只能傳一個，所以前面那個packet block後面那個packet也會跟著被block(儘管可能他傳輸的路線沒有壅塞)如圖中綠色封包被紅色封包堵住

IP protocol

  1. version:判斷是IPv4,IPv6
  2. TTL:time-to-live，用來確保封包最多只能送TTL個router，避免他在路上loop，如果傳送超過TTL，就直接把packet丟掉
  3. Datagram length:16bits，紀錄IP封包有多少資料量(header+data)，理論上能有65535bytes的data，但很少能超過1500bytes(跟link layer有關)
  4. Upper layer Protocol:用在接收端，裡面的數字會告訴接收端要傳到transport layer的哪個服務(EX:TCP/UDP…)
  5. Header checksum:檢查header有無錯誤，儘管TCP layer也有checksum，但並沒有檢查到IP header的checksum，所以有存在的必要，每個router的TTL都不同，所以每個router都要重新計算checksum
  6. src/dest IP:兩端的IP，dest IP是src host去查DNS得到的IP填入
  7. data：放TCP/UDP或ICMP的data segment
  • TCP header 20bytes, IP header: 20bytes ==> 負擔大

IP fragmentation & Reassembly

  • IP fragment原因: link layer的傳輸資料大小有限制(MTU,Maximum transmission unit)之外，還有許多不同的protocol，如ethernet的link layer封包大小是1500bytes，但有些的只能有500多bytes。因此要把IP的封包大小fragment才能夠給link layer傳送，到接收方時要再做reassembly，router仍然是傳送這些fragment，不用組裝。

  • Fragment細節
  • format:
    1. source/destination IP
    2. Identification number : 相同ID number是來自同一個封包的fragment
    3. fragment flag:每個fragment封包此bit都是1，最後一個fragment此bit=0
    4. offset:紀錄此fragment對應到原始封包的哪個offset，可以看成fragment的順序
    5. datagram
  • 雖然一個IP封包是1500 bytes，但有20bytes是header，所以實際上只有1480bytes是data,offset = bytes/8
  • 缺點:
    1. DoS attack(Jolt2 attack):送詭異的封包(如offset從來沒為0)，此時組合起來時也會爆炸
    2. overlapping IP fragment:讓offset有重疊，接收端在接收要組合時因為重疊組不起來可能會crash

IPv4 addressing

  • Interface:裝置和physical link之間的介面，故host,end system通常只有一個對外的線，只有一個interface，router連接多個physical link，所以有多個Interface
  • 每個interface要有一個IP，而且不能跟其他人的重複，要是unique的
  • 32bits : 共有2^32個IP位址
  • subnet:host和一個router interface連接的部分，通常會有相似的IP，通常一個subnet是由switch或AP所連接，並沒有透過router連接，如圖中223.1.1是一個子網域，他們的遮罩(mask)為223.1.1.0/24，在forwarding時，只要看子網路遮罩的IP，不用看全部IP，在子網路裡才看後面幾碼的IP。
  • 簡單看法：把end system router看成終點，中間的線形成一個subnet

CIDR(Classless Interdomain routing)

  • 功能:負責維持root DNS server、發放IP給ISP
  • 將IP分為兩部分: 200.23.16.0/20，前24bits叫prefix，發放給ISP時，會以block的方式發放，所以IP的prefix都會依樣，只會差在後面幾碼，然後可以這樣hireachy的發放下去，ISP在發給其他組織。
  • 在forwarding及router forwarding table變得好紀錄很多，只要紀錄prefix就好，不用紀錄整個IP，如上述IP，只有前20bits決定forward到哪個組織，後面12bits是區分這個組織內的哪台host(但後面12bits有很大機率也被拿來做subnetting)

DHCP

  • 自動分派IP給user，可以是每個user固定一個IP或者給他一個暫時的IP，即他每次登入IP都不同
  • 優點:
    1. 對常移動的人方便，如學生換地方，通常就換一個子網路，就要新的IP
    2. 可以support更多使用者，假設有200人，但不可能同時上線，所以就可以維持即便只有100個IP位址
    3. DHCP除了給user IP外，也能告知user name和DNS的IP、network mask，gateway router IP
  • 連線步驟:
    1. DHCP discover message:client不知道DHCP server IP所以發一個這個UDP message，dest IP是255.255.255.255:68，src IP是0.0.0.0(現在自己沒IP)用來braodcast給內部子網域所有人
    2. DHCP offer message:DHCP分配IP給user，依樣發送到255.255.255.255:68 broadcast(因為此時client還沒有IP)，封包內有transaction ID(因為一個subnet可能有多台DHCP)，IP address、IP lease time(life time)(能夠使用這個IP多久)
    3. DHCP request:user收到一個或多個的offer後，選擇一個發DHCP request，一樣用braoadcast到255.255.255.255:67，內含資訊跟offer差不多(transactionID和dest port不同)
    4. DHCP ACK:收到request後，發ACK回去

NAT

  • 目的:解決IP不足的問題
  • 作法:在NAT裡面的子網路中，所有host都是用虛擬IP，不能對外連線，因此要連線都必須透過NAT，NAT再用自己的IP把封包forward出去，因此整個subnet裡面網外傳封包的IP都只有一個，就是NAT的IP
  • NAT translation table: 送出去的data因為是subnet裡某個虛擬IP的user傳出去，接收時會有問題，因為資料傳出是看NAT的IP，所以回送也只有送到NAT，NAT要這個table才能知道這個封包屬於哪個user的
    1. 某user用虛擬IP和某個port(5000)傳資料給NAT要NAT幫忙外傳
    2. NAT把這個IP,port對應到NAT本身的一個port(3333)然後外傳
    3. 資料傳出去時是以NAT的IP/PORT傳出去，所以資料傳回來也是傳到這個IP/PORT
    4. NAT去看table這個port對應到哪個user/PORT再把資料forward給該user
  • 優點:
    1. user不限定IP，就算外面不知道userIP資料仍可傳遞
    2. 多一層NAT保護，安全性高
    3. 解決IPv4不足問題
  • 問題:
    1. 在NAT裡面的使用者不能作為server(別人連不進去，在P2P,server/client mode皆有此問題)，解法uPnP,
    2. NAT有可能產生bottleneck
  • uPnP: 為了解決server/p2p在NAT狀況下的問題，user先去跟NAT設定好一個mapping，接著把這個這個mapping advertise給其他人知道，簡而言之，就是先設定好mapping並告訴外面的人。

ICMP

  • host 和 router 交換資訊的方法，通常透過error check
  • error reporting(檢查到不到的了host端)、echo request(ping)
  • 屬於network layer 但建立在IP之上
  • ICMP type/code：兩個參數用來決定要做什麼
  • EX:
    1. ping:送給host端一個ICMP封包，host端回傳一個回來
    2. tracroute:發送端不斷發送UDP封包第一層發送的封包ttl=1，第二層ttl=2…第n層ttl=n。router收到expire的封包會回傳ICMP給host。當到達接收端時，因為收到的UDP沒有specific port，所以也回傳特定ICMP(unreachable ICMP)給發送端，發送端收到後就知道封包到目的地了。每層都傳三次UDP

IPv6

  • 目的:解決IP不足問題
  • format:
    1. size:IPv4的32bits變成128bits
    2. anycast address:能送一個封包給多address(一對多)
    3. Flow label priority:能夠決定封包的形式，如real-time process(audio,vedio)或者設定priority
    4. 40 bytes header:for faster processing
  • 和IP差別:
    1. 沒有fragment:如果router收到太大的檔案，他會把他drop回傳一個”檔案太大”的ICMP，只有source/destination可以fragment / reassembly
    2. 沒有IP的header checksum:因為link/tcp layer都有checksum，新版就認為應該不用，Network layer重點在快速執行、傳遞封包
  • 使與IPv4相容:
    • Dual stack: node可以發送、接收IPv6,IPv4封包，此node要同時有IPv4,IPv6的address。如果是和IPv4 node operate,就用IPv4的datagram。可以用DNS來判斷node是接收IPv4/IPv6，DNS回傳IPv6如果那個node有IPv6的address的話，不然回傳IPv4，因此只要中間有一個node只支援IPv4，封包就會變成IPv4
    • 缺點:IPV6轉成IPv4時會有資訊loss，如flow label只有IPv6有，轉成IPv4就沒有此資訊
    • Tunnel:解決IPv6轉成IPv4時資訊loss的問題，當IPv6 node要把資料傳給IPv4 node時，IPv6 node把整個IPv6封包當成data包在IPv4內傳輸
  • 結論:改變網路層、傳輸層(TCP)是一件很困難的事，因為規模太大，但要改變應用層很簡單，就像現在有很多新的應用層模式(DNS,web,p2p)

Routing Algorithm

  • default Router(First hop router): 通常end system(host)會attach一個router，要把資料送出去，host就把資料丟給這個router讓他來forward。
  • 把網路當成graph，router=vertex,link=edge,link的cost取決於速度、bandwidth之類的因素)
  • routing altorithm分類:
    • Global routing algorithm: 計算的方式是input目前網路的狀況(就是input所有node和所有路線的cost)，通常是指link-state algorithm
    • Decentralize routing algorithm: node沒有整個網路的資訊，只能透過鄰近node的資訊來計算最佳路徑，就是後面會講的Distance vector的做法
    • static routing algorithm: link的cost改變速度非常慢
    • dynamic routing algorithm: link cost依據現在網路的壅塞程度或者狀態(有些router可能會故障)做調整，可以是一段時間update或者link changes是馬上反應
  1. 因為要知道怎個網路的link state來做運算，所以每個node都要broadcast link-state packet給其他人，使所有node都有完整、依樣的網路資訊可以算最短路徑
  2. Dijkstra
  3. Oscilating:因為每個點的演算法都依樣，算出來最短路徑相同，會發生所有node同時擠同一條路線，這條路線塞爆後，大家又一起換另一條，一直發生oscilating的狀況
  4. 解法:所有node不要sync，在不同時間broadcast link-state packet

Distance vector

  1. Bellman-Ford: dv(z) => v到z的距離 c(u,v) => u和v之間的路徑
  2. 透過Bellman-Ford算出來的答案，我們可以判斷到某個destination要把封包交給哪個node，如圖所示，下一步u要給x會是到z的最短距離

  1. Algorithm:
    1. node先計算自己到其他所有點之間link的cost (distance vector)
    2. 一段時間後把自己的distance vector送給其他node，其他node也把自己的distance vector送出去
    3. 若收到別人的distance vector，或者自己監測到自己的link的cost有改變，重新跑bellman-Ford，跑完後若自己的routing table有改變，就在把新的distance vector broadcast出去
    4. 每個node會存自己的forwarding的值，也會存相鄰的node的forwading的值
    5. ex: X的forwarding path的table,x同時存自己跟y,z兩個node的path table

  1. 問題:容易發生loop,因為彼此table async，所以可能會發生loop，Count-to-infinity problem

https://www.youtube.com/watch?v=_lAJyA70Z-o

  1. poison reverse:為了解決上述問題 假設z要透過y傳封包給x，那z傳給y時更新DV會把z到x這段路改成無限大，即使事實上不是這樣，但poison reverse只能用來解決兩個router loop的狀況，更多router的loop是無解的。
comparsion link state Distant vector
message send O(N * E) 只要送給相鄰neighbor
speed O(N^2) 會很慢收斂甚至不收斂(routing loop)
Robustness 雖然蒐集網路資訊時可能出錯(封包drop)但是最佳路徑是每台router個別運算 若有錯誤資訊會受到很大影響，假設某ISP不小心設定錯誤，可能就會導致其他ISP把資料全部送給這個ISP處理，導致問題
可行性 不可行(網路規模太大存不了整個網路資訊，而且bandwidth會變成全部拿來braodcast，沒有剩下的可以給data傳輸使用 可行

Hierachical routing

  • Autonomous system(AS):分自治區，一個自治區內部可以自己決定routing algorithm(LS)和一些規範.解決前面講到link state scale的問題
  • Intra-AS routing protocol:AS裡面自己規範的routing algorithm然後擁有AS內其他router的資訊
  • Gateway router:雖然自治區內部可以自己決定routing但總要有對外的forwarding，因此這個router就負責處理對外的forwardin或routing，對外連接的router就是gateway router
  • 問題:若今天要forward到外面某個AS(如AS2)但我們本身AS1有超過一個Gateway router，那要送給哪個Gateway router
  • inter-AS routing:
    1. AS1要學哪個router可以到哪個AS
    2. 把這些學到的資訊broadcast給AS1內每台router
    3. 全網路都使用同套protocol(BGP4)，因為要和外面的AS溝通，所以規格要統一
  • hot potato routing:假設今天要送去的地方，複數個gateway router都送的到，作法就是選擇在AS內送到那個gateway router cost最低的那一個router

Intra-AS routing(IGP,interior Gateway Protocol)

  • 決定在AS內傳輸的protocol

RIP(routing information protocol)

  1. RIP table：routing table，內含destination,Next Router,Hop三個資料 routing table存在application layer
  2. 在AS內forward的過程每經過一個subnet叫一個hop，最多只能15個hop
  3. RIP response message(RIP advertisement): 採用UDP的方式每個router每30s會送出封包告訴目前的資料給其他router，每次含有最多25個destination的資訊，收到後如果路線有比較好就更新，就像DV protocol每一段時間也會放上自己的Distance vector
  4. 假設180s沒收到來自一個router的訊息，基本上就是當那個router掛了，所以會修改自己的routing table傳給其他router

advertisment格式

Open shortest path first(OSPF)

  • Link state algorithm:router建造一個完整AS內的network，並跑Dijkstra
  • Broadcast:advertise是給整個AS內的人，不是只有鄰近的，網路只要有一點變化就會broadcast，超過30min沒有broadcast也會定期broadcast
  • 封包由IP layer送:Broadcast資訊直接由IP送出去，所以沒有TCP layer的reliable之類的規範，要自己implement
  • security:authenticate的router的broadcast封包才會接送
  • multiple same cost path allow
  • multicast support:MOSPF
  • 不同service可以有不同cost:如multimedia這種realtime的和一般的資料
  • hireachical：可以再細分成好幾個area，每個區選一個負責對外的router
    1. area router：負責area間的連接
    2. backbone router:在backbone area跑OSPF
    3. boundary router：連到其他的OSPF

BGP(border gateway protocol)

  • inter-AS routing
  • 從鄰近AS知道subnet的reachable資訊
  • propogate rechability資訊給在AS內的其他router，並決定最佳路徑
  • 幫助subnet告訴整個internet它的存在以及怎麼連進來
  • BGP session:不同AS溝通的一個TCP通道,AS之間用eBGP，router間用iBGP
  • AS2內部網路先整合自己的subnet prefix給AS1，AS1再把他broadcast給AS1每台router，每台router建立一個entry
  • BGP attribute:
    1. AS-PATH:包含這個advertise走過的AS
    2. NEXT-HOP:決定下一個要跳到哪