COMMUNICATION NETWORKS : Data Link Layer

Selective-Repeat ARQ: Sliding Window Protocol

Fig: Selective Repeat ARQ, Lost frame

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS : Data Link Layer
Selective-Repeat ARQ: Sliding Window Protocol
In Selective Repeat ARQ, the size of the sender and receiver window must
be at most one-half of 2m.

Fig: Selective Repeat ARQ, sender window size

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS : Data Link Layer
Error Control: Maximum Utilization of Protocol

α  Tprop / Tframe P  Prob. of error W  Window Size

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS : Data Link Layer
Sliding Window Protocol:
Problem 1: Consider the use of 10 K-bit size frames on a 10 Mbps satellite
channel with 270 ms delay. What is the link utilization for Go-back-N ARQ
technique with window size of 7 assuming P = 10-3 ?
Solution:

Channel utilization for go-back-N = N(1 – P) / (1 + 2a)(1-P+NP)

P = probability of single frame error ≈ 10-3

Channel utilization ≈ 0.01285 = 1.285%

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS : Data Link Layer
Sliding Window Protocol:
Problem 2: Consider a 10 KB/s link with 100ms propagation delay (latency)
and frame size of 1 KB. If we use a sliding window protocol with the sender
window size of 5, what is the maximum link utilization?
Solution:
W = windows size of sliding window protocol = 5

Tprop(Latency) = 100ms Tframe = 100ms

a = Tprop / Tframe = 100/100 = 1

Link utilization in sliding window Protocol

= W / (2a +1) if W < (2a+1)
=1 if W > (2a+1) where W  Window Size
So, 2x+1=2(1)+1=3 Since W>(2x+1) i.e 5>3
So Link utilization is 100% when window size is 5.
25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS : Data Link Layer
Sliding Window Protocol:
Problem 3: If there is a 64 Mbps point-to-point link between earth and
planet which are separated by a distance of 9 × 1010 m. If the frame size is
32 KB, If we use sliding window protocol, what is the sender window size
that gives 100% link utilization?
Hint: The processing times at the sender and the receiver are ignored.
Answer: The sender window size = 150001 frames.

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS : Data Link Layer
Stop-and-Wait Protocol:
Problem 4: The frames of 1Kb each are generated at node A and sent to
node C through node B. The links between A and B, B and C are full-duplex,
error-free.

The data rate between A and B is 100 kbps.

The propagation delay is 5 µsec/km for both lines
ACK frames are separate frames of negligible length.
Between A and B, a sliding window protocol is used, with a window size of 3.
Between B and C, stop-and-wait protocol is used.

Find the data rate of B  C link to avoid buffer overflow at node B.

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer:

Who goes next on a multi-access channel ?
Channel Allocation Problem
How to allocate a single broadcast channel among competing users ?

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

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.
ALOHA: Pure ALOHA, Slotted ALOHA

CSMA (Carrier Sense Multiple Access): Persistent CSMA, Non-persistent CSMA

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

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:
• Each source in a network sends data whenever there is a frame to send.

• If the frame successfully reaches the destination, the next frame is sent.

• Collision can be sensed by each station by listening to its own burst or

awaiting the acknowledgement of receipt.

• If the frame fails to be received at the destination, it is sent again after a

random amount of time.

• As networks become more complex, eg. in an Ethernet system trouble occurs

because data frames collide

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Random Access Protocols
Pure ALOHA Protocol:

Figure: Frames in a pure ALOHA network

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:

Figure: Frames in a pure ALOHA network

25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:

Figure: Frames in a pure ALOHA network

If the first bit of a new frame overlaps with just the last bit of a frame almost finished, both
the frames will be totally destroyed. It does not distinguish between a total loss or a near miss.
25-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2
 QUERIES ?

25-Aug- RAVILLA DILLI, ECE, MIT, Manipal, India

25-Aug- RAVILLA DILLI, ECE, MIT, Manipal, India
28-Aug- RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Revision of the Syllabus for 1st Sessional

Practice Problems

28-Aug- RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS : Data Link Layer
Physical Layer:
Problem 1: If the 100BASET cable is used to transmit frames of minimum
size 64KB. How much of the wire is occupied by a single bit?
Problem 2: Assume that SNR = 36dB and the channel bandwidth is 2 MHz.
What is the theoretical channel capacity ?
Problem 3: We need to send 265 kbps over a noiseless channel with a
bandwidth of 20 kHz. How many minimum number of bits required to
represent signal levels?
Problem 4: We have a channel with a 1-MHz bandwidth. The SNR for this
channel is 63. What are the appropriate bit rate and signal level?
Problem 5: What is the minimum SNR IN dB, that must be maintained in
order to transmit a 600Kbps signal over a medium with a bandwidth of
20,000Hz?
Problem 6: We would like to use “CAT-5” twisted-pair cable to transmit
information at a bit rate of 500Mbps. Is a signal-to-noise ratio of 30dB
enough to reliably transmit this much information? Why or why not?
28-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS : Data Link Layer
Stop-and-Wait Protocol:
Problem 7: Consider a 1.5 Mbps link with 45 sec as RTT. If a Stop-and-wait
Protocol is used with a frame size of 1 KB. What is the maximum link
efficiency ?
Problem 8: If there is a 64 Mbps point-to-point link between earth and
planet which are separated by a distance of 9 × 1010 m. If the frame size is
32 KB,
i) what is the channel utilization if a stop-and-wait protocol is used ?
ii) If we use sliding window protocol, what is the sender window size that
gives 100% link utilization?
Hint: The processing times at the sender and the receiver are ignored.

28-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS : Data Link Layer
Stop-and-Wait Protocol:
Problem 9: The frames of 1Kb each are generated at node A and sent to
node C through node B. The links between A and B, B and C are full-duplex,
error-free.

The data rate between A and B is 100 kbps.

The propagation delay is 5 µsec/km for both lines
ACK frames are separate frames of negligible length.
Between A and B, a sliding window protocol is used, with a window size of 3.
Between B and C, stop-and-wait protocol is used.

