計算機網路(下)

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
    1. 包含
      • 路徑
      • VC number
      • 路徑上所有router的forwarding table index
    2. performance-wise
    3. 三個階段:
      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

宅學習(輔大)