Two ships have started repairing undersea cables that were cut on 19 December disrupting telephone and net services to Asia and the Middle East.
The cables were cut about 140km off the coast of Sicily and are thought to have been damaged by a ship.
Egypt says it has been able to restore most of its communications by re-routing services, but other parts of the Middle East remain badly affected.
The same day, a suspected earthquake damaged the main cable to Malta.
On Sunday, the French repair ship Raymond Croze started work on two of the cables (SEA-ME-WE3 and 4) with the Italian vessel Teliri arriving the next day to work on the Flag Asia-Europe cable.
They three cables were cut within 40 minutes of each other, possibly by a trawler net or ship's anchor.
A ROV (Remotely Operated Vehicle) will locate the ends of the cables on the sea bed and bring them to the surface to be re-connected.
Flag Europe Asia said it expected to have the FLAG subsea cable repaired by 26 December, although that was dependent on weather and how badly damaged the cable was.
Jonathan Wright - director of wholesale products at Interoute which manages part of the optical fibre network - told the BBC that once one of the cables gets repaired, telecommunication companies will have far more options to get their services back online.
"SEA-ME-WE4 is the newest line. It has the largest capacity and so is probably the most critical line. Once that is repaired it should take some of the pressure off the one remaining cable."
"As luck would have it, a second submarine line was being installed to Malta earlier this month and that should go on line today, which will help alleviate some of the communication problems Malta is suffering," he added.
Experts have warned that it may be days before the fault is fixed and that the knock-on effect could have serious repercussions on regional economies.
Engineers from France Telecom Marine arrived at the site of the damage to the SEA-ME-WE4 and SEA-ME-WE3 lines onboard Raymond Croze at 1330 GMT on 21 December, spokesman Louis-Michel Aymard said.
The engineers then sent a remotely-operated submarine robot called "Hector" to the sea bed to begin the search for the two ends of each line.
It is unclear how long repairs to the two cables will take, as a ship could have dragged the cables several kilometres from their normal positions.
Once located, the cable ends will be brought to the surface by the robot and repairs will be carried out in a special facility on the ship - a process that could take days.
Engineers will deploy 'Hector' to retrieve cables from the sea floor
"We have to fix the cable fibre by fibre, and it's a very huge cable," Mr Aymard told the Associated Press.
France Telecom said it expected to repair SEA-ME-WE4 by 25 December and SEA-ME-WE3 by the end of the year.
In January the same line was damaged off Egypt's Mediterranean coast, severely disrupting internet and phone communications for many in the Middle East for days, although only two lines were snapped then.
A few hours before the three lines were cut, a suspected sub-sea earthquake damaged a local GO cable to Malta, severely disrupting communications to the island.