diff --git a/core-internal.h b/core-internal.h
index 7608a41..c8e7b25 100644
--- a/core-internal.h
+++ b/core-internal.h
@@ -24,6 +24,13 @@
 #define MCTP_REQ_TAGS MCTP_REASSEMBLY_CTXS
 #endif
 
+#ifndef MCTP_DEFAULT_CLOCK_GETTIME
+#define MCTP_DEFAULT_CLOCK_GETTIME 1
+#endif
+
+/* Tag expiry timeout, in milliseconds */
+static const uint64_t MCTP_TAG_TIMEOUT = 6000;
+
 /* Internal data structures */
 
 enum mctp_bus_state {
@@ -73,6 +80,8 @@
 	mctp_eid_t local;
 	mctp_eid_t remote;
 	uint8_t tag;
+	/* time of tag expiry */
+	uint64_t expiry;
 };
 
 struct mctp {
@@ -102,4 +111,7 @@
 	size_t max_message_size;
 
 	void *alloc_ctx;
+
+	uint64_t (*platform_now)(void *);
+	void *platform_now_ctx;
 };
diff --git a/core.c b/core.c
index 3a4ed89..e28f6bc 100644
--- a/core.c
+++ b/core.c
@@ -20,6 +20,10 @@
 #include "compiler.h"
 #include "core-internal.h"
 
+#if MCTP_DEFAULT_CLOCK_GETTIME
+#include <time.h>
+#endif
+
 #ifndef ARRAY_SIZE
 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))
 #endif
@@ -238,6 +242,19 @@
 	return mctp;
 }
 
+#if MCTP_DEFAULT_CLOCK_GETTIME
+static uint64_t mctp_default_now(void *ctx __attribute__((unused)))
+{
+	struct timespec tp;
+	int rc = clock_gettime(CLOCK_MONOTONIC, &tp);
+	if (rc) {
+		/* Should not be possible */
+		return 0;
+	}
+	return (uint64_t)tp.tv_sec * 1000 + tp.tv_nsec / 1000000;
+}
+#endif
+
 int mctp_setup(struct mctp *mctp, size_t struct_mctp_size)
 {
 	if (struct_mctp_size < sizeof(struct mctp)) {
@@ -246,6 +263,9 @@
 	}
 	memset(mctp, 0, sizeof(*mctp));
 	mctp->max_message_size = MCTP_MAX_MESSAGE_SIZE;
+#if MCTP_DEFAULT_CLOCK_GETTIME
+	mctp->platform_now = mctp_default_now;
+#endif
 	return 0;
 }
 
@@ -893,11 +913,24 @@
 				       msg_len);
 }
 
+void mctp_set_now_op(struct mctp *mctp, uint64_t (*now)(void *), void *ctx)
+{
+	assert(now);
+	mctp->platform_now = now;
+	mctp->platform_now_ctx = ctx;
+}
+
+uint64_t mctp_now(struct mctp *mctp)
+{
+	assert(mctp->platform_now);
+	return mctp->platform_now(mctp->platform_now_ctx);
+}
+
 static void mctp_dealloc_tag(struct mctp_bus *bus, mctp_eid_t local,
 			     mctp_eid_t remote, uint8_t tag)
 {
 	struct mctp *mctp = bus->binding->mctp;
-	if (local == 0 || remote == 0) {
+	if (local == 0) {
 		return;
 	}
 
@@ -907,6 +940,7 @@
 			r->local = 0;
 			r->remote = 0;
 			r->tag = 0;
+			r->expiry = 0;
 			return;
 		}
 	}
@@ -916,17 +950,16 @@
 			  mctp_eid_t remote, uint8_t *ret_tag)
 {
 	assert(local != 0);
-	assert(remote != 0);
+	uint64_t now = mctp_now(mctp);
 
 	uint8_t used = 0;
 	struct mctp_req_tag *spare = NULL;
 	/* Find which tags and slots are used/spare */
 	for (size_t i = 0; i < ARRAY_SIZE(mctp->req_tags); i++) {
 		struct mctp_req_tag *r = &mctp->req_tags[i];
-		if (r->local == 0) {
+		if (r->local == 0 || r->expiry < now) {
 			spare = r;
 		} else {
-			// TODO: check timeouts
 			if (r->local == local && r->remote == remote) {
 				used |= 1 << r->tag;
 			}
@@ -944,6 +977,7 @@
 			spare->local = local;
 			spare->remote = remote;
 			spare->tag = tag;
+			spare->expiry = now + MCTP_TAG_TIMEOUT;
 			*ret_tag = tag;
 			mctp->tag_round_robin = (tag + 1) % 8;
 			return 0;
diff --git a/libmctp.h b/libmctp.h
index 1075f7a..f78132b 100644
--- a/libmctp.h
+++ b/libmctp.h
@@ -224,6 +224,15 @@
 #define MCTP_LOG_INFO	 6
 #define MCTP_LOG_DEBUG	 7
 
+/* Environment-specific time functionality */
+/* The `now` callback returns a timestamp in milliseconds.
+ * Timestamps should be monotonically increasing, and can have an arbitrary
+ * origin. (As long as returned timestamps aren't too close to UINT64_MAX, not
+ * a problem forany reasonable implementation). */
+void mctp_set_now_op(struct mctp *mctp, uint64_t (*now)(void *), void *ctx);
+/* Returns a timestamp in milliseconds */
+uint64_t mctp_now(struct mctp *mctp);
+
 #ifdef __cplusplus
 }
 #endif