Find the data rate of B  C link to avoid buffer overflow at node B.

28-Aug-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 QUERIES ?

28-Aug- RAVILLA DILLI, ECE, MIT, Manipal, India

28-Aug- RAVILLA DILLI, ECE, MIT, Manipal, India
5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Data Link Layer (DLL)

Medium Access Control Protocols (Contd.,)

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:

Vulnerable period: The time interval during which the packets are susceptible
to collisions with transmissions from other users.
5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 3
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 4

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:
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 × 103 ) / (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.
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 > 15, it is normally set to 15.

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 5
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:
Throughput (S)  number of Packets successfully (without collision)
transmitted per unit time.
The throughput for pure ALOHA is S = G × e −2G .
The maximum throughput Smax = 0.184 when G= (1/2).
G offered traffic on the channel including new transmissions
and retransmissions, and measured in packets/packet time.
Problem 1: 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 1ms period that
this station is sending.
5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 6
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:
Problem 2: 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).
Therefore, the throughput is 1000 × 0.135 = 135 frames.
Only 135 frames out of 1000 will probably survive.

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 7

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Pure ALOHA Protocol:
Solution:
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 %).
This means that the throughput is 500 × 0.184 = 92.
Only 92 frames out of 500 will probably survive.
Note: This is the max. throughput for pure ALOHA.

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 %).
This means that the throughput is 250 × 0.152 = 38.
Only 38 frames out of 250 will probably survive.

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 8

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:
• A simple way to double ALOHA’s capacity
• Make sure transmissions start on a slot boundary
• Halves window of vulnerability
• Used in cellular phone uplink

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 9

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 10

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

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

Fig: Vulnerable time for slotted ALOHA protocol

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 11
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

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

What is max fraction slots successful?

Suppose n stations have packets to send,

Each transmits in slot with probability p
Prob[successful transmission], S, = p (1-p)(n-1)
any of n nodes:
S = Prob[one transmits] = np(1-p)(n-1)
(optimal p as n->infinity = 1/n)
= 1/e = .37

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 12

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:
Problem 3: 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 millisec.
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.

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 13

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:
b. If the system creates 500 frames per second, this is (1/2) frame per millisec.
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 millisec.
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.

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 14

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:
Problem 4: A network of ‘N’ stations share a 56-kbps channel using pure ALOHA
protocol. Each station outputs a 1kb frame on an average of once every 100 sec,
even if the previous one has not yet been sent (e.g., the stations can buffer
outgoing frames). What is the maximum possible number of nodes in the network?
Solution:
With pure ALOHA the usable bandwidth is 0.184 × 56 kbps = 10.3 kbps.
Each station requires 10 bps, so N = 10300/10 = 1030 stations.
Problem 5: Ten thousand airline reservation stations are competing for the
use of a single slotted ALOHA channel. On average, each station makes 18
requests/hour. A slot is 125 μsec. What is the approximate total channel
load?
Solution: One request made by each node = (60 x 60)/18 = 200 sec,
Each node will make 1/200 requests in 1 sec.
Total load made by all 10000 stations = (1/200) x 10000 = 50 requests/sec.
Hence G = 50 requests/sec x 125 μsec = 6.25 x 10-3.
5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 15
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:
In Pure ALOHA, The prob. Of avoiding collision is e-2G

Fig: Throughput verses offered Traffic of ALOHA protocols

In Slotted ALOHA, The prob. of avoiding collision is e-G
NOTE: The Prob. of a transmission require k attempts, Pk= e-G(1-e-G)k-1
5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 16
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Slotted ALOHA Protocol:
Problem 6: A large population of ALOHA users manages to generate 50
requests/sec, including both originals and retransmissions. Time is slotted in units of
40 msec.
(a) What is the chance of success on the first attempt?
(b) What is the probability of success in the kth attempt?
(c) What is the expected number of transmission attempts needed?
Solution:
(a) Load on the channel, G = 50 req/sec x 40 msec = 2
Chance of success on the 1st attempt =The probability of avoiding collisions
= e −2
(b) e −G (1 − e −G)k-1 = 0.135 × 0.865k-1 .
(c) The expected number of transmissions is eG = 7.4.

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 17

 QUERIES ?

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

5-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
12-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Data Link Layer (DLL)

Medium Access Control Protocols (Contd.,)

12-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:
Principle: “Sense before transmit” or “listen before talk”
Each station first listen to the medium ( or check the state of the medium )
before sending.
CSMA reduces the possibility of collisions, but it can’t eliminate it.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

Figure: Space/time model of the collision in CSMA

In CSMA Protocol, Propagation delay causes the collisions.
12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

collisions can occur:

Because of Propagation delay, two
nodes may not hear each other’s
transmission.
collision: Entire packet transmission
time wasted
Note:
Role of distance and propagation delay
in determining collision probability.

Figure: Collisions in CSMA Protocol

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

At time t=0, a frame is sent on the idle medium by NIC A.

A short time later, NIC B also transmits. (In this case, the medium, as observed by
the NIC at B happens to be idle too).

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

After a period, equal to the propagation delay of the network, the NIC at B detects
the other transmission from A, and is aware of a collision, but NIC A has not yet
observed that NIC B was also transmitting.
B continues to transmit, sending the Ethernet Jam sequence (32 bits).

After one complete round trip propagation time (twice the one way propagation
delay), both NICs are aware of the collision. B will shortly cease transmission of the
Jam Sequence, however A will continue to transmit a complete Jam Sequence.
Finally the cable becomes idle.
12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

Figure: Vulnerable time in CSMA

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

Figure: Flow diagram for three persistence CSMA methods

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

