System and method for internodal information routing within a communications network

• US 6,785,277 B1
• Filed: 08/06/1998
• Issued: 08/31/2004
• Est. Priority Date: 08/06/1998
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Sundling, Karl Johan Marten, Gilén, Christer
• Primary Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/130,184
• Time in Patent Office: 2,217 Days
• Field of Search: 370/254, 370/255, 370/256, 370/389, 370/392
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A system and method for facilitating the routing of small information packages between nodes in a network. In particular, the system and method of the present invention utilize a routing table at each node of the network. The routing table for each node contains a list of the nodes, ordered the same in each table, and an indexing value is utilized to refer to particular node values. Internodal linkage information is also stored in the routing table along with an alternative link should the primary link fail. The addition/deletion of nodes and the failure of any link is handled by an update function.

Claims

1. A network having a plurality of interconnected nodes, the network comprising:

a plurality of processors for executing commands;

a plurality of nodes for transmitting at least one message packet, each of said plurality of nodes including a respective one of said plurality of processors;

a plurality of routing links for interconnecting said plurality of nodes;

a plurality of routing tables respectively corresponding to each of said plurality of nodes, each of said routing tables comprising an ordered table of said plurality of nodes, the position of each node within each of said routing tables being the same;

a set of commands embodied on the plurality of processors, the set of commands causes the processors to;

retrieve, from the routing table of a first of said nodes, a first routing link for a message packet from said first node to a second of said nodes through said plurality of interconnected nodes, wherein the position of said second node within said first routing table is utilized in retrieving said first routing link;

transmit said message packet from said first node to said second node across said first routing link;

modify said plurality of interconnected nodes;

update the respective routing table of the first node to indicate the modified configuration of said plurality of interconnected nodes;

forward a node change command to the plurality of interconnected nodes other than the first node, said node change command updating respective routing tables of said plurality of interconnected nodes;

wait, at each of said plurality of interconnected nodes, for receipt of the node change command; and

update, upon receipt of the node change command by each of said plurality of interconnected nodes, the respective routing table for each node of the plurality of nodes.

2. The network according to claim 1, wherein an index value is associated with the position of each node within the respective routing tables.

3. The network according to claim 2, wherein said index value comprises an integer offset within the respective routing tables.

4. The network according to claim 1, wherein the routing table of said first node comprises a plurality of alternative routing links for said message packet from said first node to said second node through said plurality of interconnected nodes.

5. The network according to claims 4, wherein said set of commands further causes the processors to retrieve a second routing link from said first node routing table, said second routing link being utilized when said first routing link is unavailable.

6. The network according to claim 4, wherein said plurality of alternative routings within said routing table for said first node are linked via a linked list.

7. The network according to claim 1, wherein said message packet is dynamically routed from said first node to said second node through a plurality of intermediate nodes, the position of said second node within said first routing table and the respective routing tables associated with said intermediate nodes being utilized in dynamically routing said message packet to said second node.

8. The network according to claim 1, wherein when said message packet reaches said second node, said set of commands further causes the processes to retrieve from the routing table associated therewith no further routing links, said message packet being applied at said second node.

9. The network according to claim 1, wherein a plurality of pathways interconnect said plurality of interconnected nodes, each of said pathways having a transmission cost associated therewith, said first routing link for said message packet from said first node to said second node having the lowest cost for a transmission from said first node to said second node through said plurality of interconnected nodes.

10. The network according to claim 9, wherein a second routing link, at said routing table of said first node, has the second lowest cost for said transmission, said second routing link being utilized when said first routing link is unavailable.

11. The network according to claim 1, wherein said change in the configuration to said plurality of interconnected nodes is the connection of another node to at least one of said plurality of interconnected nodes, said another node being inserted at a given position into each of said routing tables and into another routing table associated with said another node, the position of each node within all of said routing tables being the same.

12. The network according to claim 1, wherein said change in the configuration to said plurality of interconnected nodes is the disconnection of a given one of said plurality of interconnected nodes, said given node being removed from a respective position within each of said routing tables, the routing table for said given one of said nodes being deleted, the position of each remaining node within all of the remaining routing tables being the same.

