chapter 12

DSL

• Uses existing telephone infrastructure
• up to 8Mbps downstream, 1Mbps upstream
• dedicated physical line to telephone central office
• multiplexing by spliting the frequency

Cable Modem

• Uses cable TV infrastructure
• HFC: hybrid fiber coax
  • asymmetric: up to 30Mbps downstream, 2 Mbps upstream
• net work of cable and fiber attaches homes to ISP router
  • homes share access to router
• FDM: frequency devision multiplexing

FTTH

• Optical links from CO(central office) to the home
• Two competing optical technologies:
  • Passive Optical network (PON)
  • Active Optical network (AON): signal amplification
• Much higher Internet rates; fiber also carries television and phone services

Ethernet Internet access

• Typically used in companies, universities, etc
• 10 Mbps, 100Mbps, 1Gbps, 1Gbps, 10Gbps Ethernet
• Today, end systems typically connect into Ethernet switch

Wireless access networks

• shared wireless access network connects end system to router
  • via base station aka "access point"
• wireless LANs:
  • 802.11/g (WIFI): 11 or 54 Mbps
• wider area wireless access
  • provide by telco operator
  • ~1Mbps over cellular system(EVDO, HSDPA)

chapter 13

circuit switching

defdicated circuit per call: telephone net

End-end resources reserved for "call"

• link bandwidth, switch capacity
• dedicated resources: no sharing
• circuit-like (low delay and no loss) (guaranteed) performance
• call setup required (缺點)
  network resources divided into calls
• resource piece idle if not used by owning call (no sharing) (缺點，資源閒置)
• devided link bandwidth into "pieces"
  • frequency division
  • time division

packet switching

data sent thru net in discrete "chunks" (packet)

each end-end data stream divided into packets

• user A, B packets share network resources
• each packet uses full link backwidth
• resources used as needed
  resource contention (缺點，資源爭奪)
• aggregate resource demand can exceed amount available
• congestion: packets queue, wait for link use might loss (缺點，會掉包)
• store and forward: packets move one hop at a time (缺點，會等到封包完整抵達之後才會傳送)
  • Node receivescomplete packet before forwarding
  • Takes L/R seconds to transmit (push out) packet of L bits on to link of R bps
    • bps: bits per second
  • Entire packet must arrive at router before it can be transmitted on next link: store and forward
  • "store and forward" delay = 3L/R
  • So larger packet takes more delay, because of store and forward
    Message Segment
• piplining: each link works in parallel
• the reason why keep small packets，越小store and forward造成的延遲越低

Statistical Multiplexing
Why store and forward?

• Two key network-core functions
  • routing: determines source-destination route taken by packets
    • routing algorithms
  • forwarding: move packets from router's input to appropriate router output
  • Because of the forwarding functionality, so we need to store the entire packet
    forwarding
• Goad: move packets through routers from source to destination
• datagram network:
  • destination address in packet determines next hop
  • routes may change during session
  • analogy: driving, asking directions
• virtual circuit network:
  • each packet carries tag (virtual circuit ID), tag determines next hop
  • fixed path determined at call setup time, remains fixed thru call
  • routers maintain per-call state

Packet switching vs. Circuit switching

Packet switching allows more users to use network!

• 1Mb/s link

• each user:

  • 100kb/s when "active"
  • active 10% of time

• circuit-switching:

  • 10 users

• packet switching:

  • with 35 users, probability > 10 active at same time is less than 0.0004

Is packet switching a "slam duck winner" ?

• Great for bursty data
  • resource sharing
  • simpler, no call setup
• Excessive congestion: packet delay and loss
  • protocols needed for reliable data transfer, congestion control
• Q: How to probide circui-like behavior?
  • bandwidth guarantees needed for audio/video apps
  • still an unsolved problem (chapter 9)

chapter 14

Four sources of packet delay

1. nodal processing
   • check bit errors
   • determine output link
2. queueing
   • time waiting at output link for transmission
   • depends on congestion level of router
