CS 352 Exam 3

Spring 2013

    PART I – 32 points

  1. 8 Points
    Suppose that Dijkstra's algorithm computed the following results for network costs starting from node a:
    D(b), p(b) D(c), p(c) D(d), p(d) D(e), p(e) D(f), p(f)
    2, a 1, a 2, c 4, d 3, d
    (a) What is the full path from node a to node f? Express it as an ordered list of nodes starting from a.
    (b) Routing tables store first hops to a destination. What is the routing table at a? If some destination n is directly connected to a, write "n" for the next hop.
    Destination First hop
    b  
    c  
    d  
    e  
    f  
  2. 8 Points

    Node B has nodes A and C as neighbors. B's initial distance vector is [A=1, C=2], identifying the cost of getting to A as 1 and the cost to C as 2. B receives a distance vector from A that contains: [B=1, D=3, E=7, F=9]. Shortly after that, B receives a distance vector from C that contains [B=2, D=8, E=5]

    (a) After B receives these two vectors, what is its view of least-cost distances from B to the following nodes? Express the distance as a single number.

    Destination Least-cost distance
    A  
    C  
    D  
    E  
    F  

    (b) After B updates its distance vector and sends it to C, what is C's distance vector? Express the distance as a single number.

    Destination Least-cost distance
    A  
    B  
    D  
    E  
    F  
  3. 8 Points
    The data shown uses two-dimensional parity and has a one-bit error. Locate and correct the error.
  4. 8 Points

    (a) State the number of bits that the CRC code will occupy given a generator of 101. (b) Compute the CRC code for the bits 101100 with the generator 101.

    5. PART II – 68 points – 4 points each

  5. In a link-state routing protocol:
    (a) A node informs only its neighbors about changes to the state of any of its links.
    (b) The state of a link is dynamically queried to determine whether data can be routed through it.
    (c) The state of a link will change based on the state of other links that share the same node.
    (d) All nodes get updates on node connectivity so each node can build a full graph of the network.
  6. Poison reverse is designed to:
    (a) Detect invalid links on a route.
    (b) Handle the case where link costs may be asymmetric (that is, c(a, b) ≠ c(b, a)).
    (c) A spoofing technique to force a route to go through a specific machine.
    (d) Avoid creating routing loops.
  7. A multi-homed stub Autonomous System:
    (a) Is a subnetwork containing multiple systems but not connected to the Internet.
    (b) Is a subnetwork that is a member of multiple ASes at the same time.
    (c) Is a subnetwork that is connected to only one AS at a time.
    (d) Will not route traffic from one connected AS to another connected AS.
  8. Reverse Path Forwarding (RPF) is used to:
    (a) Route messages from the receiver back to the sender.
    (b) Build a spanning tree.
    (c) Duplicate multicast packets and send them to interested destinations.
    (d) Ensure that forwarding loops do not develop.
  9. The Internet Group Multicast Protocol (IGMP):
    (a) Allows hosts to inform their connected routers that they are interested in joining a multicast group.
    (b) Allows a multicast sender to inform its connected router that it is interested in sending to a multicast group.
    (c) Establishes routes between multicast senders and multicast receivers.
    (d) All of the above.
  10. Channel partitioning protocols such as TDM or FDM:
    (a) Have a high probability of collisions.
    (b) May fail if any node in the network goes down.
    (c) Pass a token to nodes to give them permission to access the network.
    (d) Will never allow a node to use the full channel capacity.
  11. Collisions can occur in this form of MAC protocol:
    (a) Frequency division multiplexing.
    (b) Random access.
    (c) Token passing.
    (d) Polling.
  12. In CSMA/CD, binary exponential backoff is used to:
    (a) Make an adapter wait exactly double the previous interval whenever a frame experiences a collision.
    (b) Increase the chance that an Ethernet adapter will wait longer times as a frame experiences more collisions.
    (c) Require that an adapter first listen to the channel to sense that it is clear before transmitting.
    (d) Ensure that collisions cannot occur because two adapters will never transmit during the same time slot.
  13. IPv6's Neighbor Discovery protocol differs from ARP (Address Resolution Protocol) because:
    (a) It uses TCP instead of UDP for greater reliability.
    (b) A query is not sent to every host on the LAN.
    (c) Hosts never have to send queries because every host periodically sends announcements.
    (d) It uses a three-way handshake instead of a query-response.
  14. An Ethernet switch knows which interface to use to forward an incoming frame based on:
    (a) Having seen a source address in an earlier frame that arrived from that destination interface.
    (b) The administrator having configured a switch table to identify which addresses are at which interfaces.
    (c) The use of ARP to find the corresponding MAC address for an IP address.
    (d) Each interface on a switch having a distinct MAC address and the sender using it as a destination address.
  15. CSMA/CA:
    (a) Waits a random time interval before transmitting after a channel is sensed to be busy.
    (b) Is a taking-turns protocol; a device cannot transmit until it gets a token from the access point.
    (c) Waits a random time interval if a transmitted frame resulted in a collision.
    (d) Allocates time slots for each wireless station, which has to wait for its time slot before transmitting.
  16. Unlike Ethernet, 802.11 uses sequence numbers in its frame to allow the receiver to
    (a) Detect and discard duplicate frames.
    (b) Ensure that all frames are delivered to upper protocol layers in the proper order.
    (c) Request retransmission of missing frames.
    (d) All of the above.
  17. Request to Send / Clear to Send (RTS/CTS) is a feature of the 802.11 MAC to:
    (a) Provide acknowledgements from the access point to indicate that a frame has been received successfully.
    (b) Enable power management by telling the access point that a station will or will not be transmitting anymore.
    (c) Allow all stations to know that one station will be transmitting even if they are out of range of that station.
    (d) Allow one station to negotiate to receive a frame from another station, bypassing the access point.
  18. Differentiated Services (DiffServ) is a technique for:
    (a) Providing quality of service on a network by reserving router resources ahead of time.
    (b) Grouping datagram streams from different servers together if they are routed to the same client.
    (c) Identifying and prioritizing classes of network traffic by tagging IP datagrams.
    (d) Transforming an IP network into one with the properties of a circuit switched network.
  19. A weighted fair queuing link scheduling discipline:
    (a) Services output queues in strict priority order to ensure that their quality of service needs are met.
    (b) Uses multiple output queues and gives each of them an equal percentage of link bandwidth.
    (c) Prioritizes output queues but ensures that each gets a defined minimum percentage of link bandwidth.
    (d) Uses a single output queue per link and transmits packets in the order that they arrive.
  20. A leaky bucket algorithm primarily addresses which quality of service (QoS) problem?
    (a) Bandwidth
    (b) Delay
    (c) Jitter
    (d) Packet loss
  21. The Reservation Protocol (RSVP) is used to:
    (a) Schedule packets in a router's output queue.
    (b) Reserve socket resources on both the client and server.
    (c) Specify the quality of service needs for a stream of datagrams.
    (d) Police traffic to drop any datagrams that exceed a bandwidth threshold.
  22. The RTP Control Protocol, RTCP:
    (a) Is a version of the RTP (Real-Time Protocol) that uses reliable datagram delivery.
    (b) Dynamically modifies an RTP datagram stream to enforce quality of service guarantees.
    (c) Provides a sender with feedback on the quality of service that a receiver is getting.
    (d) Allows an administrator to configure quality of service parameters on an RTP datagram stream.