Figure: Behavior of three persistence CSMA methods

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:
Behavior of three persistence CSMA methods
Persistence strategy: The procedures for a station that senses a busy
medium.
Non-persistent CSMA: A station that has a frame to send senses the line.
If the line is idle, the station sends immediately.
If the line is not idle, the station waits a random amount of time
and then senses again.
Advantage: reduces the chance of collision
Disadvantage: Reduces the efficiency of the network if the medium is idle
when there are stations that have frames to send.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:
Behavior of three persistence CSMA methods
Persistent CSMA: A station senses the line. If the line is idle, the station
sends a frame.
1-persistent: If the station finds the line idle, the station sends its frame
immediately( with probability 1)
Disadvantage: increases the chance of collision because two or more
stations may send their frames after finding the line idle.
P-persistent: If the station finds the line idle, the station may or may not
send.
It sends with the probability ‘p’ and refrains from sending
with probability ‘1-p’
Advantages: It reduces the chance of collision and improves the efficiency.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA ( Carrier Sense Multiple Access) Protocol:

Behavior of three persistence CSMA methods:

Non-persistent CSMA: Give up, or send after some random delay

Problem: May cause larger delay when channel is idle

1-Persistent CSMA: Send as soon as channel is idle

Problem: Blocked senders all try to send at once

p-Persistent CSMA: If idle, send packet with probability p, repeat

Make sure, (p * N ) < 1
where N is the maximum number of stations that can be active at a time.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA : Link Utilization of Non-persistent CSMA

Link Utilization, U

Where, α  the ratio of end-to-end propagation delay in the cable to the frame
transmission time.
G  Load on the channel

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA :

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA :

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA :

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA :

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA :

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA :

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

Fig: Comparison of Throughput verses offered Traffic of Random Access protocols

CSMA (all methods) has an inefficiency:
If a collision has occurred, the channel is unstable until colliding packets
have been fully transmitted.
12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD (Carrier Sense Multiple Access with Collision Detection) Protocol:
CSMA/CD: Listen While Talking
CSMA/CD works as follows:
 While transmitting, the sender is listening to medium for collisions.

 Sender stops transmission if collision has occurred reducing channel

wastage .

CSMA/CD is Widely used for bus topology LANs (IEEE 802.3, Ethernet).

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:
CSMA/CD performance:
Use one of the CSMA persistence algorithm (non-persistent, 1-persistent, p-
persistent) for transmission.
If a collision is detected by a station during its transmission then it should
do the following:
Abort transmission and
Transmit a jam signal (48-bit) to notify other stations of collision so that
they will discard the transmitted frame also to make sure that the
collision signal will stay until detected by the furthest station.
After sending the jam signal, backoff (wait) for a random amount of
time, then
Transmit the frame again

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA /CD Protocol:

Figure: Flow diagram for the CSMA/CD

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Random Access Protocols
CSMA /CD Protocol:

Figure: Collision of the first bit in CSMA/CD

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:
How long does it take to detect a collision?
Answer: In the worst case, twice the maximum propagation delay of the
medium. a = maximum propagation delay

Figure: Collision detection in CSMA/CD

Restrictions of CSMA / CD: Packet transmission time should be at least as
long as the time needed to detect a collision (2 * max. propagation delay +
jam sequence transmission time)
12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:

Figure: Collision and abortion in CSMA/CD Protocol

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:
Problem 1: 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) is 25.6 μs, what is the minimum size
of the frame?

Solution:
The frame transmission time is Tfr = 2 × Tp = 51.2 μs.
Therefore, in the worst case, a station needs to transmit for a period of 51.2 μs
to detect the collision.
The min. size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes.
This is actually the min. size of the frame for Standard Ethernet.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:
Problem 2: In CSMA/CD protocol, the channel has 1Mbps bit rate and max.
network span of 10 kms with no repeaters. If a medium propagation delay
of 4.5 ns / meter, find the minimum frame length ?
Solution:
Min. frame size for CSMA/CD = 2 * Tprop

Propagation Delay : Tprop = (4.5 * 10-9)*(10 * 103) = 4.5 * 10-5 sec.

Thus, Min. Frame Size = (1.0 * 106) * (9.0 * 10-5) = 11.25 bytes.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:
Problem 3: In a CSMA/CD LAN of 2 km using copper wire running at 100
Mbps, what would be the minimum frame size to hear all collisions?
Solution:
Bandwidth delay product is the amount of data on transit.
Tprop= ( lenght of wire/speed of signal).

since, copper wire i.e speed =2/3* speed of light

Tprop=(2000/(2*3*108/3)) =10us

Round Trip Time = 2 * Tprop = 20us

Minimum frame size = Bandwidth * Delay (RTT)
Frame size = Bandwidth * RTT = 100Mbps * 20us = 2000 bits

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CD Protocol:
The maximum efficiency of CSMA/CD = Tframe / ( Tframe + Overhead )

= Tframe / ( Tframe + Average Contention Interval )

= 1 / [ 1 + ( 2a / A ) ]
Where a  end-to-end propagation delay
A  the probability that a station can successfully transmit in a slot.

12-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 QUERIES ?

12-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India

12-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
14-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Data Link Layer (DLL)

Medium Access Control Protocols (Contd.,)

MAC Sublayer: Token Ring ( IEEE 802.5 )

14-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance ) Protocol:
CSMA/CA was invented for wireless networks.

Collisions are avoided through the use of three strategies:

the IFS (Inter Frame Space)
Contention Window
and ACK’s

IFS: When the channel is idle, the station does not send immediately.
The station waits for IFS time.
After the IFS time, if the channel is still idle,
Wait for a time equal to contention window slots

NOTE: The station assigned with shorter IFS has a higher priority.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance ) Protocol:
Contention Window: It is an amount of time divided into slots.
A station that is ready to send chooses a random number of slots as its wait
time.
The number of slots in the contention window changes according to the binary
exponential back-off strategy.
The station needs to sense the channel after each time slot.
If the stations finds the channel busy, it does not restart the process. It just
stops the timer and restarts it when the channel sensed as idle.
This gives priority to the station with the longest waiting time.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CA Protocol:

Figure: CSMA/CD Energy level during transmission, idleness, or collision

Figure: Timing in CSMA/CA

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Random Access Protocols

CSMA/CA Protocol:

