Communications network and method of routing messages within the network
AssigneeTelefonaktiebolaget LM Ericsson (publ)
InventorMajid Zolfaghari
Life of this patent
Estimating the term…
Abstract
A communications network includes a plurality of nodes with unique identities and a server unit. Each node is provided with a first storing device for storing a list of all nodes neighboring the node which are directed to it and a second storing device containing a data field which forms an array of cells indexed for all nodes in the network. A third storing device is provided in the server unit for forming a temporary queue. Messages are routed within the network by transforming a graph-representation of the network into a tree model with the destination node as root. This tree is the shortest which the graph can be transformed into.
Claims8
A method of routing messages within a communications network comprising a plurality of nodes having unique identities, the method comprising the steps of:
- calculating the shortest path between a first node and a second node by:
- forming a list of the identities of all nodes neighboring said first node and to which it is directed,
- putting the identity of the second node in a queue,
- writing a stop command in a data field for registration of identity of the second node,
- taking the identity of the node in front of the queue and writing its identity in the data field of all its neighbors, unless there already is an entry in this data field,
- putting the identity of a node in the queue each time an entry is written into the data field of this node,
- removing from the queue the identity of the node in front of the queue, after visiting all nodes in the lost of all neighboring nodes of said node, and
- repeating the step of taking the identity of the node in front of the queue and writing its identity in the data field of all its neighbors, until the visited node is the first node.
A method of routing messages within a communications network for sending messages between a plurality of nodes having unique identities, the method comprising the steps of:
- calculating the shortest path between all pairs of nodes in the network by:
- forming a list of the identities of all nodes neighboring a node and to which it is directed,
- putting the identity of the node in a queue,
- writing a stop command for this node in a cell which is indexed in an array data field indexed for registration of identity of all nodes in the network,
- taking the identity of the node in front of the queue and writing its identity in the cell which is indexed in the data field of all its neighbors, unless there already is an entry in this data field,
- putting the identity of the visited node in the queue each time an entry is written into the cell which is indexed in the data field of a node,
- removing from the queue the identity of the node in from of the queue, after visiting all nodes in the list of all neighboring nodes of said nodes,
- repeating the step of taking the identity of the node in front of the queue and writing its identity in the data field cell of all its neighbors, until the queue is empty, and
- repeating the above step for all nodes in the network.
Dependencies are inferred from the claim text.