Chapter 1 Problems, Wireshark Lab, Interview · Computer Networking Interactive

Twenty-eight review questions and thirty-four problems from chapter 1, every one of them checkable, and every one showing its full working once you have tried.

How to use this page

Review questions check that you can state the ideas. Most reveal a written answer.
Problems make you use the formulas. Numeric answers are checked to within 1 %, so round sensibly.
Every exercise has a worked solution, and it appears only after you answer or explicitly ask for it. A solution read too early is a solution not learned.
Where a problem asks you to visit the book’s companion web site, the answer here points you at the equivalent widget on this site instead.

Why this matters

The delay and throughput formulas from §1.4 are used in homework throughout the rest of the book. This is where they stop being something you read and start being something you can do.

Several problems also answer questions the chapter deliberately left open:

P2 finishes the equation the book poses and abandons;
P13a computes the average queuing delay §1.4.2 leaves as an exercise;
P28c produces the number that motivates the whole of §3.4.2.

Before you start

Three things trip people up, every time.

Watch for these

Bytes are not bits. A 1,500-byte packet is 12,000 bits. Half the wrong answers in this chapter come from a missing factor of 8.
Check which formula the numbers belong to. Several problems hand you a packet length and a distance and a rate, then ask for propagation delay — which uses only two of them. Giving you numbers you must not use is a deliberate test.
Store-and-forward means each link costs its own $L/R$ . Unless a problem says the switch forwards bits immediately, as P11 does.

Scratch calculator — the formulas these problems need

What each symbol means

L — packet length (bits)
R — link rate (bits per second)
N — links on the path (a count)
P — packets sent back to back (a count)

Read aloud: one packet pays one transmission time per link; each extra packet adds just one more.

Packet length LbitsLink rate RMbpsNumber of links NlinksNumber of packets Ppackets

One hop4.80 ms

d_trans = L / R
        = 12,000 bits / 2.50 Mbps
        = 4.800e-3 s
        = 4.80 ms

One packet over N links14.4 ms

d_end-to-end = N × L / R
             = 3 × 12,000 bits / 2.50 Mbps
             = 3 × 4.80 ms   (one hop)
             = 14.4 ms

P packets over N links14.4 ms

d = (N + P − 1) × L / R
  = (3 + 1 − 1) × 4.80 ms
  = 3 × 4.80 ms
  = 14.4 ms

Change any number above and the arithmetic re-runs, carrying the units through.

Here so you do not have to leave the page to check arithmetic. Remember that a byte is 8 bits — forgetting that is the commonest mistake in this chapter.

Review questions

Review questions R1–R28

These check that you can state the chapter's ideas. Answer first, then reveal. Questions that ask you to research your own city or visit an outside web site are answered here with what the book expects you to find.

