Calculation, representation, and maintenance of sharing information in mesh networks

1. A method comprising:

representing, in a network data structure, information associated with a mesh network having a plurality of nodes interconnected by a plurality of links, wherein the network data structure comprises, for each link in the network and each node and each other link in the network, a representation of a minimum amount of protection bandwidth required to be reserved on said each link to restore service upon failure of said each node or other link;

receiving a request for a new service in the network, wherein the new service is represented by a service data structure comprising an identification of each link and transit node in a primary path for the new service;

determining, using the network and service data structures, whether the new service requires additional protection bandwidth to be reserved on any link in the network; and

updating the network data structure if any additional protection bandwidth is determined to be required for the new service.

2. The invention of claim 1 , wherein the service data structure further comprises an identification of bandwidth associated with the new service.

3. The invention of claim 1 , wherein the network is a virtual-circuit mesh data network that transmits packetized data.

4. The invention of claim 1 , wherein the network data structure is distributed over the network such that at least one node in the network does not have all of the information in the network data structure.

5. The invention of claim 1 , wherein each of the nodes in the network has all of the information in the network data structure.

6. The invention of claim 1 , further comprising, in response to the new service request, determining a restoration path for the new service in the network using the network data structure.

7. The invention of claim 1 , wherein:

the network data structure is an array of vectors, wherein:

each vector in the array corresponds to a different link in the network;

each vector in the array has a plurality of entries corresponding to the nodes and links in the network;

for a first vector corresponding to a first link, each entry in the first vector corresponding to a node or other link identifies the minimum amount of protection bandwidth required to be reserved on the first link to restore service upon failure of the node or other link; and

the service data structure is a primary path vector having a plurality of entries corresponding to the nodes and links in the network, wherein:

each entry of the primary path vector identifies whether the corresponding node or link is part of the primary path for the new service.

8. The invention of claim 7 , wherein determining whether the new service requires any additional protection bandwidth to be reserved on a link A in the network comprises applying a vector addition operation between the primary path vector corresponding to the new service request and the vector of the array corresponding to the link A to form a result vector, and comparing the maximum value in the result vector with the bandwidth already reserved on the link A to determine whether any additional protection bandwidth is required for the new service.

9. The invention of claim 8 , wherein the additional protection bandwidth is required and is reserved if any result vector entry is greater than the bandwidth already reserved on the link.

10. The invention of claim 8 , wherein the vector addition operation is applied between the primary path vector and each vector in the array corresponding to each different link in a restoration path for the new service.

11. The invention of claim 1 , wherein the service data structure is primary path node-link vector V pnl .

12. The invention of claim 1 , wherein a compact version of the network data structure is used for transmitting sharing information in order to reduce the amount of data that needs to be transmitted in the network to disseminate the information about each link.

13. The invention of claim 12 , wherein transmission control protocol/Internet protocol (TCP/IP) connections are used for the dissemination.

14. The invention of claim 12 , wherein the compact representation is a node aggregate vector V na wherein each element of V na corresponds to a node in the network wherein the element's value is a function of the maximum of reservation bandwidths reserved on all links incident to the node.

15. The invention of claim 12 , wherein the dissemination is accomplished using a link-state routing protocol.

16. The invention of claim 1 , wherein an incremental version of the network data structure is used to reduce the amount of data that is transmitted in the network to disseminate the information.

17. A network manager for a mesh network having a plurality of nodes interconnected by a plurality of links, the network manager adapted to:

represent, in a network data structure, information associated with the mesh network, wherein the network data structure comprises, for each link in the network versus each node and each other link in the network, a representation of a minimum amount of protection bandwidth required to be reserved on said each link to restore service upon failure of said each node or other link;

receive a request for a new service in the network, wherein the new service is represented by a service data structure comprising an identification of each link and transit node in a primary path for the new service;

determine, using the network and service data structures, whether the new service requires additional protection bandwidth to be reserved on any link in the network; and

update the network data structure if any additional protection bandwidth is determined to be required for the new service.

18. The invention of claim 17 , wherein the network manager is distributed over the network.

19. The invention of claim 17 , wherein the network manager is located at a single node of the network.

20. The invention of claim 17 , wherein a compact version of the network data structure is used for transmitting sharing information in order to reduce the amount of data that needs to be transmitted in the network to disseminate the information about each link.

21. The invention of claim 1 , wherein:

the network data structure is an array of vectors, wherein:

each vector in the array corresponds to a different link in the network;

each vector in the array has a plurality of entries corresponding to all the nodes and links in the network;

for a first vector corresponding to a first link, each entry in the first vector corresponding to a node or other link identifies the minimum amount of protection bandwidth required to be reserved on the first link to restore service upon failure of the node or other link; and

the service data structure is a primary path vector having a plurality of entries corresponding to the nodes and links in the network, wherein each entry of the primary path vector identifies whether the corresponding node or link is part of the primary path for the new service.

22. The invention of claim 1 , wherein:

the network data structure is an array of vectors, wherein:

each vector in the array corresponds to a different link in the network;

each vector in the array has a plurality of entries corresponding to the nodes and links in the network;

for a first vector corresponding to a first link, each entry in the first vector corresponding to a node or other link identifies the minimum amount of protection bandwidth required to be reserved on the first link to restore service upon failure of the node or other link; and

the service data structure is a primary path vector having a plurality of entries corresponding to all the nodes and links in the network, wherein each entry of the primary path vector identifies whether the corresponding node or link is or is not part of the primary path for the new service.

23. The invention of claim 1 , wherein:

the network data structure is an array of vectors, wherein:

each vector in the array corresponds to a different link in the network;

each vector in the array has a plurality of entries corresponding to the nodes and links in the network;

for a first vector corresponding to a first link, each entry in the first vector corresponding to a node or other link identifies the minimum amount of protection bandwidth required to be reserved on the first link to restore service upon failure of the node or other link; and

the service data structure is a primary path vector having a plurality of entries corresponding to the nodes and links in the network, wherein each entry of the primary path vector identifies whether the corresponding node or link is part of the primary path for the new service, wherein at least one entry of the primary path vector identifies that the corresponding node or link is not part of the primary path for the new service.

24. The invention of claim 21 , wherein the service data structure is a primary path vector having a plurality of entries corresponding to all the nodes and links in the network, wherein each entry of the primary path vector identifies whether the corresponding node or link is or is not part of the primary path for the new service.