CSEN3141 -ADVANCED COMPUTER NETWORKS

UNIT - 2
Syllabus:
Internetworking (Part I): Switching and Bridging-Datagrams, Virtual Circuit Switching, Source
Routing, Bridges and LAN switches.
Basic Internetworking (IP)-What is an internetwork, service model, global addresses,
Datagram Forwarding in IP, Subnetting and classless addressing, address translation (ARP),
DHCP, ICMP, Virtual Networks and Tunnels.
2.1 Switching and Bridging
2.2 Basic Internetworking (IP)
2.1 Switching and Bridging
A switch is a device that connects different parts of a network together. It's like a traffic
controller for data, directing information from one device to another. Unlike shared media
networks where devices take turns sending information, a switch gives each device its own
dedicated connection. This allows for much faster and more efficient communication.

Figure 1: A switch provides a star topology

A switch adds the star topology (see the above Figure 1) to the point-to-point link, bus
(Ethernet), and ring topologies established in the last chapter.
A star topology has several attractive properties:
◼ Even though a switch has a fixed number of inputs and outputs, which limits
the number of hosts that can be connected to a single switch, large networks can
be built by interconnecting a number of switches
◼ We can connect switches to each other and to hosts using point-to-point links,
which typically means that we can build networks of large geographic scope
◼ Adding a new host to the network by connecting it to a switch does not
necessarily mean that the hosts already connected will get worse performance
from the network
Benefits of switches:
Improved performance: Each device has its own connection to the switch, so multiple devices
can transmit data at full speed without affecting each other.
Scalability: Switches can be easily connected together to create larger networks. This makes
them ideal for growing businesses or organizations that need to add more devices to their
network.
Reduced congestion: By separating devices onto dedicated connections, switches help to
reduce congestion on the network. This means that data can flow more freely and reliably.
How switches work:
Receiving data: A switch receives data packets from a device connected to one of its ports.
Reading the address: The switch reads the destination address in the header of the packet.
This address tells the switch where the packet needs to be sent.
Forwarding the data: The switch uses the destination address to determine the appropriate
output port and forwards the packet to that port.
Types of switching:
There are two main types of switching:
1. Datagram (Connectionless) Switching:
Imagine sending letters without any prior communication with the postman. Each letter (data
packet) has the recipient's address on it, and the postman (switch) reads the address and delivers
it directly. This is a faster approach, but there's no guarantee that the packets arrive in order or
at all.
Datagram switching is commonly used in networks where real-time order isn't crucial, like:
• Web browsing (downloading web pages piece by piece)
• Online gaming (tolerates slight delays)
• Video streaming (minor glitches might occur)
2. Virtual Circuit (Connection-oriented) Switching:
Think of reserving a specific route for your delivery truck beforehand. The switch sets up a
dedicated path for data packets to travel between the sender and receiver.
This ensures that all packets arrive in the correct order and without any loss. It's like having a
guaranteed delivery service.
Virtual circuit switching is preferred for applications where order and reliability are essential,
such as:
• Online banking transactions
• Video conferencing calls
• File transfers
 Table 1. Differences between Datagram and Virtual Circuit
Datagram Virtual Circuit
Feature
(Connectionless) (Connection-oriented)
Connection Setup No Yes (establishes a path before data
flow)
Order of Packets Not guaranteed Guaranteed (packets arrive in
order)
Reliability Lower (packets may be lost) Higher (guaranteed delivery)
Speed Faster Slower (due to connection setup)
Applications Web browsing, gaming, Online banking, video calls, file
streaming transfers

2.1.1 Datagrams
Datagram networks operate on a simple principle: every data packet carries its destination
address, allowing any switch to route it towards the final destination independently.
To decide how to forward a packet, a switch consults a forwarding table (sometimes called a
routing table).
Consider the example network illustrated in below Figure, in which the hosts have addresses
A, B, C, and so on. To decide how to forward a packet, a switch consults a forwarding table
(sometimes called a routing table), an example of which is depicted in Table 2. This particular
table shows the forwarding information that switch 2 needs to forward datagrams in the
example network.

