Communications network and method of routing messages within the network

• US 6,674,757 B1
• Filed: 11/12/1999
• Issued: 01/06/2004
• Est. Priority Date: 11/12/1998
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Zolfaghari, Majid
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): PHAM, BRENDA H
• Application Number:
  US09/439,160
• Time in Patent Office: 1,516 Days
• Field of Search: 370/235, 370/238, 370/238.1, 370/256, 370/254, 370/351, 370/379, 370/382, 370/395.3, 370/395.31
• US Class Current: 370/395.31
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/76 Routing in software-defined topologies, e.g. routing between virtual machines

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.

Claims

1. 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.

2. A method according to claim 1, further comprising checking the network for nodes which have been disconnected from a certain node.

3. A method according to claim 2, wherein said checking comprises the following steps:

putting the identity of said node in the queue and marking said node,

taking the node in front of the queue and marking its unmarked neighbors,

each time the identity of a new node is marked, placing it in the queue,

after visiting all nodes in the list of the identities of all nodes neighboring said node in front of the queue, moving said node from the queue and putting it in a set of visited nodes,

repeating the step of taking the node in front of the queue and marking its unmarked neighbors until the queue is empty, and

subtracting the resulting set of visited nodes from the set of all nodes which said node is aware of, wherein the result is the set of nodes which are disconnected from the aforementioned node.

4. A method according to claim 1, further comprising the step of:

representing the distance and/or the traffic load between each pair of nodes by a number of assumed virtual nodes, said number being proportional to said distance and/or traffic load.

5. 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.

6. A method according to claim 5, further comprising checking the network if a node has connection to all other nodes.

7. A method according to claim 6, wherein said checking comprises the following steps:

putting the identity of said node in the queue and marking said node,

taking the node in front of the queue and marking its unmarked neighbors,

each time the identity of a new node is marked, placing it in the queue,

after visiting all nodes in the list of the identities of all nodes neighboring said node in front of the queue, moving said node from the queue and putting it in a set of visited nodes,

repeating the step of taking the node in front of the queue and marking its unmarked neighbors until the queue is empty, and

subtracting the resulting set of visited nodes from the set of all nodes which said node is aware of, wherein the result is the set of nodes which are disconnected nodes.

8. A method according to claim 5, further comprising the step of:

representing the distance and/or traffic between each pair of nodes by a number of assumed virtual nodes, said number being proportional to said distance and/or traffic load.