Datacommchapter 5 Part1

Chapter 5 Multiple Access Networks

1 Main reference: Copyright © The McGraw-Hill Companies Inc.

PART 1: 5.1: RANDOM ACCESS 5.2 CONTROLLED ACCESS

2

Introduction

Local Area Network [LAN] - used to interconnect distributed communities of computerbased DTEs located within a single building or localized group of buildings - also referred to as private data networks Advantage: i. Inexpensive and fast interconnections of minicomputers, PCs, workstations, etc., in business, education and research environments ii. Allow users to share expensive resources, such as repository data [e.g., file servers] repository knowledge [e.g., database servers] service provider [e.g., printer, plotter]

3

Characteristics: i. Moderate-size geographic area [diameter of no more than a few km] ii. Located within a single building or localized group of buildings [warehouse, campus, hostel] iii. Total data rate of at least several Mbps iv. Complete ownership by a single organization The link layer is divided into 2 sub layers: Application i. Logical link control (LLC) Presentation ii. Medium access control (MAC) Session Transport Network LLC MAC Physical

Link layer

4

Medium Access Control [MAC] - regulates the access to the shared link Logical Link Control [LLC] - implements reliable packet transmission [flow and error control] LLC sublayer was originally designed to be the same for all LAN for interoperability Standards - MAC: IEEE 802.3-12 - LLC: IEEE 802.2 Most common protocols - ALOHA, Ethernet, Token Ring, WIFI Two main classes of LANs: i. Wired LANs ii. Wireless LANs 5

Main performance parameters of interest - Throughput: maximum bit transmission rate when the LAN is heavily loaded - Efficiency: fraction of throughput to channel rate - Delay: typical time taken to transmit a packet between two nodes

6

IEEE 802




LAN protocols are concerned principally with lower layers of the OSI Model. Thus, higher-layer protocols are independent of network architecture and are applicable to LANs, MANs and WANs. IEEE 802 LAN/MAN Standards Committee (www.ieee802.org) has developed the IEEE 802 reference model for LAN specifications. OSI reference model

Application Presentation Session Transport Network Data link layer

IEEE 802 reference model

Upper layer protocol

LLC service access point [LSAP]

() () () Logical link control Medium access control

Physical

Physical

Medium

Medium

Scope of IEEE 802 standards

7













The lowest layer of the IEEE 802 reference model corresponds to the physical layer of the OSI model and includes functions: - Encoding/decoding signal - Preamble generation/removal [for synchronization] - Bit transmission/reception In addition, the physical layer of 802 model also includes specification of transmission medium and topology, as the choice of transmission medium and topology is critical in LAN. The data link layer in OSI model is implemented as 2 sublayers in IEEE 802 model: - logical link control [LLC] - medium access control [MAC] Logical link control layer provides interface to higher layers and perform flow and error control. 8







Medium access control layer provides functions such as: - assemble data into frame with address and error-detection fields on transmission - dissemble frame and perform address recognition and error detection on reception - Govern access to the LAN transmission medium The separation is required because: - The logic required to manage access to a shared-access medium is not found in traditional layer 2 data link control - For the same LLC, several MAC options may be provided

9

The architecture of IEEE 802 LAN standards

NL etc.

IEEE 802.1 Higher Layer Interfaces Bridging , Management , etc.

LLC

IEEE 802 .2

100(Base)

Shielded twisted pair Optical fiber

VG-AnyLAN

IEEE 802.12

Radio Infrared

Wireless

IEEE 802.11

Optical Fiber

DQDB

IEEE 802.6

Optical Fiber

Token Ring

FDDI

IEEE 802.5

Unshielded twisted pair Shielded twisted pair

Token Ring

Token Bus

IEEE 802.4

Unshielded twisted pair Broadband coaxial Optical fiber

IEEE 802.3

PHY

CSMA/CD

Broadband coaxial Optical fiber

MAC

1. Unacked CL 2. Acked CL 3. CO

CL – connectionless CO – connection oriented 10

Taxonomy of multiple-access protocols


.


.

11

5.1 RANDOM ACCESS In random access or contention methods, no station is superior to another station and none is assigned the control over another. No station permits, or does not permit, another station to send. At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send.

12

ALOHA