Figure 2. Datagram forwarding: an example network.

 Table 2. Forwarding Table for Switch 2

Imagine a network of mailboxes:

• Each mailbox (host) has a unique address.
• Letters (data packets) contain the recipient's address on the envelope.
• Post offices (switches) have a directory (forwarding table) listing mailbox locations.
• When a letter arrives, the post office looks up the address and directs it to the correct
mailbox.
Key characteristics of datagram networks:
• Connectionless: Unlike making a phone call (connection-oriented), datagrams don't
require pre-established connections. Hosts can send packets anytime without setup.
• Unreliable Delivery: Networks don't guarantee packet delivery. They simply try their
best based on forwarding tables. It's like sending regular mail - there's a chance it might
get lost.
• Independent Routing: Each packet travels independently. Two packets from the same
source to the same destination might take different paths due to changing network
conditions.
• Robustness: Datagram networks are resilient to failures. If a switch or link fails, the
network can often reroute packets around the issue, as long as alternative paths exist
and forwarding tables are updated. This is a key reason why the internet is so robust!
Datagram vs. Connection-oriented Networks:
Think of datagrams as sending postcards - quick and convenient, but no guarantee of arrival.
Connection-oriented networks are like sending registered mail - slower with setup, but ensure
delivery and order.
Datagram networks are ideal for:
• Web browsing (downloading webpages in pieces)
• Online gaming (tolerates slight delays)
 • Video streaming (minor glitches might occur)
Datagram networks are not ideal for:
• Online banking transactions (needs guaranteed delivery)
• Video conferencing calls (requires order and reliability)
• File transfers (ensuring complete and ordered data is crucial)
2.1.2 Virtual Circuit Switching
A second technique for packet switching uses the concept of a virtual circuit (VC). This
connection-oriented model approach requires setting up a virtual connection from the source
host to the destination host before sending any data. Virtual Circuit (VC) networks offer a
reliable alternative to datagram networks for sending data packets.
Virtual Circuit Switching
◼ Widely used technique for packet switching
◼ Uses the concept of virtual circuit (VC)
◼ Also called a connection-oriented model
◼ First set up a virtual connection from the source host to the destination host and
then send the data
Example: host A again wants to send packets to host B.

Figure 3. An example of a virtual circuit network

Two-stage process
◼ Connection setup
◼ Data Transfer
Concept: Setting Up a Virtual Connection
Imagine a dedicated phone line reserved for your calls between two locations. Virtual circuits
work similarly in data networks. Before sending data, a connection (VC) is established between
the source and destination hosts. This involves a two-stage process:
1. Connection Setup:
o A message travels from the source host to the destination, specifying the
complete destination address.
 o Each switch along the path creates an entry in its Virtual Circuit Table (VC
Table). This entry contains:
▪ Virtual Circuit Identifier (VCI): A unique identifier for this
connection on that specific switch.
▪ Incoming Interface: The interface on which packets for this VC arrive.
▪ Outgoing Interface: The interface on which packets for this VC leave.
▪ Outgoing VCI: The VCI used for packets leaving this switch (might
differ from incoming VCI).
2. Data Transfer:
o Once the VC is established, data packets are sent from the source to the
destination.
o Each packet includes the VCI assigned by the source switch.
o Switches use the VCI in the packet header and the VC table to efficiently route
it towards the destination.
The semantics for one such entry is as follows:
If a packet arrives on the designated incoming interface and that packet contains the
designated VCI value in its header, then the packet should be sent out the specified
outgoing interface with the specified outgoing VCI value first having been placed in its
header.
Benefits of Virtual Circuits:
• Reliable Delivery: VCs ensure packets arrive in order and without loss, similar to a
registered mail service.
• Reduced Overhead: Data packets only carry the VCI (smaller than a full address),
reducing per-packet overhead compared to datagrams.
• Faster Lookups: Switches use VCIs for fast table lookups, improving efficiency
compared to searching by full addresses.
• Potential for QoS: VCs allow allocating resources like bandwidth for guaranteed
performance. (Not as common today)
Drawbacks of Virtual Circuits:
• Setup Delay: Establishing a VC before data transfer adds a round-trip delay compared
to datagrams.
• Switch Failure Impact: A switch or link failure disrupts the connection, requiring a
new VC setup.
• Limited Popularity: While successful in the past (X.25, Frame Relay, ATM),
connectionless datagram networks (like the internet) are more dominant today.
Whenever a new connection is created, we need to assign a new VCI for that connection on
each link that the connection will traverse. We also need to ensure that the chosen VCI on a
given link is not currently in use on that link by some existing connection.
Two broad classes of approach to establishing connection state
◼ Network dministrator will configure the state
◼ The virtual circuit is permanent (PVC)
◼ The network administrator can delete this
◼ Can be thought of as a long-lived or administratively configured VC
◼ A host can send messages into the network to cause the state to be established
◼ This is referred as signalling and the resulting virtual circuit is said to be
switched (SVC)
◼ A host may set up and delete such a VC dynamically without the
involvement of a network administrator
Let’s assume that a network administrator wants to manually create a new virtual connection
from host A to host B
◼ First the administrator identifies a path through the network from A to B

