Pigeon Express
Messenger birds have been around for a long time, and can travel much faster than a man on horse.
The Romans were good at roads, and with peace comes trading, so it would be in everyone's best interest to establish a good route with inns every 30-40 miles. These would also be great places to house messenger birds, so a message could be written in Rome and sent down the line from bird to bird until it got to the emperor of China.
Edit:
While kind of a joke, there is a protocol for IP over Avian Carrier.
In a race between a pigeon, a car, and Australia's Telestra internet provider, the pigeon transfered a 700 mb video file in 1 hour 5 minutes. The car took 2 hours 10 minutes, and the file upload was estimated to take 4 hours, but kept losing connection.
While slower than light, their carrying capacity is pretty high, and things like maps, diagrams, mathematical calculations, pictures and other non alphanumeric items are much easier to transmit.
With training, pigeons can carry up to 75 g (2.5 oz) on their backs. The German apothecary Julius Neubronner used carrier pigeons to deliver urgent medication. In 1977 a similar carrier pigeon service was set up for the transport of laboratory specimens between two English hospitals.
Pigeons can transmit data on overcast days, and even during the night.
They can also be used in parallel, so that larger messages can be carried between multiple birds, and important messages can be sent via more than one bird at a time to reduce the chance total packet loss.
Pigeons can travel between 600 and 700 miles in a single day, meaning the 5000 mile distance between Rome and Beijing could be traveled in as few as 9 days with only 9 birds.
Pigeons also have an advantage to ground based transportation in that they don't have to worry about terrain.
This is much better than a horse, which as an average galloping speed of 25 miles per hour, and will be slowed by things like swamps, rivers, oceans, mountains, etc.
Most people assume the Pony Express riders galloped their entire route. In fact, the speed of a pony express rider averages out to 10 miles per hour- meaning they spent most of their time alternating between a trot (about 8-9 mph) and a canter (12-13mph). The Pony Express riders switched to fresh horses every 10-15 miles.
Americas
By using a route through northern UK, Iceland, Greenland and northern Canada, it is possible to use carrier birds to send messages into the Americas too.
A China, Siberia, Alaska route would also work with a lot less ocean to cross.