Math 343/443 Midterm study guide answers Dordal
Exercise numbers are in the form (3rd_edition)/(2nd_edition).
chapter 1:
======================================================================
#22/18
Either way, we have 35 microsec switch delay and a net 40 microsec
propagation delay. Sent as one packet, we have two 1000-microsec
bandwidth delays as well; sent as two packets, we have three 500-microsec
delays. Thus, the totals are 2075 and 1575, respectively.
======================================================================
======================================================================
chapter 2:
======================================================================
#36/30 Sliding windows
Note that this is the canonical SWS = bandwidth x delay case,
with RTT = 4 sec.
(a)In the following we list the progress of one particular packet. At any given
instant, there are four packets outstanding in various states.
T=N Data[N] leaves A
T=N+1 Data[N] arrives at R
T=N+2 Data[N] arrives at B; ACK[N] leaves
T=N+3 ACK[N] arrives at R
T=N+4 ACK[N] arrives at A; DATA[N+4] leaves.
Here is a specific timeline showing all packets in progress:
T=0 Data[0]...Data[3] ready; Data[0] sent
T=1 Data[0] arrives at R; Data[1] sent
T=2 Data[0] arrives at B; ACK[0] starts back; Data[2] sent
T=3 ACK[0] arrives at R; Data[3] sent
T=4 ACK[0] arrives at A; Data[4] sent
T=5 ACK[1] arrives at A; Data[5] sent ...
(b) (delay changed to 1 sec *latency*)
T=0 Data[0]...Data[3] sent
T=1 Data[0]...Data[3] arrive at R
T=2 Data arrive at B; ACK[0]...ACK[3] start back
T=3 ACKs arrive at R
T=4 ACKs arrive at A; Data[4]...Data[7] sent
T=5 Data arrive at R
======================================================================
#37/31 Sliding windows
T=0 A sends frames 1-4. Frame[1] starts across the R--B link.
Frames 2,3,4 are in R's queue.
T=1 Frame[1] arrives at B; ACK[1] starts back; Frame[2] leaves R.
Frames 3,4 are in R's queue.
T=2 ACK[1] arrives at R and then A; A sends Frame[5] to R;
Frame[2] arrives at B; B sends ACK[2] to R.
R begins sending Frame[3]; frames 4,5 are in R's queue.
T=3 ACK[2] arrives at R and then A; A sends Frame[6] to R;
Frame[3] arrives at B; B sends ACK[3] to R;
R begins sending Frame[4]; frames 5,6 are in R's queue.
T=4 ACK[3] arrives at R and then A; A sends Frame[7] to R;
Frame[4] arrives at B; B sends ACK[4] to R.
R begins sending Frame[5]; frames 6,7 are in R's queue.
The steady-state queue size at R is two frames.
======================================================================
#39/33 Ethernet minimum packet size
Ethernet has a minimum frame size (64 bytes for 10Mbps; considerably
larger for faster Ethernets); smaller packets are padded out to the
minimum size. Protocols above Ethernet must be able to distinguish
such padding from actual data.
======================================================================
#47/39 Ethernet collision timeline
Here is one possible solution; many, of course, are possible.
The probability of four collisions appears to be quite low.
Events are listed in order of occurrence.
A attempts to transmit; discovers line is busy and waits.
B attempts to transmit; discovers line is busy and waits.
C attempts to transmit; discovers line is busy and waits.
D finishes; A, B, and C all detect this, and attempt to transmit, and collide.
A chooses k_A=1, B chooses k_B=1, and C chooses k_C=1.
One slot time later A, B, and C all attempt to retransmit, and again collide.
A chooses k_A=2, B chooses k_B=3, and C chooses k_C=1.
One slot time later C attempts to transmit, and succeeds.
While it transmits, A and B both
attempt to retransmit but discover the line is busy and wait.
C finishes; A and B attempt to retransmit and a third collision occurs.
A and B back off and (since we require a fourth collision) once again
happen to choose the same k<8.
A and B collide for the fourth time; this time A chooses k_A=15
and B chooses k_B=14.
14 slot times later, B transmits. While B is transmitting,
A attempts to transmit but sees the line is busy, and waits for B to finish.
======================================================================
======================================================================
Chapter 3:
======================================================================
#1/1 connections => VCI tables
The following table is cumulative;
at each part the VCI tables consist of the entries at that part
and also all previous entries.
part switch Port VCI | Port VCI
(a) 1 2 0 | 1 0
2 3 0 | 0 0
3 0 0 | 3 0
(b) 1 3 0 | 1 1
2 3 1 | 1 0
4 3 0 | 1 0
(c) 2 2 0 | 0 1
3 0 1 | 2 0
(d) 1 0 0 | 1 2
2 3 2 | 0 2
3 0 2 | 3 1
(e) 2 1 1 | 0 3
3 0 3 | 1 0
4 2 0 | 3 1
(f) 1 1 3 | 2 1
2 1 2 | 3 3
4 0 0 | 3 2
======================================================================
#3/2 datagram forwarding
Node A: Node B:
Dest Next hop Dest Next hop
B C A E
C C C E
D C D E
E C E E
F C F E
Node C: Node D:
Dest Next hop Dest Next hop
A A A E
B E B E
D E C E
E E E E
F F F E
Node E: Node F:
Dest Next hop Dest Next hop
A C A C
B B B C
C C C C
D D D C
F C E C
======================================================================
#4/3 datagram forwarding with DEFAULT entry
S1: destination port
A 1
B 2
default 3
S2: destination port
A 1
B 1
C 3
D 3
default 2
S3: destination port
C 2
D 3
default 1
S4: destination port
D 2
default 1
======================================================================
#15/13 Ethernet learning bridges
When A sends to C, all bridges see the packet and learn where A is.
However, when C then sends to A, the packet is routed directly to A
and B4 does not learn where C is. Similarly, when D sends to C,
the packet is routed by B2 towards B1 only, and B1 does not learn
where D is.
B1: A-interface: A B2-interface: C (not D)
B2: B1-interface: A B3-interface: C B4-interface: D
B3: B2-interface: A,D C-interface: C
B4: B2-interface: A (not C) D-interface: D
======================================================================
======================================================================
Chapter 4:
======================================================================
#1/1 IP addresses are per host, not per machine
IP addresses include the network/subnet, so that interfaces
on different networks must have different network portions
of the address. Alternatively, addresses include location
information and different interfaces are at different locations,
topologically.
Point-to-point interfaces can be assigned a duplicate
address (or no address) because the other endpoint of the link
doesn't use the address to reach the interface; it just sends.
Such interfaces, however, cannot be addressed by any other
host in the network. See also RFC1812, section 2.2.7, page 25,
on ``unnumbered point-to-point links''.
======================================================================
#2/2 Fragmentation, header layout issues
The IPv4 header allocates only 13 bits to the Offset field,
but a packet's length can be up to 2^16 - 1.
In order to support fragmentation of a maximum-sized packet,
we must count offsets in multiples of 2^{16-13} = 2^3 bytes.
The only concerns with counting fragmentation offsets in 8-byte units
are that we would waste space on a network with MTU = 8n+7 bytes,
or that alignment on 8-byte boundaries would prove
inconvenient. 8-byte chunks are small enough that neither of
these is a significant concern.
======================================================================
#15/12
Here is the table for (c):
stored | distance to reach:
at node | A B C D E F
----------+--------------------------
A | 0 6 3 6 4 9
B | 6 0 3 4 2 9
C | 3 3 0 3 1 6
D | 6 4 3 0 2 9
E | 4 2 1 2 0 7
F | 9 9 6 9 7 0
======================================================================
#18/14
A-----B-----C
| | |
| | |
D-----E-----F
======================================================================
#20/15 Standard DV update exercise
(a) "inf" = infinite cost
A: dest cost nexthop B: dest cost nexthop
B inf - A inf -
C 3 C C inf -
D inf - D 4 E
E inf - E 2 E
F 9 C F inf -
D: dest cost nexthop F: dest cost nexthop
A inf - A 9 C
B 4 E B inf -
C inf - C 6 C
E 2 E D inf -
F inf - E inf -
(b)
A: dest cost nexthop
B 12 D
C 3 C
D 8 D
E 10 D
F 9 C
D: dest cost nexthop
A 8 A
B 4 E
C 11 A
E 2 E
F 17 A
(c)
C: dest cost nexthop
A 3 A
B 15 A
D 11 A
E 13 A
F 6 F
======================================================================
======================================================================
Here are solutions for the two that didn't appear in the text.
1. (a). A's table:
200.0.{5,6} direct
default B
B's table:
200.0.{6,7,9} direct
200.0.5 A
200.0.10 C
default D
C's table
200.0.{9,10} direct
default B
D's table
200.0.{7,8} direct
200.0.{5,6,9,10} B
default DEFAULT
(b): Note there is more than one possible solution; A can use either B
or C as a default path.
Still other solutions are *possible*.
B *could* use A as default, if A defaulted to C
and C defaulted to D, but that would be somewhat inefficient.
======================================================================
2. A sends an ARP request "where is B", but lists C's phys addr.
Then B will reply, but to *C*. B will install the entry
in its table. C will receive the reply packet and discard it.
Any *other* machine that had had A in its cache will now also
update its entry to that above,
Such machines that had been sending to A will now also send to C,
and C will (unless it is a router) discard the packets.
Even C will have this entry. It may or may not actually
*receive* the packet sent to its own ethernet address, but
either way A surely will not receive it.