Analysis Of The IRC Server-Server Protocol And Synchronization
--------------------------------------------------------------
by Carlo Wood March 2002
This report is the result of a research on channel synchronization.
During this research net-breaks have not been taken into account.
The research for performed in an attempt to introduce a new message
DESTRUCT, which is needed when we want to keep empty channels alive
for a certain period of time.
Channel modes are assumed to be a direct function of the timestamp:
when the timestamp is preserved then the modes are synchronized too.
In order to achieve this it is necessary to use the BURST message
as synchronization message for the (re)-creation of channels, outside
the normal net.burst.
The following messages are considered:
CREATE : Generated by a server when a previously non-existant
channel is created by a local user.
JOIN : Generated by a server when a local user joins an existant
channel.
PART : Generated by a server when a local user leaves a channel
that it previously joined.
DESTRUCT: Generated by a server when a channel without users is
removed from memory (making the server forget all modes).
BURST : A resynchronization message containing all modes, the
timestamp of the channel and all members on the channel.
Each of messages has a TimeStamp (TS), except PART.
Examples
--------
This report contains several examples, each of those are about a network
with three servers: A, B and C. The map is as follows:
A --- B --- C
The notation in the examples is:
|A:03/01<0027>|B:02/00<0027>|C:02/01<0027>| A<B:{48 PART<27>}; B>C:{48 PART<27>} {51
|JOIN<27>}
Where "A:03/01<0027>" means that server A sees 3 channel members,
1 of which is local. The timestamp of the channel is <0027>.
Right of the three servers (that are seperated with '|') are
the currently queued messages. "A<B:{48 PART<27>}" means that on
the link from B going to A there is queued one message "{48 PART<27>}".
Here, '48' is the member prefix, a unique id for a user, and <27> is the
timestamp (the same as <0027> thus). When there are two or more messages
queued on a link, like in this example on the link from B going to C:
"{48 PART<27>} {51 JOIN<27>}" then the right most message is the FIRST
message that will go out, independant of the direction ('<' or '>').
Next there are two types of events: local events and flushing of queued
messages:
|A:03/01<0027>|B:03/01<0027>|C:02/01<0027>| B>C:{51 JOIN<27>}
PART
|A:03/01<0027>|B:02/00<0027>|C:02/01<0027>| A<B:{48 PART<27>}; B>C:{48 PART<27>} {51
|JOIN<27>}
A<B:{48 PART<27>}
|A:02/01<0027>|B:02/00<0027>|C:02/01<0027>| B>C:{48 PART<27>} {51 JOIN<27>}
This means that first a 'PART' happened on server B
(the PART is written directly below server B) and next the
queued message "{48 PART<27>}" was processed (which is written
directly below the '|' between A and B).
PART
----
CREATE, JOIN and PART use a prefix uniquely identifying the user
joining or leaving; because a server always first generates a
CREATE or JOIN for a user and only then a PART, it is garanteed
to find the user on the channel when a PART is received.
The processing of a PART is therefore very straight forward:
.----------------------------------------------------.
| PART | Remove the given member from the channel. |
`----------------------------------------------------'
In the old protocol the channel was also destructed when a PART
caused a channel to become empty.
CREATE
------
A CREATE message is the equivalent of a JOIN plus a MODE that
gives ops the user, in one message. Because we do not consider
modes in this research it follows that a CREATE is equivalent
with a JOIN except that sometimes a CREATE is translated into
a JOIN (when the timestamp on the message is younger than the
age of the channel).
JOIN
----
A JOIN is only generated (possibly disguised as a CREATE) when
a _local_ user joins a channel. It is always propagated and
never bounced. Its counter part is the PART message that always
travels in the same direction and from the same source (the server
local to the user). Please note that the KICK message was
effectively removed from this picture by the introduction of
'zombies': a KICK doesn't remove a user from a channel, it merely
requests the server local to the user to send a PART. It is this
PART which then really removes the user from the channel.
The only other message that joins users to a channel is the BURST
message. The BURST message should only ever contain nick names
of users that it travels away from; therefore it is impossible
that a JOIN for a certain user reaches a server where that user
is already joined.
The processing of a JOIN is therefore also very straight forward:
.----------------------------------------------------.
| JOIN | Add the given member to the channel. |
`----------------------------------------------------'
For the synchronization of the timestamp the follow rules must
be followed:
.------------------------------------------------------------------.
| 1) Copy the timestamp of the message when it is older than the |
| current timestamp on the channel. |
| 2) Always use the (final) timestamp on the channel for the |
| propagated (or bounced) message(s). |
`------------------------------------------------------------------'
Note that in the case of a CREATE, the CREATE turns into a JOIN
(and a deop MODE is bounced back) when the timestamp on the CREATE
is younger than the current timestamp on the channel.
BURST
-----
A BURST message contains a timestamp that is handled according to
the rules given above. However, a BURST message is not propagated
under certain circumstances (unlike JOIN and PART).
A BURST message is not propagated when the timestamp on the message
is younger than the current timestamp on the channel (It wouldn't
harm when it was though).
The BURST message contains all nicks on the channel. Because now
we use the BURST message outside a normal burst, it is possible
that it follows a JOIN/CREATE and a listed nick is _already_ on
the channel. Therefore it must be carefully checked whether or
not nicks in a BURST are already joined or not, and if so, not
send a JOIN to the channel (again).
DESTRUCT
--------
A DESTRUCT message should cause a channel to be destructed on ALL
servers: if that would fail then there is a desynchronization because
information was lost on some servers, but not on all.
However, sometimes a DESTRUCT message cannot be propagated: when
the channel isn't empty! In that case we need to bounce a fully
synchronizing BURST message back upstream.
A DESTRUCT message must be ignored when the channel it tries to
destruct doesn't exist (which means that it was already destructed
and another DESTRUCT message is travelling in the opposite
direction). The DESTRUCT message can also ignored when timestamp
on the message is younger than the channel, just as with BURST
(and also in this case it wouldn't harm if it was propagated,
but it just isn't necessary).
Finally, a DESTRUCT message that *succeeds* must be propagated
in *all* directions, also the direction it came from. This is
needed to 'wipe out' a "JOIN/PART" combination that might have
crossed the DESTRUCT message. If this wasn't done, it would
become possible that channel would exist on some servers but
not on others (without synchronizing messages inbetween) and
that can again can lead to desychronization.
|A:00/00<0092>|B:00/00<0092>|C:00/00<0092>| State OK
JOIN
|A:01/01<0092>|B:00/00<0092>|C:00/00<0092>| A>B:{214 JOIN<92>}
DESTRUCT
|A:01/01<0092>|B: <none>|C:00/00<0092>| A>B:{214 JOIN<92>}; A<B:{DESTRUCT<92>};
|B>C:{DESTRUCT<92>}
B>C:{DESTRUCT<92>}
|A:01/01<0092>|B: <none>|C: <none>| A>B:{214 JOIN<92>}; A<B:{DESTRUCT<92>}
PART
|A:00/00<0092>|B: <none>|C: <none>| A>B:{214 PART<92>} {214 JOIN<92>};
|A<B:{DESTRUCT<92>}
A>B:{214 JOIN<92>}
|A:00/00<0092>|B:01/00<0092>|C: <none>| A>B:{214 PART<92>}; A<B:{DESTRUCT<92>};
|B>C:{214 JOIN<92>}
A>B:{214 PART<92>}
|A:00/00<0092>|B:00/00<0092>|C: <none>| A<B:{DESTRUCT<92>}; B>C:{214 PART<92>}
|{214 JOIN<92>}
B>C:{214 JOIN<92>}
|A:00/00<0092>|B:00/00<0092>|C:01/00<0092>| A<B:{DESTRUCT<92>}; B>C:{214 PART<92>}
B>C:{214 PART<92>}
|A:00/00<0092>|B:00/00<0092>|C:00/00<0092>| A<B:{DESTRUCT<92>}
A<B:{DESTRUCT<92>}
|A: <none>|B:00/00<0092>|C:00/00<0092>| State of A differs from state of B!
The old protocol
----------------
The old protocol, without the DESTRUCT message, suffered from
easy desychronization, for example:
|A: <none>|B: <none>| State OK
CREATE<17>
|A: <none>|B:01/01<0017>| A<B:{22 CREATE<17>}
CREATE<18>
|A:01/01<0018>|B:01/01<0017>| A>B:{23 CREATE<18>}; A<B:{22 CREATE<17>}
PART
|A:01/01<0018>|B: <none>| A>B:{23 CREATE<18>}; A<B:{22 PART<17>} {22 CREATE<17>}
A<B:{22 CREATE<17>}
|A:02/01<0017>|B: <none>| A>B:{23 CREATE<18>}; A<B:{22 PART<17>}
A>B:{23 CREATE<18>}
|A:02/01<0017>|B:01/00<0018>| A<B:{22 PART<17>}
A<B:{22 PART<17>}
|A:01/01<0017>|B:01/00<0018>| State of A differs from state of B!
Conclusion
----------
With the introduction of a DESTRUCT message it is possible to
completely get rid of TimeStamp desynchronization. However, we
need to allow BURST messages outside the normal burst then and
take care not to send JOIN messages to the users for members
that are already on the channel.
The C++ program that was developed during this research and that was
used to verify all of the above is attached.
--
Carlo Wood <[EMAIL PROTECTED]>
// destruct v1.0
//
// Copyright (C) 2002, by
//
// Carlo Wood, Run on IRC <[EMAIL PROTECTED]>
// RSA-1024 0x624ACAD5 1997-01-26 Sign & Encrypt
// Fingerprint16 = 32 EC A7 B6 AC DB 65 A6 F6 F6 55 DD 1C DC FF 61
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//
#include <deque>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cassert>
#include <set>
#define USEDESTRUCT
enum DirectionType {
up,
down
};
std::ostream& operator<<(std::ostream& os, DirectionType const& type)
{
switch(type)
{
case up:
os << "up";
break;
case down:
os << "down";
break;
}
return os;
}
class Direction {
private:
DirectionType M_direction_type;
public:
Direction(DirectionType d) : M_direction_type(d) { }
Direction other(void) const;
friend bool operator==(Direction const& d, DirectionType t) { return
d.M_direction_type == t; }
friend bool operator==(DirectionType t, Direction const& d) { return
d.M_direction_type == t; }
friend bool operator!=(Direction const& d, DirectionType t) { return
d.M_direction_type != t; }
friend bool operator!=(DirectionType t, Direction const& d) { return
d.M_direction_type != t; }
bool operator==(Direction const& d) const { return M_direction_type ==
d.M_direction_type; }
friend std::ostream& operator<<(std::ostream& os, Direction const& direction);
void reverse_direction(void) { M_direction_type = (M_direction_type == up) ? down
: up; }
};
std::ostream& operator<<(std::ostream& os, Direction const& direction)
{
os << direction.M_direction_type;
return os;
}
Direction Direction::other(void) const
{
return Direction(M_direction_type == up ? down : up);
}
enum MsgType {
create,
join,
part,
burst,
#ifdef USEDESTRUCT
destruct,
#endif
none
};
std::ostream& operator<<(std::ostream& os, MsgType const& type)
{
switch(type)
{
case create:
os << "CREATE";
break;
case join:
os << "JOIN";
break;
case part:
os << "PART";
break;
case burst:
os << "BURST";
break;
#ifdef USEDESTRUCT
case destruct:
os << "DESTRUCT";
break;
#endif
case none:
os << "<none>";
break;
}
return os;
}
class Message {
private:
MsgType M_msgtype;
int M_timestamp;
Direction M_direction;
int M_prefix;
std::set<int> M_member_list;
public:
Message(MsgType type, int prefix, int t, Direction d, std::set<int> member_list)
: M_msgtype(type), M_timestamp(t), M_direction(d), M_prefix(prefix),
M_member_list(member_list)
{ assert( type == burst ); }
Message(MsgType type, int prefix, int t, Direction d)
: M_msgtype(type), M_timestamp(t), M_direction(d), M_prefix(prefix)
{ assert( (prefix == -1 || type == create || type == join || type == part) ); }
Message(MsgType type) : M_msgtype(none), M_timestamp(-1000), M_direction(down) {
assert(type == none); }
MsgType type(void) const { return M_msgtype; }
int timestamp(void) const { return M_timestamp; }
Direction direction(void) const { return M_direction; }
int prefix(void) const { return M_prefix; }
void reverse_direction(void) { M_direction.reverse_direction(); }
void set_timestamp(int timestamp) { M_timestamp = timestamp; }
std::set<int>& member_list(void) { return M_member_list; }
std::set<int> const& member_list(void) const { return M_member_list; }
friend std::ostream& operator<<(std::ostream& os, Message const& msg);
};
std::ostream& operator<<(std::ostream& os, Message const& msg)
{
os << '{';
if (msg.M_prefix != -1)
os << msg.M_prefix << ' ';
os << msg.M_msgtype << '<' << msg.M_timestamp << '>';
if (msg.type() == burst)
{
bool first = true;
for (std::set<int>::const_iterator i(msg.member_list().begin()); i !=
msg.member_list().end(); ++i)
{
if (first)
first = false;
else
os << ',';
os << (*i);
}
}
os << '}';
return os;
}
struct Network;
class Server;
class State {
private:
bool M_exists; // Channel structure exists.
int M_timestamp; // Timestamp.
std::set<int> M_members_list; // Prefixes of the members.
std::set<int> M_local_members_list; // Prefixes of the local members.
public:
State(void) : M_exists(false), M_timestamp(0) { }
Message receive(int link_id, Server& server, Message& msg);
Message generate(MsgType type, Network& network);
bool exists(void) const { return M_exists; }
int timestamp(void) const { return M_timestamp; }
int members(void) const { return M_members_list.size(); }
int local_members(void) const { return M_local_members_list.size(); }
int new_member(Network& network);
int delete_member(void);
void add_members(std::set<int> const& member_list); // Add remote members.
friend bool operator!=(State const& s1, State const& s2);
friend bool operator==(State const& s1, State const& s2);
friend std::ostream& operator<<(std::ostream& os, State const& state);
};
std::ostream& operator<<(std::ostream& os, State const& state)
{
if (state.M_exists)
os << std::setw(2) << state.members() << '/' << std::setw(2) <<
state.local_members() << '<' << std::setw(4) << std::setfill('0') << state.M_timestamp
<< '>';
else
os << " <none>";
return os;
}
class Queue {
private:
std::deque<Message> M_q;
public:
void push(Message const& m);
Message pop(void);
bool empty(void) const { return M_q.empty(); }
friend std::ostream& operator<<(std::ostream& os, Queue const& queue);
int size(void) const { return M_q.size(); }
};
std::ostream& operator<<(std::ostream& os, Queue const& queue)
{
bool first = true;
for (std::deque<Message>::const_iterator i(queue.M_q.begin());
i != queue.M_q.end(); ++i)
{
if (!first)
os << ' ';
else
first = false;
os << (*i);
}
return os;
}
void Queue::push(Message const& m)
{
M_q.push_front(m);
}
Message Queue::pop(void)
{
Message out(M_q.back());
M_q.pop_back();
return out;
}
class Server;
class Link {
private:
Queue M_deque;
Server const& M_from_server;
Server& M_server;
int M_id;
public:
Link(Network& network, Server const& from, Server& server);
bool empty(void) const { return M_deque.empty(); }
bool flush(void);
int id(void) const { return M_id; }
void push(Message const& msg) { M_deque.push(msg); }
std::string const& from(void) const;
std::string const& to(void) const;
friend std::ostream& operator<<(std::ostream& os, Link const& link);
int size(void) const { return M_deque.size(); }
void print_link_on(std::ostream& os) const;
};
class Server {
typedef std::vector<Link*> links_t;
private:
links_t links;
int M_id;
std::string M_name;
public:
State state;
Server(int id) : M_id(id)
{
M_name = "\e[33m";
M_name += 'A' + id;
M_name += "\e[0m";
}
bool generate(MsgType type, Network& network);
void propagate(int from, Message const& msg);
void bounce(int from, Message& msg);
void connect(Server& uplink, Network& network);
std::string const& name(void) const { return M_name; }
};
struct Network {
int now;
int next_link_id;
std::vector<Link*> all_links;
std::vector<Server> all_servers;
int actions;
int events;
int next_member;
Network(void) { }
Network(int n);
void connect(int s1, int s2) { all_servers[s1].connect(all_servers[s2], *this); }
bool generate(MsgType type, int s) { return all_servers[s].generate(type, *this); }
bool shift(int link) { return all_links[link]->flush(); }
int number_of_links(void) const { return all_links.size(); }
int number_of_servers(void) const { return all_servers.size(); }
};
int State::new_member(Network& network)
{
int prefix = network.next_member++;
M_local_members_list.insert(prefix);
return prefix;
}
int State::delete_member(void)
{
assert( !M_local_members_list.empty() );
std::set<int>::iterator iter(M_local_members_list.begin());
int prefix = *iter;
M_local_members_list.erase(iter);
return prefix;
}
Link::Link(Network& network, Server const& from, Server& server)
: M_from_server(from), M_server(server), M_id(network.next_link_id++) { }
bool Server::generate(MsgType type, Network& network)
{
if (type == part && state.local_members() == 0)
return false;
Message result(state.generate(type, network));
if (result.type() == none)
return false;
std::cout << ' ';
for (int i = 0; i < M_id; ++i)
std::cout << " ";
std::cout << type;
if (type == create)
std::cout << "<" << result.timestamp() << ">";
std::cout << '\n';
for (links_t::iterator i(links.begin()); i != links.end(); ++i)
(*i)->push(result);
return true;
}
void Link::print_link_on(std::ostream& os) const
{
if (M_from_server.name() < M_server.name())
os << M_from_server.name() << '>' << M_server.name();
else
os << M_server.name() << '<' << M_from_server.name();
}
std::ostream& operator<<(std::ostream& os, Link const& link)
{
link.print_link_on(os);
os << ':' << link.M_deque;
return os;
}
std::string const& Link::from(void) const
{
return M_from_server.name();
}
std::string const& Link::to(void) const
{
return M_server.name();
}
bool Link::flush(void)
{
if (empty())
return false;
Message what(M_deque.pop());
Message result(M_server.state.receive(M_id, M_server, what));
int indent = (M_id >> 1);
std::cout << " ";
for (int i = 0; i < indent; ++i)
std::cout << " ";
print_link_on(std::cout);
std::cout << ':' << what;
std::cout << '\n';
if (result.type() == none)
return true; // Ignored, but processed.
if (result.direction() == up)
M_server.bounce(M_id, result);
else
M_server.propagate(M_id, result);
return true;
}
void Server::propagate(int from, Message const& msg)
{
for (links_t::iterator i(links.begin()); i != links.end(); ++i)
if ((from & ~1) != ((*i)->id() & ~1))
(*i)->push(msg);
}
void Server::bounce(int from, Message& msg)
{
msg.reverse_direction();
for (links_t::iterator i(links.begin()); i != links.end(); ++i)
if ((from & ~1) == ((*i)->id() & ~1))
(*i)->push(msg);
}
void Server::connect(Server& uplink, Network& network)
{
Link* p1 = new Link(network, *this, uplink);
links.push_back(p1);
network.all_links.push_back(p1);
Link* p2 = new Link(network, uplink, *this);
uplink.links.push_back(p2);
network.all_links.push_back(p2);
}
bool operator!=(State const& s1, State const& s2)
{
#if 0
if (!s1.M_exists && (!s2.M_exists || s2.members() == 0))
return false;
if (!s2.M_exists && (!s1.M_exists || s1.members() == 0))
return false;
#endif
if (s1.M_exists != s2.M_exists)
return true;
return s1.M_exists && (s1.M_timestamp != s2.M_timestamp || s1.M_members_list !=
s2.M_members_list);
}
bool operator==(State const& s1, State const& s2)
{
#if 0
if (!s1.M_exists && (!s2.M_exists || s2.members() == 0))
return true;
if (!s2.M_exists && (!s1.M_exists || s1.members() == 0))
return true;
#endif
if (s1.M_exists != s2.M_exists)
return false;
return !s1.M_exists || (s1.M_timestamp == s2.M_timestamp && s1.M_members_list ==
s2.M_members_list);
}
Network::Network(int n) : now(0), next_link_id(0), actions(0), events(0),
next_member(0)
{
for (int i = 0; i < n; ++i)
all_servers.push_back(Server(i));
}
int random(int max)
{
return (int)((double)max * rand() / (RAND_MAX + 1.0));
}
void State::add_members(std::set<int> const& member_list)
{
for (std::set<int>::const_iterator iter(member_list.begin()); iter !=
member_list.end(); ++iter)
{
std::set<int>::const_iterator li(M_local_members_list.find(*iter));
assert( li == M_local_members_list.end() ); // A BURST msg should never contain a
local client.
bool new_member = M_members_list.insert(*iter).second;
}
}
Message State::generate(MsgType type, Network& network)
{
int prefix = -1;
switch (type)
{
case create:
// Disallow CREATE event on server where the channel already exist.
if (M_exists)
return Message(none);
// Channel now exist.
M_exists = true;
// Use a new, unique creation time.
M_timestamp = ++network.now;
// Use a new, unique, prefix for the new member.
prefix = new_member(network);
// Add that member to this channel.
M_members_list.insert(prefix);
assert( members() == 1);
break;
#ifdef USEDESTRUCT
case destruct:
// Disallow a DESTRUCT event when the channel doesn't exist or isn't empty.
if (!M_exists || members() > 0)
return Message(none);
// Destruct the channel.
M_exists = false;
break;
#endif
case join:
// Disallow JOIN event on server that doesn't already have the channel (should
be a CREATE).
// Also disallow a JOIN event when there is already a local user on the channel:
it makes
// no sense to test that.
if (!M_exists || local_members() > 0)
return Message(none);
// Use a new, unique, prefix for the new member.
prefix = new_member(network);
// Add that member to this channel.
M_members_list.insert(prefix);
break;
case part:
{
// Disallow a PART event for a channel that doesn't exist or doesn't have any
local members.
if (!M_exists || local_members() == 0)
return Message(none);
assert( members() >= 0 );
// Get the prefix of a local user.
prefix = delete_member();
std::set<int>::iterator iter(M_members_list.find(prefix));
assert( iter != M_members_list.end() );
// Remove that member from this channel.
M_members_list.erase(iter);
#ifndef USEDESTRUCT
// Destruct the channel when it becomes empty.
if (members() == 0)
M_exists = false;
#endif
break;
}
default:
abort();
}
// Propagate message 'downstream' (to all connected servers) with current timestamp.
return Message(type, prefix, M_timestamp, down);
}
Message State::receive(int link_id, Server& server, Message& msg)
{
switch(msg.type())
{
case none:
abort();
case create:
case join:
{
// Always add the new member to the channel.
bool new_member = M_members_list.insert(msg.prefix()).second;
assert( new_member ); // It *should* always be a NEW member...
// Channel doesn't exist?
if (!M_exists)
{
// Create the channel.
M_exists = true;
// Set the timestamp to the timestamp in the message.
M_timestamp = msg.timestamp();
// Number of members on the channel is now 1.
assert( members() == 1);
break;
}
if (msg.timestamp() > M_timestamp)
{
// Timestamp in message is younger than of channel.
if (msg.type() == create)
{
// Propagate a JOIN with current timestamp of channel.
return Message(join, msg.prefix(), M_timestamp, down);
}
// Use current timestamp in propagated message.
msg.set_timestamp(M_timestamp);
break;
}
else if (msg.timestamp() < M_timestamp)
{
// Timestamp in message is older than of channel.
// Use timestamp of message.
M_timestamp = msg.timestamp();
}
break;
}
case part:
{
// The channel must always exist.
assert( M_exists );
// Try to remove the user from the channel.
std::set<int>::iterator iter(M_members_list.find(msg.prefix()));
// Must always be found.
assert( iter != M_members_list.end() );
// Remove member from the channel.
M_members_list.erase(iter);
#ifndef USEDESTRUCT
// Destruct the channel when it becomes empty.
if (members() == 0)
M_exists = false;
#endif
break;
}
#ifdef USEDESTRUCT
case destruct:
// Ignore DESTRUCT messages for non-existing channels.
if (!M_exists)
return Message(none);
if (msg.timestamp() > M_timestamp)
{
#if 0
msg.set_timestamp(M_timestamp);
#else
// Ignore DESTRUCT when the timestamp of the message is younger than the
channel creation time.
return Message(none);
#endif
}
if (members() == 0)
{
#if 1
// Bounce (and propagated) a DESTRUCT that was successful.
Message extra_msg(destruct, -1, M_timestamp, up);
server.bounce(link_id, extra_msg);
#endif
// Remove the channel only when it is empty.
M_exists = false;
}
else
if (members() > 0)
{
// When the channel is not empty then bounce a BURST message upstream.
return Message(burst, -1, M_timestamp, up, M_members_list);
}
break;
#endif
case burst:
if (!M_exists)
{
// If the channel didn't exist, create it, set the creation time and add the
given members.
M_exists = true;
M_timestamp = msg.timestamp();
assert( members() == 0 );
add_members(msg.member_list());
break;
}
if (msg.timestamp() > M_timestamp)
{
#if 0
msg.set_timestamp(M_timestamp);
#else
// Ignore a BURST with a timestamp that is younger than the current
creationtime of the channel.
return Message(none);
#endif
}
// Add the new members.
add_members(msg.member_list());
if (msg.timestamp() < M_timestamp)
{
// If the timestamp in the message is older than of the current channel,
// set the creationtime to it.
M_timestamp = msg.timestamp();
}
break;
}
// Propagate message, always use the current creationtime of the channel as
timestamp.
// (except when the channel doesn't exist anymore or for a PART message, which
doesn't
// really HAVE a timestamp.
assert( msg.type() == part || !M_exists || msg.timestamp() == M_timestamp );
return msg;
}
enum step_nt {
event,
shift,
done
};
struct Step {
step_nt what;
union {
int server;
int link;
};
MsgType type;
};
#define RANDOM
int main(void)
{
Network network(7);
srand(0);
// Connect servers.
network.connect(0, 1);
network.connect(1, 2);
network.connect(2, 3);
network.connect(3, 4);
network.connect(2, 5);
network.connect(5, 6);
Step const step[] = {
#ifdef USEDESTRUCT
{ event, 0, create },
{ event, 0, part },
{ shift, 0 },
{ shift, 0 },
{ event, 0, destruct },
{ event, 1, join },
{ event, 1, part },
{ shift, 0 },
{ shift, 1 },
{ shift, 1 },
{ shift, 1 },
{ shift, 0 },
#endif
{ done }
};
Network empty_network = network;
int min_actions = INT_MAX;
int target_actions = 0;
int min_events = INT_MAX;
int target_events = 0;
bool better = false;
int k = 0;
for (int loop = 0; loop < 1000000; ++loop)
{
int queued_msgs = 0;
for (std::vector<Link*>::iterator i(network.all_links.begin()); i !=
network.all_links.end(); ++i)
queued_msgs += (*i)->size();
// Print state of servers and queues.
std::cout << '|';
for (int i = 0; i < network.number_of_servers(); ++i)
std::cout << network.all_servers[i].name() << ':' <<
network.all_servers[i].state << '|';
if (queued_msgs)
{
// Print state of links.
bool first = true;
for (std::vector<Link*>::iterator i(network.all_links.begin()); i !=
network.all_links.end(); ++i)
{
if ((*i)->empty())
continue;
if (first)
first = false;
else
std::cout << ';';
std::cout << ' ' << *(*i);
}
}
else
{
// Check if all states are equal.
for (int i = 1; i < network.number_of_servers(); ++i)
if (network.all_servers[0].state != network.all_servers[i].state)
{
if (network.all_servers[1].state == network.all_servers[i].state)
std::cout << " State of " << network.all_servers[0].name() << " differs
from state of " << network.all_servers[1].name() << "!";
else
std::cout << " State of " << network.all_servers[i].name() << " differs
from state of " << network.all_servers[0].name() << "!";
std::cout << '\n';
if (network.actions < min_actions)
{
min_actions = network.actions;
better = true;
}
if (network.events < min_events)
{
min_events = network.events;
min_actions = network.actions;
better = true;
}
if (loop > 10000 * min_actions)
{
target_actions = min_actions;
target_events = min_events;
}
std::cout << "\e[31mCur actions " << network.actions << "; Min actions: " <<
min_actions << "\e[0m\n";
std::cout << "\e[31mCur events " << network.events << "; Min events : " <<
min_events << "\e[0m\n";
if (network.actions > target_actions || network.events > target_events)
{
network = empty_network;
if (better)
{
std::cin.get();
better = false;
}
continue;
}
abort();
}
std::cout << " \e[31mState OK\e[0m";
network.actions = 0;
network.events = 0;
}
std::cout << '\n';
// Now lets do something
#ifndef RANDOM
if (step[k].what == done)
break;
if (step[k].what == event)
network.generate(step[k].type, step[k].server);
else
network.shift(step[k].link);
++k;
#else // random
if ((network.events < min_events
&& queued_msgs < 4 * network.number_of_servers()
&& random(2 * network.number_of_servers()) == 0)
|| queued_msgs == 0)
{
// Generate a new spontaneous message.
#ifdef USEDESTRUCT
int const per[4] = { 30, 10, 30, 30 }; // Percentages chance for msg PART,
JOIN, CREATE and DESTRUCT.
#else
int const per[3] = { 43, 14, 43 }; // Percentages chance for msg PART,
JOIN and CREATE.
#endif
bool success;
do
{
MsgType mt;
int what = random(100);
if (what < per[0])
mt = part;
else if (what < per[1] + per[0])
mt = join;
else if (what < per[2] + per[1] + per[0])
mt = create;
#ifdef USEDESTRUCT
else
mt = destruct;
#endif
int server = random(network.number_of_servers());
success = network.generate(mt, server);
}
while(!success);
++network.events;
}
else
{
// Process a queued msg.
bool success;
do
{
int link = random(network.number_of_links());
success = network.shift(link);
}
while(!success);
}
#endif // RANDOM
++network.actions;
}
return 0;
}
