EL5373 Internet Architecture and Protocols

Review Problems Set One

Question 1
Compute the percentage overhead (defined as the number of bytes in headers and trailers divided by the total
number of bytes sent) incurred by sending data payload in
a. fully loaded Ethernet frames (per RFC 894).
b. fully loaded PPP frames.
In both cases, assume the channel to be idle initially. Note that the period that a host must wait before it transmits is
also ignored.
Solution
a. The Header and Trailer of an Ethernet frame count to 18 byte. A fully loaded Ethernet frame has 1500byte of
payload. Thus the overhead is
18
= 1.186%
1500 + 18
b. Similarly, for a fully loaded PPP frame, the overhead is
8
= 0.531%
1500 + 8

Question 2
Assuming initially idle channel, consider sending 400 byte of data over an Ethernet and a PPP Link. What are the
actual overhead percentages for the data transfers?
Solution
This is the same as the previous question, except that the payload sizes have changed. Thus, for an Ethernet frame,
the overhead is
18
= 4.306%
400 + 18
and for the PPP frame, the overhead is
8
= 1.961%
400 + 8

Question 3
As you have learnt, a number of hosts using Ethernet, share a single channel and each collision decreases
throughput. If hosts on a 6-host 10 Mbps 80 m Ethernet LAN send frames 64 byte long,
a. What is the scenario that maximizes throughput of the hosts?
b. For the scenario you chose, what is the maximum number of frames that can be sent in a 1 second time
period?
Explain your assumptions and show all steps. Assume that the speed of light is 2 10 ms .
-1

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

Solution
a. The throughput will be maximized when only one of the 6 hosts transmits data at a time, while all others are
silent (unrealistic, but maximizing throughput).
b. Two answers will be regarded as correct. Given the scenario mentioned above, we can assume no collisions
for both answers.
i. Since each frame is 64 byte long, its transmission takes
64 8
= 51.2 10 = 51.2
10 10

Thus, maximum number of frames that can be sent in 1s is

1
= 19531
51.2 10
ii.

In the above case, we assumed that a single host sends data continuously during the entire 1s period.
This isnt actually allowed in Ethernet because it might result in a greedy host taking the shared bus
forever. In Ethernet, when a host gets hold of the bus, it transmits a frame and waits for a period equal
to twice the maximum propagation delay before starting to transmit the next frame. During this waiting
period, the other hosts get a fair chance to compete for the channel.
In this case, time required for transmission of one frame (which includes the waiting time) is
80
= 52 10 = 52
51.2 10 + 2
2 10
Thus, maximum number of frames that can be sent in this case is
1
= 19,230
52 10

Question 4
Consider the network shown in the figure on the next page. The IP Address and MAC Address of each interface are
given in the figure. Assume ARP cashes at the hosts and routers to be empty initially.
Consider the following three events:
Event 1. Host I sends an IP datagram to Host II.
Event 2. 20 s later, Host II sends an IP datagram to Host III.
Event 3. 20 s later, Host III sends an IP datagram to Host I.
Assuming the three events occur in sequence, answer questions below, for each of them.
a. How many ARP Request-Reply pairs are exchanged?
b. For each of these ARP Request-Reply pair,
i. on which network does the exchange take place? (say PPP, or if Ethernet, give subnet).
ii. what is the IP Address being resolved in the ARP Request?
iii. what is the resolved MAC Address?
iv. who sends the ARP Request, and who sends the ARP Reply?
c. How many frames are sent when the actual IP datagram is transferred? On which networks are the frames
sent? What are the source and destination MAC addresses in each of these frames (if applicable)?
d. What is the order in which the ARP Requests, Replies, and the frames carrying the actual datagram are
sent?

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

131.12.16.50

.3

.4

00:23:06:ff:12:21

00:21:61:d1:1a:01

Host II

Host I

Host III

PPP
131.12.16

140.160.91

Ethernet

Ethernet
.1
00:00:06:0f:ef:3d

Router
.1
03:2f:6e:5f:4d:1a

Solution
Since every segment in the network is being observed separately, the same packet going through a segment and
then going through another would be looked at as two different frames, for easier presentation of answers.

Answer
a

ARP Request Reply pairs

