Problem 10 - An Introduction to Computer Networks

Question

(This exercise assumes some familiarity with Distance-Vector routing as in 9 Routing-Update Algorithms.) a. Suppose switches are able to identify the non-switch hosts that are directly connected, that is, reachable without passing through another switch. Explain how the algorithm of \(9.1\) Distance-Vector Routing-Update Algorithm could be used to construct optimal Ethernet forwarding tables even if loops were present in the network topology. b. Suppose switches are allowed to "mark" packets; all packets are initially unmarked. Give a mechanism that allows switches to detect which non-switch hosts are directly connected. c. Explain why Ethernet broadcast (and multicast) would still be a problem.

Step-by-Step Solution

Answer

Distance-Vector routing lends itself well to constructing Ethernet forwarding tables by keeping infinite distance values for loop paths. Marking packets with a specific identifier or flag helps switches in recognizing directly connected hosts. Ethernet broadcast, however, still poses a problem and leads to instances like broadcast storms due to the necessity of forwarding along all interfaces. Establishing broadcast domains can help control and limit these broadcasts.

Step 1: Distance-Vector Routing and Ethernet Forwarding Tables

A Distance-Vector Routing protocol implies that each router only knows the shortest distance to its immediate neighbors and how to get to them. To construct Ethernet forwarding tables, a router sends its distance vector to all its immediate neighbors when initialized or after a change in the network topology. In case of looped networks, a router keeps its distance figure as infinity whenever it receives an update from a router through a path that it itself constitutes a part of. This allows the system to avoid count-to-infinity problems.

Step 2: Marking Packets and Identifying directly connected hosts

In a switch segment, whenever a switch receives a frame from a directly connected host, it saves the Source MAC Address and Input Interface in the switch table. Additionally, to figure out the directly connected hosts, the switches can mark packets with a specific flag or identifier, and this can be done at the time of their entry into the network. All packets are initially unmarked and as they pass through the first switch, they get marked. Only those hosts capable of marking the packets (indicating they function as switches) are considered as indirect links.

Step 3: Addressing Ethernet Broadcast and Multicast

Ethernet broadcast and multicast pose a problem in these scenarios as they can lead to broadcast storms. These broadcasts are unavoidable and Switches don’t know where all hosts are located, and as such, must forward on all interfaces. As a result, there could be instances of packet duplications across different paths. The key here is to limit the scope of such broadcasts - which is typically done by establishing broadcast domains. A VLAN is an example of such a domain where broadcast traffic is kept within the confines of that VLAN.

Key Concepts

Ethernet Forwarding Tables

Ethernet forwarding tables are essential components of network switches, responsible for determining the correct path to forward network packets. These tables map Ethernet addresses to the physical ports on a switch. Every time a switch receives a frame, it checks its forwarding table to decide which port should receive the traffic. To construct these tables efficiently, especially in networks that may contain loops, the Distance-Vector Routing algorithm can be employed. This algorithm updates each switch with information about the shortest path to all reachable Ethernet addresses, based on distance vectors shared repeatedly amongst the switches. In the event of a loop, the algorithm optimizes routing by declaring a distance to an address as 'infinity,' thus preventing route errors like the 'count-to-infinity' problem.

Broadcast Storm

A broadcast storm occurs when excessive broadcast traffic floods a network, potentially causing a significant slowdown or complete failure. It happens because Ethernet is a broadcast medium by default, meaning any broadcast frame sent by a host is forwarded by switches to all ports within the network segment. This problem is exacerbated when there are loops in the network since the broadcast frames keep circulating through multiple paths, amplifying the network's load. One effective way to manage broadcast storms is by segmenting networks into smaller broadcast domains, which limits the scope of broadcast frames. Implementing Spanning Tree Protocol (STP) can also help, as it creates a loop-free logical topology for the network.

VLAN

Virtual Local Area Networks (VLANs) are used to segment network traffic logically. They create numerous distinct broadcast domains within the same physical network infrastructure, which helps control broadcasting issues. By isolating network segments, VLANs enhance security and manageability. They ensure that broadcast frames sent within one VLAN remain confined to that VLAN, reducing the risk of broadcast storms and improving overall network performance. Configuring VLANs involves assigning specific switch ports to different VLANs. Devices connected to these ports can communicate with each other as if they were on the same physical segment, regardless of their actual physical location.

Network Topology

Network topology refers to the layout or structure of a network, encompassing both physical connectivity and logical arrangement. It dictates how devices communicate with each other and plays a critical role in network performance. Common forms of topology include bus, star, ring, mesh, and hybrid configurations. Each topology has its own benefits and drawbacks, such as star topology's ease of troubleshooting and mesh topology's high redundancy. Complex topologies can sometimes introduce loops, which are problematic for broadcasting traffic. Hence, routing algorithms like Distance-Vector or protocols like STP are implemented to maintain efficient data transmission without traffic loops.

Multicast

Multicast is a communication method where data is sent from one or multiple sources to many destinations simultaneously. Unlike broadcast, which sends data to all network nodes, multicast selectively targets a group of hosts, thus conserving bandwidth. In an Ethernet environment, however, multicast can still contribute to network flooding, comparable to broadcast storms, if not managed properly. To mitigate its effect on network performance, multicast traffic is often controlled using protocols such as Internet Group Management Protocol (IGMP) in IPv4 or Multicast Listener Discovery (MLD) in IPv6. Multicast allows efficient usage of network resources by making data distribution to multiple recipients less resource-intensive than multiple, unicast streams, ultimately optimizing network traffic handling.