I'm wondering if Egypt has reconsidered its actions...
http://www.worldcat.org/title/introducing-internet-to-egypt-...
It might be John McConnell's Internetworking computer systems : interconnecting networks and systems (1988):
http://www.worldcat.org/title/internetworking-computer-syste...
Prentice Hall seems right for the publisher, though I'm not positive on the title. Date seems a year or three early.
Possibly John Quartman's The Matrix, 1990, which sounds closer to the right date:
https://www.amazon.com/Matrix-Computer-Networks-Conferencing...
You might be able to cross the Baring Strait with a LOS microwave relay -- there's a somewhat fanciful video which explores the possibility of driving from Tierra del Fuego to London. It's only really hard in a few areas, one of the more problematic being Guatemal.
Conceptually, tunnelling or bridging (my option would be the former) the Straight is within reason (51 km, compare the Gotthard Base tunnel at 35.5 km). It's creating all-season driveable roads (or trainable tracks) across Alaska and Siberia which are the more formidable challenges.
But for the Atlantic? Cable. Seriously.
And the Lima - Sydney tunnel is going to take a while to dig.
More seriously, back in the old days:
... the Usenet link to Australia was a daily batch of tapes flown by 747. High bandwidth, but long ping times.
One of the first publicly-accessible network links between the US and Europe ... was a 9600 BAUD line.
I'd cite both of these in more detail, but the book is buried somewhere in archives presently. A late 1980s / early 1990s (just prior to the dawn of the public Internet) item.
More generally, though, to address your question, oceans aren't the problem. We've got ocean links.
It's the last mile, between you and the local on-ramp. That's where Comcast, Verizon, AT&T, and TWC have their monopolies, which need breaking up.