Time Out Timer | Karn Algorithm | Jacobson Algorithm

Computer Networks
Spread the love

TCP Timers-

 

Before you go through this article, make sure that you have gone through the previous article on TCP Timers.

 

We have discussed-

  • TCP Timers are used to avoid excessive delays during communication.
  • Several timers used in a TCP implementation are-

 

 

  1. Time Out Timer
  2. Time Wait Timer
  3. Keep Alive Timer
  4. Persistent Timer

 

In this article, we will discuss about Time Out Timer and its Computation.

 

Time Out Timer-

 

TCP uses a time out timer for retransmission of lost segments.

 

  • Sender starts a time out timer after transmitting a TCP segment to the receiver.
  • If sender receives an ACK before the timer goes off, it stops the timer.
  • If sender does not receives any ACK and the timer goes off, then TCP Retransmission occurs.
  • Sender retransmits the same segment and resets the timer.
  • The value of time out timer is dynamic and changes with the amount of traffic in the network.

 

Network Traffic And Time Out Timer-

 

Consider-

  • Receiver has sent the ACK to the sender.
  • The ACK is on its way through the network.

 

Now, following two cases are possible-

 

Case-01: High traffic-

 

If there is high traffic in the network-

  • The time taken by the ACK to reach the sender will be more.
  • So, as per the high traffic, the value of time out timer should be kept large.

 

If the value is kept small, then-

  • Timer will time out soon.
  • It causes the sender to assume that the segment is lost before reaching the receiver.
  • However, in actual the ACK is delayed due to high traffic.
  • Sender keeps retransmitting the same segment.
  • This overburdens the network and might lead to congestion.

 

Case-02: Low traffic-

 

If there is low traffic in the network-

  • The time taken by the ACK to reach the sender will be less.
  • So, as per the low traffic, the value of time out timer should be kept small.

 

If the value is kept large,

  • Timer will not time out soon.
  • Sender keeps waiting for the ACK even when it is actually lost.
  • This causes excessive delay.

 

Conclusion-

 

The value of time out timer should be such that-

  • It decreases when there is low traffic traffic in the network.
  • It increases when there is high traffic in the network.

 

Algorithms For Computing Time Out Timer Value-

 

The algorithms used for computing the value of time out timer dynamically are-

  1. Basic Algorithm
  2. Jacobson’s Algorithm
  3. Karn’s modification

 

Rules

 

All the above algorithms work on the following rules-

 

Rule-01:

 

The value of time out timer for the next segment is increased when-

  • Actual round trip time for the previous segment is found to be increased indicating there is high traffic in the network.

 

Rule-02:

 

The value of time out timer for the next segment is decreased when-

  • Actual round trip time for the previous segment is found to be decreased indicating there is low traffic in the network.

 

Now, let us see all the algorithms one by one.

 

Basic Algorithm-

 

The steps followed under Basic Algorithm are-

 

Step-01: Sending 1st Segment-

 

While sending the 1st segment,

  • Sender assumes any random value of initial RTT say IRTT1.
  • So after sending the 1st segment, sender expects its ACK to arrive in time IRTT1.
  • Sender sets time out timer value (TOT) for the 1st segment to be-

 

TOT1 = 2 X IRTT1

 

  • Suppose ACK for the 1st segment arrives in time ARTT1.
  • Here, ARTT1 = Actual Round Trip Time for the 1st segment.

 

Step-02: Sending 2nd Segment-

 

While sending the 2nd segment,

  • Sender computes the value of initial RTT for the 2nd segment using the relation-

 

IRTTn+1 = α IRTTn + (1 – α)ARTTn

 

Here, α is called smoothing factor where 0 <= α <= 1

(Its value will be given in questions)

 

Now,

  • Substituting n=1, sender gets IRTT2 = α IRTT1 + (1 – α)ARTT1.
  • So after sending the 2nd segment, sender expects its ACK to arrive in time IRTT2.
  • Sender sets time out timer value (TOT) for the 2nd segment to be-

 

TOT2 = 2 X IRTT2

 

  • Suppose ACK for the 2nd segment arrives in time ARTT2.
  • Here, ARTT2 = Actual Round Trip Time for the 2nd segment.

 

In the similar manner, algorithm computes the time out timer value for all the further segments.

 

Advantages-

 

The advantages of Basic Algorithm are-

  • Time out timer value is flexible to dynamic round trip time.
  • It takes into consideration all the previously sent segments to derive the initial RTT for the current segment.

 

Disadvantage-

 

