CS 145A Lab 3(due: Dec 1st 23:59:59)

Simplified BGP Finite State Machine

Tasks for Lab 3: Implement a (simplified) simplified BGP Finite State Machine

• Your implementation should be able to communicate with several other machines, with the same protocol.
• The protocol is a simplified BGP Finite State Machine, given in this specification. (NOT exactly the one you designed, it's a simplified version of the reference result of lab2)
• The implementation is based on TCP layer. You can assume the TCP is reliable if you get successful return from the socket operation.

The Finite State Machine for implementation:

Note:

"-" on the arcs means "nothing".

If it's used as an operation, that means you don't need to do anything for this transition. (Also, you can display the message on the screen. It's up to you.)

For the "-" from "Active" to "OpenSent", you can make the transition right after you get to "Active".

For the "-/10" from "Established" to "Established", the implementation is up to you: you can send the UPDATE message when a user input something, or you can send an UPDATE message every several second, or just ignore this transition.

" 1 Request for Connection " means the implementation received a request for connection from other machines.

" 2 Connection Succeeded " means the implementation connected to a remote host successfully.

Message format:

Messages are sent in packets. Each packet has the following format: (Note that TCP is actually a streamed connection. The packet may be splitted into several small packets. In this lab, you don't need to worry about the packet fragmentation and combination -- You can assume that each time you call a socket read (with large enough buffer, e.g. >4096) /write, one packet is read or written.)

0－15th Byte: FF (hexadecimal)
16-17th Byte: Unsigned number, Length of the Packet, from the beginning to the end. (So, it should be >=19)
18th Byte: Packet Type:
1 OPEN
2 UPDATE
3 NOTIFICATION
4 KEEPALIVE
19th Byte to the end of the Packet: Routing Data

The following diagram shows the packet format (First 20 Bytes in the packet) in an intuitive way:

(The first row is a ruler in bit and is just for your convenience, it's not part of the packet.)

(There may be more rows after that, if the packet size is larger than 20.)

According to RFC 1771, a BGP should not be larger than 4096.

Requirements:

• Understand this state transition graph.
• The implementation must be able to actively connect to multiple machines and it must be able to accept requests from multiple machines.
  
• The implementation must allow at most one connection from one machine (identified by IP / hostname).
  
• For each connection, the implementation must implement the Finite State Machine described above. The communication must be in the format as described above.
• The implementation should be able to read from a file called "server.conf". The format of server.conf is as follow:

(The first column is a ruler in line and is just for your convenience, it's not part of the file. Items in different columns in the same line is separated by one space.)

1st Line	LISTEN_PORT	Connection_Num(N)
2nd Line	IP_1	Port_1
...
(N+1st) Line	IP_N	Port_N

The implementation should be able to read from "server.conf", listen to any connection coming into the LISTEN_PORT, and activly connect the N (N is the second number in the first line) connections listed in the file.

Possible Problems:

• How to implementation of Finite State Machine
• (Event 13) Check the errors (including operation errors and Packet errors)
• How to identify multiple connections from the same machine ( you solved it in lab1).

Submission:

Please submit your code and your documentation (server.txt) by sending them to weixl@cs.caltech.edu. In the documentation, please write down your design of the program, describe your test suits briefly. Also, please write comments in your codes to help TA to understand your code.

Grading:

Grading will be based on how many correct transitions you've made. Be careful that although you may implement some transitions, your failure of other transitions may make those successful transition unaccessible. In this case, you will lose points for all those successful transitions too. (For example, if your program cannot finish any transition from "Idle" state, you can get no points even other states are implemented correctly -- since there is no way to test the other state before you can start from "Idle".) So, please do the implementation step by step.

TIPS

• Re-Use the codes in Lab 1 (You can use either the reference code or your own code. Remember to delete the unnecessary parts such as maximum connection detection...)
• How to implement the Finite State Machine? Two solution:

1. “if … then…”: write a lot of "if...then" to finish each transition.
2. “State transition table”: build a table, give each action and each event a ID number, something like:

You can build a 2-dimentional array to store this table. And find the proper action and next state directly.

• How to test? (You can run two of your own implementation and see if they works. Also, you can write a very simple program to send and receive packets in BGP format to see if the server works.)
• Incremental Development (You can first finish the basic state transition part, and then deal with the error... For the basic part, you can start from "Idle" state, and then other states that can accessed from "Idle"... and finally the whole transition graph.)
• DON’T START AT THE LAST MOMENT!

TA Hours:

Tue / Thu (20:00 – 22:00) JRG 170
Except: Nov.19 / Nov.21

Acknowledgement: