William needed a reliable supply of soldiers to help him rule a holstile country of two million people. The feudal syste mmeant that tenants-in-chief not only swore loyalty but also provided knights to fight for the King. Some paid for tropps but many gave land to knights who in return promised to fight for them when called upon- usually about 40 days.
By about 1100 the Norman King could call upon 5000 knights and other peasant soldiers. The Norman system was an improvement because under the Normans, Knights made an oath so it was a religious duty to serve and under the saxons, thegns had not always carried out military service for their lord.
Wales and Marcher Lords:
Wales was not a united country with a single leader but five kingdoms, each ruled by a warrior prince. So William could not conquer Wales as he had England.
On several occasions William attempted to take over the North and West but failed. The princes swore loyalty to William for his protection. However, they were not very co-operative and the border area was constantly under threat of attack.
In England, William did not want his barons to become too powerful but the border areas were an exception. When he feared invasion, he granted larger areas of land to his most trusted followers. The border area was known as the Marches and so these barons were known as 'Marcher Lords'
Scotland:
William was unable to conquer Scotland, there were constant disputes between the Scots and Normans at the border. At the Treaty of Abernethy in 1072, Malcolm III swore Fealty to William.