計算機網路 趙禧綠

Introduction

  • Telecom (Tele Communication)

  • Datacom (Data Communication)

  • Course Taken

    • Computer network
    • Cellular network
    • Cloud computing
    • Programming
  • Final Projects

  • Theory

    • Algo. DataStruct.
    • Graph
    • Control Theory: TCP, load-sensitive routing
    • Queueing theory: 了解、分析網路狀況 (太複雜時無法分析)
    • Optimization
    • Game Theory
    • Information Theory: 可以算出 network properties
  • Goals

    • Overview
    • state-of-the-art
    • conduct research
  • Logistics

  • Syllabus

    • Internet arch. & proto.
    • Underlay
      • Wireless
      • Datacenter
      • SDN & NFV
      • Cloud RANs / 5G / WiGig
    • Overlay
      • Application
      • Web, streaming, p2p, distribution
      • Edge computing
    • Miscellaneous (Misc.)

Architecture

一旦網路架構定好了,當需要改變時,是很麻煩的 => 一開始設計好架構是很重要的

  • Network
    • Best-effort (最小架構,剩下的 host 端處理 ex. tcp)
    • lost, corrupted, out-of-order
  • Host
    • everything else
  • 5G
    • Broadband communications
    • Massive IoT
    • URLLC (高可靠,低延遲)
    • => 不是 best-effort
  • Congestion Control
    • 需有現在網路狀況
    • 要 low lagicy 就不一定是最短路徑,而是可能需要 ECMP
      • what rate to use for each flow?
      • 最好還是分散式架構
      • 交換資訊越少越好
    • TCP Congestion Control
    • Why TCP 不會壅塞在 host 端?
      • 3 way handsharking 時就會告知 host 的資源
  • 網路如何傳送?
    • 電訊號、電磁波
    • 大、小 功率?
      • 大: 遠、干擾、2.4GHz
      • 小: 進、5GHz、低延遲、高速
    • => 5G 取 功率小
      • 低延遲、高速
      • 高密度佈建 (0.001/m^2)
      • UDN small cell (ultra dense network)
      • small buffer (單顆不會有太多人連線) => cheap

How to Read a Paper

Foundation of Computer Networks

  • 網路需要
    • Application Programmer
    • Network Designer
    • Network Provider
  • 連線
    • Term.
      • Scale
      • Link
      • Nodes
      • Point-to-Point (PPPoE)
      • Multiple access (Switch、Hub、Bus、)
      • Packet / Circuit Switched (因為 multiple access 要處理何時誰傳 or 如何同時傳)
      • store-and-forward
        • cut through
          • 不將封包全部收進來,看到 header 後就動作了
        • S.A.F.
          • 將封包全部收進來,才開始檢查 header 後動作
    • Resource
      • link & node
      • shared link
        • Multiplexing
        • De-multiplexing
        • DM (division Multiplexing)
          • FDM
          • TDM
          • CDM
        • Statistical Multiplexing
          • Flow: 點到點
          • Resource Allocation: FIFO, Round-Robin, QoS
          • Congested
            • 加 buffer => 延遲
            • 好的 tcp congestion 會檢查 buffer 中,只有佔 queue 太多的 source 才會丟 window ack,只有送最多的 source 才需要降封包送出數,流量佔不多的其實不需要降流量
  • Reliability
    • hide error
    • bits / packets lost
    • failures
    • delay
    • out-of-order
    • eavesdrop (竊聽)
      • 軟體:加密
      • 通訊:跳頻 (frequency hopping) (HSSS, DSSS)
  • Protocols
    • Spec.: prose, pseudo-code, state transition diagram
    • Interoperable(互操作)
    • IETF(Internet Engineering Task Force): 訂定 RFC 的組織 (免費)
  • Performance
    參考
    • Bandwidth
      • 每單位時間內,可以傳送的資訊量
      • bandwidth (Hz)
    • Latency
      • propagation delay + transmit delay + queueing delay
      • propagation delay: 網路線上電子訊號跑的速度有關
      • transmit delay: 網路卡將資料傳送到網路線上 (正比於資料大小)
      • queueing delay: 經過 switch / router 中 queue 的時間
    • delay * bandwidth
    • jitter
      • vedio 或 voice
      • 抖動、時基誤差,穩定度的量化
      • 若 jitter 高,聽到的聲音可能會不穩,vedio 了化可以用 buffer 來處理,電話了化可能無解
      • 因為有了 buffer 所以現在 paper 比較少出現這種

