CS522 F2006 hw#3

Goal:

Learn how to apply reachability analysis to verify and design protocols.
Learn how time-out helps recover message loss in the alterante bit protocol.
Learn how the alternate bit protocol uses a single control bit to gurantee that one and only one msg (not duplicate msg) gets delivered to the upper layer of the receiver.
Learn how to implement protocol (in this case Alternating Bit Protocol) using Socket.
Learn how to write a socket program that implements a protocol entity, in our case the sender.
Learn how to use select() and set up timeout for retransmission when packets are lost.
Learn how to write a program that sends datagram packets with simualted bandwidth data to a ABWPlot Java GUI program running on a different machine.

Assignment Date: 9/26/2006
Due Day:10/2/2006 part1; 10/9/2006 part2
Description:

Part1. Protocol Verification

Exercise 1a. Reachability Analysis

Given the following network of two CFSMs.

Questions:

Perform the reachability analysis on the Network (M, N).
Ans: The following is the reachability graph generated by the reachability analysis. It indicates that there are 20 global states, one deadlock state, global state 12.
What sizes of buffers are needed for the two FIFO channels?
Ans: By observing the reachability graph, the channel from M to N requires a buffer size of two indicated by global state 19, and the channel from N to M requires a buffer size of two as indicated by global states 11 and 17.
Are there non-executable states or transitions?
Ans: After marking the states and transitions appear on reachability graph, we found there is no non-executable states and one transition,
(5, 1, +B) on machine M is a non-executable transition.
(6, 1, +D) on machine N is a non-executable transition.
Try to fix the protocol so that there are no deadlock, no unspecified reception states, and no non-executable states or transitions. Brief explain your design.
Ans: There is a simple solution in this case. Just change the label of the transition 5-(5, 1, +B) on machine M from +B to -D. The following reachability graph validates that there is no error states.

Note you can use a tool called setool to verify your reachability analysis result. The web page for using setool is at http://cs.uccs.edu/~cs522/hw/hwF2004/setool.htm

Exercise 2. Understand the protocol behavior of Alternating Bit Protocol.

Given the alternating bit protocol,

Describe the event sequence, starting from initial states, of the alternating bit protocol, if both channels lose the even messages, i.e., they lose the 2nd, 4th, 6th,... messages appears on channels. Each event can be identified as starting global state--machine:transition->ending global state. For example, (1,1,E,E)--S:NewData-->(2,1,E,E) is the first event.

Include events up to the one that successfully delivers A1 to the Sender.

Ans: The event sequence is as follows:

1. (1, 1, E, E)—S:New Dataà(2, 1, E, E)

2. (2, 1, E, E)—S:-D0à(3, 1, D0, E)
3. (3, 1, D0, E) —R: +D0à(3, 2, E, E)
4. (3, 2, E, E)—R: Deliver Dataà(3, 3, E, E)
5. (3, 3, E, E)—R:-A0à(3, 4, E, A0)

6. (3, 4, E, A0)—A:+A0à(4, 4, E, E)

7. (4, 4, E, E)—S:New Dataà(5, 4, E, E)

8. (5, 4, E, E)—S:-D1à(6, 4, D1, E)

9. (6, 4, D1, E) —C1:Second Msg, loses D1à(6, 4, E, E)

10. (6, 4, E, E)—S:timeoutà(8, 4, E, E)

11. (8, 4, E, E)—S:-D1à(6, 4, D1, E) # this is a retransmission of D1

12. (6, 4, D1, E)—R: +D1à(6, 5, E, E) # 3rd msg on C1, C1delivers D1

13. (6, 5, E, E)—R:Deliver Dataà(6, 6, E, E)

14. (6, 6, E, E)—R:-A1à(6, 1, E, A1)
15. (6, 1, E, A1)—C2: Second Msg, Lose A1à(6, 1, E, E)
16. (6, 1, E, E)—S:timeoutà(8, 1, E, E)
17. (8, 1, E, E)—S:-D1à(6, 1, D1, E)

18. (6, 1, D1, E)—C1:4th Msg, loses D1à(6, 1, E, E)

19. (6, 1, E, E)—S:timeoutà(8, 1, E, E)
20. (8, 1, E, E)—S:-D1à(6, 1, D1, E)
21. (6, 1, D1, E)—R:+D1à(6, 8, E, E) # 5th msg on C1, C1 delivers D1
22. (6, 8, E, E)—R:-A1à(6, 1, E, A1) # retransmission of A1

