HW#3 --- last modified April 06 2023 01:28:13.

Solution set.

Due date: Apr 5

Files to be submitted:
  Hw3.zip

Purpose: To gain experience with internetworking, simple socket programming, and more network tools.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO4 -- Describe local area network protocols including Ethernet, Token Ring, and Wireless LAN, and their major schemes such as Spanning Tree Protocol (STP) in IEEE 802.1D.

LO6 -- Understand network protocols, RIP and OSPF, and the details of IPv4.

LO7 -- Develop a software simulator simulating RIP, OSPF, forwarding and subnetting in IPv4.

LO9 -- Use networking tools including telnet, ping, traceroute, bing, and Ethereal to evaluate simple network characteristics.

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw3.zip file. The written part should be in a file Hw3.pdf. For the written part of the homework you should write solutions to the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Ch 3 #4 (modified) Give forwarding tables for switches S1-S4 in the figure below. Each switch should have a "default" routing entry, chosen to forward packets with unrecognized destination addresses toward OUT. Any specific-destination table entries duplicated by the default entry should then be eliminated.
   
2. Ch 3 #9 (modified) The virtual circuit mechanism described in class assumes that each link is point-to-point. Extend the forwarding algorithm to work in the case that links are both point-to-point and shared-media connections such as Ethernet.
3. Ch 3 #13 (modified) Given the extended LAN shown below, indicate which ports are not selected by the spanning tree algorithm.
4. Ch 3 #37 (modified) Suppose the packet fragments below all pass through another router onto a link with an MTU of 350 bytes, not counting the link header. Show the fragments produced. If the packet were originally fragmented for this MTU, how many fragments would be produced?
5. Ch 3 #43 Suppose an IP implementation adheres literally to the following algorithm on receipt of a packet, P, destined for IP address D:

    if ([Ethernet address for D is in ARP cache])
       [send P]
    else
       [send out an ARP query for D]
       [put P into a queue until the response comes back]
   

   1. If the IP layer receives a burst of packets destined for D, how might this algorithm waste resources unnecessarily?
   2. Sketch an improved version.
   3. Suppose we simply drop P, after sending out a query, when cache lookup fails. How would this behave?
6. For the network below, show how the (a) RIP and (b) link-state algorithm builds the routing table for node D.
7. Ch 4 #1 Consider the network shown below, in which horizontal lines represent transit providers and numbered vertical lines are inter- provider links.
   1. How many routes to P could provider Q's BGP speakers receive?
   2. Suppose Q and P adopt the policy that outbound traffic is routed to the closest link to the destination's provider, thus minimizing their own cost. What paths will traffic from host A?
   to host B and from host B to host A take?
   3. What could Q do to have the B -> A traffic use the closer link 1?
   4. What could Q do to have the B -> A traffic pass through R?
8. Ch 4 #15 (modified) Consider the example internet shown in below, in which sources S1 and S2 send packets to multicast group G, whose members are shaded in gray. Show the shortest-path multicast trees for each source.

For the coding part, I want you to write a program, LinkStateSimulator.java, for the link state protocol and compare it to the behavior of distance vector routing for router in a line (the situation in class where we had a count-to-infinity problem). Your program will be compiled from the command-line by the grader using the line:

javac LinkStateSimulator.java

Your program will be run with a command of the form:

java LinkStateSimulator some_topology_file

Here some_topology_file is the file name of a file containing the network topology to use for the test. For example, the grader might run program with the line:

java LinkStateSimulator test_topology1.txt

The topology file should consist of a sequence of newline terminated lines of the form:

router_port adjacent_router_1_port-distance_1 ... adjacent_router_n_port-distance_n

Items within a line are space separated. The adjacent_router_i portion of adjacent_router_i_port-distance_i should be a valid TCP/UDP port number. The distance_i portion of adjacent_router_i_port-distance should be an integer distance. For example, some_topology_file might look like

13370 11380-1
11380 13370-1 11390-5 11400-7
11390 11380-5
11400 11380-7

When run, your LinkStateSimulator should cycle through the lines of some_topology_file, and for each line, instantiate an appropriate instance of a class MockRouter. Its constructor should take an int portNumber, String[] adjacents so can be fed the port and adjacent routers from the given line in the file. MockRouter should instantiate two Thread's. The run() method of the first thread should create a ServerSocket bound to portNumber. When it accepts a connections, it expects to receive one newline terminated message to which it then responds before closing the connection. MockRouter should be able to respond to three possible messages: (a) link state messages to which it responds with ACK and a newline, (b) h followed by a newline (a history message) to which it responds with all the link state messages its received (and at what time since the start of the simulation), followed by a line with the word TABLE followed by lines giving its routing table, (c) s followed by a newline (stop) to which it responds with STOPPING and a newline and then it stops its thread.

A link state message should be a line with format:

l sender_port originator_port seq_number time_to_live adjacent_router_1_port-distance_1 ... adjacent_router_n_port-distance_n

The second of MockRouter's Thread's run methods should be every 3 + random float between 0 and 1 seconds cycle through each of its neighbors making Socket connections to the neighbor router's port and sending all link state messages it has (its own and those it needs to forward) to its adjacent neighbors. Sequence numbers and time to live should be integers and the time to live should be updated as per the algorithm in the book/class. This thread should also compute a new routing table using Dijkstra's algorithm based on messages received from other routers by the other SocketServer thread.

Your LinkStateSimulator should start() each of a given MockRouter's threads after instantiation. It should then say "Initialization complete. Ready to accept commands." It should then go into a mode where it receives commands from the user, issues responses, and loop. Allowed commands are:

h some_port_number #returns the result of sending an h message to the router some_port_number
s some_port_number #shuts down MockRouter some_port_number
e #exits the program

Given your simulator is working you can construct networks with varying numbers of nodes in a line. Using the history command (h) conduct experiments to see how quick the routes converge for different nodes in your network of a given total number of nodes. Conduct further experiments to see the effect of shutting down a node on how long it takes for the network to re-stabilize.

In addition to these experiments, to gain more practice using netstat and nmap, run each of tools during at least one of your simulations and create a file transcripts.txt with the contents of running these commands. For each of these transcript have a sentence or two explaining what sockets you saw open related to your NetworkSimulator and what ports you saw in use.

Point Breakdown