Network used
IP being resolved
Resolved MAC
ARP Request from
ARP Reply from
No. of frames
Network used

c
Network used
d

Sequence of events

Event 1
1
131.12.16
131.12.16.1
00:00:06:0f:ef:3d
Host I
Router
2
131.12.16
Source MAC
Destination MAC
00:23:06:ff:12:21
00:00:06:0f:ef:3d
PPP
Source MAC
Destination MAC
ARP Req - ARP Rep - IP Frame 1 - IP Frame 2

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

Answer
a

Event 2
ARP Request Reply pairs
Network used
IP being resolved
Resolved MAC
ARP Request from
ARP Reply from
No. of frames
Network used

c
Network used
d
Answer
a

Sequence of events

ARP Request Reply pairs

Network used
IP being resolved
Resolved MAC
ARP Request from
ARP Reply from
No. of frames
Network used

c
Network used
d

Sequence of events

1
140.160.91
140.160.91.4
00:21:61:d1:1a:01
Router
Host III
2
PPP
Source MAC
Destination MAC
140.160.91
Source MAC
Destination MAC
03:2f:6e:5f:4d:1a
00:21:61:d1:1a:01
IP Frame I - ARP Req - ARP Rep - IP Frame 2
Event 3
0
2
140.160.91
Source MAC
Destination MAC
00:21:61:d1:1a:01
03:2f:6e:5f:4d:1a
131.12.16
Source MAC
Destination MAC
00:00:06:0f:ef:3d
00:23:06:ff:12:21
IP Frame 1 - IP Frame 2

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

Question 5
Consider the Network of LANs and MAC Bridges shown below.

H1
02:08:10:5f:6e:45

LAN A
2
00:00:1f:1d:02:4e
02:08:01:05:6d:7e
4

1
5e:12:5f:56:6e:45
-

photon

LAN B

catt

01:08:10:5f:6e:45
02:04:05:03:6d:7e

6e:34:90:54:89:07
-

LAN F

H2

LAN D

02:08:16:56:6e:45

LAN C
2

1
04:98:08:78:6f:6a
-

utopia

duke
05:14:5f:6e:04:05
05:12:5f:6e:04:05

06:18:5f:6e:01:45
04:11:10:5f:6e:45

6e:34:90:54:89:07
3

LAN E
Assume all LANs are Ethernet LANs. The priorities of the bridges in the above figure are shown below.

Bridge

Priority (0x)

photon

cd:12

duke

ac:12

utopia

ac:12

catt

bc:15

Answer the following questions.

a.
b.

c.

What are the Bridge Identifiers of the four bridges?

Order the four bridges based on their Bridge Identifiers (answered in a.) and assign them logical numbers 1,
2, 3, and 4 in order, with logical number 1 being assigned to the bridge with the lowest Bridge Identifier. Note
that now, each bridge has three attributes the Name, the Bridge Identifier and the Logical Number.
What are the initial BPDUs that the bridges generate at = 0? Use the notation for BPDUs used in the
example in the slides (<root id, root path cost, bridge id>). Use the bridge Logical Numbers
instead of Bridge Identifiers for the root id and bridge id fields of the BPDUs. Note that this is just a
short hand to avoid writing the whole Bridge Identifiers all the time. In the actual BPDUs exchanged by the
bridges, the whole Bridge Identifiers are used.

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

= 0, = 1, = 2,... and that the bridges receive the

corresponding BPDUs at = 0 + , = 1 + , = 2 + ,... respectively. When the bridges receive BPDUs,
they compute five parameters. Fill in the shaded regions of the tables below using values of these five
parameters generated at each time = + until the network reaches a stable point (i.e., when there are
no further changes in the five parameters computed by each bridge).

d. Assume that the bridges send out BPDUs at

Parameters computed at
photon
Parameter

+
duke
Parameter

Value

utopia
Parameter

Value

Value

catt
Parameter

Root Bridge

Root Bridge

Root Bridge

Root Bridge

Root Port

Root Port

Root Port

Root Port

Root Path Cost

Root Path Cost

Root Path Cost

Root Path Cost

New BPDU

New BPDU

New BPDU

New BPDU

Designated Port(s)

Designated Port(s)

Designated Port(s)

