On Mon, Feb 26, 2007 at 05:18:03PM +0800, Gautam John wrote: > Saw this post on his Hyderabad talk: > > http://gauteg.blogspot.com/2007/02/vint-cerfs-talk-in-hyderabad.html
A lot of the original design for the protocols didn't address several basic issues. - the network was small and irregular - transfer speed was well below relativistic - logic was electronics, not photonics If you fire photons in a fiber FIFO, very much like sending information by firing tracer bullets into the night, you want to make the routing decision while the packet headers are still streaming past you. It is a switch, not a router. Because of timing, you need pretty shallow logic, since invididual gate delays add up. Worse, you don't want to convert photons to electrons and back, so you preferrably would do this with photonic gates, which are expensive in numbers and power dissipation (NLO usually appears at higher fluxes). The idea is to make an astonishingly dumb network, one that is basically only a thin decoration upon this universe's basic laws. Once you fire your stream of tracer bullets, they go on own power, until they hit a node somewhere, and have to be redirected on the fly to a different sky segment. I've once experimented with node layout on global scale (where the geometry is the surface of a sphere, or a concentric thick shell, and you can actually build a local-knowledge only routing scheme which is quick enough. Basically, you don't store global routes, but deviations of the local lattice defects from perfection. The node address is a binary string representing the current node position (something like a polar coordinate system, but with a Gray-like encoding with local bit flips and no addressing singularities). I was thinking about using a hierarchical addressing scheme to switch to individual gravitational assemblies (Earth/Moon, Sun, galactic system, etc). Incidentally, the same addressing scheme works on very small scale (die, wafer), too. I did a (very bad and purple, I was dumb, 1994/95) writeup on http://leitl.org/oldcontent/ui22204/.html/txt/8uliw.txt (I think I did manage to do a fairy well kook impersonation here)? Definition and Performance of n-grids. A perfect n-grid consists of 2^n nodes, each having 2*n links. From any node only links to nodes differing in binary offsets from self node are allowed. Provided, the wiring constraints are sufficient, the self ID arises from neighbour IDs deterministically. E.g. in 8-grid: 256 nodes, 0-node has +-1 +-2 +-4 +-8 +-16 +-32 +-64 +-128. Since links reaching out beyond ID space are considered void, 0-node has links to 1,2,4,8,16,32,64,128-nodes. +------+---------------------------+ | Total| Distance in node-node hops| | Nodes| 0 1 2 3 4 5 6 7 8 | +------+---------------------------+ | 1 | 1 0 0 0 0 0 0 0 0 | Number of nodes | 2 | 1 1 0 0 0 0 0 0 0 | having the minimum | 4 | 1 2 1 0 0 0 0 0 0 | distance in hops | 8 | 1 3 3 1 0 0 0 0 0 | (Pascal triangle for | 16 | 1 4 6 4 1 0 0 0 0 | nondefective n-grids) | 32 | 1 5 10 10 5 1 0 0 0 | | 64 | 1 6 15 20 15 6 1 0 0 | | 128 | 1 7 21 35 35 21 7 1 0 | | 256 | 1 8 28 56 70 56 28 8 1 | +------+---------------------------+ /* ************************************* */ Consider the Bresenham line drawing algorithm. It decides which pixel to choose from several neighbours using only the knowledge where it is now and where it has to go. To make it work the lattice/grid has to be regular and each element to have an unique ID/addressing. If we use a regular higher-dimensional grid and a higher Bresenham homologue it will obviously work. Even better, very high degrees of defectivity can be tolerated. The probability of a blockage goes almost down to zero with increasing number of dimensions. Detection of the blockage condition is trivial: the path begins to show a small periode (due to routing artefacts). A tiny FIFO of a path will do. A random kick will often solve the problem. If not, an exhaustive local search will do. But is it worth the trouble? Packet lossage is usually handled transparently by a protocol.) I refer to this scheme as higher-dimensional Bresenham routing or simply grassrouting, because of its simplicity. ^^^^^^^^^^^^ The boolean hypercube (n-cube) a member of the hypergrid or the n-grid family, will be our model case. The n-grid/n-cube. Imagine a standard three-dimensional cube with an edge of length 1, the first node lying at coordinates (0,0,0), the second at (0,0,1), the third ... (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0) and the eighth at (1,1,1) (see picture). It is a member Y | Z | / 011| o--------o 111 |/| / /| 010 o--------o | 110 A 3-cube with binary labeled | |/ | | nodes in a cartesian coordinate 001| o------|-o 101 system |/ |/ o--------o-------X 000 100 of the boolean n-cube homologue sequence with total number of nodes being 2^n. Thus one can label the nodes with a binary integer 0,..,(2^n)-1. Alternatively, one can say there a space of IDs for each n-cube. If we consider a single reference node in a boolean n-cube, it is connected to n nodes _with binary offsets_ (2^i). The sign of the offset is derived from the binary count pattern bit sequence. This is a constructive definition. (Look up connectivity matrix of boolean 5-cube way down. Note that it contains _four_ 3-cubes). This table represents the 3-cube: ref. Binary Signs binary connected ID Count Offsets IDs +---+-----+------+-----------+-------+ (alt.: | 0 | 000 | +++ | +4 +2 +1 | 4 2 1 | perfect | 1 | 001 | ++- | +4 +2 -1 | 5 3 0 | shuffle | 2 | 010 | +-+ | +4 -2 +1 | 6 0 3 | stages (1,2,3) | 3 | 011 | +-- | +4 -2 -1 | 7 1 2 | of the initial | 4 | 100 | -++ | -4 +2 +1 | 1 6 5 | ref. ID) | 5 | 101 | -+- | -4 +2 -1 | 2 7 4 | | 6 | 110 | --+ | -4 -2 +1 | 3 4 7 | | 7 | 111 | --- | -4 -2 -1 | 4 5 6 | +---+-----+------+-----------+-------+ This boolean n-cube is a peculiar beast. On the one hand it is a very orthogonal structure, easily reasoned upon mathematically. The signs/offsets look after themselves, it is a recursive/fractal structure (each n-cube consist of 2 interconnected (via (n-1) number of links) (n-1)-type subcubes), etc. Routing in it resembles binary search: the first step brings one halfway there, the second halfway again, etc. We descend the binary cluster hierarchy until we arrive at the 0-cube (single node). The "distance distribution versus dimensionality" table is the Pascal triangle, by the way. It can derive its own ID from wiring constraints and the other IDs it is directly connected to. (This is a crucial point). Etc. Routing in a perfect n-cube runs roughly: "going from the left, find the first bit in destination ID differing from source ID. Move message packet to the according subcube via direct link (there is only one). Repeat until you reach outer (rightmost) bit. Bingo." This can be coded in some 10 assembly statements or implemented via a very primitive logic. If a part of the links is missing (the n-cube is defective) we have to visit all the nodes which should have links to the second subcube until we can prove the task impossible. The n-grid, on the other hand, can be considered a better n-cube (is a superset of it). We can derive it from the n-cube by making link offsets symmetrical. Links which would reach out of ID space can be either wrapped around (circular space) or considered void/free (open space/grid region). See connectivity table below. Routing is again completely trivial. You just choose the link which distance (arithmetical ID difference) is smallest and shove the packet through. In a perfect n-grid, this works every time and is moreover the best possible algorithm. Especially, if the near-range order (shortest offsets) is highly preserved, this scheme works also for severely defective n-grids (there is a lot of space in those higher dimensions). If the message _blocks_ (its path has a periode/loop) we can circumvent the blockage either giving the message packet a random kick or executing a plan, subsequently visiting all the nodes which should have links in this direction in ever-increasing distances. Connectivity Tables of 5-cube and 5-grid (2^5=32 nodes each) # means a link, - means there is no link. Note that the n-cube is contained in the n-grid (as it is a superset). The n-cube has a fractal/recursive makeup: it contains two interconnected (n/2 links) (n-1)-cubes. A n-grid node has (2n-1) links as compared to the n-cube (free links are not shown). Two (n-1) subgrids are connected by (2n-1) links as compared by n links in the n-cube. The simple n-grid routing algorithm does not work for the n-cube (it blocks/loops in most cases). Moreover, if the _farthest_ link of each node (n-cube) is cut, the cube collapses into 2 unconnected (n-1) cubes. This does not happen to the n-grid. Notice that a defective structure (some links missing) still routes all right because of built-in redundancy (which is higher in the n-grid). The n-grid is a superset of the n-cube. Each node has boolean 5-cube 5-grid (open-space version. free links not shown) -##-#---#-------#--------------- -##-#---#-------#--------------- #--#-#---#-------#-------------- #-##-#---#-------#-------------- #--#--#---#-------#------------- ##-##-#---#-------#------------- -##----#---#-------#------------ -##-##-#---#-------#------------ #----##-----#-------#----------- #-##-##-#---#-------#----------- -#--#--#-----#-------#---------- -#-##-##-#---#-------#---------- --#-#--#------#-------#--------- --#-##-##-#---#-------#--------- ---#-##--------#-------#-------- ---#-##-##-#---#-------#-------- #--------##-#-----------#------- #---#-##-##-#---#-------#------- -#------#--#-#-----------#------ -#---#-##-##-#---#-------#------ --#-----#--#--#-----------#----- --#---#-##-##-#---#-------#----- ---#-----##----#-----------#---- ---#---#-##-##-#---#-------#---- ----#---#----##-------------#--- ----#---#-##-##-#---#-------#--- -----#---#--#--#-------------#-- -----#---#-##-##-#---#-------#-- ------#---#-#--#--------------#- ------#---#-##-##-#---#-------#- -------#---#-##----------------# -------#---#-##-##-#---#-------# #----------------##-#---#------- #-------#---#-##-##-#---#------- -#--------------#--#-#---#------ -#-------#---#-##-##-#---#------ --#-------------#--#--#---#----- --#-------#---#-##-##-#---#----- ---#-------------##----#---#---- ---#-------#---#-##-##-#---#---- ----#-----------#----##-----#--- ----#-------#---#-##-##-#---#--- -----#-----------#--#--#-----#-- -----#-------#---#-##-##-#---#-- ------#-----------#-#--#------#- ------#-------#---#-##-##-#---#- -------#-----------#-##--------# -------#-------#---#-##-##-#---# --------#-------#--------##-#--- --------#-------#---#-##-##-#--- ---------#-------#------#--#-#-- ---------#-------#---#-##-##-#-- ----------#-------#-----#--#--#- ----------#-------#---#-##-##-#- -----------#-------#-----##----# -----------#-------#---#-##-##-# ------------#-------#---#----##- ------------#-------#---#-##-##- -------------#-------#---#--#--# -------------#-------#---#-##-## --------------#-------#---#-#--# --------------#-------#---#-##-# ---------------#-------#---#-##- ---------------#-------#---#-##- /* ************************ */ Notice that the maximum distance increases with log2(total nodes) and both the average as overwhelming majority distance even with 0.5*log2(total nodes). The function peaks very sharply for halfway distances. GrassRouting. The router is an incarnation of a minimalist packet switched GrassRouter, utilizing a higher dimensional smart Bresenham homologue upon an low-defect higher dimensional node lattice, called the n-grid. Packet switched networks offer excellent performance particularly for very large networks. Packet switched hypergrid routing allows an efficient, fault tolerant, purely local knowledge routing and ID derivation scheme, the Dynamic ID Derivation (DID). The node adress (ID) space is binary, offering 2^n addressable nodes for n bit IDs. In perfect n-grids, each node has only direct links to nodes with symmetrical binary offsets to own ID. In defective grids a large fraction of the links may be missing. E.g. the well-known boolean hypercube is a defective n-grid topology. Especially highly conserved near-range order offers still offers excellent performance. Since logically near (short offset) links are also physically shorter, when n-grid is mapped to 2-space (wafer) or 3-space (module), this is fortunate. ID space is not toroidal or wrap around, but open, offering free links for real-world I/O. For that, serial to parallel link adaptors or modified I/O 8/ULIW variants are needed. Each n-grid is recursively defined by two interconnected (n-1)-grids. Each packet is routed by descending the recursive n-grid hierarchy until it arrives at 0-grid, the single node. ID subspaces are defined in terms of binary masks, starting with zero (zero additional information is needed to pinpoint an object), over 1, 2, 4 etc. Broadcast or WALL message flooding (via message cloning) is usually limited to subspaces. Notice that the address subspace n-subspace is identical to total n-grid ID space, they are congruent. Provided, the wiring constraints are sufficient, and the direct IDs are visible through links, own (self) ID is deterministic. Due to high lattice orthogonality and n-grid redundancy, high degrees of defectivity (fraction of shot vs. intact links) are tolerated without DID impairment and good routing performance. -- Eugen* Leitl <a href="http://leitl.org";>leitl</a> http://leitl.org ______________________________________________________________ ICBM: 48.07100, 11.36820 http://www.ativel.com 8B29F6BE: 099D 78BA 2FD3 B014 B08A 7779 75B0 2443 8B29 F6BE
signature.asc
Description: Digital signature
