計算機網路(下)

發表於 分類於 文章字數： 7k

Chap04 Network Layer

transport layer: between two processes
network layer: between two hosts and router (may also involve intervening routers in case of VCs)

  • routing protocols
    • path selection
    • RIP, OSPF, BGP
  • IP protocol
    • addressing conventions
    • datagram format
    • packet handling conventions
  • ICMP protocol
    • error reporting
    • router
    • signaling

routing: 決定packet傳送的路徑
forwarding: 實際傳送
router has forwarding table

Different from TCP/UDP(transport layer protocol)

  1. service:host-to-host
  2. no choice:network provides one or the other
  3. implemented in network core

network layer service

datagram network: network-layer connectionless service
virtual-circuit network: network-layer connection service

  1. Virtual-Circuit Networks
    3. 包含
    - 路徑
    - VC number
    - 路徑上所有router的forwarding table index
    6. performance-wise
    7. 三個階段:
    1. VC建立:傳送端的傳輸層會聯繫網路層，指定接收端的位址，並等待網路建立 VC。網路層會決定傳送端到接收端之間的路徑，也會為路徑上所有的連結決定其VC編號，在路徑每一台router的轉送表中都加入一筆項目。
    2. 資料傳輸
    3. VC斷線
  2. Datagram Networks(資料封包網路)
    • using destination address(IP)
    • longest prefix matching: goto longest address prefix that matches destination address
      • 110010000001011100010************ -> send to 1
      • 1100100000010111000100001******** -> send to 2
  3. 比較
    • Internet (datagram)
      • no setup, routers do not remember state
      • “elastic” service, no strict timing request
      • many link types: uniform service difficult
      • “smart” end systems (computers)
        • can adapt, perform control, error recovery
        • simple inside network, complexity at “edge”
    • ATM (VC)
      • human conversation: strict timing, reliability requirements
      • need for guaranteed service
      • “dumb” end systems
        • telephones
        • complexity inside network

Router architecture

Usage

  1. routing protocol (RIP, OSPF, BGP)(software)
  2. forwarding datagrams(hardware)

Structure

  1. Input Ports
    • physical layer(bit level)
    • datalink layer(Ethernet)(receive)
    • decentralized switching
  2. Switching Fabric
    • transfer packet from input buffer to appropriate output buffer
    • router內部的網路
    • 實作
      1. memory(慢):查詢轉送表，找出適當的輸出埠，然後將該封包複製到該輸出埠的緩衝區
      2. bus:同一時間內只能傳輸一個封包
      3. crossbar(棋盤式):2N bus，將n格輸入埠連接到n個輸出埠
      4. crossbar
  3. Output Ports: input port反過來
  4. Queue Management:
    佇列前端攔阻(Head-of-the-line (HOL) blocking):

Total overhead = 20 bytes of TCP + 20 bytes of IP + app layer overhead

IP: Internet Protocol

