ELEC 373, W24 : Solution #4

Problem 1
a. Instead of finding a MaxWeight matching in a bipartite graph, suppose we do the following:

(1) Start with an edge with non-zero weight, add it to the matching;
(2) Add a non-zero weight edge to the matching which does not conflict with the first edge;
(3) Continue to add non-zero weight edges such that there are no conflicts at any stage, till you cannot
add any more edges.

(Remark : Two edges are in conflict if they have a common node.) Such a matching is called a maximal
matching. Find at least two maximal matchings in the following graph (only edges with non-zero
weight are shown).

ANSWER:
Intuitively, a maximal matching is a matching in which you cannot add more edges without conflicting
the existing edges. Below are two example maximal matchings. 

b. Show that the ratio of the weight of a maximal matching to the weight of a MaxWeight matching can
be arbitrarily close to zero.

ANSWER:
Consider the graph

Problem 1 continued on next page. . . Page 1 of 6

We see that

is a maximal matching with weight 2.

is the MaxWeight matching (with weight w). The ratio of between the weights of the two matchings
is w2 → 0 as w → ∞. 

c. Consider the following greedy algorithm for a bipartite graph matching problem.

(1) Pick an edge with the largest weight and add it to the matching;
(2) Remove all edges from the graph that conflict with the edge picked in (1);
(3) Repeat step (1) and (2) in the remaining graph until the remaining graph is empty.

Such a matching is called a greedy maximal matching. Find two greedy maximal matchings in the
graph below.

ANSWER:
Below are two example greedy maximal matchings.

Page 2 of 6
 ELEC 373, W24 : Solution #4

Problem 2
Consider a router that interconnects three subnets: Subnet 1, Subnet 2 and Subnet 3. Suppose all of the
interfaces in each of these three subnets are required to have the prefix 223.1.17/24. Also suppose that
Subnet 1 is required to support at least 60 interfaces, Subnet 2 is to support at least 90 interfaces, and
Subnet 3 is to support at least 12 interfaces. Provide three network addresses (of the form A.B.C.D/X) that
satisfy these constraints.

ANSWER:
223.1.17.0/26
223.1.17.128/25
223.1.17.64/28
Note that the answer is not unique.


Problem 3
Consider sending a 2400-byte datagram into a link that has an MTU of 700 bytes. Suppose the original
datagram is stamped with the identification number 422. How many fragments are generated? What are
the values in the various fields in the IP datagram(s) generated related to fragmentation?

ANSWER:
The maximum size of data field in each fragment = 680 (because there are 20 bytes IP header). Thus the
number of required fragments
 
2400 − 20
= 4.
680

Each fragment will have Identification number 422. Each fragment except the last one will be of size 700
bytes (including IP header). The last datagram will be of size 360 bytes (including IP header). The offsets
of the 4 fragments will be 0, 85, 170, 255. Each of the first 3 fragments will have flag=1; the last fragment
will have flag=0. 

Problem 4
Suppose you are interested in detecting the number of hosts behind a NAT. You observe that the IP layer
stamps an identification number sequentially on each IP packet. The identification number of the first IP
packet generated by a host is a random number, and the identification numbers of the subsequent IP packets

Problem 4 continued on next page. . . Page 3 of 6

are sequentially assigned. Assume all IP packets generated by hosts behind the NAT are sent to the outside
world.

a. Based on this observation, and assuming you can sniff all packets sent by the NAT to the outside, can
you outline a simple technique that detects the number of unique hosts behind a NAT? Justify your
answer.

b. If the identification numbers are not sequentially assigned but randomly assigned, would your technique
work? Justify your answer.

ANSWER:

a. Since all IP packets are sent outside, so we can use a packet sniffer to record all IP packets generated by
the hosts behind a NAT. As each host generates a sequence of IP packets with sequential numbers and
a distinct (very likely, as they are randomly chosen from a large space) initial identification number
(ID), we can group IP packets with consecutive IDs into a cluster. The number of clusters is the
number of hosts behind the NAT.

b. However, if those identification numbers are not sequentially assigned but randomly assigned, the
technique suggested in part (a) won’t work, as there won’t be clusters in sniffed data.

Problem 5
Find the least-cost path from every node to node 1 for the following graph using the Dijkstra’s algorithm.

ANSWER:

Page 4 of 6
 ELEC 373, W24 : Solution #4

Step N D(2), p(2) D(3), p(3) D(4), p(4) D(5), p(5) D(6), p(6) D(7), p(7)

0 1 4, 1 5, 1 ∞ ∞ ∞ ∞

1 1, 2 5, 1 7, 2 14, 2 ∞ ∞

2 1, 2, 3 7, 2 14, 2 14, 3 ∞

3 1, 2, 3, 4 13, 4 10, 4 ∞

4 1, 2, 3, 4, 6 12, 6 12, 6

5 1, 2, 3, 4, 6, 5 12, 6

6 1, 2, 3, 4, 6, 5, 7

2→1
3→1
4→2→1
5→6→4→2→1
6→4→2→1
7→6→4→2→1 

Problem 6
Consider the network fragment shown below. Node x has only two attached neighbors, w and y. Node w
has minimum-cost path to destination u (not shown) of 5, and node y has a minimum-cost path to u of 6.
The complete paths from w and y to u are not shown. All link costs in the network have strictly positive
integer values.

a. Give x’s distance vector for destinations w, y, and u.

b. Give a link-cost change for either c(x; w) or c(x; y) such that x will inform its neighbors of a new
minimum-cost path to u as a result of executing the distance-vector algorithm.

c. Give a link-cost change for either c(x; w) or c(x; y) such that x will not inform its neighbors of a new
minimum-cost path to u as a result of executing the distance-vector algorithm.

ANSWER:

Page 5 of 6
 ELEC 373, W24 : Solution #4

a. Dx (w) = 2, Dx (y) = 4, Dx (u) = 7.

b,c. First consider what happens if c(x, y) changes. If c(x, y) becomes larger or smaller (as long as c(x, y) ≥
1), the least cost path from x to u will still have cost at least 7. Thus a change in c(x, y) (if c(x, y) ≥ 1)
will not cause x to inform its neighbors of any changes. If c(x, y) = δ < 1, then the least cost path
now passes through y and has cost δ + 6. In this case, x will inform its neighbors. Now consider if
c(x, w) changes. If c(x, w) =  ≤ 6, then the least-cost path to u continues to pass through w and its
cost changes to  + 5; x will not inform its neighbors of this new cost. If c(x, w) =  > 6, then the least
cost path now passes through y and has cost 11; again x will inform its neighbors of this new cost.
Note that all link costs are positive integers.

Page 6 of 6