Guidelines of the e-CHIMP protocol
----------------------------------
This is the basic outline of the e-CHIMP protocol that need to be
described and elaborated in the final version of the RFC. As you
read this outline, you should keep in mind that an actual deployable
protocol may need to be more robust (and hence more complex) than
what is described here. However, for ease of implementation, we
have made some assumptions and simplifications so that you can
implement these features into a working piece of software.
Entities :
----------
There are three main entities : Servers (S), Clients (C) and
Users (U). Additionally, for simplicity of design, we require a
new enitity called the e-CHIMP Designated Coordinator (D).
There is only one Designated Coordinator is resposnible for different
management functionality of the entire e-CHIMP network.
The Designated Coordinator is like a e-CHIMP client. It attaches to only one server. However, no users can attach to Designated Coordinator. The Designated Coordinator is assigned the address 0, and so the clients and the servers will have to route their packets towards the address 0 entity to reach the designated server. It can be assumed for the implementation, that the Designated Coordinator will always be available.
Connections and their management :
----------------------------------
There will be four different physical connections that the protocol
needs to address. They are :
User - Client : TCP
Client - Server : UDP
Server - Server : UDP
Server - Designated Coordinator : UDP
The peer members of the each of these connections need to have some kind of heart-beat or equivalent mechanisms to detect that the connection is active.
Group Structure :
-----------------
A group is a set of users that want to communicate on a specified
topic. It is equivalent to a channel of an IRC. When a user intends
to join a group, it effectively requires that the client it is
connected to join that group.
In this section, we look at a group as a set of clients (derived from
a set of users).
Each group has a `group leader' -- which is one of the clients that
is part of the group. The group leader maintains information about all
the members of the group, and disseminates this to other new joining
members.
The group leader will send periodic heart-beat messages to all members
of the group to announce its presence.
When a new member (client) wants to join the group, it first finds out who the group leader is (this it does from the Designated Coordinator, as described later). It then informs the group leader its intent to join. The group leader will inform this member about all the other members of the group, as well as inform all the other members about this new member. These interactions must be done reliably.
When a member leaves the group, it would try to inform the group leader if possible. This message need not be reliable, and also it is possible that no message is sent, e.g. if the member fails.
The group leader informs all group membership changes to the members. If at any time, a group leader does not get an ack from a member after repeated attempts at distributing a group change information, it concludes that the member is lost and would need to inform all the other members of the group.
Data exchanges :
----------------
All data exchange must be reliable. The user sends the data over to
the clients using TCP. The clients are responsible for distributing
the data reliably to the destination client(s).
There are two kinds of data messages :
- One to one or private messages
- One to many or group messages
For private messages, the destination client will send an ack to the source client indicating proper receipt of the message.
For group messages, one such ack is expected from each of the destination clients. The message is sent as a replicated set of unicast messages originating at the source client. Retransmissions should be made directed to each of the destination clients that did not ack.
Since each client is informed of all the other members of a group, by the group leader, it knows exactly which clients to send the messages. However, it is possible that some of the destination clients may have silently left the group without being able to inform the group leader. In this case, the message to that client will not elicit acks. In such a case, this client is expected to report to the group leader (via reliable mechanism), that this specific destination client has failed. The group leader will test the existence of this client, itself before it concludes that the destination client is lost, and report it to all the remaining group members.
Group leader management :
-------------------------
It is also possible that a group leader fails, in which case the group
would be temporarily without a group leader. In this case, all the
members will realize that the group leader is gone, since the heart-beats
from the group leader will stop. In this case, all members will initiate
the process of choosing a new group leader. Each member, C, will use a random
timer to send a reliable message to the Designated Coordinator. The
message would indicate C's knowledge as to who the current group leader (CGL),
is (i.e. would be the one that just went away) and requesting
the Designated Coordinator to install itself (C) as the new group leader.
If CGL indicated in the message from C, is the same as the Designated
Coordinator's knowledge of the group's leader, then Designated Coordinator,
would install C as the new leader for the group. This information is
stored by the Designated Coordinator in its permanent storage. If on
the other hand, CGL does not match with Designated Coordinator's
knowledge of the group leader, then C is refused, and is informed as
to who the group leader is (ActGL). In this case, C will then try
to join this same group by sending a reliable message to ActGL (it is
like C is joining the group afresh).
Names : nick names and group names :
------------------------------------
To ensure that the nick names and the group names are globally unique,
all assigned nick names and group names are stored at the Designated
Coordinator. Each client checks with the Designated Coordinator the
availability of a name before allowing its use. The first client to
claim a name is given the name and the Designated Coordinator retains
a copy of the name to check against duplication.
Designated Coordinator :
------------------------
The Designated Coordinator is essentially a database (but you do
not have to implement all the complexity of a database, any simple
structured file will serve the purpose). It stores three things :
- List of all alloted nick names
- List of all group names
- For each group alloted, the id of the client which serves as the
leader for that group.
The name space management should be simple to see how to implement.
When a new group is created, typically a client will report the new group creation, and by default would be made the leader of that group. When any member (another client) wants to join the group, it asks the Deisignated Coordinator the address of the group leader (as described in the group structure section).
Reliability of messages :
-------------------------
All messages (except the periodic heart-beats) need to be reliable.
This includes both private and group data messages, as well as most
administrative messages.
For data messages TCP will provide reliability for only the first
and the last hops (ie. from user to client and client to user).
Functionality needed :
----------------------
User <-> Client :
- Nick : ask for a nick name as specified
- Join group : Join a named group
- Leave group : Leave a named group
- SendData User/Group : Send a message to a single user or a group
- Query groups : Find out what all groups are there in the e-CHIMP
- Query members : Find out all the members in a group
- Query user : Check if the user is present in the network
- Query all : Find out all the members in the network
Client <-> Server :
- Attach : Client to attach to a server
- Detach
- SendData : Send data to server for Xmission to other clients
and/or the Designated Coordinator
Server <-> Server :
- Update : Routing updates
- SendData : Forward client data
Designated Coordinator <-> Client :
- Query name/group leader : Client query to check if a name is present,
or what the leader of a specified group is
- Update name/group leader : Client can add a name to the Designated
Coordinator's list, or can alter the identity of the group leader
as would be needed for group leader management. This might fail
at the Designated Coordinator (if the name already exists etc).
The Update group leader can also be treated as a Test and Set operation.
Basically, if the client's knowledge of the group leader matches the
group leader as known to the Designated Coordinator, appropriate
change is made (and no change is made otherwise). Refer to the section
on the Group leader management.
Client <-> Client :
- Join group : Send by a member to the group leader
- Leave group
- Update group membership : Group leader to other group members
Additionally there will be different heart-beat messages as required by the protocol description. The messages described here are only the basic message functionality, each message might be expanded to multiple messages, i.e. the basic message, an acceptance ack, a rejection ack, etc. Some more messaging functionality might be required too.
==========================================================================
Each project team is reponsible for completely specifying a set of messages as defined below. For each of the messages, the description should say, when the message is sent, what the possible responses are what actions need to be taken and such related details.
The components are as follows :
-------------------------------
[Task 1]
- Group structure maintainence : Client to client messages that
advertise group membership changes (from the leader to all other
members). Group leader heart-beats. The user Join/Leave group
should be handled here.
[Task 2]
- Group leader maintainence : Client and Designated Coordinator
interactions to create a new group leader. This also includes the
setting up of a new group (and the initial group leader). This
component will interface with the Group structure maintainence
when a critical number of heart-beats have been missed by a member
from a group leader, and also if a Leave group is done by a client
which is a group leader.
[Task 3]
- User queries and related interface functions : All the user queries as
outlined, need to be converted to different appropriate messages
and sent to the clients. All responses need to be handled appropriately
(eg. when a nickname is to be set, it should send a message to the client,
await the response, try a new nickname if one could not be allocated).
You should also specify the messages that need to sent from the clients
to the Designated Coordinator as appropriate. All the functionality
between the user and client as described before needs to be specified
here, except for the Join/Leave groups and the SendMsg functions.
You should also specify the valid nick name and group name strings that
are allowed by the system.
Also the user interface (that can be typed at the terminal) needs
to be specified here.
[Task 4]
- User messaging system : How the data is actually exchanged should
be specified here. The reliability mechanism, how the clients buffer
the data till it is acknowledged. This include both private and group
messages.
[Task 5]
- Designated Coordinator Management : How the Designated Coordinator
should be internally managing the name spaces, and the group leader
allotment.
[Task 6]
- Server Routing Network Management : Regular DV and update mechanisms.
Note : Since different groups will be responsible for different parts of the document, it is important that all groups mutually interact to discuss that they are not dealing with overlapping portions of the protocol, and that no required functionality is missed.
All the messages that are defined by the groups need to have an uniform message format, since clearly you need to interoperate. Hence, here is the basic message format to which you need to adhere to :
Version string : 4 bits
Msg Type : 12 bits
Src Id : 8 bits
Dst Id : 8 bits
The version string for this project is : 0110
You can allocate arbitrary message types (you have 12 bits, hence upto 4K different messages, which will be sufficient !). Each message will have a Source Id and a Destination Id, which are both 8 bits. You may choose to define a bit string 11111111 to indicate broadcast to all, as might be required by your protocol specifications. You may choose to use or not use the Destination Id field depending on the message type.
The Src and Dst Id may be interpreted differently when used between different entities, e.g. between Client and the User it may be the client address and the user address (note this is a separate address space than the IP address). It is upto you how these fields are interpreted.
Config file :
-------------
A configuration file (similar to the Distance Vector project) will
be used to intialize the server backbone. The clients and the users
will use command line arguments to connect to their respective peers.