Fig: Flow diagram for CSMA/CA

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Random Access Protocols
CSMA/CA Protocol:
DIFS  DCF Interframe spacing.
It is the time delay for which sender wait
after completing it’s backoff, before
sending RTS (Request to Send) packet.

SIFS  shortest Interframe spacing.

It is the time for which Rx wait before

sending the CTS (Clear To Send) & ACK
packet to sender, and sender waits after
receiving CTS and before sending data to
receiver. It’s main purpose is to avoid any
type of collision.

DIFS = SIFS + 2 * Slot Time

Fig: Flow diagram for CSMA/CA
14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Random Access Protocols
CSMA/CA Protocol:

Fig: Flow diagram using CSMA/CA and NAV

Network allocation vector (NAV) is a virtual carrier-sensing mechanism used
with wireless network protocols like IEEE 802.11 and IEEE 802.16 (WiMax).
14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Random Access Protocols
CSMA/CA Protocol:

Fig: Hidden Terminal Problem

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Controlled Access or Scheduling:
Provides in order access to shared medium so that every station has chance
to transfer (fair protocol)

Eliminates collision completely

Three methods for controlled access:
Reservation
Polling
Token Passing

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Controlled Access or Scheduling:

Reservation:

There is a reservation frame in the network which contains bits

corresponding to each station.

If a station has frame to transmit, it has to enable the corresponding

reservation bit the reservation frame.

Then the channel will be allotted as per the sequence.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Controlled Access or Scheduling:
Polling:

Primary is sending to
Secondary Secondary is sending to
Primary

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Controlled Access or Scheduling:
Polling:
One of the stations in the network acts as primary station.

Primary station will ask (poll) each secondary station for the frame to
transmit. If Secondary station has frame to transmit, channel will be
allotted.

If secondary station does not has a frame to transmit, it replies with NAK
to the primary station.

Primary station continues polling of the next station in the network.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Controlled Access or Scheduling:
Token Passing:

A Token (special bit stream) is continuously rotates in the network.

If a station wants to transmit a frame, first it has to seize the token.

After completion of frame transmission, it has to release the token, so that

other stations who has frame to transmit can hold the Token.

A station is not allowed to transmit a frame without holding the Token.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
 Consists of a set of nodes connected in a ring.

 Data flows in a particular direction only.

 Data received from upstream neighbor forwarded to downstream

neighbor.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
TOKEN:
“token” is a special pattern(3-bytes word) circulates around the ring.
 Each node receives and forwards Token.

 Frame makes its way back to sender

– frame removed by sender
– sender reinsert Token.

 As token circulates around ring, each station gets a chance to transmit

– Service round - robin fashion

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)

When station wants to transmit:

Waits for Token
Seizes it
Transmits frame

When the station seizes Token and begins transmission, so nobody else can
transmit.
Performance: It is fair.
Each computer is given in turn an opportunity to transmit, even when the
traffic is high.

If only one computer needs to transmit a message, it has to wait till receives
the Token.

Long messages should not be allowed.

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)

802.5 Physical Layer Characteristics:

 Date rate: 4 Mbps or 16 Mbps
 Encoding: Differential Manchester
 Max. No. of Stations : 250
 Transmission Medium: STP, UTP

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Token Ring Issues
 Any link or node failure
– Network rendered useless
 Solution : Electromechanical relay
– Station active relay is open and station included

– Station is inactive
• no power
• relay closed
• bypass station

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Data Frame Format Token Frame Format SD AC ED Token Size: 24 bits

Bytes 1 1 1 6 6 4 1 1
SD AC Destination Source FS
FC Information FCS
FCS ED
Address Address

Starting
J K 0 J K 0 0 0 J, K non-data symbols (line code)
delimiter

Access PPP Priority; T Token bit

control PPP T M RRR M Monitor bit; RRR Reservation

Frame FF frame type

FF Z Z Z Z Z Z ZZZZZZ control bit
control
Ending I intermediate-frame bit
J K 1 J K 1 I E E error-detection bit
delimiter
A address-recognized bit
Frame xx undefined
A C xx A C x x
status C frame-copied bit
Figure: IEEE 802.5 Token and data frame structure
14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)

Figure: IEEE 802.5 Token and data frame structure

14-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 QUERIES ?

14-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India

14-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Data Link Layer (DLL)

MAC Sublayer: Token Ring ( IEEE 802.5 )

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Priorities in IEEE 802.5
• Supports different levels of priority
– 3 bits
– each station waiting to send, sets priority for packet packet’s priority as high
current token
– then token can be seized
– Intending to send station – sets the priority on currently passing data frame
– releasing station sets priority of token to n.
– Lower priority packets circulate for long in ring
• Token Release
– Early release
• After transmitting packet
– Delayed release
• After removing packet when it returns to the sender

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Priority Token Ring:
Let, A  Priority Access is ‘1’(Lowest)
B, D  2; C, E  3 (highest)
Assume, ‘A’ has already seized the ring and transmitted the data frames.
So, Token is BUSY.
‘B’ places priority 2 in the reservation field within Token and it then passes
the Token to ‘C’.
‘C’ replace ‘2’ by ‘3’.
Then ‘C’ passes the frame to ‘D’.
Now, ‘D’ must defer.

‘E’ doesn’t do anything.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Station ‘A’ receives the frame back. It makes the ring free by resetting the
Token and passing the Token to ‘B’.

‘B’ is not allowed to use the Token bcoz the reservation field inside the Token
is equal to ‘3’ ( it is higher than the priority of ‘B’.)
‘C’ is allowed to seize the Token. It places its data on the ring and sends the
transmission to ‘D’.
‘D’ is now allowed to place its priority of 2 into the reservation field.
and passes the frame to ‘E’.
‘C’ is allowed to seize the Token. It places its data on the ring and sends the
transmission to ‘D’.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)

‘E’ replaces D’s priority of 2 with its priority of 3 and passes the frame to ‘A’.
‘D’ does not allowed to seize the ring since its priority of 2 less than the
reserve priority indicator of 3. So it passes the Token to ‘E’.

