diff --git a/microdroid_manager/src/main.rs b/microdroid_manager/src/main.rs
index a53b401..a706dbe 100644
--- a/microdroid_manager/src/main.rs
+++ b/microdroid_manager/src/main.rs
@@ -25,9 +25,7 @@
 use crate::instance::{ApexData, ApkData, InstanceDisk, MicrodroidData, RootHash};
 use crate::vm_payload_service::register_vm_payload_service;
 use android_system_virtualizationcommon::aidl::android::system::virtualizationcommon::ErrorCode::ErrorCode;
-use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::{
-        IVirtualMachineService, VM_BINDER_SERVICE_PORT,
-};
+use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::IVirtualMachineService;
 use android_system_virtualization_payload::aidl::android::system::virtualization::payload::IVmPayloadService::{
     VM_APK_CONTENTS_PATH,
     VM_PAYLOAD_SERVICE_SOCKET_NAME,
@@ -160,8 +158,11 @@
 }
 
 fn get_vms_rpc_binder() -> Result<Strong<dyn IVirtualMachineService>> {
-    get_vsock_rpc_interface(VMADDR_CID_HOST, VM_BINDER_SERVICE_PORT as u32)
-        .context("Cannot connect to RPC service")
+    // The host is running a VirtualMachineService for this VM on a port equal
+    // to the CID of this VM.
+    let port = vsock::get_local_cid().context("Could not determine local CID")?;
+    get_vsock_rpc_interface(VMADDR_CID_HOST, port)
+        .context("Could not connect to IVirtualMachineService")
 }
 
 fn main() -> Result<()> {
diff --git a/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl b/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl
index f2d92af..3fdb48a 100644
--- a/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl
+++ b/virtualizationservice/aidl/android/system/virtualmachineservice/IVirtualMachineService.aidl
@@ -21,12 +21,6 @@
 interface IVirtualMachineService {
     /**
      * Port number that VirtualMachineService listens on connections from the guest VMs for the
-     * VirtualMachineService binder service.
-     */
-    const int VM_BINDER_SERVICE_PORT = 5000;
-
-    /**
-     * Port number that VirtualMachineService listens on connections from the guest VMs for the
      * tombtones
      */
     const int VM_TOMBSTONES_SERVICE_PORT = 2000;
diff --git a/virtualizationservice/src/aidl.rs b/virtualizationservice/src/aidl.rs
index 578960c..297cf68 100644
--- a/virtualizationservice/src/aidl.rs
+++ b/virtualizationservice/src/aidl.rs
@@ -41,22 +41,22 @@
     IVirtualizationServiceInternal::{BnVirtualizationServiceInternal, IVirtualizationServiceInternal},
 };
 use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::{
-        BnVirtualMachineService, IVirtualMachineService, VM_BINDER_SERVICE_PORT,
-        VM_TOMBSTONES_SERVICE_PORT,
+        BnVirtualMachineService, IVirtualMachineService, VM_TOMBSTONES_SERVICE_PORT,
 };
 use anyhow::{anyhow, bail, Context, Result};
 use apkverify::{HashAlgorithm, V4Signature};
 use binder::{
     self, BinderFeatures, ExceptionCode, Interface, LazyServiceGuard, ParcelFileDescriptor,
-    SpIBinder, Status, StatusCode, Strong, ThreadState,
+    Status, StatusCode, Strong, ThreadState,
 };
 use disk::QcowFile;
 use libc::VMADDR_CID_HOST;
 use log::{debug, error, info, warn};
 use microdroid_payload_config::{OsConfig, Task, TaskType, VmPayloadConfig};
-use rpcbinder::run_vsock_rpc_server_with_factory;
+use rpcbinder::RpcServer;
 use rustutils::system_properties;
 use semver::VersionReq;
+use std::collections::HashMap;
 use std::convert::TryInto;
 use std::ffi::CStr;
 use std::fs::{create_dir, File, OpenOptions};
@@ -80,7 +80,8 @@
 
 /// The first CID to assign to a guest VM managed by the VirtualizationService. CIDs lower than this
 /// are reserved for the host or other usage.
-const FIRST_GUEST_CID: Cid = 10;
+const GUEST_CID_MIN: Cid = 2048;
+const GUEST_CID_MAX: Cid = 65535;
 
 const SYSPROP_LAST_CID: &str = "virtualizationservice.state.last_cid";
 
@@ -100,6 +101,19 @@
 
 const UNFORMATTED_STORAGE_MAGIC: &str = "UNFORMATTED-STORAGE";
 
+fn is_valid_guest_cid(cid: Cid) -> bool {
+    (GUEST_CID_MIN..=GUEST_CID_MAX).contains(&cid)
+}
+
+fn next_guest_cid(cid: Cid) -> Cid {
+    assert!(is_valid_guest_cid(cid));
+    if cid == GUEST_CID_MAX {
+        GUEST_CID_MIN
+    } else {
+        cid + 1
+    }
+}
+
 /// Singleton service for allocating globally-unique VM resources, such as the CID, and running
 /// singleton servers, like tombstone receiver.
 #[derive(Debug, Default)]
@@ -136,25 +150,63 @@
 /// The mutable state of the VirtualizationServiceInternal. There should only be one instance
 /// of this struct.
 #[derive(Debug, Default)]
-struct GlobalState {}
+struct GlobalState {
+    /// CIDs currently allocated to running VMs. A CID is never recycled as long
+    /// as there is a strong reference held by a GlobalVmContext.
+    held_cids: HashMap<Cid, Weak<Cid>>,
+}
 
 impl GlobalState {
     /// Get the next available CID, or an error if we have run out. The last CID used is stored in
     /// a system property so that restart of virtualizationservice doesn't reuse CID while the host
     /// Android is up.
-    fn allocate_cid(&mut self) -> Result<Cid> {
-        let cid = match system_properties::read(SYSPROP_LAST_CID)? {
-            Some(val) => match val.parse::<Cid>() {
-                Ok(num) => num.checked_add(1).ok_or_else(|| anyhow!("ran out of CIDs"))?,
+    fn allocate_cid(&mut self) -> Result<Arc<Cid>> {
+        // Garbage collect unused CIDs.
+        self.held_cids.retain(|_, cid| cid.strong_count() > 0);
+
+        // Start trying to find a CID from the last used CID + 1. This ensures
+        // that we do not eagerly recycle CIDs, which makes debugging easier.
+        let last_cid_prop =
+            system_properties::read(SYSPROP_LAST_CID)?.and_then(|val| match val.parse::<Cid>() {
+                Ok(num) => {
+                    if is_valid_guest_cid(num) {
+                        Some(num)
+                    } else {
+                        error!("Invalid value '{}' of property '{}'", num, SYSPROP_LAST_CID);
+                        None
+                    }
+                }
                 Err(_) => {
                     error!("Invalid value '{}' of property '{}'", val, SYSPROP_LAST_CID);
-                    FIRST_GUEST_CID
+                    None
                 }
-            },
-            None => FIRST_GUEST_CID,
+            });
+
+        let first_cid = if let Some(last_cid) = last_cid_prop {
+            next_guest_cid(last_cid)
+        } else {
+            GUEST_CID_MIN
         };
-        system_properties::write(SYSPROP_LAST_CID, &format!("{}", cid))?;
-        Ok(cid)
+
+        let cid = self
+            .find_available_cid(first_cid..=GUEST_CID_MAX)
+            .or_else(|| self.find_available_cid(GUEST_CID_MIN..first_cid));
+
+        if let Some(cid) = cid {
+            let cid_arc = Arc::new(cid);
+            self.held_cids.insert(cid, Arc::downgrade(&cid_arc));
+            system_properties::write(SYSPROP_LAST_CID, &format!("{}", cid))?;
+            Ok(cid_arc)
+        } else {
+            Err(anyhow!("Could not find an available CID."))
+        }
+    }
+
+    fn find_available_cid<I>(&self, mut range: I) -> Option<Cid>
+    where
+        I: Iterator<Item = Cid>,
+    {
+        range.find(|cid| !self.held_cids.contains_key(cid))
     }
 }
 
@@ -162,14 +214,14 @@
 #[derive(Debug, Default)]
 struct GlobalVmContext {
     /// The unique CID assigned to the VM for vsock communication.
-    cid: Cid,
-    /// Keeps our service process running as long as this VM instance exists.
+    cid: Arc<Cid>,
+    /// Keeps our service process running as long as this VM context exists.
     #[allow(dead_code)]
     lazy_service_guard: LazyServiceGuard,
 }
 
 impl GlobalVmContext {
-    fn create(cid: Cid) -> Strong<dyn IGlobalVmContext> {
+    fn create(cid: Arc<Cid>) -> Strong<dyn IGlobalVmContext> {
         let binder = GlobalVmContext { cid, ..Default::default() };
         BnGlobalVmContext::new_binder(binder, BinderFeatures::default())
     }
@@ -179,7 +231,7 @@
 
 impl IGlobalVmContext for GlobalVmContext {
     fn getCid(&self) -> binder::Result<i32> {
-        Ok(self.cid as i32)
+        Ok(*self.cid as i32)
     }
 }
 
@@ -341,8 +393,10 @@
 }
 
 fn handle_stream_connection_tombstoned() -> Result<()> {
+    // Should not listen for tombstones on a guest VM's port.
+    assert!(!is_valid_guest_cid(VM_TOMBSTONES_SERVICE_PORT as Cid));
     let listener =
-        VsockListener::bind_with_cid_port(VMADDR_CID_HOST, VM_TOMBSTONES_SERVICE_PORT as u32)?;
+        VsockListener::bind_with_cid_port(VMADDR_CID_HOST, VM_TOMBSTONES_SERVICE_PORT as Cid)?;
     for incoming_stream in listener.incoming() {
         let mut incoming_stream = match incoming_stream {
             Err(e) => {
@@ -394,22 +448,7 @@
         let global_service =
             BnVirtualizationServiceInternal::new_binder(global_service, BinderFeatures::default());
 
-        let service = VirtualizationService { global_service, state: Default::default() };
-
-        // binder server for vm
-        // reference to state (not the state itself) is copied
-        let state = service.state.clone();
-        std::thread::spawn(move || {
-            debug!("VirtualMachineService is starting as an RPC service.");
-            if run_vsock_rpc_server_with_factory(VM_BINDER_SERVICE_PORT as u32, |cid| {
-                VirtualMachineService::factory(cid, &state)
-            }) {
-                debug!("RPC server has shut down gracefully");
-            } else {
-                panic!("Premature termination of RPC server");
-            }
-        });
-        service
+        VirtualizationService { global_service, state: Default::default() }
     }
 
     fn create_vm_internal(
@@ -538,6 +577,18 @@
             )
         })?;
 
+        // Start VM service listening for connections from the new CID on port=CID.
+        // TODO(b/245727626): Only accept connections from the new VM.
+        let vm_service = VirtualMachineService::new_binder(self.state.clone(), cid).as_binder();
+        let vm_server = RpcServer::new_vsock(vm_service, cid).map_err(|e| {
+            error!("Failed to start VirtualMachineService: {:?}", e);
+            Status::new_service_specific_error_str(
+                -1,
+                Some(format!("Failed to start VirtualMachineService: {:?}", e)),
+            )
+        })?;
+        vm_server.start();
+
         // Actually start the VM.
         let crosvm_config = CrosvmConfig {
             cid,
@@ -565,6 +616,7 @@
                 requester_uid,
                 requester_debug_pid,
                 vm_context,
+                vm_server,
             )
             .map_err(|e| {
                 error!("Failed to create VM with config {:?}: {:?}", config, e);
@@ -1188,17 +1240,6 @@
 }
 
 impl VirtualMachineService {
-    fn factory(cid: Cid, state: &Arc<Mutex<State>>) -> Option<SpIBinder> {
-        if let Some(vm) = state.lock().unwrap().get_vm(cid) {
-            let mut vm_service = vm.vm_service.lock().unwrap();
-            let service = vm_service.get_or_insert_with(|| Self::new_binder(state.clone(), cid));
-            Some(service.as_binder())
-        } else {
-            error!("connection from cid={} is not from a guest VM", cid);
-            None
-        }
-    }
-
     fn new_binder(state: Arc<Mutex<State>>, cid: Cid) -> Strong<dyn IVirtualMachineService> {
         BnVirtualMachineService::new_binder(
             VirtualMachineService { state, cid },
diff --git a/virtualizationservice/src/crosvm.rs b/virtualizationservice/src/crosvm.rs
index 68324c5..33ebd8b 100644
--- a/virtualizationservice/src/crosvm.rs
+++ b/virtualizationservice/src/crosvm.rs
@@ -42,6 +42,7 @@
 use binder::Strong;
 use android_system_virtualmachineservice::aidl::android::system::virtualmachineservice::IVirtualMachineService::IVirtualMachineService;
 use tombstoned_client::{TombstonedConnection, DebuggerdDumpType};
+use rpcbinder::RpcServer;
 
 /// external/crosvm
 use base::UnixSeqpacketListener;
@@ -206,6 +207,9 @@
     /// Handle to global resources allocated for this VM.
     #[allow(dead_code)] // The handle is never read, we only need to hold it.
     vm_context: Strong<dyn IGlobalVmContext>,
+    /// Handle to global resources allocated for this VM.
+    #[allow(dead_code)] // The handle is never read, we only need to hold it.
+    vm_server: RpcServer,
     /// The CID assigned to the VM for vsock communication.
     pub cid: Cid,
     /// The name of the VM.
@@ -239,6 +243,7 @@
         requester_uid: u32,
         requester_debug_pid: i32,
         vm_context: Strong<dyn IGlobalVmContext>,
+        vm_server: RpcServer,
     ) -> Result<VmInstance, Error> {
         validate_config(&config)?;
         let cid = config.cid;
@@ -247,6 +252,7 @@
         Ok(VmInstance {
             vm_state: Mutex::new(VmState::NotStarted { config }),
             vm_context,
+            vm_server,
             cid,
             name,
             protected,
diff --git a/vm_payload/Android.bp b/vm_payload/Android.bp
index dd2a937..6be6f22 100644
--- a/vm_payload/Android.bp
+++ b/vm_payload/Android.bp
@@ -17,6 +17,7 @@
         "liblibc",
         "liblog_rust",
         "librpcbinder_rs",
+        "libvsock",
     ],
     apex_available: [
         "com.android.compos",