A virtual LAN (VLAN) has a number of segments connected by a connection-based network. A method for providing differentiated service to frames having different user priorities in a VLAN carries frames associated with different user priorities over different channels in the connection-based network. The connection-based network may be an ATM network in which channels are specified by a connection identifier which may comprise a VPI/VCI pair. A bridge according to the invention has one or more bridge ports. Each of the bridge ports may be associated with a VPI. The bridge ports may each be associated with a plurality of service interfaces each capable of terminating a connection in the connection-based network. The service interfaces may each be associated with a VCI. Priority tagged frames received at the bridge port are mapped to service interfaces on the basis of their user priorities.