A method for a network controller to configure a physical network comprising a set of physical nodes (155,160,165) that implement a logical network comprising a set of logical forwarding elements (105,110,115) that connect a set of end machines (120, 125, 130, 135), wherein each logical forwarding element (105,110,115) in the set is implemented by a plurality of physical managed forwarding elements (715, 735) in a distributed manner in the physical network, the method characterized by: configuring a logical middlebox as a part of the logical network by: receiving a set of configuration data for the logical middlebox; using a set of tables stored by the network controller that describe physical locations of the end machines (120,125,130,135) to identify a plurality of nodes (155,160,165) that host at least a subset of the end machines (120,125,130,135) of the logical network; and distributing the logical middlebox configuration to the identified nodes (155,160,165) that host the end machines (120,125,130,135) of the logical network in order to implement the logical middlebox configuration on the identified nodes (155,160,165), wherein the logical middlebox is implemented in a distributed manner by middlebox elements on the plurality of identified nodes (155,160,165), and wherein each of the identified nodes (155,160,165) operates a physical managed forwarding element (715, 735) for implementing the logical forwarding elements (105,110,115) and a middlebox element for implementing the logical middlebox. configuring a logical middlebox as a part of the logical network by: receiving a set of configuration data for the logical middlebox; using a set of tables stored by the network controller that describe physical locations of the end machines (120,125,130,135) to identify a plurality of nodes (155,160,165) that host at least a subset of the end machines (120,125,130,135) of the logical network; and distributing the logical middlebox configuration to the identified nodes (155,160,165) that host the end machines (120,125,130,135) of the logical network in order to implement the logical middlebox configuration on the identified nodes (155,160,165), wherein the logical middlebox is implemented in a distributed manner by middlebox elements on the plurality of identified nodes (155,160,165), and wherein each of the identified nodes (155,160,165) operates a physical managed forwarding element (715, 735) for implementing the logical forwarding elements (105,110,115) and a middlebox element for implementing the logical middlebox. receiving a set of configuration data for the logical middlebox; using a set of tables stored by the network controller that describe physical locations of the end machines (120,125,130,135) to identify a plurality of nodes (155,160,165) that host at least a subset of the end machines (120,125,130,135) of the logical network; and distributing the logical middlebox configuration to the identified nodes (155,160,165) that host the end machines (120,125,130,135) of the logical network in order to implement the logical middlebox configuration on the identified nodes (155,160,165), wherein the logical middlebox is implemented in a distributed manner by middlebox elements on the plurality of identified nodes (155,160,165), and wherein each of the identified nodes (155,160,165) operates a physical managed forwarding element (715, 735) for implementing the logical forwarding elements (105,110,115) and a middlebox element for implementing the logical middlebox.