Figure 4. A packet is sent into a virtual circuit network.

• In the example network of above Figure, The administrator then picks a VCI value that
is currently unused on each link for the connection.
• For our example,
▪ Suppose the VCI value 5 is chosen for the link from host A to switch 1
▪ 11 is chosen for the link from switch 1 to switch 2
▪ So the switch 1 will have an entry in the VC table

Table 3. Virtual Circuit Table Entry for Switch 1

• Similarly, suppose
▪ VCI of 7 is chosen to identify this connection on the link from switch 2
to switch 3
▪ VCI of 4 is chosen for the link from switch 3 to host B
▪ Switches 2 and 3 are configured with the following VC table
Table 4. Virtual Circuit Table Entries for Switches 2 and 3

◼ For any packet that A wants to send to B, A puts the VCI value 5 in the header of the
packet and sends it to switch 1
◼ Switch 1 receives any such packet on interface 2, and it uses the combination of the
interface and the VCI in the packet header to find the appropriate VC table entry.
◼ The table entry on switch 1 tells the switch to forward the packet out of interface 1 and
to put the VCI value 11 in the header
◼ Packet will arrive at switch 2 on interface 3 bearing VCI 11
◼ Switch 2 looks up interface 3 and VCI 11 in its VC table and sends the packet on to
switch 3 after updating the VCI value appropriately
◼ This process continues until it arrives at host B with the VCI value of 4 in the packet
◼ To host B, this identifies the packet as having come from host A

Figure 5. A packet makes its way through a virtual circuit network.

◼ In real networks of reasonable size, the burden of configuring VC tables correctly in a
large number of switches would quickly become excessive
 ◼ Thus, some sort of signalling is almost always used, even when setting up
