A determination is made that network access between a virtualized graphics device and a compute instance of a client is to be enabled. A source network address for graphics-related traffic of the compute instance is identified. From a range of source port numbers associated with the source network address, a particular source port number which is unused is found. Routing metadata is transmitted to one or more routing devices indicating that a key based at least in part on (a) the source network address and (b) the particular source port number is to be used to identify a route for network packets from the first application compute instance to a virtualized graphics device.