IPV4

  1. 標頭
    • 標頭長度(HEADER LENGTH)
    • 協定(protocol):只有當ip資料段達到最後目的端時，才會使用這個欄位，值為TCP或UDP。
    • 標頭檢查(Header checksum)
    • TTL(Time-to-live):確保資料封包不會在網路中無窮循環，每經過一個router，TTL的值就會遞減1
  2. Datagram Fragmentation
    • MTU(maximum transfer size): 控制IP的封包長度
      • Ex. 4000 byte datagram, MTU = 1500 bytes, real data = 1480bytes -> 1480 + 1480 + 11xx
    • be “reassembled” only at final destination
  3. IPv4 Addressing
    • address為host/router和physical layer的連接
    • Subnet: 高位元相同的ip集合，不用router就可以連接
      • subnets
    • CIDR(Classless InterDomain Routing)
      • Ex. 11001000 ,00010111 ,0001000 | 0, 00000000
      • 200.23.16.0/23(23 is number of subnet bits)
  4. Get IP address
    • ISP向ICANN(Internet Corporation for Assigned Names and Numbers)申請IP address, 記錄domain name至DNS上
    • hard-coded by system admin in a file
      • Windows: control-panel->network->configuration->tcp/ip->properties
      • UNIX: /etc/rc.config
    • DHCP(Dynamic Host Configuration Protocol)
      • IP address的分配
      • get address while connected on
        • sent to DHCP: 255.255.255.255, 67
        • listen from DHCP: 255.255.255.255, 68
      • 四階段
        • host broadcasts “DHCP discover” [optional]
        • DHCP server responds with “DHCP offer” [optional]
        • host requests IP address: “DHCP request”
        • DHCP server sends address: “DHCP ack”
      • DHCP server can also return useful information
        • address of first-hop router for client
        • name and IP address of DNS sever
        • network mask (indicating network versus host portion of address)
      • Real action
        • DHCP request encapsulated in UDP, encapsulated in IP, encapsulated in 802.1 Ethernet
        • Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN
  • NAT(Network Address Translation)(網路位址轉譯)
    • 產生local network, 可自定義ip address, 再交由NAT轉譯成正確IP
    • 可避免攻擊，便於管理。
    • http://www.cs.nccu.edu.tw/~lien/Writing/NGN/firewall.htm
    • violates end-to-end argument
    • NAT traversal problem: 在外面的user如何連到未知(不知道ip)的server
      1. 固定ip(失去保護作用)
      2. UPnP(通用型隨插即用）: 應用程式將獲得共用的Public IP地址及Port做點對點的傳輸。
      3. relaying (used in Skype)
        • 以relay server 作為 bridge
    • NAT possibility must be taken into account by app designers, e.g., P2P applications
  1. ICMP: 回報錯誤

IPv6

  1. 簡介
    • 因應大量的IP位址空間需求
      • IP位址長度從32位元增加到128位元
    • 新的位址型態: 任意點位址(anycast adress)，它允許含有任意點位址的資料段，可以傳送到一群主機中的任一台主機
    • 固定長度的40個位元組標頭, 加快資料處理
    • no fragmentation allowed
    • 資料流標記和優先權
  2. IPv6 Datagram 格式
    • 版本號碼(Version): ip的版本號碼
    • 轉送次數限制(Hop limit):每當路由器轉送資料段後，就會將資料段此欄位的內容遞減1。如果hop limit計數減到0時，就會捨棄這個資料段
    • checksum: removed in IPV6 to reduce processing time
    • ICMPv6:new version of ICMP
  3. 從 IPv4 到 IPv6
    1. 雙堆疊(dual-stack)法:其中的ipv6節點也實作了完整的ipv4，也就是這種結點能夠傳送和接收ipv6及ipv4兩種的資料段。
      ipv6/ipv4節點必須同時擁有ipv6和ipv4的位址，也需要能夠決定其它結點是否可以執行ipv6的功能。這個問題可以使用DNS解決，如果結點名稱解析為可使用IPV6功能，則它會傳回IPV6位址;否則它會傳回IPV4位址。 在雙堆疊法中，如果傳送端或接收端其中一方只能使用IPV4功能，則必須使用IPV4資料段，有可能會發生兩個可以執行ipv6功能的節點不使用ipv6，而是彼此送出ipv4資料段。這會造成IPV6的資料欄位在轉換成IPV4的型式時發生欄位遺失，最後在傳送到目的地時，不會是原始的ipv6 資料段的所有欄位。
    2. 建立通道(tunneling): 中間有中介的ipv4路由器，稱為通道(tunnel)。通道傳送端的將整個ipv6資料(含標頭檔)放入ipv4，當作資料傳送。起點和終點均為ipv6 router

Routing Algorithm

  1. Link-State (LS)
    • global: all routers have complete topology, link cost info
    • Dijkstra: 放入想算的點U至N，找!N距U最近，將其放入N，LOOP
      • !N: 若經過[最新放入的N值的點]走更近，更新值
      • O(nlogn)
  2. Distance-Vector (DV)
    • decentralized: router only knows link costs to neighbors
    • each node maintains distance vector
    • When link cost changes: update, if DV change, notify neighbors
      • bad news travels slow
      • Poisoned reverse
        • 防止路由迴圈(Routing loop)出現
        • If Z routes through Y to get to X(use time much over than expect) : Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z)
        • 當Router A發現Network X的中斷後, 將其跳躍數Hop count變更為Maximum+1, 其他router收到更新時會立刻知道Network X為Inaccessible，加快網絡收斂的速度
    • Bellman-Ford equation
      • dx(y) = argmin(v) {c(x,v) + dv(y)}
  3. 比較
    • speed of convergence
      • LS:O(n) algorithm requires O(nE) msgs
        • may have oscillations
          • 若經過的封包愈多，花費愈高
      • DV:convergence time varies
        • may be routing loops
        • count-to-infinity problem(??)
        • 惡意router散播假消息
  4. Hierachical Routing
    • aggregate routers into regions,“autonomous systems”(AS)
    • AS(Autonomous System)：一群路由器在一位管理者之下, 使用IGPs去互相傳送封包的系統