R1What is the difference between a host and an end system? List several different types of end systems. Is a web server an end system?
R2The word protocol is often used to describe diplomatic relations. How would you describe diplomatic protocol, and how does it match the networking definition?
R3Why are standards important for protocols?
R4List four access technologies and classify each as home access, enterprise access, or wide-area wireless access.
R5Is the HFC transmission rate dedicated or shared among users? Are collisions possible in a downstream HFC channel?
a.Dedicated or shared?
b.Are collisions possible downstream?
R6List the residential access technologies available in your own city, with their advertised downstream rate, upstream rate and monthly price.
R7What is the transmission rate of Ethernet LANs?
R8What physical media can Ethernet run over?
R9HFC, DSL and FTTH are all used for residential access. For each, give a range of transmission rates and say whether the rate is shared or dedicated.
R10Describe the most popular wireless Internet access technologies today. Compare and contrast them.
R11One packet switch sits between a sending host and a receiving host. The rates are R1 and R2. With store-and-forward, what is the total end-to-end delay for a packet of length L? Ignore queuing, propagation and processing.
R12What advantage does a circuit-switched network have over a packet-switched network? What advantage does TDM have over FDM?
R13Users share a 2 Mbps link. Each user transmits continuously at 1 Mbps when active, and is active 20 % of the time.
a.With circuit switching, how many users can be supported?
users
b.With packet switching, why is there essentially no queuing delay when two or fewer users transmit at once, and a queuing delay when three do?
c.What is the probability that a given user is transmitting?
d.With three users, what is the probability that all three are transmitting at once?
R14Why do two ISPs at the same level of the hierarchy often peer with each other? How does an IXP earn money?
R15Describe Google's network. What motivates content providers to build their own networks?
R16List the delay components in the end-to-end delay of a packet on a fixed route. Which are constant and which are variable?
R17Find a combination of rate, propagation delay and packet size for which the sender finishes transmitting before the first bit reaches the receiver — and another for which the first bit arrives before the sender has finished.
R18How long does a packet of 1,000 bytes take to propagate over a link of 2,500 km, propagation speed 2.5 × 10⁸ m/s, transmission rate 2 Mbps?
The propagation delay, in milliseconds.
ms
R19Host A sends a large file to host B over three links with rates R1 = 500 kbps, R2 = 2 Mbps, R3 = 1 Mbps, with no other traffic.
a.What is the throughput, in kbps?
kbps
b.The file is 4 million bytes. Roughly how long does the transfer take, in seconds?
s
c.Now R2 falls to 100 kbps. How long does the transfer take, in seconds?
s
R20How does a sending host create packets from a file? What does a router use to decide where to forward one? Why is packet switching like driving and asking directions?
R21Using a queue simulation, what emission and transmission rates give a traffic intensity above 1, and how long does it take for loss to start? Does it take the same time if you repeat the experiment?
R22List five tasks a layer can perform. Could one of them be performed by two layers?
R23What are the five layers of the Internet protocol stack, and what is each principally responsible for?
R24What is an application-layer message? A transport-layer segment? A network-layer datagram? A link-layer frame?
R25Which layers does a router process? A link-layer switch? A host?
Pick the correct assignment.
R26What is self-replicating malware?
R27Describe how a botnet can be created, and how it can be used for a DDoS attack.
R28Trudy can capture every packet Alice and Bob send, and can send anything she likes to either of them. List some malicious things she can do.

Problems

Problems P1–P34

These make you use the formulas. Numeric answers are checked to within 1 %, so round sensibly. Every one reveals its full working — but attempt it first.