First Multiple Access Protocol using contention scheme
Precursor to CSMA/CD
Applicable to any shared transmission medium: radio transmitters, coaxial cable, twisted pair or optical fiber
Two versions:
Pure ALOHA
Slotted ALOHA
Pure ALOHA is the original ALOHA
Each station starts transmitting whenever it has data to send
After transmitting a data frame, the sender expects the receiver to send an acknowledgment. 13

PURE ALOHA


If the acknowledgement does not arrive after a timeout period, the sender assumes that the data frame has been destroyed and resends the frame.
If all stations experience collision try to resend their data frames after the timeout period, the data frames will collide again.
To overcome this, each station waits a random amount of time before resending its data frame.
This random waiting time is called the backoff time (TB) and it helps avoid more collisions.
To avoid congesting the channel with retransmitted frames, a station must give up after a maximum number of retransmission attempts 14

Frames in a pure ALOHA network





As there is only one channel to share, there is a possibility of collision if more stations are sending at about the same time. Due to its simplicity, the number of collisions rises rapidly with increased load.

15

Procedure for pure ALOHA protocol

16

Example 1 The stations on a wireless ALOHA network are a maximum of 600 km apart. If we assume that signals propagate at 3 × 108 m/s, we find Tp = (600 × 105 ) / (3 × 108 ) = 2 ms. Now we can find the value of TB for different values of K. a. For K = 1, the range is {0, 1}. The station needs to| generate a random number with a value of 0 or 1. This means that TB is either 0 ms (0 × 2) or 2 ms (1 × 2), based on the outcome of the random variable.

17

Example 1(continued) b. For K = 2, the range is {0, 1, 2, 3}. This means that TB can be 0, 2, 4, or 6 ms, based on the outcome of the random variable. c. For K = 3, the range is {0, 1, 2, 3, 4, 5, 6, 7}. This means that TB can be 0, 2, 4, . . . , 14 ms, based on the outcome of the random variable. d. We need to mention that if K > 10, it is normally set to 10.

18

Vulnerable time for pure ALOHA protocol






Vulnerable time is the duration with a possibility of collision Consider 3 stations (A, B & C) with each station sending a fixed length data frame taking transmission time Tfr Pure ALOHA vulnerable time= 2 x Tfr 19

Example 2 A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the requirement to make this frame collision-free? Solution Average frame transmission time Tfr is 200 bits/200 kbps or 1 ms. The vulnerable time is 2 × 1 ms = 2 ms. This means no station should send later than 1 ms before this station starts transmission and no station should start sending during the one 1-ms period that this station is sending.

20

Note The throughput for pure ALOHA is S = G × e −2G . The maximum throughput Smax = 0.184 when G= (1/2).

21

Example 3 A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces a. 1000 frames per second b. 500 frames per second c. 250 frames per second. Solution The frame transmission time is 200/200 kbps or 1 ms. a. If the system creates 1000 frames per second, this is 1 frame per millisecond. The load is 1. In this case S = G× e−2 G or S = 0.135 (13.5 percent). This means that the throughput is 1000 × 0.135 = 135 frames. Only 135 frames out of 1000 will probably survive. 22

Example 3 (continued) b. If the system creates 500 frames per second, this is (1/2) frame per millisecond. The load is (1/2). In this case S = G × e −2G or S = 0.184 (18.4 percent). This means that the throughput is 500 × 0.184 = 92 and that only 92 frames out of 500 will probably survive. Note that this is the maximum throughput case, percentagewise. c. If the system creates 250 frames per second, this is (1/4) frame per millisecond. The load is (1/4). In this case S = G × e −2G or S = 0.152 (15.2 percent). This means that the throughput is 250 × 0.152 = 38. Only 38 frames out of 250 will probably survive. 23

Frames in a slotted ALOHA network







Pure ALOHA has a vulnerable time of 2Tfr as there is no rule that defines when a station can send (stations may send at arbitrary time) Slotted ALOHA was invented to improve the efficiency In slotted ALOHA, time is divided into slots of Tfr each Each station can only transmit at the beginning of the time slot

24

Note The throughput for slotted ALOHA is S = G × e−G . The maximum throughput Smax = 0.368 when G = 1.

25

Vulnerable time for slotted ALOHA protocol



There is still possibility of collision as two or more stations may send in the same time slot Nonetheless, the vulnerable time is reduced to only Tfrc

