The mode of operation employed by Computational Data Centres that offer Utility Computing differs significantly from that of traditional supercomputers and server clusters and as such present new architectural problems that should be studied and solved. In this paper we concentrate on issues facing the interconnection network. We argue that this is a part of the overall architecture where shortcomings in present day solutions are most severe and present a model for the mode of operation of a Utility Computing Data Centre where virtualisation is a main ingredient. Based on this model we identify several areas where the interconnection network faces new challenges and needs new solutions. In each of these areas we give a brief introduction to previous results before we identify the new challenges.