Local Area Networks - WPI

Local Area Networks - WPI

LANs Studying Local Area Networks Via Media Access Control (MAC) SubLayer Networks: Local Area Networks 1 Local Area Networks Aloha Slotted Aloha CSMA (non-persistent, 1-persistent, ppersistent) CSMA/CD Ethernet Token Ring Networks: Local Area Networks 2 Network Layer Network Layer

802.2 Logical Link Control LLC Data Link Layer MAC Physical Layer 802.3 CSMA-CD 802.5 Token Ring 802.11 Wireless LAN Other LANs

Various Physical Layers IEEE 802 Copyright 2000 The McGraw Hill Companies Networks: Local Area Networks Physical Layer OSI Figure 6.11 3 1 3 2 4

Shared Multiple Access Medium 5 M Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.1 4 Static Channel Allocation Problem The history of broadcast networks includes satellite and packet radio networks. Let us view a satellite as a repeater amplifying and rebroadcasting everything that comes in.

To generalize this problem, consider networks where every frame sent is automatically received by every site (node). Networks: Local Area Networks 5 = fin Satellite Channel = fout Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.3 6 Static Channel Allocation Problem

We model this situation as n independent users (one per node), each wanting to communicate with another user and they have no other form of communication. Channel Allocation Problem To manage a single broadcast channel which must be shared efficiently and fairly among n uncoordinated users. Networks: Local Area Networks 7 Ring networks Multitapped Bus Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.5

8 Possible Model Assumptions for Channel Allocation Problem 0. Listen property :: (applies to satellites) The sender is able to listen to sent frame one round-trip after sending it. no need for explicit ACKs 1. Model consists of n independent stations. 2. A single channel is available for communications. Networks: Local Area Networks 9 Possible Model Assumptions for Channel Allocation Problem 3. Collision Assumption :: If two frames are transmitted simultaneously, they overlap in time and the resulting signal is garbled. This event is a collision. 4a. Continuous Time Assumption :: frame transmissions can begin at any time instant. 4b. Slotted Time Assumption :: time is divided into discrete intervals (slots). Frame transmissions

always begin at the start of a time slot. Networks: Local Area Networks 10 Possible Model Assumptions for Channel Allocation Problem 5a. Carrier Sense Assumption :: Stations can tell if the channel is busy (in use) before trying to use it. If the channel is busy, no station will attempt to use the channel until it is idle. 5b. No Carrier Sense Assumption :: Stations are unable to sense channel before attempting to send a frame. They just go ahead and transmit a frame. Networks: Local Area Networks 11 a :: Relative Propagation Time a = length of the data path (in bits) -------------------------------------------------length of a standard frame (in bits)

-ORa = propagation time ( in seconds) -----------------------------------------------transmission time (in seconds) -ORa= delay-bandwidth product* ----------------------------------------- [ LG&W def p.346] average frame size * Delay-bandwidth product :: the product of the capacity (bit rate) and the delay. Networks: Local Area Networks 12 Networks: Local Area Networks 13 Relative Propagation Time

R = capacity (data rate) d = maximum distance of communications path v = propagation velocity (Assume v = 2/3 speed of light 2 x 108 meters/second) L = frame length d/v a = ------L/R = Rd -----vL Networks: Local Area Networks 14 Upper Bound on Utilization for Shared Media LAN Assume a perfect, efficient access that allows one transmission at a time where there are no collisions, no retransmissions, no delays between transmissions and no bits wasted on overhead.

{These are best-case assumptions} Tput Util = --------------- = Capacity L -----------------------------------------------propagation time + transmission time -------------------------------------------------------R Networks: Local Area Networks 15 Maximum Utilization for LANs L max. Util --------------d L = ---- + ---v R ------------------R =

max. Util L --------------- = Rd ---- + L v 1 -----------a + 1 1 = --------1 + a Networks: Local Area Networks 16 A transmits A at t = 0 A detects

collision at t = 2 tprop Distance d meters tprop = d / seconds B A B A B Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks B transmits before t = tprop and detects

collision shortly thereafter Figure 6.7 17 Networks: Local Area Networks 18 Efficiency [LG&W p.346] L 1 Efficiency = --------------- = ----------L + 2t prop R 1 + 2a Why is this result different? Networks: Local Area Networks 19 LAN Design considering Performance

For broadcast LANs what are the factors under the designers control that affect LAN performance? Capacity {function of media} Propagation delay {function of media, distance} Bits /frame (frame size) MAC protocol Offered load depends on how retransmissions are handled Number of stations Error rate Networks: Local Area Networks 20 Historic LAN Performance Notation I :: input load - the total (normalized) rate of data generated by all n stations G :: offered load the total (normalized) data rate presented to the network including retransmissions S :: throughput of LAN - the total (normalized) data rate transferred between stations D :: average frame delay the time from when a frame is ready for transmission until completion of a

