Data communications network

• US 5,142,531 A
• Filed: 05/10/1990
• Issued: 08/25/1992
• Est. Priority Date: 05/18/1989
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Kirby, Lewis G.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/522,601
• Time in Patent Office: 838 Days
• Field of Search: 370/58.1, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/94.1, 370/94.2, 370/94.3, 370/85.13, 370/85.14
• US Class Current: 370/254
• 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/18 Loop-free operations
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04Q 3/665 Circuit arrangements therefor

Abstract

A network is arranged to generate circuits between source node (N_S) and destination nodes (N_D) by means of datagrams which are guided at each node over a path (D) which minimizes delay in establishing the circuit. Certain sub-destination nodes (N_B and N_C) are designated as intermediate circuit nodes by the datagram and accordingly a circuit (C) is established. Each circuit node is determined by the preceding circuit node in such a manner as to minimize the hop count to the destination node (N_D). To this end, each node incorporates in its memory (M) a first list (LIST 1) showing the link with the best hop count to each possible destination node and also incorporates a list (LIST 2) of its links with the best transmission delay to the destination node. These lists are updated dynamically by means of routing information packets which are exchanged between neighboring nodes. However, best hop count and best delay information is not transmitted over those links (L) which are themselves the subject of that information. In this manner "ping-pong" type looping is avoided.

Claims

1. A distributed communications comprising:

a plurality of nodes which are each capable of acting as source, sub-destination and destination nodes, the nodes being interconnected by links and each node having local processing and memory means,

each node including in its memory means a stored list of destination nodes in association with a first stored list and a second stored list of its links of neighboring nodes,

each entry in the stored list of destination nodes being associated with a respective link or neighboring node in said first stored list and in said second stored list,

the processing means being arranged such that a datagram can be sent between one of said nodes acting as a source node and another of said nodes acting as a destination node via one or more other of said nodes acting as sub-destination nodes in response to the source node calling the destination node,

each sub-destination node being determined by the link or neighboring node selected from said first stored list in the source node or in a preceding sub-destination node,

the datagram being arranged to designate at least some of said sub-destination nodes as circuit nodes and to store circuit data in the memory means for the circuit nodes,

said circuit data establishing a temporary circuit for date transmission between the source and destination nodes via said circuit nodes,

each node traversed by said datagram which is not the source node, the destination node or a circuit node being determined by selecting that link or neighboring node from said second stored list in the immediately preceding node which is associated with a following designated circuit node in the path of the datagram,

the criteria on which said first and second stored lists in each node are based being distinct and being biased towards optimum transmission of said data in said temporary circuit and optimum establishment of said temporary circuit, respectively.

2. A distributed communications network as in claim 1, wherein link or neighboring node entries in said first stored list of said nodes are those entries which minimize hop-count for circuits of said nodes to the respective destination nodes.

3. A distributed communications network as in claim 2, wherein link or neighboring node entries in said second stored list of said nodes are those entries which minimize the time taken for the datagram to travel to a next successive circuit node for circuits to the respective destination nodes.

4. A distributed communications network as in claim 3, wherein:

each node is arranged to update its second stored list in response to delay information received from a neighboring one of said nodes which relates to the transmission delay between that neighboring node and a distant one of said nodes in the network,

each node being arranged to add to said transmission delay the additional delay associated with receiving the delay information over the link from the neighboring node, to transmit the resulting total delay information to its other neighboring nodes if any, and to measure said additional delay by transmitting and receiving a timing packet over the link via which the delay information was received.

5. A distributed communications network as in claim 3, wherein each node is arranged to update its first stored list in response to hop-count information received from a neighboring one of said nodes which relates to hop-count between that neighboring one of said nodes and a distant node in the network, each node being arranged to increment the hop-count information from a neighboring node and to communicate the incremented hop-count to its other neighboring nodes if any.

6. A distributed communications network as in claim 5, wherein:

each node is arranged to update its second stored list in response to delay information received from a neighboring one of said nodes which relates to the transmission delay between that neighboring node and a distant one of said nodes in the network.

