CSSE 432 - Computer Networks Rose-Hulman Institute of Technology Spring 2007-2008 Computer Science and Software Engineering 1 of 7 Mid-term Exam 2 Name:____________________________________________ CM: __________________ Instructions: • Write all answers on these pages. • Skim the entire examination before starting, and then budget your time. Authorized resources: • You may use a 8.5’ x 11’ sheet of paper with notes on both sides. You may NOT borrow another person’s notes. • You may use a calculator. Unauthorized resources: You are NOT permitted to use any resources other than those identified above. In particular, you may NOT use books, electronic files, PDAs, or computers. Good luck! Problem Max pointsPoints Earned 1 10 2 10 3 10 4 7 5 7 6 6 7 50 Total 100CSSE 432 - Computer Networks Rose-Hulman Institute of Technology Spring 2007-2008 Computer Science and Software Engineering 2 of 7 1. [10 points] TCP Congestion Control You are given the following description of events that occur in a TCP connection. Using the chart provided below, plot the size of the congestion window size versus transmission round. Also, indicate the value of the threshold if it changes. Recall that TCP ensures congestion control with Slow Start, AIMD, and the use of a threshold. Also, recall the refinements to the TCP congestion control mechanism that take into account the different ways in which loss is detected. the events are listed in the order in which they occurred: Transmission round Event Threshold value 1 TCP connection established and data transfer begins (Don’t plot the connection establishment phase – start with the segment transfer at time 1 MSS) 30 5 Loss event detected by timeout event 18 Loss event detected by duplicated ACKS Plot the graph until 30 transmission rounds. Transmission roundTCP Congestion controlCSSE 432 - Computer Networks Rose-Hulman Institute of Technology Spring 2007-2008 Computer Science and Software Engineering 3 of 7 2. [10 points] Routing algorithms Consider the network shown below. Using Dijkstra's algorithm, fill in the table below to compute the shortest path from node A to all network nodes. You may not need to use all the rows in the table. step N D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F) D(G),p(G) 0 1 2 3 4 5 6 7 8 9 10CSSE 432 - Computer Networks Rose-Hulman Institute of Technology Spring 2007-2008 Computer Science and Software Engineering 4 of 7 3. [10 points] Error detection using CRC codes Given that the generator polynomial G = 1001, the data to be transmitted D = 10101011, determine the length of R (the remainder, r) and the value of R. Also, specify the value of (D. 2r ) XOR R.CSSE 432 - Computer Networks Rose-Hulman Institute of Technology Spring 2007-2008 Computer Science and Software Engineering 5 of 7 4. [7 points] What is the difference between a datagram network and a virtual-circuit network? 5. [7 points] Explain CSMA/CD as implemented in Ethernet technology. 6. [6 points] Explain the exponential backoff algorithm used in Ethernet technology.CSSE 432 - Computer Networks Rose-Hulman Institute of Technology Spring 2007-2008 Computer Science and Software Engineering 6 of 7 7. [50 points]Vocabulary You are given a list of 25 terms and definitions. All of the terms have matching definitions in the list, and all the definitions have matching terms. You need to match each term with its definition. Here are the definitions. Fill in the number of the matching term from the list. a 48-bit pattern that is used by Ethernet hosts to inform other hosts on the shared bus of a collision a bit pattern specified at the beginning of each Ethernet frame that is used to synchronize the Ethernet sender and receiver. a data-link layer device that stores, forwards, and filters Ethernet frames a MAC protocol in which a token is passed between hosts that shared the access medium and the host that holds the token can transmit data. a mechanism to prevent either side of a connection from overwhelming the other a network layer protocol used by hosts and routers to communicate network level information a physical layer device that amplifies and forwards packets a router that is a direct link to another autonomous system a table that contains the MAC address that corresponds to a specific IP address a table that contains the prefix value and the next interface to take to reach the prefix. a type of IP addressing in which the length of the subnet mask is not fixed to be 8,16, or 24 and addresses are not mapped into class a, B or C addresses. an intra-AS routing protocol that uses the distance vector algorithm an intra-AS routing protocol that uses the link-state algorithm decreasing transmission rate quickly (halving it) when congestion is observed encapsulating a packet; including all of its headers; inside another packet layer of the Internet Protocol Stack that routes datagrams from one host to another host in the network. layer of the Internet Protocol Stack that routes frames from one host to adjacent/neighboring host. queued datagram in the front of a datagram in an input port of router may delay the transmission of one or more packets region within a subnet in which if more than one host were to transmit collisions of the data frames would occur regions routers are aggregated into routers provide feedback to the sending node indicating overwhelmed routers the number of bytes that a TCP receiver can receive without overflow. the random access MAC protocol in which all hosts are synchronized with each other and must transmit a ready frame only at the beginning of a time-slot. type of routing in which the datagram is forwarded to the closest router in the autonomous system. type of routing protocol which advertises to an AS which other ASes are reachable through a specific AS and propagates this information to all the routers in the ASCSSE 432 - Computer Networks Rose-Hulman Institute of Technology