--- date: 2021-04-02 title: "How does Ouroboros do anycast and multicast?" linkTitle: "Does Ouroboros do (any,multi)-cast?" description: > Searching for the answer to the question: why do packet networks work? author: Dimitri Staessens --- ``` Nothing is as practical as a good theory -- Kurt Lewin ``` How does Ouroboros handle routing and how is it different from the Internet? How does it do multicast? That's a good subject for a blog post! I assume the reader to be a bit knowledgeable about the Internet Protocol (IP) suite. I limit this discussion to IPv4, but generally speaking it's also applicable to IPv6. Hope you enjoy the read. Network communications is commonly split up into four classes based on the delivery model of the message. If it is a single source sending to a single receiver, it is called _unicast_. This is the way most of the traffic on the Internet works: a packet is forwarded to a specific destination IP address. This process is then called _unicast routing_. If a sender is transmitting a message to _all_ nodes in a network, it's called _broadcast_. To do this efficiently, the network will run a bunch of protocols to construct some form of _spanning tree_ between the nodes in the network a process referred to as _broadcast routing_. If the destination is a specific set of receivers, it's called _multicast_. Broadcast routing is augmented with a protocol to create groups of nodes, the so-called multicast group, to again create some form of a spanning tree between the group members, called _multicast routing_. The last class is _anycast_, when the destination of the communication is _any_ single member of a group, usually the closest. Usually these concepts are explained in an Internet/IP setting where the destinations are (groups of) IP addresses, but the concepts can also be generalized towards the naming system: resolving a (domain) name to a set of addresses, for instance, which can then be used in a multicast implementation called _multidestination routing_. Multidestination routing (i.e. specifying a bunch of destination addresses in a packet) doesn't scale well. Can we contemplate other classes? Randomcast (sending to a random destination)? Or stupidcast (sending to all destinations that don't need to receive the message)? All kidding aside, the 4 classes above are likely to be all the _sensible_ delivery models. ### Conundrum, part I During the development of Ouroboros, it became clearer and clearer to us that the distinction based on the delivery model is not a _fundamental_ one. If I have to make a -- definitely imperfect -- analogy, it's a bit like classifying animals by the number of eyes they have. Where two eyes is unicast, more is multicast and composite eyes broadcast. Now, it will tell you _something useful_ about the animals if they are in the 2, multi or composite-eye class, but it's not how biologists classify animals. Some animal orders -- spiders -- have members with 2, 4, 6 and 8 eyes. There are deeper, more meaningful distinctions that can be made on more fundamental grounds, such as whether the species has a backbone or not, that traces back their evolution. What are those fundamental differences for networks? Take a minute to contemplate the following little conundrum. Take a network that is linear, e.g. ``` source - node - node - node - node - destination ``` and imagine observing a packet traveling over every _link_ on this linear network, from source to destination. Was that communication anycast, unicast, multicast or broadcast? Now this may seem like a silly question, but it should become clearer why it's relevant, and -- in fact -- fundamental. I will come back to this at the end of this post. But first, let's have a look at how it's done, shall we? ### Unicast This is the basics. IP routers will forward packets based on the destination IP address (not in any special range) in their header to the host (in effect: an interface) that has been assigned that IP address. The forwarding is based on a forwarding table that is constructed using some routing protocol (OSPF/IS-IS/BGP/...). I'll assume you know how this works, and if not, there are plenty of online resources on these protocols. On unicast in Ouroboros, I will be pretty brief: it operates in a similar way as unicast IP: packets are forwarded to a destination address, and the layer uses some algorithm to build a forwarding table (or more general, a _forwarding function_). In the current implementation, unicast is based on IS-IS link-state routing with support for ECMP (equal-cost multipath). The core difference with IP is that there are _no_ special case addresses: an address is _always_ uniquely assigned to a single network node. To scale the layer, there can be different _levels_ of (link-state) routing in a layer. It's very interesting in its own right, but I'll focus on the _modus operandi_ in this post, which is: packets get forwarded based on an address. I'll take a more in-depth look into Ouroboros addressing in (maybe the next) post (or you can find it in the [paper](https://arxiv.org/abs/2001.09707). ### Anycast IP anycast is a funny thing. It's pretty simple: it's just unicast, but multiple nodes (interfaces) in the network have the same address, and the shortest path algorithm used in the routing protocol will forward the packet to the nearest node (interface) with that address. The network is otherwise completely oblivious; there is no such thing as an _anycast address_, it's a concept in the mind of network engineers. Now, if your reaction is _that can't possibly work_, you're absolutely right! Equal length paths can lead to _route flapping_, where some packets would be delivered _over here_ and other packets _over there_. That's why IP anycast is not something that _anyone_ can do. I can't run this server somewhere in Germany and a clone of it in Denver, and yet another clone in Singapore, and give them the same IP address. IP anycast is therefore highly restricted to some select cases, most notably DNS, NTP and some big Content Delivery Networks (CDNs). There is a certain level of trust needed between BGP peers, and BGP routers are monitored to remove routes that exhibit flapping. In addition, NTP and DNS use protocols that are UDP-based with a simple request-response mechanism, so sending subsequent packets to a different server isn't a big problem. CDN providers go to great _traffic engineering_ lengths to configure their peering relations in such a way that the anycast routes are stable. IP anycast "works" because there are a lot of assumptions and it's engineered -- mostly through human interactions -- into a safe zone of operations[^1]. In the case of DNS in particular, IP anycast is an essential part of the Internet. Being close to a root DNS server impacts response times! The alternative would be to specify a bunch of alternate servers to try. But it's easier to remember [9.9.9.9](https://www.quad9.net/) than a whole list of random IP addresses where you have to figure out where they are! IP anycast also offers some protection against network failures in case the closest server becomes unreachable, but this benefit is relatively small as the convergence times of the routing protocols (OSPF/BGP) are on the order of minutes (and should be). That's why most hosts usually have 2 DNS servers configured, because relying on anycast could mean a couple of minutes without DNS. Now, about anycast in Ouroboros, I can again be brief: I won't allow multiple nodes with the same address in a layer in the prototype, as this doesn't _scale_. Anycast is supported by name resolution. A service can be registered at different locations (addresses) and resolving such a name will return a (subset of) address(es) from the locations. If a flow allocation fails to the closest address, it can be repeated to the next one. Name resolution is an inherent function of a _unicast layer_, and currently implemented as a Distributed Hash Table (DHT). When joining a network (we call this operation _enrolment_, Kademlia calls it _join_), a list of known DHT node addresses is passed. The DHT stores its <name, address> entries in multiple locations (in the prototype this number is 8) and the randomness of the DHT hash assignment in combination with caching ensures the _proximity_ of the most popular lookups with reasonable probability. ### Broadcast IP broadcast is also a funny thing, as it's not really IP that's doing the broadcasting. It's a coating of varnish on top of _layer 2_ broadcast. So let's first look at Ethernet broadcast. Ethernet broadcast does what you would expect from a broadcasting solution. Note that switched Ethernets are confined to a loop-free topology by grace of the (Rapid) Spanning-Tree Protocol. A message to the reserved MAC address FF:FF:FF:FF:FF:FF will be _broadcasted_ by every intermediate Layer 2 node to all nodes (interfaces) that are connected on that Ethernet segment. If VLANs are defined, the broadcast is confined to all nodes (interfaces) on that VLAN. Quite nice, no objections _your honor_! The semantics of IP broadcast are related to the scope of the underlying _layer 2_ network. An IP broadcast address is the last "IP address" in a _subnet_. So, for instance, in the 192.168.0.0/24 subnet, the IP broadcast address is 192.168.0.255. When sending a datagram to that IP broadcast destination, the Ethernet layer will be sending it to FF:FF:FF:FF:FF:FF, and every node _on that Ethernet_ which has an IP address in the 192.168.0.0/24 network will receive it. You'd be forgiven to think that an IP broadcast to 255.255.255.255 should be spread to every host on the Internet, but for obvious reasons that's not the case. The semantic of 0.0.0.0/0 is to mean your own local IP subnet on that specific interface. The DHCP protocol, for instance, makes use of this. A last thing to mention is that, in theory, you could send IP broadcast messages to a _different_ subnet, but few routers allows this, because it invites some very obvious [smurf attacks](https://en.wikipedia.org/wiki/Smurf_attack). Excuse me for finding it more than mildly amusing that standards originally [_required_](https://tools.ietf.org/html/rfc2644) routers to forward directed broadcast packets! So, in practice,IP broadcast is a _passthrough_ interface towards layer 2 (Ethernet, Wi-Fi, ...) broadcast. In Ouroboros -- like in Ethernet -- broadcast is a rather simple affair. It is facilitated by the _broadcast layer_, for which each node implements a _broadcast function_: what comes in on one flow, goes out on all others. The implementation is a stateless layer that -- also like Ethernet -- requires the graph to be a tree. But it has no addresses -- in fact, it doesn't even have a _header_ at all! Access control is part of _enrolment_, where participants in the broadcast layer get read and/or write access to the broadcast layer based on credentials. Every message on a broadcast layer is actually broadcast. This is the only way -- at least that I know of -- to make a broadcast layer _scaleable_ to billions of receivers![^2] So here is the first clue to the answer to the little conundrum at the beginning of this post. The Ouroboros model makes a distinction between _unicast layers_ and _broadcast layers_, based on the _nature of the algorithm_ applied to the message. If it's based on a _destination address_ in the message, we call the algorithm _FORWARDING_, and if it's sending on all interfaces except the incoming one, we call the algorithm _FLOODING_. An application like 'ping', where one broadcasts a message to a bunch of remotes, and each one responds back requires _both_ a broadcast layer and a unicast layer of (at least) the same size, with the 'ping' application using both[^3]. Tools like _ping_ and _traceroute_ and _nmap_ are administrative tools which reveal network information. They should only be available to _administrators_. It's not prohibited to implement an IPCP that does both broadcast (to the complete layer) and unicast. In fact, the unicast IPCP in the prototype in some sense does it, as we only figured out broadcast layers _after_ we implemented the link-state protocol, which is effectively broadcasting link-state messages within the unicast layer. All it would take is to implement the _flow\_join()_ API in the unicast IPCP and send those packets like we send Link-State Messages. But I won't do it, for a number of reasons: the first is that it is rare to have broadcast layers and unicast layers to be exactly the same size. Usually broadcast layers will be much smaller. The second is that, in the current implementation, the link-state messages are stateful: they have the source address and a sequence number to be able to deal with loops in the meshed topology. This doesn't scale to the _full_ unicast layer. To create a scaleable _do-both-unicast-and-broadcast_ layer, it would require to create a "virtual tree-topology-network" within the unicast layer, which is adjacency management. This would require an adjacency management module (running something like a hypothetical RSTP that is able to scale to billions of nodes) as part of the unicast IPCP. Adjacency management is functionality that was removed -- we called it the _graph adjaceny manager_ and the logic put _outside_ of the IPCP and replaced with a _connect_ API so it could be scripted as part of network management. And the third, and most important, is that we like the prototype to reflect the _model_, as it is more educational. Unicast layers and broadcast layers _are_ different layers. Always have been, and always will be. Combining them in an implementation only obfuscates this fact. To make a long (and probably confusing) story short, combining unicast and broadcast in a single IPCP _can_ be done, but at present I don't see any real benefit in doing it, and I'm pretty sure it will be hard to avoid [_making a mess_](https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1304.html) out of it. This transitions us nicely into multicast. Because combining unicast and multicast in the same layer is exactly what IP tries to do. ### Multicast Before looking at IP, let's first have a look at how one would do multicast in Ethernet, because it's simpler. The simplest way to achieve multicast within Ethernet 802.1Q is using a VLAN: Configure VLANs on the end hosts and switch, and then just broadcast packets on that VLAN. The Ethernet II (MAC) frame will look like this: ``` +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | FF:FF:FF:FF:FF:FF | SRC | 0x8100 | TCI | Ethertype | .. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ``` The 0x8100 _en lieu_ of the Ethertype specifies that it's a VLAN, the Tag Control Information (TCI) has 12 bits that specify a VLAN ID, so one can have 4096 parallel VLANs. There are two fields needed to achieve the multicast nature of the communications: The destination set to the broadcast address, and a VLAN ID that will only be assigned to members of the group. Now, it won't come as a surprise to you, but IP multicast _is_ a funny thing. The gist of it is that there are protocols that do group management and protocols that assist in building a (spanning) tree. There is a range of IP addresses, 224.0.0.0 -- 239.255.255.255 (or in binary: starting with the 1110), called _class D_, which are only allowed as destination addresses. This _class D_ is further subdivided in different ranges for different functionalities, such as source-specific multicast. An IPv4 multicast packet can be distinguished by a single field: a destination address in the _class D_ range. If we compare this with Ethernet above, the _class D_ IP address is behaving more like the VLAN ID than the destination MAC _address_. The reason IP doesn't need an extra destination address is that the _broadcast_ functionality is _implied_ by the _class D_ address range, whereas a VLAN also supports unicast via MAC learning. Ethernet actually also has a special address range for multicast, 01:00:5E:00:00:00 to 01:00:5E:7F:FF:FF, that copies the last 23 bits of the IP multicast address when that host joins the multicast tree. The reasoning behind it is this: if there are multiple endpoints for an IP multicast tree on the _same_ Ethernet segment, instead of the IP router sending individual unicast messages to each of them, that last "hop" can use a single Ethernet broadcast message. Next Ouroboros. From the discussion of the Ouroboros broadcast layer, you probably already figured out how Ouroboros does multicast. The same as broadcast! There is literally _zero_ difference. The only difference between multicast and broadcast is in the eye of the beholder when comparing a unicast layer and a broadcast layer. There is something else to remember about (Ouroboros) broadcast layers: the broadcast function is _stateless_, and _all_ broadcast IPCPs are _identical_ in function. The reason I mention this, is in relation the problem that I just mentioned above. What if I have a broadcast layer, for which a number of endpoints are also connected over a _lower_ broadcast layer? Can we, like IP/Ethernet, leverage this? And the answer is: no, there is no sharing of information between layers, and broadcast layers have no state. But we don't really need to! If there is a device with a broadcast IPCP in a lower broadcast layer, just add a broadcast IPCP to the higher level broadcast layer! It's not a matter of functionality, since the functionality for the higher level broadcast layer is _exactly_ the same as the lower one. While I am not eager to mix broadcast and unicast in a single IPCP program, I have few objections for creating a single program that behaves like multiple IPCPs of the same type. Especially for the stateless broadcast IPCP it would be rather trivial to make a single program that implements parallel broadcast IPCPs. And allowing something like _sublayers_ (like VLANs, with a single tag) is also something that can be considered for optimization purposes. ### Conundrum, part II Now, let's look back at our little riddle, with a packet observed to move from source to destination over a linear network. ``` source - node - node - node - node - destination ``` Now, if we pedantically apply the definition of one-to-one communication given in most textbooks, it is unicast, since it has only a single source and a single destination. But to know what's going on at the routing level, can not be known. But I hope you gave it some thought about what information you'd need to be _able to tell_. Let's start with Ethernet. The Ethernet standard says that all MAC addresses are unique, so it's not anycast, and there is no _real_ difference between multicast and broadcast. So, if the address is not the broadcast address or in some special range, it's _unicast_, else it's multi/broadcast. But really? What if the nodes were hubs instead of switches? What about IP? Bit harder. If it was anycast, it wouldn't have reached the destination if there was another node with the same address in this particular setup. But in a general IP network, it's not really possible to tell the difference between unicast and anycast without looking at all reachable node addresses. To know if it was broadcast or multicast, it would suffice to know the destination address in the packet. For Ouroboros, all you'd need to know what was going on is the type of layer. To detect anycast, one would need to query the directory to check if it returns a single or multiple destination addresses (since we don't allow _anycast routing_), and, like Ethernet in a way, it makes the distinction between multicast and broadcast rather moot. ### The Ouroboros model In a nutshell, what does the Ouroboros model say? First, all communications is composed of either unicast or broadcast, and these two types of communications are fundamentally different and give rise to distinct types of layers. In a _unicast_ layer, nodes implement _FORWARDING_, which moves packets based on a destination address. In a _broadcast_ layer, nodes implement _FLOODING_, which sends incoming packets out on all links except for the incoming link. If we leave out the physical layer (wiring, spectrum tuning etc), constructing a layer goes through 2 phases: adding a node to a network layer (enrolment) and adding links (by which I mean allowed adjacencies) between that node and other members of the layer (adjacency management). After this the node becomes active in the network. During enrolment, nodes can be authenticated and permissions are acquired such as read/write access. Both types of layers go through this phase. A unicast layer, may, in addition, periodically disseminate information that enables _FORWARDING_. We call this dissemination function _ROUTING_, but if you know a better word that avoids confusion, we'll take it. _ROUTING_ is distinct from adjacency management, in the sense that adjacency management is administrative, and tells the networks which links it is allowed to use, which links _exist_. _ROUTING- will make use of these links and make decisions when they are unavailable, for instance due to failures. Let's apply the Ouroboros model to Ethernet. Ethernet implements both types of layers. Enrolment and topology management are taken care of by the _spanning tree protocol_. It might be tempting to think that STP does _only_ topology management, but that's not really the case. Just add a new _root bridge_ to an Ethernet network: at some point, that network will go down completely. The default operation of Ethernet is as a _broadcast layer_: the default function applied to a packet is _FLOODING_. To allow unicast, Ethernet implements _ROUTING_ via _MAC learning_. MAC learning is thus a highly specific routing protocol, that piggybacks its dissemination information on user frames, and calculates the forwarding tables based on the knowledge that the underlying topology is a _tree_. This brings a caveat: it only detects sending interfaces. If there are receivers on an Ethernet that never send a frame (but for which the senders know the MAC address), that traffic will always be broadcast. And in any case, the _first_ packet will always be broadcast. Next, VLAN. In Ouroboros speak, a VLAN is an implementation detail (important, of course) to logically combine parallel Ethernets. VLANs are independent layers, and indeed, must be enrolled (VLAN IDs set on bridge interfaces) and will keep their own states of (R)STP and MAC learning. Without VLAN, Ethernet is thus a single broadcast layer and a single multicast layer. With VLAN, Ethernet is potentially 4096 broadcast layers and 4096 unicast layers. If we apply the Ouroboros model to IP, we again see that IP tries to implement both unicast and broadcast. A lot is configured manually. Enrolment and adjacency management are basically assigning IP addresses and, in addition, adding BGP routes and rules. IP has two levels of _ROUTING_, one is inside an autonomous system using link-state protocols such as OSPF, and on top there is BGP, which is disseminating routes as path vectors. Multicast in IP is building a broadcast layer, which is identified using a "multicast address", which is really the name of that broadcast layer. Enrolment into this virtual broadcast layer is handled via protocols such as IGMP, with adjacencies managed in many possible ways that involve calculating spanning trees based on internal topology information from OSPF or other means. The tree is then grafted into the routing table by labeling outgoing interfaces with the name of the broadcast layer. Yes, _that_ is what adding a multicast destination address to an IP forwarding table is _really_ doing! It's just hidden in plain sight! Now, my claim is that the Ouroboros model can be applied to _any_ packet network technology. To conclude this post, let's take a real tricky one: Multi-Protocol Label Switching (MPLS). MPLS looks very different from Ethernet and IP. It doesn't have addresses at all, but uses _labels_, and it can swap and stack labels. Now, surely, MPLS doesn't fit the unicast layer, which says that every node gets an address, and forwards based on the destination address. Here's the solution to MPLS: it is a set of broadcast layers! The labels are a distributed way of identifying the layer _by its links_, instead of a single identifier for the whole layer, like a VLAN or a multicast IP address. RSVP / LDP (and their traffic engineering -TE cousins) are protocols that do enrolment and adjacency management. I hope this gave you a bit of an insight into the Ouroboros view of the world. Course materials on computer networks consist of a compendium of technologies and _how_ they work. The Ouroboros model is an attempt to figure out _why_ they work. Stay curious. Dimitri [^1]: I'm sure someone has or will propose some AI to solve it. [^2]: Individual links on a broadcast layer can be protected with retransmission and using multi-path routing in the underlying unicast layer. [^3]: Now that I'm writing this, I put it on my todo list to implement this into the oping application.