Using Dijkstras algorithm, find the shortest-path spanning-tree for routing packets fromrouterR1toeveryotherrouter.Clearlyshoweachstepofthealgorithm,includingtheevolutionof the shortest-path set, S. Write your answer in the table below. Each entry in the secondcolumnshouldbeatriple:(NewRouterintheshortestpathset,Next-hopfromR1 toreachthenewrouter,Costtoreachtherouter)

CSC\t458:\tComputer\tNetworks,\tFall\t2015 Department\tof\tComputer\tScience,\tUniversity\tof\tToronto Handout\t#\t11\t-\tSample\tMidterm Date:\tTuesday,\tOctober\t20th Multiple\tChoice\tQuestions Instructions: In the following questions, check all listed assertions that appear to be correct. There is at least one correct assertion per question, but there may be more. Each correct assertion\tchecked\twill\tearn\tyou\tone\tpoint.\tFor\teach\tincorrect\tassertion\tyou\tcheck,\tyou\twill\tlose one\tpoint.\tIf\tyou\tdon't\tknow\tan\tanswer,\tchecking\tno\tassertion\twill\tneither\tearn\tyou\tnor\tlose\tyou any\tpoints. 1.\tLayering.\t\"Layering\"\tis\tcommonly\tused\tin\tcomputer\tnetworks,\tbecause: (a) It\tforces\tall\tnetwork\tsoftware\tto\tbe\twritten\tin\tANSI\t'C'. (b) Encapsulation\tis\tthe\tlowest\toverhead\tmethod\tto\ttransmit\tdata. (c) It\tallows\twidespread\tcode\tand\timplementation\tre-use. (d) It\tkeeps\tnetworks\twarm\tenabling\tthem\tto\trun\tfaster. 2.\tReliable\tFlooding.\tWhich\tof\tthe\tfollowing\tare\ttrue\tstatements\tabout\treliable\tflooding? (a) It is used in Distance Vector table exchange protocols enabling neighboring routers to periodically\texchange\ttheir\ttables. (b) It\tis\tused\tin\tLink\tState\ttable\texchange\tprotocols\tenabling\trouters\tto\tdistribute\tthe\tstate of\ttheir\tlinks. (c) Can\tbe\tachieved\tonly\tif\trouters\talways\tsend\tpackets\tback\tthrough\tthe\tinterface\tthrough which\tthey\tentered\tthe\trouter. (d) Can\tbe\tachieved,\tin\tpart,\tif\tpackets\tcontain\ta\tsequence\tnumber\tand\t"time\tto\tlive"\tfield to\tprevent\tpackets\tfrom\tlooping\tendlessly\tin\tthe\tnetwork. (e) Is\tan\tefficient\tcentralized\talgorithm\tfor\tcalculating\trouting\ttables. 3.\tLongest\tPrefix\tMatch\tLookups.\tWhich\tof\tthe\tfollowing\tare\ttrue? (a) 171.64.128/17\tcannot\tbe\ta\tprefix\tbecause\tit\tis\ta\tClass\tB\taddress. (b) If\ta\trouting\ttable\tcontains\tprefixes\t31.75/16\t(for\twhich\tpackets\tare\tsent\tto\tport\t1)\tand 31.75.93.128/25 (for which packets are sent to port 2) then an arriving packet with IP address\t31.75.93.129\twill\tbe\tsent\tto\tport\t2. (c) A routing table can correctly contain the two prefixes 50.50.128/17 and 50.50.128/18 simultaneously. (d) If a routing table is organized in order of decreasing prefix length, then a routing decision\tmay\tbe\tperformed\tby\tfinding\tthe\tfirst\tmatching\tprefix. 4. Transmission Rate. What transmission rate is needed to transmit a 4" x 6" photograph (uncompressed,\tand\twith\ta\tresolution\tof\t1200\tdots\tper\tinch\tand\t24\tbits\tper\tpixel)\tin\t1\tsecond? (a) 691,200kb/s (b) 28.8kb/s (c) 28.8kbits (d) 8.29Mb/s (e) None\tof\tthe\tabove. Longer\tQuestions 5. Routing Protocols. Consider the network topology shown below. The topology consists of multiple\trouters\tinterconnected\tby\tfull-duplex\tlinks.\tEach\tlink\thas\ta\tstatic\tcost\tassociated\twith\tit which\trepresents\tthe\tcost\tof\tsending\tdata\tover\tthat\tlink.\tFor\texample,\tthe\tlink\tfrom\tR2\tto\tR4\thas a\tcost\tof\t3.\tSome\tof\tthe\tlinks\tare\tsymmetric\t(i.e.\tthe\tcost\tis\tthe\tsame\tin\tboth\tdirections,\tsuch\tas between\tR1\tand\tR6),\twhereas\tothers\tare\tasymmetric\t(i.e.\tthe\tcost\tis\tdifferent\tin\teach\tdirection, such\tas\tbetween\tR2\tand\tR4). a)\tWrite\tdown\tfour\tdifferent\tattributes\tof\ta\tlink\tthat\tcould\tdetermine\tits\t\"cost\". b) Suppose that we decide to use the distributed Bellman-Ford (distance-vector) algorithm to determine\tthe\trouting\tentries\tin\teach\trouter,\tR2,\tR3,\t...,\tR8 that\tdetermines\tthe\troute\tto\tR1.\tWhat is\tan\tupper\tbound\ton\tthe\tnumber\tof\tsteps\tit\twill\ttake\tfor\tthe\talgorithm\tto\tconverge\t(i.e.\tuntil\tthe routing\ttables\tstop\tchanging)?\tExplain\tyour\tanswer. c) Using Dijkstra's algorithm, find the shortest-path spanning-tree for routing packets from router\tR1\tto\tevery\tother\trouter.\tClearly\tshow\teach\tstep\tof\tthe\talgorithm,\tincluding\tthe\tevolution of the shortest-path set, S. Write your answer in the table below. Each entry in the second column\tshould\tbe\ta\ttriple:\t(New\tRouter\tin\tthe\tshortest\tpath\tset,\tNext-hop\tfrom\tR1\tto\treach\tthe new\trouter,\tCost\tto\treach\tthe\trouter). Step New\tentry\tin\tshortest\tpath\tset,\tS (Router,\tNext-hop,\tCost),\tS 1 (R1,\tR1,\t0),\tS\t=\t{R1} 2 3 6. Coding. Represent the bit sequence 101110101100011110101010 in NRZ, NRZI, and Manchester\tencodings. 7. Fragmentation. A TCP message of size 3000 (including the TCP header) bytes is sent over a series of three IP routers. The MTU for the routers (in the order that the message passes through them) are 1500 bytes, 800 bytes, and 1000 bytes. Assume IP header is 20 bytes, link layer\theaders\tare\t30\tbytes,\tand\tpackets\tare\tnot\treordered\tin\tthis\tsystem.\tShow\tthe\tsequence\tof packets as they arrive to the destination node. For each packet identify the packet length, as well\tas\tthe\toffset. 8. End-to-end latency. A message of size 100,000 bytes is sent from a source node A to a destination node B passing through two routers R1 and R2. All three links on the path have a delay\tof\t20\tms.\tNode\tA\thas\ta\ttransmission\trate\tof\t1000\tbits/sec,\tR1\thas\ta\ttransmission\trate\tof 1000,000 bits/sec, and R2 has a transmission rate of 10,000 bits/ sec. Assuming this is a store and forward system, and there is not queueing delay, find the end-to-end latency of the message\tin\teach\tof\tthe\tfollowing\tcases.\tIgnore\tany\theader\toverheads. a)\tWe\tsend\tit\tas\ta\twhole. b)\tWe\tbreak\tthe\tmessage\tinto\t100\tpackets\teach\tof\tsize\t1000\tbytes