Chapter 4. The Medium Access Control Layer

4. The Medium Access Control Sublayer Broadcast networks and protocol Broadcast channels 어떤 channel을 동시에 사용하고자 할 때, 누가 그것을 사용하도록 하는가를 결정하고, 그러한 결정을 어떻게 하는가의 여부가 가장 중요한 문제 Multiaccess channels Random access channels MAC (Medium Access Control) Sublayer

4.1. The Channel Allocation Problem (1/2) In LANs and MANs Static Channel Allocation Dynamic Channel Allocation

4.1. The Channel Allocation Problem (2/2) LAN의 특징 반경이 수 km 이내 수 Mbps의 전송속도 하나의 기관이 소유 LAN의 필요성 To connect existing machine together The superior price/performance ratio of a network of workstations LAN의 특성 High bandwidth Simpler protocols Easier implementation High reliability

4.1.1. Static Channel Allocation in LANs and MANs FDM : A small and fixed number of users, each of those has a heavy traffic cf. Computer system : bursty traffic Performance of FDM (approximation) Average delay : T [sec] Channel capacity : C [bps] Arrival rate : [frame/sec] Frame size : [bit/frame] Service rate : [frame/sec] Traffic intensity :

4.1.1. Static Channel Allocation in LANs and MANs Little’s Theorem FDM의 average delay 각 subchannel의 capacity : Average arrival rate : 하나의 high bandwidth로 서비스하는 것보다 여러 개의 low bandwidth로 서비스하는 것이 평균 delay 특성을 나쁘게 한다. TDM도 유사한 특성

4.1.2 Dynamic Channel Allocation in LANs and MANs 1. Station model N개의 독립 stations arrival rate = 시간 동안 새로운 frame이 생성될 Probability : station 에는 no buffer 2. Single channel assumption All stations are equivalent all stations can transmit and receive from a single channel 3. Collision assumption All stations can detect collision Collision 외에는 error가 발생하지 않는 것으로 가정

4.1.2 Dynamic Channel Allocation in LANs and MANs 4. a. Continuous time Frame 전송이 언제 어느 순간에나 시작될 수 있음 Master clock이 존재하지 않음 4. b. Slotted time master clock, discrete intervals 0 : idle, 1 : successful transmission, 2 이상 : collision 5. a. Carrier sense 송신 전에 carrier를 감지 빈 channel이 생길 때까지, station은 channel을 사용하기 위해 시도하지 않음 5. b. No carrier sense 전송을 시도하고 전송의 성공여부만 나중에 결정

4.2. Multiple Access Protocols ALOHA Carrier Sense Multiple Access Protocols Collision-Free Protocols Limited-Contention Protocols Wavelength Division Multiple Access Protocols Wireless LAN Protocols

4.2.1 ALOHA Uncoordinated users are competing for the use of a single shared channel Pure ALOHA vs. slotted ALOHA Pure ALOHA : 모든 frame들이 반드시 맞춰지는 discrete slot으로 나누므로, synchronization이 필요하지 않음 cf. slotted ALOHA : synchronization이 필요

< Pure ALOHA (1/5) > ALOHA system의 basic idea Transmit any time and listen the feedback signal whether it was collided or not. 충돌 시 random amount of time을 기다리도록 한다. Contention system Uniform frame size → maximum throughput Fig 1. In pure ALOHA, frames are transmitted at completely arbitrary times.

< Pure ALOHA (2/5) > ALOHA channel의 efficiency Infinite population of users Poisson distribution : S [frames/frame time] S > 1 : overflow 0 < S < 1 : reasonable throughput Old (retransmission) and new combined transmission Poisson distribution : G [frames/frame time] Low load : S ≈ G High load : G > S

< Pure ALOHA (3/5) > Throughput Offered load : G The probability of a transmission being successful : Ps The probability that k frames are generated during a given frame time since Poisson distribution The probability of zero frame :

< Pure ALOHA (4/5) > Vulnerable period : frame time의 2배 The probability of no other traffic being initiated during the entire vulnerable period Fig 2. Vulnerable period for the shaded frame.

< Pure ALOHA (5/5) > Throughput : Maximum throughput은 G=0.5 일 때, Fig 3. Throughput versus offered traffic for ALOHA systems.

< Slotted ALOHA (1/2) > Transmission at the beginning of the slot vulnerable period is reduced to one frame time Maximum throughput은 G=1 일 때, Fig 3. Throughput versus offered traffic for ALOHA systems.

< Slotted ALOHA (2/2) > Frame이 충돌을 피할 확률 : k 번의 시도를 통해 전송이 성공할 확률 : Geometric distribution Expected number of transmission E

4.2.2. Carrier Sense Multiple Access Protocols Persistent and Non-persistent CSMA CSMA with Collision Detection (CSMA/CD)

< Persistent and Nonpersistent CSMA (1/3) > Fig 4. Comparison of the channel utilization versus load for various random access protocols.

< Persistent and Nonpersistent CSMA (2/3) >

< Persistent and Nonpersistent CSMA (3/3) > (a) 1-persistent CSMA 만약에 channel이 idle하면 1의 확률로 전송 (b) Non persistent CSMA Channel이 busy 할 때 wait : random amount of time 특성 : better channel utilization, longer delay (c) p-persistent channel : Applies slotted channel If channel is idle : it transmits with a probability p 즉, 확률 q= 1- p로서 다음 slot까지 전송을 연기 이 때 다른 station이 transmit하면 (collision이 일어난 것과 같이) random amount of time을 기다림 If channel is busy : slot이 idle 할 때까지 기다림

< CSMA with Collision Detection (1/2) > Station abort their transmission as soon as they detect a collision Contention, Transmission, Idle periods가 존재 full cable propagation time (τ)의 2배 즉, 2τ 동안은 Collisions이 발생했는지 들을 수 없다. : worst case Seized the channel 모든 station들이 transmission 하는 것을 알고 방해 안 하는 경우 Slotted ALOHA의 경우 Contention interval : 2τ → slot width 두 개의 0 volts의 충돌은 detect 할 수 없으므로 Manchester encoding Manchester encoding : Ethernet에서 설명

< CSMA with Collision Detection (2/2) > Fig 5. CSMA/CD can be in one of three states: contention, transmission, or idle.

4.2.3. Collision-Free Protocols Reservation protocol Bit map protocol Binary countdown

< Bit map protocol > Reservation protocol N stations → N bits contention period Station j가 송신할 것이 있으면, j 번째 slot을 1로 예약 Data size : d bits Fig 6. The basic bit-map protocol.

< Bit map protocol > Low traffic의 경우 : contention period의 반복 Average waiting time Low numbered station : 1.5N slots High numbered station : 0.5N slots The mean for all stations is N slots Efficiency : High traffic의 경우 : 모든 station이 보낼 것이 있다고 가정 Frame의 평균 delay :

< Binary countdown > Bit map protocol의 문제점 : station 당 overhead가 1bit Binary countdown Channel을 사용하기 원하면, station은 자신의 주소를 binary bit string의 형태로 높은 순위의 bit부터 보냄 Boolean OR 연산을 통해, 높은 주소를 가진 station이 전송을 시도하는지 확인 Channel efficiency : d/(d+log2N) Fig 7. The binary countdown protocol. A dash indicates silence.

4.2.4. Limited-Contention Protocols Low load의 통신 환경에서 적합 Delay를 줄일 수 있음 ex. Pure ALOHA 또는 Slotted ALOHA Traffic이 많아지면, 채널 중재를 위한 overhead가 커짐 Contention free protocol High load의 통신 환경에서 적합 channel efficiency가 좋음 Traffic이 줄어들면, delay가 길어짐 따라서, Limited contention protocols 적용 The Adaptive tree walk protocols

