A method for a network controller, wherein the method is for configuring a logical middlebox that provides middlebox service to a logical network implemented across a plurality of hosts, the method comprising: assigning a first set of connection identifiers to a first middlebox instance of a plurality of middlebox instances (125,130,135,140) that operate in the plurality of hosts to implement the logical middlebox for the logical network which logically connects a plurality of virtual machines (VM1-VM3) through a set of logical forwarding elements, each host executing a managed forwarding element that implements one or more of the logical forwarding elements that logically connect a subset of virtual machines operating in the host to each other and to other virtual machines operating in other hosts, the first middlebox instance operating in a first host of the plurality of hosts; assigning a second set of connection identifiers to a second middlebox instance of the plurality of middlebox instances (125,130,135,140), the second middlebox instance executing on a second host of the plurality of hosts, wherein the first set of connection identifiers comprises different identifiers than the second set of connection identifiers; configuring the first middlebox instance to associate a first connection identifier from the first set of connection identifiers with a first packet originating from a first virtual machine operating in the first host and logically attached to a first logical switch of the logical network, so that the first packet is modified to include the first connection identifier; and configuring the second middlebox instance to associate a second connection identifier from the second set of connection identifiers with a second packet originating from a second virtual machine operating in the second host and also logically attached to the first logical switch, so that the second packet is modified to include the second connection identifier, wherein the first and second packets are both sent to a third virtual machine operating in a third host of the plurality of hosts and logically attached to a second logical switch of the logical network, wherein the third host receives the first and second packets and uses the first and second connection identifiers to distinguish between sources of the first and second packets when the first and second packets have identical source network-layer addresses. assigning a first set of connection identifiers to a first middlebox instance of a plurality of middlebox instances (125,130,135,140) that operate in the plurality of hosts to implement the logical middlebox for the logical network which logically connects a plurality of virtual machines (VM1-VM3) through a set of logical forwarding elements, each host executing a managed forwarding element that implements one or more of the logical forwarding elements that logically connect a subset of virtual machines operating in the host to each other and to other virtual machines operating in other hosts, the first middlebox instance operating in a first host of the plurality of hosts; assigning a second set of connection identifiers to a second middlebox instance of the plurality of middlebox instances (125,130,135,140), the second middlebox instance executing on a second host of the plurality of hosts, wherein the first set of connection identifiers comprises different identifiers than the second set of connection identifiers; configuring the first middlebox instance to associate a first connection identifier from the first set of connection identifiers with a first packet originating from a first virtual machine operating in the first host and logically attached to a first logical switch of the logical network, so that the first packet is modified to include the first connection identifier; and configuring the second middlebox instance to associate a second connection identifier from the second set of connection identifiers with a second packet originating from a second virtual machine operating in the second host and also logically attached to the first logical switch, so that the second packet is modified to include the second connection identifier, wherein the first and second packets are both sent to a third virtual machine operating in a third host of the plurality of hosts and logically attached to a second logical switch of the logical network, wherein the third host receives the first and second packets and uses the first and second connection identifiers to distinguish between sources of the first and second packets when the first and second packets have identical source network-layer addresses.