successful transmission. Networks: Local Area Networks 21 Normalizing Throughput (S) [assuming one packet = one frame] Throughput (S) is normalized using packets/packet time where packet time :: the time to transmit a standard fixedlength packet i.e., packet length packet time = ----------------bit rate NOTE: Since the channel capacity is one packet /packet time, S can be viewed as throughput as a fraction of capacity. Represented in LG&W by in later graphs. Networks: Local Area Networks 22

Historic LAN Performance Notation retransmissions 1 2 3 n I G S X X X D Networks: Local Area Networks

23 Typical frame delay versus throughput performance Transfer Delay E[T]/E[X] 1 max 1 Load Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.8

24 Delay-Throughput Performance Dependence on a E[T]/E[X] a > a a Transfer Delay a 1 max Copyright 2000 The McGraw Hill Companies max 1 Load Leon-Garcia & Widjaja: Communication Networks

Networks: Local Area Networks Figure 6.9 25 ALOHA Abramson solved the channel allocation problem for ground radio at University of Hawaii in 1970s Aloha Transmission Strategy Stations transmit whenever they have data to send Collisions will occur and colliding frames are destroyed Aloha Retransmission Strategy Station waits a random amount of time before sending again Networks: Local Area Networks 26 ALOHA First transmission

t0-X t0 t0+X Vulnerable period Retransmission t0+X+2tprop Time-out t0+X+2tprop Backoff period t Retransmission if necessary

random backoff period B Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.16 27 Networks: Local Area Networks 28 Slotted ALOHA (Roberts 1972) uses discrete time intervals as slots (i.e., slot = one packet transmission time) and synchronize send time (e.g., use pip from a satellite) Slotted Aloha Strategy Stations transmit ONLY at the beginning of a time slot Collisions will occur and colliding frames are

destroyed Slotted Aloha Retransmission Strategy Station waits a random amount of time before sending again Networks: Local Area Networks 29 Slotted ALOHA kX (k+1)X Vulnerable period t0 +X+2tprop Time-out t t0 +X+2tprop Backoff period Retransmission if necessary

random backoff period B slots Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.18 30 ALOHA and Slotted ALOHA Throughput versus Load 0.4 0.368 0.35 0.3 S

Ge-G 0.25 0.184 0.2 0.15 0.1 Ge-2G 0.05 8 4 2 1 0.5

0.25 0.125 0.0625 0.03125 0.01563 0 G Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks Figure 6.17 31 Non-Persistent CSMA (Carrier Sense with

Multiple Access) nonpersistent CSMA {less greedy} 1. Sense the channel. 2. IF the channel is idle, THEN transmit. 3. IF the channel is busy, THEN wait a random amount of time and start over. Networks: Local Area Networks 32 1 - Persistent CSMA (Carrier Sense with Multiple Access) 1 - persistent CSMA {selfish} 1. Sense the channel. 2. IF the channel is idle, THEN transmit. 3. IF the channel is busy, THEN continue to listen until channel is idle. Now transmit immediately. Networks: Local Area Networks 33

P - Persistent CSMA (Carrier Sense with Multiple Access) p - persistent CSMA {a slotted approximation} 1. Sense the channel. 2. IF the channel is idle, THEN with probability p transmit and with probability (1-p) delay for one time slot and start over. 3. IF the channel is busy, THEN delay one time-slot and start over. Networks: Local Area Networks 34 P Persistent CSMA details the time slot is usually set to the maximum propagation delay. as p decreases, stations wait longer to transmit but the number of collisions decreases Considerations for the choice of p: (n x p) must be < 1 for stability, where n is

maximum number of stations, i.e., p < 1/n Networks: Local Area Networks 35 CSMA Collisions In all three cases a collision is possible. CSMA determines collisions by the lack of an ACK which results in a TIMEOUT. {This is extremely expensive with respect to performance.} If a collision occurs, THEN wait a random amount of time and start over. Networks: Local Area Networks 36 CSMA/CD Collisions If a collision is detected during transmission, THEN immediately cease transmitting the frame. The first station to detect a collision sends a jam signal to all stations to indicate that there has been a collision.

After receiving a jam signal, a station that was attempting to transmit waits a random amount of time before attempting to retransmit. The maximum time needed to detect a collision = 2 x propagation delay. Networks: Local Area Networks 37 CSMA vs CSMA/CD CSMA is essentially a historical technology now. If propagation time is short compared to transmission time, station can be listening before sending with CSMA Collision detection (CD) accomplished by detecting voltage levels outside acceptable range. Thus attenuation limits distance without a repeater. If the collision time is short compared to packet time (i.e., small a), performance will increase due to CD Networks: Local Area Networks 38 frame