< Symmetric한 경우 Performance (1/2) > Contention protocol에서 모든 station이 동일한 확률로 채널 점유를 시도하는 방식 k 개의 stations : 각 station은 확률 p의 전송 확률을 가짐 어떤 station이 주어진 slot에서 성공적으로 채널을 획득할 확률은 따라서, 최적의 p 값을 찾기 위해서, p에 대해서 미분하고 결과가 0이 되는 p 값을 찾으면,

< Symmetric한 경우 Performance (2/2) > Fig 8. Acquisition probability for a symmetric contention channel. Station의 수가 줄어들어 경쟁이 줄어들면, 한 station이 channel을 확보할 확률은 늘어난다. Station이 늘어나면, 확률은 1/e에 근접한 값으로 떨어진다.

Limited contention protocol Station들은 group으로 나눔 Group 0의 station들은 slot 0에서 경쟁 Group 1의 station들은 slot 1에서 경쟁 이와 같은 식으로 group을 나눔 낮은 traffic에서는 한 slot에 많은 station을 할당 높은 traffic에서는 적은 station을 할당하여 경쟁하도록 함 하나의 slot에서 1개의 station이 경쟁 : 충돌이 발생하지 않음 Contention-free protocol : binary countdown 하나의 slot에서 2개의 station이 경쟁 각 station의 전송 확률이 p라면, 충돌 확률은 p2. p가 작은 값일 때, 무시할 수 있음 하나의 group이 모든 station을 포함 Slotted ALOHA Traffic load에 따라, slot에 station을 동적으로 할당

< Adaptive Tree Walk Protocol > Binary tree Frame을 전송하고자 하는 station은 모두 leaf node ‘Slot 0’에서는 모든 station이 경쟁에 참가, 하나의 station만 보내려고 하면 충돌 없이 전송 가능 충돌이 발생하면, ‘slot 1’에서 2 group (A, B, C, D)만 경쟁에 참가 heavy traffic일 경우 중간 level부터 점검하기 시작 Fig 9. The tree for eight stations.

4.2.5. Wavelength Division Multiple Access Protocols (1/5) Optical LAN Spectrum is divided up into wavelength bands Each station A narrow channel for control : m time slots A wide channel for data : (n+1) time slots Fig 10. Wavelength division multiple access.

4.2.5. Wavelength Division Multiple Access Protocols (2/5) 3 종류의 traffic Constant data rate connection-oriented traffic : video, voice Variable data rate connection-oriented traffic : file transfer Datagram traffic : UDP packets Communication from A to B : connection-oriented protocols 각 station은 자신의 control channel을 듣는 fixed wavelength receiver 다른 station의 control channel에 전송하는 tunable transmitter Data frame을 전송하는 fixed wavelength transmitter 자기에게 전송되는 data를 선택할 tunable receiver Wavelength tuning Fabry-Perot or Mach-Zehnder interferometer (like bandpass filter)

4.2.5. Wavelength Division Multiple Access Protocols (3/5) Station A → Station B : file transfer class 2 A의 data receiver를 B의 data channel에 tuning, 상태 슬롯 (status slot)을 기다림. 상태 슬롯은 어떤 control slot이 설정되어 있고, 비어 있는지를 알려줌 Fig. 10에서 B의 control channel 중 4번째(0, 4, 5 : empty) slot에 CONNECTION REQUEST를 삽입 B는 slot 4를 할당함으로써 요청을 수락. 상태 슬롯을 통해 알림 A가 이 announcement를 보면, unidirectional connection. 이 경우, A가 two-way connection을 원하면 B가 이 동작을 반복. 둘 이상의 station들이 하나의 같은 control slot을 차지하려고 하면 failure. 각각은 random amount of time을 기다린 후 재시도. 연결이 된 후, 각 station은 수신 station에 control message 전달. “나의 data를 몇 번 째 slot에서 확인하시오.” 이 경우, 둘 이상의 송신기(A, C)가 B에게 같은 slot을 사용하려고 요청을 하면, B는 둘 중 하나를 random하게 선택 Receiver는 임의의 한 순간에 하나만 수신 가능

4.2.5. Wavelength Division Multiple Access Protocols (4/5) Constant rate traffic 각 frame 내의 같은 번째 slot을 사용 Class 3 (datagram) traffic Connection request를 요구하지 않고, 즉시 control channel에 “DATA FOR YOU IN SLOT 3” 라고 쓴다. 다음 번 frame에서 성공 하거나 실패

4.2.5. Wavelength Division Multiple Access Protocols (5/5) 변형된 형태 하나의 control channel을 모든 station이 공유하는 방법 multiple virtual channels이 하나의 physical channel로 Multiplexing n+1 data slots에 따라 각 station이 channel을 m control slots으로 나눔으로써, 각 station마다 하나의 tunable transmitter와 tunable receiver Propagation delay도 고려 DWDM (Dense Wavelength Division Multiplexing) 많은 양의 주파수를 사용하는 system

4.2.6. Wireless LAN Protocols Wireless communication : effective range가 존재 CSMA 사용의 문제점 Hidden station problem Competitor is too far away. A→B로 전송할 때, C가 A의 전송을 듣지 못하는 경우 Exposed station problem B→A로 전송할 때, C→D가 가능한데도 전송을 못하는 경우 Short-range radio waves의 경우 multiple transmission이 동시에 가능 Fig 11. A wireless LAN. (a) A transmitting. (b) B transmitting.

< MACA and MACAW (1/3) > MACA (Multiple Access with Collision Avoidance) IEEE 802.11 wireless LAN standard 통신 전에 A에서 B로 RTS (Request to Send : 30 bytes) 송신 다음에 전송될 message 길이를 포함 주변 station들이 A→B 송신 기간 중 송신 중단 B는 A에게 CTS (Clear to Send : data length 포함) 이 후, A에서 B로 data 전송 Fig 12. The MACA protocol. (a) A sending an RTS to B. (b) B responding with a CTS to A.

< MACA and MACAW (2/3) > Fig 12. The MACA protocol. (a) A sending an RTS to B. (b) B responding with a CTS to A. RTS와 CTS를 송신함으로써, 주변 station들은 주의 C는 RTS를 들으나, CTS는 듣지 못한다. B를 방해하지 않으며, CTS를 방해하지 않는 한 전송이 가능하다. D는 RTS는 듣지 못하나, CTS는 듣는다. B를 방해하지 않기 위해서, 전송을 중지한다. E는 RTS 및 CTS를 둘 다 듣는다. 동시에 RTS를 보내면 collision → binary exponential backoff algorithm

< MACA and MACAW (3/3) > MACAW : improved version Successful transmission 후의 ACK frame 추가 Carrier sensing 기능 추가 : 충돌을 줄이는 효과 (짧은 반경) Binary backoff algorithm을 각 source-destination data stream 별로 동작하게 함 각 station 별로 동작하는 것이 아님 : fairness Collision 정보는 station끼리 공유하는 메커니즘 추가 Backoff algorithm을 일시적인 문제에 대해 덜 극단적으로 대응하도록 변형

< IEEE 802 Standards > Fig 1-38. The 802 working groups. The important ones are marked with *. The ones marked with  are hibernating. The one marked with † gave up.

4.3. Ethernet (1/2) Ethernet Cabling Manchester Encoding The Ethernet MAC Sublayer Protocol The Binary Exponential Backoff Algorithm Ethernet Performance Switched Ethernet Fast Ethernet Gigabit Ethernet IEEE 802.2: Logical Link Control Retrospective on Ethernet

4.3. Ethernet (2/2) 802.3 (Ethernet) and 802.11 (wireless LAN) 서로 다른 physical layer와 MAC sublayer Same LLC (Logical Link Control) : network layer에 대해 같은 interface 제공 Ethernet에 대한 소개 : sec. 1.5.3. 설명 참고 본 장에서는 Protocol 및 high-speed (gigabit) Ethernet 소개 참고사항) 두 가지 약간 차이점이 있으나, “Ethernet”과 “IEEE 802.3”를 혼용

