Systems and methods are provided to use a custom tuple definition to route packets of network traffic. Each packet can correspond to a different custom tuple definition based on the custom tuple definitions provided. Each custom tuple definition may be applied to a subset of network traffic based on certain parameters. A stateful network routing service may intercept packets and determine a tuple value for the packet based on a corresponding tuple definition and information from the packet. The stateful network routing service may route the packet based on the tuple value of the packet to a network appliance. Further, subsequent packets associated with the same tuple value may be routed to the same network appliance. In some embodiments, the custom tuple definition may be used to determine multiple tuple values for a subset of network traffic.