Faz um certo tempo que descrevi neste post que o UDP estava sofrendo algum tipo de shaping no Velox, o que acabava afetando o Skype.
A solução paliativa era impedir o tráfego UDP entrante, forçando o uso de TCP. O Skype fica "esquisito", a ligação cai mais, provavelmente sobrecarrega o interlocutor, mas a opção é não usá-lo.
Nesta semana, testei o Skype com UDP liberado e funcionou perfeitamente, com nenhuma perda de pacotes, em diversos dias e horários diferentes. Parece que o shaping foi removido ou abrandado.