4.3.1. Ethernet Cabling (1/4) Fig 13. The most common kinds of Ethernet cabling. Fig 14. Three kinds of Ethernet Cabling. 10Base5 10Base2 10Base-T.

4.3.1. Ethernet Cabling (2/4) 10Base5 : Fig. 4-14 (a) Thick Ethernet, thick coaxial vampire taps : 핀이 coaxial cable의 core에 중간까지 삽입 10 Mbps, baseband signal, max. segment : 500 m Transceiver : carrier detection and collision detection Controller : input frame을 위한 buffer, 송신될 buffer들의 queue, host computer와의 DMA 전송 등을 관리 Transceiver cable or drop cable 10Base2 : Fig. 4-14 (b) Thin Ethernet BNC connection : T junction Cheap, easy to install, no hub needed Segment 당 185 m, max. 30 machines만 연결 time domain reflectometry : 미리 정해진 신호를 보내고 echo를 측정 cable connection 및 cable break check

4.3.1. Ethernet Cabling (3/4) 10Base-T : Fig. 4-14 (c) 10Base-F Hub : different wiring pattern → twisted pairs (기존의 여분의 전화선 이용) 유입되는 traffic을 buffer에 저장하지 않음 cable 손상을 쉽게 감지 station의 추가 및 제거가 매우 쉬움 Hub로부터 최대 cable의 길이가 최대 100 m 정도 기존에 설치된 회선을 그대로 사용하고, 유지보수가 편함 10Base-F Optical fiber Expensive Excellent noise immunity 멀리 떨어져 있는 건물이나 허브 사이에서 운용 가능 max. segment : 2,000 m security

4.3.1. Ethernet Cabling (4/4) Fig 15. Cable topologies. (a) Linear, (b) Spine, (c) Tree, (d) Segmented. Segment당 최대 cable 길이가 정해져 있음 : Fig. 15 (d) Repeater : physical layer device 양방향으로 신호를 수신, 증폭, 재송신 등 두 개의 transceiver 사이는 Max. 2.5 Km, Max.4개의 repeaters

4.3.2. Manchester Encoding (1/2) Fig 16. Binary encoding Manchester encoding Differential Manchester encoding. 직접적인 binary encoding 0 bit는 0 volt, 1 bit는 5 volt 신호가 모호해짐 0001000을 전송할 경우, 0010000 또는 0100000 로 오인 가능성 상이한 clock 속도에 의해 synchronization를 잃어버릴 수도 있음 Ethernet은 Manchester encoding (simplicity) 사용 Ethernet은 differential Manchester encoding을 사용하지 않지만, 다른 LANs (ex. 802.5 Token Ring) 에서 사용

4.3.2. Manchester Encoding (2/2) Fig 16. Binary encoding Manchester encoding Differential Manchester encoding. Manchester encoding 1 : 첫 번째 구간에서 높은 volt, 두 번째 구간에서는 낮은 volt 0 : binary 0 bit와는 반대로 설정 synchronization, collision detection, 2배의 bandwidth Differential Manchester encoding 1 : start에서 no transition 0 : start에서 transition complex, better noise immunity

4.3.3. Ethernet MAC Sublayer Protocol (1/4) Fig 17. Frame formats. (a) DIX Ethernet, (b) IEEE 802.3. DIX Ethernet frame format : Fig. 4-17 (a) 1. preamble : 8 bytes “10101010” 2. destination address, source address : 2 or 6 bytes 시작이 1이면 multicast (group management), 모두 1이면 broadcast Ethernet에서 multicast : 선택된 station 그룹에만 전송 Broadcast : 모든 station에게 frame 전송 local address인지 global address인지 구별 48-2 = 46 bits → 7 x 1013 global address 어떤 2개의 station도 똑같은 global address를 갖지 않도록 network layer에서 destination node의 위치를 찾음

4.3.3. Ethernet MAC Sublayer Protocol (2/4) type : receiver가 그 frame을 가지고 할 일을 알려줌. 한 machine에 동시에 여러 개의 network layer protocol이 사용될 수 있음. Kernel은 도착한 frame을 누구에게 넘겨줘야 하는지 알아야 함. 4. data : up to 1500 bytes (초기에 결정, RAM의 크기에 따라 ) destination address부터 checksum까지 적어도 64 bytes를 가져야 함. 5. pad : 0 ~ 46 bytes valid frame과 collided frame과의 구별 Frame이 짧으면 2 τ 이전에 송신이 끝나 충돌이 되었는지 모름. 10 Mbps, 2.5 km → 64 bytes Ex. Repeater delay : 50 usec 10 Mbps에서 1 bit 전송 시 100 nsec 소요 → 500 bits → 512 bits 6. checksum : 32 bit data hash code, CRC (error detection)

4.3.3. Ethernet MAC Sublayer Protocol (3/4) Fig 18. Collision detection can take as long as 2τ Frame이 최소한의 길이를 가져야 하는 이유 첫 번째 bit가 다름 frame과 충돌할 수 있을 정도의 cable 거리에 도달하기 전에 전송을 완료하는 것을 방지하기 위해 모든 frame의 송신에는 2τ 이상의 시간이 소요

4.3.3. Ethernet MAC Sublayer Protocol (4/4) DIX format과 비교해서, IEEE standard Ethernet (Fig. 4-17(b)) preamble 8 bytes 중에서 7 bytes를 preamble로, 마지막 1 byte를 Start of Frame (SOF)으로 사용. 802.4와 802.5와의 compatibility Type field가 Length Field로 바뀜. 1,500보다 작은 숫자 : length, 1500보다 큰 숫자 : Type

4.3.4. The Binary Exponential Backoff Algorithm (1/2) Collision이 발생 후 Time은 discrete slots으로 나뉨 각 slot의 길이는 worst round-trip propagation delay : 2τ Ethernet에서 허용된 최장의 path : 2.5 km, 4 repeaters Slot time : 51.2μsec, 64 bytes (512 bits) Binary exponential backoff algorithm n 번 충돌 : 0 ~ 2n-1 slot time 중 하나를 선택해서 waiting 10 번 이후 : 0 ~ 1023(210-1) slot time 중 하나를 선택해서 waiting 16 번 충돌 : give up → higher layers에서 recovery

4.3.4. The Binary Exponential Backoff Algorithm (2/2) Slot time 구간은 최대 1,023개로 제한 소수의 station들이 충돌 → low delay 다수의 station들이 충돌 → reasonable delay를 보장 CSMA/CD에는 no ack. → 개선책 성공한 transmission 후에, 첫 번째 contention slot을, ack.를 위해 reserve.

4.3.5. Ethernet Performance (1/3) Heavy and constant load k stations ready to transmit 각 station은 전송확률 p로 contention slot에서 전송 임의의 station이 channel을 획득할 확률 A A= k p (1-p) k-1 따라서, 경쟁 당 평균 slot의 개수

4.3.5. Ethernet Performance (2/3) 평균 경쟁 구간은 이므로, 최적의 frame 당 contention slot 수 : e Frame length : F Cable length : L Network bandwidth : B Speed of signal propagation : c

4.3.5. Ethernet Performance (3/3) Fig 19. Efficiency of Ethernet at 10 Mbps with 512-bit slot times.

4.3.6. Switched Ethernet (1/2) 증가하는 load를 처리하기 위해 적은 비용으로 speed의 향상 Fig 20. A simple example of switched Ethernet. Room switch high speed (수십 Gbps) backplane 4~32 plug-in line cards 각 line card는 1-8 connections (10Base-T로 host computer에 연결) 같은 card 내의 station에 전송하지 않을 경우 high-speed backplane

4.3.6. Switched Ethernet (2/2) 특징 Local on-card LAN 구성 하나의 plug-in card 내에서는 한 순간에 하나의 전송만 가능. CSMA/CD, binary backoff algorithm으로 재전송 각 card마다 독립적인 collision domain 형성 On-board RAM을 사용하는 plug-in card 각 input port는 buffered 되어, 각 card의 on-board RAM(no collision)에 저장 이 경우, card내에서 전송될 것은 직접 처리하고, 이외의 것들은 backplane을 통해 다른 card로 보내짐으로써 throughput 향상 full duplex 임의의 port는 concentrators (hub에 연결)로도 사용.