Connected in LAN

沒有 routing

  • 分散式 media access control (避免訊號碰撞)
  • control frame
  • framing (data 內部要塞什麼)
  • Link Capacity
    • Shannon-Hartley Theorem: \(C = B * log_2(1+S/N)\)
      • B:bandwidth
      • S:signal
      • N:noice
    • capacity 代表是理論值
  • Links
    • medium
    • frequency
      • 影響 S (接收訊號)
      • F 高 => B 會增加 => 可是受干擾的影響大 => 距離要大
    • encoding: 把 binary 資訊放到 signal 上
    • Modulation: 調變 (MAC 層)
      • 一個 signal 可以傳送多個 data 意義
      • 可以改變 振幅、相位、頻率、
      • ex. 將振幅切成四個等級,一個振幅可以代表不只一個訊息
      • ex. BPSK, QPSK, 16QAM, others
  • encoding
    • NRZ (none-return-to-zero)
    • 中間才是 0
    • 問題:
      • 電腦不同不:當出現一連串的 0 或 1 時,A 電腦可能以為是 3 個 0,B 電腦可能以為是 4 個 0
      • 機械漂移:因為電壓是相對的,所以其實 baseline 是用平均算出來的 => 當收到的資訊愈多,baseline 就會漂移
    • NRZI (Non Return to Zero Inverted)
      • 0 電壓不改變
      • 1 電壓改變
    • Manchester
      • 只有中間有改變
      • 0 低到高電壓
      • 1 高到低電壓
      • 目前使用最普遍的
    • 4B/5B encoding
      • 根據 spec. 若有連續 n 個 0/1,用其他 encode 代表之
      • no more than one leading 0(zero) and no more than two trailing 0’s
      • No pair of 5-bit codes results in more than three consecutive 0’s
      • 有 table 可以參考
  • Framing
    • byte 為單位
      • BYSINC、PPP、DDCMP
    • bit 為單位
      • HDLC
  • Error
    • Detection
      • kind
        • CRC (Cyclic Redundancy Check) => 用晶片做
        • Checksum (IP) => 軟體作
    • Correction
    • Re-send
  • Reliable
    • 要確保可靠傳輸
    • ARQ (Automatic Repeat Request)
    • kind
      • stop and wait
        • ACK / NAK
        • timer (timeout) (seq number)
      • go back N
        • 一次送多個
        • sliding window
        • 第 n 個錯了話,從第 n 個開始全部重送
        • 對 receiver 的 buff 好作,不需要紀錄送錯的 packet 以及之後的 packet
      • select repeat
        • 第 n 個錯了,只重送第 n 個
        • receiver 的 buff 要記住對的 packet 與位置
    • seq no 要多長?
      • stop & wait 只要 0 與 1,有交錯就是正確執行,有連續就是 seq 有問題
      • \(SWS < (MaxSeqNum + 1)/2\)
    • Flow Control
      • 在 ack 裡回復 window 要開多大
      • if connection 多 => window 要減小 => 把 buffer 平均分攤
  • 監聽 channel busy
    • 1-persistent protocol
      • 聽到 channel 空的就直接送
      • ethernet 使用
      • 碰撞機率高 but 因為 ethernet 有辦法煞車 (可以邊送邊聽) (CSMACD)
      • wifi 因為無法煞車 => 不能使用 (CSMACA)
      • 適合較少用戶之網路(較激進的使用)
    • non-persistent
      • 若 channel 使用中,就不監聽 => 停一個隨機的數字後,再一次監聽
      • 適合高使用率網路
    • p-persistent
      • p 的機率送,1-p 的機率不送,p 以網路的狀況決定
      • p 不好預測 (也許可以用 AI 處理)
  • 543 規則
    • 5 個網域
    • 4 個 repeater: 太多雜訊會提高
    • 3 個電腦群體
  • TXOP
    • transmition oppotunity
    • 時間單位
    • 每次搶到 channel 有這麼長的時間可以使用
    • 原本只有一個 frame/ack 就要重新搶 channel,現在因為 throughput 變大了,所以開始允許使用多一些時間,利用 TXOP 來決定可以使用多久
    • ip / mac 都有 unicast / multicast / broadcast
  • Wireless
    • 要做調變 (用 震幅/角度/ 來放入不同資訊)
    • broadband 寬頻通訊
    • header 一定是用最慢的速度傳輸 (電磁波角度)
    • payload 會比 header 快很多 => packet aggregation: 將 payload 結合起來,讓 payload 很常,避免每次傳一個 frame 都要浪費時間在傳 header
  • Wireles
    • FHSS
    • DSSS

