A technique is provided for one or more network nodes to deterministically select data flows to preempt. In particular, each node employs a set of predefined rules which instructs the node as to which existing data flow should be preempted in order to admit a new high-priority data flow. The rules are precisely defined and are common to all nodes configured in accordance with the present invention. Illustratively, a network node not only selects a data flow to preempt, but additionally may identify other “fate sharing” data flows that may be preempted. As used herein, a group of data flows has a fate-sharing relationship if the application instance(s) containing the data flows functions adequately only when all the fate-shared flows are operational. In a first illustrative embodiment, after a data flow in a fate-sharing group is preempted, network nodes may safely tear down the group's remaining data flows. In a second illustrative embodiment, when a data flow is preempted, all its fate-shared data flows are marked as being “at risk.” Because the at-risk flows are not immediately torn down, it is less likely that resources allocated for the at-risk flows may be freed then subsequently used to establish relatively lower-priority data flows instead of relatively higher-priority data flows.