Chapter 16 High Speed LANs

Fibre Channel Association Introduction Range of technologies IEEE 802.3 표준 (Ethernet) : 10Mbps, 100Mbps(Fast Ethernet), 1Gbps(Gigabit Ethernet), 10Gbps CSMA/CD MAC 프로토콜 1Gbps, 10Gbps : Switching 기술 사용 IEEE 802.5 표준 : Token Ring, 4Mbps – 1Gbps Fibre Channel : SAN과 같이 고속이 필요한 응용분야에서 사용되는 기술 High Speed Wireless LANs Fast Ethernet Gigabit Ethernet Fibre Channel Wireless LAN Data Rate 100Mbps 1 / 10 Gbps 100Mbps~3.2Gbps 1Mbps~54Mbps Medium UTP, STP, Fiber UTP, Fiber Fiber, Coaxial, STP 2.4GHz, 5GHz Microwave Access Method CSMA/CD Switched CSMA/Polling Standard IEEE802.3 Fibre Channel Association IEEE802.11

Why High Speed LANs? LAN에 대한 요구사항이 변경되고 있음. Speed and power of PCs has risen Graphics-intensive applications and GUIs MIS (Management Information System; 경영정보시스템) organizations recognize LANs as essential Began with client/server computing Now dominant architecture in business environment Intra-networks Frequent transfer of large volumes of data in a transaction-oriented environments

Applications Requiring High Speed LANs Centralized server farms User needs to draw huge amounts of data from multiple centralized servers E.g. Color publishing Servers contain tens of gigabytes of image data Downloaded to imaging workstations Power workgroups Small number of cooperating users Draw massive data files across network E.g. Software development group testing new software version or computer-aided design (CAD) running simulations High-speed local backbone Processing demand grows LANs proliferate at site High-speed interconnection is necessary

도로상의 Collision

MAC 프로토콜의 필요성 LAN에 연결된 노드(컴퓨터, 스테이션)들은 Shared Medium을 사용하기 때문에 Collision이 발생됨.

IEEE802.3 Medium Access Control Random Access Stations access medium randomly Contention Stations content for time on medium (pure) Aloha Slotted CSMA CSMA/CD CSMA/CA Token Ring Bus IEEE 802.3 IEEE 802.11 IEEE 802.5 IEEE 802.4

(Pure) ALOHA Packet Radio Network를 위해 개발되었음. 동작원리 When station has frame, it sends Station listens for max round trip time plus small increment If ACK, fine. If not, retransmit If no ACK after repeated transmissions, give up Frame check sequence (as in HDLC) If frame OK and address matches receiver, send ACK Frame may be damaged by noise or by another station transmitting at the same time (collision) Any overlap of frames causes collision Max Channel utilization 18%

ALOHA

ALOHA N: 망 내에서 한 프레임 시간 동안 생성되는 평균 프레임의 개수(Poission 분포로 발생) N>1 : 매번 collision이 발생 어느 정도의 성능이 나오기 위해서는 0<N<1 이어야 함. 한 프레임 시간 동안에 시도되는 전송개수가 있을 것임(재전송 포함). k transmission attempts per frame time is also Poission, with mean G per frame time. G≥N (재전송이 포함되어 있으므로)

Poisson Distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate and independently of the time since the last event. If the expected number of occurrences in this interval is λ, then the probability that there are exactly n occurrences (n being a non-negative integer, n = 0, 1, 2, ...) is equal to

ALOHA 망 내에 load가 작은 경우(N≈0) 망 내에 load가 큰 경우 Collision이 적어 재전송도 적을 것임. G ≈ N 망 내에 load가 큰 경우 Collision이 많아 G>N 성능은 offered load(G)와 전송 성공확률(S)에 의해 결정됨. S=GP0 P0 : 한 프레임이 collision이 없을 확률

ALOHA t t0 t0+t t0+2t t0+3t t0에서 to+t 사이에서 프레임에 생성되면 collision

Slotted ALOHA Time in uniform slots equal to frame transmission time Need central clock (or other sync mechanism) Transmission begins at slot boundary Frames either miss or overlap totally Max channel utilization 37%

성능 한 프레임 시간 동안 k개의 프레임이 생성될 확률은 Poission 분포에 따라 (Slotted ALOHA) 2개의 프레임 시간 동안에 k개의 프레임이 생성될 확률은 (ALOHA)