“permanent” VCs
◼ In case of PVCs, signalling is initiated by the network administrator
◼ SVCs are usually set up using signalling by one of the hosts
◼ How does the signalling work
◼ To start the signalling process, host A sends a setup message into the network
(i.e. to switch 1)
◼ The setup message contains (among other things) the complete
destination address of B.
◼ The setup message needs to get all the way to B to create the necessary
connection state in every switch along the way
◼ It is like sending a datagram to B where every switch knows which
output to send the setup message so that it eventually reaches B
◼ Assume that every switch knows the topology to figure out how to do
that
◼ When switch 1 receives the connection request, in addition to sending it on to
switch 2, it creates a new entry in its VC table for this new connection
◼ The entry is exactly the same shown in the previous table
◼ Switch 1 picks the value 5 for this connection
◼ When switch 2 receives the setup message, it performs the similar process and
it picks the value 11 as the incoming VCI
◼ Similarly switch 3 picks 7 as the value for its incoming VCI
◼ Each switch can pick any number it likes, as long as that number is not
currently in use for some other connection on that port of that switch
◼ Finally, the setup message arrives at host B.
◼ Assuming that B is healthy and willing to accept a connection from host A, it
allocates an incoming VCI value, in this case 4.
◼ This VCI value can be used by B to identify all packets coming from A
◼ Now to complete the connection, everyone needs to be told what their downstream
neighbor is using as the VCI for this connection
◼ Host B sends an acknowledgement of the connection setup to switch 3 and
includes in that message the VCI value that it chose (4)
◼ Switch 3 completes the VC table entry for this connection and sends the
acknowledgement on to switch 2 specifying the VCI of 7
◼ Switch 2 completes the VC table entry for this connection and sends
acknowledgement on to switch 1 specifying the VCI of 11
 ◼ Finally switch 1 passes the acknowledgement on to host A telling it to use the
VCI value of 5 for this connection
◼ When host A no longer wants to send data to host B, it tears down the connection by
sending a teardown message to switch 1
◼ The switch 1 removes the relevant entry from its table and forwards the message on to
the other switches in the path which similarly delete the appropriate table entries
◼ At this point, if host A were to send a packet with a VCI of 5 to switch 1, it would be
dropped as if the connection had never existed
◼ Characteristics of VC
◼ Since host A has to wait for the connection request to reach the far side of the
network and return before it can send its first data packet, there is at least one
RTT of delay before data is sent
◼ While the connection request contains the full address for host B (which might
be quite large, being a global identifier on the network), each data packet
contains only a small identifier, which is only unique on one link.
◼ Thus the per-packet overhead caused by the header is reduced relative
to the datagram model
◼ If a switch or a link in a connection fails, the connection is broken and a new
one will need to be established.
◼ Also the old one needs to be torn down to free up table storage space in
the switches
◼ The issue of how a switch decides which link to forward the connection request
on has similarities with the function of a routing algorithm
◼ Good Properties of VC
◼ By the time the host gets the go-ahead to send data, it knows quite a lot about
the network-
◼ For example, that there is really a route to the receiver and that the
receiver is willing to receive data
◼ It is also possible to allocate resources to the virtual circuit at the time it is
established
◼ For example, an X.25 network – a packet-switched network that uses the connection-
oriented model – employs the following three-part strategy
◼ Buffers are allocated to each virtual circuit when the circuit is initialized
◼ The sliding window protocol is run between each pair of nodes along the virtual
circuit, and this protocol is augmented with the flow control to keep the sending
node from overrunning the buffers allocated at the receiving node
 ◼ The circuit is rejected by a given node if not enough buffers are available at that
node when the connection request message is processed
◼ Comparison with the Datagram Model
◼ Datagram network has no connection establishment phase and each switch
processes each packet independently
◼ Each arriving packet competes with all other packets for buffer space
◼ If there are no buffers, the incoming packet must be dropped
◼ In VC, we could imagine providing each circuit with a different quality of service
(QoS)
◼ The network gives the user some kind of performance related guarantee
◼ Switches set aside the resources they need to meet this guarantee
◼ For example, a percentage of each outgoing link’s bandwidth
◼ Delay tolerance on each switch
◼ Most popular examples of VC technologies are Frame Relay and ATM
◼ One of the applications of Frame Relay is the construction of VPN
Asynchronous Transfer Mode (ATM): A Specific VC Technology
Asynchronous Transfer Mode (ATM) was a prominent virtual circuit networking technology
in the 1980s and early 1990s.
Popularity: Gained traction due to adoption by the telephone industry and its timing -
emerging as shared media like Ethernet reached their limits.
Function: Offered high-speed switching compared to existing technologies.
Competition: Seen as a rival to Ethernet switching and even the Internet Protocol (IP).
Current Status: While not as widely used today, ATM serves as a historical example of virtual
circuit technology.
The previous technology used fixed-size data packets called cells. Here are some key points
about ATM:
• Used small, fixed-length cells (53 bytes) for efficient hardware switching and low
latency.
• VPI (Virtual Path Identifier) and VCI (Virtual Circuit Identifier) combined to identify
connections.
• Offered benefits like efficient switching and interleaving voice/data traffic.
• Faced limitations like "cell tax" due to header overhead and potential for partially filled
cells.
ATM (Asynchronous Transfer Mode)
o Connection-oriented packet-switched network
o Packets are called cells
 ▪ 5 byte header + 48 byte payload
