COMP412B - Assignment 1 - Protocol Design Matt Brown - 0122881 - Version: $Id: protocol.txt,v 1.15 2003/08/15 04:14:17 mglb1 Exp $ 1. Client <-> Server Protocol Definition 1.1 Structure Every packet consists of a fixed length 32-bit header, followed by a 96-bit HMAC field that can be used to authenticate the packet and ensure that the contents were not modified in transit. The HMAC is followed by a variable length data field. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Packet Header | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | HMAC | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . Data . . . . . The minimum size of a packet is therefore 16 octets (Header, HMAC, No Data). 1.2 Header Every packet must begin with a 32 bit header in the following format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version| idType| Length | aType | opts | Group | pType | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Example Packet Header Figure 1. Note that each tick mark represents one bit position. Version: 4 bits The version field indicates the format of the packet. This specification describes version 1 of the packet. idType: 4 bits The type of client identifier in use. Len: 8 bits Total length in 32-bit words of the packet (including header). aType: 4 bits The type of authentication function used to compute the HMAC field. options: 4 bits See section 1.2.1 for details for the options field group: 4 bits Specifies a group of clients that this packet is relevant for. See section TODO for further details. pType: 4 bits Specifies the format for the remainder of the packet. See section TODO for more details. 1.2.1 Option Fields The following options are available. +-+-+-+-+ |O F * *| +-+-+-+-+ O: Observer - Only valid in ADD and UPDATE packets send by a client. This bit indicates that the client only wants to receive updates from the group and should be part of updates sent to other clients in the group. F: Force Update - Only valid in packets sent from the server. If this bit is set the client should drop any current data it holds and explicitly use the values contained in the packet. This option can be used if the server's clock has gone back in time to force clients to use an update that they would otherwise think from in the past. * indicates that that bit of the option field is currently not used and should be set to 0. 1.3 Packet Types 1.3.1 General Notes The data field of a packet may not be more 532 bytes long to ensure that the entire packet will fit within a 576 byte IP packet. The data portion of the packet must end on a 32-bit boundary. If data section does not naturally end of a 32-bit boundary it should be padded with zeros. 1.3.2 Client Hello (0x1) Type The Client Hello packet is used by a client to notify the server of it's existence. The data section of a Client Hello packet is arranged as shown below. +--------+--------+--------+--------+ | Serial No (Timestamp) | +--------+--------+--------+--------+ | Client ID | +-----------------//----------------+ | Address Family | Port | +--------+--------+--------+--------+ | Client Address | +-----------------//----------------+ The length (in octets) of the client identifier field is defined by the type of id specified in the idType header field. A Client Hello packet is identified by a value of 0x1 in the pType field of the packet header. If the Client ID is not found in the list then a new entry is created, otherwise the packet is used to update the details stored in the list for this client. Upon receipt of a Client Hello packet the server will always respond with a Client Data packet. 1.3.4 Remove Client (0x2) Type The Remove Client packet is identified by a value of 0x2 in the pType field of the packet header. The data section of a Remove Client packet is arranged as shown below. +----------//----------+ | Client Identifier | +----------//----------+ 1.3.5 Client Query (0x8) Packet A Client Query Packet is sent when the server has not heard from a client for a period of time as defined in 1.4.4 and wishes to ascertain whether or not the client is still connected before removing it from it's list of clients. A Client Query Packet is identifed by a value of 0x8 in the pType field of the packet header. A Client Query packet has no data section. When a client receives a Client Query packet it should immediately respond with an Client Hello packet to let the server know it is still alive. 1.3.6 Client Data (0x9) Packet The Client Data packet is the primary packet that the server uses to communicate information about the current state of the other clients to a client. It consists of a series of Client Info records that describe a change in the state of a specified client. Each Client Data packet may contain 1 or more of these Client Info records. The data section of a Client List packet is formatted as shown below. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (Serial No) Timestamp | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Client Info . | . . Timestamp: 32 bits The servers timestamp for this update. Client Info: Variable Lengths The Client Info field contains a series of variable length Client Info records that describe the state or change in state of a particular client. The maximum length of this field is 528 bytes to ensure the entire packet will fit within a 576 byte IP packet. The format for the different Client Info messages is shown below. All Client Info messages begin with a 8-bit header field which allows the format and length of the remainder of that message to be determined. Update Client Info Format: +-+-+-+-+-+-+-+-+--------//--------+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |1 0| Reserved | Client ID | Address Family | +-+-+-+-+-+-+-+-+--------//--------+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Port | Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-----------------//---------------+ An Update Client message is identified by the first two bits having the value 10. The next 6 bits are reserved for future use. These are followed by the ClientID then a 16-bit Address Family and Port. Finally the Client Address belonging to the Address Family. The Client Info record must finish on a byte boundary. No Change / Delete Client Format: +-+-+-+-+-+-+-+-+--------//--------+ |0 X| Reserved | Client ID | +-+-+-+-+-+-+-+-+--------//--------+ The No Change and Delete Client messages share the same message layout which consists only of a Client ID. The No Change message is identified by a value of 00 in the first two bits followed by a 6-bit reserved field. A Delete Client message is identified by a value of 01 in the first two bits. 1.3.7 Group Query (0x3) Packet A client may send a Group Query Packet to a server in order to determine which groups are available on the server. A Group Query packet does not contain a data section. 1.3.8 Group List (0xA) Packet Upon receipt of a Group Query packet the server responds by sending a Group List packet containing a list of all groups that are available on the server. The data section of the packet contains a number of records in the form shown below. +-+-+-+-+-+-+-+-+-----------------------------------------//----+ | Group | Res. | Group Name | +-+-+-+-+-+-+-+-+-----------------------------------------//----+ Group: 4 bits The Group Identifier, there may be no more than 15 groups on a server as group 0 is reserved for the default group. Res: 4 bits Reserved Field. Should be set to 0. Group Name: Variable The Group Name field is interpreted as a series of ASCII bytes which terminates when a NULL byte (0x0) is read. The protocol places not restriction on the length of this name except that it must fit within a single Group List packet, it is expected that the client / server will restrict the group name to a sensible size. The group name has no use in the protocol and is simply provided so the user can easily identify group IDs. 1.3.9 Client Packet Error (0xB) Packet A Client Packet Error Packet is sent by the server in response to a client packet that generated an error during it's processing. The packet consists simply of the standard header followed by a series of bytes that comprise an ASCII string representation of the error message. The string may be up to 531 characters long to ensure that it fits within a single packet. The primary purpose of this packet is to allow the client to determine that there was an error in it's packet and handle it appropriately rather than receiving no response from the server and assuming that the packet was lost. 1.4 Protocol Operation 1.4.1 Principles of Design The protocol is designed to be an intelligent location service. Multiple clients connect to a server and inform the server of their location. In return the client is provided with a list of all other clients that have also registered with the server. The protocol tries to be AF independent and leaves it up to the client to decide which of the other clients it is able to communicate with. The protocol is designed to minimise the amount of traffic passed between the client and server without sacrificing the ability to keep all clients up to date with changes in the network in a timely manner. 1.4.2 Protocol Operation Clients will regularly (UPDATE_INTERVAL) send a Client Hello packet to the server containing details about the location of the service they are registering and the lowest serial number in their list of clients. Upon receipt of a Client Hello packet the server will try to find the Client ID that the packet is from in it's list of clients. If the client is not found it is added and a notice is sent to all other clients. If the client is found it's details are checked against the details just received and if any have changed they are updated and a notice is sent to all other clients. A service location is composed of 3 fields, an Address Family, a Port and an Address. Every packet sent from the server to a client contains a serial number which is the servers current timestamp. Every record that is modified or confirmed as a result of that packet is updated to the that serial number and the client makes a note of the time at which it was updated. If a client record has not been updated for EXPIRE_TIME seconds than it will be removed from the clients list. The purpose of the serial number is to allow the server to send incremental updates to the client. Every Client Hello packet contains the lowest serial number currently present in the client's list. Instead of sending back a full update about every client the server instead sends back changes only for clients that have been updated since that time and a very short no change message for all other clients. A client will not update a record in it's list if the serial number of the packet currently being processed is lower than the serial number of the record in the list. This prevents packets that have been delayed in the network from corrupting the list with old data. This behaviour can be overriden by setting the F flag in the header in which case the client will always use the data in the packet being processed regardless of it's serial number. Before a client leaves the network it should send a Delete Client message to the server so that other clients may be notified of it's absence. This is desirable to avoid having to wait for the entry to timeout. When the server receives a Delete Client message it immediately informs all other clients that the specified client has left the network. When responding only to the originator of the packet that the server recieved the server should respond immediately. If an update is being sent to all clients then the server may choose to hold it in a buffer for up to 1/4 of the UPDATE_INTERVAL to try and decrease the chance of multiple small updates being sent close together. 1.4.3 Client Groups The server may choose to provide a set of groups that clients can belong to. If the server chooses to provide groups it must return a list of these in a Group List packet in response to a Group Query packet from a client. A client may retrieve a list of the groups available on a particular server by sending a Group Query packet. The client does not need to be registered with the server to send a Group Query packet. A client may belong to multiple groups with each group having a different service address / port mapping. Client Hello / Client Delete and Client Data packets will contain data for a single group only. 1.4.4 Protocol Timeouts Each record containing information about another client held by a client or the server will have a associated with it a timestamp of the last update to that record. If the record has not been updated in the last EXPIRE_TIME seconds then it will be removed from the list. A server must attempt to make contact with a client that has not in contact for EXPIRE_TIME seconds by sending a Client Query packet and waiting for a further UPDATE_INTERVAL seconds before removing the client. EXPIRE_TIME must always be at least 3 times greater than UPDATE_INTERVAL UPDATE_INTERVAL may be any value desired but must be the same on both the client and the server. A client should always receive a response from the server when it sends a packet. If a client does not receive a response within SERVER_TIMEOUT seconds the client should wait RETRY_TIME seconds and send the request again. If the client has sent RETRY_LIMIT consequtive packets and not received a reply then the client should keep retrying at intervals defined by an exponential backoff function until a connection is made. The function used to compute the backoff time should have a maximum period between connection attempts of BACKOFF_LIMIT. 1.4.5 Packet Authentication and Verification Each packet contains a 96-bit HMAC field that must contain a checksum to verify the integrity of the packet. Alternatively this field could hold a cryptographic signature of the message to authenticate the sender. The packet header provides a 4-bit aType field to allow specification of the format and contents of the HMAC field. Every server and client must provide support for at least MD5 hash as described in RFC1321. A simple MD5 hash of the packet in the HMAC field is identified by a value of 0x0 in the aType field of the header. All other values for aType are available for implementation specific header checksum / authentication routines. Upon receiving a packet a client/server should immediately verify that the HMAC field is correct using the algorithm specified in the aType field. If the client/server does not recognise the algorithm code specified in the aType field, or the HMAC field does not correctly match the contents of the packet the packet should be immediately discarded without affecting the state of the receiver and no response should be generated. For the purposes of calculating the HMAC value the field should be initialised to zeros. Advanced Authentication implementations may choose to implement additional checks on the data in the packet if it passes the initial validation. The packet may be discarded at any one of these further checks with the same rules as the original validation check. If the packet is discarded it may not affect the state of the receiver in any way and no response should be generated. 1.4.6 Multiple Servers Multiple Servers are supported via a dns round-robbin style approach. Once the addresses for all possible servers have been retrieved the client starts to maintain a score for each server that is initialised off the rtt to that server. If a server ever fails to respond to a query or provides information that is timestamped in the past it's score is increased. If a server continuously provides current information and the client does not detect lost packets then it's score is decreased. Whenever the client needs to send a packet to the server it simply picks the server from it's list with the lowest score. The Server <-> Server protocol described in Section 2 and onwards keeps the servers in synchrony with each other so that it does not matter which one of the servers the client sends the query to. The one exception to this is when responding to a Client Query packet the response must be sent to the server that issued the query. The reason for this restriction will become clear in the next paragraph. When multiple servers are present a method is required to determine which server is responsible for checking on a client if an update has not been received in the last EXPIRE_TIME seconds. When a server receives an Add Client or Update Client packet that server becomes the authoritative server for that client and has the responsibility for staying in communication with that client. If a server is not authoritative for a client in may not remove a client from it's list when the timestamp expires unless the timestamp is older than EXPIRE_TIME+2*UPDATE_INTERVAL seconds. 2 Server <-> Server Protocol Description (this section is incomplete) 2.1 Protocol Description Unlike the UDP Based Client to Server protocol the Server to Server protocol is based on TCP. This provides a reliable sequenced method of transport for updates between each server. It is expected that all of the servers will be NTP synchronised. Upon establishing a connection the two servers will exchange a full client list with each other. After that point they only need to communicate the changes and send ping/pong messages to check that the connection is still alive. The servers can be connected in any topology that you desire however it is intended and recommended that all servers be connected in a mesh and that clients are informed of all available servers. The Server to Server protocol is text based. 2.2 Server to Server Protocol Specification 2.2.1 General Message Format Every message begins on a new line and is of the format 2.2.2 Add Client Message Data ADD [O:true] [G:] [P:] 2.2.3 Update Client Message Data UPD [P:] 2.2.4 Remove Client Message Data DEL 2.2.5 Ping Message PING 2.2.6 PONG 3 Protocol Rational The primary design principles observed in both the client to client protocol and the client to server protocol were - Bandwidth minimisation - Speed of updates That is the protocol should use as little network bandwidth as possible and inform all clients of changes to other clients as quickly as possible. Secondary design considerations were the complexity of the implementation and the storage requirements for the list of clients. In keeping with these principles UDP has been chosen as the communication method used between the client and the server. UDP is the best protocol for this section of the protocol because it is very lightweight and does not require the server to keep a TCP connection open for every client that is connected to it. It also allows clients to jump around between available servers depending on which server is the fastest to respond without having to worry about setting up and tearing down a TCP connection each time. The main disadvantage in using UDP is that there is no guarantee that the data is successfully received by the other end. This risk is mitigated by the client regularly sending Client Hello packets to the server and receiving information about the current state of the other clients in return. The protocol takes this into account when requiring that the expire time be at least 3 update intervals in length - hence three consecutive Client Hello packets (and the corresponding returns) must be lost before either the client or the server will start to remove records from it's list. The server to server protocol should require even less bandwidth between each server pair as the use of a reliable transport mechanism (TCP) means that no updates need to be sent between the servers when the network is stable and in that case only a simple PING/PONG exchange needs to occure every server update interval seconds.