26






Efficiency ratio (ratio of throughput achieved to channel rate) o Pure ALOHA = 0.184 o Slotted ALOHA=0.368 Both versions exhibit poor utilization as they fail to take advantage of short propagation delay (w.r.t frame transmission time) in LANs For short propagation delay, when a station launches a frame, a;; other station will know it almost immediately ⇒CSMA

27

Example 4 A slotted ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces a. 1000 frames per second b. 500 frames per second c. 250 frames per second. Solution The frame transmission time is 200/200 kbps or 1 ms. a. If the system creates 1000 frames per second, this is 1 frame per millisecond. The load is 1. In this case S = G× e−G or S = 0.368 (36.8 percent). This means that the throughput is 1000 × 0.0368 = 368 frames. Only 386 frames out of 1000 will probably survive. 28

Example 4 (continued) b. If the system creates 500 frames per second, this is (1/2) frame per millisecond. The load is (1/2). In this case S = G × e−G or S = 0.303 (30.3 percent). This means that the throughput is 500 × 0.0303 = 151. Only 151 frames out of 500 will probably survive. c. If the system creates 250 frames per second, this is (1/4) frame per millisecond. The load is (1/4). In this case S = G × e −G or S = 0.195 (19.5 percent). This means that the throughput is 250 × 0.195 = 49. Only 49 frames out of 250 will probably survive. 29

Carrier Sense Multiple Access (CSMA)









CSMA is a polite version of ALOHA With CSMA, a station wishing to transmit first listens to the medium (carrier sense) and obeys the following rules: 1) If the medium is idle, transmit; otherwise, go to step 2 2) If the medium is busy, continue to listen for idle medium; when medium becomes idle, transmit whole frame immediately CSMA reduces the possibility of collision, but cannot eliminate it Even though each station listens to the medium before transmitting, collision still exists due to propagation delay When a frame is sent, it takes a while(though very short) for every station to sense it A station may sense the medium and find it idle, only because the frame has not yet reach the station

30

Space/time model of the collision in CSMA



CSMA reduces the possibility of collision, but cannot eliminate it Collision still exists because of propagation delay

At time t1, B senses that the medium is idle and send a frame. At time t2(t2 > t1), C senses that the medium is idle(as the frame from B has not arrived at C yet) and sends a frame Both frames collide and are destroyed

31

Vulnerable time in CSMA





The vulnerable time for CSMA is the propagation time, Tp (the time time for a signal to propagate from one end to another end of the medium) If the first bit of the frame reaches the end of the medium, every station will already have heard the bit and will refrain from sending Consider the worst case where A at one end is sending a frame This frame is susceptible for collision until its first bit arrives at the other end.

32

Behavior of three persistence methods



Persistence Strategy defines the procedure for a station that senses a busy medium. Two strategies: 1) Non-persistent o A station with frame to send senses the medium o If the medium is idle, it sends immediately o If the medium is busy, it waits a random time before sensing the medium again o Reduce the chance of collision as stations are unlikely to wait the same amount of time o Lower efficiency as the medium may be idle while the stations are waiting

33

2) Persistent o A station with frame to send senses the medium o If the medium is idle, it sends immediately o If the medium is busy, a) 1-persistent - The station sends a frame immediately ( with a probability of 1) if the medium is sensed idle -Increase the chance of collision as 2 or more stations may send their frames simultaneously after finding the medium idle.

34

b) p-persistent - The station send with probability p (i.e. may or may not send) if the medium is sensed idle - Reduce chance of collision and improve efficiency

35

Flow diagram for three persistence methods

36

Carrier Sense Multiple Access with Collision Detection (CSMA/CD)





With CSMA, the medium remains unusable for the duration of frame transmission when two frames collide For long frames, the amount of wasted capacity can be significant [wasted time equal to frame transmission time] This waste can be reduced if a station continues to listen to the medium while transmitting [collision detection] How to detect: i. The station sends frame and senses the medium ii. Collision detected if Coax:station senses power exceeding transmitted signal strength [maximum length must be restricted to limit signal attenuation] UTP: there is signal on more than one port [sensed by hub and collision presence signal is generated and sent to all stations] 37