ALOHA / Slotted ALOHA

CSMA Propagation time is much less than transmission time All stations know that a transmission has started almost immediately First listen for clear medium (carrier sense) If medium idle, transmit If two stations start at the same instant, collision Wait reasonable time (round trip plus ACK contention) No ACK then retransmit Max utilization depends on propagation time (medium length) and frame length Longer frame and shorter propagation gives better utilization 종류 Non-persistent CSMA 1-persistent CSMA p-persistent CSMA

Non-persistent CSMA If medium is idle, transmit; otherwise, go to 2 If medium is busy, wait amount of time drawn from probability distribution (retransmission delay) and repeat 1 Random delays reduces probability of collisions Consider two stations become ready to transmit at same time While another transmission is in progress If both stations delay same time before retrying, both will attempt to transmit at same time Capacity is wasted because medium will remain idle following end of transmission Even if one or more stations waiting

1-persistent CSMA To avoid idle channel time, 1-persistent protocol used Station wishing to transmit listens and obeys following:  If medium idle, transmit; otherwise, go to step 2 If medium busy, listen until idle; then transmit immediately 1-persistent stations selfish If two or more stations waiting, collision guaranteed

p-persistent CSMA Compromise that attempts to reduce collisions Like non-persistent And reduce idle time Like 1-persistent Rules: If medium idle, transmit with probability p, and delay one time unit with probability (1 – p) Time unit typically maximum propagation delay If medium busy, listen until idle and repeat step 1 If transmission is delayed one time unit, repeat step 1 What is an effective value of p?

Value of p? n stations waiting to send End of transmission, expected number of stations attempting to transmit is number of stations ready times probability of transmitting np If np > 1 on average there will be a collision Repeated attempts to transmit almost guaranteeing more collisions Retries compete with new transmissions Eventually, all stations trying to send Continuous collisions; zero throughput So np < 1 for expected peaks of n If heavy load expected, p small However, as p made smaller, stations wait longer At low loads, this gives very long delays

CSMA Picture HERE Non-persistent Constant or variable delay Channel Busy time p-persistent 1-persistent

Ethernet (CSMA/CD) Carrier Sense Multiple Access with Collision Detection DEC, Xerox, HP - Ethernet IEEE 802.3

CSMA/CD With CSMA, collision occupies medium for duration of transmission Stations listen whilst transmitting If medium idle, transmit, otherwise, step 2 If busy, listen for idle, then transmit If collision detected, send jamming signal then cease transmission After jam, wait random time (backoff) then start from step 1

CSMA/CD Operation 낭비되는 용량은 충돌을 감지하는데 걸리는 시간이 됨. 충돌감지시간은 종점간 전파지연시간의 2배보다 작다 낭비되는 용량은 충돌을 감지하는데 걸리는 시간이 됨. 전송이 끝나기 전에 충돌을 감지할 수 있을 정도로 프레임이 길어야 함

