Networking – how to solve the “fileX and fileY” problem

In this post: A detailed, step-by-step guide demonstrating the steps I use to solve a problem similar to one encountered in my CS 372 Intro to Networking class. 

You’re given a link with a maximum transmission rate of 70.5 Mbps. Two computers, X and Y, want to transmit starting at the same time. Computer X sends File X (18 MiB) and computer Y sends File Y (130 KiB), both starting at time t = 0.

  • Statistical multiplexing is used, with details as follows
    • Packet Payload Size = 1000 Bytes
    • Packet Header Size = 24 Bytes (overhead)
  • Ignore Processing and Queueing delays
  • Assume partial packets (packets consisting of less than 1000 Bytes of data) are padded so that they are the same size as full packets.
  • Assume continuous alternating-packet transmission.
  • Computer X gets the transmission medium first.

At what time (t = ?) would File X finish transmitting?

Suppose they want the answer in seconds (hah – not milliseconds like usual!) and they want it rounded to two decimal places.

The “twist” of this problem is that File X and File Y take turns being sent in little chunks of 1000 bytes (plus 24 bytes of overhead).

First a piece of X goes, then a piece of Y, then back to X, etc.

Y is smaller so you run out of Y before you run out of X, but fortunately for us, this problem wants to know when X is done being sent. So really what we’re looking for is how long it takes to send both X and Y.

Here’s a drawing I made to visualize the problem (obviously, X and Y are both way more than just 10 and 5 packets in our real problem).

Diagram depicting X1, Y1, X2, Y2, X3, Y3, X4, Y4, X5, Y5, X6, X7, X8, X9, X10 interwoven with each other. Each block represents a packet.

Step 1: Figure out how many packets have to be sent, total

Our packet size (1000 bytes) and our overhead size (24 Bytes) are given in bytes, so I’m going to turn the two filesizes into Bytes instead of bits for this one. (We can always turn it into bits later if needed.)

File X = 18 MiB // turn to bytes by multiplying by 1024 twice
= 18 * 1024 * 1024 
= 18874368 bytes
File Y = 130 KiB // turn to bytes by multiplying by 1024 once 
= 130 * 1024
= 133120 bytes

Now X and Y are in the same units (bytes) and we can use that to figure out how many packets of 1000 bytes each one would be divided into.

File X = 18874368 Bytes / 1000 = 18874.368 packets

Our result isn’t a whole number. What should we do with the “partial packet”? Well, the problem tells us that any partial packets should be padded up to a full size. In practice, this just means we round up to the next nearest whole number. 18874.368 becomes 18875 packets for File X.

Now do the same for File Y:

File Y = 133120 Bytes / 1000 = 133.12 
Round up to get 134 packets for File Y

(Save these numbers for later, we’ll come back to them.)

Step 2: Calculate the time needed to send one packet plus its overhead

Add the packet size and the overhead size (both must be in the same units; here, that’s bytes but your variation of this problem may differ). Since transmission rate is in bits, let’s also multiply the packet size + overhead size by 8 to put it in bits, and multiply the transmission rate by 10^6 to put it in bits also. That looks like…

L/R, where R's units is what the outcome of this calculation will be 
= (1000 Bytes + 24 Bytes * 8) / (70.5 Mbps x 10^6)
= (8192) / (70.5 x 10^6)
= 0.0001161985816 seconds // same units as R (bits per second) 
= 0.11619858156 msec // multiply by 1000 to get milliseconds

We now know that it takes 0.11619858156 milliseconds to send one packet (and its overhead). Save this number for later.

Step 3: Calculate the time it takes to send all packets

This step is easy: we know how many packets we have between File X and File Y, and we know how long it takes to send one of them, so let’s figure out how long it takes to send all of them.

18875 packets + 134 packets = 19009 packets to send
19009 packets x 0.11619868156 msec = 2208.820738 milliseconds to send all 

Step 4: Convert to seconds and round to 2 decimal places to get the final answer

This variation of the problem wants the solution in seconds, so divide our result from Step 3 by 1000 to get 2.208820738 seconds and round it to two decimal places to get 2.21 seconds, which is when time at which File X will be done sending.

