Local Network Traversal - Multicast Discovery

[joshuakarp]

Created by @CMCDragonkai

Specification

There are two types of Data Flow in the MDNS System, Polling (Pull), and Announcements/Responses (Push). When a Node joins the MDNS group, the records are pushed to all other nodes. However, for the joined node to discover other nodes, it needs to conduct polling queries that other nodes respond to.

Sending Queries

The MDNS spec states that query records can have additional records, but we won't care to do this as it isn't necessary. Queries won't have any other records in the query record, much like a standard DNS packet (albeit an mdns query packet can contain multiple questions).

In the case that a responder is binded to 2 interfaces that are connected to the same network (such as a laptop with WiFi + ethernet connected), the queries asking for the ip for a hostname of the responder will receive multiple responses with different ip addresses.

This behavior is documented in: RFC 6762 14.

Control Flow

Unlike other mDNS libraries, we're going to use an AsyncIterator in order to have the consumer to have more control over the querying. An example of this would be:

async function* query({...}: Service, minimumDelay: number = 1, maximumDelay: number = 3600) {
   let delay = minimumDelay;
   while (true) {
    await this.sendPacket(...);
    delay *= 2;
    yield delay;
  }
}

The query system has been decided to have it's runtime contained within MDNS rather than being consumer-driven. This means that scheduled background queries will have to be managed by a TaskManager (similar to polykey)

Data Flow

Receiving Announcements/Responses (Pull)

Data Flow

Because queries are basically fire and forget, the main part comes in the form of receiving query responses from the multicast group. Hence, our querier needs to be able to collect records with a fan-in approach using a muxer that is reactive:

This can also be interpreted as a series of state transitions to completely build a service.

There also needs to be consideration that if the threshold for a muxer to complete is not reached, that additional queries are sent off in order to reach the finished state.

The decision tree for such would be as follows:

Control Flow

Instances of MDNS will extend EventTarget in order to emit events for service discovery/removal/etc.

class MDNS extends EventTarget {
}

The cache will be managed using a timer that is set to the soonest record TTL, rather than a timer for each record. The cache will also need to be an LRU in order to make sure that malicious responders cannot overwhelm it.

Sending Announcements

Control Flow

This will need to be experimented with a little. Currently the decisions are:

• registerService cannot be called before start is called.
• create should take in services in place of this.
• stop should deregister all services
• destroy should remove everything from the instance

  class MDNS extends EventTarget {
  create()
  start()
  stop()
  register()
  deregister()
  }

Types

Messages can be Queries or Announcements or Responses. This can be expressed as:

type MessageType = "query" | "announcement" | "response";
type Message = [MessageType, ResourceRecord] & ["query", QuestionRecord];
const message = ["query", {...}];

Parser / Generator

The Parsing and Generation together are not isomorphic, as different parsed UInt8array packets can result in the same packet structure.

Every worker parser function will return the value wrapped in an object of this type:

type Parsed<T> = {
  data: T;
  remainder: UInt8Array;
}

The point of this is so that whatever hasn't been parsed get returned in .remainder so we don't keep track of the offset manually. This means that each worker function also needs to take in a second uint8array representing the original data structure.

1. DNS Packet Parser Generator Utilities
   • Parser - parsePacket(Uint8array): Packet
   • Headers - parseHeader(Uint8array): {id: ..., flags: PacketFlags, counts: {...}}
   • Id - parseId(Uint8array): number
   • Flags - parseFlags(Uint8Array): PacketFlags
   • Counts - parseCount(Uint8Array): number
   • Question Records - parseQuestionRecords(Uint8Array): {...}
     • parseQuestionRecord(Uint8Array): {...}
   • Resource Records - parseResourceRecords(Uint8Array): {...}
     • parseResourceRecord(Uint8Array): {...}
     • parseResourceRecordName(Uint8Array): string
     • parseResourceRecordType(Uint8Array): A/CNAME
     • parseResourceRecordClass(Uint8Array): IN
     • parseResourceRecordLength(Uint8array): number
     • parseResourceRecordData(Uint8array): {...}
     • parseARecordData(Uint8array): {...}
     • parseAAAARecordData(Uint8array): {...}
     • parseCNAMERecordData(Uint8array): {...}
     • parseSRVRecordData(Uint8array): {...}
     • parseTXTRecordData(Uint8array): Map<string, string>
     • parseOPTRecordData(Uint8array): {...}
     • parseNSECRecordData(Uint8array): {...}
   • String Pointer Cycle Detection
     • Everytime a string is parsed, we take reference of the beginning and end of the string so that pointers cannot point to a start of a string that would infinite loop. A separate index table for the path of the dereferences to make sure deadlock doesn't happen.
   • Errors at each parsing function instead of letting the data view failing
     • ErrorDNSParse - Generic error with message that contains information for different exceptions. Ie. id parse failed at ...
   • Record Keys - parseResourceRecordKey and parseQuestionRecordKey and parseRecordKey - parseLabels.
   • Generator - generatePacket(Packet): UInt8Array
   • Header generateHeader(id, flags, counts...)
     • Id
     • Flags - generateFlags({ ... }): Uint8Array
     • Counts - generateCount(number): Uint8Array
   • Question Records - generateQuestionRecords(): Uint8Array - flatMap(generateQuestion)
     • generateQuestionRecord(): Uint8Array
   • Resource Records (KV) - generateResourceRecords()
     • generateRecord(): Uint8array -
     • generateRecordName - "abc.com" - ...RecordKey
     • generateRecordType - A/CNAME
     • generateRecordClass - IN
     • generateRecordLength
     • generateRecordData
     • generateARecordData(string): Uint8array
     • generateAAAARecordData(string): Uint8array
     • generateCNAMERecordData(string): Uint8array
     • generateSRVRecordData(SRVRecordValue): Uint8array
     • generateTXTRecordData(Map<string, string>): Uint8array
     • generateOPTRecordData(Uint8array): Uint8array
     • generateNSECRecordData(): Uint8array
   • Integrated into MDNS
