Block-cipher based vs Hash based MAC When it comes to MAC algorithms one can have many choices. CBC-MAC, CMAC, PMAC etc are some MAC algorithms that rely on block ciphers (ex AES) to generate a MAC. On the other hand HMAC is very popular on the Internet and relies on compression functions (ex SHA-1, MD5). 

What are the drawbacks of each from a security perspective and how do you make a choice if you need to include MAC in your protocol?
Here are some advantages and disadvantages for each of the three classes of MACs, which I know about:

Based on block cipher

There are constructions where the security of the MAC is proven in terms of the security definition of a block cipher. This means as long as the block cipher is secure, the MAC will be secure.

There are constructions where encryption and MAC can be computed with almost no extra CPU cost compared to only encrypting.

Based on cryptographic hash (HMAC)

Assuming the underlying hash is secure, a HMAC guarantees that even an adversary who knows the key cannot produce two different messages for which the same HMAC value would be valid. Neither could an adversary produce a HMAC value which would be valid with two different keys.

One disadvantage is that security of HMAC cannot be proven based on the usual properties regarding collisions of the underlying hash. There could exist a secure cryptographic hash which would lead to an insecure MAC if used in an HMAC. Put differently, HMAC could be broken without ever finding a collision in the underlying hash.

Based on almost 2-universal classes of hash functions

This kind of MAC is provably secure.

Like a one-time-pad, this kind of MAC consumes key material. You will need some key material, that is used only for a single message.

Unlike a one-time-pad, the number of bits consumed does not grow with the message size. You can authenticate an arbitrarily large message using a constant number of key bits from your pool. (The key material also has a reusable part, that grows logarithmically in message size.)

Public key signatures based on cryptographic hash

It is possible to construct a public key signature using a cryptographic hash as the only underlying primitive. These can be proven secure based on the usual assumptions about the security of the underlying cryptographic hash.

A major drawback is that they are expensive to compute, and the signatures require a huge number of bits compared to other public key algorithms.

This is not really a MAC, because it is using asymmetrical keys. A signature could be used in place of a MAC, if it wasn't so expensive. The CPU time needed and the number of bits in a signature is prohibitive in many of the situations, where a MAC would be used.