CS 536 Fall 2009 - Homework 2Due 10/6/2009 in classTotal Points : 100Instructions. Submit your homework electronically in a text or PDF file. Please use theblackboard to submit your homework by Oct 6th of 2009 before class. Late submission will notbe accepted, nor will we allow group submissions. You can discuss with other students, butplease write your own answers. Please also indicate the set of students you have discussed theproblems with in case you collaborate.To receive credit, all submissions should contain this statement at the beginning: “By turningin this homework submission, I certify that this work was done solely by me.”Problem 1 (10 pts)Consider a datagram network using 32-bit host addresses. Suppose a router has four links,numbered 0 through 3, and packets are to be forwarded to the link interfaces as follows:• 11100000 00000000 00000000 00000000 through 11100000 01111111 11111111 11111111 tointerface 0• 11100000 10000000 00000000 00000000 through 11100000 10000001 11111111 11111111 tointerface 1• 11100000 10000010 00000000 00000000 through 11100000 11111111 11111111 11111111 tointerface 2• otherwise to interface 3a. Provide a forwarding table that has four entries, uses longest prefix matching, and forwardspackets to the correct link interfaces.b. Describe how your forwarding table determines the appropriate link interface for datagramswith destination addresses:11101000 10010001 01010001 0101010111100000 10000001 01000011 0011110011100000 11000000 00010001 01110111Problem 2 (15 pts)Virtual Circuit Network. Consider a virtual-circuit VC number is a 16-bit field.1. What is the maximum number of virtual circuits that can be carried over a link ?12. Suppose a central node determines paths and VC numbers at connection setup. Supposethe same VC number is used on each link along with the VC’s path. Describe how thecentral node might determine the VC number at connection setup. Is it possible thatthere are fewer VCs in progress than the maximum determined in part (a) yet there is nocommon free VC number ?3. Suppose that different VC numbers are permitted in each link along a VC’s path. Duringconnection setup, after an end-to-end path is determined, describe how the links can choosethier VC numbers and configure their forwarding tables in a decentralized manner, withoutreliance on a central node.Problem 3 (15 pts)Switch fabrics.1. Why would there be no input queueing if the switch fabric is n times faster than the inputline rates, assuming n input lines all have the same line rate.2. Consider a router with a switch fabric with 2 input ports A and B, and 2 output ports Cand D. Suppose the switch fabric operates at 1.5 times the line speed.• If, for some reason, all packets from A are destined to D, and all packets from B aredestined to C, can a switch fabric be designed so that there is no input port queuing? Explain why or why not in one sentence.• Suppose now packets from A and B are randomly destined to both C and D. Can aswitch fabric be designed so that there is no input port queuing ? Explain why orwhy not in one sentence.Problem 4 (10 pts)Consider a subnet with prefix 123.123.123.64/26. Give an example of one IP adress (of formxxx.xxx.xxx.xxx) that can be assigned to this network. Suppose an ISP owns the block ofaddresses of the form 123.123.128/17. Suppose it wants to create four subnets from this block,with each block having the same number of IP addresses. What are the prefixes (of forma.b.c.d/x) for the four subnets?Problem 5 (20 pts)Consider the network below:xy5v7w9z8t32s4810u66212Using Dijkstra’s algorithm, and showing your work using a table similar to the one shown inclass slides, do the following:a. Compute the shortest path from s to all network nodes.b. Compute the shortest path from u to all network nodes.c. Compute the shortest path from x to all network nodes.d. Compute the shortest path from z to all network nodes.Problem 6 (10 pts)Consider the network below:uv6x14z5y8329Assume each node initially knows the costs to each of its neighbors. Consider the distance-vectoralgorithm and show the distance entries at node z.Problem 7 (10 pts)Consider the network below, which shows a network with 4 ASes (each enclosed in a box). Nodeidentifiers begin with their AS number.4a4b4c3cx3b3a1c1a1b1d2a2c2bSuppose AS3 and AS2 are running OSPF for their intra-AS routing protocol. Suppose AS1 andAS4 are running RIP for their intra-AS routing protocol. Suppose eBGP and iBGP are usedfor the inter-AS routing protocol.3a. Router 3c learns about prefix x from which routing protocol: OSPF, RIP, eBGP, or iBGP?b. Router 3a learns about x from which routing protocol?c. Router 1c learns about x from which routing protocol?d. Router 1d learns about x from which routing protocol?Problem 8 (10 pts)What is the size of the multicast address space? Suppose now that two multicast groups ran-domly choose a multicast address. What is the probability that they choose the same address?Suppose now that 5,000 multicast groups are ongoing at the same time and choose their multicastgroup addresses at random. What is the probability that they interfere with each