In CSMA/CD, a station wishing to transmit obey these rules: i. If the station senses that the channel is idle (for 96 bit times), it start to transmit the data frame and go to step (iii), otherwise go to step (ii). ii. If the channel is busy, the station waits (1-persistent) until it senses that the channel is idle for 96 bit times and start to transmit the frame and go to step (iii). iii. While transmitting, it monitors the channel for possible collision; if it transmits the entire frame without collision, the transmission is considered as successful. iv. If collision is detected, the station stops transmitting its frame, transmit a 48-bit jam signal and go to step (v) v. After aborting, the station enters an exponential backoff phase and waits a random time before returns to step (i) 38

Binary Exponential Backoff



When transmitting a given frame, after experiencing the nth collision in a row for this frame, the station chooses a value K at random from {0, 1, 2, …2m-1}, where m = min(n, 10). The station then waits K slot times before it attempts to transmit 1st 2nd 3rd mth

collision waits 0 or 1 slot time collision waits 0, 1, 2 or 3 slot times collision waits 0, 1, 2 … 7 slot times collision waits 0 … 2m-1 slot times

After 10th collision, m fixed at 10 After 16th collision, frame is discarded and report failure to upper layer

Note: Slot time = worst-case round-trip propagation time

39






In the presence of collisions, the mean value of the random delay is doubled after each collision As congestion increases, stations back off by larger and larger amount to reduce the probability of collision After 16 unsuccessful attempts, the station gives up and report an error to the upper layer

40

CSMA/CD with exponential backoff

41

Collision Detection & Frame Transmission time






In CSMA/CD, the transmitting station senses the voltage levels before and during transmissions A collision results in a change of voltage level, and it takes time to propagate back to the station

A station will only sense collision while transmitting; if a very short frame is transmitted, the station might stop transmitting/sensing before the collision signal arrives. 42




Consider the worst case scenario : A

B

C

D

t=0

t = tp

t = 2tp

i. At t = 0, A transmits a frame onto the medium. ii. At t = Tp − ε, frame from A almost arrives at D. iii. At t = Tp, D just starts to transmit frame onto medium. It immediately detects collision and transmit a jamming signal iv. At t = 2Tp, A detects the collision. Note: Tp is the end-to-end propagation time. 43





The amount of time required to detect a collision is no greater than twice the end-to-end propagation delay A frame must take at least 2Tp to send to prevent the sender from incorrectly concludes that the transmission was successfully

A starts to transmit frame A has been completely transmitted the frame B starts to transmit frame prior detecting frame from A Collision occurs

Collision propagates throught the network A does not detect the collision 44 as it has finished transmission

1. A starts to transmit frame

2. A continue to sense medium while transmitting

3. B starts to transmit frame just before frame from A arrives

A

7. A transmit 48bit jam signal 6. A detects collision and stop transmitting

B

5. Collision propagates through the network

4. Collision occurs 45

Example 5 A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal, as we see later) is 25.6 µs, what is the minimum size of the frame? Solution The frame transmission time is Tfr = 2 × Tp = 51.2 µs. This means, in the worst case, a station needs to transmit for a period of 51.2 µs to detect the collision. The minimum size of the frame is 10 Mbps × 51.2 µs = 512 bits or 64 bytes. This is actually the minimum size of the frame for Standard Ethernet. 46







Major difference between ALOHA and CSMA/CD - ALOHA: transmit as soon as there is a frame to be sent - CSMA/CD:wait first for the channel to be idle before a frame is transmitted Efficiency of CSMA/CD (empirical):

1 1 + 5a end − to − end propagationdelay a= frame transmissi on time U=

where




CSMA/CD will be more efficient than - pure ALOHA for a < 0.89 - slotted ALOHA for a < 0.34

47

Example of a > 1 and a < 1

48

5.2 CONTROLLED ACCESS

In controlled access, the stations consult one another to find which station has the right to send. A station cannot send unless it has been authorized by other stations.

49

Reservation access method


A station needs to make a reservation before sending data.
Time is divided into intervals.
In each interval, a reservation frame frame precedes the data frames sent in that interval. 50

Select and poll functions in polling access method





All data exchanges must be made through the primary device even when the ultimate destination is a secondary device. The primary device controls the link; the secondary devices follow its instruction

51

Logical ring and physical topology in token-passing access method






The stations in a network are organized in a logical ring. Each processor has a predecessor and a successor. A special packet called a token circulates through the ring 52