23. (6, 1, E, A1)—S:+A1à(1, 1, E, E) # This completes the first cycle of Senser's CFSM

Exercise 1c. Byte Ordering in Communications.

We will use penr and pens code to study the impact of byte ordering on network communications.
Run penr on any of vlsi machine (SPARC big endian machine); Run pens on any of the CS Unix machines (Intel little endian machine) to send an structured msg to penr.
First remote login to any of vlsi machines (vlsia, ..., vlsil) using SSH secure shell client or putty with cs522p1 account. Let say you login to vlsib.uccs.edu
cd project/socket/byteorder/SPARC
run "penr" command and record the port number allocated by the OS.
Start another SSH secure shell client and login to any of CS Unix machines, say windom.uccs.edu.
cd ~cs522/project/socket/byteorder/I386
run "pens -i <7th digit of your SID> -x <8th digit of your SID> -y <9th digit of your SID>"
for example, if your last three digits of SID is 234, you will execute "pens -i 2 -x 3 -y 4"
Record what msg got sent by windom and what msg received by vlsia.
You should observe interaction similar to those below:

On SSH Shell Client Window on vlsib:

Last login: Tue Sep 26 22:29:57 2006 from 128.198.16.54
Sun Microsystems Inc. SunOS 5.10 Generic January 2005
vlsib% cd project/socket
vlsib% ls
ABWPlot altbitjava ipc-tutorial.pdf unixdomain
Makefile byteorder mapping
altbit inetdomain sock.pdf
vlsib% cd byteorder
vlsib% cd SPARC
vlsib% ls
penr pens
vlsib% penr
socket has port #57868
sizeof(pen)=24
The no. of bytes received=24
receive pen message:
pen.header.sender = cs522
pen.header.sessionID = 33554432
pen.msg_type = 3
pen.size = 8
pen.x = 768
pen.y = 1024

On SSH Shell Client login to windom:
Last login: Sun Sep 24 17:54:24 2006 from 71-211-49-77.clsp.qwest.net
[cs522p1@windom ~]$ cd ~cs522/project/socket/byteorder/
[cs522p1@windom byteorder]$ ls
ALPHA I386 Makefile penra.c penr.c pensa.c pens.c SPARC
[cs522p1@windom byteorder]$ cd I386
[cs522p1@windom I386]$ ls
penr pens
[cs522p1@windom I386]$ pens -i 2 -x 3 -y 4 vlsib 57868
pens: Command not found.
[cs522p1@windom I386]$ ./pens -i 2 -x 3 -y 4 vlsib 57868
The sessionID is set to 2
The x is set to 3
The y is set to 4
socket has port #32926
sizeof(pen)=24
send pen message:
pen.header.sender = cs522
pen.header.sessionID = 2
pen.msg_type = 3
pen.size = 8
pen.x = 3
pen.y = 4
[cs522p1@windom I386]$
Discuss why pen.SessionID, pen.x, and pen.y values reported by the sender were different from those reported by the receiver, and what are their relationship in terms of mathematic equations.
Ans: For the above example, sender is windom an Intel little endian machine. The pen.header.sessionID on windom is allocated with four bytes and with content 2, 0, 0, 0 (increaing address order). The first byte has a weight of 2^0=1; 2nd byte with 2*8=256 as its weight; 3rd byte with 2^16=65536; 4th byte with 2^24= 16777216. The first byte is the least signifcant byte. When the msg is received by vlsib, same byte order 2,0,0,0 is filled in pen.header.sessionID from lower address to higher memory address. But vlsi is a big endian machine, it interprets bytes with different weight, the first byte is considered as the most signifcant byte and has a weight of 2^24. Therefore the value of sessionID becomes 2 * 2^24=2*16777216=33554532. Same for penx. and pen.y. There are short two byte integer. pen.x at sender is two byte with 3,0 as content and with value as 3*2^0+0*2^8=3. Same order of bytes is receieved vlsib but it interprets as 3*2^8+0*2^0=768.

Part2. Protocol Implementation.

Solution to CS522 F2006 Homework#3: Protocol Verifiation/Implementation

Exercise 2a: