Architecture and mechanism for forwarding layer interfacing for networks

• US 7,116,640 B2
• Filed: 12/22/2000
• Issued: 10/03/2006
• Est. Priority Date: 12/22/2000
• Status: Expired due to Term

• Current Assignee: Genuity Inc. (Lumen Technologies, Inc.), Raytheon BBN Technlogies Corp. (Rtx Corporation)
• Original Assignee: Level 3 Communications LLC (Lumen Technologies, Inc.)
• Inventors: Redi, Jason Keith, Pearson, David Spencer, Tasman, Mitchell Paul
• Primary Examiner(s): MARCELO, MELVIN C
• Application Number:
  US09/748,621
• Publication Number:
  US 20020080755A1
• Time in Patent Office: 2,111 Days
• Field of Search: 370/252, 370/345, 370/349, 370/390, 370/392, 370/474, 370/475
• US Class Current: 370/252
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/52 Multiprotocol routers
• CPC Class Codes: H04L 49/00 Packet switching elements
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 88/02 Terminal devices
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

A communications apparatus (2) in a communications network (100 or 110) is provided for communication among a plurality of communication apparatuses. The communications apparatus (2) routes messages for neighboring apparatuses. The communications apparatus (2) includes a memory (4, 7 or 8), a processor (3) and a transceiver (6). The memory has a plurality of routing managers (12, 13, and 14) stored thereon, and each manager maintains at least one network table including one or more entries. The processor 3 selects at least one network table from those maintained by the plurality of routing managers (12, 13 and 14) that are stored in the memory (4, 7 or 8), based on an address indicator and/or on a type-of-service of a message. The processor 3 extracts network information from the selected network table or tables. The processor (3) also controls transmission of the message according to the extracted network information. The transceiver (6) transmits and receives messages.

Claims

1. A mobile communications station for use in a wireless communications network including a plurality of mobile communications stations, each station being configurable to route message packets for neighboring stations, said mobile communications station including a transceiver to transmit and receive message packets, said mobile communications station comprising:

an electronic memory circuit having network information stored thereon; and

an electronic processor circuit which (i) determines a routing type for a message packet;

(ii) selects a class of routing managers from a plurality of routing managers based on the determined routing type;

(iii) selects at least one network table corresponding to the selected class of routing managers;

(iv) selects a radio profile for the message packet; and

(v) causes the message packet to be transmitted according to information contained in the network tables and radio profile.

2. A mobile communications station according to claim 1, wherein a routing type comprises one of unicast, broadcast and multicast routing.

3. A mobile communications station according to claim 2, wherein said electronic processor circuit determines a routing type based on an address indicator of the message packet.

4. A mobile communications station according to claim 3, wherein when the address indicator is a unicast address and the unicast address does not match a unicast address of said mobile communications station, said electronic processor circuit determines a type-of-service indicator of the message packet and uses the type-of-service indicator to index into a forwarding table number lookup table to select the network table.

5. A mobile communications station according to claim 4, wherein said electronic processor circuit uses the type-of-service indicator to index into a queuing table to select a queuing discipline, and causes the message packet to be processed according to the queuing discipline.

6. A mobile communications station according to claim 4, wherein the network table is comprised of a next-hop table, a neighbor table, and a radio profile table.

7. A mobile communications station according to claim 6, wherein said electronic processor circuit indexes into the next-hop table by a destination indicator of the message packet to find a corresponding neighbor index, and uses the neighbor index to index into a neighbor table, the neighbor table having one or more entries each indexed according to neighboring stations, said electronic processor circuit selecting from the neighbor table at least a radio profile index number and a neighbor address, wherein said electronic processor circuit selects the radio profile by using the radio profile index number to index into the radio profile table.

8. A mobile communications station according to claim 7, wherein the radio profile is in an opaque format.

9. A mobile communications station according to claim 3, wherein when the address indicator is a unicast address and the unicast address does not match a unicast address of said mobile communications station, said electronic processor circuit determines a type-of-service indicator of the packet and uses the type-of-service indicator to select from a table data corresponding to a queuing discipline.

10. A mobile communications station according to claim 3, wherein the network information stored in said electronic memory circuit comprises the network table including a broadcast radio profile index table having one or more entries, each entry corresponding to a radio profile index number, and a broadcast radio profile table having one or more entries, each entry corresponding to a radio profile.

11. A mobile communications station according to claim 10, where when the address indicator is a broadcast address said electronic processor circuit determines a type-of-service indicator from the packet and uses the type-of-service indicator to index into the broadcast radio profile index table to select a radio profile index number.

