diff --git a/openbsc/include/openbsc/bsc_nat.h b/openbsc/include/openbsc/bsc_nat.h
index 8fbed5b..e6f555c 100644
--- a/openbsc/include/openbsc/bsc_nat.h
+++ b/openbsc/include/openbsc/bsc_nat.h
@@ -306,7 +306,7 @@
  */
 int bsc_nat_filter_ipa(int direction, struct msgb *msg, struct bsc_nat_parsed *parsed);
 int bsc_nat_vty_init(struct bsc_nat *nat);
-struct bsc_connection *bsc_nat_find_bsc(struct bsc_nat *nat, struct msgb *msg, int *_lac);
+int bsc_nat_find_paging(struct msgb *msg, const uint8_t **,int *len);
 
 /**
  * Content filtering.
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat.c b/openbsc/src/osmo-bsc_nat/bsc_nat.c
index 2146da1..ba27341 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat.c
@@ -549,6 +549,50 @@
 	bsc_write(bsc, refuse, IPAC_PROTO_SCCP);
 }
 
+static void bsc_nat_send_paging(struct bsc_connection *bsc, struct msgb *msg)
+{
+	if (bsc->cfg->forbid_paging) {
+		LOGP(DNAT, LOGL_DEBUG, "Paging forbidden for BTS: %d\n", bsc->cfg->nr);
+		return;
+	}
+
+	bsc_send_data(bsc, msg->l2h, msgb_l2len(msg), IPAC_PROTO_SCCP);
+}
+
+static void bsc_nat_handle_paging(struct bsc_nat *nat, struct msgb *msg)
+{
+	struct bsc_connection *bsc;
+	const uint8_t *paging_start;
+	int paging_length, i;
+
+	if (bsc_nat_find_paging(msg, &paging_start, &paging_length) != 0) {
+		LOGP(DNAT, LOGL_ERROR, "Could not parse paging message.\n");
+		return;
+	}
+
+	/* This is quite expensive now */
+	for (i = 0; i < paging_length; i += 2) {
+		unsigned int _lac = ntohs(*(unsigned int *) &paging_start[i]);
+		unsigned int paged = 0;
+		llist_for_each_entry(bsc, &nat->bsc_connections, list_entry) {
+			if (!bsc->cfg)
+				continue;
+			if (!bsc->authenticated)
+				continue;
+			if (!bsc_config_handles_lac(bsc->cfg, _lac))
+				continue;
+			bsc_nat_send_paging(bsc, msg);
+			paged += 1;
+		}
+
+		/* highlight a possible config issue */
+		if (paged == 0)
+			LOGP(DNAT, LOGL_ERROR, "No BSC for LAC %d/0x%d\n", _lac, _lac);
+
+	}
+}
+
+
 /*
  * Update the auth status. This can be either a CIPHER MODE COMAMND or
  * a CM Serivce Accept. Maybe also LU Accept or such in the future.
@@ -677,16 +721,7 @@
 	 * message and then send it to the authenticated messages...
 	 */
 	if (parsed->ipa_proto == IPAC_PROTO_SCCP && parsed->gsm_type == BSS_MAP_MSG_PAGING) {
-		int lac;
-		bsc = bsc_nat_find_bsc(nat, msg, &lac);
-		if (bsc && bsc->cfg->forbid_paging)
-			LOGP(DNAT, LOGL_DEBUG, "Paging forbidden for BTS: %d\n", bsc->cfg->nr);
-		else if (bsc)
-			bsc_send_data(bsc, msg->l2h, msgb_l2len(msg), parsed->ipa_proto);
-		else if (lac != -1)
-			LOGP(DNAT, LOGL_ERROR, "Could not determine BSC for paging on lac: %d/0x%x\n",
-			     lac, lac);
-
+		bsc_nat_handle_paging(nat, msg);
 		goto exit;
 	}
 	/* currently send this to every BSC connected */
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c b/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
index 4d1afe2..0a565a9 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
@@ -208,25 +208,23 @@
 	talloc_free(conn);
 }
 
