Banner
    The Shortest Path Problem in a Dynamic Network.
    By Patrick Lockerby | April 14th 2009 08:21 PM | 12 comments | Print | E-mail | Track Comments
    About Patrick

    Retired engineer, 60+ years young. Computer builder and programmer. Linguist specialising in language acquisition and computational linguistics....

    View Patrick's Profile
    The Shortest Path Problem in a Dynamic Network.

    A method is needed by which efficient new network routes can rapidly be
    calculated to route traffic away from problem paths and nodes. A
    possible method is proposed.  I propose to call it the Wentrok heuristic.

    What Is The Quickest Route From Newtork To Wentrok?

    A network is only as efficient as the algorithm used to control its traffic. The most efficient use of resources is achieved when all traffic encounters the least physically possible delay in going from A to B. In real life, this might apply to the internet or to road traffic.   In the case of road traffic, a vehicle standing still with its engine running has an instantaneous efficiency of zero distance per unit of fuel.   In a dynamic network, failures occur and present themselves as blocked or congested paths (highways) and nodes (junctions and interchanges).  In many real cases like this, an improved network efficiency can lead to worthwhile economies.

    A network comprises a number of paths over which traffic may pass, together with points of interconnection of the paths. The network graph may describe a computer network or a road network, or any broadly similar real-world routing problem. traditionally, in describing such entities, the terms 'edge' and 'vertex' are used by mathematicians; 'path' and 'node' by many other disciplines.

    The generalised problem in such a graph is to find the smallest sum of paths between all possible pairings of nodes. In the generalised model described, an assumption is made that a packet is to be sent between two nodes. This could be a data-packet, or a parcel in a truck.

    The Dynamic Network Problem.

    In a computer or road network it can be useful to determine the path along which a packet may be sent with least delay. As an example, at peak traffic times it can save delay if a packet is routed away from a choked main highway.   Again, a path may be temporarily out of commission: there may be roadworks, or a network server may be down.

    The Shortest Path Problem in a Dynamic Network, SPPDN, is a problem of sending a packet from one node to another with the least delay, over a network that has no perfect, permanently fixed structure and which is subject to varying volumes of traffic.

    A Proposed Solution.

    Based on the notions of six degrees of separation and the magic number six, a heuristic is built in which there is no outside observer or group of observers needed to model a dynamic network.  In a sense, the network models itself.

    Each node is modelled as a data array in a dynamic network. Adding or removing nodes or paths does not impact on the efficiency of the heuristic. No single node need keep an excessively large list of paths, and the loss of any single path, node or path-list is immediately recoverable by the network overall.

    In the diagram, nodes are lettered to show the method.  Coloured rings show waves of interrogation.  For each node there is a list of nearest neighbours and distances. The heuristic is indifferent to the unit name ascribed to these distances: it may be physical distance for roads, or delay times for electronic signals.

    To initiate or refresh a  node, as e.g. the one shown in red, the computer interrogates its nearest neighbours and stores the neighbour-labels and route-delays in a look-up table.  A refresh is performed as frequently as may be needed to cater for delays due to congestion at peak traffic times.



    How far is it from Newtork to Wentrok?

    Newtork wishes to send a packet to Wentrok by the shortest route. A query  is forwarded in the format:
    To: Wentrok
    From: Newtork.

    Node E now sends a 1st wave (green) message to each of b,c,f,g as:
    To: Wentrok
    From: E, Newtork.

    Each of b,c,f,g forwards a 2nd wave (light blue) message. Two examples are given:
    To: Wentrok
    From: G, E, Newtork.
    .....
    To: Wentrok
    From: F, E, Newtork.

    Each node which has no listing for Wentrok adds its own unique i.d. as sender to the front of the sender list and forwards the query to every node in its neighbours list which is not in the senders list. There is a wave-front effect. Ultimately one or more nodes will recognise Wentrok, aka node K, and return the query. The query is returned via the sender list until it arrives back at Newtork. Newtork takes the first instance of a returned list as a de facto validation of a fastest route to Wentrok and sends the packet with an attached routing list.

    In the event of a node or route failure during packet transmission, the node which fails to forward the packet initiates a new Wentrok query, and then acts as an initiator of the packet transmission.

    In practice, each node may accept a copy of the forwarding list of nodes held by each immediately  adjacent node. Thus, node H for example would hold data as m{r,p,l}, g{e,r,j}. The number of 'dimensions' held by any particular node will depend on the computing power available to enact the heuristic.

    If each node appends a 'job done' list of nodes already queried, there will be no back-propagation of the interrogation wave.  Queries will only be forwarded to nodes not in the senders list and not in the 'job-done' list, with an improvement of efficiency.

    Discussion:

    If the 6-degrees of connection model is valid, then I suggest that if each computer on a real network such as the internet, being a non-terminal node, has only 6 levels of neighbourhood name-space, then any Newtork-Wentrok shortest route can be determined after a maximum of 6 waves of interrogation.

    It is possible that problems involving the exchange of information more generally, not previously viewed as network-oriented problems, may become tractable using this heuristic.  The heuristic may thus, perhaps, have applications in linguistics and cell biology.

    Comments

    Gerhard Adam
    Patrick

    Two questions:

    1.  How do you detect failures and what is the algorithm used to ensure that the remaining nodes are made aware of the failing node?

    2.  How is this different from TCP/IP's OSPF protocol?
    Mundus vult decipi
    logicman
    Hi, Gerhard.  thanks for the interest.

    1.  How do you detect failures and what is the algorithm used to ensure that the remaining nodes are made aware of the failing node?
    Each node refreshes its data by sending an occasional ping to its immediate neighbours.  Thus, its map of the local area is constantly updated as a list of available adjacent nodes, with delay times.  Each node could, alternatively, request a refresh of the neighbours' node lists, so as to extend its local map.  The constant refresh of map data keeps the totality of the network model in step with the outer realities of resource availablity.

    2.  How is this different from TCP/IP's OSPF protocol?
    OSPF - Open Shortest Path First - depends on an address table built up by the handshaking of dedicated computers.  The shortest path may be built by e.g. Dijkstra's algorithm.  Such algorithms compute a route via every node.

    An address table for an extremely wide area suffers from obsolescence.  By the time an entry in the list comes to be used, the route may no longer be available.

    The proposed 'Wentork heuristic' is a dynamic map of a dynamic system.  Where it is implemented as a one- computer-per-node network, it is a self-repairing map having a real time 1-to-1 correspondence with its own available resources.

    The Wentork heuristic describes a data exchange between multiple 'observers' - all of the nodes.  OSPF and similar models map nodes onto a single-observer map.  The one is a parallel processing of all solutions, the other a serial computing of idealised and static solutions to part only of the dynamic shortest path problem.
    Gerhard Adam

    Maybe I'm not understanding what you're trying to say, but how does your approach avoid flooding the network with broadcasts to update routing information versus the packets being sent.  Even in your example, Node E sent a message to Node C (which should have been ignored as an end-node).

    Part of the rationale in consolidating link-state information and synchronizing databases was precisely to avoid the problem of too much broadcast traffic taking away available bandwidth.

    In addition, the issue of convergence when a problem has been detected has resulted in additional modifications like split-horizon, poison reverse, triggered updates and counting to infinity.  These are described in RFC 1058.

    These implementations are all intended to avoid propagating loop configurations throughout the network, reducing broadcast traffic, and limiting the volume of database updates to be synchronized.

    Mundus vult decipi
    logicman
    The network isn't flooded because the updates are entirely asynchronous.  End nodes are included because they are addresses to which other computers might want to send data.  Try to visualise the placing of a new node, or the re-booting of an old one.  The newly booted computer  sends a 'hello' message and gets back a reply only from its immediate neighbours.  It now stops broadcasting.  It contributes no traffic to the web outside of its own immediate neighbourhood.  It stores neighbour's names and delay times.

    I surmise that by use of lists, no single computer needs to hold a larger list in order for the system, acting as a massively parallel computer, to map itself from every node to every other node.  At no point does the entire network need to send routing data.  It is only ever local.

    The system isn't flooded because lists are updated asymmetrically to cope with only the expected mtbf of system components.  Once any two computers have established a shortest path, that same path will be used as a forwarding list for quite a while.  It may be that an algorithm is used to detect degradation beyond a certain level, when a new path request might be initiated, but there is absolutely no need for a path request before sending any packet.

    Ordinary packets follow the path of least delay, optimising the use of resources.  Path requests propagate as waves, but die out at nodes where the nodes' list is already in the senders' list.  There is no reverse propagation, no looped paths.  The path list is always returned, I surmise, in about 6 wave steps or less, and the overall use of resources is less than the current 'supervisor-created' web mapping systems.
    Gerhard Adam
    Perhaps it would be easier if you indicated what routing protocols you were looking at replacing with this.  Since there are so many possibilities and each has certain advantages/disadvantages depending on the configuration, it might be easier for me to see what you're getting at if you could identify some of the ones you're referring to.
    Mundus vult decipi
    logicman
    Gerhard: the heuristic is intended as a general solution to a lot of different topological problems, all of the general 'shortest route' type.

    I gave the network implementation as an example by way of explaining the heuristic.  The internet is a specific case.  Historically, it developed from academic requirements of reliable communication, via military requirements of fail-safe distributed computing and data paths, into the internet that we all know and love.

    The dotted octet / domain name protocol with name servers was devised to allow for the simple fact that there was no full solution to the generalised shortest-path problem.  In the current model, lookup tables must be stored by specialised name servers.  Routing tables must be stored by servers.  The model is entirely server dependent.

    I don't see the Wentrok heuristic being adopted on a planet-wide scale any time soon, if only because of the current investment in infrastructure.

    Where it might be useful is, in the first place, as a computer model for pure mathematics.  It might lead to a proof of the 6-degrees of separation theory.

    It might also be useful where a wide area network is being built from scratch.  In such a network, no single computer is a name-server.  All that is needed is a system-wide reserved name such as  'newnode'.  Suppose a new name is needed for a computer which has just been added.  This query is propagated with no destination and the reserved name 'newnode' as sender.  This one message is broadcast to all computers, and each returns its neighbours list.  A new name is generated which is not on any list.  The new computer then forwards an 'add me' request to its immediate neighbours, and uses the 'added ok' response to create its own neighbours list.

    Once such a network is running, it is only necessary for the nodes to asynchronously update their neighbours lists daily, hourly or whatever.  The resources used for such updates are trivially small.  The network overall is exceedingly robust, has no dedicated name servers or routers, hence no weak points which could be attacked and uses its bandwidth in the most efficient way possible.  Any single computer can be taken down for maintenance or replacement without impacting on overall web performance.

    The model is enhanced if, as well as shortest routes, second and third shortest routes are stored.  In this way, performance can be monitored by a handshaking sender as against projected performance.  Forwarding requests can use alternate forwarding lists, testing to see which list gives the shortest delay during peak traffic times.

    Getting back to the maths behind this:  if the '6-degrees theory' is valid, then even in a global scale network, no forwarding list attached to a packet need contain more than 6 addresses, and no master list of network addresses  is needed.  One of the factors in the efficiency of a network is the percentage of network resources consumed by the networking protocols.  I surmise that the Wentrok heuristic minimises such resource usage.
    Cybernaut
    This has some rather exciting implications, if it's prove-able and implementable.  Is this current research you're working on?
    logicman
    Hi Mel.

    This started out as a computer program to link word groupings.  I was trying to model the 'priming effect' whereby a word can make a following word easier to grasp if it's in an overlapping category.  I saw the network aspect and tried a few variant heuristics.  I've used the method in a small scale simulation - about 100 nodes.  It works ok.  But there are limits to what any one person can do working alone - that's why I've published this heuristic, also one for encryption - to let others run with the ideas.
    Cybernaut
    I find it interesting, because I've been looking at some similar things from an information sense (how you acquire the optimal assistive technology for yourself if you become disabled) -- I'm going at it from a "roles and schema=filters" angle.

    In Linguistics, the structure of the input information gives clues about the meaning of the information... I suppose this is ground that you've been over already?
    Cybernaut
    Erk!  I see from your profile that you know more about Linguistics than I do.  Yeah, you've considered it....
    logicman
    In Linguistics, the structure of the input information gives clues about the meaning of the information... I suppose this is ground that you've been over already?
    Mel:  I've written some program snippets which take ASCII input and look for regularities.  In general, by doing a 'sum and difference' test, the program can detect regularities in a sample of texts in one language and output some 'grammar words', common suffixes and proper nouns.

    Two small samples of the output from a run of 10 Enid Blyton books:
    admiringly anne
    admiringly gazed
    amiably wagging
    anxiously barnard
    anxiously george
    anxiously looked
    anxiously tried
    approvingly timmy
    .....
    a bit
    a boy
    a day
    a dog
    a girl
    a holiday
    a pair
    a rabbit
    a thing
    .....
    The various algorithms work for English, Spanish, French, German, Italian and Latin.
    small sample output, Latin:
    nobis
    vobis
    avobis
    orbis
    morbis
    urbis
    dicis
    amicis
    corticis
    alcis
    calcis
    sulcis
    vincis
    lyncis
    .....
    I need to do a bit more development before I publish the method.  In brief, it's pure pattern matching with absolutely no built-in patterns.  That is, it is not told to look for e.g. words ending in  -ing, rather it finds regular word ending patterns in regular sentence locations.  It does this by finding similarities in a number of texts and then comparing that summary with unique texts.  I'm trying to replicate at least a small part of the way children acquire language.  I also have a model of language as a network of 'buckets of ideas' labelled with words.
    Cybernaut
    Aha.  I was going at it from an anthropological perspective and a human-search engine interface, where you need a corpus and some sort of background to know if the person who is searching with the word "klein" might be English and be looking for the "klein bottle" or the topologist or might be German and be hunting for something small or a paper called "der Klein."  Or if it's a misspelling of "climb" or "in cline".

    You're going at it from a purely "corpus search" aspect, though.  Have you tried running it in "tag clouds" just for grins?