What if it wanted to know when the smaller file was done sending?

Well, let’s look at our diagram again. Here we can see that for every packet of Y sent, a packet of X has already been sent.

For every packet of Y that is sent, one from X precedes it. In other words, to send all 5 packets of Y we must also send 5 packets of X.

We know Y is made up of 134 packets, so that many packets of X will also be sent. That means for our final answer all we have to do is figure out how long it’ll take to send 134*2 packets.

134 * 2 = 268 // all of Y + same amount of X
268 packets x 0.11619868156 msec = 31.14124666 msec to send File Y

Convert that answer to seconds and there we have it: 0.03 seconds have elapsed when File Y (the smaller file) is done sending.

Networking – how to solve the “routers in a sequence” problem

In this post: A detailed, step-by-step guide demonstrating the steps I use to solve a problem similar to one encountered in my CS 372 Intro to Networking class. Yeah, I’m still cranky that this class makes no effort to teach this stuff. They just send you a-Googlin’. Welcome, Googlers…

Suppose there are 3 routers in sequence between Host A and Host B, all of which use store-and-forward routing. What is the total end-to-end delay for a packet originating from Host A with destination Host B, under the following conditions.

  • Each of the link transmission rates are 5.1 Mbps
  • The total distance from Host A to Host B along its path of transmission is 175.1 km
  • The speed of propagation through the transmission medium is is 2.7 x 108 m/s
  • The packet size is 2 KiB

Remember that you must also uplink from Host A to the first router. Suppose this one wants the answer in milliseconds rounded to 1 decimal place.

Step 1: Figure out the transmission delay for one link

The “twist” of this problem is that there are multiple transmission delays to account for. Every “hop” incurs a transmission delay.

