Marcos Anastassiou, 14 Jan 1997, Victoria University of Technology
Luke Bowker, 24 Nov 1996 , Suburbia Public Access Network Site Sysadmin
Greg Jones, 1 Jan 1997, TAPR.ORG (Tuscon Amateur Packet Radio)
Phil Karn, 21 Dec 1996 , creator of KA9Q NOS
Subject: Re: Ubiquitous Public Network
Date: Sun, 24 Nov 1996 23:51:00 +1100 (EST)
From: Luke Bowker <puke@tinkertrain.suburbia.net>
To: derekw@suburbia.net (Derek Weston)
CC: proff@suburbia.net, puke@suburbia.net
> Gentlemen (yes... I *do* mean you guys !!!). You may (or may not?) be interested in the attached.
Of course we are. This kind of low cost power-to-the-people enabling technology has a close relationship with why suburbia is what it is.
I've read it all, and I can't see any arguments against any part of it, at least not without having had a few days to let the ideas gel in my mind, except one bit:
>Consider a data transfer across a mesh network comprising type 2 and type 3 nodes. Assume
>* an end-to-end distance of 10 km
> * an average hop distance of 100 metres
> * a packet size of 281 bytes, of which 5 are start bytes and 20 are header bytes
> * a distance efficiency (ie. end-to-end distance divided by the sum of > the hop distances) of 50%
> * a sliding window size of 512 packets
> * simplex physical links in which data can only flow in one direction at a time along a particular physical link
> * CRC or other packet integrity checking only at the final node in the chain
>Number of hops = 10000 / 100 /.5 = 200
Here we find a practical expression of the classical computer science problem known as the "Shortest path problem", which is to find the shortest traversal of a directed graph with the graph arcs having "weights" which are assumed to be the cost of moving along that particular arc. Two problems posed by this that I see are:
1. The "weights" are changing dynamically in a real network, and it's debateable whether or not any single node can get a sufficiently close approximation of what the weights should be to determine a suitably efficient route through the network.
2. The shortest path problem has been shown to be N-P complete, requiring 2^n operations to solve the problem, where n is the number of arcs in the graph. For each additional node in the graph, the problem takes twice as long to solve, because the only way to guarantee an optimal solution is to try out every single combination of routes through the graph. Various heuristics exist, but there's always cases where they don't produce the optimal route. On the other hand, "optimal" isn't a necessity for this application, and a "good" solution will work quite reasonably. More information at http://www.bath.ac.uk/~masjpb/teaching/qc/lectures/node77.html, or any discrete mathematics textbook.
If you use a routing method of "figure out which of the nodes directly attached to me is closest to the destination node, send the packet there and let it figure out the optimal route for the next node", then you also have the problem of what if the next node decides that the most optimal way to the destination is to go back through you? This can happen because of nodes having different pictures of the weighting of the graph arcs, or because of differing algorithms to find the route.
The solution we tend to find in existing networks is to build on a backbone, somewhat like the postal system. If me in Geelong wants to send something to somewhere like Byron Bay, you usually find that the mail first goes to Melbourne, then to Sydney, then on to Byron Bay. This is not because it's the optimal route, but because the system works on the idea of sending anything with a postcode that starts with 2 to Sydney, then letting the GPO there figure out the rest. It works adequately, but depends on there being a high capacity channel between Melbourne and Sydney.
The Internet is more complex but still built on the idea of having high capacity channels connecting major sites, then smaller sites connecting to the major sites.
In practice, I imagine a UPN network would have a few sites setting up high capacity long distance links due to differing needs of people in the network. eg. Proff and me would likely set up a high speed link across the bay because we need the capacity for our own purposes. Other sites with lower capacity requirements would then probably connect to us as leaf nodes, or perhaps others will find needs for high capacity links to us for whatever reasons, with leaf nodes and subnets sprouting from them in their immediate geographic area, thus a high speed backbone gets formed without it needing to be designed into the network. So perhaps the shortest path problem isn't all that relevant, but then we see a large part of the network being controlled by a few people, which is one of the things the UPN is trying to avoid.
As for the rest, I can't see any problems, and in fact many of the problems you pose seem to have already been solved by things like ipv6 (now in 2.1 Linux kernels. Don't know about others), such as encryption and addressing problems. All in all, I suggest publishing that thing widely, since the world needs a low cost network free of phone companies, and one way or the other someone is going to implement it. Even if the way you suggest isn't viable (and I don't see any fundamental reason why it shouldn't be, just a few nitpicking maybes), widespread awareness of the idea of a UPN would doubtless create one.
Luke Bowker, puke@suburbia.net, puke@deakin.edu.au
Suburbia Public Access Network Site Sysadmin
Date: Sat, 21 Dec 1996 23:19:55 -0800 (PST)
From: Phil Karn <karn@unix.ka9q.ampr.org>
To: derekw@suburbia.net.au
Derek,
Thanks for the pointer. I read your paper. As you probably well know,the transmission side of the network is the hard part -- thanks to NOS, Linux and cheap PCs, the switching part is now easy. Your emphasis on optical links tells me you're interested mainly in densely populated areas -- right?
I think the underlying problem is your telephone company. Ours is not much better, but at least we do have the cable companies to compete with them. Fast cable modems are now starting to appear in several US cities, and we're supposed to get them next year. Once we do, much of the problem will go away.
Phil
Subject: Re: Ubiquitous Public Network
Date: Wed, 1 Jan 1997 04:54:31 -0600
From: "Greg Jones, WD5IVD" <wd5ivd@tapr.org>
To: Derek Weston <derekw@suburbia.net.au>
Hi Derek.
I really think you need to take you paper and submit it for the 1997 ARRL/TAPR Digital Communications Conference next Sept. That would be one of the best places to get it printed in.
Your welcome to add my comments to your page. Please note we now have the radios available http://www.tapr.org/ss/radio900.html
Cheers - Greg
Subject: A Ubiquitous Public Network
Date: Tue, 14 Jan 1997 11:11:33 +0000
From: Marcos Anastassiou <MarcosAnastassiou@fox.vut.edu.au>
Organization: Victoria University of Technology
To: derekw@suburbia.net.au
Dear Derek,
After reading your proposal for a community based public network, I am of the opinion that it offers many advantages to education institutions. I have passed your proposal on to senior management in this university for consideration.
Marcos Anastassiou
Lecturer, Communication Studies, Victoria University of Technology.