Introduction

Size: px

Start display at page:

Download "Introduction"

绮童
5 years ago
Views:

1 Chapter 4 The Medium Access Control Sublayer 陳瑞奇 (Rikki) 亞洲大學資訊工程學系 Adapted from Computer Networks, Andrew S. Tanenbaum, Vrije University, Netherlands & Computer Networking: A Top Down Approach, Jim Kurose, Keith Ross Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, Pearson Education-Prentice Hall, The Medium Access Control Sublayer data application Application presentation Presentation session Session H: header T: trail Each may be empty. SH PH PH AH AH AH data data data transport Transport Network network LLC data MAC link physical Physical DH NH NH TH TH TH SH SH SH PH bit streams PH PH AH AH AH data data data DT OSI Reference Model 2 1

Allocation Problem Static Channelization eg.

2 The Channel Allocation Problem Static Channel Allocation e.g., static TDM Channel Dynamic Channel Allocation 3 The Channel Allocation Problem Static Channelization eg., FDM, TDM Mediumsharing Techniques Scheduled Dynamic Medium Access Control Random Access eg., Ethernet, WiFi 4 2

3 2018/10/28 Assumptions for Dynamic Channel Allocation 1. Independent traffic: N independent stations (terminals, nodes) 2. Single channel (link) 3. Observable Collisions 4. Continuous or slotted time 5. Carrier sense or no carrier sense 5 Multiple access (Medium Access Control, MAC) MS 3 (Link, Channel) MS 2 Multiple Access Medium MS 4 MS 1 MS n 6 3

4 Why do we need MAC? Contention and Collision Avoidance! ieee WirelessNet Prof. Tseng, NCTU 7 Why Do We Need MAC? Fairness!!! ieee WirelessNet Prof. Tseng, NCTU 8 4

5 Multiple Access Protocols (Random Access) ALOHA Carrier Sense Multiple Access Collision-free protocols Limited-contention protocols Wireless LAN protocols 9 ALOHA (in the 1970s) In pure ALOHA, frames are transmitted at completely arbitrary times. Stations, Nodes, Terminals 10 5

Hawaii Honolulu http://www.punjabigraphics.

6 Hawaii Honolulu The ALOHA packet radio system 檀香山 (Honolulu)

7 ALOHA (1) Stations, Nodes, Terminals Collision Time Collision In pure ALOHA, frames are transmitted at completely arbitrary times 13 ALOHA (2): Performance Vulnerable period (2t) for the shaded frame 2t Frame Frame Time 15 7

8 0.5 Throughput for ALOHA Max. throughput for ALOHA S th = at G = ½ Throughput S th Aloha Slotted Aloha G Traffic load G Slotted ALOHA: Performance Vulnerable period (t) for the shaded frame. t Deferred to next slot Frame Time 17 8

9 Comparison of Throughputs for ALOHA and Slotted ALOHA Throughput S th Slotted Aloha Aloha 2 4 G Traffic load G 6 Max. throughput for ALOHA (A) S th = at G = ½ Max. throughput for Slotted ALOHA (SA) S th = at G = 1 Notice that S th for SA is exactly 2 x bigger than S th for A Hypothesis: bec. max. duration of a collision for SA (=2T) is 2 x 8 smaller than for A (=T) 18 Carrier Sense Multiple Access (CSMA) 1-persistent CSMA (Link) Listen before transmit: If the channel is busy, the station waits until it becomes idle. Time Frame (Collision) If channel sensed idle: transmit entire frame 20 9

blogspot.com/-eh0psxikw4a/tuy1imeaiyi/aaaaaaaaaeu/pngzpdkp7s8/s1600/csma-cd.

10 Stations, Nodes, Terminals CSMA (Link, Channel) Link access Half duplex (vs. Full duplex): (Collision) nodes at both ends of link can transmit, but not at same time 21 CSMA collisions Entire packet transmission time wasted Station (Collision) Computer Networking: A Top Down Approach, Jim Kurose, Keith Ross By 清大資工系黃能富教授 22 10

11 LAN Ethernet MAC Sublayer Protocol (2) Ethernet( 乙太網路 ): LAN 廣播式傳輸 (Broadcasting) No centralized control distributed algorithm 採用 CSMA/CD 技術 : 載波感測 (Carrier Sense) Half duplex 碰撞偵測 (Collision Detection) 27 Ethernet MAC Sublayer Protocol (3) 碰撞 (collide) BEBA: Binary Exponential Backoff Algorithm Collision 32-bit jamming sequence (signal) 28 11