The disadvantage of Basic Algorithm is-

  • It always considers Time out timer value = 2 x Initial round trip time.
  • There is no logic behind using the number 2.

 

2. Jacobson’s Algorithm-

 

  • Jacobson’s Algorithm is a modified version of the basic algorithm.
  • It gives better performance than Basic Algorithm.

 

The steps involved in Jacobson’s Algorithm are-

 

Step-01: Sending 1st Segment-

 

While sending the 1st segment,

  • Sender assumes any random value of initial RTT say IRTT1.
  • So after sending the 1st segment, sender expects its ACK to arrive in time IRTT1.
  • Sender assumes any random value of initial deviation say ID1.
  • So after sending the 1st segment, sender expects there will be a deviation of ID1 time from IRTT1.
  • Sender sets time out timer value (TOT) for the 1st segment to be-

 

TOT1 = 4 x ID1 + IRTT1

 

  • Suppose ACK for the 1st segment arrives in time ARTT1.
  • Here, ARTT1 = Actual Round Trip Time for the 1st segment.
  • Then, Actual deviation from IRTT1 is given by-

AD1 = | IRTT1 – ARTT1 |

 

Step-02: Sending 2nd Segment-

 

While sending the 2nd segment,

  • Sender computes the value of initial RTT for the 2nd segment using the relation-

 

IRTTn+1 = α IRTTn + (1 – α)ARTTn

 

Here, α is called smoothing factor where 0 <= α <= 1

(Its value will be given in questions)

  • Sender computes the value of initial deviation for the 2nd segment using the relation-

 

IDn+1 = α IDn + (1 – α)ADn

 

Here, α is called smoothing factor where 0 <= α <= 1

(Its value will be given in questions)

  • Substituting n=1, sender gets-

IRTT2 = α IRTT1 + (1 – α)ARTT1

ID2 = α ID1 + (1 – α)AD1

 

  • So after sending the 2nd segment, sender expects its ACK to arrive in time IRTT2 with deviation of ID2 time.
  • Sender sets time out timer value (TOT) for the 2nd segment to be-

 

TOT2 = 4 x ID2 + IRTT2

 

  • Suppose ACK for the 2nd segment arrives in time ARTT2.
  • Here, ARTT2 = Actual Round Trip Time for the 2nd segment.
  • Then, Actual deviation from IRTT2 is given by-

AD2 = | IRTT2 – ARTT2 |

 

In the similar manner, algorithm computes the time out timer value for all the further segments.

 

Problems with Basic Algorithm and Jacobson’s Algorithm-

 

To calculate initial round trip time, both the algorithms depend on the actual round trip time of the previous segment through the relation-

 

IRTTn+1 = α IRTTn + (1 – α)ARTTn

 

Now,

  • Consider ACK of some segment arrives to the sender after its initial time out timer goes off.
  • Then, sender will have to re transmit the segment.
  • Now for the segment being re transmitted, what should be the initial time out timer value is the concern.
  • This is because the ACK is delayed and will arrive after time out.
  • So, ARTT is not available.

 

This problem is resolved by Karn’s modification.

 

3. Karn’s Modification-

 

Karn’s modification states-

  • Whenever a segment has to be re transmitted, do not apply either of Basic or Jacobson’s algorithm since actual RTT is not available.
  • Instead, double the time out timer (TOT) whenever the timer times out and make a retransmission.

 

NOTE

In the above discussion,

Initial time out timer value may also be called as the estimated time out timer value for the segment being sent.

 

PRACTICE PROBLEMS BASED ON CALCULATING TIME OUT TIMER VALUE-

 

Problem-01:

 

In TCP, the initial RTT is 10 msec. The acknowledgements for the first three segments are received in time 15 msec, 20 msec and 10 msec.

Find the time out timer value for the first four segments using basic algorithm. Use α = 0.5.

 

Solution-

 

For 1st Segment-

 

Initial round trip time (IRTT1) = 10 msec

 

So, Time out timer value (TOT1)

= 2 x IRTT1

= 2 x 10

= 20 msec

 

Now,

  • ACK for the 1st segment is received after 15 msec.
  • So, Actual round trip time (ARTT1) = 15 msec.

 

For 2nd Segment-

 

Initial round trip time (IRTT2)

= α x IRTT1 + (1-α) x ARTT1

= 0.5 x 10 + (1-0.5) x 15

= 5 + 7.5

= 12.5 msec

 

So, Time out timer value (TOT2)

= 2 x IRTT2

= 2 x 12.5

= 25 msec

 

