“NATO’s member states are willing to defend one another, and they have the troops and the equipment to do so. But quickly getting those troops and equipment to their destination is a different matter altogether. In some new NATO member states, bridges and railroads are simply not suitable for large troop movements. But one thing frustrates commanders even more: the arduous process of getting permission to move troops across borders.

“I was probably naïve,” admits Lieutenant General Ben Hodges, the commander of the U.S. Army in Europe. “I assumed that because these were NATO and EU countries we’d just be able to move troops. But ministries of defense are not responsible for borders.”

At their upcoming summit in Warsaw, NATO members will discuss joint responses to Russian aggression, and they are likely to agree to station four battalions—totaling about 4,000 troops—in the Baltic states and Poland. But with Russia forming two new divisions in its western military region, which borders the Baltic states, 4,000 forward-stationed troops may not be enough to deter a potential attack. (A division consists of 10,000 to 20,000 troops.)

Indeed, “if NATO’s emerging forward enhanced presence is going to be more than a symbolic tripwire,” Ian Brzezinski, a deputy assistant secretary of defense under George W. Bush who is now a senior fellow at the Atlantic Council, told me, “NATO will have to conduct brigade- to division-level enforcement exercises in the Baltic region.”

And beyond deterrence, if a member state were attacked, NATO commanders would need to quickly pull together troops from different corners and bring them across Europe to their destination, which would most likely be a new NATO member state.

And there’s the complication. Moving troops across Europe requires permission at each border. “During the Cold War, we had pretty good plans to rapidly move across borders, but until [the 2014 NATO summit in] Wales we didn’t have similar plans for new NATO member states,” says a NATO official knowledgeable with the issue. “Right after Crimea we sent out a questionnaire about [border regulations] to each member states, and the results were pretty scary. Some countries needed to recall parliament in order to let NATO units cross their borders. And one country said, ‘we can only have 1,600 soldiers on our soil.’” In reality, that meant that NATO would be unable to use that member state, which the NATO official declined to identify, for passage.

Since then, NATO has made impressive progress. It has tripled the size of its 13-year-old NATO Response Force (NRF), which can muster up to 40,000 troops and is, at least in theory, able to deploy quickly to new NATO member states as well as old ones. And all of its member states have agreed to pre-clearance—the military version of a green card for troops and equipment—although it is not clear how the system will work in practice. As the NATO official reports, “some countries say ‘we don’t need any advance notice for pre-clearance,’ while others say they need four to five days’ notice.” According to the official, in most of NATO’s eastern-facing countries, getting the clearance would be a matter of five days or fewer, although one country—he declined to specify which one—still requires more time.

And so, although Hodges and his fellow commanders know how fast their troops can physically move, they have little idea whether crossing borders will take five days, two days, or perhaps just hours. “An official [in an eastern European NATO member state] told me, ‘I hope we can get this [clearance] done quickly,’” Hodges reports. “But you can’t plan based on hopes and wishes.”

SACEUR, NATO’s Supreme Allied Command in Europe, does, however, have clearance for access to Polish and Baltic airspace. And according to a NATO spokesperson, almost all NATO member states now have legislation in place for the deployment of the alliance’s 5,000-man VJTF rapid response force, usually referred to as the Spearhead Force. The VJTF, established at the 2014 Wales Summit, is NATO’s rapid response to any attack on a member state’s territory. It operates on a rotational basis and does not have a permanent home. The reaction time of the quickest units of the VJTF will be measured in hours, and the first troops will deploy to the crisis area within 48 hours.

In late May, the Spearhead Force conducted a 2,500-man Brilliant Jump exercise, which focused on the logistics of moving from Spain to Poland within four days. It succeeded, but the question is what will happen when more new NATO members’ borders, and larger numbers of troops, are involved. Estonia, for one, is trying to speed up diplomatic clearance. “[At the end of May] I had a regular Baltic defense ministers’ meeting with my Latvian and Lithuanian colleagues, where we also discussed how to achieve progress in making the Allied troops movement in the Baltic region simpler and faster,” Estonian Defense Minister Hannes Hanso told me. “We agreed to continue the work on simplifying the relevant procedures and regulations. Estonia has already eased its regulations about requesting the entry permissions for military vessels and aircraft.” According to the new regulations, the permission must be granted within seven working days, though Hanso says that in practice the procedure usually takes only a few days, and in urgent cases the permit can be issued within hours.