P1Design an application-level protocol between a cash machine and a bank's central computer. It must verify a card and password, report the balance, and dispense money — including when the account has too little.
P2Equation 1.1 gives the end-to-end delay for one packet of length L over N links of rate R. Generalise it for P such packets sent back to back.
P3An application transmits at a steady rate — it generates an N-bit unit of data every k time units, where k is small and fixed — and runs for a long time.
a.Which kind of network suits it better?
b.If a packet-switched network is used, and all traffic comes from such applications whose combined rate is below every link's capacity, is congestion control needed?
P4In the circuit-switched network of Figure 1.13 there are four switches — call them A, B, C, D clockwise — joined by four links, with four circuits on each link.
a.What is the maximum number of simultaneous connections in the whole network?
connections
b.If all connections are between switches A and C, what is the maximum number at once?
connections
c.Can four connections between A and C, and another four between B and D, all be routed at once?
P5Return to the caravan analogy. Cars travel at 100 km/hour and a tollbooth serves one car every 12 seconds.
a.A ten-car caravan travels 175 km, starting in front of one tollbooth, passing a second, and finishing just after a third. What is the end-to-end delay, in minutes?
minutes
b.Repeat with eight cars instead of ten.
minutes
P6Hosts A and B are joined by a single link of rate R bps. They are m metres apart and the propagation speed is s m/s. A sends a packet of L bits.
a.Express the propagation delay, the transmission time, and the end-to-end delay ignoring processing and queuing.
b.A starts transmitting at t = 0. At t = d_trans, where is the LAST bit of the packet? And at that same moment, where is the FIRST bit — if d_prop > d_trans, and if d_prop < d_trans?
c.With s = 2.5 × 10⁸ m/s, L = 1,500 bytes and R = 10 Mbps, what distance m makes d_prop equal d_trans? Give the answer in kilometres.
km
P7Host A converts speech to a 64 kbps digital stream and groups the bits into 56-byte packets. One link joins A and B, at 10 Mbps with a propagation delay of 10 ms. A sends each packet as soon as it is full; B converts a packet back to sound as soon as it has all of it.
How much time passes between a bit being created at A and being decoded at B, in milliseconds?
ms
P8Users share a 10 Mbps link. Each requires 200 kbps when transmitting, and transmits only 10 % of the time.
a.With circuit switching, how many users can be supported?
users
b.With packet switching, what is the probability that a given user is transmitting?
c.With 120 users, what is the probability that exactly n are transmitting at once?
d.What is the probability that 51 or more of the 120 are transmitting simultaneously?
P9Return to the 1 Mbps example of §1.3.2, where users generate 100 kbps when busy and are busy with probability p = 0.1. Now replace the 1 Mbps link with a 1 Gbps link.
a.What is N, the maximum number of users supported simultaneously under circuit switching?
users
b.With packet switching and M users, give a formula for the probability that more than N users are sending at once.
P10A packet of length L travels from host A over three links, joined by two packet switches. Link i has length dᵢ, propagation speed sᵢ and rate Rᵢ. Each switch delays the packet by d_proc. Ignore queuing.
a.Write the total end-to-end delay.
b.Now put in numbers: 1,500-byte packet, all links 2.5 Mbps, propagation speed 2.5 × 10⁸ m/s on all three, processing delay 3 ms per switch, link lengths 5,000 km, 4,000 km and 1,000 km. Give the end-to-end delay in milliseconds.
ms
P11Same setup, but now all three links have the same rate R, the processing delay is zero, and the switches do NOT store and forward — each transmits every bit as soon as it arrives.
Using the numbers from P10, what is the end-to-end delay in milliseconds?
ms
P12A packet arrives at a switch. One other packet is halfway through being transmitted on the outgoing link, and four more are waiting. Packets are sent in order of arrival, all are 1,500 bytes, and the link runs at 2.5 Mbps.
a.What is the queuing delay for the arriving packet, in milliseconds?
ms
b.Give the general formula: packets of length L, rate R, x bits of the current packet already sent, and n packets already queued.
P13N packets arrive simultaneously at a link where nothing is being transmitted or queued. Each is L bits and the link rate is R.
a.What is the average queuing delay for the N packets?
b.Now suppose N such packets arrive every LN/R seconds. What is the average queuing delay of a packet?
P14Let I = La/R be the traffic intensity, and suppose the queuing delay takes the form I·L/(R(1−I)) for I < 1.
a.Give a formula for the total delay — queuing plus transmission.
b.Describe the plot of total delay against L/R.
P15Let a be the packet arrival rate and μ the link's transmission rate, both in packets per second. Using the total-delay formula from P14, derive the total delay in terms of a and μ.
P16Little's formula says N = a · d, where N is the average number of packets in the buffer plus the one being transmitted, a is the arrival rate, and d the average total delay. Suppose the buffer holds 100 packets on average, the average queuing delay is 20 ms, and the link transmits 100 packets/s.
What arrival rate does Little's formula give, in packets per second?
packets/s
P17Generalise equation 1.2, which assumed every node was identical.
a.First for different processing rates, transmission rates and propagation delays at each node.
b.Now also allow an average queuing delay at each node.
P18Run Traceroute between a source and destination on the same continent at three different times of day, then repeat between different continents.
What should you look for?
P19Metcalfe's law says the value of a network is proportional to the square of the number of connected users. If each of n users sends one message to each of the others, how many messages are sent? Does this support the law?
P20In Figure 1.20(b), suppose there are M client-server pairs rather than 10. Let Rs, Rc and R be the server-link, client-link and shared-core rates. Derive a general expression for the throughput of each download.
P21In Figure 1.19(b), suppose there are M paths between server and client, no two sharing a link. Path k has N links with rates Rₖ₁ … RₖN.
What is the maximum throughput using ONE path? Using all M?
P22In Figure 1.19(b), each of the N links loses a packet with probability p, independently of the others.
What is the probability a packet is received successfully? On average, how many times must the server retransmit before the client receives it?
P23In Figure 1.19(a), the bottleneck is the FIRST link, of rate Rs. Two packets of L bits are sent back to back with no other traffic, and both links have the same propagation delay.
a.What is the time between the two packets arriving at the destination?
b.Now suppose the SECOND link is the bottleneck (Rc < Rs). Can the second packet queue before the second link? If the server waits T seconds between the two packets, how large must T be to avoid that?
P24You must urgently move 50 terabytes from Boston to Los Angeles. You have a dedicated 100 Mbps link. Would you use it, or send disks by overnight courier?
How many days would the link take?
days
P25Hosts A and B are 20,000 km apart, joined by a direct 5 Mbps link with propagation speed 2.5 × 10⁸ m/s.
a.What is the bandwidth-delay product, in bits?
bits
b.A file of 800,000 bits is sent as one continuous message. What is the maximum number of bits in the link at any moment?
bits
c.What does the bandwidth-delay product mean?
d.How wide is one bit in the link, in metres?
m
e.Give a general expression for the width of a bit, in terms of s, R and the link length m.
P26Keeping the link of P25, for what value of R is the width of a bit as long as the whole link?
Give R in bits per second.
bps
P27The same 20,000 km link, but now at R = 500 Mbps.
a.The bandwidth-delay product, in bits.
bits
b.Sending the 800,000-bit file continuously, what is the maximum number of bits in the link at once?
bits
c.How wide is one bit now, in metres?
m
P28Back to the 5 Mbps link of P25, sending an 800,000-bit file.
a.How long does it take if the file is sent continuously? Give the answer in milliseconds.
ms
b.Now break the file into 20 packets of 40,000 bits. Each is acknowledged, acknowledgement transmission time is negligible, and the sender may not send a packet until the previous one is acknowledged. How long now, in seconds?
s
c.Compare the two answers.
P29A 10 Mbps microwave link joins a geostationary satellite to its base station on Earth. Every minute the satellite takes a photograph and sends it. The propagation speed is 2.4 × 10⁸ m/s.
a.What is the propagation delay of the link, in milliseconds?
ms
b.What is the bandwidth-delay product, in bits?
bits
c.Let x be the size of a photograph. What is the minimum x for the link to be transmitting continuously? Give the answer in bits.
bits
P30In the airline analogy of §1.5, headers are added as a packet moves down the protocol stack. Is there an equivalent for passengers and baggage moving down the airline stack?
P31A message of 10⁶ bits travels from source to destination over three links joined by two packet switches, as in Figure 1.27. Each link is 5 Mbps. Ignore propagation, queuing and processing delays.
a.Without segmentation: how long, in seconds, to move the whole message from source to destination?
s
b.Now segmented into 100 packets of 10,000 bits each. At what time, in milliseconds, is the SECOND packet fully received at the first switch?
ms
c.How long, in seconds, does the segmented file take end to end?
s
d.Besides reducing delay, why else segment messages? And what are the drawbacks?
P32Experiment with a message-segmentation animation. Do its delays match your answer to P31? How do link propagation delays affect end-to-end delay, with and without segmentation?
P33A file of F bits is sent over three links joined by two switches, all uncongested. The source splits it into segments of S bits and adds an 80-bit header to each, giving packets of L = 80 + S bits. Every link runs at R bps. Disregard propagation delay.
Find the value of S that minimises the delay.
P34A service lets you call an ordinary telephone from a computer, so the call must cross both the Internet and the telephone network. How might that be done?

