# US 8,787,208 B2 · Method and apparatus for allocating backbone VLAN identifiers > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,787,208 B2 - Document ID: US8787208B2 - Status: Granted - Kind: B2 - Application number: 13/245,867 - Filed: 2011-09-27 - Published: 2013-01-31 - Granted: 2014-07-22 - Earliest claimed: 2011-09-27 - Assignees: Indian Institute of Technology Bombay - Applicants: Deval A. Bhamare; Ashwin Gumaste - Inventors: Deval A. Bhamare; Ashwin Gumaste - Web page: https://patentgrep.com/patent/US8787208B2 ## CPC - H04L 12/28: characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] (wireless communication networks H04W {; arrangements for dividing the transmission path H04W40/00}) - H04L 12/4658: {wherein a VLAN tag represents a service provider backbone VLAN, e.g. B-Tag, S-Tag} - H04L 45/128: for finding disjoint paths - H04L 12/56: {Packet switching systems} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Methods and apparatuses for allocating backbone virtual local area network identifiers (BVIDs) to connection requests in a provider backbone bridging-traffic engineering (PBB-TE) network are described. During operation, a system (e.g., a network management system) can receive a set of connection requests for a set of connections that are desired to be set up in the PBB-TE network. Next, the system can allocate a BVID to each connection request in the set of connection requests so that, once the set of connection requests are set up in the PBB-TE network, conflicting connections in the PBB-TE network have different BVIDs. ## Claims ### Claim 1 A method for allocating backbone virtual local area network identifiers (BVIDs) to connection requests in a provider backbone bridging-traffic engineering (PBB-TE) network, the method comprising: receiving a set of connection requests for a set of connections that are desired to be set up in the PBB-TE network; and allocating a BVID to each connection request in the set of connection requests so that, once the set of connection requests are set up in the PBB-TE network, conflicting connections in the PBB-TE network have different BVIDs, wherein said allocating comprises: determining a path from a source node to a destination node associated with the connection request; selecting a BVID; determining a first sub-network of the PBB-TE network such that each link in the first sub-network carries one or more connections that are associated with the selected BVID; determining a second sub-network by performing a union of the path and the first sub-network; and in response to determining that the second sub-network does not contain a cycle, allocating the selected BVID to the connection request. ### Claim 2 (depends on 1) The method of claim 1, wherein a first connection conflicts with a second connection if the first and second connections have the same destination node, and the paths associated with the first and second connections have at least one common intermediate node such that portions of the paths from the common intermediate node to the destination node do not have the same set of nodes. ### Claim 3 (depends on 1) The method of claim 1, wherein the path is a shortest path from the source node to the destination node. ### Claim 4 (depends on 1) The method of claim 1, wherein selecting the BVID includes preferentially selecting BVIDs that have been allocated to existing connections in the PBB-TE network. ### Claim 5 A non-transitory tangible computer-readable storage medium encoded with a computer program that, when executed by a computer, causes the computer to perform a method for allocating backbone virtual local area network identifiers (BVIDs) to connection requests in a provider backbone bridging-traffic engineering (PBB-TE) network, the method comprising: receiving a set of connection requests for a set of connections that are desired to be set up in the PBB-TE network; and allocating a BVID to each connection request in the set of connection requests so that, once the set of connection requests are set up in the PBB-TE network, conflicting connections in the PBB-TE network have different BVIDs, wherein said allocating comprises: determining a path from a source node to a destination node associated with the connection request; selecting a BVID; determining a first sub-network of the PBB-TE network such that each link in the first sub-network carries one or more connections that are associated with the selected BVID; determining a second sub-network by performing a union of the path and the first sub-network; and in response to determining that the second sub-network does not contain a cycle, allocating the selected BVID to the connection request. ### Claim 6 (depends on 5) The non-transitory tangible computer-readable storage medium of claim 5, wherein a first connection conflicts with a second connection if the first and second connections have the same destination node, and the paths associated with the first and second connections have at least one common intermediate node such that portions of the paths from the common intermediate node to the destination node do not have the same set of nodes. ### Claim 7 (depends on 5) The non-transitory tangible computer-readable storage medium of claim 5, wherein the path is a shortest path from the source node to the destination node. ### Claim 8 (depends on 5) The non-transitory tangible computer-readable storage medium of claim 5, wherein selecting the BVID includes preferentially selecting BVIDs that have been allocated to existing connections in the PBB-TE network. ### Claim 9 An apparatus, comprising: a processor; and a non-transitory processor-readable storage medium storing instructions that are capable of being executed by the processor, the instructions comprising: instructions for receiving a set of connection requests for a set of connections that are desired to be set up in the PBB-TE network; and instructions for allocating a BVID to each connection request in the set of connection requests so that, once the set of connection requests are set up in the PBB-TE network, conflicting connections in the PBB-TE network have different BVIDs, wherein said allocating comprises: determining a path from a source node to a destination node associated with the connection request; selecting a BVID; determining a first sub-network of the PBB-TE network such that each link in the first sub-network carries one or more connections that are associated with the selected BVID; determining a second sub-network by performing a union of the path and the first sub-network; and in response to determining that the second sub-network does not contain a cycle, allocating the selected BVID to the connection request. ### Claim 10 (depends on 9) The apparatus of claim 9, wherein a first connection conflicts with a second connection if the first and second connections have the same destination node, and the paths associated with the first and second connections have at least one common intermediate node such that portions of the paths from the common intermediate node to the destination node do not have the same set of nodes. ### Claim 11 (depends on 9) The apparatus of claim 9, wherein the path is a shortest path from the source node to the destination node. ### Claim 12 (depends on 9) The apparatus of claim 9, wherein instructions for selecting the BVID includes instructions for preferentially selecting BVIDs that have been allocated to existing connections in the PBB-TE network.