We can use the L/R formula with the known packet size (2 KiB and known transmission rate (5.1 Mbps) to calculate the transmission delay for one node to another. Node here means host or router. Be sure to convert both into bits.

(2 KiB * 8192) / (5.1 Mbps * 10^6) 
= 16,384/5,100,000 = 0.00321254... seconds

Remember that the units R is in determines the outcome, so this result is in seconds. Multiply it by 1000 to turn it into milliseconds and save this result for later.

0.00321254 x 1000 = 3.21254901... milliseconds

Step 2: Figure out the entire path’s transmission delay

Recall that our three routers and two hosts basically look like this:

[A]–[1]–[2]–[3]–[B]

We know the transmission delay (the time it takes for a bit to be placed on the transmission medium) at one host or router, and we know how many routers there are total, so we can figure out how many “transmission delays” our bits will go through by multiplying the total number of routers plus one (to account for being placed on the transmission medium by A) by the transmission delay we calculated in step 1.

(R + 1) * 3.21254901  // R is the number of routers
= (3 + 1) * 3.21254901 // add 1 to account for initial link
= 4 * 3.21254901 
= 12.85019604 milliseconds

This number represents the total amount of transmission delay experienced by bits traversing this multi-router path.

Step 3: Figure out the propagation delay

Recall that our distance is 175.1 km and our speed of propagation is 2.7 x 108 m/s and the propagation delay formula is Tprop = d/s. Note that km has to be turned into meters and the result will be in seconds.

= (175.1 * 1000) / (2.7 x 108 m/s) = 0.0006485185... seconds 
0.0006485185... seconds x 1000 = 0.64851 milliseconds

Step 4: Add it all up

 3.21254901 + 12.85019604 + 0.64851 = 16.71125505 milliseconds

And that’s it, you’re done! Hope you found this helpful!

Networking – how to solve the “VOIP problem”

In this post: A detailed, step-by-step guide demonstrating the steps I use to solve a problem similar to one encountered in my CS 372 Intro to Networking class.

The “VOIP problem”

You’re given a diagram (you won’t need it) and some values in the form of…

  • Host A converts analog to digital at a = 40 Kbps
  • Link transmission rate R = 4.2 Mbps
  • Host A groups data into packets of length L = 51 bytes
  • Distance to travel d = 900 km
  • Propagation speed s = 2.5 x 108 m/s
  • Host A sends each packet to Host B as soon as it gathers a whole packet.
  • Host B converts back from digital to analog as soon as it receives a whole packet.

The question asks, How much time elapses from when the first bit starts to be created until the conversion back to analog begins?

Let’s say they want the answer in milliseconds rounded to two decimal places (note: this varies – sometimes the answer has to be in seconds, sometimes they want it rounded to one decimal place – double check your instance of the problem!)

Step 1: Figure out how long it takes to make a single packet

“When the first bit starts to be created” means “when this imaginary machine starts building the very first packet”.

We know how big a packet is: 50 bytes.

We know the rate at which it produces packets: 40 Kbps.

This is the classic L/R (length over rate) you’ve hopefully seen if you’re keeping up with the course materials. We can use L/R here, but we have to turn 51 bytes into bits (multiply it by 8) and we have to turn 40 Kbps into bps (multiply it by 1,000).

(51 * 8) / (40 * 1,000) = (408 / 40,000) = 0.0102 seconds

We get 0.0102 seconds because the units that R is in determines the outcome. R is in bits per second (bps), so that’s how we know the units we’re looking at here is seconds.

We need this in milliseconds, because we’re going to put everything in milliseconds so that we’re working in the units the question expects. Multiply the seconds answer by 1000 to get milliseconds, like so:

0.0102 x 1000 = 10.2 milliseconds

That’s the time it takes to make one single, complete, ready-to-transmit packet. Save this value for later, we will come back to it in step 4.

Step 2: Figure out the transmission delay

Recall from the course materials that transmission delay is the time it takes to place every bit onto the transmission medium. Transmission delay is not the time it takes to actually send it!

If you like car analogies, consider transmission delay the time it takes to get your car onto the highway. Your car is being placed on the transmission medium, and the time it takes to do that is the transmission delay. (Again, this is not the time it takes to travel the length of the highway! It’s the time it takes to get your car onto the highway.)

We will use the L/R formula again for this step. This time L is the length of the packet (51 bytes) and R is the transmission rate (4.2Mbps). We need both of them in bits, so multiply 51 (bytes) by 8 to get bits, and multiply 3.8 by 1,000,000 to get bps.

(51 * 8) / (3.8 x 1,000,000) = (408 / 3,800,000) = 0.00010737 seconds

Again, the units of R determine what units the result is in, which in this case is seconds (because we had bits per second for our R).

To turn it into milliseconds, multiply by 1000:

0.00010737 x 1000 = 0.10736842 milliseconds

So, what do we have so far? We have the time it takes to make one packet and the time it takes to transmit that packet, both in milliseconds. There is one missing piece: propagation delay.

Step 3: Figure out the propagation delay

Propagation delay is the time it takes a bit to travel the given distance (900 km) at the given speed (2.5 x 108 m/s). The formula for propagation delay is d/s (distance over speed).

To go back to our car analogy, the propagation delay is the time it takes the car to zoom down the highway to its destination.

Like L/R, the d/s result will be in the same units as the bottom number (so, seconds). However, before we proceed, note that the distance we were given is in kilometers and the speed is given in meters per second. We need to convert kilometers to meters when we do our calculation, so multiply that 900 by 1,000.

(900 km * 1,000 / 2.5 x 108) = 0.0036 seconds

Remember to convert that answer to milliseconds:

0.0036 x 1000 = 3.6 milliseconds

Step 4: Add the previous three answers together

Time to generate packet + time to place it on the transmission medium + time for it to propagate = our answer

10.2 msec + 0.10736842 msec + 3.6 msec = 13.90736842 milliseconds

Step 5: Round to the requested number of decimal places

Since this problem wants the answer rounded to two decimal places, 13.90736842 becomes 13.91

I hope this breakdown of the “VOIP problem” helps someone else!

I have to admit I’m a bit salty this class had us sit through all those lectures, read all those book chapters, and do all those worksheets and couldn’t once be bothered to expose us to even a watered-down or partial version of it before throwing it as us on a graded, timed quiz.

Fortunately, once you’ve mastered solving this problem, a lot of the other “math problems” that CS 372 throws at you in week 1 and week 2 will feel like variations on it.