1. A method comprising:
by a network device, calculating a plurality of maximally redundant trees from an ingress network device to a plurality of egress network devices based on a network graph, in which each of the plurality of maximally redundant trees comprises a spanning tree to the plurality of egress network devices rooted at the ingress network device, wherein each of the maximally redundant trees is calculated to comprise a point to multipoint (P2MP) path from the ingress network device to the plurality of egress network devices that is as disjoint as possible from a respective P2MP path from the ingress network device to the plurality of egress network devices for each other one of the plurality of maximally redundant trees, and wherein the maximally redundant trees are calculated such that each link along each of the plurality of maximally redundant trees satisfies a specified traffic-engineering constraint;
in response to determining, by the network device, that the plurality of maximally redundant trees include at least one node whose removal partitions a network represented by the network graph:
modifying, by the network device, the specified traffic-engineering constraint to have a less restrictive value;
modifying the network graph to add links to the network graph that satisfy the modified traffic-engineering constraint to obtain a modified network graph; and
re-calculating, by the network device, at least a portion of the plurality of maximally redundant trees based on the modified network graph to obtain a plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned; and
with the ingress network device, establishing a plurality of P2MP label switched paths (LSPs) from the ingress network device to the plurality of egress network devices along each of the plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned, wherein each of the P2MP LSPs corresponds to a different one of the plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned.
2. The method of claim 1, further comprising:
concurrently sending multicast traffic from a multicast source device to a plurality of destination devices on each P2MP LSP of the plurality of P2MP LSPs.
3. The method of claim 1, wherein the traffic-engineering constraint comprises one or more of an amount of bandwidth, link color, priority, and class type.
4. The method of claim 1, wherein the plurality of maximally redundant trees comprises a pair of spanning trees that share a least number of links possible and share a least number of nodes possible.
5. The method of claim 4, wherein the plurality of maximally redundant trees comprises a pair of spanning trees that are link disjoint and node disjoint.
6. The method of claim 1, wherein a maximally redundant tree of the plurality of maximally redundant trees comprises a plurality of branches, and wherein establishing the plurality of P2MP LSPs along the maximally redundant trees comprises establishing the plurality of P2MP LSPs along a subset of the plurality of branches of the maximally redundant tree.
7. The method of claim 1, further comprising, by the ingress network device, periodically re-calculating the plurality of maximally redundant trees to determine whether a more optimal plurality of maximally redundant trees exists on the network graph.
8. The method of claim 1, further comprising:
detecting a change to a network topology yielding a modified network graph; and
with the ingress network device, automatically re-calculating the plurality of maximally redundant trees based on the modified network graph.
9. The method of claim 1, further comprising:
prior to calculating the plurality of maximally redundant trees on the network graph, modifying the network graph to remove links from the network graph that do not satisfy the traffic-engineering constraint to obtain a modified network graph, wherein calculating the plurality of maximally redundant trees based on the network graph comprises calculating the plurality of maximally redundant trees based on the modified network graph.
10. The method of claim 1, further comprising using a resource reservation protocol to establish the P2MP LSPs.
11. The method of claim 10, wherein the resource reservation protocol comprises the Resource Reservation Protocol with Traffic Engineering extensions (RSVP-TE).
12. The method of claim 1, wherein establishing the plurality of P2MP LSPs comprises:
sending resource reservation requests to label-switching routers (LSRs) along each of the maximally redundant trees, wherein the resource reservation requests each include an identifier associating the requests with the respective maximally redundant tree; and
receiving resource reservation messages in response to the resource reservation requests that specify reserved resources and labels allocated to the respective one of the plurality of P2MP LSPs to be used for forwarding network traffic to corresponding next hops, wherein the resource reservation messages each include an identifier associating the messages with the respective maximally redundant tree.
13. The method of claim 1, wherein the traffic engineering constraint comprises one of:
a maximum link bandwidth for each of the one or more network links, wherein the maximum link bandwidth defines a maximum amount of bandwidth capacity associated with a network link;
a residual bandwidth for each of the one or more network links, wherein the residual bandwidth defines an amount of bandwidth capacity for a network link that is a maximum link bandwidth less a bandwidth of the network link reserved by operation of a resource reservation protocol; and
an available bandwidth for each of the one or more network links, wherein the available bandwidth defines an amount of bandwidth capacity for the network link that is neither reserved by operation of a resource reservation protocol nor currently being used by the first router to forward traffic using unreserved resources.
14. The method of claim 1, wherein the ingress network device comprises the network device that computes the plurality of maximally redundant trees.
15. A network device comprising:
a processor;
a constrained maximally redundant tree module configured for execution by the processor to calculate a plurality of maximally redundant trees from the network device to a plurality of egress network devices based on a network graph, in which each of the plurality of maximally redundant trees comprises a spanning tree to the plurality of egress network devices rooted at the network device, wherein each of the maximally redundant trees is calculated to comprise a point to multipoint (P2MP) path from the network device to the plurality of egress network devices that is as disjoint as possible from a respective P2MP path from the network device to the plurality of egress network devices for each other one of the plurality of maximally redundant trees, and wherein the maximally redundant trees are calculated such that each link along each of the plurality of maximally redundant trees satisfies a specified traffic-engineering constraint,
wherein the constrained maximally redundant tree module is configured to, in response to determining that the plurality of maximally redundant trees includes at least one node whose removal partitions a network represented by the network graph:
modify the specified traffic-engineering constraint to have a less restrictive value;
modify the network graph to add links to the network graph that satisfy the modified traffic-engineering constraint to obtain a modified network graph; and
re-calculate at least a portion of the plurality of maximally redundant trees based on the modified network graph to obtain a plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned; and
a resource reservation protocol module configured for execution by the processor to establish a plurality of P2MP label switched paths (LSPs) from the network device as an ingress network device to the plurality of egress network devices along each of the plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned, wherein each of the P2MP LSPs corresponds to a different one of the plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned.
16. The network device of claim 15, further comprising a forwarding component that concurrently sends multicast traffic from a multicast source device to a plurality of destination devices on each P2MP LSP of the plurality of P2MP LSPs.
17. The network device of claim 15, wherein the plurality of maximally redundant trees comprises a pair of spanning trees that share a least number of links possible and share a least number of nodes possible.
18. The network device of claim 15, wherein the constrained maximally redundant tree module automatically recalculates the plurality of maximally redundant trees based on the modified network graph upon the network device detecting a change to a network topology yielding a modified network graph.
19. A non-transitory computer-readable storage medium comprising instructions for causing a programmable processor to:
calculate a plurality of maximally redundant trees from an ingress network device to a plurality of egress network devices based on a network graph, in which each of the plurality of maximally redundant trees comprises a spanning tree to the plurality of egress network devices rooted at the ingress network device, wherein each of the maximally redundant trees is calculated to comprise a point to multipoint (P2MP) path from the ingress network device to the plurality of egress network devices that is as disjoint as possible from a respective P2MP path from the ingress network device to the plurality of egress network devices for each other one of the plurality of maximally redundant trees, and wherein the maximally redundant trees are calculated such that each link along each of the plurality of maximally redundant trees satisfies a specified traffic-engineering constraint;
in response to determining that the plurality of maximally redundant trees includes at least one node whose removal partitions a network represented by the network graph:
modify the specified traffic-engineering constraint to have a less restrictive value;
modify the network graph to add links to the network graph that satisfy the modified traffic-engineering constraint to obtain a modified network graph; and
re-calculate at least a portion of the plurality of maximally redundant trees based on the modified network graph to obtain a plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned; and
establish a plurality of P2MP label switched paths (LSPs) from the ingress network device to the plurality of egress network devices along each of the plurality of maximally redundant trees, wherein each of the P2MP LSPs corresponds to a different one of the plurality of maximally redundant trees.
20. The method of claim 1, further comprising repeatedly modifying the specified traffic-engineering constraint, modifying the network graph, and re-calculating at least a portion of the plurality of maximally redundant trees until obtaining the plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned.
21. The method of claim 1, wherein modifying the specified traffic-engineering constraint to have the less restrictive value comprises modifying the specified traffic-engineering constraint for only a certain part of the maximally redundant trees that includes the at least one node whose removal partitions the network.
The claims below are in addition to those above.
All refrences to claim(s) which appear below refer to the numbering after this setence.
1. A system for locating access to wireless resources, comprising:
a portable electronic device including a short range radio frequency (RF) transceiver,
a database program running an the portable electronic device, the database program configured to store a history of wireless station information and available resource information,
the wireless station informatiog being representative of wireless stations coming in communications with the short range RF transceiver as the portable electronic device is being moved through an environment, and
the available resource information being correlated with the wireless station information and the available resource information being distinct from and representative of the resources available through the wireless stations.
2. The system of claim 1, wherein the portable electronic device is a handheld computer.
3. The system of claim 1, wherein the short range RF transceiver is a Bluetooth transceiver.
4. The system of claim 1, wherein the short range RF transceiver is a IEEE 802.11 transceiver.
5. The system of claim 1, wherein the wireless station information includes the type of wireless transceiver being used by the wireless station.
6. The system of claim 1, wherein the wireless station information includes an address of the wireless station.
7. The system of claim 1, wherein the wireless station information includes information representative of the location of the wireless station.
8. The system of claim 1, wherein the wireless station information includes a timestamp representative of a time that the portable device was in range of the wireless station.
9. The system of claim 1, wherein the resource information includes a resource identifier.
10. The system of claim 1, wherein the resource information includes a resource description.
11. The system of claim 1, wherein the resource information includes keywords relating to the resource.
12. The system of claim 1, wherein the resource information includes attributes for an object oriented data description.
13. The system of claim 1, wherein the resource information includes a listing of associated wireless stations.
14. A method of locating access to resources in an environment, comprising:
roaming within an environment with a portable electronic device having a short range radio frequency (RF) transceiver;
scanning for wireless enabled devices within range of the RF transceiver of the portable device;
storing wireless station information relating to the wireless enabled devices in a database;
storing available resource information distinct from and relating to the resources coupled to and available trough the wireless station in the database; and
accessing, on the portable electronic device, the database including the wireless station information and the available resource information.
15. The method of claim 14, further comprising:
querying the database for a specified resource.
16. The method of claim 15, further comprising:
performing a keyword search of the database.
17. The method of claim 15, further comprising:
providing location information relating to accessing the specified resource.
18. The method of claim 17, wherein the location information includes a set of directions.
19. The method of claim 17, wherein the location information includes a map.