Characteristic routing

• US 20030026268A1
• Filed: 03/11/2002
• Published: 02/06/2003
• Est. Priority Date: 11/28/2000
• Status: Abandoned Application

• Current Assignee: Centerboard Incorporated
• Original Assignee: Siemens Technology-To-Business Center LLC (Siemens AG)
• Inventors: Navas, Julio Cesar
• Application Number:
  US10/096,154
• Publication Number:
  US 20030026268A1
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 2101/33 containing protocol addresses or telephone numbers
• CPC Class Codes: H04L 2101/375 Access point names [APN]
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/30 Managing network names, e.g. use of aliases or nicknames name-to-address mapping H04L61/45
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function

Abstract

A routing protocol, called characteristic routing, which allows data to be transported multi-hop through an internetwork from a sender to a set of receiver nodes using a description of the receiver nodes in the form of multiple arbitrary identifying descriptive names (called characteristics). Host nodes can have multiple dynamic characteristics. Characteristic routing is optimized to make the multiple-name case operate in a fast manner. In particular, characteristic routing creates an efficient routing table index using bit vectors and compression techniques. Using characteristic routing, the sender can choose whether the receiver nodes need to exactly match the characteristic routing address or certain characteristics in the routing address, or whether the receiver nodes can be simply “similar” to the characteristic routing address, or whether the receiver nodes have desired ranges of characteristics.

Claims

1. A method for routing a packet from over a network including multiple nodes, said method comprising steps of:

receiving a packet from a sender node over said network, wherein said packet is intended for at least one destination node having a plurality of defined characteristics, said plurality of defined characteristics being determinable by said sender node, and wherein said packet includes information on said plurality of defined characteristics;

said receiving step occurring at said at least one destination node having said plurality of defined characteristics;

wherein said plurality of defined characteristics is a subset of or a total set of multiple, arbitrary characteristics describing aspects of said multiple nodes in said network;

discovering a topology of said network based on said total set of multiple arbitrary characteristics, wherein said network couples said sender node, said at least one destination node, and at least one routing node, and wherein said discovering step is performed proactively before said packet is sent from said sender node and before said packet is received at said at least one destination node;

forwarding to said sender node a routing table including entries based on said particular characteristics of each node in network portions, wherein said routing table is not configured at each routing node; and

sending a copy of said packet based on said entries in said routing table.

2. The method of claim 1 wherein said discovering step is performed using a peek trailblazer packet.

3. The method of claim 1 wherein said packet includes said information on said plurality of defined characteristics in a header of said packet.

4. The method of claim 1 wherein said packet further includes an IP address, wherein said IP address may be a unicast or multicast address.

5. The method of claim 1, wherein each of said entries is a bit vector of said total set of multiple arbitrary characteristics, each of said multiple arbitrary characteristics having a predefined bit location in said bit vector.

6. The method of claim 1, wherein said packet includes said information on said plurality of defined characteristics in a predetermined location in a payload of said packet.

7. The method of claim 1, further comprising a step of sending said packet from said sender node, wherein said sending step uses a compression technique.

8. The method of claim 7, wherein each of said entries is an approximated bit vector of said total set of multiple arbitrary characteristics, and wherein said compression technique results in an approximated bit vector of said information on said plurality of defined characteristics.

45. The method of claim 1 wherein a border router on the edge between a network of higher bandwidth and a network of lower bandwidth will execute and translate between both a proactive and reactive algorithm in terms of said discovery step and said routing table configuration.

9. A method for routing a packet over a network including multiple nodes, said method comprising steps of:

sending a packet from a sender node over said network, wherein said packet is intended for at least one destination node having a plurality of defined characteristics, said plurality of defined characteristics being determinable by said sender node, and wherein said packet includes information on said plurality of defined characteristics, wherein said plurality of defined characteristics is a subset of or a total set of multiple, arbitrary characteristics describing aspects of said multiple nodes in said network;

discovering a topology of said network based on said total set of multiple arbitrary characteristics, wherein said network couples said sender node, said at least one destination node, and at least one routing node, and wherein said discovering step is performed reactively after said packet is sent from said sender node and said packet is received at the first of said routing nodes;

configuring a routing table in soft state at each routing node of said topology of network portions intermediate respective to said first of said routing nodes, said routing table including entries based on said particular characteristics of each node in said network portions; and

sending a copy of said packet based on said entries in said routing table to said at least one destination node having said plurality of defined characteristics.

10. The method of claim 9 wherein said discovering step includes said first of said routing nodes sending a route discovery request for said plurality of defined characteristics to destination nodes, and receiving from said destination nodes meeting said plurality of defined characteristics an acknowledgement.

11. The method of claim 9 wherein said packet includes said information on said plurality of defined characteristics in a header of said packet.

12. The method of claim 9 wherein said packet further includes an IP address, wherein said IP address may be a unicast or multicast address.

13. The method of claim 9, wherein each of said entries is a bit vector of said total set of multiple arbitrary characteristics, each of said multiple arbitrary characteristics having a predefined bit location in said bit vector.

14. The method of claim 9, wherein said packet includes said information on said plurality of defined characteristics in a predetermined location in a payload of said packet.