2. MDNS
   • Querying
   • MDNS.query()
     • query services of a type
   • MDNS.registerService()
   • MDNS.unregisterService()
   • Responding
   • Listening to queries
   • Responding to all queries with all records
   • Respond to unicast
   • Truncated bit

Testing

We can use two MDNS instances to interact with each other to test both query and respond on separate ports.

Additional Context

The following discussion from 'Refactoring Network Module' MR should be addressed:

• @CMCDragonkai: (+3 comments)

  Next things:

  1. Multicast discovery (bring back what we had in the old code)
  2. Update our peer table
  3. Implement kademlia on peer table
  4. Refactor GRPC commands for this
  5. Produce test harness for multiple nodes on a local network

  Multicast Discovery

  DNS-SD and mDNS are related protocols for discovery on a local network. This local network is designated usually by a "home router" or a switch. But basically some arbitrary subnet with gateways that are part of a "single network".

  The way this works is that there's a special address (for IPv4 and IPv6) that a mDNS software both listens and sends UDP packets on. This is known as a "multicast" address.

  The UDP packet contains information structured as a "DNS message", basically the same kind of message you get when you actually query a DNS server to resolve a hostname.

  What we have to do is register a hostname for our application. Let's say "polykey", this registration is done on IANA (just like how we registered the OID for our company). This list is here: https://www.iana.org/assignments/service-names-port-numbers/service-names-port-numbers.xhtml and our application for an assignment is here: https://www.iana.org/form/ports-services

  Now once we build a multicast mDNS client/server, we can then advertise on the multicast address by sending a DNS UDP packet that claims "polykey.local" is registered to IP at PORT. Simultaneously we can listen on the multicast address for DNS packets, and filter for all claims to "polykey.local".

  Since multiple PK agents can occur on the same subnet, this means we may either have to differentiate on a subdomain of our hostname, or append a renew record to the hostname. It is possible for a given hostname to contain multiple DNS records (and these may indicate IP and PORT assignments). I'm not sure if this is the right way to do this. Need to do a bit of research.

  At the end of the day, PK node table gets populated with this initial multicast discovery. We have to have a mDNS client (to send multicast) and mDNS server (to listen for multicast). The mDNS server would be listening for these packets.

  Note that there is software like avahi, that acts like an mDNS server/client, this is used interactively by other software that don't have native mDNS capabilities. This is not important to us... we will be advertising directly.

  According to this: https://askubuntu.com/a/1105895 it may be possible that the "service type" is different from the hostname. Therefore it's possible to randomly allocate a hostname, and only listen for a given "service type". In which case _polykey_._tcp would be the service type, and you could get hostnames like polykey-PUBLICKEYFINGERPRINT.local, and thus that should be considered unique. Therefore from a service discovery point of view, the only thing static is the IP used for multicast, and the "service type" which is globally setup at IANA. The hostnames, IPs and even ports are all dynamically setup.

  The node library https://github.com/agnat/node_mdns binds into system-level services and provides the ability to listen and query mdns packets: https://github.com/agnat/node_mdns

  A lower level library in pure-js is here: https://github.com/mafintosh/multicast-dns that is used with https://github.com/mafintosh/multicast-dns-service-types according to this issue: https://github.com/mafintosh/multicast-dns/issues/6#issuecomment-91034709

• https://news.ycombinator.com/item?id=8229792

• https://blog.apnic.net/2022/05/03/how-nat-traversal-works-concerning-cgnats/

• https://github.com/MatrixAI/Polykey/issues/487#issuecomment-1294558470

• https://github.com/MatrixAI/Polykey/issues/487#issuecomment-1294742114

• https://support.citrix.com/article/CTX205483/how-to-accommodate-hairpinning-behaviour-in-netscaler

• mDNS RFC https://datatracker.ietf.org/doc/html/rfc6762

• DNS-SD RFC https://datatracker.ietf.org/doc/html/rfc6763

• Domain Names RFC https://datatracker.ietf.org/doc/html/rfc1035

• Extension Mechanisms for DNS RFC https://datatracker.ietf.org/doc/html/rfc6891

• NSEC RFC https://datatracker.ietf.org/doc/html/rfc3845

Tasks

• [x] Parser - 5.5 days
  • [x] Packet Header - 0.5 days
  • [x] Packet Flags - 0.5 days
  • [x] Questions - 0.5 days
  • [x] Resource Records - 4 days
• [x] Generator 5.5 days
  • [x] Packet Header - 0.5 days
  • [x] Packet Flags - 0.5 days
  • [x] Questions - 0.5 days
  • [x] Resource Records - 4 days
• [x] MDNSCache - 2.5 days
  • [x] Multi-Keyed Maps for ResourceRecord Querying - 0.5 days
  • [x] TTL Expiry Record Invalidation - 0.5 days
  • [x] Reverse Host to Record Mapping - 0.5 days
  • [x] LRU to Prevent DoS - 0.5 days
  • [x] Support use as local resource record in-memory database - 0.5 days
• [x] TaskManager - ? days
  • [x] Migrate to in-memory - ? days
• [x] MDNS - 11.5 days
  • [x] UDP Networking Logic - 2 days
  • [x] Socket Binding to Multiple Interfaces - 1 days
  • [x] Error Handling - 1 days
  • [x] Querier - 4 days
  • [x] Service Querying - 2.5 days
    • [x] Record Aggregation for Muxxing Together Services - 0.5 days
    • [x] Querying For a Service's Missing Records - 0.5 days
    • [x] Emitting Expired Services - 0.5 days
  • [x] Unicast 1.5 days
    • [x] Checking for Unicast Availability - 1 days
    • [x] Sending queries with unicast enabled - 0.5 days
  • [x] Responder 5.5 days
  • [x] Service Registration - 0.5 days
  • [x] Filter Messages Received from Multicast Interface Loopback - 0.5 days
  • [x] Unicast
    • [x] Responding to Unicast Queries - 0.5 days

[CMCDragonkai]

Does this mean 2 sockets for every IP address?

[amydevs]

Does this mean 2 sockets for every IP address?

yes, but that is if we decide to do unicast response, request.

for now, i'm just focusing on not touching any of that @CMCDragonkai

[CMCDragonkai]

We're going to have to do it the way ciao does it. 1 socket per interface, but bound to wildcard.

Make sure that the sockets will be able to join both the IPv4 multicast group and IPv6 multicast group.

[amydevs]

Some tests to consider:

• DNS Packet Parsing/Generating
• Cache Insertion
• Cache Querying
• Cache Expiry
• Cache Overload
• Creating/Receiving Announcements
  • Cancelling Announcements (via stop())
• Creating/Receiving Responses
• Creating/Receiving Queries
  • Cancelling Queries
• Creating/Receiving Unicast Response
• Port Conflict

[CMCDragonkai]

@amydevs

1. Logging should use INFO for most things. The only warnings right now should only be for when os.networkInterfaces provide invalid information and when you can proceed.
2. Use X, Xing, Xed for the logging first keyword. Where X is the verb. Only using Xing when it's a one-off thing. X, Xed is for pre-X and post-X respectively.
3. Mock testing just means mocking the input/output to MDNS. We don't need to simulate multiple interfaces or multiple sockets. But by controlling the input/output, we can simulate an entire interaction of MDNS in different scenarios.

[amydevs]

On linux, due to node setting the IP_MULTICAST_ALL flag to true, will have sockets bound to any wildcard address (::, ::0, 0.0.0.0) receive all multicast traffic from all added groups on the system! This is not the same behavior as that on windows/macos/bsd.

https://github.com/nodejs/node/issues/19954

[CMCDragonkai]

Note that here https://github.com/clshortfuse/node-getsockethandleaddress it indicates that you can get the sockfd integer just by doing socket._handle.fd. Specifically for linux and macos I think.

You should confirm if this fix is needed for macos.

You'll still need to write the NAPI code to actually do something with that file descriptor number.

The _handle.fd does come with some sort of warning message. See if you can suppress that...?

[amydevs]