CSMA with Collision Detection (CSMA/CD) collisions detected within short time colliding transmissions aborted, reducing channel wastage 32-bit Jamming signal Computer Networking: A Top Down Approach,

12 CSMA with Collision Detection (CSMA/CD) collisions detected within short time colliding transmissions aborted, reducing channel wastage 32-bit Jamming signal Computer Networking: A Top Down Approach, Jim Kurose, Keith Ross By 清大資工系黃能富教授 29 CSMA/CD (Cont d) T 0 A begins transmission A B T B begins transmission A B T 0 + T Time B detects collision A detects collision just before end of transmission A A ( is the propagation time) Collision Window = round-trip delay (2 ) (2 ) (Slot time) 30 B B 12

13 Ethernet MAC Sublayer Protocol (4) The two hosts are at opposite ends of the Ethernet. Collision detection can take as long as 2. Collision Window = round-trip delay (2 ) (2 ) (Slot time) 32 Binary Exponential Backoff Algorithm BEBA Collision 32-bit jamming sequence (signal) 33 13

14 Binary Exponential Backoff Algorithm First collision: selects either 0 or 1 collision window (2 ) at random for delay. (Slot time) Second collision: waits 0, 1, 2, or 3 collision windows (selected randomly) before trying again (This is k* (2 ) for k= 0, 1, 2, 3 slots) 10th collision: randomly selects a k between 0 and (k = 0, 1, 2,, 1023 slots) 16th collision: randomly selects a k between 0 and (k = 0, 1, 2,, 1023 slots) 34 CSMA/CD Protocol Carrier Sense before transmission Carrier Sense while transmission Collision: Two or more stations transmitting simultaneously Backoff: Random delay after collision Deference: Defers transmission if channel is sensed busy Collision Window (Slot time):round-trip propagation delay time plus some carrier sense time. By 清大資工系黃能富教授 35 14

15 CSMA with Collision Detection Ethernet k slots 2 per slot 1. Quickly terminating damaged frames saves time and bandwidth. 2. CSMA/CD can be in one of three states: contention, transmission, or idle. 3. Collision window = slot time = 2 (2 ) 4. Half duplex 36 Ethernet (IEEE 802.3) (using CSMA/CD) Physical layer (Manchester Encoding) MAC sublayer protocol Ethernet performance Fast Ethernet Gigabit Ethernet 10 Gigabit Ethernet IEEE 802.2: Logical Link Control Retrospective on Ethernet 39 15

10 Mbps 100 Gbps Computer Networking: A Top Down Approach,

16 Ethernet (IEEE 802.3) Most successful local area networking technology of last 30 years. First widely used LAN technology Kept up with speed race: 10 Mbps 100 Gbps Computer Networking: A Top Down Approach, Jim Kurose, Keith Ross By 清大資工系黃能富教授 40 Classic Ethernet Physical Layer Architecture of classic Ethernet

17 Ethernet (10Base5) Broadcast( 廣播 ) Terminators By 清大資工系黃能富教授 42 Ethernet (IEEE 802.3) DEC, Intel, and Xerox (DIX): 10Mbps Ethernet in 1978 Standard: IEEE Mbps version: Fast Ethernet 1000Mbps version: Gigabit Ethernet 10 Gigabit Ethernet 100 Gigabit Ethernet Connectionless & Unreliable 43 17

IEEE Project 802 Network 802.11 CSMA /CA WCB/McGraw-Hill The McGraw-Hill Companies, Inc.

18 IEEE Project 802 Network CSMA /CA WCB/McGraw-Hill The McGraw-Hill Companies, Inc., MAC Sublayer Protocol (1) Frame formats. (a) Ethernet (DIX) (b) IEEE

19 Two segments via a repeater A repeater is a device that forwards digital signals By 清大資工系黃能富教授 46 Five segments, maximum four repeaters 2500m = 2.5km By 清大資工系黃能富教授 47 19

