Albania and Croatia are set to receive formal invitations to join. Macedonia is hoping to follow suit. And Ukraine and Georgia, both former Soviet republics that now have Western-leaning governments, are looking to receive Membership Action Plans (MAP), the first step toward becoming full-fledged NATO members. Outgoing President Vladimir Putin will be present at the Bucharest events, even as NATO-Russian relations are under heavy strain.

Despite frequent calls by Ukrainian politicians (as recently as January 2008) for Russia to moves its navy and troops out of the Ukraine, the Russians have nowhere to go. On January 18, Ukrainian Foreign Minister Volodymyr Ohryzko handed in a request for Kiev to join NATO's Membership Action Plan to the alliance's secretary general, Jaap de Hoop Scheffer. The Action Plan is a necessary step for countries wishing to eventually become full members of NATO. Russia reacted strongly, saying any move toward NATO would "exacerbate Russian-Ukrainian relations in many areas". Russia’s naval presence in the Black Sea is determined by the willingness of the Ukrainian Government to tolerate the continued Russian occupation of its naval bases at Simferopol and Odessa. If Russia loses control of these the Russian Navy will have no southern ports. The Russian Black Sea Fleet is based on Ukraine's Crimean peninsula. It is headquartered at Sevastopol', with an additional home port in Odessa. Russian interest in the Black Sea goes back over two hundred years when Catherine the Great annexed the Crimea in 1783, and subsequently established a Russian naval base at Sevastopol.

When the Soviet Union fell apart the Black Sea Fleet became an object of contention between Russia and Ukraine when the Ukraine declared its independence. The Ukraine rents facilities in its port of Sevastopol to the 250-ship Russian Black Sea fleet. Ukrainian naval forces, with about 160 vessels, are based to the south in the port of Donuzlav. Although Ukraine had no use for a blue-water navy and cannot afford to maintain one, it was reluctant to surrender its share of the fleet, both of whose home ports are in Ukraine, to a larger neighbour with a tradition of domination. Ukraine wanted its share of the ships it found in the Ukraine after its declaration of independence.

There was a lot or arguing and threats by nationalist politicians on both sides. Were the Ukrainian sailors on Russian ships in the Ukraine Russians or Ukrainians? Were these vessels Russian or Ukrainian?  The presidents of Russia and Ukraine reached agreement in August 1992 under which the fleet and ports would be under joint command of Russia and Ukraine for 3 years. At the Tashkent summit, Russia agreed to cede to Ukraine a certain portion of the former Soviet Union's weapons, units, and sites.

According to Global Security, by 1995, the fleet had approximately 48,000 naval and marine personnel, 14 submarines, 31 surface ships, 43 patrol and coastal ships, 125 combat aircraft, and 85 helicopters. Equipment covered by the CFE Treaty included one coastal defence division with 175 tanks, 450 armoured infantry fighting vehicles, and 72 artillery pieces. The fleet also contained a naval infantry brigade with 50 tanks, 218 ACVs, and 45 artillery pieces. Based in the Odessa Military District in the Crimea, this fleet was manned predominantly by Russian sailors and officers. The fleet's Russian commander and its senior officers resisted any partition and transfer to Ukraine.

On 25 November 1995 Russia and Ukraine reached an agreement on division of the Black Sea Fleet, under which Ukraine would receive 150 naval installations of the fleet. Another agreement in February 1996 fell apart two months later, when Russian Defence Minister Pavel Grachev stopped the division because of controversy over where the Russian fleet would be based.

After nearly five years of controversy, on 28 May 1997 Moscow and Kiev finally settled their dispute over the Black Sea Fleet, when Prime Ministers Chernomyrdin and Lazarenko signed three intergovernmental agreements. The two sides agreed to divide the fleet's assets and to lease port facilities in Sevastopol to the Russian Navy. Under the agreement the two nations split the fleet's ships evenly, though Russia agreed to buy back some of the more modern ships with cash. Thus Russia ultimately received four-fifths of the Black Sea Fleet's warships, while Ukraine received about half of the facilities.

The two leaders agreed that Russia would rent three harbours for warships and two airfields for a twenty-year period, for a payment of about $100 million annually. Sevastopol, which had been partly under Russian control, was given to Ukraine. Russia will keep its portion of the former Soviet fleet for 20 years in several bays at Sevastopol, and the Ukrainian navy will also be stationed at a bay there. Russians leased the Saki shore carrier flight training facility on the Crimean Peninsula prior to the re-deployment of the Kuznetsov to the Northern Fleet. Russia agreed to station no more than 25,000 military personnel at the bases, and that it would place no nuclear weapons at the leased facilities. A result of the division of the Black Sea Fleet between Ukraine and the Russian Federation, armaments and equipment of the Coastal Defence Forces and Naval Infantry assigned to the Russian Federation were subject to withdrawal from the territory of Ukraine.

