I'm developing a multiplayer Android game with push notifications by using Google GCM.
My web server has a REST API. Most of the requests sent to this API send a request to Google GCM server to send a notification to the opponent.
The thing is on average, a call to my API is ~140 ms long, and ~100 ms is due to the http request sent to Google server.
What can I do to speed up this? I was thinking (I have full control of my server, my stack is Bottle/gunicorn/nginx) of creating an independent process with a database that will try to send a queue of GCM requests, but maybe there's a much simpler way to do that directly in bottle or in pure python.
The best thing you can do is making all networking asynchronous, if you don't do this yet.
The issue is that there will always be users with a slow internet connection and there isn't a generic approach to bring them fast internet :/.
Other than that, ideas are to

send only few small packets  or one huge in favor of many small packets (that's faster)
use UDP over TCP, UDP being connectionless and naturally faster
Avoiding a 100ms http request to slow down the REST API where it's called from