Transcript Midterm Solutions

Data Networks Summer 2007
Midterm Exam
Name: _________________________
Email: _________________________
Student ID: _____________________
Problems
Points
1
2
3
4
5
Total
1
1 (20 points) Circuit switching vs datagram packet switching.
(a) State two reasons why circuit switching can provide more predictable communication
performance than datagram packet switching. (6 points)
Guaranteed bandwidth or time slot, fixed network path.
(b) Assume you wish to transfer an n-byte file along a path composed of the source,
destination, 3 point-to-point links, and 2 switches. Suppose each link has a propagation
delay of 20 ms, bandwidth of 2 Mbps, and that the switches support both circuit and
datagram packet switching. Thus you can either break the file up into 1 KB packets, or set
up a circuit through the switches and send the file as one contiguous bit stream. Suppose
that packets have 24 bytes of packet header information and 1000 bytes of payload, that
store-and-forward packet processing at each switch incurs a 1 ms delay after the packet
has been completely received, that packets may be sent continuously without waiting for
acknowledgements, and that circuit setup requires a 1 KB message to make one roundtrip on the path incurring a 1 ms delay at each switch after the message has been
completely received, and the delay at the destination is zero. Assume switches introduce
no delay to data traversing a circuit. You should ignore the circuit teardown. You may also
assume that file size is a multiple of 1000 bytes. For what file size n bytes is the total
latency incurred before the entire file arrives at the destination less for circuits than for
packets? (14 points)
For packet, total transmission time is:
Tp = (n/1000) * (1024*8/2M) + 3*20ms + 2*(1ms + 1024*8/2M)
= n*4.096u + 70.192ms
For circuit:
Tc = (3*1000*8/2M + 3*20ms + 2*1ms)*2 + (n/1000) * (1000*8/2M) + 3 * 20ms
= 208ms + n*4u
So, for Tc < Tp,
n*4u+ 208ms < n*4.096u+ 70.192ms
n > 1.4355MB
2
2 (20 points) Broadcast and switched Ethernet.
(a) State two reasons why broadcast Ethernet, where all hosts on the network share one
single channel (i.e. wire) and CSMA/CD (carrier sense multiple access/collision detect) is
used to arbitrate media access among the hosts, cannot support a large number of hosts
spread across a large geographic area. (6 points)
(1) To implement collision detection correctly, the maximum propagation delay of the
network must be limited and related to the minimum packet size, thus as the physical
length of the network increase, the minimum packet size must also increase, leading
to inefficiency when sending small messages.
(2) Since the medium is shared and has a limited bandwidth/capacity, performance will be
very poor when a large number of hosts are sharing the medium.
(b) A network based on Ethernet bridges (i.e. a switched Ethernet) does not use any routing
protocol like distance vector or link-state to compute forwarding tables at the Ethernet
bridges. Instead it uses two primitives: flooding and address learning. Briefly explain how
these two mechanisms work together to let Ethernet bridges create forwarding tables. You
may assume that the network has a tree topology. (14 points)
If a bridge doesn’t know the destination address, flood packet, packet will reach
destination. Each bridge notices the incoming port for each source address in the flooded
packets and caches the port for subsequent forwarding to the previously seen source
address.
3
3 (20 points) IP forwarding table aggregation.
(a) Because IP packet forwarding is based on longest prefix matching of the packet destination
address against forwarding table entries, it is possible to have redundant entries in the
forwarding table. Forwarding table aggregation is a technique used to combine redundant
entries to reduce the size of the forwarding table. In a few sentences, describe under what
conditions two table entries can be combined and what the combined entry should contain.
(10 points)
(1) Both table entries have the same next hop output.
(2) One entry’s address prefix defines an address space that is a superset of the other
entry’s address space
(3) The combined entry should contain the address pattern and the mask of the original
entry that is the superset and the same next hop output
(b) Perform forwarding table aggregation on the following IP forwarding table and write down
the final table contents after all possible aggregations have been performed. Note that you
may or may not receive any partial credit in this part if your answer to part (a) is incorrect.
(10 points)
Entry # Address Pattern
Mask
Next Hop
1
128.42.222.3
255.255.255.0
R1
2
128.42.128.4
255.255.128.0
R2
3
18.0.0.0
255.0.0.0
R4
4
0.0.0.0
0.0.0.0
R4
5
128.42.127.3
255.255.248.0
R1
6
128.42.216.0
255.255.248.0
R1
7
128.42.128.4
255.255.0.0
R3
Entries 1, 6 can be aggregated, so can entries 3, 4.
Aggregated
entries
Entry #
Address Pattern
CIDR Mask
Next Hop
1
128.42.128.4
255.255.128.0
R2
2
0.0.0.0
0.0.0.0
R4
3
128.42.127.3
255.255.248.0
R1
4
128.42.216.0
255.255.248.0
R1
5
128.42.128.4
255.255.0.0
R3
4
4 (20 points) Consider the simple network in the figure below, in which A and B exchange
distance-vector routing information. All links have cost 1. Suppose the distance vector
routing information has already converged, and now the A-E link fails.
E
A
B
(a) Give a sequence of routing table updates that leads to a routing loop between A and B. (8
points)
Node A
Node B
Dest
Cost
Next
Dest
Cost
Next
Dest
Cost
Next
Dest
Cost
Next
B
1
B
B
1
B
B
1
B
B
1
B
E
1
E
E
infty
-
E
3
B
E
3
E
Dest
Cost
Next
Dest
Cost
Next
Dest
Cost
Next
Dest
Cost
Next
A
1
A
A
1
A
A
1
A
A
1
A
E
2
A
E
2
A
E
2
A
E
4
A
time
A-E fails
(b) Describe an addition to the basic distance-vector routing algorithm that will prevent the
problem identified in (a). Show how it solves the problem in this specific case. (6 points)
Split horizon, with or without poison reverse, eliminates the problem in this case. With split
horizon, a node does not advertise a route to the node that it uses as a next hop to a given
destination. With poison reverse, a node advertises a cost of infinity to the node that it uses
as a next hop to a given destination.
(c) Describe a generalization of the distance-vector routing algorithm that avoids the problem
identified in (a) regardless of the network topology. (6 points)
A path-vector algorithm eliminates the problem in any topology. With path-vector, nodes
advertise the full path, thus allowing all nodes to check for routing loops.
5
5 (20 points) Sliding window based retransmission protocols.
(a) In the stop and go protocol (i.e. the sliding window size is one packet), what is the
minimum number of bits required to encode the sequence number for the protocol to work
correctly? (3 points)
1 bit
(b) If sequence number is not used, the resulting “broken” stop and go protocol may fail to
transfer data correctly. Describe a specific scenario that explains the problem of not using
sequence number in stop and go. (7 points)
Suppose the acknowledgement for the first packet is lost, and the sender retransmits
the first packet after a timeout, then the receiver would mistake the retransmitted first
packet as the second packet when no sequence number is used.
(c) Assuming there is never any packet corruption or loss along a network path, therefore
retransmission is never needed, what are the two primary factors that determine the
overall throughput (in bits per second) of a data transfer using a sliding window protocol?
(3 points)
The sliding window size and the round-trip delay.
(d) State a mathematical formula to describe how the two factors determine the throughput..
(2 points)
Window size in bits
Throughput =
Round trip delay in seconds
(e) What problems can arise if the retransmission timeout value is chosen arbitrarily? Be as
specific as possible. (5 points)
If the RTO is chosen to be smaller than the RTT, then many unnecessary packet
retransmission will result and waste network bandwidth.
If the RTO is chosen to be much larger than the RTT, then the retransmission of a lost
packet will be unnecessarily delayed, leading to poor performance.
6
(Extra work space)
7
(Extra work space)
8
(Extra work space)
9
COMP/ELEC 429 Spring 2006 Midterm Exam
Exam instructions:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
Once you open this exam, you have exactly 1.5 contiguous hour to work on the exam.
It is your responsibility to time yourself and stop after 1.5 hour. No time credit for
breaks allowed.
This exam is closed books, closed notes, closed computers. You must work on this
exam on your own.
You are allowed to use a hand-held calculator for doing arithmetic.
You may not ask the instructors questions during the exam. The exam has been
designed to eliminate ambiguities. When absolutely necessary, state your
assumptions and proceed.
Be sure to fill out the front page with your name, email address, student ID number,
and the time you started and finished the exam.
Sign the pledge in the space provided.
Notation: K=1000, M=1000000, G=1000000000, 1 byte (B) = 8 bits (b).
You may use the reverse side of a page to write your answers. The last few pages are
scratch sheets you may use.
This exam is assigned on 3/2/2006 at 2:20pm.
This exam is due on 3/9/2006 at 1:00pm at Duncan Hall room 1042. Late exam
turn-in will not be accepted. Early turn-in can be submitted to DH 3005.
This exam accounts for 15% of your final grade.
Points assigned to each problem roughly corresponds to the problem’s difficulty.
Be sure to show your work appropriately.
You should write all your answers in this provided exam, and only attach additional
sheets of paper if necessary.
10