Question

In the source routing example of Section 3.1.3, the address received by B is not reversible and doesn't help B know how to reach A. Propose a modification to the delivery mechanism that does allow for reversibility. Your mechanism should not require giving all switches globally unique names.

Short answer

Record the path of switches in sequence as the packet travels, then reverse this sequence to route back without needing globally unique switch names.

Step-by-step solution

Understand the Problem

Consider a source routing scenario where an address received by a node (B) is not reversible, complicating the process of determining a return route to the source node (A). The objective is to modify the delivery mechanism to enable route reversibility without requiring globally unique switch names.

Analyze the Addressing Mechanism

In the current mechanism, the address packet received by node B provides the path to B, but lacks the information to reverse and send back to A. This implies that some additional information is needed for reversibility.

Introduce Path Recording

One way to make the path reversible is to have each packet record the sequence of switches it passes through. This can be done by appending each switch's local identifier to the packet as it travels from A to B. These local identifiers are only unique within the context of the path, not globally.

Reverse the Path for Return

When node B needs to send a packet back to A, it can use the recorded sequence of switches in reverse order. This way, it effectively retraces the route taken by the packet from A, without needing globally unique identifiers.

Ensure Local Context

Ensure that each switch only appends its identifier when forwarding packets and remove it when routing back. This keeps the address context local and straightforward.

Key concepts

Address Reversibility

Address reversibility is about making sure that a packet sent from a source node (like A) to a destination node (like B) can find its way back using the same route. In source routing, the information in the packet reaching B is usually not enough for B to find a way back to A. Reversibility means allowing B to use the same path A used but in reverse.
To achieve this, the solution is to modify the address recording method so that the path information is captured and can be reused. The address packet can include a record of the route it traveled through. By doing this, B can just reverse this recorded information to find the way back to A.
In summary, address reversibility is about dynamically recording the path as a packet moves from node to node. This method ensures every node can be reached again without requiring that each switch has a globally unique name. This makes the entire process efficient and scalable in large networks.

Path Recording

Path recording is a practical solution that ensures address reversibility in source routing setups. As the packet travels from the source node A to the destination node B, it logs each switch it passes through. Each switch has a local identifier, which is added to the packet.
This local identifier is unique only within that specific path context, meaning it doesn't need to be globally unique. This method simplifies the routing process and minimizes the need for complex naming systems. When B wants to send a packet back to A, it can reverse this recorded path.
This path recording enables each switch to store relevant routing information without overwhelming the network with data. By maintaining simplicity and context-specific addresses, this solution effectively supports seamless routing even in extensive and complex networks.

Local Identifiers

Local identifiers are crucial in the modified addressing scheme for source routing. These identifiers are unique only within the specific route but don't need to be unique globally. It significantly reduces the complexity and overhead compared to using globally unique names for each switch.
As a packet travels from A to B, each switch appends its local identifier to the packet. When B needs to send information back to A, it can use the reverse of these local identifiers to trace back the path effectively.
This approach keeps the addressing and routing process clean and manageable. It also makes the network more adaptable to changes, as new paths or nodes can be integrated without reworking existing global identifiers. This simplifies the routing algorithm and ensures efficient operation in diverse and dynamic network environments.