6

I’m working through questions from computer networking top down approach and was hoping to get some clarity on the end-to-end delay calculation. At this stage we are not considering processing, transmission or propagation delay.

N = link
L = packet length 
R = transmission rate

The end-to-end Delay is N*L/R (N links in series, using store-and-forward between the links).

The author asks to generalize the above formula for sending P packets over N links.

The solution I derived is (N*L/R)*P.

Is this a reasonable solution?

PS. This is not home working.

Ron Maupin
  • 98,218
  • 26
  • 115
  • 191
dcrearer
  • 489
  • 2
  • 4
  • 15
  • 2
    In your question you say you aren't considering transmission delay, but that is exactly what you are considering with (L/R) –  Jul 22 '18 at 07:29
  • I think the formula (P + N-1)*(L/R) might be missing the delay for hop from the last link to the destination. So the total end to end delay should be (P+N)*(L/R), which conforms to the example of 3 packets and a delay of 4*(L/R) given in the book by Kurose and Ross. – febin Jul 04 '20 at 10:49
  • 1
    Replying to febin's comment: In Kurose, Ross, N refers to the number of links. **This includes the link to the destination.** Using the example in the book, when there are 1 source, 1 router and 1 destination, there are a total of 2 links. (One that connects the source and the router and one that connects the router to the destination.) This means N = 2. When there are 3 packets, P = 3. Therefore (P + N-1) or (3 + 2 - 1) is correct. – Yan Bo Pei Jan 14 '21 at 03:55

2 Answers2

7

So, this assumes that all packets are the same length and all links are the same bandwidth.

I think a mistake you are making is that your formula looks at the end-to-end delay for a single packet, then multiplies it by the number of packets. In this case, the first packet would be sent end-to-end, then the second packet would be send end-to-end etc.

In reality, many packets can be in transit within the network at any one time. If the only delays we are considering are serialisation, then the following would happen:

  • The first packet is serialised onto the first link
  • As soon as the first packet has been serialised onto the first link, as we are only considering serialisation delay, it can begin serialising on the second link
    • At this same time, the second packet can begin serialising on the first link, it can't begin any sooner as the first link was clocking the first packet up until this time.
  • In this simple model, the first and second packets finish serialising on second and first links (respectively) at the same time
    • The first packet can now begin serialising on the third link
    • The second packet can now begin serialising on the second link
    • The third packet can now begin serialising on the first link
  • And it goes on until the last packet is serialised onto the first link
  • Each packet must then serialise on each remaining link until it reaches the last link.

So really, you need to look at the time taken to send all packets across the first link, one-by-one, then look at the time taken for the last packet to traverse the remaining links.

  • So if you consider (L/R) as the time taken to transport one packet across one link.

  • Then consider there are P of these delays to transport all packets over the first link, one-by-one

  • And there are (N-1) of these delays to transport the last packet over the remaining links

Then the formula for this would be:

(P + (N-1)) * (L/R)

Note: this formula is very simplistic and assumes there are no propagation delays, node processing delays or queuing delays etc.

  • Can you explain why you summing the number of packet P + N -1. Where N is the number of links in the transmission path. (P + (N-1)) – dcrearer Jul 23 '18 at 11:36
  • As in the answer, (L/R) is time to clock one packet onto one link, but you need to calculate the time taken to clock each packet on the first link, which is P * (L/R), at this stage the last packet has been clocked onto the first link, so you need to consider that it needs to now clock on the remaining links, which is (N-1) * (L/R), you don't need to consider the rest of the packets at this stage as they will be delivered before the last packet, if you add the two together you get (P+N-1) * (L/R) –  Jul 23 '18 at 12:23
1

At t =N*L/R the 1st packet reaches the destination.

At t =N*L/R +L/R the 2nd packet reaches the destination.

At t = N*L/R +L/R+L/R the 3rd packet reaches the destination.

Similarly,

At t = N*L/R + (P-1)*L/R the Pth packet reaches the destination. So total delay = N*L/R + (P-1)*L/R = (N+P-1)*L/R

Ganesh
  • 11
  • 1