Log in

No account? Create an account
16 February 2005 @ 07:26 pm
IRC network design thoughts  
Since IRC was first invented, the standard network topology for it has been a rooted tree. The advantage of this is its simplicity: it's easy to map,  it's easy to configure, and if a server receives a message from one connection and sends it only to each other connection, then messages can never be duplicated. The downside, as everyone who has spent significant time on IRC knows, is its fragility: if a single connection goes down, the network is split into two, and there is no way for messages on one half of the split to reach servers and clients on the other; if a hub goes down, the split can be even worse. This type of network gets more unstable the more layers of hubs you add to it (the longer a path between servers, the more likely the path will be broken, because it is dependent on more connections, all of which are capable of breaking), and since bandwidth is limited, larger networks demand more layers of hubs. A star topology (every leaf connected to a single hub) isn't scalable, and furthermore the hub itself becomes a major point of failure (if it goes down, every leaf becomes a stand-along server unable to communicate with the others).

One solution to this is to move from a acyclic tree topology to a less strict connected-graph topology that allows cycles. A naïve solution is to make every server connect to every other server, but this just extends the bandwidth problems of a star topology to every server. A more realistic solution would be a topology in which there are at least two internally disjoint paths between any two servers: in this case, at least two connections would have to break for two servers to lose contact with each other. The problems with generalized graph topologies are increased overhead (both bandwidth and processor), and more message complexity (each message would need some sort of identifier, so a server can tell if it has already received a copy).

However, there's another way: multicasting. Traditional IRC server-to-server communication (and, in fact, most Internet protocols) use unicasting (in particular TCP/IP,which maintains connections and handles lost packets), which is communication between two peers. It's one-to-one. Multicasting is one-to-many or many-to-many: peers register with their local network as listeners to a shared multicast IP address, and any packet sent to that address is received by all listeners. The problem with multicasting has been that it has no concept of connections like TCP/IP does—lost packets vanish into the ether and listeners have no way of detecting that a packet has been lost, making it useful for applications where some packet loss isn't a big deal (like audio and video, where a stream loses some quality if a few packets disappear, but remains intelligible). However, more recently reliable multicasting protocols have been developed. These build on top of multicasting by implementing ways of identifying lost packets and requesting that they be resent. For example, one tactic is for a server to number each packet it sends sequentially, so if a listener receives packets #12 and #14, it knows that it has missed #13 and can send a "noack" (negative acknowledgement) requesting that #13 be resent.

Basing server-to-server communications on reliable multicasting would allow the topology to be a hypergraph, in which each "edge" can connect more than two servers. On a network like this, all servers could be "leaf servers" sending and listening to a single multicast IP. In effect, the Internet itself would be acting as a "hub", without the bandwith problems a single hub for several leaves would have. With a sufficiently sophisticated reliable multicasting protocol, increasing the number of servers would actually increase the robustness of the network (e.g. in the noack-based protocol, any server that has received a packet could respond to requests for it, not just the originating server).

The main disadvantages with the multicasting solution are unfamiliarity (most network programmers are used to TCP/IP and UDP/IP, but multicasting is new and rare) and obtaining a multicast IP (I don't know how you'd go about getting a transient multicast IP, although I know you can). Another problem is security: there is no way of controlling who is allowed to listen to or send to a multicast IP the way you can allow or disallow connections to a hub you control. A snooper could conceivably register himself as a listener at the multicast address and packet-sniff from nearly anywhere on the 'Net. Also, an attacker could send spoofed packets to the multicast address and perform commands he shouldn't be allowed to (e.g. oper commands). However, implementing some simple encryption (we're not talking SSL or PGP here—more like XORing packets with a shared private key) and authentication, rather than sending everything in the clear, would remove that problem.
Current Mood: geekygeeky
dacut on February 17th, 2005 02:45 pm (UTC)
I've wondered why they didn't just make a ring topology with very simple rules:
1. If I'm originating a packet, send it to both of my neighbors.
2. If I receive a packet, check it's ID against the last N IDs I've seen. If I've already seen it, discard it. Otherwise, record the ID and forward it down the ring.

I'll admit to being fearful of multicasting. We barely grok most of the security implications of TCP/IP; I wouldn't know where to begin with multicasting. What works well behind a firewall can break down on the wild, wild Intarweb.
Vorn the Unspeakableunspeakablevorn on February 19th, 2005 04:59 am (UTC)
Ring topology has the problem of "how many IDs do I keep?" -- if you keep ids based on time you double up messages with lag, and if you keep ids based on a count you double up messages with heavy traffic but low lag.

dacut on February 19th, 2005 05:31 am (UTC)
Well, I wouldn't do it based on time, IP routing performance being as unpredictable as it is. You'd spend all your time tuning the thing...

Assuming that all packets from a given server along a given path experience the same lag, keeping a per-server queue would suffice. This, of course, becomes prohibitive as the number of servers increases.

If you know the size of the ring and are willing to assume that the performance is symmetric (heh heh), each server could just put a TTL on the packet.
Vorn the Unspeakableunspeakablevorn on February 19th, 2005 05:35 am (UTC)
And then there's the other problem: How exactly do you add new objects to the ring without making it go blee?