Our previous experience building systems for middlebox chain composition and scaling in software-defined networks has revealed that existing mechanisms of flow annotation commonly do not survive middlebox-traversals, or suffer from extreme identifier domain limitations resulting in excessive flow table size. In this paper, we analyze the structural artifacts resulting in these challenges, and offer a framework for describing the behavior of middleboxes based on actions taken on traversing packets. We then present a novel mechanism for flow annotation that features an identifier domain significantly larger than existing techniques, that is transparent to hosts traversed, and that conserves flow-table resources by requiring only a small number of match rules and actions in most switches. We evaluate said technique, showing that it requires less per-switch state than conventional techniques. We then describe extensions allowing implementation of this architecture within a broader class of systems. Finally, we close with architectural suggestions for enabling straightforward integration of middleboxes within software-defined networks.