4.3.7. Fast Ethernet Ring based optical LANs : FDDI, Fiber Channel Fig 21. The original fast Ethernet cabling. Ring based optical LANs : FDDI, Fiber Channel IEEE 802.3u : Fast Ethernet Keep all the old frame formats, interfaces, and procedural rules Reduce the bit time from 100 nsec to 10 nsec 10Base-T가 기본 설계

4.3.8. Gigabit Ethernet (1/2) Fig 22. (a) A two-station Ethernet. (b) A multistation Ethernet.

4.3.8. Gigabit Ethernet (2/2) Fig 23. Gigabit Ethernet cabling. wavelength : 0.85 microns and 1.3 microns 1 Gbps는 매우 빠른 속도 → flow controls이 중요 10 Gigabit Ethernet → IEEE 802.3ae

4.3.9. IEEE 802.2: Logical Link Control (1/3) Ethernet을 포함한 802 protocols → datagram service IP packet이 802 payload field에 삽입되면 datagram service LLC : Data Link Layer 내의 MAC 윗 단 Error control, flow control → HDLC와 유사 각종 802 frame들을 하나의 통일된 format으로

4.3.9. IEEE 802.2: Logical Link Control (2/3) Fig 24. (a) Position of LLC. (b) Protocol formats. LLC service options Unreliable datagram service (Internet, best efforts IP packets delivery) Internet : LLC에서는 no ack. Acknowledged datagram service Reliable correction oriented service

4.3.9. IEEE 802.2: Logical Link Control (3/3) LLC header destination/source access point field 이 frames이 어느 process에서 오고 가는지 replace the DIX Type field control field : sequence와 acknowledgement #(reliable connection) 포함. HDLC style과 비슷 reliable connection-oriented service

4.3.10. Retrospective on Ethernet Ethernet이 오래가는 이유 : simple and flexible Reliable, cheap, easy to maintain TCP/IP와 쉽게 interworking Speed가 향상되고 hub나 switch들이 개발되었지만, S/W의 변화를 요구하지 않음

4.4. Wireless LANs (1/2) The 802.11 Protocol Stack The 802.11 Physical Layer The 802.11 MAC Sublayer Protocol The 802.11 Frame Structure Services

4.4. Wireless LANs (2/2) Wireless LANs are increasingly popular office buildings, airports, public place 등 Fig 1-35. (a) Wireless networking with a base station. (b) Ad hoc networking.

4.4.1. The 802.11 Protocol Stack (1/2) Physical layer Data link layer OSI physical layer와 유사 Data link layer MAC (Medium Access Control) Channel을 어떻게 할당할지 누가 다음 전송을 수행할지 LLC (Logical Link Control) 802 사양들 사이의 차이점을 은닉 네트워크 계층이 전송에 관여할 때까지 802 사양들 간의 구별을 없앰 Fig 25. Part of the 802.11 protocol stack.

4.4.1. The 802.11 Protocol Stack (2/2) 3가지 전송기술 High bandwidth Infrared method : as television remote control Short-range radio : FHSS, DSSS 2.4 GHz ISM band 1 or 2 Mbps로 동작 너무 많은 충돌이 발생하지 않을 정도의 저전력 사용 High bandwidth OFDM : 54 Mbps HR-DSSS : 11 Mbps

4.4.2. The 802.11 Physical Layer (1/4) Infrared option : 0.85 or 0.95 microns에서의 diffused transmission 1 Mbps와 2 Mbps 속도 지원 Gray Code 1 Mbps : 4 bits → 16 bits codeword (연속된 0 : 15개, 1 : 1개) Single bit error detection 2 Mbps : 2 bits → 4 bits codeword (0 : 3개, 1 : 1개) 0001, 0010, 0100, 1000 벽을 투과하지 못하므로, 방마다 서로 다른 cell로 분리 Low bandwidth

4.4.2. The 802.11 Physical Layer (2/4) FHSS (Frequency Hopping Spread Spectrum) 79 channels, each 1 MHz, 2.4 GHz ISM band Pseudo-random generator 일련의 frequency hopping sequence를 발생시키기 위해 사용 똑같은 seed를 사용하고 synchronization time을 유지 동시에 같은 frequency 대역으로 hopping Dwell time : 각 frequency에서 사용하는 시간의 양 400 msec 보다 적어야 함 Longer distance의 multipath에도 좋은 성능 Security 제공, 전파 방해에 덜 민감하므로 building 간의 통신 단점 : low bandwidth

4.4.2. The 802.11 Physical Layer (3/4) DSSS (Direct Sequence Spread Spectrum) : CDMA 시스템과 유사 1 Mbps와 2 Mbps로 제한 각 bit는 Barker sequence를 사용하여 11 chips으로써 전송 1 Mbaud에 phase shift modulation 사용 1 Mbps (1 bit per baud) 2 Mbps (2 bit per baud)

4.4.2. The 802.11 Physical Layer (3/4) OFDM (Orthogonal Frequency Division Multiplexing) IEEE 802.11a, ETSI HyperLAN/2 5 GHz ISM band에서 최대 54 Mbps 52 frequency band 48 data 4 synchronization Signal을 다수의 narrow band으로 분리해서 동시에 전송 가능 서로 배타적인 대역 사용의 가능성을 높임. 54 Mbps (216 data bits가 288 bit symbols로 encoding) 5 GHz ISM band Spectrum의 효율적인 사용으로 bits/Hz의 전송속도를 향상 multipath fading에 좋은 immunity 특성을 가짐.

4.4.2. The 802.11 Physical Layer (4/4) HR-DSSS (High Rate Direct Sequence Spread Spectrum) 11 million chips/sec → 11 Mbps in the 2.4 GHz band 802.11b data rate 1 Mbps (1 bit/baud), 2 Mbps (2 bit/baud) – 1 Mbaud phase shift keying (PSK) 5.5 Mbps (4 bit/baud), 11 Mbps (8 bit/baud) – 1.375 Mbaud Walsh / Hadamard code 802.11g 802.11a의 OFDM modulation 방식 사용 : 54 Mbps 802.11b의 narrow 2.4 GHz ISM band에서 동작 현재까지는 이 속도가 실현될지는 미지수

4.4.3. The 802.11 MAC Sublayer Protocol (1/7) Wireless 환경의 inherent complexity 때문에, Ethernet과 많이 다르다. Carrier sense와 collision detection이 어렵다. Ethernet : CSMA/CD 방식을 사용하여 전송이 시작되면, 거의 정확하게 전송된다고 보장 Single frequency 대역에서 동시에 잡음 burst 현상에 대해 송, 수신이 불가능 결론 : 802.11 Wireless LAN에서는 CSMA/CD 방식을 사용할 수 없음. Fig 26. (a) The hidden station problem. (b) The exposed station problem.

4.4.3. The 802.11 MAC Sublayer Protocol (2/7) Two mode of operation DCF (Distributed Coordination Function) : no central control (similar to Ethernet) Physical channel sensing and virtual channel sensing PCF (Point Coordination Function) : Base station이 제어, no collision DCF를 적용하여, CSMA/CA (CSMA with Collision Avoidance) Station이 전송을 원할 때, channel을 sense (physical channel sensing) Idle 일 때 전송, 모든 frame을 전송 Busy 일 때 idle까지 wait Collision 일 때 random time wait → binary exponential backoff algorithm

< MACA and MACAW > Fig 12. The MACA protocol. (a) A sending an RTS to B. (b) B responding with a CTS to A. RTS와 CTS를 송신함으로써, 주변 station들은 주의 C는 RTS를 들으나, CTS는 듣지 못한다. B를 방해하지 않으며, CTS를 방해하지 않는 한 전송이 가능하다. D는 RTS는 듣지 못하나, CTS는 듣는다. B를 방해하지 않기 위해서, 전송을 중지한다. E는 RTS 및 CTS를 둘 다 듣는다. 동시에 RTS를 보내면 collision → binary exponential backoff algorithm