Russia has substantial commitments in the area with its former headquarters at Sevastopol and major construction yards at Nikolayev which produced four Kiev class carriers and the more recent conventional carrier Admiral Kuznetsov. Moreover, the Black Sea has been a research and development ground for numerous ships, aircraft, hydrofoils, hovercraft, wing-in-ground effect platforms, and weapons systems.  The Russian substitute base at Novorossiysk has yet to be developed and is subject to heavy icing.

That means that the Russians are facing the chance that a government in the Ukraine, hostile to the Russians, may ask the Russians to take their ships, men and support groups home; to remove them from the Crimea. That would be a strategic blow to Russia and would dramatically change the power dynamic in the region. That is why Russia has consistently sought to protect its ‘friends’ in the Ukraine, especially after the ‘Orange Revolution’. Russia will do everything it can to assure its continued safe harbour for the Black Sea Fleet and avoid the Ukraine’s entrance into NATO which will see the removal of Russian ships and troops from the Ukraine and their possible replacement by elements of the US Sixth Fleet.

Even as it stands, the bases in the Ukraine are not entirely satisfactory. While the Black Sea has perhaps the most pleasant climate in all of the Former Soviet Union, it has possibly the worst strategic location of all the four fleets. The only exit from the Black Sea is through the 180 mile long Turkish-controlled Turkish Straits. The straits are composed, from NE to SW, of the Bosporus, the Sea of Marmara and the Dardanelles. In the Bosporus, at the northern end of the straits, ships must navigate a passage that narrows to as little as 800 yards before the Sea of Marmara is reached. After the Sea of Marmara, ships transit the final 40 miles of the straits, the Dardanelles, which are from one to four miles wide.

In addition to the great geographic restrictions on transit, there are legal restrictions as well. Under the 1936 Montreux Convention, Turkey must be notified eight days before a transit through the straits. Aircraft carriers are not allowed to transit and submarines must transit the straits on the surface. Such a restriction, however, did not prevent illegal transit of the first Kiev carrier in 1976.

Once through the straits, ships must pass through the Aegean Sea. It is dotted with approximately 2500 small islands and is controlled/patrolled by the Greek and Turkish Navies, which are equipped with specially designed ships and boats to operate in such areas at great speeds. Sovereignty over the islands, including Cyprus, is one of the causes of on-going tensions between the Greeks and Turks. Further, one should note that both states are members of NATO.

Russia has found it difficult to negotiate with the Ukraine. It has used it energy resources to blackmail the Ukrainians to pay ever higher prices for gas. Indeed, it has cut off energy supplies to the Ukraine. It has intervened in the internal politics of the Ukraine by supporting opponents of Ukrainian President Viktor Yushchenko and Yulia Tymoschenko with cash, threats and bullying. Many pro-Western Ukrainian politicians have attacked the Russians for their excesses and violations of 1997 treaty.

Many Ukrainian Atlanticists believe Russian military presence poses a serious obstacle to North Atlantic Treaty Organization membership. Pro-Western elites in Ukraine, who have been in power since last year, have set NATO membership as a major foreign policy goal.  After Ukrainian independence from the Soviet Union in 1992, much of the Black Sea Fleet infrastructure and personnel fell under Ukrainian jurisdiction, but conflicts immediately arose, as many officers expressed loyalty to Russia.

Moscow and Kiev decided to sign a treaty providing for joint command of the fleet, but ultimate power was always in Russian hands. In 1997 a decision was taken to establish two separate Black Sea fleets and evenly distribute armament and infrastructure by adopting a Partition Treaty, with Ukraine leasing much of its base to the Russian Black Sea Fleet.

The agreement allows for Russian troops to remain until 2017, after which Ukrainian officials in the present pro-Western cabinet say the lease won't be renewed. Often accusing the Russian side of obstructionism, Kiev argues that many facilities used by the Russians are not included in the 1997 basic agreement. They say this should be updated.

Tensions between the two countries have cantered on the details of the lease; especially concerning lighthouses which the Ukrainian side claims are being illegally occupied by the Russian military. Kiev said Russians are not allowing Ukrainian officials to carry out legitimate weapon inspections of the fleet, that ecological norms are being violated and that the Russian side is subletting facilities in contravention of the 1997 agreement.

There have been several decisions by Ukrainian courts ordering Russia to return the contested property to Ukraine, but Russia has thus far ignored the rulings, claiming that the Basic Agreement establishes that such issues are to be decided at the inter-state level in accordance with international law. Ukraine has also persistently called for an inventory of plots of land and real estate used by the fleet, and while the Russian side has agreed to this, no progress has been made in practical terms.

