CS522 F2002 Midterm Solution

The CS522 F2002 midterm grade distribution is as follows:

98

98

94

94

94

92

91

90

89

87

87

84

84

84

83

82

81

80

80

76

75

74

72

71

71

71

70

70

68

66

64

62

60

60

58

58

57

55

53

53

Problem 1. Reachability Analysis.
Given the following network of two CFSMs,

  1. Perform the reachability analysis on the Network (M, N).
    Ans:
  2. What sizes of buffers are needed for the two FIFO channels?
    Ans: Channel from M to N needs a buffer of size 2 as indicated in global state gs9. Channel from N to M needs a buffer size of 2 as indicated in global state gs8.
  3. Are there non-executable states or transitions?  Specify them.
    Ans: There is no non executable states on both machines. There is a non-executable transition on Machine M (2, 1, +C). There is a non-executable transition on Machine N (3,1,+H).
  4. Assume the errors are caused by two incorrect transition labels on machine M, draw your modified machine M which can result in an error-free protocol with machine N.
    Ans: The following modified machines results in error-free protocol.
     
    Note that Machine N at state 3 needs to receive R otherwise there will be unspecified reception.  The resulting RG is shown in Figure 1.
    The following modified machines will have state explosion problem,

    since there loops that send one message and receive two msg. Messages will be accumulated in the channel. Their partial reachability graph is shown in Figure 2.

 

Figure 1. RG of modified CFSMs.


 

Figure 2. Partial RG of the incorrect CFSMs.



Problem. 2. Trellis Modulation.

Given the same example in Page 29 of the Chapter 3 transmission handout

  1. What signal sequence will be sent when sender gets 01110010 at state 0?
    Ans: 2, 7, 3, 6.

Current State

Input Data

Output Signal

Next State

0

01

2

2

2

11

7

3

3

00

3

2

2

10

6

0
  1. At state 1 the receiver receives a signal with 80 degree phase angle, what the bit sequence should the receiver send to the upper layer?
    Ans: At state 1, the only legal signals are 1, 3, 5, 7. A signal with 80 degree phase angle is closer to signal 1 than signal 3. Therefore it was considered as signal 1. According  to he trellis diagram, at state 1 receiving signal 1, the receiver should deliver 00 to the upper layer.

 

Problem 3. Routing and Internet message format.

Assume blanca.uccs.edu sends a DNS query request to the UCCS DNS server klingon.uccs.edu. Here is the routing table on blanca:

Kernel IP routing table

Destination     Gateway         Genmask         Flags   MSS Window  irtt Iface

128.198.160.0   0.0.0.0         255.255.248.0   U        40 0          0 eth0

127.0.0.0       0.0.0.0         255.0.0.0       U        40 0          0 lo

0.0.0.0         128.198.167.254 0.0.0.0         UG       40 0          0 eth0

The IP address of blanca.uccs.edu is 128.198.162.60.  The Ethernet Mac address of blanca’s network interface card (NIC) is 00:B0:D0:D1:13:5C.

The IP address of klingon.uccs.edu is 128.198.1.250. The Ethernet Mac address of klingon’s network interface card is 00-02-b3-90-d9-3e.

  1. Identify the subnet of blanca using the classless network notation or CIDR notation.
    Ans: 128.198.160.0/21.
  2. For the Ethernet frame, which arrives at klingon’s NIC card and carries the above DNS query request, does its source MAC address field contain 00:B0:D0:D1:13:5C?
    Ans: No. Since the two machines are on a different subnet, the source MAC address field will contains the MAC address of the router’s port that connects to 128.198.1.250’s subnet.
  3. What transport protocol is used to exchange the DNS query and its response?
    Ans: User Datagram Protocol.
  4. For the Ethernet frame that leaves the NIC of blanca and carries the above DNS query request, does its the destination IP address fields contain 128.198.167.254?
    Ans: No. It should contain 128.198.1.250.

Problem 4. Socket Programming.

1.       Is it correct that the ABWPlot program uses datagram and therefore it can accept packets from multiple senders simultaneously?
Ans: Yes. A datagram server accepts packets from multiple senders.

2.       For the sender that sends measurement data to the ABWPlot program, what information uniquely identifies the socket listen by the ABWPlot program?
Ans: IP address and port number.

3.       For the select system call, do we have to reset the timeout value and the readfdset before each call? Why?
Ans: Yes. Otherwise the residual timeout and readfdset values will be used in the next select() call.