‘E’ seizes the ring, bcoz its priority of 3 equal to or greater than the
reservation indicator of 3.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Token Size: 24 bits
– Minimum number of stations is 24
– Overcome this by including a monitor which adds the extra bits of delay
• Token operation
– Token circulates – Modifies a bit in the second byte of token
– Station seizes a token– Station that has token transmits data
– Station drains token out of the ring
– Station sends data
– Each packet has destination address
– All stations downhill check destination address
– Destination copies packet
– Packet finds its way back to sending station
– Sending station removes packet from ring
– Station reinserts token into the ring
• Size of packet stored in the ring
– Larger/smaller than ring
• Add/remove bits
19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Issues
– Size of data that given node is allowed to transmit
– Token holding time (THT) = ∞ ?
• Utilization is 100%
• Unfair to stations to other than the station holding the token
– THT affects ring performance
Token Holding Time(THT) Token Rotation Time (TRT)

• TRT ≤ Active nodes * THT + Ring Latency

• Ring Latency – token circulation time
Reliable Transmission
• Use A and C bits
• Initially A and C zero.
• Receiver sets A bit after seeing that it is the intended recipient
• Receiver sets C bit after copying frame
• If both A and C are not set – retransmit

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Ring Latency : The no. of bits that can be simultaneously in transit around
the ring.

Token Rotation Timer (TRT): Measures the time that has elapsed since the
station last received a token.

Token Holding Time (THT): Measures the degree of activity in the ring.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
• Every station in a token ring network is either an Active monitor (AM) or
Standby monitor (SM) station.
• There can be only one AM on a ring at a time.
• The active AM is chosen through an election or monitor contention
process.

• The monitor contention process is initiated when

 A loss of signal on the ring is detected,
 An AM station is not detected by other stations, or
 When a timer on an end station expires (the station hasn't seen a
token in the past 7 seconds).
• When any of the above conditions take place and a station decides that a
new AM is needed.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
The AM performs a number of ring management functions and roles:

1. Master clock for the ring, synchronization.

2. Ensure always that there is only one token in the ring

3. Regenerate a vanished token

(no token seen for TRT => regenerate

4. Removes circulating frames from the ring (Orphan Frames).

5. Detects a broken ring.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Designated monitor :
– any station can become a monitor
– defined procedures for becoming a monitor
– healthy monitor announces that it is a monitor at periodic interval
– if a station does not see that packet for some time – then it sends a “claim
token”
– if claim token comes back to station then it is monitor
– if another wants to claim see other stations claim first some arbitration rule.

Role of monitor :
– insert additional delay in ring
– ensure always that there is a token somewhere in the ring
– regenerate a vanished token
– no token seen for TRT => regenerate

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Let, speed of ring, R = 4 Mbps,
No. of stations, M = 20
Distance b/w stations = 100 meters, and b = 2.5 bits

b  delay that each station interface introduces between when the

interface receives a frame and forwards it along the output line.

Ring Latency ( in bits) = 20 X 100 X 4 X 106/ (2 X 108) + 20(2.5) = 90 bits

Let, speed of ring, R = 16 Mbps,

No. of stations, M = 80
Distance b/w stations = 100 meters, and b = 2.5 bits

Ring Latency ( in bits) = 80 X 100 X 16 X 106/ (2 X 108) + 80(2.5) = 840 bits

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
A A A A
(a) Low Latency Ring

t=0, A begins frame t=90, return t=400, transmit t=490, reinsert

of first bit last bit token
(b) High Latency Ring
A A A A

t=0, A begins frame t=400, last bit of t=840, return of first t=1240, reinsert
frame enters ring bit token

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Problem 1: Consider a 200m, 4Mbps token ring containing 20stations, each
transmitting with equal priority. Suppose no station is allowed to transmit
more than 5000 bytes before giving up the token. Once a station gives up a
token how long will it take (in the worst case) for that station to get the
token again? Assume Speed of signal is 200 meters/µsec. ? Assume frame
processing time at each station is 2.5-bits.
Solution: Bit duration = 1/ 4 Mbps = 0.25 µsec,
TToken = 24 x 250 nsec = 6 µsec
T5000 bytes = 5000 x 8 x 0.25 µsec = 10000 µsec
TProcessing =19 x 2.5 x 0.25 µsec = 11.875 µsec
TPropagation = 200/ (2 x 108) = 1 µsec
T10 meters = 10 / (2 x 108) = 0.05 µsec
TTotal = (TToken+T10 meters)+19 x (TToken +T5000 bytes +TPropagation +TProcessing +
19 x (TToken+T10 meters)
= 20 x (6 µ + 0.05 µ ) + 19 x (6 µ + 10000 µ + 1 µ + 11.875 µ)
= 190.48 msec.
19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Problem 2: Consider a 1000m, 16Mbps token ring containing 20 stations.
Every station has data to transmit with equal priority. The maximum data
allowed to transmit is 5000 bytes before giving up the token. Once a
station gives up a token how long will it take for that station to get the
token again? Assume frame processing time at each station is 4-bits.

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 QUERIES ?

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

19-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
21-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Data Link Layer (DLL)

MAC Sublayer: Ethernet ( IEEE 802.3 )
Ethernet Performance

21-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Token Ring (IEEE 802.5)
Problem 2: Consider a 1000m, 16Mbps token ring containing 20 stations.
Every station has data to transmit with equal priority. The maximum data
allowed to transmit is 5000 bytes before giving up the token. Once a
station gives up a token how long will it take for that station to get the
token again? Assume frame processing time at each station is 4-bits.
Solution: Bit duration = 1/ 16 Mbps = 62.5 nsec,
TToken = 24 x 62.5nsec = 1.5 µsec
T5000 bytes = 5000 x 8 x 62.5nsec = 2500 µsec
TProcessing =19 x 4 x 62.5 nsec = 4.75 µsec
TPropagation = 1000/ (2 x 108) = 5 µsec
T50 meters = 50 / (2 x 108) = 0.25 µsec

TTotal = (TToken+T50 meters)+19 x (TToken +T5000 bytes +TPropagation +TProcessing +

19 x (TToken+T50 meters)
= 20 x (1.5 µ + 0.25 µ ) + 19 x (1.5 µ + 2500 µ + 5 µ + 4.75 µ)
= 47.749 msec.
21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer:

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Ethernet’s MAC Algorithm

Packet?
No

Sense Send Detect

Carrier Collision

Yes
Discard
Packet Jam channel
attempts < 16 b=CalcBackoff();
wait(b);
attempts++;
attempts == 16

Figure: State Diagram for CSMA/CD

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Ethernet’s MAC Algorithm

• Ethernet uses CSMA/CD – listens to line before/during sending
• If line is idle (no carrier sensed)
– send packet immediately
– upper bound message size of 1500 bytes
– must wait 9.6us between back-to-back frames
• If line is busy (carrier sensed)
– wait until idle and transmit packet immediately
• called 1-persistent sending
• If collision detected
– Stop sending and jam signal
– Try again later

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: Ethernet’s MAC Algorithm

Exponential Backoff:
• If a collision is detected, delay and try again
• Delay time is selected using binary exponential backoff
– 1st time: choose K from {0,1} then delay = K * 51.2us
– 2nd time: choose K from {0,1,2,3} then delay = K * 51.2us
– nth time: delay = K x 51.2us, for K=0..2n – 1
• Note max value for k = 1023
– give up after several tries (usually 16)
• Report transmit error to host
• If delay were not random, then there is a chance that sources would
retransmit in lock step
• Why not just choose from small set for K
– This works fine for a small number of hosts
– Large number of nodes would result in more collisions

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet Performance
CSMA analysis: Assumptions: –infinite population
–Poisson arrival
–fixed frame size
P[success] = e-aG , where G= Offered Load
Throughput S= G e-aG a  Propagation delay
CSMA –p-persistent: Mean length of contention interval
P  Probability of sending frame

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet Performance
CSMA –p-persistent: Mean length of contention interval
E[(i-1) collision slots followed by a success]

If ‘1/2a’ is time in slots for transmitting data, then

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3) Performance
Problem: The maximum length of a 10Base5 cable is 500 meters.
a) How long does it take for a bit to travel from the beginning to the end of
the network? Ignore any propagation delay in the equipment .
b) find the maximum time it takes for a sender to detect a collision.
c) find the minimum size of an Ethernet frame for collision detection
d) Find the bit length in the medium.
Solution: a) 500/ [(2/3) * 3* 108] = 2.5 µsec b) 5 µsec c) 6.25 bytes
d) Bit length = 2 x 108 m/sec /10 Mbps= 20 m

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: IEEE 802.3 MAC Frame structure

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: Minimum and Maximum lengths of IEEE 802.3 MAC Frame

Note: Frame length: Minimum: 64 bytes (512 bits) ,
Maximum: 1518 bytes (12,144 bits)

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: IEEE 802.3 MAC Address format

Figure: IEEE 802.3 MAC Unicast and Multicast Addresses

The least significant bit of the first byte defines the type of address.
If the bit is 0, the address is unicast; otherwise, it is multicast.
The broadcast destination address is a special case of the multicast address
in which all bits are 1s.

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Define the type of the following destination addresses:
a. 4A:30:10:21:10:1A b. 47:20:1B:2E:08:EE
c. FF:FF:FF:FF:FF:FF
Solution:
To find the type of the address, we need to look at the second hexadecimal
digit from the left.
If it is even, the address is unicast.
If it is odd, the address is multicast.
If all digits are F’s, the address is broadcast.

Therefore, we have the following:

a. This is a unicast address because A in binary is 1010.
b. This is a multicast address because 7 in binary is 0111.
c. This is a broadcast address because all digits are F’s.

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Show how the address 47:20:1B:2E:08:EE is sent out on physical line.
Solution: The address is sent left-to-right, byte by byte; for each byte, it is
sent right-to-left, bit by bit, as shown below:

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
The original Ethernet was created in 1976 at Xerox’s Palo Alto Research
Center (PARC). Since then, it has gone through four generations.

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: Categories of Standard Ethernet

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: Encoding in a Standard Ethernet implementation

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: 10Base5 Standard Ethernet implementation

Figure: 10Base2 Standard Ethernet implementation

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: 10Base-T Standard Ethernet implementation

Figure: 10Base-F Standard Ethernet implementation

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)

Figure: Summary of Standard Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Fast Ethernet (IEEE 802.3u): It was designed to compete with LAN protocols
such as FDDI or Fiber Channel.
It can transmit data 10 times faster at a rate of 100 Mbps.

Figure: Fast Ethernet topology

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Fast Ethernet (IEEE 802.3u):

Figure: Fast Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Fast Ethernet (IEEE 802.3u):

Figure: Fast Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Fast Ethernet (IEEE 802.3u):

Figure: Summary of Fast Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Gigabit Ethernet (IEEE 802.3z):

Figure: Topologies of Gigabit Ethernet

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Gigabit Ethernet (IEEE 802.3z):

Figure: Gigabit Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Gigabit Ethernet (IEEE 802.3z):

Figure: Encoding in Gigabit Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: Ethernet (IEEE 802.3)
Gigabit Ethernet (IEEE 802.3z):

Figure: Summary of Gigabit Ethernet implementations

Figure: Summary of Ten-Gigabit Ethernet implementations

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 QUERIES ?

21-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

21-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
26-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in the Section

Data Link Layer (DLL)

MAC Sublayer: FDDI

26-Sep- RAVILLA DILLI, ECE, MIT, Manipal, India 2

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: FDDI

Fiber Distributed Data Interface (FDDI)
A

E
B

C D
26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: FDDI

