CS计算机代考程序代写 algorithm Microsoft Word – assignment4sol.docx

Microsoft Word – assignment4sol.docx

Assignment 4: CMPT 371
To be completed in groups of 1 or 2

1) [19 points] A source host sends a packet with an MTU of 1500 octets in an Ethernet frame.

The MTU or maximum transmission unit indicates the length of the data field in the Ethernet
frame (the length of the IP packet). The length of the IPv4 header is 32 octets. The length of
the TCP header is 24 octets. On its way to the destination the packet passes through a
network with a MTU of 920 octets. Explain how the packet is fragmented by filling in the
requested information in the diagram below. You should create a copy of the diagram below
including the information requested in your solution. The data you are to fill in is indicated in
two ways

a. A space after an = needs to be filled with a numeric value
b. A ? needs to be replaced with a label indicating the type of header and its length in

octets
c. A %% indicates that the field should hold the length of the application data (without

any encapsulating headers). In addition to the final answer you should provide an
equation showing how that length was calculated (either words or just an expression
showing how you combined the supplied values to determine the length. ).

Remember the payload of the IP datagram for each fragment (except the last) must be a
multiple of 8.
Consider what would change in your calculation if the MTU was increased to 927. Does the
amount of data and / or the offset in the first fragment change when the MTU is increased
from 920 to 927? Give an explanation, including a calculation, of why the amount of data
changes (or does not change) and why the offset changes (or does not change).

Original Ethernet frame before fragmentation

Ethernet frames containing IP fragments after fragmentation

%% ? ?

?

? %%

%% ? ?

?

?

MTU= bytes actual size= octets

MTU= bytes, actual size= octets

More=
Offset= octets

More=
Offset= octets
= (value in
header field)

SOLUTION

Original Ethernet frame before fragmentation

Ethernet frames containing IP fragments after fragmentation

TOTAL points

 12 points: 1 point each for red item
o In the data field 1 point for equation in words OR with values

showing how result was determined
o In the data field 1 point for the final answer

 4 points: ½ point for each green item
 4 points: how does the calculation change when MTU increased to 927

If the MTU was increased to 927 then very little changes.
The data length of the first fragment remains the same (1 point) since the payload of the
IP header must be a multiple of 8 the last seven octets of the first fragment will be empty
and the amount of data in the fragment will not change. (1 point)

Usable payload 920: max payload = MTU – IP header =920-32 = 888
But payload must be floor(888/8) * 8 = 888
Usable payload 927: max payload = MTU – IP header =927-32 = 895
But payload must be floor(895/8) * 8 = 888
(1 point for calculation of amount of data)

Therefore, the offset and the amount of data in the second frame will not change either.
Since the amount of data in the first fragment does not change the next octet of data to
be transmitted does not change. Thus, the offset does not change. (1 point)

Application data =
1500-32-24=1444

TCP
24

IPH
32

ETHH

IPH
32

Data
(1444-864) = 580 octets

Data =
920-32-24 = 864

TCP
24

IPH
32

ETHH

ETHH

MTU 920 bytes (actual size 920 octets)

MTU 920 bytes, actual size 612 octets

More=1
Offset=0

More=0
Offset=888 octets
=111 (value of
header field)

2) Consider routing within an AS (autonomous system). Answer the following questions
regarding routing protocols. Each answer should be no more than two sentences per point.

21 points: 1 point for each checked idea below

a) [2 points] What is an AS?

 An autonomous system is a network or group of networks (1 point)
 administered by a single authority

b) [1 point] Where is an internal routing protocol used?

 Inside a single AS

c) [1 point] Where is an external routing protocol used?
 Between different ASs

d) [2 points] What is a distance vector?

 The distance vector for router A is a list of costs from router A to other routers
 one cost from the router A to each of the other routers in the AS

e) [1 point] When using a link state type protocol what routing information is exchanged?

 The cost to each router that is on the same physical network segment

f) [2 points] Consider a router A in an AS. When using a link state type protocol which

routers send routing information to Router A? Which routers does Router A send
routing information to?
 Router A will send its routing information to all other routers in the AS.
 All other routers in the AS will send routing information to Router A.

g) [2 points] One of the problems with distance vector based routing is slow convergence.

What is slow convergence?
 Distance vectors are exchanged with neighbors every T seconds so it takes a

minimum of N*T seconds for information about changes in routing to cross an AS
with diameter N.

 Changes in routing information, and further changes those changes cause, must
cross the network before the routing algorithm converges to a stable state so
convergence to a new state can be slow.

h) [3 points] Is RIP a link state routing protocol? How does RIP mitigate (reduce) the effects

of slow convergence?
 NO

 RIP is a distance vector type routing protocol. (no points for this)
 RIP uses triggered updates to mitigate slow convergence.

 Triggered updates allow distance vectors that have changed due to a recently
received distance vector from their neighbors to be sent to neighbors immediately
after recalculation of the distance vector instead of waiting for the next scheduled
exchange of distance vectors.

i) [2 points] What problem does RIP use triggered updates to mitigate? Briefly explain
how triggered updates mitigate this problem.
 RIP uses triggered updates to mitigate slow convergence.
 Triggered updates allow distance vectors that have changed due to a recently