7. A distributed communication network as in claim 6, wherein the nodes are arranged to give the transmission of data for updating said stored lists priority over the transmission of datagrams governing the establishment and release of circuits and to give priority to the transmission of said datagrams over the transmission of data in the circuits established by such datagrams.

8. A distributed communications network as claimed in claim 6 wherein

each node is arranged to communicate changes in at least one of its said first and said second stored lists to selected neighboring nodes in dependence upon the updated entries in said at least one of its said first and said second stored lists,

each updated link or neighboring node entry being communicated via only those links to neighboring nodes which do not correspond to that entry.

9. A distributed communications network as in claim 8 wherein

each node further includes third and fourth stored lists of its links or neighboring nodes,

each destination node in the stored list of destination nodes being associated with the link or neighboring node in said third and fourth stored lists,

the criteria on which the entries in said third and fourth stored lists are based being distinct and being biased towards near optimum transmission of said data in said temporary circuit and near optimum establishment of said temporary circuit, respectively, and

wherein each node is arranged to communicate changes in its said first, second, third and fourth stored lists to selected neighboring nodes in dependence on the updated entries in its said first, second, third and fourth stored lists, each updated link or neighboring node entry of the first and fourth stored lists being communicated via that link to a neighboring node which is the associated entry in the said second stored list and each updated link or neighboring node entry of the second and third stored lists being communicated via that link to a neighboring node which is the associated entry in the said first stored list.

10. A distributed communications network as in claim 1 wherein

each node is responsive to conditions in the network to update at least one of its said first and said second stored lists,

each node being arranged to communicate changes in at least one of its said first and said second stored lists to its neighboring nodes and to modify at least one of its said first and said second stored list in response to updating information received from its neighboring nodes.

11. A distributed communications network as in claim 10, wherein

each node further includes third and fourth stored lists of its links or neighboring nodes,

each destination node in the stored list of destination nodes being associated with the link or neighboring node in said third and fourth stored lists,

the criteria on which the entries in said third and fourth stored lists are based being distinct and being biased towards near optimum transmission of said data in said temporary circuit and near optimum establishment of said temporary circuit, respectively.

12. A distributed communications network as in claim 11, wherein

link or neighboring node entries in said third stored list of said nodes represent sub-optimal hop-count for circuits to the respective destination nodes and link or neighboring node entries in said fourth stored list of said nodes represent sub-optimum time taken for the datagram to travel a successive sub-destination node for circuits to the respective destination nodes.

13. A distributed communications network as in claim 10 wherein

each node is arranged to communicate changes in at least one of its first and said second stored lists to selected neighboring nodes in dependence upon the updated entries in said at least one of its said first and said second stored lists,

each updated link or neighboring node entry being communicated via only those links to neighboring nodes which do not correspond to that entry.

14. A distributed communications network as in claim 13 wherein

each node further includes third and fourth stored lists of its links or neighboring nodes,

each destination node in the stored list of destination nodes being associated with the link or neighboring node in said third and fourth stored lists,

the criteria on which the entries in said third and fourth stored lists are based being distinct and being biased towards near optimum transmission of said data in said temporary circuit and near optimum establishment of said temporary circuit, respectively,

each node further including third and fourth stored lists of its links or neighboring nodes,

each destination node in the stored list of destination nodes being associated with the link or neighboring node in said third and fourth stored lists,

the criteria on which the entries in said third and fourth stored lists are based being distinct and being biased towards near optimum transmission of said data in said temporary circuit and near optimum establishment of said temporary circuit, respectively, and

each node being arranged to communicate changes in its said first, second, third and fourth stored lists to selected neighboring nodes in dependence on the updated entries in its said first, second, third and fourth stored lists, each updated link or neighboring node entry of the first and fourth stored lists being communicated via that link to a neighboring node which is the associated entry in the said second stored list and each updated link or neighboring node entry of the second and third stored lists being communicated via that link to a neighboring node which is the associated entry in the said first stored list.

15. A distributed communications network as in claim 12, 6, 7, 8, 9, 13 or 14, wherein

each node is arranged to communicate updating information to neighboring nodes for updating their first and said second stored lists,

said updating information being communicated within routing information packets, each routing information packet containing at least one routing element which includes a node address and the entries for that node address in said first and said second stored lists,