Wireshark Lab — watch a web page arrive

The book’s lab asks you to install Wireshark, visit a web site, and examine the messages your browser and the server exchange. Wireshark is a packet sniffer: it passively copies the messages your computer sends and receives, and displays the contents of each protocol field.

That is the same tool §1.6 described as a security problem. Here it is turned to a legitimate purpose — watching your own traffic so that you can understand the protocols.

This lab runs here

You do not need to install anything. Below is a captured exchange with every byte genuine, including both checksums, which were computed rather than invented. If you would rather use the real tool as well, Wireshark is free and runs on Windows, macOS and Linux.

The book’s Figure 1.28 is a screenshot of the Wireshark window. This site does not reproduce it. The working inspector below stands in its place.

What you are looking at

Lin’s laptop at 192.168.1.24 fetches http://www.example.edu/index.html from the server at 198.51.100.7 — the canonical running example. Seven frames: the TCP (Transmission Control Protocol) three-way handshake, the HTTP (HyperText Transfer Protocol) request, and the beginning of the response.

Three panes, exactly as the real tool has them. Click a packet to load it. Click a field in the protocol tree and its bytes light up in the hex dump.

A web page fetch, captured

No.	Time	Source	Destination	Protocol	Length	Info
1	0.000000	192.168.1.24	198.51.100.7	TCP	54	49152 → 80 [SYN] Seq=0 Win=64240
2	0.180216	198.51.100.7	192.168.1.24	TCP	54	80 → 49152 [SYN, ACK] Seq=0 Ack=1 Win=65535
3	0.180298	192.168.1.24	198.51.100.7	TCP	54	49152 → 80 [ACK] Seq=1 Ack=1 Win=64240
4	0.180452	192.168.1.24	198.51.100.7	HTTP	173	GET /index.html HTTP/1.1
5	0.360912	198.51.100.7	192.168.1.24	TCP	54	80 → 49152 [ACK] Seq=1 Ack=120
6	0.361847	198.51.100.7	192.168.1.24	HTTP	175	HTTP/1.1 200 OK (text/html)
7	0.361998	192.168.1.24	198.51.100.7	TCP	54	49152 → 80 [ACK] Seq=120

