How to handle ThreadPool hitting the server connection limit

I could be asking a design pattern question here.

On Android, I am using a thread pool to open 8 threads to download some files.

    try {
        ExecutorService pool = Executors.newFixedThreadPool(8);
        for (int i = 0; i < someList.size(); i++) {
            pool.submit(new DownloadJsonTask(someList.get(i), context));
        }
        pool.shutdown();
        pool.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);
    } catch (Exception e) {
    }

I noticed if I use one thread to download one-by-one, then I hardly get download fails but if I use 8 threads, then I sometimes get download fails. I am not a server/network person so I don't know in detail but I am guessing the server is putting a limit of one device (or one IP address) trying to connect multiple connections.

If this is the reason, then how do I design the code to overcome this issue? I have already implemented to try downloading 3 times before failing. It does seem to fixed it "for now". However, I know my code is not robust and it can fail at one point.

I figured, I wouldn't be the first one facing this issue. I would like to know a robust solution around this issue.

Solutions I could think of:
- Try to download at least 3 times before failing
- Once failed, then try to sleep for a random amount of time. So that failed threads don't wake up at the same time and fail again. - If the server throws come kind of unique message back such as Server busy, then re-try unlimited(?)(large amount of) times.

I have not yet implemented above possible solutions. I want to know the common/best solution first and spend time implementing it.

Any ideas?