o Fixed length packets are easier to switch in hardware
▪ Simpler to design
▪ Enables parallelism
• ATM
o User-Network Interface (UNI)
▪ Host-to-switch format
▪ GFC: Generic Flow Control
▪ VCI: Virtual Circuit Identifier
▪ Type: management, congestion control
▪ CLP: Cell Loss Priority
▪ HEC: Header Error Check (CRC-8)
o Network-Network Interface (NNI)
▪ Switch-to-switch format
▪ GFC becomes part of VPI field

Figure 6. ATM cell format at the UNI.

The ATM packet format is shown in the above figure, more commonly called an ATM cell
will illustrate the main points.
• We’ll skip the generic flow control (GFC) bits, which never saw much use,
• and start with the 24 bits that are labelled VPI (virtual path identifier—8 bits) and
VCI (virtual circuit identifier—16 bits). If you consider these bits together as a single
24-bit field, they correspond to the virtual circuit identifier introduced above.
• The reason for breaking the field into two parts was to allow for a level of hierarchy:
All the circuits with the same VPI could, in some cases, be treated as a group (a virtual
path) and could all be switched together looking only at the VPI, simplifying the work
of a switch that could ignore all the VCI bits and reducing the size of the VC table
considerably.
• Skipping to the last header byte, we find an 8-bit cyclic redundancy check (CRC),
known as the header error check (HEC). Protecting the cell header is particularly
important because an error in the VCI will cause the cell to be misdelivered.
• Probably the most significant thing to notice about the ATM cell, and the reason it is
called a cell and not a packet, is that it comes in only one size: 53 bytes.
2.1.3 Source Routing
A third approach to switching that uses neither virtual circuits nor conventional
datagrams is known as source routing. The name derives from the fact that all the information
about network topology that is required to switch a packet across the network is provided by
the source host.
In computer networks, source routing is a unique approach for sending data packets
from a source to a destination. Unlike traditional methods, source routing relies on the sender
(source host) to specify the exact path the packet should take through the network. Here's a
breakdown to understand how it works:
All the information about network topology that is required to switch a packet across
the network is provided by the source host.
Core Concept:
• Imagine you're giving detailed instructions to a friend on how to navigate a maze.
Source routing is similar – the source host provides all the necessary information
(switches and ports) for the packet to reach its destination.
Implementation:
• There are different ways to implement source routing. One method involves assigning
a number to each output port of every switch.
• This number is then included in the packet header as a roadmap for each switch.
• The switch reads the port number in the header and directs the packet accordingly.

Challenges of Source Routing:

• Header Size: The packet header must contain information for every switch in the path.
This can lead to variable and potentially very large header sizes.
• Network Knowledge: The source host needs to know the complete network layout
(switch connections and ports) to create an accurate source route.
• Scalability Issues: As networks grow, maintaining accurate information for source
routing becomes difficult for senders.
Addressing Challenges:
• Header Techniques: Techniques like rotation, stripping, or using pointers can help
manage the header size and simplify switch processing.
• Limited Use: Source routing is often used for specific purposes like initial setup in
virtual circuit networks or troubleshooting in datagram networks (like the internet). It's
not typically used for everyday data transfer due to scalability limitations.
Strict vs. Loose Source Routing:
 • Strict Source Route: Every single switch along the path is explicitly specified in the