20 Collision Window Collision Window = round-trip delay (2 ) (2 ) Consider that a maximally configured 10 Mbps Ethernet is 2500 m long, and there may be up to four repeaters between any two hosts, the round trip delay (2 ) has been determined to be 51.2 us (512 bit time) 10 Mbps x 51.2 us = 512 bits = 64 bytes Minimal frame size = 64 bytes to distinguish from collision 48 Ethernet MAC Sublayer Protocol (5) 偵測碰撞 (collision detection) (512 bit time) 1. RTT(Round Trip Time) < 51.2us (2 ) 2. Frame( 訊框 ) 大小 >= 64 bytes 以 10Mbps 計算 10 7 x51.2x10-6 =512 bits = 64 bytes 3. Frame( 訊框 ) 大小 <= 1518 bytes 為免某工作站佔用傳輸媒介太久 ( 公平 ) 3. 網路最大長度約 2500 公尺 49 20

21 Ethernet Cabling The most common kinds of Ethernet cabling. 50 Ethernet Cabling (2) Three kinds of Ethernet cabling. (a) 10Base5, (b) 10Base2, (c) 10Base-T

最多 100 部電腦 52 10 Base2 Ethernet 最長 185 公尺 Bus Topology(

22 10 Base5 乙太網路 RG 11A/U 同軸電纜最長 500 公尺 50 歐姆終端電阻收發器收發器收發器 50 歐姆終端電阻 [Transceiver] [Transceiver] [Transceiver] 最多 100 部電腦 Base2 Ethernet 最長 185 公尺 Bus Topology( 匯流排拓樸 ) RG 58A/U 同軸電纜 50 歐姆終端電阻 50 歐姆終端電阻最多 30 部電腦 53 22

RJ-45 接頭 RG 58A/U 同軸電纜 50 歐姆終端電阻 50 歐姆終端電阻最多 30 部電腦

23 Repeater( 中繼器 ) A repeater is a device that forwards digital signals 這台中繼器正面具有光纖和 BNC 接頭翻到背面, 則可看到 2 個 RJ-45 接頭 RG 58A/U 同軸電纜 50 歐姆終端電阻 50 歐姆終端電阻最多 30 部電腦 55 A Repeater: Layer 1 device 185m 10Base2 185m 56 23

24 10 BaseT Ethernet Hub (a multiway repeater) 集線器 (Hub) UTP 線最長 100 公尺.. PC PC PC PC Star Topology( 星狀拓樸 ) 57 集線器 (Hub): 延長通訊距離多台主機或網路設備之連通 Layer 1 設備, 不具 MAC 位址過濾能力本設備所連接網路屬相同碰撞領域 (Collision Domain) 及相同廣播領域 (Broadcast Domain) 常見於公司小部門或學校電腦教室之內部網路 58 24

Ethernet MAC Sublayer Protocol (6) 碰撞領域 (Collision Domain) 僅由第一層設備所連結之網路屬相同碰撞領域頻寬由此領域所有節點分享 ( 同一時間只有一個節點會成功傳送資料 ) 10Mbps Ethernet 同一碰撞領域任兩節點距離需 <2500 公尺, 若所接集線器較多, 則距離更應縮短 Hub

25 Ethernet MAC Sublayer Protocol (6) 碰撞領域 (Collision Domain) 僅由第一層設備所連結之網路屬相同碰撞領域頻寬由此領域所有節點分享 ( 同一時間只有一個節點會成功傳送資料 ) 10Mbps Ethernet 同一碰撞領域任兩節點距離需 <2500 公尺, 若所接集線器較多, 則距離更應縮短 Hub 會有延遲, 故以 51.2 us 為訊號來回時間為考量若是 100Mbps Fast-Ethernet, 同一碰撞領域任兩節點距離需 <250 公尺 59 3 合 1 網路卡這種網路卡具有 3 種接頭, 可接 3 種纜線, 因此稱為 3 合 1 網路卡 10BaseT 10Base5 10Base2 (RJ-45) (AUI) (BNC) 60 25

26 網路介面卡 Adaptor (network interface card, NIC): 每張網路卡都有一個唯一的硬體位址, 叫做 MAC 位址 61 MAC 位址格式由 IEEE 管制 OUI (MAC Prefix) 00:60:2F:3A:07:BC 62 26

27 My IP/ MAC Address/ DNS Win 9x/Me winipcfg.exe Win NT/Server/XP/7/8/10 ipconfig /all Linux ifconfig -a Solaris Arp Netstat -p 63 Winipcfg 64 27

28 65 查詢電腦 IP/MAC 的另一個方法 3. 點選 Ethernet 或區域網路 1. 網路圖示按滑鼠右鍵 2. 點選網路設定 66 28

4. 5. 07 67 Ethernet Frame Format bytes DA SA TYPE FCS

..1010) for Synchronization SFD: Start Frame Delimiter