The intended behavior is that a binded socket to "0.0.0.0" or "::0", with IP_MULTICAST_ALL disabled, will not receive any multicast messages at all. Furthermore, when addMembership is called specifying a specific interface, multicast packets will only be received from that group on that interface.

It would seem, that disabling IP_MULTICAST_ALL works as intended on udp4 sockets.

However, it seems that when disabling IPV6_MULTICAST_ALL, without calling addMembership, it works as intended. However, as soon as I call addMembship, that socket seems to start receiving multicast packets from every interface even when i've only specified one specific interface.

[amydevs]

it seems that there are several options that add an ipv6 socket to a multicast group, being IPV6_JOIN_GROUP and IPV6_ADD_MEMBERSHIP. They all use the ipv6_mreq struct as a configuration option rather than the ip_mreq struct.

The key difference between these is that ipv6_mreq takes in the interface index, whilst ip_mreq takes an interface ip address.

Node, upon calling addMembership, will call uv_udp_set_membership with JOIN_GROUP, passing in the interface ip address. If it is udp4, libuv will throw ENODEV when an iface does not correspond to the address you have provided. However, on udp6, libuv tries to look for the index (scopeid) of the interface with the address you've provided using uv_ip6_addr. It SHOULD give an ENODEV error if it is invalid, but it is not bubbling up to node for some reason.

On udp6, libuv chooses the scopeid by WHATEVER IS AFTER THE % SIGN, IF IT CAN'T BE FOUND, IT'S IGNORED. THAT IS WHY ADDMEMBERSHIP WITH JUST A IPV6 ADDRESS IS NOT ENOUGH, I THINK THE SCOPE ID NEEDS TO BE PROVIDED AFTER THE PERCENTAGE SIGN. This is only on windows, (on linux, providing the network interface name after the % sign is correct)

On udp6, using either IPV6_ADD_MEMBERSHIP or IPV6_JOIN_GROUP, will for whatever reason, make your socket listen to multicast packets on all interfaces rather than just a singular specified one. The native code that i tested is:

int AddMulticastMembership6(int sockfd, char* group, char* interface) {
  struct ipv6_mreq mreq;
  inet_pton(AF_INET6, group, &mreq.ipv6mr_multiaddr);
  mreq.ipv6mr_interface = if_nametoindex(interface);
  bool success = setsockopt(sockfd, IPPROTO_IPV6, IPV6_JOIN_GROUP, &mreq, sizeof(mreq)) >= 0;
  return if_nametoindex(interface);
}

[amydevs]

i've found that IP_BLOCK_SOURCE also exists. this could be useful in filtering out our own traffic. However, we would need to implement a platform-agnostic solution if we wanted to use this across all platforms. For now, having a set ip to filter out seems fine to me.

[amydevs]

as a workaround to https://github.com/MatrixAI/js-mdns/issues/1#issuecomment-1637365999, i'm trying to just bind a unicast socket first, then binding all the multicast sockets after. This is done so that the first unicast socket will catch all of the necessary unicast traffic.

I'm at the point of implementing this. However, even though i've made sure that the unicast socket is the first thing to be binded on a particular port, as soon as i bind other sockets, none of the sockets seem to be receiving any unicast traffic at all!

I wonder if the first socket bound to a port on an interface with reuseaddr being true receiving all unicast traffiic is deterministic...

[amydevs]

on macos, tests run correctly, just some counted references are making the cleanup (afterAll) of MDNS hang. I've pinned it down to the sending of the goodbye packets, but i'm still figuring a solution

[amydevs]

on windows, it is not possible to bind to a multicast address like you can on any unix system. On windows systems, i am binding each multicast socket to "::" instead. This functionally is the same as binding to the multicast address in my case, as i'm binding a unicast socket before all the other multicast sockets are binded. Windows makes sure that only the first socket that you've bound will receive multicast traffic.

[CMCDragonkai]

on macos, tests run correctly, just some counted references are making the cleanup (afterAll) of MDNS hang. I've pinned it down to the sending of the goodbye packets, but i'm still figuring a solution

Are you tracking all resources between start and stop? Always make sure to keep track of them. We already have problems with memory leaks and we have to be very strict here.

[CMCDragonkai]

Merged into staging now, doing the release.

[tegefaulkes]

Is this fully addressed by MDNS? Are there still plans to handle Hairpinning, PMP and PCP?

[CMCDragonkai]

PMP and PCP should be done separately.

Hairpinning not sure how that would be achieved.

[CMCDragonkai]

I created https://github.com/MatrixAI/Polykey/issues/536 to track PCP/PMP via UPNP. I did find a project that could be wrapped around in JS to make use of.

[CMCDragonkai]

@amydevs please tick off everything that was done above too.