blog: Add post on uni/any/multicast

1 files changed, 479 insertions, 0 deletions

diff --git a/content/en/blog/20210402-multicast.md b/content/en/blog/20210402-multicast.md
new file mode 100644
index 0000000..38a71ee
--- /dev/null
+++ b/content/en/blog/20210402-multicast.md
@@ -0,0 +1,479 @@
+---
+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/255
+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 adjancy
+management, in the sense that adjancy 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 adjancy 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.