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

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.)

00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Marker (all "FF")
Marker (all "FF")
Marker (all "FF")
Marker (all "FF")
Length of the Packet
Type
Data

(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:

(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.)

Possible Problems:

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

  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:

Incoming Events:

Current State

Event1

 

Event 2

 

Event3

 

...

 

State 1

Action 11

Next State 11

Action 12

Next State 12

Action 13

Next State 13

...
State 2

Action 21

Next State 21

Action 22

Next State 22

Action 23

Next State 23

...
State 3

Action 31

Next State 31

Action 32

Next State 32

Action 33

Next State 33

...
... ... ... ... ...

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

TA Hours:

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

 

Acknowledgement:

This lab was originally designed by Yixin Zhao and Bin (Benjamin) Wang from Computer Networking and Protocol Testing Lab, Tsinghua University. It's used as part of the projects in the undergraduate networking class in Tsinghua. We also get help from Dongluo Chen and Xia Yin from CNPT Lab in adapting this lab to CS145a class. (Zhao and Wang are now in Intel Research China.)