Topology: Ring
Type of Fiber: multimode or single mode
Distance: 200 kms
No. of stations: up to 500 stations.
• Data is encoded using a 4B/5B encoder.
• Line Encoding : NRZ-I
• Local clock is 125MHz.
• Data Rate : 100 Mbps.
• Modulation : ASK{ or Intensity Modulation}
• Wavelength: 1300 nm
• Dual rings (primary and secondary) –transmit in opposite directions
• Normally, second ring is idle and used for redundancy for automatic
repair (self-healing).

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: FDDI

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: FDDI

Token Frame Format
PRE SD FC ED

FDDI frame structure

8 1 1 2 or 6 2 or 6 4 1 1
Destination Source
PRE SD FC Information FCS ED FS
Address Address
Preamble Data Frame Format

Frame CLFFZZZZ C = Synch/Asynchrnous

Control L = Address length (16 or 48 bits)
FF = LLC/MAC control/reserved frame type

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Medium Access Control (MAC) Sub layer: FDDI
Preamble: Synchronizes the frame with each station’s Clock
Starting Delimiter: Indicates start of frame.
Frame Control(FC): CLFFZZZZ, C  indicates synchronous or asynchronous frame
L  16 or 48- bit Addresses
FF  indicates LLC, MAC control or reserved frame
Destination Address(DA): may be Unicast, multicast or broadcast Address
Source Address(SA) : Specify the station that sent the frame
8 1 1 2 or 6 2 or 6 4 1 1
Destination Source
PRE SD FC Information FCS ED FS
Address Address
Preamble

Information: Contains LLC data unit or information related to a control operation.

Frame Check Sequence(FCS): 32-bit CRC
Ending Delimiter(ED): Indicates end of the frame; Contains a non-data symbol(T).
Frame Status(FS): Contains, E  Error detected
A  Address recognized
F  frame copied

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: FDDI

Token Frame Format
FDDI Token
PRE SD FC ED

Preamble: Sync. Purpose

SD: start of the frame
FC: To indicate the Token; has bit format 10000000 or 11000000
ED: Termination of the Token frame

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Medium Access Control (MAC) Sub layer: FDDI

Ring Latency : The no. of bits that can be simultaneously in transit around
the ring.
Token Rotation Timer (TRT): Measures the time that has elapsed since the
station last received a token.
Token Holding Time (THT): Measures the degree of activity in the ring.

Traffic is low  TRT is low, Traffic is high  TRT is high

If THT > 0, station transmits synchronous traffic, if time not elapsed station
is allowed to transmit asynchronous traffic till timer expires, then token
must be released.
If THT < 0, station transmits only synchronous traffic and token must be
released.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Differences between 802.5 and FDDI
Token Ring FDDI

• Shielded twisted pair • Optical Fiber

• 4, 16 Mbps • 100 Mbps

• No reliability specified
• Reliability specified (dual ring)

• Differential Manchester
• 4B/5B encoding
• Centralized clock • Distributed clocking

• Priority and Reservation bits • Timed Token Rotation Time

• New token after transmit

• New token after receive
26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Topics to be Discussed in this Lecture

Network Layer:
Design Issues
Store & Forward Packet Switching
Connection less & Connection Oriented Service
Shortest Path Routing Algorithms:
Dijkstra’s Algorithm
Bellman- Ford Algorithm

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India 1

 COMMUNICATION NETWORKS
Network Layer:
What is the responsibility of Network Layer ?
The N/W is responsible for getting packets from the Source all the way to the
Destination.

The N/W Layer must take care to choose routes to avoid overloading some of
the communication lines and routers while leaving others idle.

The N/W must know the topology of the communication subnet.

Essential functionalities:
Routing: mechanisms for determining the set of best paths for routing
packets requires the collaboration of network elements

Forwarding: transfer of packets from NE inputs to outputs

Priority & Scheduling: determining order of packet transmission in each NE
Optional: congestion control, segmentation & reassembly, security

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer:

Figure: The environment of the Network Layer Protocols

( Store-and-forward packet switching)

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Implementation of connectionless services:

Figure: Routing within a datagram subnet

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Network Layer: Implementation of connection-oriented services:

Fig: Routing within a virtual-circuit subnet

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Network Layer: Connection less & Connection Oriented Service

Fig: Comparison of Datagram and Virtual-Circuit subnets

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing
The one-to-all shortest path problem is the problem of determining the
shortest path from node ‘S’ to all the other nodes in the network.

The weights on the links are also referred as costs.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing: Dijkstra’s Algorithm
 It finds the shortest path from a given node s to all other nodes in
the network

 Node ‘S’ is called a starting node or an initial node

 Dijkstra’s algorithm starts by assigning some initial values for the

distances from node s and to every other node in the network

 It operates in steps, where at each step the algorithm improves the

distance values.

 At each step, the shortest distance from node s to another node is

determined.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Step 1: Initialization

 Assign the zero distance value to node ‘S’, and label it as Permanent.
[The state of node ‘S’ is (0, p).]

 Assign to every node a distance value of 1 and label them as Temporary.

[The state of every other node is (1, t).]

 Designate the node ‘S’ as the current node.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Step 2: Distance Value Update and Current Node Designation Update
Let i be the index of the current node.

(1) Find the set J of nodes with temporary labels that can be reached from the
current node i by a link (i, j). Update the distance values of these nodes.

For each j ϵ J, the distance value dj of node j is updated as follows

new dj = min{dj, di +cij}
where cij is the cost of link (i, j), as given in the network problem.

(2) Determine a node j that has the smallest distance value dj among all nodes j ϵ J,
find j* such that min dj = dj*
jϵJ
(3) Change the label of node j to permanent and designate this node as the
current node.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing: Dijkstra’s Algorithm
Step 3. Termination Criterion

 If all nodes that can be reached from node ‘S’ have been permanently
labeled, then stop - we are done.

 If we cannot reach any temporary labeled node from the current node,
then all the temporary labels become permanent - we are done.

 Otherwise, go to Step 2.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

