Method and apparatus for dynamically addressing and routing in a data network

• US 20020091855A1
• Filed: 02/01/2001
• Published: 07/11/2002
• Est. Priority Date: 02/02/2000
• Status: Abandoned Application

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Yemini, Yechiam, Florissi, Danilo, Grossberg, Michael D.
• Application Number:
  US09/775,350
• Publication Number:
  US 20020091855A1
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 41/5019 Ensuring fulfilment of SLA
• CPC Class Codes: H04L 41/5022 by giving priorities, e.g. assigning classes of service
• CPC Class Codes: H04L 41/5029 Service quality level-based billing, e.g. dependent on measured service level customer is charged more or less
• CPC Class Codes: H04L 41/5041 characterised by the time relationship between creation and deployment of a service
• CPC Class Codes: H04L 41/509 wherein the managed service relates to media content delivery, e.g. audio, video or TV
• CPC Class Codes: H04L 43/0852 Delays
• 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/12 Shortest path evaluation
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/507 Label distribution
• CPC Class Codes: H04L 45/62 Wavelength based optical switching H04Q11/0062
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/50 : Address allocation

Abstract

DART dynamically assigns addresses to Nodes according to their relative location within the network. When a Node joins or moves the network, or a Link or Node fails addresses are dynamically updated. If some Nodes are mobile (either clients or servers) the ability to route to and from the mobile Node persists. Link failures, caused by movement, or otherwise, can be similarly accommodated.

Claims

1. A network comprising a plurality of Nodes interconnected by Links, wherein:

(a) each Node is assigned a set of one or more coordinate labels, each representing a path comprising one or more Links or other Nodes;

(b) each coordinate label is unique to the Node to which it is assigned; and

(c) a path between a first Node and a second Node being determined from one of said coordinate labels associated with said first Node and one of said coordinate labels associated with said second Node.

2. The network of claim 1 where said coordinate label represents a path between said Node to which said coordinate label is assigned and a root Node.

3. The network of claim 1 where said coordinate label represents a path between said Node to which said coordinate label is assigned and at least one of a plurality of root Nodes.

4. The network of claim 1 where at least one of said plurality of No des is a computer file.

5. The network of claim 1 where at least one of said one or more Links is a directory access path.

6. The network of claim 1 where at least one of said plurality of Nodes is a computer process.

7. The network of claim 1 where at least one of said one or more Links is a directory access path.

8. The network of claim 1 where at least one of said Links is a virtual Link.

9. The network of claim 1 wherein each coordinate label representing a path comprises, in series, identifiers for Links and Nodes comprising said path.

10. The network of claim 1 wherein each of said set of one or more coordinate labels is periodically updated to reflect changes in said path.

11. The network of claim 1 wherein a Node identifier is indexed to at least one of said set of one or more coordinate labels, where said at least one of said set of one or more coordinate labels corresponds to at least one of said plurality of Nodes.

12. The network of claim 1 wherein said path is determined from said coordinate labels from said network and at least one coordinate label from at least one second network.

13. The network of claim 1 wherein at least one of said coordinate labels contains path information from said network and a second network.

14. The network of claim 13 where said path information from said second network indicates a backbone address.

15. The network of claim 1 wherein:

said first Node is a source Node; and

said second Node is a destination Node; and

data is routed from said source Node

to said destination Node via said path.

16. The network of claim 15 wherein said data is routed to a plurality of destination Nodes.

17. The network of claim 15 wherein said second node is located on a second network.

18. The network of claim 17 wherein said data is routed through at least one third network in order to reach said destination node.

19. The network of claim 1 wherein a tree of routing paths is computed from at least one of said set of one or more coordinate labels.

20. The network of claim 19 wherein data is routed to at least one of said plurality of Nodes according to said tree of routing paths.

21. The network of claim 1 wherein a multi-cast tree is computed from a plurality of said set of one or more coordinate labels.

22. The network of claim 21 where data is routed to a plurality of said plurality of Nodes according to said multi-cast tree.

23. The network of claim 1 where said network is a ATM network.

24. The network of claim 1 where said network is a packet-based network.

25. The network of claim 1 where said set of one or more coordinate labels does not disclose information relating to a physical structure of said network.

26. The network of claim 1 where said set of one or more coordinate labels is further comprised of coordinate labels from a first virtual network, and coordinate labels from at least one second virtual network.

28. The method of claim 27 wherein each coordinate label representing a path comprises, in series, identifiers for Links and Nodes comprising said path.

29. The method of claim 27 wherein each coordinate label representing a path is periodically updated to reflect changes in said path.

30. The method of claim 27 wherein said method comprises:

routing data from said source Node to said destination Node via said path between said source Node and said destination Node.

31. The method of claim 30 wherein said data is routed to a plurality of destination Nodes.

32. The method of claim 30 wherein said destination node is located on a second network.

33. The method of claim 32 wherein said data is routed through at least one third network in order to reach said destination node.

34. The method of claim 27 where said coordinate labels do not disclose information relating to a physical structure of said network.

35. The method of claim 27 where said coordinate labels do not disclose information relating to a physical structure of said network.

36. The method of claim 27 where said set of one or more coordinate labels is further comprised of coordinate labels from a first virtual network, and coordinate labels from at least one second virtual network.

37. The method of claim 27 wherein said path is determined from at least one coordinate label from said network and at least one coordinate label from at least one second network.

39. The Node of claim 38 wherein each coordinate label representing a path comprises, in series, addresses for Links and Nodes comprising said path.

40. The Node of claim 38 wherein each coordinate label representing a path is periodically updated to reflect a change in said path.

41. The Node of claim 38 wherein:

said Node routes data to a destination Node via a path determined by combining one of said labels of said Node and a label of said destination Node.

42. The Node of claim 41 wherein said packet is routed to a plurality of destination Nodes.

43. The Node of claim 38 where said coordinate labels do not disclose information relating to a physical structure of said network.

44. The Node of claim 38 where said set of one or more coordinate labels is further comprised of coordinate labels from a first virtual network, and coordinate labels from at least one second virtual network.

27. A method for determining a path from a source Node to a destination Node in a network comprising a plurality of Nodes interconnected by Links, said Nodes including a first Node, and a plurality of second Nodes, said second Nodes including said source Node and destination Node, said method comprising the steps of:

(a) assigning to each of said second Nodes, including said source Node and said destination Node, one or more coordinate labels, each coordinate label assigned to a second Node representing a path through said network from said second Node to said first Node; and

(b) determining a path from said source Node to said destination Node by combining one coordinate label of said source Node and one coordinate label of said destination Node.

38. A Node for use in a network, said network comprising a plurality of Nodes connected by Links, wherein:

said Node for use in said network has one or more coordinate labels assigned thereto, each label representing a path from said Node to a particular other Node of said network, each of said labels being unique to said Node.