Moreover, Ukrainian President Viktor Yushchenko has said the rental fee paid by the Russian side -- estimated at about $100 million a year, and which is deducted from Ukraine's debt for Russian energy supplies -- is below market value and should be raised. Even though Moscow has persistently refused a revision of the terms of the agreement, Ukrainian media are speculating that Kiev wants to double the rental amount, especially if a future inspection finds the fleet using facilities not included in the 1997 agreement. However, there is a symbolic and political dispute here.

Many Ukrainian citizens and politicians see the ubiquitous presence of Russian flags and other state symbols in Sevastopol as a sign of disrespect toward Ukraine's sovereignty, prompting Ukrainian nationalists to hold periodical protest against the fleet. But the presence of pro-western politicians in Ukraine's cabinet has always coincided with calls for the Russian side to immediately start preparations for withdrawal in 2017.

Politicians favouring closer ties to Russia insist that the issue should be dealt with by whatever government is in place in 2017, agreeing with Moscow in that it is too soon to take decisions. Recent inter-state meetings have concluded with both sides calling for the matter not to be politicized any further. However, seeking admission to NATO could hardly politicise the matter more clearly.

Russia has sought to maintain all its bases abroad. There are 16 military bases and 40,000 troops outside Russia's border. Another 25,000 civilian employees are working at the foreign bases. According to a report by the Interfax press service, a meeting had revealed that the three "most problematic" countries for the Russian bases were three formerly Soviet republics: Georgia, Moldova and Ukraine.

The meeting in October 2007 in the Duma to consider a new draft law on rules of engagement for Russian troops abroad was convened by the parliamentary committees on defense and security, and on Commonwealth of Independent States affairs, which oversees relations with the 14 ex-Soviet republics that have now won independence.

It was attended by representatives of the Defense, Foreign and Finance Ministries and 'other relevant departments,' a reference to the FSB intelligence bureau. The Russian base in Georgia is overdue for closure under the Conventional Forces in Europe treaty, and the Russian Black Sea naval base on Ukraine territory is a matter of negotiation. But the situation in Moldova may be shifting. The committees were told that international agreements limit the Russian presence to two peacekeeping battalions, about 1,200 troops.

"All other units of the former 14th Army, which means over 1,000 servicemen, are staying in Moldova illegally," a participant in the meeting told Interfax. "However, because the military property has not been evacuated -- and the Russian side is not to blame -- servicemen have to stay to guard the facility."

There has been increasing pressure for Ukrainian parliamentarians to counter the Gazprom offensive against the Ukrainian energy sector by ‘playing the Black Sea” card. This has been mirrored by US support for the admission of both the Ukraine and Georgia into NATO. Fortunately the Russian Navy is weak and falling apart at the seams, so poses no real threat to NATO in the region.

Few expect the divide to be resolved by the close of the Bucharest summit. But Russia, which has already twice endured the ignominy of its former republics and Warsaw Pact allies entering the Western military alliance in 1999 and 2004, isn't taking any chances. The Kremlin has been waging a nonstop press campaign to remind NATO and the world that a friendly gesture toward Kyiv and Tbilisi may cost them dearly in Moscow's goodwill.

A spokesman for the Kremlin, said that Ukraine and Georgia's acceptance into NATO, if approved, would be a direct snub to Russia. Dmitry Medvedev, who becomes Russia's next president in May, said in an interview published last week that the situation surrounding Georgia and Ukraine is "extremely troublesome for the existing structure of European security."

Foremost among Russia’s concerns are U.S. plans to build parts of a missile-defence system in Poland and the Czech Republic, both NATO members. The United States maintains the shield is necessary to monitor missile movements in unfriendly states, such as Iran and North Korea. The Kremlin, however, sees the shield as a threat to its own security, and fears the system may be expanded to include elements in Ukraine and Georgia, potentially taking U.S. military equipment within kilometres of its own border.

In 2000, as Putin assumed the Russian presidency, one of Russia's foreign policies was to improve ties with its close neighbours. But the reality turned out somewhat differently, with coloured revolutions in Georgia and Ukraine that saw pro-Western reformers ousting their Russia-friendly leaders. The use of economic blackmail has not been a positive solution to the problem.

The Ukrainians are determined that Russia will vacate the Crimea bases when its lease runs out in 2017 and will pay a higher rent for these facilities in the intervening years. If Russia resists, or uses its energy muscle to punish the Ukraine, it will only bring forward the day of Ukrainian retaliation in the Crimea and accelerate its path to NATO admission.