A method for implementing a logical network that comprises a set of virtual machines and a logical middlebox on a physical network comprising a plurality of nodes, the method comprising: receiving middlebox configuration data for the logical middlebox; identifying a plurality of host machines to which the middlebox configuration data should be distributed, wherein each host machine in the identified plurality of host machines executes: (i) at least one virtual machine of the set of virtual machines of the logical network; (ii) a managed switching element, MSE, in a hypervisor of the host machine, for implementing a set of logical forwarding elements, LFEs, of the logical network to perform forwarding operations on data packets sent from the virtual machines of the logical network that execute on the host machine; and (iii) a middlebox element, in the hypervisor of the host machine, for implementing the logical middlebox of the logical network to perform non-forwarding operations on data packets sent from the virtual machines of the logical network that execute on the host machine, wherein the plurality of MSEs executing on the plurality of host machines collectively implement the LFEs of the logical network and the plurality of middlebox elements executing on the plurality of host machines collectively implement the logical middlebox of the logical network; and distributing the middlebox configuration data to the plurality of middlebox elements of the identified host machines for implementing the logical middlebox. receiving middlebox configuration data for the logical middlebox; identifying a plurality of host machines to which the middlebox configuration data should be distributed, wherein each host machine in the identified plurality of host machines executes: (i) at least one virtual machine of the set of virtual machines of the logical network; (ii) a managed switching element, MSE, in a hypervisor of the host machine, for implementing a set of logical forwarding elements, LFEs, of the logical network to perform forwarding operations on data packets sent from the virtual machines of the logical network that execute on the host machine; and (iii) a middlebox element, in the hypervisor of the host machine, for implementing the logical middlebox of the logical network to perform non-forwarding operations on data packets sent from the virtual machines of the logical network that execute on the host machine, wherein the plurality of MSEs executing on the plurality of host machines collectively implement the LFEs of the logical network and the plurality of middlebox elements executing on the plurality of host machines collectively implement the logical middlebox of the logical network; and (i) at least one virtual machine of the set of virtual machines of the logical network; (ii) a managed switching element, MSE, in a hypervisor of the host machine, for implementing a set of logical forwarding elements, LFEs, of the logical network to perform forwarding operations on data packets sent from the virtual machines of the logical network that execute on the host machine; and (iii) a middlebox element, in the hypervisor of the host machine, for implementing the logical middlebox of the logical network to perform non-forwarding operations on data packets sent from the virtual machines of the logical network that execute on the host machine, distributing the middlebox configuration data to the plurality of middlebox elements of the identified host machines for implementing the logical middlebox.