12. A mobile communications station according to claim 11, wherein said electronic processor circuit uses the selected radio profile index number to index into the broadcast radio profile table to select the radio profile.

13. A mobile communications station according to claim 3, wherein the network information comprises a plurality of network tables, each network table including a next-hop table, a neighbor table having node addresses and radio profile indices as entries, and a radio profile table.

14. A mobile communications station according to claim 13, wherein when the address indicator is a multicast group number, said electronic processor circuit selects the network table according to a type-of-service indicator, and uses an address of the source station of the message to identify a next-hop table to retrieve a data structure corresponding to next-hops.

15. A mobile communications station according to claim 14, wherein said electronic processor circuit uses the data structure of next-hops to index into an associated neighbor table to obtain neighbor addresses and radio profile index numbers corresponding to the multicast packet.

16. A mobile communications station according to claim 1, further comprising a metric calculator that supplies network routing information to at least one of the plurality of routing managers.

17. A mobile communications station according to claim 1, wherein said electronic processor circuit generates information regarding a received signal.

18. A mobile communications station according to claim 1, wherein said electronic memory stores a plurality of software modules and said electronic processor circuit maintains an interface between the plurality of software modules.

19. A mobile communications station which communicates among a plurality of mobile stations in a network in which stations are arranged in clusters of communication member stations, with one member station in each cluster being a head station for the cluster, each member station communicating with the network through one or more cluster head stations, the cluster head stations communicating with other cluster head stations, said mobile communications station comprising:

an electronic memory circuit having network information stored thereon; and

an electronic processor circuit which (i) selects a routing manager from among a plurality of routing managers based on a type-of-service indicator associated with a message packet;

(ii) selects at least one network table maintained by the selected routing manager based at least in part on a source indicator of the message packet to be transmitted;

(iii) determines a transmission profile; and

(iv) causes the message packet to be transmitted according to information contained in the network table and transmission profile.

20. Computer executable code stored on a computer readable medium, the code to operate a communications router to route messages in a network including a plurality of routers, each router having a multi-layered system architecture including a forwarding layer and a plurality of routing modules each of which maintains at least one network table, said computer executable code comprising:

code to direct the forwarding layer to select a class of routing modules from the plurality of routing modules based on an address indicator of a message;

code to index into at least one network table corresponding to the selected class of routing modules to obtain network information;

code to select a radio profile for the message;

code to direct the transmission of the message as specified by the network information and radio profile; and

code to provide an interface at least between the forwarding layer and the plurality of routing modules.

21. In a communications system for communication among plural member communication stations in a network in which at least one of the member stations route messages for neighboring stations, each of the member stations having a multi-layered architecture including a forwarding layer, and each of the member stations having a plurality of routing managers that have access to the forwarding layer through an interface, a method of operating a communications station comprising the steps of:

selecting a class of routing managers from the plurality of routing managers based on an address indicator of a message;

selecting routing criteria for the message from information maintained by the selected class of routing managers; and

transmitting the message based on the selected criteria.

22. A communications apparatus in a network for communication among a plurality of communications apparatuses, said communications apparatus routing messages for neighboring apparatuses, said communications apparatus comprising:

an electronic memory circuit having a plurality of routing managers stored thereon, each manager defining at least one network table including a plurality of entries;

an electronic processor circuit which (i) selects a class of routing managers from the plurality of routing managers stored in said electronic memory circuit based on an address indicator of a message;

(ii) extracts network information from the at least one network table maintained by the selected class of routing managers; and

(iii) controls transmission of the message according to the extracted network information; and

a transmitter which transmits messages.

23. A wireless mobile communication station for communication among a plurality of stations in a wireless, mobile network having changing topology, said mobile station routing messages for neighboring stations, said mobile station comprising:

metric calculation means for calculating networking routing conditions; and

means for transmitting packets of information, said transmitting means comprising;

forwarding means for selecting among a plurality of routing managers and for assigning forwarding information to a packet based on information maintained by a selected routing manager; and

queuing means for queuing the packet for transmission.

24. A mobile communications station for use in a wireless communications network including a plurality of mobile communications stations, each station being configurable to route message packets for neighboring stations, said mobile communications station including a transceiver to transmit and receive message packets, said mobile communications station comprising:

memory means for storing network information; and

processing means for (i) determining a routing type for a message packet;

(ii) selecting a routing manager from a plurality of routing managers that corresponds to the determined routing type;

(iii) selecting at least one network table corresponding to the selected routing manager;

(iv) selecting a radio profile for the message packet; and