Which Persistence Algorithm? IEEE 802.3 uses 1-persistent Both non-persistent and p-persistent have performance problems 낭비되는 용량이 있다. 1-persistent (p = 1) seems more unstable than p-persistent But wasted time due to collisions is short (if frames long relative to propagation delay With random backoff, unlikely to collide on next tries To ensure backoff maintains stability, IEEE 802.3 and Ethernet use binary exponential backoff

Binary Exponential Backoff Attempt to transmit repeatedly if repeated collisions First 10 attempts, mean value of random delay doubled Value then remains same for 6 further attempts After 16 unsuccessful attempts, station gives up and reports error As congestion increases, stations back off by larger amounts to reduce the probability of collision. 단점 Backoff algorithm gives last-in, first-out effect Stations with few collisions transmit first

Collision Detection On baseband bus, collision produces much higher signal voltage than signal Collision detected if cable signal greater than single station signal Signal attenuated over distance Limit distance to 500m (10Base5) or 200m (10Base2) For twisted pair (star-topology) activity on more than one port is collision (2개 이상의 입력선으로 신호가 들어오면 Collision) Special collision presence signal

IEEE 802.3 Frame Format SFD : 10101011

10Mbps Specification (Ethernet) 10Base5 10Base2 10Base-T 10Base-FP Medium Coaxial cable UTP Fiber Signalling Manchester Manchester/ On-Off Topology Bus Star Max. Segment Size (m) 500 185 100 Nodes per Segment 30 - 33 Cable Diameter (mm) 10 5 0.4~0.6 62.5/125um

100Mbps Fast Ethernet (100Base-T) Use IEEE 802.3 MAC protocol and frame format 100BASE-X use physical medium specifications from FDDI Two physical links between nodes Transmission and reception 100BASE-TX uses STP or Cat. 5 UTP May require new cable 100BASE-FX uses optical fiber 100BASE-T4 can use Cat. 3, voice-grade UTP Uses four twisted-pair lines between nodes Data transmission uses three pairs in one direction at a time Star-wire topology Similar to 10BASE-T

Token Ring (802.5) Developed from IBM's commercial token ring Because of IBM's presence, token ring has gained broad acceptance Never achieved popularity of Ethernet Currently, large installed base of token ring products Market share likely to decline

Ring Operation Each repeater connects to two others via unidirectional transmission links Single closed path Data transferred bit by bit from one repeater to the next Repeater regenerates and retransmits each bit Repeater performs data insertion, data reception, data removal Repeater acts as attachment point Packet removed by transmitter after one trip round ring

Ring Repeater States

Listen State Functions Scan passing bit stream for patterns Address of attached station Token permission to transmit Copy incoming bit and send to attached station Whilst forwarding each bit Modify bit as it passes e.g. to indicate a packet has been copied (ACK)

Transmit State Functions Station has data Repeater has permission May receive incoming bits If ring bit length shorter than packet Pass back to station for checking (ACK) May be more than one packet on ring Buffer for retransmission later

Bypass State Signals propagate past repeater with no delay (other than propagation delay) Partial solution to reliability problem (see later) Improved performance

802.5 MAC Protocol Small frame (token) circulates when idle Station waits for token Changes one bit in token to make it SOF for data frame Append rest of data frame Frame makes round trip and is absorbed by transmitting station Station then inserts new token when transmission has finished and leading edge of returning frame arrives Under light loads, some inefficiency Under heavy loads, round robin

Token Ring Operation

성능문제 (Transmission time = 1)

성능문제 표 16.8 참조 U: Utilization R : Data Rate d : 2 station간 거리 V : 전파속도 Throughput : 단위시간당 전송되는 비트수이다. 표 16.8 참조 

성능문제 (Token Ring) 가정 Token Ring N개의 스테이션 항상 프레임을 보낼 준비가 되어 있다. Transmission Delay : 1 Propagation Delay : a Token Ring C : 한 사이클의 평균시간 (C = T1+T2) T1 : 한 개의 데이터프레임을 전송하는 평균시간 T2 : 한 개의 토큰이 다음 노드로 가는 전달 평균시간 a < 1 a > 1

성능 - Token Ring a < 1 a > 1

Time slot S R 한 Frame이 전송되는데 소요되는 시간  전파지연시간(a)의 2배  2a Slot time은 전송시작부터 collision을 알 수 있을 때까지의 시간임. slot slot slot slot slot slot slot slot time

성능문제 (CSMA/CD) 가정 N개의 스테이션 항상 프레임을 보낼 준비가 되어 있다. 항상 충돌의 가능성이 있으며, 각 스테이션은 확률 P로 전송을 한다. 슬롯(매체의 시간단위)의 길이는 종점간 전파지연시간의 2배이다. Slot의 크기 = 2a 2가지의 구간 전송구간 : 1/2a slots  한 슬롯의 크기는 2a이고, Transmission에 사용되는 크기는 1 (transmission delay) 이므로 2a중에 1만 사용한다는 의미 충돌구간(충돌이 발생되었거나 전송이 없는 슬롯구간) i 개의 슬롯 Slot time 어떤 슬롯에서는 데이터 전송이 이루어지거나 혹은 충돌하거나 전송하지 않는다.

성능문제 (CSMA/CD) CSMA/CD A의 최대값은 P=1/N일 때. 슬롯 단위로 경쟁간격의 평균길이, w는 [i slots in a row with a collision or no transmission followed by a slot with one transmission]

성능문제 (CSMA/CD) Token Ring a < 1 a > 1 CSMA/CD e=2.718