Traditional voice chat topology
Some say a picture is worth a thousand words. Let's test that.
For comparison, a dedicated T1 line, at US$2500/month, could support fewer than 100 concurrent voice chatters using GSM compression. Thus, this model is only financially practical on a mass scale if users pay some fee - probably about $5/month each. This model does not work for freeware.
If all voice chat users in a group have at least a 33.6 connection, but no ADSL, Cable,
ISDN, or other high bandwidth connection, then
this model works (in theory) for up to 5 users. However, if one or more participants
have a fast Internet connection, maximum conference size increases dramatically. Cable modem and ADSL are rapidly growing in popularity. There are currently about 200,000 cable modem users in the US, and that number is expected to top 1 million in 1999. Warning: many people with a 33.6 or 56K modem actually get a much slower connection, say about 25K, due to poor copper wire, poor ISP Quality Of Service, or both. Maximum group size depends mostly on the fraction of users with high bandwidth connections.
The group voice chat session functions as a "collective". The "collective" eats
each new client that joins, with each member contributing spare resources (primarily bandwidth).
EACH client in the "collective" act as a reflector, and the reflection topology
alters dynamically each time group membership changes.
Each member of the colective "donates" much of its available bandwidth towards
reflecting the current speaker's voice stream to other collective
members. This means there must be a complex and constantly shifting
reflection topology. Coordinating this reflection topology, and
moderating who can speak, is the hardest part of developing this software.
It is a complicated system, but seems workable.If "collective chat" is turned on, SF would listen to port 2081 (or some other port that no other major application uses) and would contact (via TCP, not UDP) port 2081 on every machine it interacted with. If they are both in collective chat mode they would merge and "enter the collective". One very nice feature of this approach is its great simplicity from a user perspective. Simply call ANYONE who is already in the group, and you automatically join the group.
We find that one "relay" yields good sound quality, two relays show some
degradation, and three or more relays are usually unworkable. We've
tested this under several permutations of the real Internet. It also
makes sense, as one would expect signal degradation to be
1 relay: (1-s)
2 relays: (1-s)*(1-s)
3 relays: (1-s)*(1-s)*(1-s)
etc. Where s is fractional loss for one hop. Thus, signal quality degrades
exponentially with more relays.
In general, a 33.6 modem can JUST BARELY handle one incoming and one
outgoing GSM stream, if it has VERY GOOD copper, and if there is NO
OTHER network activity. Since many supposed 33.6 connections are
actually slower, break up occurs for long speeches, but short bursts
usually work fine, since they do not overflow the outgoing buffer.
Inceasing transmission buffer size might be wise ...
The "collective" must have one supreme master that determines and
distributes the overall relay structure (possibly delegating some tasks
to "centurions" in the case of a very large collective). The master
also governs who can talk, via a speech token. Note that the USER of
the master CPU has no special control privileges, and probably will not
even know that he/she has the master client. The supreme master is
chosen for its high CPU speed and performace, plus low average network
latency. Users can say "Make my client a slave whenever possible" to
reduce system load. I.e. Someone with a fast machine might want to
reserve their computer's resources for other purposes.Each client starts out as a master. Each client also stores a performance benchmark, an estimate of its available bandwidth, and the time it last started. Anytime two or more clients "meet" they exchange data, the fastest becomes master (breaking ties with start time), and the rest become slaves. Each slave client checks in with the master every xx seconds, where xx increases as group size increases. Slaves take relay orders from the master, and only speak when they have the speech token. If the master ever disappears, all "stranded" slaves check in one after another with the other slaves, in order of seniority by speed. The senior slave becomes the new master.
Thus, this voice chat collective would be a benificent dictatorial meritocracy with socialist leanings.
Once a client enters the collective all other group
members know about it, and as long as at least two collective members
remain online they will stay in verbal contact. It seems this approach
would tie in especially well with ICQ, if only it were fully cross
platform. ICQ was recently sold to (boo! hiss!) AOL for $300 million,
but AOL has promised not to mess it up. ICQ has some 15 million users,
is growing at about a million users a month, and works on all
platforms. If we actually create this system, and if it works as I
think it will, I suspect it could become very popular.
Initial reflection topology is based only on bandwidth available to each client. Each
client does a gross bandwidth estimate by measuring download time for an
FTP download of a known file. The master determines how many GSM relays
each client is capable of, then assigns a relay matrix for each speaker. The master distributes the relay
matrix to all slaves. Each client has the current relay matrix, and thus
need only know who is speaking to know whom to relay to.e.g. Imagine a group of clients, A through H. Clients B and F both have more bandwidth than the others, with B having the most. If client A is speaking and has a only 33.6 connection, A trasmits to B and F. Client B relays to C, D, and E, and client F relays to G and H. If client B is speaking, we have a different relay pattern ...
Here follow a few features it should contain, in some detail. Required
features are in red, and optional ones to be
added later in Lime Green1. Start my own room, and invite others in. Seperate rooms remain in the same "collective", but are on a seperate voice stream relay grid. Each "room" is governed by it's own centurion, which handles token passing, etc, but is answerable to the supreme master. Rooms can be either "public", "private" (you must know the room name,and the room is not visible), or "private and password protected".
2. The first thing a master does is choose several "heirs". All clients might be heirs. Only an heir can be promoted to master. Designated heirs remain synchronized to their master's operational parameters. Thus, they are ready to take over at a any time, minimizing recovery time if the master goes offline.
3. Any time their are many lost udp packets do a traceroute to all
other members and re-arrange the relay order to route around the
trouble. Solving this perfectly is nearly impossible, but I already
have a simple algorhythm that gives a decent solution. This feature
gets clients that are topologically "close" to each other to relay to
each other preferentially. It is described in more detail in the next
item.
4. Here's how to improve network relay topology with traceroute data. This should substantially improve the topology over the current network-topology-blind one I have working. I'd like to eventually add this feature to collective mode. This feature is a relay topology enhancer, and only kicks in after a functional network topology already exists.
Each member does a traceroute to every member other of the collective
and orders the others from worst to best quality. Each member then
calculates its mean latency to all other memebers and announces its mean
latency to the master, along with its latency to all other colective
members. The master then calcualtes relays, staying within the
bandwidth limitations of the collective, starting with the WORST
latency. Thus, the worst network location gets the best treatment.
Once this "refined" network is established, each machine monitors its quality-of-service (QOS) in the form of lost and delayed packets. Each machine periodically reports on its QOS to the master. The master picks the machine with the worst QOS, and tries alternate routes to and from it. Once it finds the best route for that client, it then moves to the the next worst QOS, and tries to improve it.
Properly implemented (and there's the catch!) this approach should gradually improve the network topology, by best-guess trial and error, until it eventually reaches the near ideal topology. Also, it will adjust to changing network conditions. It will still be vulnerableto RAPID and FLUCTUATING changes in network conditions, as occurs frequently on the real Internet.
5. The system I have described is very vulnerable to denial of service
attacks. One could largely protect against this by having each machine
generate a public/private key pair via the encryption feature that is
already included in SF. This could uniquely identify each client. This
is getting pretty far fetched, but I try to think ahead. All the large
group chat sessions I've done (both voice and text) have had at least
one jerk who wanted to annoy the rest of the group. Spoofing the
master/slave structure would be an easy way to kill the collective.
6. There must be an "ignore" feature. If you are ignoring someone, you will not hear what they say, and the master will not to use your client to relay their voice stream. Thus, if many people in the collective ignore someone, it starves that person of bandwidth and effectively silences them. But only if the majority of the group ignores them.
7. Be network friendly. Be nice to ISPs and network carriers. Each client uses this creedo: "I will use all or most of my available bandwidth to help other members of the collective communicate, but only until I degrade my host network no more than x%", where x is probably 5, 10 or 20 percent.
FYI: network latency will only increase due to relatively heavy network load by a single user, and only if that user single consumes a substantial fraction of the network resources. Only a fat end user network connection, such as cable modem or T1, has the capacity to degrade the typical network. Since these fast connections often share inadequate total bandwidth resources, it is critical that our clients not be bandwidth hogs.
The only complication here is that, once a possible network clog is
created, that clog must be verified by observing network latency while
increasing and lowering bandwidth demands over time.
In general, clients with a lot of bandwidth will try to reserve as much for themselves as they can, while still getting the job done. The total bandwidth load should be shared proportionally between high-bandwidth clients.
8. As the proportion of high-bandwidth clients increases, the maximum audience size increases very rapidly. If one allows two hops, uses GSM, and if even 10% of users have dual ISDN connection or faster (at only 128k dual ISDN is slow compared to cable modem and ADSL), the maximum group size very quickly becomes HUGE. I calculate 27 users for the above situation.
A single cable modem or ADSL modem might theoretically relay 50 or more GSM streams. The real number is probably much smaller, but still greater than 10.
This leads to the weird situation that by 2002 or so moderated voice
chat sessions with tens of thousands of participants become possible -
and the network load is evenly distributed. I don't know that they'll
be WANTED, but they'll be possible. I could see certain political
rallys happening this way, for example.
9. There must be a unique collective ID number - I suggest the time stamp for when it begins. A collective can be "non-mergable", which means it should never merge with another collective above a certain size. Thus, it would be impossible for a prankster to merge the Republican Wives convention with Betty's After 8 Lounge Lizards.
10. There would need to be a very extensive token monitoring system for
large groups. Even small groups need a way to pick the conference
moderator. I propose that each collective must agree on an IP for the
moderator. The default moderator is the master, and a client can say "I
remain the moderator, even if there are faster machines out there",
which the conference starter can do. VoxChat had a very nice token
moderation system which was also not terribly complicated. I have
already created a functional token moderation system - it was not too
hard. I have NOT added the bells and whistles that make it truly user
friendly. I am intimately familiar with VoxChat's moderation system,
though, and that one worked very well.
11. If there is not enough bandwidth to get the message out to everyone, automatically switch to LPC10. The simplest approach is to have EVERYONE switch to LPC10. The MUCH more complicated approach is to have some clients act as a "gateway", receiving in GSM, decoding the GSM (with jitter), then re-sending the stream compressed in LPC-10, possibly redundently. I believe this feature, though appearing simple on the surface, is actually extremely difficult.
12. Related to 11. above, if some clients have poor network
connectivity (AOL users!) and can not receive a GSM stream, then have
one other client act as a "gateway". We have found that a 4x redundency
LPC-10 voice stream with 3 second jitter is intelligble under the worst
network conditions we could find. The "gateway" would "translate" from
GSM to 4x LPC-10 for this disadvantaged user. The disadvantaged user
would ALSO receive some notice that his/her Internet connection really
sucks, and suggest upgrading to better service provider.
13. This voice chat feature should tie in nicely with ICQ's popular text chat client. ICQ now has far and away the most popular text chat client - the chat client is ICQ's most popular feature. Specifically, one should be able to syncronize member ship in voice chat and text chat gatherings. I have done a LOT of voice chat (I ran an online interactive storytelling company for 18 months), and we found from experience that concurrent voice chat and text chat allows for multiple levels of communication, and that this mix works really well.
14. If a non-colective member contacts a collective slave, the slave
refers the new member to the collective master, or its local centurion.
15. If a new member has the highest CPU rating, and is thus qualified to be the new master, the tradeoff is "gracefull", and only occurs if the current master has performance issues. Since typical CPU speed is now very fast compared to what SF needs for GSM compression and decompression, I doubt CPU will be a major factor. The master should actually have a combination of high CPU and good bandwidth, if possible, since the master will have much heavier overhead bandwidth than the typical slave.
16. Send "keep alive" TCP packets from the master to each slave on a regular basis. At least every minute, unless group size is very large. Large group size will require intermediary centurions to avoid clogging the master with keep alive packets. This is because of the relative inefficiency of TCP/IP message layering - there's lots of necesary garbage in a simple "I am alive" packet.
17. Slaves must be smart enough to detect that a master has died, and be able to immediately agree on a new master. The newly selected master must then take over master duties immediately.
That's all I can think of at the moment. While I describe a large and complex project, it is not nearly as complicated as building speakfreely in the first place probably was. I am very interested in what the rest of the Speakfree community, especially other developers, think of this approach.
Thanks for taking the time to read this.
Regards,
Bruce Stephenson
ICQ 118802