(v) causing the message packet to be transmitted according to information contained in the network table and radio profile.

25. In a communications system for communication among a plurality of member stations in a network in which at least one of the member stations routes messages for a neighboring station, each of the member stations having a transceiver and a multi-layered architecture including a forwarding layer, and each of the member stations having a plurality of routing managers that each maintains at least one table that is made accessible to the forwarding layer via an interface, a method of operating a communications station to route messages including unicast messages, a unicast message including a type-of-service indicator and a destination indicator, said method comprising the steps of:

selecting a unicast routing manager from the plurality of routing managers when a message contains a unicast address and when the unicast address does not match an address of the communications station, the unicast routing manager maintaining a plurality of forwarding tables;

selecting a forwarding table from the plurality of forwarding tables according to the type-of-service indicator, the selected forwarding table including a next-hop table, a neighbor table, and a radio profile table;

indexing into the next-hop table by the destination indicator to find a corresponding neighbor index, and using the neighbor index to index into the neighbor table, the neighbor table having at least one entry including neighbor addresses and radio profile indices;

selecting from the neighbor table at least a radio profile index and a neighbor address, and using the selected radio profile index to select a radio profile from the radio profile table; and

transmitting the message according to the selected neighbor address and the selected radio profile.

26. A method according to claim 25, wherein the radio profile is opaque with respect to the forwarding layer.

27. A method according to claim 25, wherein the multi-layered architecture includes queuing disciplines and a queuing discipline is selected based on the type-of-service indicator to queue the unicast message.

28. In a communications system for communication among a plurality of member stations in a network in which at least one of the member stations routes messages for a neighboring station, each of the member stations having a transceiver and a multi-layered architecture including a forwarding layer, and each of the member stations having a plurality of routing managers that each maintains at least one table that is made accessible to the forwarding layer via an interface, a method of operating a member station to route messages including multicast messages, a multicast message including a type-of-service indicator and an originating source indicator, said method comprising the steps of:

selecting a multicast routing manager from the plurality of routing managers when a message contains a multicast address, the multicast routing manager maintaining one or more forwarding tables;

selecting a forwarding table according to the type-of-service indicator, the selected forwarding table including an origin map table, a next hop-table, a neighbor table, and a radio profile table;

indexing into the origin map table by the originating source indicator to identify the corresponding next-hop table;

indexing into the next-hop table using the multicast address to identify the set of corresponding neighbor indices, and using the neighbor indices to index into the neighbor table, the neighbor table having the plurality of entries including neighbor addresses and radio profile indices;

selecting from the neighbor table at least one radio profile index and neighbor address, and using the selected radio profile index to select at least one corresponding radio profile from the radio profile table; and

transmitting the message to the next-hop neighbor addresses according to the at least one corresponding selected radio profile.

29. A method according to claim 28, wherein the multicast address comprises a multicast group identifier.

30. A method according to claim 28, wherein the next-hop table includes a previous-hop indicator, and the multicast message includes a previous-hop indicator, and after a next-hop table has been selected, said method comprises the steps of:

comparing the previous-hop indicator in the multicast message against the previous-hop indicator of the selected next-hop table, and

forwarding the message only if the previous-hop indicators match.

31. A method according to claim 28, wherein the neighbor addresses comprise an address for the member station.

32. A method according to claim 31, further comprising the step of delivering the message to the member station.

33. A method according to claim 32, wherein the message is forwarded to a component of the member station.

34. A method according to claim 33, wherein the message is forwarded to the component without a radio profile.

35. A method according to claim 28, wherein at least one radio profile is opaque with respect to the forwarding layer.

36. In a communications system for communication among a plurality of member stations in a network in which at least one of the member stations routes messages for a neighboring station, each of the member stations having a transceiver and a multi-layered architecture including a forwarding layer, and each member station having a plurality of routing managers that each maintains at least one table that is made accessible to the forwarding layer via an interface, a method of operating a communications station to route messages including broadcast messages, a broadcast message including a type-of-service indicator, said method comprising the steps of:

selecting a broadcast routing manager from the plurality of routing managers when a message contains a broadcast address, the broadcast routing manager maintaining a broadcast radio profile index table having one or more entries with each entry corresponding to a radio profile index number, and a broadcast radio profile table having one or more entries with each entry corresponding to a radio profile;

indexing into the broadcast radio profile index table by using the type-of-service indicator to select a radio profile index number;

selecting a radio profile by indexing into the broadcast radio profile table with the selected radio profile index number; and

transmitting the message according to the selected radio profile.

