Work on phase two, which links the south of the country to the north is due for completion at the end of this year. Phase three, which will connect the cable with Rwanda, is expected to begin in the course of the second half of the year.

"By mid-next year, the national backbone should be completed," Mwesigwa said. He noted that the Ugandan cable has two components -- one has linked all government offices and another with spare capacity for the private operators to lease.

The Kenyan government is also investing $60 million in a fiber cable of its own. The National Optic Fibre Backbone Infrastructure (NOFBI) is being implemented by Chinese firms Huawei and ZTE and a French firm, Sagem. Unlike the other countries of East Africa, Kenya's private sector has laid a lot of the fibre optics. Some 5,000 km of fiber had been laid by the private players by June 2010.

The five partner states plan to link their cables in one network to lower the cost of communication by increasing the speed and capacity of internet connectivity.

Telecommunications regulators from these partner states are also pushing for a regional internet exchange point to keep traffic within the region local.