The link is only as strong as it's weakest... link? Anyway, given the structure of internet, I wouldn't say it is O(N*M), more like O(the number of major ISPs).