4.4.3. The 802.11 MAC Sublayer Protocol (3/7) MACAW (Multiple Access with Collision Avoidance for Wireless) Virtual channel sensing NAV : Network Allocation Vector Fig 27. The use of virtual channel sensing using CSMA/CA.

4.4.3. The 802.11 MAC Sublayer Protocol (4/7) Frame이 짧을수록 오류가 발생할 확률이 적음. Fragmentation : noise channel의 문제를 다루기 위해서, 각각이 checksum 포함 Stop-and-wait protocol (individually acknowledged) Fragmentation은 throughput을 증가 Sequence of fragments : fragment burst라고 지칭 Fig 28. A fragment burst.

4.4.3. The 802.11 MAC Sublayer Protocol (5/7) PCF : base station이 polling을 수행하여, station이 전송할 frame을 가지고 있는 물어봄. Collision이 발생하지 않음. Standard : polling frequency, polling order 등 규정 주기적으로 beacon frame을 발송 FHSS를 위한 hopping sequence Dwell time Synchronization inviting message (new station) Battery 수명도 중요한 issue power management mobile node : sleep mode

4.4.3. The 802.11 MAC Sublayer Protocol (6/7) PCF와 DCF가 공존 가능 Fig 29. Interframe spacing in 802.11.

4.4.3. The 802.11 MAC Sublayer Protocol (7/7) Interframe SIFS (Short InterFrame Spacing) Receiver가 RTS에 대한 CTS 응답 Receiver가 Fragmentation frame 또는 전체 data frame에 대한 ACK 전송 Sender가 매번 RTS를 반복해서 보내지 않고 다음 frame을 전송 PIFS (PCF InterFrame Spacing) PCF frame이 보내짐. Base station이 beacon frame 또는 poll frame을 전송 Fragment burst의 sequence 전송이 끝나면, base station에 channel을 가짐. DIFS (DCF InterFrame Spacing) DCF frames이 보내짐. DCF frame 전송을 위한 RTS를 보냄. DIFS가 끝나고 나면, frame 전송을 위해 contention Collision이 일어날 때 → binary exponential backoff EIFS (Extended InterFrame Spacing) Bad frame에 대한 보고

4.4.4. The 802.11 Frame Structure (1/3) Data frame Control frame Management frame Fig 30. The 802.11 data frame.

4.4.4. The 802.11 Frame Structure (2/3) Fig 30. The 802.11 data frame. Duration (2 bytes) Frame과 ack.가 이 channel을 얼마동안 점유하고 있을 것인지 Control frame에도 존재 Address (6 bytes) source address, destination address source and destination base station address : base station을 통하여 cell을 들어오고 나간 경우 Seq. (sequence : 2 bytes) : fragmentation에 번호 부여 12 bit : frame 식별, 4 bit : fragment frame 식별

4.4.4. The 802.11 Frame Structure (3/3) Control frame : No data field and no sequence field Version : 2개의 protocol version 지원 Type : data, control 또는 management 구분 Subtype : RTS 또는 CTS를 나타냄. To DS and From DS : 셀 간(intercell) distribution system(예. Ethernet)으로 들어오거나 나가는 frame 구분 MF (more fragmentation) : 뒤따르는 fragmentation frame이 더 있음을 의미 Retry (retransmission) : 이전에 보낸 frame을 재전송 Pwr (power management) : base이 mobile로 보낼 때 사용하는 bit, sleep mode로의 전환 More : 추가적으로 보낼 frames이 존재하는지 W : WEP (wired equivalent privacy) 알고리즘을 이용하여 암호화 O : receiver에게 이 bit가 1로 설정된 frame의 sequence는 반드시 순서대로 처리하도록 함. Management frame Data frame과 유사 Base station address 제외 : 하나의 single cell로 제한 Data와 sequence 필드가 없는 짧은 길이의 frame Subtype 필드가 매우 중요 : RTS, CTS, ACK

4.4.5. Services (1/3) Wireless LAN은 9가지 services 제공 Five distribution services cell membership의 관리와 cell 밖의 station 간의 통신 Base station에 의해 제공 Cell로 들어오고 나갈 때, base station에 추가되고 제거되는 station의 mobility를 다룸 Four station services : single cell 내에서의 service

4.4.5. Services (2/3) Five distribution services Association (결합) : mobile station의 cell 가입 PCF service (polling), data rate, power management의 필요성을 보고 결합 후, 인증 절차를 거쳐야 함. Disassociation (해제) : power off 전, 다른 cell로의 이동 전에 수행 Reassociation (재결합) : 더 좋은 base station 선택 Handover로 인한 데이터 분실에 주의 Distribution (분배) : base station으로 보내진 frame의 routing Destination이 cell 외부라면, wired network으로 보내짐. Integration (통합) : non-802.11 net으로 보내지는 경우 destination network에 필요한 frame format으로 대체

4.4.5. Services (3/3) Four station services Authentication (인증) : data 전송 허가를 받기 전에 인증과정을 거침. Mobile station이 올바른 secret key를 가지고 있는지 base station이 확인 Deauthentication (인증해제) : network을 떠날 때, 인증 해제 Privacy (프라이버시) : 정보의 신뢰성을 제공하기 위해 encryption, decryption 관리 RC4 : encryption algorithm Data delivery (데이터 전송) : 데이터 송수신을 위한 방법 제공 Upper layer에서의 error detection and correction

4.5. Broadband Wireless Comparison of 802.11 and 802.16 The 802.16 Protocol Stack The 802.16 Physical Layer The 802.16 MAC Sublayer Protocol The 802.16 Frame Structure Outdoor LMDS 개발 (Fig. 2-30) Easier and cheaper IEEE 802.16 (wireless MAN or wireless local loop) : Air Interface for Fixed Broadband Wireless Access Systems

4.5.1. Comparison of 802.11 with 802.16 (1/2) 802.11과 802.16의 동작 환경 유사 High-bandwidth wireless communication 제공 802.11 : mobility 802.16 Not mobile : cell의 이동이 없음 Building에 service : 보다 넓은 bandwidth 필요

4.5.1. Comparison of 802.11 with 802.16 (2/2) 802.16 full duplex을 사용 가능 수 km 반경 : 거리가 다양 S/N 비, modulation 다양, security와 privacy 802.11 cell 보다 더 많은 user 가능 : 각 user는 더 많은 bandwidth 사용 10 ~ 66 GHz (ISM band보다 높은 대역) 주파수가 높아 error handling도 중요 Multipath fading voice service가 중요 Future : mobile 제공 → 802.16e

4.5.2. The 802.16 Protocol Stack (1/2) Physical layer Fig 31. The 802.16 Protocol Stack. Physical layer 802.16a standard : 2 ~ 11 GHz, OFDM 802.16b standard : 5 GHz ISM band QPSK, QAM-16, QAM-64 Transmission convergence sublayer : data link layer의 다른 기술들을 숨기기 위해

4.5.2. The 802.16 Protocol Stack (2/2) Data link layer Security sublayer : privacy와 보안과 관련된 사항 encryption, decryption, key management MAC sublayer common part Channel management Downstream : base station → subscriber station (channel scheduling) Upstream : subscriber station → base station QoS (Quality of Service )를 제공하기 위해, connection-oriented 방식 Service specific convergence sublayer : logical link sublayer Network layer로의 interface 제공 Datagram protocol : PPP, IP, Ethernet ATM : easy

4.5.3. The 802.16 Physical Layer (1/3) 10 ~ 66 GHz 대역 Base station은 multiple antenna (different sector) beam의 directionality Three different modulation scheme QAM-64 : 6 bits/baud QAM-16 : 4 bits/baud QPSK : 2 bits/baud Ex. 25 MHz band QAM-64 : 150 Mbps QAM-16 : 100 Mbps QPSK : 50 Mbps Fig 32. The 802.16 transmission environment.

