CS395 Due 11:10 AM, Monday, November 13, 1995 Midterm 2 Ondich You may use an publicly available on-line resource for this exam, and you may use any of your own notes and programs. You may consult with no person other than Jeff Ondich. You may accept divine guidance. Have fun. I. The Link Layer (6 points) If you haven't done so already, read about Carrier Sense Multiple Access with Collision Detection (CSMA/CD) on pages 167-173 of Shay. Then do problem 17 on page 192. II. The Network Layer (12 points) Don't overdo this problem. Though long in statement, it is not complicated in execution. I have enclosed a cnet program and a topology file below (the topology file is just a little gift--you may modify it or discard it as you see fit). The cnet program implements a very rudimentary flooding algorithm. You should read the code to understand what this algorithm does to get a frame from node 0 (Stlouispark in my topology file) to all other nodes. Run the algorithm with various values of INITIAL_TTL. How quickly (in how many hops) does the first copy of the frame arrive at each node? Under what conditions does the frame never arrive at a node or nodes? What happens if you increase INITIAL_TTL to a fairly large value? Now look at the "Frames transmitted" portion of the cnet summary (use cnet -s to get the summary). How is this affected by changing the value of INITIAL_TTL? Modify the code so that whenever node A gets a frame that still has time to live from node B, A retransmits the frame to all its neighbors except B. Hand in the modified code. How does this modification affect the "Frames transmitted"? Finally, explain briefly the main advantages and disadvantages of flooding as a routing algorithm. III. The Transport Layer Let's just skip this layer for now. See part V below. IV. The Application Layer (6 points) 1. If I type "finger president@whitehouse.gov" at my Unix prompt, what destination port number does my finger client try to connect to (this one's easy--take a look at the file /etc/services)? What string does my client send to the destination finger server once the TCP connection has been made? (See RFC 1288.) V. Putting it together (18 points) Suppose I am logged onto neptune.mathcs.carleton.edu, and I type (as I often do) "ftp nic.merit.edu". Suppose further that nic.merit.edu is not in my DNS cache, my IP routing table is as you will find it by logging onto neptune and typing "netstat -r", neptune's ARP cache is empty (by some bizarre and disturbing Act of the Test Writer), and there exist on neptune some sort of software "entities" corresponding to and named after IP and TCP. 1. Describe clearly and concisely what happens next, as my command tries to make contact with the ftp server at nic.merit.edu. Try to be complete within reason--the story you are going to tell me could legitimately be a very long one. Keep your version of the story under two pages. One page should really be enough. 2. My ftp client will be sending a first message off in the direction of nic.merit.edu. After passing through quite a bit of software and accumulating several headers, my message will become a grown-up Ethernet frame on the mathcs Ethernet. Show me the contents of this frame, in as much detail as you can. I want you to fill in the actual values of as many of the fields in the various headers as you can. Also, what, if any, non-header data will this frame contain? (To answer that last question, you need to explain the purpose of this very first nic.merit.edu-bound message.) VI. The Obligatory Frivolous Question (2 points) 1. Direct me to an RFC that might amuse me. Although I find many RFC's interesting, I wouldn't say that 1058 or 1288 are particularly amusing, so you'll need to do better than that. /******************************************************* For midterm 2, Fall 1995, CS395, Jeff Ondich flood.c This program implements a very simple flooding algorithm. Here's what happens: 1. All nodes start up, and node 0 enables its application layer. 2. When the first message is given by node 0's application layer to this flooding algorithm, node 0 sends its own frame, containing only the "Howdy" message and a time-to-live field, to *all* its neighbors. The packet generated by the application layer is discarded, and the application layer is permanently disabled. 3. Upon receiving a frame, any node will increment its own "framesArrived" counter, and decrement the incoming frame's time-to-live field. If this is the first time the flooded frame has arrived, the node stores the frame. If the frame's decremented time-to-live is greater than 0, the node passes copies of the frame to all of its neighbors. 4. When a node shuts down, it announces whether the frame arrived at all, how many times it arrived, and the number of hops it took for the first copy of the frame to arrive. *******************************************************/ #include #include #define CHECK(call) if( (call) != 0 ) {\ (void)fprintf( stderr, "%s:%s, line%d : %s\n",\ nodeinfo.nodename, __FILE__, __LINE__, \ cnet_errstr[cnet_errno]); exit(1); } #define INITIAL_TTL 8 typedef struct { int timeToLive; char message[20]; } Frame; static void physicalReady( CnetEvent, CnetTimestamp, CnetData ); static void applicationReady( CnetEvent, CnetTimestamp, CnetData ); static void shutDown( CnetEvent, CnetTimestamp, CnetData ); static Frame theFrame; static int framesArrived = 0; void reboot_node( CnetEvent ev, CnetTimestamp ts, CnetData data ) { CNET_set_handler( EV_PHYSICALREADY, physicalReady, 0 ); CNET_set_handler( EV_APPLICATIONREADY, applicationReady, 0 ); CNET_set_handler( EV_SHUTDOWN, shutDown, 0 ); theFrame.timeToLive = -1; strcpy( theFrame.message, "No frame arrived." ); if( nodeinfo.nodenumber == 0 ) CNET_enable_application( ALLNODES ); } /********************************************************* physicalReady Processes an in-coming frame. *********************************************************/ static void physicalReady( CnetEvent ev, CnetTimestamp ts, CnetData data ) { int link, length = sizeof( Frame ); Frame f; /* Get the frame and record its appearance,... */ CHECK( CNET_read_physical( &link, (char *)(&f), &length ) ); framesArrived++; /* ...accept it if this is the first time it has arrived here,... */ if( framesArrived == 1 ) theFrame = f; /* ...decrement its time-to-live, and ship it out if it has a positive time-to-live remaining. */ (f.timeToLive)--; if( f.timeToLive > 0 ) { for( link=1; link <= nodeinfo.nlinks; link++ ) { length = sizeof( Frame ); CHECK( CNET_write_physical_reliable( link, (char *)(&f), &length )); } } } /********************************************************* applicationReady Only gets called once, by the application layer of node 0. This is the signal for node 0 to flood a frame with an initial time to live of INITIAL_TTL. applicationReady disables the application layer forever. *********************************************************/ static void applicationReady( CnetEvent ev, CnetTimestamp ts, CnetData data ) { Frame f; int link, length; CHECK( CNET_disable_application( ALLNODES ) ); fprintf( stderr, "%s sending initial frame.\n\n", nodeinfo.nodename ); f.timeToLive = INITIAL_TTL; strcpy( f.message, "Howdy." ); for( link=1; link <= nodeinfo.nlinks; link++ ) { length = sizeof( Frame ); CHECK( CNET_write_physical_reliable( link, (char *)(&f), &length )); } } /********************************************************* shutDown Reports on the number of copies of the flooded frame that arrived, and the number of times it arrived. *********************************************************/ static void shutDown( CnetEvent ev, CnetTimestamp ts, CnetData data ) { fprintf( stderr, "%s\n\tFrame message: %s\n", nodeinfo.nodename, theFrame.message ); if( theFrame.timeToLive >= 0 ) { fprintf( stderr, "\tFrame first arrived after %d hops.\n", INITIAL_TTL - theFrame.timeToLive + 1 ); fprintf( stderr, "\t%d copies of the frame arrived.\n\n", framesArrived ); } else fprintf( stderr, "\n\n" ); } compile="flood.c" host stlouispark { messagerate = 5s link to minneapolis } host minneapolis { messagerate = 5s link to stlouispark link to northfield link to stpaul } host stpaul { messagerate = 5s link to minneapolis link to northfield link to rochester } host northfield { messagerate = 5s link to minneapolis link to stpaul link to rochester link to dundas } host dundas { messagerate = 5s link to northfield link to faribault } host faribault { messagerate = 5s link to dundas } host rochester { messagerate = 5s link to northfield link to stpaul }