The start of the second millenium was a period when Scotland and England were both establishing. Several Scottish kings (for instance Malcolm III and his son David I)tried to expand control further south. After the Norman invasion it looked at first like the border might be basically the line between their two new castles built in Carlisle and Newcastle but certainly no further south than that. The Scots looked to push south but events like the death of Malcolm then later David I losing the Battle of the Standard hindered the Scottish advances. I suspect that as well as events a defining factor in the end might simply be the lay of the land. The border in the east of the country as it is follows natural boundaries. That is the River Tweed then the Cheviot Hills which run across the country rather than north to south. You have the fertile Scottish border valleys north of the Cheviots and the much hillier less agricultural land south of the Cheviot line. So in the end how much resource and trouble would Scotland be prepared to go to in order to try and grab the hills and moors between Carter Bar and Newcastle?