We consider a weighted connected simple graph G with vertices a = v0, v1, .
. . , vn = z and
weights w(vi, vj) > 0 where w(vi, vj) = ∞ if {vi, vj} is not an edge.
Dijkstra’s algorithm finds the cost of the “cheapest” path between vertices
a and z.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Explanation of Shortest Path using Dijkstra’s Algorithm:
1. It maintains a list of unvisited vertices.
2. It chooses a vertex (the source) and assigns a maximum possible cost (i.e.
infinity) to every other vertex.
3. The cost of the source remains zero as it actually takes nothing to reach from
the source vertex to itself.
4. In every subsequent step of the algorithm it tries to improve(minimize) the
cost for each vertex. Here the cost can be distance, money or time taken to
reach that vertex from the source vertex. The minimization of cost is a multi-
step process:
i) For each unvisited neighbor (vertex 2, vertex 3, vertex 4) of the
current vertex (vertex 1) calculate the new cost from the vertex
(vertex 1).
ii) For e.g. the new cost of vertex 2 is calculated as the min. of the two
( (existing cost of vertex 2) or (sum of cost of vertex 1 + the cost of
edge from vertex 1 to vertex 2) )
26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Explanation of Shortest Path using Dijkstra’s Algorithm:

5. When all the neighbors of the current node are considered, it marks the
current node as visited and is removed from the unvisited list.

6. Select a vertex from the list of unvisited nodes (which has the smallest cost)
and repeat step 4.

7. At the end there will be no possibilities to improve it further and then the
algorithm ends.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 1: Find the shortest path from node 1 to all other nodes using
Dijkstra’s algorithm.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

STEP 1:

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

STEP 2:

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

STEP 3:

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Another Implementation of Step 2

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Another Step 2

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Another Step 2

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 2: Computing the shortest path from ‘a’ to ‘z’ using Dijkstra’s
Algorithm.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 2: Computing the shortest path from ‘a’ to ‘z’ using Dijkstra’s
Algorithm.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 2: Computing the shortest path from ‘a’ to ‘z’ using Dijkstra’s
Algorithm.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 2: Computing the shortest path from ‘a’ to ‘z’ using Dijkstra’s
Algorithm.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 3: Computing the shortest path from A to D using Dijkstra’s
Algorithm.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Figure: The first five steps used in computing the shortest path from A to D.
The arrows indicate the working node.
26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India
 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing: Dijkstra’s Algorithm
Problem 4: Use Dijkstra’s algorithm to find the cost of the cheapest path
between 1 and 6 in the following weighted graph.

Relaxation: For any given nodes u, v in the graph, if d[u] + c(u, v) < d[v]
then d[v] = d[u] + c(u, v)

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing: Dijkstra’s Algorithm
Problem 4: Use Dijkstra’s algorithm to find the cost of the cheapest path
between 1 and 6 in the following weighted graph.

STEP S D2 D3 D4 D5 D6
0 {1} ∞ ∞ ∞ ∞ ∞

1 {1} 2 4 ∞ ∞ ∞
2 {1,2} 2 3 9 ∞ ∞
3 {1,2,3} 2 3 9 6 ∞
4 {1,2,3,5} 2 3 8 6 11
5 {1,2,3,5,4} 2 3 8 6 9
6 {1,2,3,5,4,6} 2 3 8 6 9

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing: Dijkstra’s Algorithm
Problem 5: Use Dijkstra’s algorithm to find the cost of the cheapest path
between a and z in the following weighted graph.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Solution: The iterations of Dijkstra’s algorithm are described in the
following table.

We conclude that the cheapest path from a to z has a cost of 7.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 6: Use Dijkstra’s algorithm to find the cost
of the shortest path from Node ‘1’ to all the
remaining nodes in the following weighted graph.

Solution:

Step 1:
Step 2:

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Solution:
Step 5:
Step 3:

Step 4: Step 6:

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Solution:
Step 7:

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

2 3 1
1
6
5 2
3
1 4 2
3
2
4 5

Problem 7: Find the shortest route from node ‘1’ to all other nodes using
Dijkstra’s algorithm

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS
Network Layer: Shortest Path Routing: Dijkstra’s Algorithm
Problem 8: Use Dijkstra’s algorithm to find the cost of the cheapest path
between a and z in the following weighted graph.

Problem 9: Use Dijkstra’s algorithm to find the cost of the cheapest path
between s and t in the following weighted graph.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Problem 10: Use Dijkstra’s algorithm to find the cost of the cheapest path
between s and t in the following weighted graph.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Dijkstra’s Algorithm

Analysis of the algorithm:

1. The outer loop runs for |V| times

2. The inner loop runs for |V-1| times for a complete graph as each
vertex has |V-1| edges.

3. Also, for each iteration of the inner loop we do an extract min. and a
reduce Key operation for the vertex.

4. Hence the total running time has an upper bound of O(|V| * |V-1|).
This is the upper bound, O(|V|2)

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Bellman-Ford Algorithm

Dijkstra’s algorithm does not give does not work
with –ve edge cycles.

Links with –ve weights.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Bellman-Ford Algorithm

Drawback of Dijkstra’s Algorithm:
1. The execution time is O(E +V logV) depending on our choice of data
structure to implement the required Priority Queue.
2. It does not give the shortest path if the link weights are –ve.
How is Bellman Ford solving the negative weight cycles problem?
It is theoretically impossible to find out the shortest path if there exists a -ve weight
cycle.

If we try to find the shortest path, then we can go through the -ve cycle once more
and get a smaller path.

We can keep repeating this step and go through the cycle every time and reduce the
total weight of the path to negative infinity.

So, in practical scenarios, this algorithm will either give you a valid shortest path or
will indicate that there is a negative weight cycle.

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India

 COMMUNICATION NETWORKS

Network Layer: Shortest Path Routing: Bellman-Ford Algorithm

Links with –ve weights.

n  No. of vertices

Relaxation: For any given nodes u, v in the graph, if d[u] + c(u, v) < d[v]
then d[v] = d[u] + c(u, v)

26-Sep-18 RAVILLA DILLI, ECE, MIT, Manipal, India