15. The method of claim 9, further comprising a step of sending said packet from said sender node, wherein said sending step uses a compression technique.

16. The method of claim 15, wherein each of said entries is an approximated bit vector of said total set of multiple arbitrary characteristics, and wherein said compression technique results in an approximated bit vector of said information on said plurality of defined characteristics.

17. The method of claim 16, wherein said compression technique comprises use of Bloom filters including a Bloom filter bit vector and a number of hash functions.

18. The method of claim 17 wherein a size of said Bloom filter bit vector is reduced when said network is unreliable and/or has low bandwidth.

19. The method of claim 17 wherein said number of hash functions is reduced when said network is unreliable and/or has low bandwidth.

20. The method of claim 19 wherein said number of hash functions comprises less than 4.

21. The method of claim 17 wherein said hash functions are derived from an MD5 encoding.

22. The method of claim 21 wherein said number of hash functions comprises 1 and said MD5 encoding is used as a single hash value modulo a size of said Bloom filter bit vector.

23. The method of claim 22 wherein said size of said Bloom filter bit vector is reduced when said network is unreliable and/or has low bandwidth.

44. The method of claim 21 wherein said number of hash functions comprises 2 and said MD5 encoding is halved and the two halves are used as the two hash values each modulo a size of said Bloom filter bit vector.

46. The method of claim 9 wherein a border router on the edge between a network of higher bandwidth and a network of lower bandwidth will execute and translate between both a proactive and reactive algorithm in terms of said discovery step and said routing table configuration.

47. The method of claim 22 wherein a border router on the edge between a network of higher bandwidth and a network of lower bandwidth will execute and translate between both a proactive and reactive algorithm in terms of said discovery step and said routing table configuration.

24. A method for efficient hierarchical routing in a low bandwidth network or in an unreliable network, said method comprising steps of:

representing a set of characteristics for a characteristic destination as a bit vector;

approximating the set of characteristics to provide a limit on an overall size of the bit vector representing the set of characteristics, said approximating step comprising utilizing a compression technique comprising Bloom filters; and

transmitting over the network a message utilizing the approximated set of characteristics.

25. The method of claim 24, wherein:

said Bloom filters have a Bloom filter bit vector comprising said bit vector and a number of hash functions less than 4.

26. The method of claim 25 wherein a size of said Bloom filter bit vector is reduced.

27. The method of claim 25 wherein said hash functions are derived from an MD5 encoding.

28. The method of claim 27 wherein said number of hash functions comprises 1 and said MD5 encoding is used as a single hash value modulo a size of said Bloom filter bit vector.

48. The method of claim 27 wherein said number of hash functions comprises 2 and said MD5 encoding is split into two and used as two hash values modulo a size of said Bloom filter bit vector.

29. A method of automatically configuring a characteristic network into a hierarchical organization, said characteristic network including a plurality of characteristic routers and a plurality of nodes, said method comprising the steps of:

discovering a topology of said characteristic network using a routing algorithm at each characteristic router, said routing algorithm including choosing a plurality of non-overlapping groups of characteristic routers that are connected and contiguous such that each characteristic router in said characteristic network belongs to exactly one group;

determining membership of particular characteristic routers in particular non-overlapping groups by inspecting relationships between said characteristic routers; and

regulating a size of each of said plurality of non-overlapping groups as individual characteristic routers either join or leave said characteristic network.

30. The method of claim 29 wherein said determining step groups characteristic routers such that each group contains characteristic routers that are adjacent, strongly connected to each other, and share a minimal number of border connections to characteristic routers in other groups.

31. The method of claim 30 wherein an algorithm finding all maximal cliques can be employed in said determining step.

32. The method of claim 30 wherein an algorithm finding all strongly connected characteristic routers can be employed in said determining step.

33. The method of claim 29 wherein said regulating step includes specifying a system-wide maximum node count and a minimum node count, said maximum node count and said minimum node count each being able to be specified depending on the environment of said characteristic network.

34. The method of claim 33 wherein said regulating step includes each group reviewing its membership of nodes to determine if that group as a whole has exceeded either said maximum node count or said minimum node count.

35. The method of claim 34 wherein each group divides into a plurality of groups if the maximum node count is exceeded by its current membership of nodes.

36. The method of claim 35 wherein said plurality of groups comprises two groups.

37. The method of claim 35 wherein each group disbands when its minimum node count is not met by its current membership of nodes, with nodes in said disbanded group join other adjacent groups.

38. The method of claim 34, wherein said maximum node count or said minimum node count can be specified at a low setting when said characteristic network comprises a bandwidth poor, resource poor wireless network.

39. The method of claim 29 wherein each non-overlapping group can be represented as a single routing node to provide for higher levels of hierarchical organization.

40. The method of claim 39 wherein border characteristic routers in each group maintain separate routing tables for each level of hierarchy and border characteristic routers in each group perform routing duties for packets entering and leaving the group.

41. The method of claim 40 wherein said border characteristic routers in each group also cooperate with each other to share information to jointly represent their group to the hierarchy.

42. The method of claim 39 wherein a single border characteristic router in each group performs all routing duties for packets entering and leaving the group.

43. The method of claim 42 wherein said single border characteristic router in each group is elected to represent the group to the hierarchy.