The Visigoths consolidated a kingdom spanning most of Iberia and Gaul. For the next two centuries, they warred not only amongst themselves in a sequence of succession crises – which followed the election of a new king after every royal death, but also against the Byzantine Empire, which was trying to regain lost territory in the south, the Arian Suevi trying to preserve their hold on Gallaecia, and the Franks pushing south against them from Gaul. The Visigoth military structure was highly decentralised – the great territorial magnates, the "duces" (dukes), maintained their own armies, as in all the great Germanic kingdoms of Europe at the time. These armies rarely cooperated in campaigns. At the Battle of Vouillé in 507, the Franks under Clovis I wrested control of Aquitaine from the Visigoths. The Visigoths lost all of their territory north of the Pyrenees except the province of Gallia Narbonensis. The first half of the 6th century was largely a failure for the Visigoths. They failed to hold onto their Gallic possessions, they failed to oust the Suevi, and they failed to repulse the Byzantine Empire when it first endeavoured to reassert control over its Iberian provinces, taking advantage of a local rebellion. In 554, Granada and southernmost Hispania Baetica were taken from the Byzantines; under the last Arian king, Leovigild, the Suevi kingdom was annexed in 585 and the war of reconquest against the remainder of the Byzantine territories was begun, finally being completed under King Suintila in 624. The Visigoths faced no serious external threat from then on until the sudden Moorish invasion of 711.