there being at most one routing element corresponding to each node address in a single routing information packet.

16. A distributed communications network as in claim 5, 4, 10, 11, 12, 6, 7, 8, 13, or 14 wherein each new node is arranged to indicate its existence to its neighboring nodes by sending them an identification routing information packet comprising its own node address and entries of zero for said first and second stored lists of its neighboring nodes.

17. A distributed communications network as in claim 1 wherein

said circuit data stored by the datagram which is sent from the source node includes connection structure information comprising a call identifier which is unique to a circuit being established by the datagram and also upstream and downstream links to those circuit nodes which are respectively upstream and downstream of the circuit node currently being visited by the datagram,

said currently visited circuit node being arranged to check that the call identifier currently being stored by the datagram is not identical with a call identifier already stored in that circuit node,

the data being arranged up update its connection structure information as it traverses successive nodes in the circuit.

18. A distributed communications network as in claim 17, wherein

in the event that said currently visited circuit node determines that the call identifier currently being stored by the datagram is identical with a call identifier already stored in that circuit node, the currently visited circuit node is arranged to check the stored connection structure associated with the already-stored call identifier and in the event that the upstream link of the stored connection structure does not lead to the circuit node last visited by the datagram, is arranged to cancel its status as a circuit node and to return the datagram to the last-visited circuit node, said last-visited circuit node being arranged to re-send the returned datagram to an alternative sub-destination node in an attempt to construct a circuit to said destination node.

19. A distributed communications network as in claim 18, wherein

each node further includes a third stored list of its links or neighboring nodes, each destination node in said stored list of destination nodes being associated with a link or neighboring node in said third stored list, the criterion on which the entries in said third stored list are based being biased towards near optimum transmission of said data in said temporary circuit, and,

when instructed by a datagram to attempt to establish an alternative data circuit, does so by selecting that link or neighboring node entry in said third stored list which corresponds to the desired destination node.

20. A distributed communications network as in claim 19, wherein each node is arranged to record, when acting as a source node, failed attempts to establish a circuit.

21. A distributed communications network as in claim 19, wherein each node is arranged to make further attempts to establish a circuit by sending datagrams via remaining links or neighboring nodes in sequence.

22. A distributed communications network as in claim 1 wherein

each node is arranged to monitor the spare data-carrying capacity of each of its links and in the event that it receives a datagram designating it as a circuit node but the downstream link in a circuit being established by the datagram has insufficient date-carrying capacity, is arranged to transmit a datagram to the source node to instruct it to attempt to establish an alternative circuit to the destination node.

23. A distributed communications network as in claim 1 wherein

each node is arranged to monitor its links to the neighboring nodes and is arranged, in the event that such a link fails, to update at least one of its said first and said second stored lists accordingly and to communicate to all its remaining neighboring nodes and changes in its said first and said second stored lists which result from link failure.

24. A distributed communications network as in claim 23, wherein

each node is arranged to store in its memory means in respect of each of its links, a list of pointers to stored connection structures in which that link is an upstream link in a said data transmission circuit passing through that node, and a list of pointers to stored connection structures in which that link is a downstream link in a said data transmission circuit passing through that node,

the node being arranged to detect failure of any of its links, to search the lists of pointers relating to any failed link, and to send datagrams over each remaining link of the connection structures indicated by the pointers relating to the failed link,

each connection structure including an upstream link which is directed towards a source node and a downstream link which is directed towards a destination node,

each said datagram which is sent via an upstream link being arranged to instruct the associated source node to attempt to establish an alternative circuit and

each datagram which is sent via a downstream link being arranged to cancel the downstream portion of the circuit which is interrupted by the link failure.

25. A distributed communications network as in claim 1 wherein each node is arranged to send, on receiving a datagram which designates it a destination node, an acknowledgement datagram back to the corresponding source node.

26. A distributed communications network as in claim 25, wherein each node is arranged to send, when acting as a source node, a further datagram to attempt to establish a circuit in the event that it receives no acknowledgement datagram within a predetermined period after sending the first-mentioned datagram.

27. A distributed communications network as in claim 1 wherein all information carried by said links is in time-division multiplexed form.