13. The network according to claim 1, wherein each of said nodes comprise a component selected from the group consisting of computers, servers, processors and other computing devices.

14. The network according to claim 1, wherein said plurality of interconnected nodes are arranged in a configuration selected from the group consisting of a star, a ring and other topological configurations.

15. The network according to claim 1, wherein the size of said message packet is within the range of 1-50 bytes.

16. The network according to claim 1, wherein the number of said plurality of nodes is within the range of 2 to 100.

17. The network according to claim 16, wherein the number of said plurality of nodes is within the range of 2 to 50.

18. The network according to claim 17, wherein the number of said plurality of nodes is within the range of 5 to 10.

19. The network according to claim 18, wherein the number of said plurality of nodes is within the range of 5 to 7.

42. The communication system according to claim 1, wherein said node change command generates at least one of the following modifications:

adding another node to the respective routing tables, and

deleting at least one of said plurality of interconnected nodes from the respective routing tables.

43. The communication system according to claim 1, wherein updating the respective routing links includes analyzing respective transmission costs associated with the respective routing links, said first routing link being the lowest cost routing link.

20. In a communication system having a plurality of interconnected nodes, a method for routing a message packet from a first of said nodes to a second of said nodes, said method comprising:

referring, within said first node, to a first routing table associated therewith, each of said plurality of nodes within said communication system having a respective routing table associated therewith, each of said routing tables comprising an ordered table of said plurality of nodes, the position of each node within each of said routing tables being the same;

retrieving, from said first routing table associated with said first node, a first routing link for said message packet to said second node through said plurality of interconnected nodes, wherein, in said steps of referring and retrieving, the position of said second node within said first routing table is utilized in retrieving said first routing link;

transmitting said message packet from said first node to said second node across said first routing link;

modifying a configuration of said plurality of interconnected nodes;

updating the respective routing table of the first node to indicate the modified configuration of said plurality of interconnected nodes;

forwarding a node change command to the plurality of interconnected nodes other than of the first node, said node change command updating respective routing tables of said plurality of interconnected nodes;

waiting, at each of said plurality of interconnected nodes for receipt of the node change command; and

upon receipt of the node change command by each of said plurality of interconnected nodes, updating the respective routing table for each node of the plurality of nodes.

21. The method according to claim 20, wherein, an index value is associated with the position of each node within the respective routing tables.

22. The method according to claim 21, wherein said index value comprises an integer offset within the respective routing tables.

23. The method according to claim 20, wherein, in said step of retrieving, a second routing link to said second node is retrieved from said first routing table, said second routing link comprising an alternative routing link for said message packet from said first node to said second node through said plurality of interconnected nodes, said second routing link being utilized in said step of transmitting when said first routing link is unavailable.

24. The method according to claim 20, wherein said first routing table comprises a plurality of alternative routing links for said message packet from said first node to said second node through, said plurality of interconnected nodes.

25. The method according to claim 20, further comprising:

repeating the steps of referring, retrieving and transmitting a plurality of times when said first and second nodes are separated by at least one other node there between, the first routing link in said first routing table comprising a link to an intermediate node, said message packet being transmitted from said intermediate node across another routing link toward said second node.

26. The method according to claim 25, wherein said step of repeating dynamically routes said message packet from said first node to said second node through a plurality of intermediate nodes, the position of said second node within said first routing table and the respective routing tables associated with said intermediate nodes being used to dynamically route said message packet to said second node.

27. The method according to claim 20, further comprising the step of applying, upon receipt at said second node, said message packet at said second node.

28. The method according to claim 20, wherein a plurality of pathways interconnect said plurality of interconnected nodes, each of said pathways having a transmission cost associated therewith, said first routing link for said message packet from said first node to said second node having the lowest cost for a transmission from said first node to said second node through said plurality of interconnected nodes.

29. The method according to claim 28, wherein a second routing link, at said routing table of said first node, has the second lowest cost for said transmission, said second routing link being utilized by said retrieval and transmission means when said first routing link is unavailable.

