Some embodiments provide, for a gateway datapath that executes on a gateway device to implement tenant logical routers for multiple different tenant logical networks and process traffic between the tenant logical networks and an external network, a method for managing QoS for the plurality of tenant logical networks. The method receives a data message for a particular tenant logical network. The method executes a set of processing stages to process the data message. The set of processing stages includes a processing stage for a particular tenant logical router of the particular tenant logical network. As part of the processing stage for the particular tenant logical router, the method uses a QoS data structure specific to the particular tenant logical router to determine whether to allow the data message. The gateway device stores at least one separate QoS data structure for each of a set of the tenant logical routers.