Transactions are not required to include a fee. Zero fee transactions are fine, and will make it into blocks rather quickly if they have a sufficiently high priority (input age).

The DoS prevention measures are enacted by the enforcing the dust limit (min transaction relay fee), based on the cost to the network to spend the coins.