Principle
- Router and Router 間為一個 link
- error detection, correction
- sharing a broadcast channel (使用單一通道傳送資料): multiple access
- link layer addressing
- reliable data transfer, flow control
Content:
+ Link Layer Services
+ Techniques for Error Detection
+ Multiple Access Links and Protocols
+ MAC address and ARP (位址解析 protocol)
+ Ethernet
+ Hub and Switch
+ Point to Point
+ Virtualization
+ ATM
+ Multi-protocol label switching (MPLS)
+ Reference
Link Layer Services
Framing (打包)
- encapsulate datagram into frame, adding header, trailer
Trailer: 包含錯誤檢查碼
- ‘physical addresses’ used in frame headers to identify source, destination => different from IP address!
Link access
- Media access control (MAC) protocol
- Coordinate the frame transmissions of many nodes if multiple nodes share a medium
Reliable delivery between adjacent nodes
- Timeout 重送等等
- Rare used on low bit error link (fiber, some twisted pair)
- Always used on wireless links: high error rates => Correct an error locally at link level
More
- Flow control
- Error Detection, Error Correction
- Half-duplex (能互送 + 不能同時送) and full-duplex (能互送 + 能同時送)
Techniques for Error Detection
- Parity checks
- Checksumming methods
Checksumming methods => used at transport layer only
- Cyclic redundancy checks
Multiple Access Links and Protocols
Two types of “links”:
- point-to-point
- broadcast (shared wire or medium)
point-to-point
- PPP (point-to-point protocol) for dial-up access
- point-to-point link between Ethernet switch and host
broadcast (shared wire or medium)
- traditional Ethernet
- upstream HFC (Hybrid fiber coaxial cable)
- 802.11 wireless LAN
Multiple Access protocols
- single shared broadcast channel => 只有一個通道，所以大家一起送資料的話會發生衝撞 (collision)
- MAP => 決定誰可以送
- 但是是在同一條通道上決定，沒有另外開通道 (no out-of-band channel for coordination)
- 方法：TDMA (切時間), FDMA (切空間), Random Access, Taking-turns (802.5, 大家輪流)
Random Access: E.g. slotted ALOHA (from 夏威夷大學, 應該已經被淘汰), ALOHA, CSMA (送資料前先聽聽看), CSMA/CD, CSMA/CA
Taking-turns: E.g. polling, use token run on cycle
MAC address and ARP (位址解析 protocol)
MAC address
- 又稱 LAN or physical or Ethernet address
- 資料在 router 間傳送是靠 MAC address 不是靠 IP address
- 48 bit (vs. IP address 32 bit)
- 通常不可變更
- 若要廣播 = FF-FF-FF-FF-FF-FF (48個1)
- administered by IEEE
- 有一部份的 bit 代表來自哪個廠商
How to determine MAC address of B knowing B’s IP address? (如何知道目的地的 MAC address?)
- Use ARP Table: IP/MAC address mappings for some LAN nodes
Address Resolution Protocol (ARP)
- A wants to send datagram to B, and B’s MAC address not in A’s ARP table.
- A broadcasts ARP query packet, containing B’s IP address
=> Destination MAC address = FF-FF-FF-FF-FF-FF
=> all machines on LAN receive ARP query (大家都要收)
3. B receives ARP packet, replies to A with its (B’s) MAC address
4. A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out)
=> soft state (持續更新 table): information that times out (goes away) unless refreshed
ARP is “plug-and-play”: nodes create their ARP tables without intervention from net administrator (不受 administrator 干預)
一個傳送的例子
Ethernet
- 802.3
- dominant wired LAN technology => cheap, fast
- Unreliable, connectionless service
- Use CSMA/CD
Ethernet CSMA/CD algorithm
- Adaptor receives datagram from network layer and creates frame
- If adaptor senses channel idle, it starts to transmit frame. => If it senses channel busy, waits until channel idle and then transmits
- If adapter transmits entire frame without detecting another transmission, the adapter is done with frame !
- If adapter detects another transmission while transmitting, aborts and sends jam signal
jam signal: make sure all other transmitters are aware of collision; 48 bits; (讓他撞得更嚴重點)
5. After aborting, adapter enters exponential backoff: after the nth collision, adapter chooses a K at random from {0,1,2,…,2m-1} where m = min(n, 10). Adapter waits K*512 bit times and returns to Step 2
exponential backoff = 等等在 try 一次
Manchester encoding
- 在 Ethernet 上的編碼
- Used in 10BaseT, 10Base2
- Each bit has a transition — 1: up to down, 0: down to up
- Allows clocks in sending and receiving nodes to synchronize to each other
=> no need for a centralized, global clock among nodes! (clock 和 data 混合在一起)
- Hey, this is physical-layer stuff!
Hubs
- physical-layer repeaters (訊號放大器)
- 沒 buffer (switch 做)
- collision can be happened
- no CSMA/CD
Switch
- 應該可以說是 Hub EX
- Link layer device (不看IP但會處理 MAC)
- smarter than Hub
- one switch multiple port = multiple MAC
- 檢查 source 的 MAC address
- Use CSMA/CD protocol
- 隨插即用，不需要設定
- self-learning
- Switches 可以彼此連結
Switches vs. Routers
- Both store-and-forward devices
=> Routers: network layer devices (examine network layer headers)
=> Switches are link layer devices
- Routers maintain routing tables, implement routing algorithms
- Switches maintain switch tables, implement filtering, learning algorithms
Institutional network
IP subnet = broadcast domain (若廣播所有藍色內的 host 都收得到)
Point to Point
- no MAC address
Point to point protocol (PPP, RFC 1557)
- packet framing (有自己的 data frame): encapsulation of network-layer datagram in data link frame
=> carry network layer data of any network layer protocol (not just IP) at same time
=> ability to demultiplex upwards
- bit transparency: must carry any bit pattern in the data field
- error detection (no correction)
- connection liveness: detect a link failure, signal link failure to network layer
- network layer address negotiation: endpoint can learn/configure each other’s network address
- no flow control (降低複雜度)
Virtualization
What is virtualized?
- two layers of addressing: internetwork and local network
- new layer (IP) makes everything homogeneous (一致) at internetwork layer
- underlying local network technology (網路層下層不再重要)
=> cable, satellite, 56K telephone modem (早期), today: ATM, MPLS
=> … “invisible” at internetwork layer. Looks like a link layer technology to IP!
ATM (Asynchronous Transfer Mode)
- 設計時屬網路層，現在算是連接層
- 1990年代一個標準
- 當時目標: integrated, end-to-end transport for carrying voice, video, data
- 有timing, QoS (Internet 沒有 => best-effort)
- 連線之前要建連線
- 傳送最小單位: a cell => 5 byte ATM cell header + 48 byte payload
- Virtual circuit transport
- 傳送看 VC identifier (hot destination ID)
- 兩大類: Permanent VCs (long lasting), Switched VCs (動態)
ATM Adaptation Layer (AAL)
- “adapts” upper layers (IP or native ATM applications) to ATM layer below
- AAL present only in end systems (網段末端的 Router), not in switches
- AAL layer segment (header/trailer fields, data) is fragmented across multiple ATM cells
類比: TCP segment is fragmented in many IP packets
ATM cell
- In ATM layer (under AAL Layer)
- 5 byte ATM cell header + 48 byte payload
Multi-protocol label switching (MPLS)
- 建連線
- 不看 IP address 看 label (也不看 MAC)
- 應該也是被 Ethernet 幹掉
Reference
[1] 黃能富教授 — 計算機網路概論: https://www.youtube.com/playlist?list=PLS0SUwlYe8czNZ9rRVFwp-5we8oEoVN0D
[2] 黃能富教授計算機網路概論講義https://drive.google.com/drive/folders/1qGWvoR6cvZgb_AfKCPQXvk9mEOQQVjlU (私人連結)