-struct bsc_connection *bsc_nat_find_bsc(struct bsc_nat *nat, struct msgb *msg, int *lac_out)
+
+int bsc_nat_find_paging(struct msgb *msg,
+			const uint8_t **out_data, int *out_leng)
 {
-	struct bsc_connection *bsc;
 	int data_length;
 	const uint8_t *data;
 	struct tlv_parsed tp;
-	int i = 0;
-
-	*lac_out = -1;
 
 	if (!msg->l3h || msgb_l3len(msg) < 3) {
 		LOGP(DNAT, LOGL_ERROR, "Paging message is too short.\n");
-		return NULL;
+		return -1;
 	}
 
 	tlv_parse(&tp, gsm0808_att_tlvdef(), msg->l3h + 3, msgb_l3len(msg) - 3, 0, 0);
 	if (!TLVP_PRESENT(&tp, GSM0808_IE_CELL_IDENTIFIER_LIST)) {
 		LOGP(DNAT, LOGL_ERROR, "No CellIdentifier List inside paging msg.\n");
-		return NULL;
+		return -2;
 	}
 
 	data_length = TLVP_LEN(&tp, GSM0808_IE_CELL_IDENTIFIER_LIST);
@@ -234,29 +232,15 @@
 
 	/* No need to try a different BSS */
 	if (data[0] == CELL_IDENT_BSS) {
-		return NULL;
+		return -3;
 	} else if (data[0] != CELL_IDENT_LAC) {
 		LOGP(DNAT, LOGL_ERROR, "Unhandled cell ident discrminator: %d\n", data[0]);
-		return NULL;
+		return -4;
 	}
 
-	/* Currently we only handle one BSC */
-	for (i = 1; i < data_length - 1; i += 2) {
-		unsigned int _lac = ntohs(*(unsigned int *) &data[i]);
-		*lac_out = _lac;
-		llist_for_each_entry(bsc, &nat->bsc_connections, list_entry) {
-			if (!bsc->cfg)
-				continue;
-			if (!bsc->authenticated)
-				continue;
-			if (!bsc_config_handles_lac(bsc->cfg, _lac))
-				continue;
-
-			return bsc;
-		}
-	}
-
-	return NULL;
+	*out_data = &data[1];
+	*out_leng = data_length - 1;
+	return 0;
 }
 
 int bsc_write_mgcp(struct bsc_connection *bsc, const uint8_t *data, unsigned int length)
diff --git a/openbsc/tests/bsc-nat/bsc_nat_test.c b/openbsc/tests/bsc-nat/bsc_nat_test.c
index 50da1e9..8c0abc2 100644
--- a/openbsc/tests/bsc-nat/bsc_nat_test.c
+++ b/openbsc/tests/bsc-nat/bsc_nat_test.c
@@ -384,12 +384,9 @@
 
 static void test_paging(void)
 {
-	int lac;
 	struct bsc_nat *nat;
 	struct bsc_connection *con;
-	struct bsc_nat_parsed *parsed;
 	struct bsc_config *cfg;
-	struct msgb *msg;
 
 	fprintf(stderr, "Testing paging by lac.\n");
 
@@ -400,34 +397,20 @@
 	bsc_config_add_lac(cfg, 23);
 	con->authenticated = 1;
 	llist_add(&con->list_entry, &nat->bsc_connections);
-	msg = msgb_alloc(4096, "test");
-
-	/* Test completely bad input */
-	copy_to_msg(msg, paging_by_lac_cmd, sizeof(paging_by_lac_cmd));
-	if (bsc_nat_find_bsc(nat, msg, &lac) != 0) {
-		fprintf(stderr, "Should have not found anything.\n");
-		abort();
-	}
 
 	/* Test it by not finding it */
-	copy_to_msg(msg, paging_by_lac_cmd, sizeof(paging_by_lac_cmd));
-	parsed = bsc_nat_parse(msg);
-	if (bsc_nat_find_bsc(nat, msg, &lac) != 0) {
-		fprintf(stderr, "Should have not found aynthing.\n");
+	if (bsc_config_handles_lac(cfg, 8213) != 0) {
+		fprintf(stderr, "Should not be handled.\n");
 		abort();
 	}
-	talloc_free(parsed);
 
 	/* Test by finding it */
 	bsc_config_del_lac(cfg, 23);
 	bsc_config_add_lac(cfg, 8213);
-	copy_to_msg(msg, paging_by_lac_cmd, sizeof(paging_by_lac_cmd));
-	parsed = bsc_nat_parse(msg);
-	if (bsc_nat_find_bsc(nat, msg, &lac) != con) {
+	if (bsc_config_handles_lac(cfg, 8213) == 0) {
 		fprintf(stderr, "Should have found it.\n");
 		abort();
 	}
-	talloc_free(parsed);
 }
 
 static void test_mgcp_allocations(void)