Now,

  • ACK for the 2nd segment is received after 20 msec.
  • So, Actual round trip time (ARTT2) = 20 msec.

 

For 3rd Segment-

 

Initial round trip time (IRTT3)

= α x IRTT2 + (1-α) x ARTT2

= 0.5 x 12.5 + (1-0.5) x 20

= 6.25 + 10

= 16.25 msec

 

So, Time out timer value (TOT3)

= 2 x IRTT3

= 2 x 16.25

= 32.5 msec

 

Now,

  • ACK for the 3rd segment is received after 10 msec.
  • So, Actual round trip time (ARTT3) = 10 msec.

 

For 4th Segment-

 

Initial round trip time (IRTT4)

= α x IRTT3 + (1-α) x ARTT3

= 0.5 x 16.25 + (1-0.5) x 10

= 8.125 + 5

= 13.125 msec

 

So, Time out timer value (TOT4)

= 2 x IRTT4

= 2 x 13.125

= 26.25 msec

 

Problem-02:

 

In TCP, the initial RTT is 10 msec and the initial deviation is 5 msec. The acknowledgements for the first three segments are received in time 20 msec, 30 msec and 10 msec.

Find the time out timer value for the first four segments using Jacobson’s Algorithm. Use α = 0.5.

 

Solution-

 

For 1st Segment-

 

  • Initial round trip time (IRTT1) = 10 msec
  • Initial deviation (ID1) = 5 msec

 

So,

Time out timer value (TOT1)

= 4 x ID1 + IRTT1

= 4 x 5 + 10

= 30 msec

 

Now, ACK for the 1st segment is received after 20 msec. So,

  • Actual round trip time (ARTT1) = 20 msec
  • Actual deviation (AD1) = | IRTT1 – ARTT1 | = | 10 – 20 | = 10 msec

 

For 2nd Segment-

 

Initial round trip time (IRTT2)

= α x IRTT1 + (1-α) x ARTT1

= 0.5 x 10 + (1-0.5) x 20

= 5 + 10

= 15 msec

 

Initial deviation (ID2)

= α x ID1 + (1-α) x AD1

= 0.5 x 5 + (1-0.5) x 10

= 2.5 + 5

= 7.5 msec

 

So, Time out timer value (TOT2)

= 4 x ID2 + IRTT2

= 4 x 7.5 + 15

= 45 msec

 

Now, ACK for the 2nd segment is received after 30 msec. So,

  • Actual round trip time (ARTT2) = 30 msec
  • Actual deviation (AD2) = | IRTT2 – ARTT2 | = | 15 – 30 | = 15 msec

 

For 3rd Segment-

 

Initial round trip time (IRTT3)

= α x IRTT2 + (1-α) x ARTT2

= 0.5 x 15 + (1-0.5) x 30

= 7.5 + 15

= 22.5 msec

 

Initial deviation (ID3)

= α x ID2 + (1-α) x AD2

= 0.5 x 7.5 + (1-0.5) x 15

= 3.75 + 7.5

= 11.25 msec

 

So, Time out timer value (TOT3)

= 4 x ID3 + IRTT3

= 4 x 11.25 + 22.5

= 67.5 msec

 

Now, ACK for the 3rd segment is received after 10 msec. So,

  • Actual round trip time (ARTT3) = 10 msec
  • Actual deviation (AD3) = | IRTT3 – ARTT3 | = | 22.5 – 10 | = 12.5 msec

 

For 4th Segment-

 

Initial round trip time (IRTT4)

= α x IRTT3 + (1-α) x ARTT3

= 0.5 x 22.5 + (1-0.5) x 10

= 11.25 + 5

= 16.25 msec

 

Initial deviation (ID3)

= α x ID3 + (1-α) x AD3

= 0.5 x 11.25 + (1-0.5) x 12.5

= 5.625 + 6.25

= 11.875 msec

 

So, Time out timer value (TOT4)

= 4 x ID4 + IRTT4

= 4 x 11.875 + 16.25

= 63.75 msec

 

Next Article- Silly Window Syndrome

 

Get more notes and other study material of Computer Networks.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Time Out Timer | Karn Algorithm | Jacobson Algorithm
Article Name
Time Out Timer | Karn Algorithm | Jacobson Algorithm
Description
TCP timers are used to avoid excessive delays. Time out timer is used to retransmit lost segments. Karn's Algorithm, Jacobson Algorithm & Basic Algorithm are used for computing time out timer value dynamically.
Author
Publisher Name
Gate Vidyalay
Publisher Logo

Spread the love