It has been a grim couple of weeks for the snack lovers of Camp Phoenix. First Doritos, then Snickers, now Coca-Cola: all have disappeared from the usually packed shelves of the camp store. They were among the more expendable supplies lost when the Pakistani Taleban set fire to containers bound for US bases in Afghanistan close to the Khyber Pass.

The denuded shelves underline a far more serious problem for the US: how to fuel the military effort in Afghanistan in the face of diminishing regional leverage and growing opposition from neighbours.

Weeks of attacks by the Taleban on convoys from Karachi to the Khyber Pass and the decision by Kyrgyzstan to close the only US airbase in the region have left the US scrambling to find new routes at the very moment it is planning an influx of 17,000 troops.

The search has taken the US right into the backyard of Russia, in Central Asia. Yesterday Uzbekistan confirmed that it would allow non-military cargo bound for Afghanistan to be transported through its territory. President Berdymukhamedov of Turkmenistan also said that his country would be willing to give passage to humanitarian cargo. In return he is likely to expect the volume to be lowered on the dubious human rights record of his country.

What Washington has yet to prise out of Central Asia, however, is a permanent base such as the one it stands to lose at Manas after Russia offered $2 billion (£1.5 billion) in aid to Kyrgyzstan.

“Russia views Central Asia as its unique sphere of influence,” Alex Neill, an Asia analyst at the Royal United Services Institute in London, said. “It doesn’t want Nato there any more than it wants them in Eastern Europe.”

Russia has also agreed to allow its territory to be used for the transit of non-military supplies to Afghanistan.

“The prospect of failure in Afghanistan has made the relationship between Russia and Nato more businesslike,” Christopher Langton, a senior Fellow at the International Institute for Strategic Studies, said.

The land route in effect gives Russia control of a critical supply corridor. Earlier this month President Medvedev said that Moscow was ready for “fully-fledged, comprehensive co-operation” on Afghanistan but went on to imply that its help was contingent on US concessions on Nato expansion and US plans for a missile defence system in Eastern Europe.

Islamabad’s capitulation to the Taleban over the Swat Valley has raised fears that the Pakistan route, which accounts for 75 per cent of supplies, could soon be closed.

“The Taleban know if they make a pincer movement they can choke off that access completely,” Mr Neill said. “The options for the US are closing rapidly.”

That is why, for the first time, people are thinking the unthinkable: Iran. Last week a US Nato commander said that individual member countries could seek supply routes through Iran.

The US, when it went into Afghanistan, did not predict the turn of events in Pakistan. The search for new roads may force it to entertain alliances every bit as unexpected.