Computer networks are becoming increasingly important in supporting business and everyday activities. In particular, the Internet has become part of the critical infrastructure and has a strategic importance in our society and in the digital economy. These developments have led to a highly dynamic network utilization, where traffic fluctuations and seemingly random and anomalous traffic patterns are commonly manifested and hard to diagnose. In order to ensure the protection and resilience of such networks, it is necessary to better analyze and observe network traffic. Thus, anomaly diagnosis aims to discover and characterize critical anomalies affecting the network infrastructure, where the source of these anomalies may be deliberately malicious (e.g. attacks) or unintentional (e.g. failures, misconfigurations or legitimate but abnormal use of the network such as in flash crowds). However, although there is a multitude of algorithms and techniques looking at different elements of the analysis of network traffic anomalies, most research typically focuses on a specific aspect or methodology and there is very little regard for the overall context. This survey aims to present a comprehensive investigation of the current state of the art within the network anomaly diagnosis domain, in particular for Internet backbone networks. We decompose the overall anomaly diagnosis problem spectrum into four main dimensions, namely, processing costs, diagnosis granularity, theoretical methodologies and traffic features. Subsequently the anomaly diagnosis research area is structured further and an overview of the most relevant research is provided by individually reviewing each component of the problem spectrum and proposed solutions with a deeper focus on methodologies and features. Further, we also present and review seminal pieces of work that are considered cornerstones of the anomaly diagnosis research domain.