header.
• Loose Source Route: Only a set of key points (switches) are defined, leaving some
flexibility in the exact path between those points.
Limitations of source routing:
• Source routing is a non-standard approach compared to conventional routing methods.
• While it offers some benefits like targeted troubleshooting, its challenges limit its use
in large-scale networks.
• One way to do this would be to put an ordered list of switch ports in the header and to
rotate the list so that the next switch in the path is always at the front of the list. Figure
7 below illustrates this idea.
• In this example, the packet needs to traverse three switches to get from host A to host
B. At switch 1, it needs to exit on port 1, at the next switch it needs to exit at port 0, and
at the third switch it needs to exit at port 3.
• Thus, the original header when the packet leaves host A contains the list of ports (3, 0,
1), where we assume that each switch reads the rightmost element of the list. To make
sure that the next switch gets the appropriate information, each switch rotates the list
after it has read its own entry.
• Thus, the packet header as it leaves switch 1 enroute to switch 2 is now (1, 3, 0); switch
2 performs another rotation and sends out a packet with (0, 1, 3) in the header. Although
not shown, switch 3 performs yet another rotation, restoring the header to what it was
when host A sent it.

Figure 7. Source routing in a switched network (where the switch reads the rightmost
number)
 ◼ Other approaches in Source Routing

Figure 8. Three ways to handle headers for source routing: (a) rotation; (b) stripping; (c)
pointer. The labels are read right to left.
• In each case, the entry that this switch needs to read is A, and the entry that the next
switch needs to read is B.
Source routing can be used in both datagram networks and virtual circuit networks. For
example, the Internet Protocol, which is a datagram protocol, includes a source route option
that allows selected packets to be source routed, while the majority are switched as
conventional datagrams. Source routing is also used in some virtual circuit networks as the
means to get the initial setup request along the path from source to destination.
Source routes are sometimes categorized as strict or loose.
In a strict source route, every node along the path must be specified, whereas a loose source
route only specifies a set of nodes to be traversed, without saying exactly how to get from one
node to the next.
A loose source route can be thought of as a set of waypoints rather than a completely
specified route. The loose option can be helpful to limit the amount of information that a source
must obtain to create a source route. In any reasonably large network, it is likely to be hard for
a host to get the complete path information it needs to construct correct a strict source route to
any destination. But both types of source routes do find application in certain scenarios.
2.1.4 Bridges vs. LAN Switches:
Both bridges and LAN switches play crucial roles in connecting devices on a Local Area
Network (LAN). While they share some similarities, they have distinct functionalities and
purposes. Here's a detailed breakdown to help you understand them better:
◼ Bridges and LAN Switches
◼ Class of switches that is used to forward packets between shared-media LANs
such as Ethernets
◼ Known as LAN switches
◼ Referred to as Bridges

Bridges: Connecting Separate LANs

 • Function: Bridges operate at the OSI model's Layer 2 (Data Link Layer). They act as