4.5.3. The 802.16 Physical Layer (2/3) Bandwidth를 효율적으로 사용 Voice는 uprsteam, downsteam traffic이 거의 비슷 Data는 downstream traffic이 더 많음 : internet traffic Flexible하게 bandwidth 할당 FDD and TDD

4.5.3. The 802.16 Physical Layer (3/3) Fig 33. Frames and time slots for time division duplexing. (TDD) Upstream / downstream slot 수들은 dynamic하게 변화 Downstream : base station에 의해 time slot으로 mapping Upstream : 복잡하고 QoS에 따라 달라짐. Guard time : station들이 방향을 바꿀 때의 switching time Hamming code 사용 : error correction Higher layer에서는 checksum 넓은 지역의 broadband 환경이므로.

4.5.4. The 802.16 MAC Sublayer Protocol (1/4) 모든 service가 connection-oriented 연결 방식으로 처리 4가지 service class Security (chap. 8 참조) Subscriber station이 base station에 가입 시, 인증 절차 X.509로 인증 서 RSA public key cryptography data는 DES 또는 triple DES (AES 추가 예정) Integrity checking : SHA-1 MAC frame은 다수의 physical layer time slot들로 구성 각 frame은 여러 개의 subframe들로 구성 처음의 2개의 subframe : downstream map, upstream map Subframe 정보 수록

4.5.4. The 802.16 MAC Sublayer Protocol (2/4) 4가지 Service Classes Uncoordinated subscriber가 서로 경쟁 QoS를 제공하는 channel 할당으로 인해, upstream이 복잡 Constant bit rate service Uncompressed voice : 미리 정해진 시간 간격 동안 미리 결정된 데이터량 전송 각 connection에 고정된 시간 간격이 time slot 지정 Bandwidth가 allocation되면 ack.없이 time slot을 자동적으로 사용 Real-time variable bit rate service Compressed multimedia and soft real time application Base station은 그때 그때 고정된 시간 간격으로 polling 하면서 필요한 bandwidth를 subscriber에게 물음.

4.5.4. The 802.16 MAC Sublayer Protocol (3/4) Non-real-time variable bit rate service Heavy transmission, file transfer 고정된 time interval 없이 polling 계속해서 보낼 것이 있으면, frame 중 한 bit에 표시 계속해서 k번 안보내면, multicast group으로 보냄. Multicast group이 polling 될 때, contention해서 channel 획득 Traffic이 거의 없는 station에 대해 poll을 낭비하지 않음. Best efforts service No polling Bandwidth contention Connection에 성공하면, 다음 번 downstream map에 표시 충돌을 줄이기 위해, binary exponential backoff algorithm 사용

4.5.4. The 802.16 MAC Sublayer Protocol (4/4) Bandwidth allocation Per station Subscriber station가 building 내의 모든 users의 request를 한꺼번에 처리 collective request Per connection Base station이 각각의 connection을 직접 관리

4.5.5. The 802.16 Frame Structure (1/2) Fig 34. (a) A generic frame. (b) A bandwidth request frame. Generic frame EC : encryption 여부 Type : packing, fragmentation CI : checksum의 유무 EK : 어떤 encryption key 인지 Length : header를 포함한 길이 CRC (optional) : physical error correction Real time traffic Header CRC : x8+x2+x+1

4.5.5. The 802.16 Frame Structure (2/2) Fig 34. (a) A generic frame. (b) A bandwidth request frame. Bandwidth request frame No payload or no full-frame CRC Bytes needed : how much bandwidth needed

4.6. Bluetooth (1/2) Bluetooth Architecture Applications Protocol Stack Radio Layer Baseband Layer L2CAP Layer Frame Structure

4.6. Bluetooth (2/2) 유선 cable의 연결없이 mobile phone과 다른 기기들(ex. PDA 등)을 연결 Bluetooth : SIG (Special Interest Group) – IEEE 802.15.1 (PAN) IBM, Intel, Nokia, Toshiba Accessories들과 communication devices, computing devices 간의 상호 연결을 위한 wireless standard Using short-range, low-power, inexpensive wireless radio

4.6.1. Bluetooth Architecture (1/2) Fig 35. Two piconets can be connected to form a scatternet. Piconet Master node 7개의 active slave nodes 10 meter 이내 Multiple piconet Same (large) room에 함께 존재 가능 Bridge node를 통한 연결 interconnected collection of piconet : Scatternet

4.6.1. Bluetooth Architecture (2/2) Master / Slave design 이유 값싸게 디자인하기 위해 : slave는 master의 지시에 따라 동작 Centralized TDM system Master Clock 제어 어떤 time slot에 어떤 device가 통신을 할 것인가 결정 모든 communication은 master-slave 간의 통신 Slave-slave끼리의 communication 불가능 또한, 네트워크 내에는 최대 255 개의 대기 노드 : sleep mode와 유사 Master가 battery 방전을 줄이기 위해, 저전력 상태로 변환될 수 있는 기기 대기 상태에서 master의 activation 또는 beacon signal에 반응하는 외에는 idle Hold and sniff

4.6.2. Bluetooth Applications (1/2) Bluetooth V.1.1 spec. 13 specific application 각각이 다른 protocol stacks 제공 Profile (프로파일) 필수 Generic access : master와 slave 사이의 secure link를 establish하고 maintain하는 방법 제공 Service discovery : device 들이 다른 device들에게 서비스 해야 하는 것이 무엇인가를 발견해야 할 때 사용하는 protocol Fig 36. The Bluetooth profiles.

4.6.2. Bluetooth Applications (2/2) Options Serial port : 다른 profile들이 사용하는 transport protocol Generic object exchange : client-server 관계를 정의 다른 profile들의 building block LAN access, Dial-up networking, Fax : for networking Fixed LAN에 mobile computer을 연결시키는 protocol : 802.11과 경쟁 Cordless telephony, Intercom, Headset : for telephony Object push, File transfer, Synchronization : for actually exchanging objects between two wireless devices Provides a way to exchange simple objects (ex. business cards, pictures) Synchronization : Permits a PDA to synchronize with another computer 외출 시 작성하여 PDA나notebook computer에 저장했던 data를 꺼냄

4.6.3. The Bluetooth Protocol Stack (1/3) Basic Bluetooth protocol architecture 802 committee에 의해 modified Fig 37. The 802.15 version of the Bluetooth protocol architecture. Physical radio layer OSI, 802 models의 physical layer와 유사 Radio transmission, modulation에 관여 가능한 한 inexpensive

4.6.3. The Bluetooth Protocol Stack (2/3) Baseband layer MAC sublayer와 유사. 단, physical layer의 elements 포함. Master의 time slot control, 이 slot들이 어떻게 frame내에서 group화 될지를 결정 Layer with a group of related protocols Link manager Device 간의 logical channel의 establishment Power management Authentication Quality of Service Logical link control adaptation protocol (L2CAP) 실제 transmission으로부터 upper layer를 보호 기술적으로는 상이하지만, 802 LLC sublayer와 매우 유사 Audio / Control 각각 audio, control 관련 L2CAP와 별도

4.6.3. The Bluetooth Protocol Stack (3/3) Middle ware layer : different 802 network protocol과 상호성 제공 Rfcomm (Radio Frequency communication) keyboard, mouse, modem을 연결하기 위한 PCs에서 발견되는 standard serial port를 가상실험하는 protocol Telephony 3개의 speech-oriented profiles을 위해 사용되는 real-time protocol call setup and termination을 관리 Service discovery Network 내의 services 지정하기 위해 사용 Top layer : applications and profiles protocol lower layers에 있는 protocol들이 작업을 성공적으로 완료하게 해주는 layer 각각의 application device에 따라 별도의 protocol을 가짐.

