Question

Consider a virtual-circuit network. Suppose the VC number is an 8-bit field. a. What is the maximum number of virtual circuits that can be carried over a link? b. Suppose a central node determines paths and VC numbers at connection setup. Suppose the same VC number is used on each link along the VC's path. Describe how the central node might determine the VC number at connection setup. Is it possible that there are fewer VCs in progress than the maximum as determined in part (a) yet there is no common free VC number? c. Suppose that different VC numbers are permitted in each link along a VC's path. During connection setup, after an end-to-end path is determined, describe how the links can choose their VC numbers and configure their forwarding tables in a decentralized manner, without reliance on a central node.

Short answer

a. 256 virtual circuits. b. Yes, due to uncoordinated VC allocation. c. Each link independently chooses a free VC number from its own table.

Step-by-step solution

Calculate Maximum Number of Virtual Circuits

The VC number is an 8-bit field, meaning it can represent any number from 0 to 255, inclusive. This results in a total of \( 2^8 = 256 \) possible VC numbers. Thus, the maximum number of virtual circuits that can be carried over a link is 256.

Understanding Central Node VC Number Allocation

In a central node-controlled setup, the paths and corresponding VC numbers are determined at the outset. The central node ensures that each link in the virtual circuit uses the same VC number. The central node can maintain a table of active VC numbers for each link and assign the lowest available VC number for any new connection. If the system is not fully utilizing all possible VC numbers (the 256 theoretical maximum), it is still possible to run out of common free VC numbers if VC numbers were not consistently reclaimed after use, since each link along the path might have different sets of already used VC numbers.

Decentralized VC Number Allocation

In a decentralized system, upon determining an end-to-end path, each intermediate link independently selects an available VC number for its segment. Typically, each link maintains its own table of currently active VC numbers and selects any free number for new connections. For consistent routing, this number is added to the link's forwarding table with information on the incoming and outgoing interfaces. This setup allows flexibility since each link has control over VC numbers, potentially accommodating more circuits than in the centralized scheme.

Key concepts

Centralized VC Number Allocation

In a virtual circuit network, centralized VC number allocation involves a central node determining and managing the virtual circuit (VC) numbers. When a connection is initiated, the central node calculates a path for the connection and assigns a single VC number to be used across all links along this path.

The process works as follows:

• When a connection request comes in, the central node finds a suitable route through the network.
• The node checks its database of currently active VC numbers for each link.
• It assigns the lowest available VC number that is free across all links in the circuit's path.

However, this method may face challenges. Even when the network is not using all 256 potential VC numbers (as determined by an 8-bit field), inconsistencies in reclaiming used VC numbers can lead to scenarios where no single VC number is available on every link, despite there being room for more circuits overall. This inefficiency requires careful management of VC resources to ensure maximum utilization.

Decentralized VC Number Allocation

In contrast to a centralized system, decentralized VC number allocation allows each network link to independently select its VC number when establishing a connection. This approach provides flexibility and can increase the total number of circuits accommodated by the network.

Here's how decentralized allocation typically works:

• Once an end-to-end path is determined, each link along the path independently assigns a free VC number.
• Each link maintains its own table of active VC numbers, ensuring it selects an unused number.
• After selection, the VC number is added to the link's forwarding table, which includes the information about the interfaces involved in the circuit.

This method does not rely on a single point of decision-making, reducing the potential bottlenecks associated with centralized systems. It also enables more dynamic and efficient use of available VC numbers, as each link adapts to its individual load and congestion level, potentially allowing more virtual circuits to be established.

Maximum Virtual Circuits

The maximum number of virtual circuits in a network depends on the size of the VC number field. For example, if we have an 8-bit field, this means the VC numbers can range from 0 to 255.

Mathematically, this is calculated as \(2^8\), which equals 256 possible VC numbers. Thus, each link in the network can theoretically support up to 256 simultaneous virtual circuits.

Achieving this theoretical maximum requires careful management of VC resources, especially in centralized systems where a common VC number must be available across all links in a path. In decentralized systems, the maximum is potentially higher due to the independent management of VC numbers by each link, allowing for greater flexibility and adaptability across the network.