Routing Protocols

  • IGP(interior gateway protocols): use in same AS(“intra-AS”)
    • RIP(Routing Information Protocol): DV
      • Included in BSD-UNIX Distribution in 1982
      • 對自己的neighbor要求Routing Table，並計錄最短的。
        • use route-d (application level) to manage, sent in UDP packets
        • 用hop為路徑的選擇量度。最大為15 hops
        • RIP每次更新預設為30sec
      • if no advertisement heard after 180 sec --> assume neighbor/link declared dead -> invalidate route from this neighbor
    • OSPF(Open Shortest Path First): LS
      • 透過一套演算公式，所以它的路由效率會比較好些
      • Shortest path first
      • Dijkstra's algorithm
      • features not in RIP
        • multiple same-cost paths
        • security: all OSPF messages authenticated
      • Hierarchical OSPF(分層)
        • each nodes know full of local area, and shortest path to other areas
        • saves table size, reduced update traffic
  • BGP((Border Gateway Protocol)): between different AS(“inter-AS”)
    • information from neighbors(BGP會談(BGP session))
    • 使用port179的半永久性TCP連線來交換資訊
    • iBGPs(Interior Gateway Protocols), eBGPs(Exterior Gateway protocols)
    • Prefix + attributes = “route”
      • BGP attributes
        • AS-path：表示到達某一AS所必須經過的路由
        • Next-hop ：specific internal-AS router to next AS
    • BGP Route Selection(按順序)
      1. local preference(當本地AS中有多個路由可以到達某一AS，則路由選擇的優先權於與最近路由器相連接之AS開始。偏好原則)
      2. shortest AS-PATH(經過最少AS)
      3. closest NEXT-HOP router: hot potato routing(經過最少internal router)
      4. additional criteria(其他)
    • Routing Policy: do not want to provide informations not relevalent to its own customer

broadcast and multicast routing

Source-duplication
in-network duplication: enefficient, do not know send to whom
2. flooding: 當節點接到一個廣播封包,他會複製該封包在傳送給相鄰節點
3. RPF(reversed path forwarding):
1.
if (datagram received on incoming link on shortest path back to center)
then flood datagram onto all outgoing links
else ignore datagram
3. Spanning Tree
方法：定義集結點。節點以單點傳播送至集結點,定義出樹的分支
4. IGMP (Internet Group Management Protocol): Soft State
運作於主機和其直接連結的router間
換句話說,我們可以將直接連結的router,當成到達區域網路外部任何其他主機的路徑上第一站轉送router或是到達該主機的任意路徑上最後一站轉送router
5. DVMRP(Distance-Vector Multicast Routing Protocol) vs. PIM(Protocol-Independent Multicast)

Reference

宅學習(輔大)