Problem 45 - Computer Networking: A Top-Down Approach

Question

Consider the two basic approaches identified for achieving broadcast, unicast emulation and network-layer (i.e., router-assisted) broadcast, and suppose spanning-tree broadcast is used to achive network-layer broadcast. Consider a single sender and 32 receivers. Suppose the sender is connected to the receivers by a binary tree of routers. What is the cost of sending a broadcast packet, in the cases of unicast emulation and network-layer broadcast, for this topology? Here, each time a packet (or copy of a packet) is sent over a single link, it incurs a unit of cost. What topology for interconnecting the sender, receivers, and routers will bring the cost of unicast emulation and true network-layer broadcast as far apart as possible? You can choose as many routers as you'd like.

Step-by-Step Solution

Answer

Unicast emulation costs 32 packet transmissions; network-layer broadcast costs 31. A balanced binary tree maximizes their cost difference.

Step 1: Understand the Problem

We are asked to calculate the cost of broadcasting a packet from a sender to 32 receivers using two different methods: unicast emulation and network-layer broadcast (specifically via spanning-tree broadcast). We need to assess the cost in terms of the number of packet transmissions. We'll also explore the topology that maximizes the cost difference between these two approaches.

Step 2: Unicast Emulation Cost Calculation

In unicast emulation, the sender sends individual unicast packets to each of the 32 receivers. Therefore, the cost is simply 32 packet transmissions since each packet goes directly from the sender to a receiver along a single path without sharing across any intermediary nodes.

Step 3: Network-Layer Broadcast Cost Calculation

For network-layer broadcast using spanning-tree broadcast on a binary tree topology, the sender sends one packet down each branch of its tree. At each split in the binary tree, a single packet duplicates and goes down both branches. For 32 receivers, the binary tree has 31 links to reach all the receivers (in a fully balanced tree, there are 31 routers forming a path from the root to the 32 leaf nodes). Therefore, 31 transmissions are required.

Step 4: Determine Ideal Topology to Maximize Cost Difference

To maximize the cost difference between unicast emulation and network-layer broadcast, we need to ensure that the broadcast spans minimal links and that the unicast must travel maximum separate paths. In a perfectly balanced binary tree, the spanning-tree broadcast achieves minimal cost, while unicast emulation must still send packets individually, retaining the high cost. Hence, a perfectly balanced binary tree (exactly like the one described) optimizes this difference.

Key Concepts

Unicast Emulation

When talking about unicast emulation, we are referring to the method of sending a unique copy of a packet to each receiver. The packet follows a single path to one specific receiver, rather than being distributed across a network.
In the context of our exercise with 32 receivers, this means that 32 separate paths are created from the sender. Each path carries a single packet independently to a receiver.

• Each packet incurs a unit cost per transmission.
• No sharing of paths occurs, meaning that each receiver gets one unique transmission.
• Total cost is directly proportional to the number of receivers.

This method is simple to conceptualize, but it can be inefficient in scenarios where multiple receivers are present. Unicast emulation may incur greater transmission costs due to its one-to-one communication nature.

Spanning-Tree

A spanning tree is a subgraph of a network that connects all the nodes with the minimal number of links, ensuring there are no cycles. In networking, it's often used to avoid redundant paths and loops.
When used for broadcasting, a spanning-tree approach sends a single packet from the root to all the nodes in a network.
For our scenario:

• Only 31 transmissions are required to reach all 32 receivers in a perfectly balanced binary tree.
• The spanning tree effectively minimizes the number of necessary packet duplications.
• This approach ensures that the network is efficiently traversed with minimal redundancy.

The main advantage of using a spanning tree broadcast method is the potential for significant cost savings compared to unicast emulation, especially as the number of receivers grows.

Binary Tree Topology

In a binary tree topology, each parent node is connected to exactly two child nodes. This is a very efficient structure for distributing packets across a network.

• Each level of the tree doubles the number of nodes, efficiently expanding the network coverage.
• For the given problem, the binary tree has 31 routers to reach 32 receivers, indicating a fully balanced tree.
• This symmetry allows for evenly distributed packet flows.

The binary tree is particularly well-suited for the spanning-tree broadcast, as it mimics the optimal structure needed to minimize transmissions, with each packet automatically splitting down two paths as it travels from node to node.

Packet Transmission Cost

Packet transmission cost refers to the expenses associated with sending packets across a network. In our exercise, each packet incurs a 'unit cost' every time it is sent over a single network link.

• For unicast emulation, the cost is straightforward: one transmission per receiver.
• In a network-layer broadcast, cost is minimized by efficiently using shared paths.
• In a balanced binary tree setup, spanning-tree broadcasting reduces the cost to just 31 transmissions for 32 receivers.

Understanding packet transmission costs is crucial for implementing efficient network strategies. The goal is to minimize these costs while ensuring reliable communication between the sender and all its intended receivers.