MAC Address Packet type (16bits): the higher level protocol

bytes FCS: Frame Check Sequence (CRC-32) MAC-frame size:

29 Ethernet Frame Format bytes DA SA TYPE FCS Preamble: ( ) for Synchronization SFD: Start Frame Delimiter ( ) NET DA: Destination MAC Address DLL SA: Source MAC Address Packet type (16bits): the higher level protocol LLC-Frame: Up to 1500 bytes PAD: Padding when LLC-Frame < 46 bytes FCS: Frame Check Sequence (CRC-32) MAC-frame size: from DA to FCS Min 64 bytes to distinguish from collision Max 1518 bytes to prevent dominating bandwidth 46 LLC

Ethernet Addresses Unicast address: each adaptor recognizes those frames addressed to its address 00:60:2F:3A:07:BC Broadcast address: an Ethernet

30 Ethernet Addresses Unicast address: each adaptor recognizes those frames addressed to its address 00:60:2F:3A:07:BC Broadcast address: an Ethernet address consisting of all 1s, e.g., ff:ff:ff:ff:ff:ff Multicast address has the first bit set to 1, e.g., f0:05:7a:8b:00: Ethernet Standards 70 30

31 100 Mbps Ethernet Spec. 項目 100BaseTX 100BaseT4 100BaseFX 100BaseT2 線材雙絞線雙絞線光纖雙絞線接頭 RJ-45 RJ-45 ST MIC SC RJ-45 區段最大長度 100 公尺 100 公尺 2/10 公里 100 公尺拓樸星狀星狀星狀星狀 SC:Subscriber Connector MIC:Medium-Interface Connector BaseTX Ethernet 集線器 (Hub) UTP 線最長 100 公尺.. PC PC PC PC 所有的電腦最終都透過集線器與其它電腦相連, 而集線器到電腦的距離不得超過 100 公尺若是 100Mbps Fast-Ethernet, 同一碰撞領域任兩節點距離需 <250 公尺 73 31

項目 1000BaseSX 1000BaseLX 1000BaseCX 1000BaseT 線材光纖光纖 STP

32 Fast Ethernet The original fast Ethernet cabling. Gigabit Ethernet cabling Mbps Ethernet Spec. 項目 1000BaseSX 1000BaseLX 1000BaseCX 1000BaseT 線材光纖光纖 STP 雙絞線接頭 SC SC DB9 RJ-45 區段最大長度 550 公尺 5000 公尺 25 公尺 100 公尺拓樸星狀星狀星狀星狀 75 32

33 乙太網路家族一覽表 ( 二 ) Gigabit Ethernet 78 33

34 10 Gigabit Ethernet 802.3ae 的特點是只使用光纖只有點對點的連線一律為全雙工傳輸, 而且依應用場合, 共有如下 7 種不同實體規格 : 79 IEEE 802.2: Logical Link Control Network Packet LCC Packet Header LCC Packet CRC Physical Link (channel) (a) Position of LLC. (b) Protocol formats

35 The Medium Access Control Sublayer data application Application presentation Presentation session Session H: header T: trail Each may be empty. SH PH PH AH AH AH data data data transport Transport Network network LLC data MAC link physical Physical DH NH NH TH TH TH SH SH SH PH bit streams PH PH AH AH AH data data data DT OSI Reference Model 81 End of Chapter 4 Questions? Thank you! Computer Networks, Fifth Edition by Andrew Tanenbaum and David Wetherall, Pearson Education-Prentice Hall,

OSI OSI 15% 20% OSI OSI ISO International Standard Organization 1984 OSI Open-data System Interface Reference Model OSI OSI OSI OSI ISO Prototype Prot

OSI OSI OSI 15% 20% OSI OSI ISO International Standard Organization 1984 OSI Open-data System Interface Reference Model OSI OSI OSI OSI ISO Prototype Protocol OSI OSI OSI OSI OSI O S I 2-1 Application