37. A method according to claim 36, wherein the multi-layered architecture includes queuing disciplines, and a queuing discipline is selected based on the type-of-service indicator to queue the message.

38. A method according to claim 36, wherein the radio profile is opaque with respect to the forwarding layer.

39. In a communications system for communication among a plurality of member stations in a network in which at least one of the member stations routes messages for a neighboring station, each of the member stations having a transceiver and a multi-layered architecture including a forwarding layer, and each of the member stations having a plurality of routing managers that each maintains at least one table that is made accessible to the forwarding layer via an interface, a method of operating a communications station to route messages including unicast messages, a unicast message including a type-of-service indicator and a destination indicator, said method comprising the steps of:

selecting a class of unicast routing managers from the plurality of routing managers when a message contains a unicast address and when the unicast address does not match an address of the communications station, the class of unicast routing managers maintaining a plurality of forwarding tables;

selecting a forwarding table from the plurality of forwarding tables according to the type-of-service indicator, the selected forwarding table including a next-hop table, a neighbor table, and a radio profile table;

indexing into the next-hop table by the destination indicator to find a corresponding neighbor index, and using the neighbor index to index into the neighbor table, the neighbor table having at least one entry including neighbor addresses and radio profile indices;

selecting from the neighbor table at least a radio profile index and a neighbor address, and using the selected radio profile index to select a radio profile from the radio profile table; and

transmitting the message according to the next-neighbor address and the selected radio profile.

40. A method according to claim 39, wherein the radio profile is opaque with respect to the forwarding layer.

41. A method according to claim 40, wherein the multi-layered architecture includes queuing disciplines and a queuing discipline is selected based on the type-of-service indicator to queue the unicast message.

42. In a communications system for communication among a plurality of member stations in a network in which at least one of the member stations routes messages for a neighboring station, each of the member stations having a transceiver and a multi-layered architecture including a forwarding layer, and each of the member stations having a plurality of routing managers that each maintains at least one table that is made accessible to the forwarding layer via an interface, a method of operating a member station to route messages including multicast messages, a multicast message including a type-of-service indicator and an originating source indicator, said method comprising the steps of:

selecting a class of multicast routing managers from the plurality of routing managers when a message contains a multicast address, the class of multicast routing managers maintaining one or more forwarding tables;

selecting a forwarding table according to the type-of-service indicator, the selected forwarding table including a an origin map table, a next hop-table, a neighbor table, and a radio profile table;

indexing into the origin map table by the originating source indicator to identify the corresponding next-hop table;

indexing into the next-hop table using the multicast address to identify the set of corresponding neighbor indices, and using the neighbor indices to index into the neighbor table, the neighbor table having the plurality of entries including neighbor addresses and radio profile indices;

selecting from the neighbor table at least one radio profile index and neighbor address, and using the selected radio profile index to select at least one corresponding radio profile from the radio profile table; and

transmitting the message to the selected neighbor addresses according to the at least one corresponding selected radio profile.

43. A method according to claim 42, wherein the multicast address comprises a multicast group identifier.

44. A method according to claim 42, wherein the next-hop table includes a previous-hop indicator, and the multicast message includes a previous-hop indicator, and after a next-hop table has been selected, said method comprises the steps of:

comparing the previous-hop indicator in the multicast message against the previous-hop indicator of the selected next-hop table; and

forwarding the message only if the previous-hop indicators match.

45. A method according to claim 42, wherein the neighbor addresses comprise an address for the member station.

46. A method according to claim 45, further comprising the step of delivering the message to the member station.

47. A method according to claim 46, wherein the message is forwarded to a component of the member station.

48. A method according to claim 47, wherein the message is forwarded to the component without a radio profile.

49. A method according to claim 42, wherein at least one radio profile is opaque with respect to the forwarding layer.

50. A method to determine a forwarding table which includes routing data in a communications system having a plurality of nodes, said method comprising the steps of:

identifying a type-of-service indicator,

selecting a forwarding table from a plurality of forwarding tables based on the type-of-service indicator,

arranging the plurality of forwarding tables in a table, and setting a subset of entries in the table of forwarding tables.

51. A method to determine a forwarding table which includes routing data in a communications system having a plurality of nodes, said method comprising the steps of:

identifying a type-of-service indicator

selecting a forwarding table from a plurality of forwarding tables based on the type-of-service indicator,

arranging the plurality of forwarding tables in a table, and

setting different table entries in the table of forwarding tables with respective different routing managers.

52. A method of determining routing information comprising the steps of:

selecting a class of a routing manager based on an address indicator;

selecting a forwarding table based on a type-of service indicator; and

