Now the Internet in Australia at the time was the Australian Academic and Research Network (AARNet).
UWA was the hub in Perth. Here's the network diagram from around the time I was first on it:
via http://en.wikipedia.org/wiki/File:AARNet_Network_1993.png
That's right, the whole state had an uplink of 2mbps. The entire country had an uplink of 1.5mbps. And Fiji had just a 2.4kbps uplink.