3. Transmission delay): (傳輸延遲
   • R = link bandwidth (bps)
   • L = packet length (bits)
   • time to send bots into link = L/R
4. Propagation delay: (物理傳播延遲)
   • d = length of physical link
   • s = propagation speed in medium (~
     $2\ast {10}^{8}m/sec$)
   • propagation delay = d/s

Nodal delay

$d_{nodal}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$

• $d_{proc}$ = processing delay
  • typically a few microsecs or less
• $d_{queue}$ = queuing delay
  • depends on congestion
• $d_{trans}$ = transmission delay
  • = L/R, significant for low-speed links
• $d_{prop}$ = propagation delay
  • a few microsecs to hundreds of msecs

Queueing delay

• R = link bandwidth (bps)
• L = packet length (bits)
• a = average packet arrival rate
  traffic intensity = La/R
• La/R ~0: average queueing delay small
• La/R ->1: delays become large
• La/R > 1: more "work" arriving than can be serviced, average delay infinite!

Packet loss

• queue (aka buffer) preceding link in buffer jas finite capacity
• packet arribing to full queue dropped (aka lost)
• lost packet may be retransmitted by previous node, by source end system, or not at all

Throughput

• throughput: rate (bits/time unit) at which bits transferred between sender/receiver

chapter 35

TCP: Overview

• point-to-point:
  • one sender, one receiver
• reliable, in-order byte stream:
  • no "message boundaries"
• pipelined:
  • TCP congestion and flow control set window size
• full duplex data:
  • bi-directional data flow in same connection
  • MSS: maximum segment size
• connection-oriented:
  • handshaking (exchange of control msgs) inits sender, receiver state before data exchange
• flow controlled:
  • sender will not overwhelm receiver

TCP segment structure

head len: header length, UDP has the hole file length
A，ACK: 當A flag on，代表acknowledgement number有效，傳送者想要確定這些byte有收到

connection managment

表示封包有被做connection management
R，RST: reset connection，重設連接
S，SYN: setup connections，設定連接
F，FIN: tear down a connection，解除連接

P，PSH: push data now, 馬上回推資料 (不太用)
U，URG: urgent data，緊急資料 (也不太用)

其實也有在用的bits，在not used裡面

not really for rdt, not for connection
E、C bit: 工程師預留做condition controll的

Urg data pointer: 當URG flag on，會從Urg data pointer這邊去指向要尋找的資料
receive window: window size for flow controll，要變慢receive window數字會變小，要變快receive window數字就會變大

sequence number、acknowledgement number: rdt用的，注意TCP是用byte為單位傳輸，not packet

chapter 41

Network layer

• transport segment from sending to receiving host
• network layer protocols in every host, router
• sending side: encapsulates segments into datagrams
• receiving side: delivers segments to transport layer
• router examines header fields in all IP datagrams passing through it

Two key network-layer functions

• network-layer functions:
  • forwarding: move packets from router's input to appropriate router output
  • routing: determine route taken by packets from source to destination
    • routing algorithms
• 比喻: 旅行
  • forwarding: 處理每一個中繼站的交換
  • routing: 預處理旅行的起點和目的地

Network layer: data plane, control plane

• Data plane
  • local, per-router funciton
  • determins how datagram arriving on router input port is forwarded to router output port
  • 處理 forwarding function
• Control plane
  • network-wide logic
  • determines how datagram is routed among routers along end-end path from source host to destination host
  • 處理 routing funciton
  • two control-plane approaches:
    • traditional routing演算法
      • distribute, locally
      • implemented in routers
    • software-defined networking(SDN)
      • centralized
      • implemented in (remote) servers

Per-router data plane

Forwarding table to allow fast output interface lookup

Network-wide logic in control plane

Traditional: Individual routing algorithm components in each and every router interact in the control plane

Logically centralized control plane

SDN: A distinct (typically remote) controller interacts with local control agents (CAs)

chapter 42

Router 架構

Input port functions

• decentralized switching:
  • using header field values,利用記憶體裡面的 forwarding table 查找 output port
• 目標: 在line speed下，完成input port處理
• queuing: if datagrams arrive faster than forwarding rate into switch fabric
• destination-based forwarding: forward based only on destination IP address (traditional) (比較快、便宜)
• generalized forwarding: forward based on any set of header field values (SDN) (比較慢，所以要更快的lookup處理，所以比較貴)
  

Switching fabrics

• transfer packet from input link to appropriate output link

• switching rate: rate at which packets can be transfer from inputs to outputs

  • often measured as multiple of input/output line rate
  • N inputs: switching rate N times line rate desirable
  • 

• three major types of switching fabrics
  

Switching via memory

first generation routers:

• 速度最慢，成本最低
  

Swtiching via a bus

• 多人傳送時有競爭
• 交換速度取決於bus的頻寬
  

Switching via interconnection network

• 每個人一個bus
  

Input port queuing

HOL問題: 第一個封包送不出去，所以影響到後面的封包

Output port queuing

• 進來速度 > 出去速度就會有queue問題
  
  

Buffer Management

• drop
  • 剛進來的先丟
  • 有優先權的話，低的先丟

Packet Scheduling: FCFS

• packet schefuling: 決定誰先傳
  • 先進先服務(FCFS)
  • 優先權
  • 輪流
  • 優先權決定服務權重
  • 
• FCFS: 就是First-in-first-out(FIFO)

Scheduling policies: priority

priority scheduling:

• 把進來的東西分等級，根據等級排順序
• 同個等級FCFS
• 

Scheduling policies: round robin

• 分等級，每個等級輪流輸出
• 

Scheduling policies: weighted fair queuing

Weighted Fair Queuing (WFQ):

• 每個等級都給服務，但服務權重不同
  

chapter 43

Network Layer: Internet

host, router network layer functions:

IP Datagram format

• ver: 版本
• head len: header 有多長，新版ipv6是固定長度
• tos(type of service): 資料欄位服務形式
• length: 包含header的長度
• 如果ip要切割的話，需要這些欄位
• time to live: 為了避免有些有問題的封包，找不到目的地，但是被一直繞送，所以每次轉送這個封包，這個欄位就會-1，當值為0，router就會把這個封包丟掉，然後告訴sender這個封包被丟掉了
• upper layer: 說明上層的欄位哪個協定處理
• header checksum: 判斷收到的封包有沒有錯誤
• source ip: 就sender ip
• destination ip: 就receiver ip
• options: 選項增加的欄位
  

IP fragmentation/reassembly

• 當從MTU比較大的網路進入到MTU比較小的網路，封包就需要切割，在router切割
• 重組只能在receiver執行
• 16bit identifier: 辨識哪些原本是同一個ip封包的
• flgs: 知道哪個ip分段是最後一個分段，辨識什麼時候結束，0代表後面沒有了，1代表後面還有
• fragment offset: 辨識切割前順序的編號，8bytes為一單位
• 
  
• 

IP addressing: introduction

• ip address: 32-bit identifire，定義到網卡上面，是定義在介面，一台機器可能會有多個ip，所以要說是某台機器的某一個介面的ip
• interface: connection between host/router and physical link
  • 通常一台router有多個介面，所以有多個ip
  • host通常只有一或兩個介面(e.g., wired Ethernet, wireless 802.11)

Subnets 子網路

• ip分為兩段，前段一樣的話代表在同一個子網路
• 互相連接的設備在同一個子網路的話不用透過router
• IP addresses have structure
  • subnet part: 設備在同一個子網路前面會有同樣的ip
  • host part: 後面那段ip會不一樣
• 

IP addressing: CIDR

CIDR: Classless InterDomain Routing

• https://aws.amazon.com/tw/what-is/cidr/
• 
• 

DHCP: Dynamic Host Configuration Protocol

動態配置ip
goal: 當host加入網路時，動態配置ip給他

• 可以租借一個ip來用，server會說可以用多久
• 允許使用以前用過的ip
• 支援加入網路的mobile用戶
  實現了少量ip服務多數人
  
  

DHCP: more than IP address

• 還會給default gateway和DNS
• first-hop router 的地址
• name and IP address of DNS server
• network mask (indicating network versus host protion of address)

IP addresses: how to get one

ISP要跟國際組織申請

chapter 62

Internet checksum

https://www.cnblogs.com/shelmean/p/16091622.html

Cyclic redundancy check CRC

除法進行時，用XOR做餘數計算

chapter 63

multiple access protocols

Multiple access links, protocols

兩種links:

• point-to-point 點對點
  • point-to-point link between Ethernet switch, host
  • PPP for dial-up access
• broadcast (shared wire or medium) 被多人共享
  • old-fashioned Ethernet
  • upstream HFC in cable-based access network
  • 802.11 wireless LAN, 4G/4G, satellite

Multiple access protocols

• 決定哪一個人哪一個節點何時傳送
• 決定發言的機制
• 用同一個頻道控制
  

理想的 multiple access protocols

用於判斷協定優缺
給定環境: multiple access channel of rate R bps

• 如果只有一個人在用，那他要可以用到全部rate R速度
• 當有M個節點要用，那平均速率要R/M
• fully decentralized(完全分散式):
  • 沒有一個特別的node去處理排程、協調、碰撞
  • 節點彼此不用同步
• simple 簡單

Random access protocols

沒有事先規劃好哪個節點在什麼時候傳送

• when node has packet to send
  • 傳送時使用完整rate R
  • 沒有排程
• two or more transmitting nodes: collision 碰撞
• random access MAC protocol 著重於:
  • 如何偵測碰撞
  • 如何解決碰撞
• examples of random access MAC protocols:
  • ALOHA, slotted ALOHA
  • CSMA, CSMA/CD, CSMA/CA

Pure ALOHA

• 幾乎沒有限制，沒有規定時間，沒有規定環境
• 很容易發生碰撞
• 發生碰撞的機率是兩個packet time，發送前、發送後
• pure Aloha 效率: 18%

Slotted ALOPHA

假設:

• 所有封包大小一樣
• 時間切成大小一樣的time slot
• nodes只能在slot開始的時候傳送
• nodes同步了
• 如果有兩個含以上在slot裡面，全部nodes都偵測到碰撞

操作:

• node要傳送只能在下一個slot開始的時候傳送
  • 沒有碰撞就成功了
  • 有碰撞就在後面的slot以機率p的方法決定傳送，直到成功

效率

優點:

• 一個人要使用可以使用全部資源
• 分散式的，但是要同步
• 簡單

缺點:

• 碰撞
• idle slots
• node可能會花很多時間在處理碰撞
• 要同步
• 很多人要用不能均分

Reference

好看影片: https://www.youtube.com/@pollyhuang
還有隔壁班老師的影片