4.6.4. The Bluetooth Radio Layer Master와 slave간의 bit 이동 10 meter 반경의 low power system 2.4 GHz ISM band, 각 1 MHz의 79 channels FSK, 1 Mbps Channel을 골고루 분배하기 위해 Frequency hopping spread spectrum (FHSS) 1,600 hops/sec, dwell time : 625 usec cf. IEEE 802.11 : 400 msec, 2.4 GHz, FHSS 802.11 and Bluetooth interfere with each other : 802.11과 같은 79 channels Hopping을 빨리 하기 때문에 Bluetooth가 802.11보다 빠름. Bluetooth device가 802.11 transmissions을 방해함. IEEE가 해법을 찾고 있음.

4.6.5. The Bluetooth Baseband Layer Bluetooth protocol 중 MAC sublayer에 가장 유사 Bit stream → frame 으로 변환, 중요 format을 정의 TDM : 625 usec의 time slots Event slot : master Odd slot : slave Frame이 전송되는 2가지 종류의 link를 통해 전송 ACL (Asynchronous Connection-Less) link Irregular intervals으로 발생하는 packet-switched data 이 data는 L2CAP layer를 통해 들어옴. SCO (Synchronous Connection Oriented) link Real time traffic을 위한 link : retransmission이 발생하지 않음. Fixed slot을 할당 받음. Reliability를 위해 Forward error correction Slave는 3개의 SCO link까지 소유 가능 64 Kbps PCM audio channel

4.6.6. The Bluetooth L2CAP Layer 3가지 주요 기능 Upper layer로부터 64 Kbyte까지 packet을 받아들이고, 전송을 위해 frame을 중간에 끊을 수 있음. 맨 마지막 packet은 다시 frame으로 재구성 multiple packet sources의 multiplexing and demultiplexing Link가 설정되었을 때나 정상 동작 중 QoS (quality of service)를 관리 Ex. Maximum payload size가 device 마다 다르므로

4.6.7. The Bluetooth Frame Structure (1/2) Fig 38. A typical Bluetooth data frame. Access code : master를 identification 해줌. 54 bit header Address field identifies : 8개 device 중 frame이 어디로 갈지 Type field identifies : frame type (ACL, SCO, poll, or null) type of error correction 해당 frame이 몇 slot을 차지하는지 Flow bit : slave에 의해 명시 buffer is full → 더 이상 data를 받을 수 없다고 전함 : flow control Acknowledgement bit : 한 frame의 ACK를 piggyback

4.6.7. The Bluetooth Frame Structure (2/2) Fig 38. A typical Bluetooth data frame. 54 bit header (계속) Sequence bit : retransmissions을 detect하기 위해 frame에 번호를 매김. stop-and-wait 방식이므로 1 bit면 충분 Checksum : 8 bits 18 bit header가 3번 재전송 : 다수의 bit 값을 따름. Data field : 2,744 bits 까지 사용 가능(for 5-slot transmission) SCO frame : 80, 160, 240 bit payload 중 80 bit payload가 신뢰도가 높음 3번 반복전송 800 slot/sec 이므로, 64,000 bps

4.7. Data Link Layer Switching (1/3) Bridges from 802.x to 802.y Local Internetworking Spanning Tree Bridges Remote Bridges Repeaters, Hubs, Bridges, Switches, Routers, Gateways Virtual LANs

4.7. Data Link Layer Switching (2/3) Bridge를 통해 LAN 연결 Data link layer에서 동작 Routing을 하기 위해, data link layer의 address를 참조 IPv4, IPv6, AppleTalk, ATM, OSI or any other kinds of packet 들을 전송 cf. router : packet 내의 address를 참조하고, 그 address를 기반으로 routing Fig 39. Multiple LANs connected by a backbone to handle a total load higher than the capacity of a single LAN.

4.7. Data Link Layer Switching (3/3) 다수의 LAN을 사용하고 bridge로 연결하는 이유 Multiple LANs이 bridge를 이용하여 backbone으로 연결 각 건물에 독립적인 LAN을 설치 → 적은 비용 각각의 LAN에 file server와 많은 workstation이 연결 → load 분산 각각의 LAN 반경 (Ethernet : 2.5 Km) 이므로, traffic의 과부하가 각각의 LAN에 한정 Round trip delay 감소 Reliability 증가 : garbage traffic을 소거 Security 관점 : traffic을 선별해서 차단 (bridge를 넘지 못하도록)

4.7.1. Bridges from 802.x to 802.y (1/3) Two port bridge : 802.11 WLAN (A) ↔ 802.3 Ethernet (B) Host A port → <LLC sublayer> LLC header 추가 → <MAC sublayer> 802.11 header 추가 Bridge에서 MAC header가 교체 Fig 40. Operation of a LAN bridge from 802.11 to 802.3.

4.7.1. Bridges from 802.x to 802.y (2/3) Fig 41. The IEEE 802 frame formats.

4.7.1. Bridges from 802.x to 802.y (3/3) 다양한 802 LANs 사이의 bridge 구축 시 어려운 점 각각의 LAN들은 서로 다른 frame format을 가지고 있음. Header 부분이 달라 checksum이 달라짐 → error 가능성 상호 연결된 LANs이 반드시 똑같은 data rate로 동작할 필요가 없음. Flow control 측면 서로 다른 802 LANs은 서로 다른 maximum frame length를 가지고 있음. Segmentation Reassembly Security 802.11, 802.16 모두 data link layer에서 encryption 지원 Ethernet은 지원 안 함. Wireless network에서 유효한 다양한 encryption service가 Ethernet을 거치면서 없어져 버림. 또한, 암호화된 802.11 packet은 802.3에서 해석 못함. Quality of service 802.11 : PCF 모드 사용 802.16 : constant bit rate connection을 사용 Ethernet은 QoS에 대한 개념이 없고, Ethernet을 통과하면 QoS를 잃어버림.

4.7.2. Local Internetworking (1/3) 많은 수의 LANs을 interconnecting 시 다양한 문제가 발생 이상적인 경우 H/W나 S/W의 변화가 없어야 함. Address switches를 위한 설치 단계가 없어야 함. Routing table 또는 parameter의 다운로드가 없어야 함. 기존의 작동하는 LAN은 bridge에 영향을 받으면 안됨. Bridge는 transparent 해야 함.

4.7.2. Local Internetworking (2/3) Fig 42. A configuration with four LANs and two bridges. Bridge Frame이 도착하면 폐기(discard) 되거나 전달(forward) Bridge 내에 destination address가 정리되어 있는 hash table이 존재

4.7.2. Local Internetworking (3/3) 처음에 bridge들이 on 되면, 모든 hash table들은 비워짐. 처음엔 destination을 알지 못하므로, 발원지 LAN을 제외하고 flooding → 시간이 지나면 destination의 소속을 알게 되므로flooding하지 않음. Backward learning : 자기를 거치는 frame의 source address를 본 후 이 frame이 어느 LAN에서 발원했는지를 기록 나중에 이 source를 향한 frame이 발생하면 그 쪽으로 전송 Dynamic topology change에 대비 : frame 도착 시간이 계속 update 주기적으로 bridge는 hash table을 점검하여, 몇 분이 지난 data는 정리 → flooding Routing 출발지 LAN과 목적지 LAN이 같으면, frame discard 출발지 LAN과 목적지 LAN이 다르면, frame forward 목적지 LAN을 모르면 flooding VLSI chip : table 내의 내용을 lookup, update

4.7.3. Spanning Tree Bridges (1/3) Reliability를 증가시키기 위해 bridge 둘 이상을 parallel 하게 연결 Looping 현상 발생 LAN1에서 F 발생 B1은 복사한 F1, B2는 복사한 F2를 LAN2에 flooding B1은 수신한 F2를 다시 LAN1에 복사한 F3로 flooding B2는 수신한 F3를 LAN2로 flooding 계속 cycles Looping 현상 문제점 개선 Spanning tree topology 정확하게 one path Fig 43. Two parallel transparent bridges.