Designated Port(s)

BPDUs sent at
Bridge

=
BPDU

photon
duke
utopia
catt

e.
f.

Mark the state of each port in the Network figure: use b for blocked state and f for forwarding state.
Draw the spanning tree.

g.

If host H1 sends a MAC frame to host H2, list the bridges that receive and/or forward the MAC frame with
the ports at which they receive or forward frames respectively.

h.

Subsequently, if host H2 sends a MAC frame to host H1, list the bridges that receive and/or forward the
MAC frame with the ports at which they receive or forward frames respectively.

Solution
a and b.
Bridge

Logical
Number

Identifier

photon

cd:12:02:04:05:03:6d:7e

duke

ac:12:04:98:08:78:6f:6a

utopia

ac:12:04:11:10:5f:6e:45

catt

bc:15:5e:12:5f:56:6e:45

c.
BPDUs sent at t=0
Bridge
photon
duke
utopia
catt

BPDU

[4,0,4]
[2,0,2]
[1,0,1]
[3,0,3]

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

Value

d. Parameters computed at t=0+, after BPDUs sent at t=0 are received.

photon
Parameter
Root Bridge

Value

1
3
1
[1,1,4]

Root Port
Root Path Cost
New BPDU
Designated
Port(s)

1,2

duke
Parameter

Value

utopia
Parameter

Root Bridge

Root Bridge

Root Port

Root Port

1
3
Root Path Cost
1
New BPDU
[1,1,2]
Designated
Port(s)

Root Path Cost

New BPDU
Designated
Port(s)

Value

1
0
[1,0,1]
1,2,3

catt
Parameter

Value

Root Bridge

3
0
[3,0,3]

Root Port
Root Path Cost
New BPDU
Designated
Port(s)

1,2

BPDUs sent at t=1

Bridge
photon
duke
utopia
catt

BPDU

[1,1,4]
[1,1,2]
[1,0,1]
[3,0,3]

Parameters computed at t=1+, after BPDUs sent at t=1 are received.

photon
Parameter
Root Bridge
Root Port
Root Path Cost
New BPDU
Designated
Port(s)

Value

1
3
1

duke
Parameter
Root Bridge
Root Port
Root Path Cost

[1,1,4] New BPDU

2

Designated
Port(s)

Value

utopia
Parameter
Root Bridge

1
3

Root Port
Root Path Cost

[1,1,2] New BPDU

Designated
Port(s)

Value

catt
Parameter
Value
Root Bridge

1
0
[1,0,1]
1,2,3

Root Port
Root Path
Cost
New BPDU
Designated
Port(s)

1
1
2
[1,2,3]
2

Note, this is a stable point, because the next iteration will not change anything.

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

e. Ports marked below. All Root Ports and all Designated Ports are Forwarding. All other ports are Blocking.

H1
02:08:10:5f:6e:45

LAN A
2

0f1

:f6

0b:

photon

catt

LAN B

:f5

:f7

5b0

LAN F

H2

LAN D

02:08:16:56:6e:45

LAN C
2
1

ff6

8f7

0f:

utopia
-

duke

9f:

:f5

5b:

LAN E

f. The Spanning Tree formed by removing the links connected to Blocking ports. Note that the Bridges are the
nodes of the spanning tree, and the links are its edges. Hosts simply sit on the links, and are not part of the
tree structure. The purpose of the entire process of a. through f. is to arrive at this spanning tree, hence cutting
off all loops in the network (tree property) while keeping it still intact (spanning property).

utopia
LAN C

LAN E

LAN B

duke

photon
LAN A

LAN D

catt
LAN F

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering

g.
Bridge/Port on which
frame is received

Bridge/Port on which
frame is forwarded

Photon / 2
Duke / 3
Utopia / 1
Catt / 1

Photon / 3
Duke / 1
Utopia / 2,3
Catt / 2

Bridge/Port on which
frame is received

Bridge/Port on which
frame is forwarded

Photon / 3
Duke / 3
Utopia / 2
Catt / 1

Photon / 2
DOES NOT FORWARD
Utopia / 1
DOES NOT FORWARD

h.

EL5373
Internet Architecture and Protocols

NYU Polytechnic School of Engineering