30. The method according to claim 20, wherein updating the respective routing links includes analyzing respective transmission costs associated with the respective routing links, said first routing link being the lowest cost routing link.

31. The method according to claim 20, further comprising the following steps:

(a) after detection of a transmission cost change between said first and second nodes within said communication system, modifying the respective routing tables of said first, second and a plurality of intermediate nodes there between to order respective alternative routes between said first and second node pursuant to cost;

(b) forwarding a node change command to nodes adjacent said first, second and intermediate nodes.

44. The method according to claim 28, wherein said modifying at least one said plurality of interconnected nodes includes at least one of the following:

connecting another node to at least one of said plurality of interconnected nodes, and

removing at least one of said plurality of interconnected nodes from said communication system.

45. The method according to claim 20, wherein said node change command generates at least one of the following modifications:

adding another node to the respective routing tables, and

deleting at least one of said plurality of interconnected nodes from the respective routing tables.

32. A communication system having a plurality of interconnected nodes, said communication system comprising:

a plurality of routing tables, each of said routing tables corresponding to a respective one of said nodes, each routing table having a plurality of node identifiers being ordered in accordance to index values associated with the node identifiers; and

address translation means for translating a first address space of said node identifiers for each of said plurality of interconnected nodes to a second address space, said first address space comprising an ordered list of said node identifiers, said second address space comprising the index values corresponding to the position of each node identifier within each of said muting tables, the respective position of each said node identifier within each of said muting tables being the same.

33. The communication system according to claim 32, further comprising:

retrieval means to retrieve, from the routing table of a first of said nodes, a first routing link for a message packet from said first node to a second of said nodes through said plurality of interconnected nodes, and

transmission means for transmitting said message packet from said first node to said second node across said first routing link.

34. The communication system according to claim 33, wherein the position of said second node within said first routing table is utilized by said retrieval means in retrieving said first routing link.

35. The communication system according to claim 32, wherein each of said index values comprises an integer offset within the respective routing tables.

36. The communication system according to claim 33, wherein the routing table of said first node comprises a plurality of alternative routing links for said message packet from said first node to said second node through said plurality of interconnected nodes.

37. The communication system according to claim 36, wherein said retrieval means retrieves a second routing link from said first node routing table, said second routing link being utilized by said transmission means when said first routing link is unavailable.

38. The communication system according to claim 36, wherein said plurality of alternative routings within said routing table for said first node are linked via a linked list.

39. The communication system according to claim 33, wherein said message packet is dynamically routed from said first node to said second node through a plurality of intermediate nodes, the position of said second node within said first routing table and the respective routing tables associated with said intermediate nodes being utilized by said retrieval means in dynamically routing said message packet to said second node.

40. The communication system according to claim 33, wherein a plurality of pathways interconnect said plurality of interconnected nodes, each of said pathways having a transmission cost associated therewith, said first routing link for said message packet from said first node to said second node having the lowest cost for a transmission from said first node to said second node through said plurality of interconnected nodes.

46. The communication system according to claim 32, wherein each said node identifier may represent an alphanumeric string of characters.

47. The communication system according to claim 32, wherein each of said index values may represent an integer reference of varying bit values.

41. In a communication system having a plurality of interconnected nodes, a method for routing a message packet from a first of said nodes to a second of said nodes, said method comprising:

ordering a plurality of node identifiers in accordance to index values associated with the node identifiers within each of a plurality of routing tables corresponding to a respective one of said nodes;

mapping a first address space of said node identifiers for each of said plurality of interconnected nodes to a second address space, said first address space comprising an ordered list of said node identifiers, said second address space comprising the index values corresponding to the position of each node identifier within each of said routing tables for said interconnected nodes, the respective position of each said node identifier within each of said routing tables being the same;

referring, with said first node, to a first routing table associated therewith;

retrieving, from said first routing table associated with said first node, a first routing link for said message packet to said second node through said plurality of interconnected nodes; and

transmitting said message packet from said first node to said second node across said first routing link.

48. The method according to claim 41, wherein each said node identifier may represent an alphanumeric string of characters.

49. The method according to claim 41, wherein each of said index values may represent an integer reference of varying bit values.