4.7.3. Spanning Tree Bridges (2/3) Fig 44. (a) Interconnected LANs. (b) A spanning tree covering the LANs. 9 LANs, 10 bridges (G, I가 discard) → 9 LANs, 8 bridges (가상의 loop-free topology)

4.7.3. Spanning Tree Bridges (3/3) 각 bridge는 manufacturer가 지정한 유일한 serial number를 broadcasting → 가장 낮은 serial number의 bridge가 root가 됨 → 이후 tree 형성 bridge 또는 LAN이 고장나면, 새로운 tree 형성 : shortest path Spanning tree가 형성된 후에도 topology 변경됨에 따라, tree를 update 하기 위하여 algorithm은 계속 동작

4.7.4. Remote Bridges 멀리 떨어진 LAN 들 간에는 point-to-point lines → hostless LANs 다양한 point-to-point data link protocol 사용 가능 MAC frame 전체를 PPP의 payload에 삽입, 모든 LAN이 똑같을 때 가장 잘 동작 MAC header 및 trailer를 source bridge에서 제거, 새로운 MAC header 및 trailer를 destination bridge에서 삽입 Checksum : 중간에 bridge의 memory에 error가 삽입될 수 있음. Fig 45. Remote bridges can be used to interconnect distant LANs.

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (1/7) Fig 46. (a) Which device is in which layer. (b) Frames, packets, and headers.

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (2/7) Fig 47. (a) A hub. (b) A bridge. (c) a switch.

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (3/7) Physical layer Repeaters 두 cable segment를 연결시키는 analog 장비 : amplifier 하나의 segment에 나타나는 신호를 증폭해 다른 segment에 올려놓음 Frames, packets, or headers가 무엇인지 모름 단지 volts만을 감지 Hubs : Fig. 47 (a) 다수의 input lines을 가지고 있음. 한 line에 도착한 frame은 다른 모든 line들을 통해 송출 하나의 collision domain을 가짐 : 2개 이상의 frame이 도착하면 충돌 Repeater와의 차이점 : signal을 amplify하지 않고, multiple input을 수용할 수 있도록 각 input에 line card를 하나씩 부착

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (4/7) Data link layer Bridges : Fig. 47 (b) 2개 이상의 LANs을 연결 Frame이 도착하면 frame header로부터 destination address를 추출 Table을 조사하여 어디로 보낼지를 결정 Line card를 장착하고 있음. ex. Ethernet을 위한 line card는 Token ring frame을 처리할 수 없음 서로 다른 network type이나 speed에 대응하기 위해 여러 장의 line card를 가질 수 있음. 보통은 어떤 측정 type에 대해 4개 또는 8개의input lines을 가짐. 각 line이 collision domain이 됨.

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (5/7) Switches : Fig. 47 (c) Frame addresses를 이용해 경로를 지정 독립적인 개개의 컴퓨터를 연결하기 위해 주로 사용 더 많은 line cards를 장착할 수 있도록 공간 확보 및 도착하는 frame을 위한 buffer 제공 각 port가 개별 collision domain이 되므로, collision으로 인한 frame 분실이 발생하지 않음. Buffer가 꽉 차면, frame 폐기 Modern switches Cut-through switches : destination address만 확인하고 즉시 전송 Store-and-forward switching을 사용하지 않음.

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (6/7) Network layer Routers Packet이 도착하면 frame header와 trailer를 분리 Frame payload field에 위치한 packet이 routing software에 보내짐. Output line을 선택하기 위해, packet header를 사용 IPv4 : 32-bit address IPv6 : 128-bit address cf. Ethernet : 48-bit

4.7.5. Repeaters, Hubs, Bridges, Switches, Routers and Gateways (7/7) Transport Transport gateway 서로 다른 connection-oriented transport protocol를 사용하는 2대의 computer를 연결 Connection으로부터 받은 packet들을 필요한 format으로 바꿔서 다른 connection으로 연결시켜줌. ex. 연결형 TCP/IP → 연결형 ATM transport Application Application gateway Format과 data의 내용을 해석할 수 있음. Message format을 변경할 수 있음. ex. Internet msg. → SMS

4.7.6. Virtual LANs (1/5) Fig 48. A building with centralized wiring using hubs and a switch.

4.7.6. Virtual LANs (2/5) Hubbed Ethernet 논리적으로 LAN 구성 k LANs을 설치하고자 하면, k hubs를 사서 연결 모든 LANs이 interconnected : network administrator는 physical layout 보다는 가입자들을 부서별로 구분하는 것이 바람직 Security Load Broadcasting Endless stream of broadcast frame : broadcast storm 전체 LAN capacity가 이러한 frame에 의해 점유. 연동된 LAN 상의 모든 machines은 처리되지 못하고, broadcast되는 모든 frame은 폐기 Multiple LANs : restricted scope User requests for more flexibility Rewire buildings entirely in S/W → VLAN (Virtual LAN)

4.7.6. Virtual LANs (3/5) VLAN User가 요구하는 유연성(flexibility)를 제공하기 위해, S/W로 재배선 특별히 설계된 VLAN-aware switches Network administrator의 결정사항 VLANs의 개수 어느 computer가 어느 VLAN에 속하는가 어느 VLANs이 호출될 것인가 Color로 구분

4.7.6. Virtual LANs (4/5) Fig. 49 (a) : 4 VLANs G(grey) VLANs : 8 machines W(white) VLANs : 7 machines 4개의 물리적인 LAN이 2개의 bridges(B1, B2)와 4개의 hubs로 연결 Fig. 49 (b) : 2 VLANs (Grey, White) 각 port 마다 단일 computer를 가지는 switch

4.7.6. Virtual LANs (5/5) Three method : 어떻게 frame의 color를 알 수 있을까? 모든 port가 VLAN color를 할당 받음. LAN 3, 4의 경우 가능 모든 MAC address는 VLAN color를 할당 받음. Bridge나 switch가 mapping list (MAC address → VLAN) 모든 layer 3 protocol 또는 IP address가 VLAN color를 할당 받음. Layer 간 구별이 모호 (layer 2에서 payload를 check) 이동이 잦은 경우, MAC address는 자주 바뀐다. (ex. Notebook)

< The IEEE 802.1Q Standard (1/4) > VLAN을 식별하기 위한 MAC header 802.16 : connection ID로 가능 802.3 : no Ethernet header 변경을 위한 New forma VLAN tag (802.1Q) A few questions that come to mind are: Need we throw out several hundred million existing Ethernet cards? If not, who generates the new field? What happens to frames that are already the maximum size? VLAN field는 bridge와 switch가 필요 Gigabit LAN부터는 802.1Q를 따르기를 희망

< The IEEE 802.1Q Standard (2/4) > Switch가 spender의 VLAN 에 기초한 new tagged frame 발생 MAC address, IP address, port 등을 고려 VLAN-aware switch: 전송된 tagged frame은 legacy frame으로 전환 기능 Fig 50. Transition from legacy Ethernet to VLAN-aware Ethernet. The shaded symbols are VLAN aware. The empty ones are not.

< The IEEE 802.1Q Standard (3/4) > Fig 51. The 802.3 (legacy) and 802.1Q Ethernet frame formats.

< The IEEE 802.1Q Standard (4/4) > 단지, a pair of 2 byte fields 추가 VLAN protocol ID (0x8100) : 2 bytes 항상 0x8100 값을 가짐 Tag : 2bytes Priority field Hard real-time traffic, soft real-time traffic, time-intensive traffic을 구분 Voice over Service 새로운 service CFI (Canonical Format Indicator) 1bit : 802.5 frame의 전송 VLAN identifier : occupying the low-order 12 bits VLAN-aware bridge는 tag들을 분석한 후 VLAN의 topology를 autoconfigure

Summary Fig 52. Channel allocation methods and systems for a common channel.