a link between two separate LAN segments, filtering and forwarding data packets based
on their Media Access Control (MAC) addresses.
• Limited Ports: Bridges typically have only 2 or 4 ports, connecting two or a few LAN
segments.
• Packet Forwarding: Bridges examine the destination MAC address in the packet
header. The packet is discarded if the destination is on the same segment as the
receiving port. The packet is forwarded if it's on a different segment connected to
another port.
• Collision Domains: Bridges create separate collision domains. This improves network
performance by preventing collisions (data packet overlaps) when multiple devices
attempt to transmit simultaneously on a shared network segment.
• Broadcast Domains: Bridges do not segment broadcast domains. Broadcasts (packets
sent to all devices) still reach all devices on both connected LAN segments.
LAN Switches: Smarter Traffic Management within a LAN
• Function: LAN switches, also operating at Layer 2, are more sophisticated than
bridges. They have multiple ports (often 8, 16, or even more) and can connect numerous
devices within a single LAN.
• Learning Tables: Switches learn the MAC addresses of devices connected to each
port. They build a table that maps MAC addresses to specific ports.
• Smart Packet Forwarding: When a packet arrives, the switch consults its learning
table to determine the destination port. It then forwards the packet only to that specific
port, eliminating unnecessary broadcast traffic on other ports. This significantly
improves network efficiency compared to bridges.
• Collision Domains and Broadcast Domains: Similar to bridges, switches create
separate collision domains for each port, preventing collisions. However, unlike
bridges, switches also segment broadcast domains. This means broadcasts are only sent
to the specific segment where the intended recipient resides.
◼ Suppose you have a pair of Ethernets that you want to interconnect
◼ One approach is put a repeater in between them
◼ It might exceed the physical limitation of the Ethernet
◼ No more than four repeaters between any pair of hosts
◼ No more than a total of 2500 m in length is allowed
◼ An alternative would be to put a node between the two Ethernets and have the
node forward frames from one Ethernet to the other
◼ This node is called a Bridge
 ◼ A collection of LANs connected by one or more bridges is
usually said to form an Extended LAN
◼ Simplest Strategy for Bridges
◼ Accept LAN frames on their inputs and forward them out to all other outputs
◼ Used by early bridges
◼ Learning Bridges
◼ Observe that there is no need to forward all the frames that a bridge receives
◼ When a frame from host A that is addressed to host B arrives on port 1, there is
no need for the bridge to forward the frame out over port 2.
◼ How does a bridge come to learn on which port the various hosts reside?

Figure 9. Illustration of a learning bridge

The above table shows the forwarding table maintained by a Bridge. whenever the
bridge receives a frame on port 1 that is addressed to host A, it would not forward the frame
out on port 2; there would be no need because host A would have already directly received the
frame on the LAN connected to port 1. Anytime a frame addressed to host A was received on
port 2, the bridge would forward the frame out on port 1.
◼ Spanning Tree Algorithm
• The preceding strategy works just fine until the extended LAN has a loop in it,
in which case it fails in a horrible way—frames potentially loop through the
extended LAN forever. This is easy to see in the example depicted in Figure 10,
where, for example, bridges B1, B4, and B6 form a loop.
• Suppose that a packet enters bridge B4 from Ethernet J and that the destination
address is one not yet in any bridge’s forwarding table: B4 sends a copy of the
packet out to Ethernets H and I.
• Now bridge B6 forwards the packet to Ethernet G, where B1 would see it and
forward it back to Ethernet H; B4 still doesn’t have this destination in its table,
so it forwards the packet back to Ethernets I and J.
• There is nothing to stop this cycle from repeating endlessly, with packets
looping in both directions among B1, B4, and B6.

Figure 10. Extended LAN with loops.

◼ How does an extended LAN come to have a loop in it?
◼ Network is managed by more than one administrator
◼ For example, it spans multiple departments in an organization
 ◼ It is possible that no single person knows the entire configuration of
the network
◼ A bridge that closes a loop might be added without anyone
knowing
◼ Loops are built into the network to provide redundancy in case of failures
◼ Solution
◼ Distributed Spanning Tree Algorithm
◼ Think of the extended LAN as being represented by a graph that possibly has loops
(cycles)
◼ A spanning tree is a sub-graph of this graph that covers all the vertices but contains no
cycles
◼ Spanning tree keeps all the vertices of the original graph but throws out some
of the edges

Figure 11. Example of (a) a cyclic graph; (b) a corresponding spanning tree.

Table 5. Key differences between Bridge and Switch:

Feature Bridge Switch

Number of Ports 2-4 Multiple (8, 16, etc.)

Function Connects separate LANs Connects devices within a LAN

Packet Based on destination MAC, forwards Uses learning table to forward to

Forwarding to connected segment specific port

Creates separate collision

Collision Domains Creates separate collision domains
domains

Broadcast
Does not segment broadcast domains Segments broadcast domains
Domains