selecting data to access a next-hop address and a radio profile based on a destination address.

53. A method according to claim 52, wherein the forwarding table is maintained by any one of N unicast routing managers, where N is an integer greater than 1.

54. A method according to claim 52, wherein the forwarding table is maintained by at least two unicast routing managers.

55. A method for determining addresses of nodes in a communications network, said method comprising the steps of:

accessing a MAC translation table comprising a 16-to-48 bit node number mapping; and

supplying a 16-bit next-hop neighbor address and a corresponding 48-bit IEEE MAC address.

56. A method according to claim 55, wherein the neighbor address and the MAC address are supplied to a radio layer of a node in the communications system.

57. A method according to claim 56, further comprising the step of populating the MAC translation table by statically configuring each node in the communications system with the 16-to-48 bit node number mapping for all nodes with which the node communicates directly with.

58. A method according to claim 56, wherein the MAC translation table is populated according to the steps of examining messages arriving from other nodes;

looking at both the 48-bit IEEE MAC address of the previous-hop node and at the 16-bit previous-hop node number contained in the message; and

adding an entry to the MAC translation table when a message is received from a new node.

59. In a communications system for communication among a plurality of member stations in a network in which at least one of the member stations routes messages for a neighboring station, each of the member stations having a transceiver and a multi-layered architecture including a forwarding layer and an Internet Protocol (IP) module, a method of translating IP address numbers to node numbers comprising the steps of:

attaching the forwarding layer to the IP module as an Ethernet-class interface; and

translating IP address numbers to member station numbers via an Address Resolution Protocol (ARP).

60. The method according to claim 59, wherein said translating step further comprises the steps of:

assigning each member station in the communications system an IP address, each of the member stations comprising the same IP prefix;

constructing a pseudo MAC address for each member station, the pseudo MAC address comprising an embedded 16-bit node number; and

returning a pseudo MAC address when presented with an IP address for a member station.

61. A method according to claim 60, wherein the embedding is accomplished by placing the embedded 16-bit node number in at two least bytes of the pseudo MAC address;

wherein, the pseudo MAC address is 48-bits.

62. A method according to claim 60, further comprising the step of adding static entries comprising IP address-to-pseudo MAC address mappings to a local ARP cache of each member station in the communications system.

63. A method according to claim 60, further comprising the step of intercepting ARP requests as they are handed to the forwarding layer so as to locally generate ARP replies containing correct mappings.

64. A method according to claim 61, wherein for a unicast MAC address, the embedded 16-bit node number is extracted from the 48-bit pseudo MAC address.

65. A method of accessing routing data in a communications system, said method comprising the steps of:

constructing a set of tables which include non-redundant information;

constructing directly indexed tables;

linking related tables in the set of tables, and

accessing routing data in at least one table of the set of tables.

66. A method of processing messages from a local control module of a member station in a communications system including a plurality of member stations, said method comprising the steps of:

generating a message and providing the message from the control module to a forwarding layer; and

specifying for the message;

i) a unicast or broadcast next-hop address;

ii) a type-of-service for the message; and

iii) an identifier of a radio profile to be used when transmitting the message.

67. A method according to claim 66, wherein the radio profile identifier is used to index into a radio profile table.

68. A method according to claim 66, wherein the radio profile table is designated for messages from local control modules.

69. A method according to claim 66, wherein the type of-service is used to index into a type-of-service to queuing discipline table to retrieve queuing data.

70. A method of determining routing information comprising the steps of:

selecting a class of a routing manager based on an address indicator;

selecting a forwarding table based on a type-of service indicator; and

selecting data to access a next-hop address based on a source indicator.

71. A method according to claim 70, wherein the forwarding table is maintained by any one of N multicast routing managers, where N is an integer greater than 1.

72. A method of formatting a message in a communications network, said method comprising the steps of:

attaching data to the message, the data including forwarding information;

marking the message as forwardable or non-forwardable; and

if forwardable,

specifying in the data a unicast node number of the originating communications node.

73. A method according to claim 72, wherein when the message is a unicast message, said method further comprises the step of specifying in the data the unicast node number of the destination to which the message is addressed.

74. A method according to claim 72, wherein when the message is a broadcast message, said method further comprises the step of specifying in the data a broadcast address as the destination to which the message is addressed.

75. A method according to claim 72, wherein when the message is a multicast message, said method further comprises the step of specifying in the data the multicast group to which the message is addressed.

76. A method according to claim 72, wherein a message header includes the data.

77. A method according to claim 72, wherein a message trailer includes the data.