Transcript Binary exponential backoff

Binary Exponential Backoff
Binary exponential backoff refers to a collision
resolution mechanism used in random access MAC
protocols. This algorithm is used in Ethernet (IEEE
802.3) wired LANs. In Ethernet networks, this
algorithm is commonly used to schedule
retransmissions after collisions.
Course Name: Computer Networks
Level : UG
Author
Phani Swathi Chitta
Mentor
Prof. Saravanan Vijayakumaran
Learning Objectives
After interacting with this Learning Object, the learner will be able to:
• Explain how the binary exponential backoff algorithm works
Definitions of the components/Keywords:
1
2
3
4
5
• Binary exponential backoff refers to a collision resolution mechanism used
in random access MAC protocols. This algorithm is used in Ethernet (IEEE
802.3) wired LANs.
• In Ethernet networks, this algorithm is commonly used to schedule
retransmissions after collisions.
• After a collision, time is divided into discrete slots whose length is equal to
2τ, where τ is the maximum propagation delay in the network.
•The reason for this choice is that 2 τ is the minimum amount of time a source
needs to listen to the channel to always detect a collision.
• The stations involved in the collision randomly pick an integer from the set
{0,1}. This set is called the contention window. If the sources collide again
because they picked the same integer, the contention window size is doubled
and it becomes {0,1,2,3}. Now the sources involved in the second collision
randomly pick an integer from the set {0,1,2,3} and wait that number of slot
times before trying again. Before they try to transmit, they listen to the
channel and transmit only if the channel is idle. This causes the source which
picked the smallest integer in the contention window to succeed in
transmitting its frame.
Definitions of the components/Keywords:
1
2
• In general, after collisions, a random number between 0 and
is chosen.
• After a station detects collision, it aborts its transmission in the slot
duration itself in which it started transmitting.
•In Ethernet, the doubling of the contention window stops after 10
collisions and the contention window remains {0,1,...,1023}.
3
4
5
• After 16 collisions , the process is aborted and the source stops
trying.
1
2
3
Master Layout 1
Part 1 – Collision with two sources
Part 2 – Collision with three sources
Place a drop down box to
choose number of
sources 2 and 3
Assuming two sources are involved in collision
Source
S1
Time
4
Source
S2
5
Time
1
Step 1:
Source
S1
2
3
Time
C W: {0, 1}
Source
S2
Time
CW: {0, 1}
4
Instruction for the animator
• The figure in master layout should appear
first
• The first statement in DT should appear
5
• Next the numbers 0 and 1 in braces should
appear along with the second sentence in
DT
Text to be displayed in the working area (DT)
• Assume first collision took place,
• The initial contention window for two sources is {0, 1}
1
Step 2:
Source
S1
0
2
3
1
2
3
4
5
6
Source
S2
0
Instruction for the animator
• With the first sentence in DT, the time line
should be divided.
• Next the two sentences in DT should
appear
5
8
Time
CW :{0,1}
1
2
3
4
5
6
7
8
Time
CW: {0,1}
4
7
Text to be displayed in the working area (DT)
• After a collision, time is divided into discrete slots.
• Frame length is much larger than the slot size.
• A single slot is sufficient to detect a collision.
1
Step 3:
Source
S1
0
2
3
3
4
5
6
7
8
Time
Source
S2
0
Instruction for the animator
• The first sentence appears first
• With the second sentence in DT, the blue
lines should blink and the red lines at S1
should appear
5
2
CW :{0,1}
CW :{0,1}
4
1
• The third and fourth lines should appear
and then the red lines at S2 should appear
1
2
3
4
5
6
7
8
Time
Text to be displayed in the working area (DT)
• Ideal case that S1 and S2 picks different slots randomly for the
transmission of the frame.
• Suppose S1 picks 0 and S2 picks 1, S1 starts sending the frame in slot 0
S2 should start sending the frame in slot 1 but it hears the channel is busy
and waits till the channel is free.
1
Step 4:
Source
S1
0
2
0
1
2
3
4
5
6
7
Time
CW: {0,1,2,3}
Collision occurs
3
Source
S2
0
CW: {0,1,2,3}
4
Instruction for the animator
• The first sentence in DT should appear first
• Now the numbers at the time line should
move right and the first zero should disable
• Then the blue lines should blink
5
• After that with the second line in DT, the
numbers in the braces should appear
0
1
2
3
4
5
6
7
Time
Text to be displayed in the working area (DT)
• Suppose S1 and S2 picks the same slot number 0 to transmit the frame,
they collide again.
• After second collision, the contention window changes to {0,1,2,3}
1
Step 5:
Source
S1
0
2
0
0
1
2
3
4
5
6
Time
CW: {0,1,2,3,4,5,6,7}
Collision occurs
3
Source
S2
0
0
CW: {0,1,2,3,4,5,6,7}
4
Instruction for the animator
• The first sentence in DT should appear first
• Now the numbers at the time line should
move right and the first two zeros should
disable
• Then the blue lines should blink
5
• After that with the second line in DT, the
numbers in the braces should appear
• Then the third line should appear
0
1
2
3
4
5
6
Time
Text to be displayed in the working area (DT)
• Suppose S1 and S2 picks the same slot number 2 to transmit the frame,
they collide again.
• After third collision, the contention window changes to {0,1,2,3,4,5,6,7}
• After 16 such attempts of transmission, the process is aborted.
Master Layout 2
1
2
Part 1 – Collision with two sources
Part 2 – Collision with three sources
Assuming three sources are involved in collision
Source
S1
Time
3
Source
S2
Time
4
Source
S3
Time
5
1
Step 1:
Source
S1
CW: {0,1}
Time
2
Source
S2
3
Time
CW: {0,1}
Source
S3
Time
CW: {0,1}
4
Instruction for the animator
• The figure in master layout should appear
first
• The first statement in DT should appear
5
• Next the numbers 0 and 1 in braces should
appear along with the second sentence in
DT
Text to be displayed in the working area (DT)
• Assume first collision took place,
• The initial contention window for three sources is {0, 1}
1
Step 2:
Source
S1
0
1
2
3
4
5
6
7
8
Time
0
1
2
3
4
5
6
7
8
Time
0
1
2
3
4
5
6
7
8
Time
CW: {0,1}
2
Source
S2
3
CW: {0,1}
Source
S3
CW: {0,1}
4
Instruction for the animator
• With the first sentence in DT, the time line
should be divided.
• Next the two sentences in DT should
appear
5
Text to be displayed in the working area (DT)
• After a collision, time is divided into discrete slots.
• Frame length is much larger than the slot size.
• A single slot is sufficient to detect a collision.
1
Step 3:
Source
S1
0
1
2
3
4
5
6
7
8
Time
0
1
2
3
4
5
6
7
8
Time
0
1
2
3
4
5
6
7
8
Time
CW: {0,1,2,3}
2
Source
S2
3
CW: {0,1,2,3}
Source
S3
CW: {0,1}
4
Instruction for the animator
• The first sentence in DT should appear first
• Then the blue lines should blink
• After that with the second line in DT, the
numbers in the braces should appear
5
• After that the third sentence should appear
Text to be displayed in the working area (DT)
• Suppose S1 and S2 picks the same slot number 0 to transmit the frame
and S3 picks 1, then S1 and S2 collide again.
• After second collision, the contention window changes to {0,1,2,3}
• The contention window of S3 remains same.
1
Step 4:
Source
S1
0
0
1
2
3
4
5
6
Time
7
1
2
3
4
5
6
7
CW: {0,1,2,3,4,5,6,7}
2
Source
S2
0
3
Time
CW: {0,1,2,3}
Source
S3
0
CW: {0,1,2,3}
4
Instruction for the animator
• The first sentence in DT should appear first
5
0
1
2
3
4
5
6
7
8
Time
Text to be displayed in the working area (DT)
• Then the blue lines should blink
• Suppose S1 picks slot number 0 to transmit the frame after second
collision and S3 picks 1 after first collision and S2 picks 3 after second
collision, then S1 and S3 collide again.
• After that with the second line in DT, the
numbers in the braces should appear
• After third collision, the contention window of S1 changes to
{0,1,2,3,4,5,6,7}
• After that with the third line in DT, the
numbers in the braces should appear
• After second collision, the contention window of S3 changes to {0,1,2,3}
Electrical Engineering
Slide
1
Slide
3
Introduction
Definitions
Slide
17
Analogy
Slide
19
Slide
18
Want to know more…
Test your understanding
Lets Sum up (summary)
(Further Reading)
(questionnaire)
Interactivity:
{0, 1}
Source
S1
Try it yourself
Time
• Place a dropdown box for
each source
• Place a dropdown box to
select the slot number
{0, 1}
Source
S2
• The range of the slot number
is 0 to 7
Time
{0, 1}
• Place a dropdown box to
select the contention window
•The range of the contention
window is {0,1}, {0,1,2,3},
{0,1,2,3,4,5,6,7}
Source
S3
Time
{0, 1}
Source
S4
Time
16
Credits
Questionnaire
1
1. After how many collisions will the process be aborted?
Answers: a)
2
4
5
c) 20
d)
2. If a 5th collision occurs, the contention window is
Answers: a) 35
3
b) 16
b) 0,1
c) 0 to 35
d)0 to 5
3. If a 12th collision occurs, the contention window is
Answers: a) 4095
d)0 to 1023
The answers are given in red
b) 0 to 4095
c) 1023
Links for further reading
Reference websites:
http://en.wikipedia.org/wiki/Exponential_backoff
Books:
Computer Networks – Andrew S Tanenbaum,
fourth edition, Prentice Hall
Research papers:
Summary
•
Binary exponential backoff refers to a collision resolution mechanism used
in random access MAC protocols. This algorithm is used in Ethernet (IEEE
802.3) wired LANs.
•
In Ethernet networks, this algorithm is commonly used to schedule
retransmissions after collisions.
•
After a collision, time is divided into discrete slots whose length is equal to
2τ, where τ is the time taken by the frame to reach other end.
•
In general, after
is chosen
collisions, a random number between 0 and