HOMEWORK PROBLEMS #5
5-1 Internet has many small building blocks as those shown in the following figure, called motif of type (a), type (b), … , type (e) here.
(a) (b) (c) (d) (e)
(i) Rank the above motifs in terms of their robustness against edge-removal attacks, from the strongest to the weakest.
(ii) From the above motifs (a)-(e), comment whether or not the “edge betweenness” values can be used as a unique measure of the (strong or weak) robustness against edge-removal attacks.
5-2 Consider the following undirected and unweighted network:
• Convert the network to be a weighted network, in such a way that the weight of the edge connecting node and node is defined as , where is the degree of node and is the degree of node . For every edge in the network, calculate its weight.
• For the weighted network you obtained in part (i), a “distance” between two adjacent nodes may be defined as the reciprocal of the edge weight between them, namely, . Convert all the weights to distances on the above-obtained weighted network, and mark each distance nearby on the graph.
• If the network is part of the Internet, and all nodes are AS, explain why the above-defined “distance” is meaningful.
5-3 In terms of data routing, rank the four network topologies shown in the following figure, to be the best, the second, the third, the worst, where represents AS and represents IXP. Suppose that the cable costs are negligible. Briefly explain why you think so.
(a) (b) (c) (d)
5-4 Consider the Internet AS-level Transit-Stub topology shown in the following figure, and view both transit and stub domains as nodes in the graph.
• Compute the coreness of this network.
• Compute the Clustering Coefficient of any one Transit Domain.
• Compute the edge weight of any one edge inside the Transit Domain clique:
_________ (Here, the clique has 4 Transit Domains: )
5-5 Consider the following mobile communication network, where red dots are stations, dash-circles are their signal coverages, black solid lines are optical fiber cables, and hexagonal areas (containing fully-connected squares inside) are local P2P networks. From a general (non-technical) viewpoint, compare the advantages and disadvantages of the three designs (a), (b), (c) in terms of efficiency, cost and robustness, etc.
(a) (b) (c)
Advantages
Disadvantages
(a)
(b)
(c)