contention frame Probability of 1 successful transmission: Psuccess np(1 p)n 1 Psuccess is maximized at p=1/n: max Psuccess n(1 1 n 1 1 ) n e Pmax 0.6 0.5 0.4 0.3

0.2 0.1 0 2 4 6 8 10 12 14 16 n Networks: Local Area Networks 39 Figure 6.23 Throughput vs Load varying a 0.6 S 1-Persistent CSMA 0.53 0.5 0.4 0.3

a = 0.01 0.2 0.45 a = 0.1 0.1 0.16 Copyright 2000 The McGraw Hill Companies a = 0.01 Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks 64 32 16

8 4 2 1 0.5 0.25 0.13 0.06 0.03 0.02 0 G

Figure 6.21 - Part 2 40 Throughput vs Load varying a S 0.81 0.9 0.8 0.7 Non-Persistent CSMA 0.01 0.6 0.51 0.5 0.4

0.3 0.14 0.2 0.1 0.1 64 32 16 8 4 2 1

0.5 0.25 0.13 0.06 0.03 0.02 0 G 1 Copyright 2000 The McGraw Hill Companies Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks

Figure 6.21 - Part 1 41 Maximum Achievable Throughputs 1 CSMA/CD 1-P CSMA 0.8 max Non-P CSMA 0.6 Slotted Aloha 0.4 Aloh

a 0.2 0 0.01 Copyright 2000 The McGraw Hill Companies 0.1 Leon-Garcia & Widjaja: Communication Networks Networks: Local Area Networks 1 a Figure 6.24 42 Frame Delay varying a

CSMA-CD a = 0.2 30 25 20 15 10 5 0.96 0.9 0.84 0.78 0.72 0.66 0.6

0.54 0.48 0.42 0.36 0.3 0.24 0.18 0.12 0.06 0 0 Avg. Transfer Delay

a = 0.01 a = 0.1 Load Networks: Local Area Networks 43 Figure 6.51

Recently Viewed Presentations

  • Excel Data Analysis Tools - Computer Science and Engineering

    Excel Data Analysis Tools - Computer Science and Engineering

    Descriptive Statistics (DS) versus Functions. DS do not auto update; functions do (for the most part) Quick check goes to DS; functions take a while to set up. If functions are unknown, then DS easier to auto create. ... Excel...
  • The Great Gatsby - Tri-Valley Local School District

    The Great Gatsby - Tri-Valley Local School District

    The Great Gatsby. Chapters 2 and 3. You will be working with a partner; however, you must have your own paper with answers. ... In what way is Gatsby's behavior at the party unlike the behavior of most of his...
  • Cells: The Basic Units of Life

    Cells: The Basic Units of Life

    Cells: The Basic Units of Life By: Mr. Hunter Elodea Microscope Microscope Robert Hooke Invented the microscope Viewed cork under the microscope; assigned the name cells to the "little rooms" he saw Thought animals were not made of cells Anton...
  • Présentation PowerPoint

    Présentation PowerPoint

    Ré Sol Do Ré Sol Do Ré Sol Ré Sol Ré Sol Do La Ré Sol Do Ré Sol Do Ré Mim Fa#m Sol Sim Mim Do La 26 MA PHILOSOPHIE Amel Bent Je n'ai qu'une philosophie, Être acceptée comme...
  • Презентация PowerPoint

    Презентация PowerPoint

    Dolphin Steel . Ltd. ... We offer delivery for the needs of public transport tram rails T62 and NT1 analog rails 60R1-R3, as well as laying the rails . RTZHB, LK1, B1 and components for arrangement of switches and crossings....
  • KARUJÕMM KALA PÜÜDMAS R. Valmseni järgi

    KARUJÕMM KALA PÜÜDMAS R. Valmseni järgi

    KARUJÕMM PÜÜAB KALA R. Valmseni järgi R. Valmsen "KARUJÕMMI KÄPAJÄLJED" AS Ajakirjade Kirjastus Tallinn, 2010 Lk 13-15 Eesti keele lugemik-tööraamat 4.klassile 4.osa lk 68
  • Growing Assessment Literacy Skills Throughout a District Terri

    Growing Assessment Literacy Skills Throughout a District Terri

    An assessment literate individual is one who understands how student assessment can enable them to better carry out their role in education, believes that assessment can improve teaching and learning, and puts into place activities and behaviors to act on...
  • Statistical lingua franca is R - Montefiore Institute

    Statistical lingua franca is R - Montefiore Institute

    R is a scripting language and, as such, is much more easier to learn than other compiled languages such as C. R has reasonably well written documentation (vignettes) Syntax in R is simple and intuitive if one has basic statistics...