1. A non-transitory machine readable medium of a controller of a network control system for configuring a plurality of middlebox instances to implement a logical middlebox in a distributed manner in a plurality of hosts, the non-transitory machine readable medium storing sets of instructions for: assigning a first set of connection identifiers to a first middlebox instance of a plurality of middlebox instances that implement the logical middlebox in the plurality of 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, the second middlebox instance operatin in a second host of the plurality of hosts; and configuring (i) the first middlebox instance to associate one of the first set of connection identifiers with a first packet originating from a first virtual machine operatin in the first host and (ii) the second middlebox instance to associate one of the second set of connection identifiers with a second packet originating from a second virtual machine operatin in the second host, in order for a third host of the plurality of hosts that receives the first and second packets to distinguish between sources of the first and second packets when the first and second packets have identical source network addresses.