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).
- What
sizes of buffers are needed for the two FIFO channels?
- Are
there non-executable states or transitions?
- 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.
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 1b. 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.
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.
Part2. Protocol Implementation.
Logistics: To
avoid congestion and slow down in machines used in hw3, we divide the machines
in to three groups. You will use one of the groups for your exercise
based on the last digit of your SID. You can use windom or viva machine as backup, in case some of the machines crashed or not responding.
Note: Make sure you logout or hit control-C to kill the processes after you finish your exercises! Dangling processes will slow down your next round experiments or prohit your classmate's from gaining access.
| Last digit of SID |
0, 3, 6, 9 |
1,4,7 |
2,5,8 |
| group of machines used for
hw3 |
wetterhorn, shavano, sanluis,
redcloud |
sanluis, redcloud, crestone,
blanca |
crestone, blanca, wetterhorn,
shavano |
After
finished your exercises, make sure you kill all client or server processes.
Use control-c from the terminal window or "kill <processid>". You
can find the process id by typing "ps aux". If we left too many of these processes
running, these machines will become unbearably slow.
Exercise 2a:
- You
can work on the exercise remotely from home or any machine in the CS Software
Lab ENS 149.
- In
this exercise, you are asked to implement the sender of the alternating
bit protocol.
- I
have implemented the channel and the receiver programs. They are
abrcv.c
and channel.c
in the ~cs522/project/socket/altbit directory. Copy ~cs522/project/socket
directory using
- cp
-r ~cs522/project/socket ~<login>/public_html/cs522/project
Assume you have already create cs522/project directory under your public_html
directory.
- A
template absend.c
is created for you. It handles the command line interface for reading
in the domain names and port numbers of the receiver and channel C1. It contains
the loop that sends the number of packets to the receiver. It
also contains the message structure which we will use to send packets to the
receiver.
struct Msg
{
struct sockaddr_in dst;
struct sockaddr_in src;
char msgtype;
char buf[80];
char alternating_bit; };
- You
need to fill in the declaration of variables for sockets and messages, and
the code that implement the sender part of the alternating bit protocol.
Use select system code to implement the time-out and packet reception transitions
at states 3 and 6.
- I
have included a sample executable absend program in I386 directory.
- For
group 1 with last digit of SS#=0,3,6,9. Here is the instruction on how to
emulate the alternating bit protocol:
- We
are going to run channel C1 on shavano, C2 on sanluis, abrcv (receiver)
on redcloud, absend (sender) on wetterhorn.
- We
should start C1 and C2 first, then abrcv, finally absend.
- telnet
to shavano
- shavano.uccs.edu>
cd ~<login>/public_html/cs522/project/socket/altbit/I386
shavano.uccs.edu>
channel -d -o
set
debug mode on
Channel
will lose odd numbered messages. (1,3,5)
socket
has port #1537
- telnet
to sanluis
- sanluis.uccs.edu>
cd ~<login>/public_html/cs522/project/socket/altbit/I386
sanluis.uccs.edu>
channel -d -e
set
debug mode on
Channel
will lose even numbered messages. (2,4,6)
socket
has port #1499
- telnet
to redcloud
- redcloud.uccs.edu>cd
~<login>/public_html/cs522/project/socket/altbit/I386
redcloud.uccs.edu>
abrcv sanluis 1499
C2hostname=sanluis,
C2PortNo=1499
socket
has port #1226
- telnet
to wetterhorn
- The
absend command allows -n option which specifies how many packets from upper
layer will be sent.
- It
takes the domain name and port number of receiver (abrcv) and C1 as required
parameter.
- wetterhorn.uccs.edu>cd
~<login>/public_html/cs522/project/socket/altbit/I386
wetterhorn.uccs.edu>
absend -n 5 redcloud 1226 shavano 1537
The
number of messages to be sent is 1073928917
socket
has port #3196
State1:
Get New Data=packet 0
State2:
Sending -D0
State3:
Select timeout...
State7:
Resending -D0
State3:
Received +A0 msg
State4:
Get New Data=packet 1
State5:
Sending -D1
State6:
Select timeout...
State8:
Resending -D1
State6:
Select timeout...
State8:
Resending -D1
State6:
Select timeout...
State8:
Resending -D1
State6:
Received +A1 msg
State1:
Get New Data=packet 2
- In
your implementation, you are asked to print out the state and the action
related to the transition, in a format similar to the above produced by
the absend sample program.
- On
the receiver, you will see the following output:
redcloud.uccs.edu>
abrcv sanluis 1499
C2hostname=sanluis,
C2PortNo=1499
socket
has port #1226
State1:
Received +D0 msg=packet 0
State2:
Deliver data=packet 0
State3:
Sending A0
State4:
Received +D1 msg=packet 1
State5:
Deliver data=packet 1
State6:
Sending -A1
State1:
Received +D1 msg=packet 1 It is duplicate or error!
State8:
Resending -A1
State1:
Received +D0 msg=packet 2
State2:
Deliver data=packet 2
State3:
Sending A0
State4:
Received +D0 msg=packet 2 It is duplicate or error!
State7:
Resending -A0
State4:
Received +D1 msg=packet 3
State5:
Deliver data=packet 3
- After
you compiled your absend.c, repeat the above setup and see if you get the
same state transition sequence.
- Repeat
the setup except that for Channel C1 use "channel -d " which does not
lose msg, for Channel C2 use "channel -d -o" which loses odd numbered msgs.
Capture the output of the sender and receiver from the first state 1 to the
2nd state 1. Use absend.txt and abrcv.txt as the filenames.
- Question:
- In
the above experiments, C1 was started, before the receiver was started.
In order for C1 to relay the packets from the sender to receiver, C1 must
know the socket (domain name/IP and portno) address of the receiver, but
it was started before the receiver, therefore we cannot enter the receiver's
portno in the command line for C1. Same problems for C2 w.r.t. the
sender. This is similar to a chicken-egg problem, i.e., which process should
we start first. Discuss how we solve this problem.
- The ABWPlot accepts
the datagram with structure data defined as below:
struct MSG {
int id;
struct timeval tv;
int bw;
} msg;
- Your measure.c program
will be similar to idgs.c but instead of sending character string data, it
sends out a structured MSG data defined above.
- You can reuse idgs.c
for setting up the socket and command line processing.
- Measure.c will set msg.id
to your SS# % 2. (Either one or zero). Same for all packets.
- After set up the socket
address, the program will go through a loop like this
- for
(i=0; i<n; i++) {
(void)
gettimeofday(&msg.tv, 0);
msg.bw = 1000000*cos(0.1*i)+5000000;
if
(debug)
printf("packet
%d id=%d time=%d.%d, bw=%d\n",
i,
msg.id, msg.tv.tv_sec, msg.tv.tv_usec, msg.bw);
if
(sendto(#######) < 0)
perror("sending
datagram message");
sleep(2);
}
- You can substitute the bandwidth
expression 1000000*cos(0.1*i)+5000000;
with others. Here 1000000 is bandwidth variation range;
5000000 is the baseline bandwidth.
- The
ABWPlot allows you to change the bandwidth display range.
- After
editing the program, compile it with
cc -o measure measure.c -lm
- Run
the experiment with ABWPlot and measure.
- After
the curve is displayed, hit alt-PrintScreen to get a copy of ABWPlot window
image and go to MS Word and hit control-v to paste the image from clipboard
to the document. You can also save it as PNG or .JPG using photoeditor.
- Turn
in that as part of your hw3ex2.
- mail the answer and the following
urls to chow@cs.uccs.edu:
http://cs.uccs.edu/~<login>/cs522/project/socket/altbit/absend.c
http://cs.uccs.edu/~<login>/cs522/project/socket/altbit/absend.txt
http://cs.uccs.edu/~<login>/cs522/project/socket/altbit/abrcv.txt
http://cs.uccs.edu/~<login>/cs522/project/socket/altbit/abrcv.txt
http://cs.uccs.edu/~<login>/cs522/project/socket/ABWPlot/measure.c
http://cs.uccs.edu/~<login>/cs522/project/socket/ABWPlot/screendump.png
or .doc (this contains the image of screendump).
