Routers that are compatible with Time Machine
Just to clarify, the term &quot;router&quot; is incorrect here mostly because it is used incorrectly by manufacturers who sell products in the retail market.
A router is neither compatible nor incompatible with Time Machine.  A router simply routes network traffic (packets) from one network to another.
What these retail &quot;routers&quot; actually are is an amalgamation of

the network router (described above)
a network switch
a WiFi access point
a NAS (network attached storage)
a server (DHCP, DNS, Web, etc.)
whatever other nonsense they try to jam into an overpriced, but severely under powered, extremely low quality SoC (System on Chip) covered by flashy plastic.

What is incompatible is the NAS functionality of the device.   Specifically in this case, the protocol(s) the router manufacturer chose to include don't include support for Bonjour.
Solution:  Buy a separate NAS Device
Relying on a single device that is literally at the edge of your network (meaning it's the security between your internal network and the rest of the WWW (wild wild web), it's risky to store your backups there.
Instead, get a separate NAS device that supports Time Machine.  Like the Synology (I personally use the DS212j at home)   It fully supports Time Machine and is designed to be a NAS and functions as such.
If you have an old computer you can install FreeNAS on it and basically get the NAS for free.  If you have an old Mac, you can turn it into a &quot;server,&quot; make a shared directory and backup Time Machine(s) to it over the network.
Bottom line:  Backups are important.  Put it on reliable hardware, not devices that add it on as an afterthought.