L3 Internetworking

  • virtual circute
    • ATM Switch
    • MPLS
    • VCI / VPI
    • 打 lable 代替看 L2 mac address
    • 需要先建立虛擬路徑,只有 local 知道
    • 先建立 local forwarding rule,多一個路徑建立時間 but 跑的時候比較快
    • circute switch 的概念
    • 不收的時候會 tear down
      • 早點資源釋出
      • tear down 後,memory 已經沒有資料了,因此無法回復前一個 switch 說我丟包了
  • Source Routing
    • 看 source
    • ex. PBR
    • static vs loose
  • switch vs bridge
    • switch: learning switch protocal
    • bridge: flooding
  • Reduntency
    • TOS 只放 n 選 1
  • fragment
    • Router 只做 fragment 不做 reassemble
    • 但是,如果要求重送,因為可能 H8 重要第二個 frame,可是 H5 送的時候明明只有一個 frame,無從知道 frame 2 是誰,所以後來實作時,都是先要求 MTU 多少,在統一用這個 MTU 來送資料
    • 如果 rerouting 時,path MTU 要重要求 (Maximum transmission unit)
  • Class
    • A 1/2
    • B 1/4
    • C 1/8
    • D 群播 (multicast):指定 multicast ip
    • E 保留 / 實驗
    • CIDR: 沒有 class 概念

End-to-end protocols

