Today I checked logs from the job https://review.rdoproject.org/zuul/build/c3c8003f08454b56b53e626b77946541/logs (which timed out).
I found out that there are some tests which runs very long time, like e.g. tempest.api.compute.floating_ips.test_floating_ips_actions.FloatingIPsAssociationTestJSON.test_associate_already_associated_floating_ip which took 101 seconds in that case (see https://logserver.rdoproject.org/openstack-periodic-integration-stable1/opendev.org/openstack/tripleo-ci/master/periodic-tripleo-ci-centos-8-ovb-3ctlr_1comp-featureset035-wallaby/c3c8003/logs/undercloud/var/log/tempest/tempest_run.log.txt.gz)
I compared this with u/s job and the same test took about 18 seconds.

Now, I checked in tempest logs, what took so long in that test and here is what I found:

zgrep test_associate_already_associated_floating_ip tempest.log.txt.gz                                                                                                                                                                                                  1 ↵
2021-09-07 12:11:47.017 321761 INFO tempest.lib.common.rest_client [req-fef2015f-da1e-4cd5-96a0-ae8f866b011a ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 201 POST https://[2001:db8:fd00:1000::5]:13000/v3/auth/tokens 0.618s
2021-09-07 12:11:47.019 321761 INFO tempest.lib.common.fixed_network [-] (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip) Found network {'id': 'f13ea60f-7c63-4e86-a2b5-8763b9d961ac', 'name': 'tempest-FloatingIPsAssociationTestJSON-807472534-network', 'tenant_id': 'ab0311a8b40c4819b4eaef28810349b4', 'admin_state_up': True, 'mtu': 1292, 'status': 'ACTIVE', 'subnets': [], 'shared': False, 'project_id': 'ab0311a8b40c4819b4eaef28810349b4', 'qos_policy_id': None, 'port_security_enabled': True, 'router:external': False, 'provider:network_type': 'geneve', 'provider:physical_network': None, 'provider:segmentation_id': 1566, 'availability_zone_hints': [], 'is_default': False, 'availability_zones': [], 'ipv4_address_scope': None, 'ipv6_address_scope': None, 'description': '', 'l2_adjacency': True, 'tags': [], 'created_at': '2021-09-07T12:10:46Z', 'updated_at': '2021-09-07T12:10:46Z', 'revision_number': 1} available for tenant
2021-09-07 12:11:53.102 321761 INFO tempest.lib.common.rest_client [req-160b2232-94b4-4e9a-a32c-0cad25e19623 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 202 POST https://[2001:db8:fd00:1000::5]:13774/v2.1/servers 6.081s
2021-09-07 12:12:01.016 321761 INFO tempest.lib.common.rest_client [req-a2cc5468-d003-4fdb-bb7a-9afc9b44cb5e ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 200 GET https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601 7.911s
2021-09-07 12:12:05.347 321761 INFO tempest.lib.common.rest_client [req-bc47090b-7794-4985-b365-9df25e112af7 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 200 GET https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601 3.314s
2021-09-07 12:12:09.281 321761 INFO tempest.lib.common.rest_client [req-010f44f9-cc32-478d-8d35-3de0c6dcaa09 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 200 GET https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601 2.920s
2021-09-07 12:12:16.049 321761 INFO tempest.lib.common.rest_client [req-29c050d4-2524-4679-b61e-955a569d1639 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 200 GET https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601 5.757s
2021-09-07 12:12:19.472 321761 INFO tempest.lib.common.rest_client [req-52053e26-486a-4462-935b-acad5cc3b690 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 200 GET https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601 2.413s
2021-09-07 12:12:34.758 321761 INFO tempest.lib.common.rest_client [req-4dc300ea-1938-47af-b730-32fca53c720f ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 200 GET https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601 14.274s
2021-09-07 12:12:49.928 321761 INFO tempest.lib.common.rest_client [req-71b20a7f-0ec8-4249-aa55-6b22dceaacae ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 202 POST https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/1d934f88-3c77-4f9f-aa2d-6e1bb1537683/action 15.163s
2021-09-07 12:13:08.840 321761 INFO tempest.lib.common.rest_client [req-65e32c04-44e2-4bac-bcab-1ed865f00d92 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 202 POST https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/ea159240-bdfa-4a34-ab2a-ff8f67776601/action 18.908s
2021-09-07 12:13:13.536 321761 INFO tempest.lib.common.rest_client [req-d967d72d-0279-452b-a38c-bb0ff1aa5094 ] Request (FloatingIPsAssociationTestJSON:test_associate_already_associated_floating_ip): 409 POST https://[2001:db8:fd00:1000::5]:13774/v2.1/servers/1d934f88-3c77-4f9f-aa2d-6e1bb1537683/action 4.690s

So every single call to Nova takes at least couple of seconds, even 14 in case of GET request. For POST it's even worts as it could take 18 seconds even.
I don't know if the slowdown in nova api is due to memcached servers or something else but if patch https://review.opendev.org/c/openstack/tripleo-heat-templates/+/805952 was going to fix it by setting IP addresses as memcached servers, than it is not working as expected as I still see domain names in the nova conf: https://logserver.rdoproject.org/openstack-periodic-integration-stable1/opendev.org/openstack/tripleo-ci/master/periodic-tripleo-ci-centos-8-ovb-3ctlr_1comp-featureset035-wallaby/c3c8003/logs/overcloud-novacompute-0/var/lib/config-data/puppet-generated/nova_libvirt/etc/nova/nova.conf.txt.gz