Packet 1 — The greeting. No web page is requested yet — this packet exists only to ask whether the server is willing to talk. Compare it with the first “Hi” in the human-protocol ladder of §1.1.

Protocol tree — click a field

The actual bytes

0000  aa bb cc 00 00 01 aa bb  cc 00 00 11 08 00 45 00  ..............E.
0010  00 28 1c 46 40 00 40 06  32 8f c0 a8 01 18 c6 33  .(.F@.@.2......3
0020  64 07 c0 00 00 50 9e 1c  3a 55 00 00 00 00 50 02  d....P..:U....P.
0030  fa f0 30 34 00 00                                ..04..

Seven real frames: the TCP three-way handshake, the HTTP request, and the start of the response. Every byte in the hex pane is genuine, including both checksums — you can verify them by hand if you like.

In plain words

The protocol tree is the encapsulation of §1.5, seen from outside. Every frame holds an Ethernet header, wrapped around an IP (Internet Protocol) header, wrapped around a TCP header, wrapped around whatever the application sent. The hex pane shows that these are not four separate things but one continuous run of bytes.

Click the Ethernet destination, then the IP destination, in the same packet. Two addresses, two very different meanings.

Lab exercises

Every answer is in the capture above. Click packets and fields to find it — that is the skill this lab teaches.

L1How many packets pass before any web page is actually requested?
Count them.
packets
L2How long did the server take to answer the opening request, and does that match the running example?
Subtract the time of packet 1 from the time of packet 2, in milliseconds.
ms
L3Select packet 1 and click the Ethernet Destination MAC field. Whose address is it?
L4In packet 4, how many bytes of the frame are headers, and how many are the actual HTTP request?
a.How many bytes of header? (Ethernet + IP + TCP)
bytes
b.Why can you read the HTTP request in the hex pane, but not the TCP header?
L5Find the sequence number in packet 5. Why is it 120 rather than 2?
L6Packet 6 says Content-Length: 102400, but the frame is only 175 bytes. Where is the rest of the page?
L7Click the IP header checksum in any packet. Could you verify it by hand?

Voices from the field — Leonard Kleinrock

Who he is

Professor of computer science at the University of California, Los Angeles. In 1961, as a graduate student at MIT, he created the mathematical theory of packet switching that §1.7 describes. In 1969 his computer at UCLA became the first node of the Internet.

On choosing the field. As a PhD student in 1959 he found most of his classmates working on information theory, where Claude Shannon had already solved the important problems. He judged the remaining questions hard but of lesser consequence, and went looking for an area nobody had thought of yet. Surrounded by computers at MIT, he concluded they would sooner or later need to communicate with each other, and that no effective way existed for them to do it. So he set out to build a mathematical theory for designing efficient, reliable data networks.

On the first message. Nobody had prepared anything historic. Kleinrock notes that Morse and Bell and Armstrong all understood public relations; his team just wanted to log in to the machine at Stanford. They typed L, which arrived. They typed O, which arrived. They typed G, and the host at the far end crashed.

So the first message ever carried by the Internet was, as he puts it, the shortest and perhaps most prophetic possible: “Lo!” — as in lo and behold.

On what he expected. Earlier that same year he had made a prediction. Once the network was running, people would reach computing from homes and offices as easily as they reach electricity or a telephone line. His vision was of something ubiquitous, always on, always available, reachable from any device anywhere — and invisible.

What he did not anticipate, he says, was that his 99-year-old mother and his five-year-old granddaughter would both be using it at the same time. They were.

On what comes next. He expects an Invisible Internet: wireless and mobile devices woven into ordinary spaces, so that desks, walls, vehicles and clothing carry sensors, processing and communication. Software agents that mine data and act on it. Distributed ledgers providing records nobody can alter. More traffic generated by embedded devices than by people. A pervasive global nervous system.

The harder part to predict, he adds, is the applications. E-mail, search, the Web, social networks and file sharing all arrived suddenly and unanticipated.

His advice to students. The Internet is a vast frontier, continuously full of challenges, with room for great innovation. Do not be constrained by today’s technology. Imagine what could be, then make it happen.

Condensed from the interview at the end of chapter 1. The wording is ours except where quoted.

The formulas these problems used

Transmission delay $d_{\text{trans}} = L/R$ — packet length over link rate.
Propagation delay $d_{\text{prop}} = d/s$ — distance over propagation speed.
One packet, N links $= N \times L/R$ (equation 1.1).
P packets, N links $= (N + P - 1) \times L/R$ (P2).
Queuing delay for the $n$ th of a burst $= (n-1)L/R$ ; average over a burst of $N$ is $(N-1)L/(2R)$ (P13).
Total delay with traffic intensity $I$ : $(L/R)/(1-I)$ , or $1/(\mu - a)$ in packets per second (P14, P15).
Throughput $= \min$ of the link rates, or $\min\{R_s, R_c, R/M\}$ when a core link is shared (P20).
Bandwidth-delay product $= R \times d_{\text{prop}}$ — bits in flight. Bit width $= s/R$ (P25).
Optimal segment size $S = \sqrt{40F}$ for an 80-bit header over three links (P33).

What to remember

Almost every delay problem reduces to which of the four delays dominates, and the other three are then noise.
$L/R$ and $d/s$ are the pair you will mix up. Check what each one ignores: transmission ignores distance, propagation ignores packet size and link rate.
A throughput question is always find the bottleneck. Improving anything else is worth zero, and a shared core link can be the bottleneck even when it is the fastest.