TCP

  • 希望實現可靠的通訊

  • Connection establish

  • Resend

    • relay on ACK / timeout / mss 塞滿
  • Connection termination

  • Flow control

    • 希望 sender 不要 overrun (不要送超過對方的 buffer -> 掉封包)
    • slow start
    • reciver 透過 windows size 告知 sender 我的 buffer size 多少
  • Timer

    • 如何設定 resend 的 timeout 長度
      RTO(Retransmission Time Out)
    • 需要比 來回 時間還長
      • 太小: 其實有收到,但是重傳了
      • 太大: 很晚才重傳
    • 設定方法:
      • Average Round-Trip Time (ARTT)
        • TCP 內包含 reciver 回 ACK 時的系統時間
        • sender 可以知道 來回時間
        • 用此來預測下一個 ARTT
          • \(ARTT(k+1) = \frac{K}{K+1} ARTT(K) + \frac1{K+1} RTT(K+1)\)
          • RTT: 此次 來回時間
        • RFC 793
          • Smoothed RTT
          • 原方法每次的比重都一樣
          • 應該越近的比重越重
          • \(SRTT(k+1) = \alpha * SRTT(k)+(1-\alpha) * RTT(k+1)\)
          • SRTT 可以表示現在的網路狀況,那 timeout 時間應該要比他大,但是要大多少呢?
          • \(RTO=SRTT + \Delta\)
          • 原來以為 \(\Delta\) 可以是參數 => 發現也要隨著網路狀況而改變
          • \(RTO(k+1)=min(UBound, max(LBound,\beta*SRTT(k+1))\)
    • 造成 RTT 大改變的原因
      • data transmission time
      • queuing time (Router)
      • reciver 的 waiting time (reciver 會想包裝一定的資訊量再重傳)
      • 另外一種 RTO 的算法
        • Jacobson’s Algorithm (RFC 2988)
        • 利用 error 來調整
        • Standard RoundTrip Time
        • Standatd
    • 如果封包沒有回來 (掉包 or 前面的還沒回來而已)
      • 把現在的 RTO 變兩倍 (binary exponential backoff)
      • 凡重送後成功的封包得到的間隔時間不算入 RTT 中
        • 因為其實也有可能是第一次就成功的,只是真的送的很久,TCP 無法分辨是第一個的 ack 還是重送的 ack
    • Karn's algorithm
      • 由於無法分別在Re-transmit後,回來的ACK是原ACK還是Re-transmit後之ACK
        故選擇不將其納入RTO之計算中
        • 在重傳過程結束後,後面進行的成功傳送才納入計算
          • K+1成功重傳 回傳ACK(K+2)
          • K+2成功傳送 回傳ACK(K+3)
            • 此參數才可納入RTO計算
  • tcp congestion control

    • 看網路壅塞狀況
      • TCP 是第四層,網路狀況是二、三層,對 TCP 其實不好偵測
      • IP 曾有些東西也許可以幫忙,but 可能比較沒有效率
        • ICMP Source Quench message: Router 可以透過 ICMP 叫某些 sender 不要送
          • sender 不一定會聽
        • RSVP may help but not widely implemented
    • 作法
      • slow start (RFC 2581)
        探索(probe)網路最大能力
        • Basic:
          • awnd = allowed window in segments
            awnd = min[credit, cwnd] (擇小的)
          • cwnd = congestion window in segaments
            當每個新的connection成功收到ACK,則新增一connection
            直到loss
            • 指數成長
          • credit = amount of unused credit granted in most recent ACkK in segments (= window/segment size)
        • 一直往上漲,但是不能無限上綱 => 在 flow control 的 limit 停止
        • 同樣 flow control 也要停止在 congestion control
      • Congestion avoidance
        • dynamic windows sizing on congestion
        • 基本上是用 congestion windows 來處理 (單位: segments) (TCP 是用 byte 為單位,單位不同)

        • 與slow start不同於,他會將爆掉發生的cwnd數除二
          設為下個循環的thershold
          到thershold時從指數轉為線性成長
      • Fast Retransmition
        • 加速 Slow start
        • 當 segment 丟掉後,會要重傳,可是如果又收到 duplicate 的 ack,就知道網路不是壅塞,而是掉包
        • 這時候掉下來的 cwnd 不應該回到 1 重測
      • Fast recovery
        • 因為知道是掉包,而不是壅塞
        • 收到 n duplicate ACK 後
          • ssthresh = cwnd / 2 畢竟還是有緩慢
          • cwnd = ssthresh + n
          • 確定進到下一個 windows 時,(掉包的重傳正確後),回到原來的 TCP 機制 cwnd = ssthresh
    • TCP 版本
      • TCP Tahoe
        • slow start
        • congestion avoidance
        • timeout
      • TCP Reno
        • slow start
        • fast retransmission
        • fast recovery
      • TCP Vegas
        • 看packet delay
          • accurate RTT
        • New retransmission mechanism
        • Modified slow start
          • 看其他 RTT

RTP

RTP

Real Time Transport Protocol

  • 不綁定 IP
  • TCP 不適合用在 real time distributed: 同一個內容,收件者有多人,ex. 多人視訊
  • TCP 對 real time 不友善,UDP 沒有時間資訊
  • RFC 1889, 3550
  • Require
    • 需要知道 payload 格式、payload ID
      • 跟 application 綁定
    • seq number
    • time stamp
  • 如果要有 QoS,需要有 RSVP、MPLS (預留頻寬)
  • RTCP
    • RTP 是 data plane
    • RTCP 是 control plane
    • 週期性的
Select a repo