Caledonia is the Latin name given by the Romans to the land in today's Scotland, north of their province of Britannia, beyond the frontier of their empire. The etymology of the name is probably from a P-Celtic source. Its modern usage is as a romantic or poetic name for Scotland as a whole, comparable with Hibernia for Ireland and Cambria for Wales.
After being captured, Commodus was sold to Monitor tribe, and the XIV Legion was sent in to rescue him. Marius commented that the most elite of Romes' legion attempted and failed to conquer the country. The aggression received from Caledonia caused Rome to build a wall between Caledonia and Britannia.
Caledonia on Wikipedia