У вас есть пара вариантов, два наиболее очевидных из которых: либо клиент вызывает метод, который запускает задание и запрашивает у сервера состояние, либо настраивает обратный вызов.
В любом случае задание должно выполняться в отдельном потоке, чтобы оно не блокировало службу.
Если вы идете с опросом для определения состояния маршрута, поместите фактический результат в возвращаемый статус.
Если вы используете обратный вызов, используйте WSDualHttpBinding и настройте обратный вызов. Это выглядит немного страшно для настройки, но на самом деле все не так плохо.
Я позволю кому-то еще присоединиться к реальным шаблонам или структурам, я просто не уверен. Кроме того, проверьте MSMQ, это может быть другое жизнеспособное решение.