received distance vector from their neighbors to be sent to neighbors immediately
after recalculation of the distance vector instead of waiting for the next scheduled
exchange of distance vectors.

j) [1 point] When using a link state protocol what routing information is exchanged?

 The cost to all other routers connected to the router using point to point
connections

k) [4 points] Give an example of a link state protocol discussed in class. What method

does this protocol used to share routing information between routers? Give a two to
three sentence summary of this method.
 An example of a link state protocol is OSPF
 OSPF uses controlled flooding to share routing information.
 Routing updates are flooded out all interfaces of the receiving router they did not

arrived on.
 If the packet has been received by the router before it is not flooded again

3) [14 points] Consider the distributed Bellman-Ford algorithm used in the first generation

internet. At station A, new routing tables have just arrived from A’s nearest neighbors B and
D. The cost from A to B is 6 and the cost from A to D is 4. These newly received distance
vectors are given below. Based on these newly received distance vectors calculate a new
distance vector for node A.

New table
Cost Cost Cost Next

A – – – –
B
C
D
E
F
G
H

from B from D
Cost Next Cost Next

A 6 A 2 A
B – – 7 G
C 3 C 6 G
D 8 A – –
E 2 E 5 G
F 10 C 13 G
G 3 E 4 G
H 7 E 8 G

Solution
New table

Cost Cost Cost Next

A – – – –
B 6 11 6 B
C 9 10 9 B
D 14 4 4 D
E 8 9 8 B
F 16 17 16 B
G 9 8 8 D
H 13 12 12 D

4) [20 points] Consider a system using flooding with a hop counter. Suppose that the hop counter

is originally set to the diameter of the network. When the hop count reaches zero, the packet
is discarded except at its destination. Does this always insure that a packet will reach its
destination in the case that there exists at least one operable path? Why or why not? Give an
example or counter example.

2 points: it does not insure that packet will be delivered
6 points for a Clear example that includes

 Diagram of a network indicating a source host and a destination host
used in the explanation.

 Second diagram (or annotated addition to the original showing which
connections have been broken.

12 points for explaining why and referring to the example to help
explain why

The diameter of the network is defined as the length of the longest of the minimum cost
paths through the network (The length of the minimum cost path is one more than the
number of intermediate stations along that path). The hop count is set to the diameter of
the network. As the packet moves through the network, the hop count is decremented each
time the packet is retransmitted.
Given that all links in the network of diameter N are in service then the station which is
connected to the source by the longest minimum cost path is reached by the packet the hop
count will be zero. All stations will be reached on or before the hop for which the hop count
is decremented to zero.
However, if one of the intermediate links fails there may be stations that will not be reached
before the hop count is decremented to zero. Since the packet is not forwarded when the
hop count is zero, the packet will not reach these stations. The failure of the link must
increase the length of the longest minimum cost path through the network to cause this to
happen.

An example is shown below. The solid box indicates a source station. This longest minimum
cost path (assuming unit costs) is of length 2. If a link fails, resulting in the net shown in
the lower figure, the hatched node has a minimum cost path of length 4. A packet with a
hop count of 2 will never reach this station. There is still an operable path to the hatched

( ½ points for each blue entry in
the new table, 1 point for adding 6
to the costs from the distance
vector received from B, 1 point for
adding 4 to the costs from the
distance vector in D, ignore a one
or two arithmetic slips)

station, but the length of the minimum cost path exceeds the maximum hop count (the
maximum

1. A CRC is constructed to generate a 8 bit Frame Check sequence for a 19 bit message. The
generator polynomial is 1)( 3478  XXXXXXP , The message bits for a
particular message are
1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1
a) [4 points] Draw a shift register circuit to perform the calculation of the CRC bits.

1)( 3478  XXXXXXP

(1 point off for adding C8; ½ point off for each missed or extra
connection or circle or square; ½ point off for any other
significant error)

+

C3 C2 C0

+ + +

C1 C5 C4 C6

+

C7

b) [4 points] List four examples of the types of errors an FCS can detect.
 One Single bit error
 One two bit error
 Any odd number of single bit errors
 Burst error of length <= the highest power in the generating function (1 point per bullet) a) [6 points] Can the errors represented by each of the following error polynomials E(X) be detected by the CRC? Why or why not? 0010000100000010000 (1 point for reason, 1 for explaining why reason applies) The error will be detected because the CRC detects all odd numbers of single bit errors; in this case there are 3 single bit errors 0000000010101100000 (1 point for reason, 1 for explaining why reason applies) This is a burst error of length 6, For this CRC there are 7 FCS bits so any burst error with length less than or equal to 7 will be detected. This error will be detected 0001000111111000000 1 1 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 Will be detected E(X) does not divide exactly by P(X) (1 point for explanation, 1 point for calculation) c) [7 points] Determine the FCS using polynomial division. Show your work 1 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 0 (1 point deduction for each error, 2 point deduction for not including extra FCS zeros below heavy line, 1 point off for wrong number of FCS zeros (should be 8), 2 points off for wrong number of digits in FCS remainder, 3 point off for wrong number of digits in the divisor(should be 9) d) [9 points] Determine the FCS using your shift register circuit. Show your work. 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0