There are several ways of interconnecting networks, at different layers, there are different types of devices:

LayersDevicesIf LANs are interconnected
ApplicationApplication gateway
TransportTransport gateways
NetworkRouterInter-routing
All traffic stays in its own LAN
Data LinkBridge or switchMAC address filtering
Local traffic stays in its own LAN
PhysicalRepeater or hub
Hub is the simplest repeater in Ethernet
Signal representation
All traffic appears in both LANs


Data Link Layer: Frame Switching

Bridge operates at a data link layer imply capability to work with multiple network layers, it must deal with difference in MAC formats, max frame length, data rates buffering, timers, security, etc.

In a common case, a bridge interconnects LANs of the same type to have a frame filtering capability. A bridge has to monitor the MAC address of each frame. Two types of bridges are widely used:

  1. transparent bridges (usually in Ethernet)
  2. source routing bridges (usually in Token Ring and FTTI)

Transparent Bridges

When it comes to interconnection of IEEE LANs with complete transparency, the bridge will create a lookup table based on backward learning. The table associates each station in the LAN with a port number on the bridge. The bridge observes source address of arriving frames:

  1. It discards a frame if source and destination are in the same LAN.
  2. It forwards a frame if source and destination are in different LANs.
  3. It floods a frame if its destination is unknown.

In a static network, tables eventually store all addresses and the backward learning stops. In practice, entries of stations are added and removed all the time. Adaptive backward learning introduced a timer to age each entry of station and force the table to be relearned periodically. The learning process works fine as long as there are no loops in the interconnected network. Spanning tree algorithms are adopted to avoid loops in interconnection.

Network Layer

Network layer is the most complex layer in the entire architecture. This layer must be able to deal with very large scale topology. There are mainly 2 challenges:

  1. Addressing: where should information be directed to?
  2. Routing: what path should be used?

Information is transferred as payload in data packets, which may go through different possible routes. So they may experience random delays and possible loss due to buffer overflow at some intermediate point. From application’s point of view, different applications impose different requirements on the information transfered.

While transport layer protocols (which use network layer as a service) operate end-to-end, the network layer operates hop-by-hop. Network layer can offer a variety of services to the transport layer.

Network servicesInternal network operations
ConnectionlessDatagram transferIP
Connection-orientedReliable and possibly constant bit rate transferATM

Various “service over operation” combinations are possible. Context and requirements determine what combination makes sense, for instance:

  1. Connection-oriented service over connectionless operation
  2. Connectionless service over connection-oriented operation

Network layer may not offer all kinds of services, usually it keeps the set of network services to the minimum. The end-to-end argument for system design states that an end-to-end function is best implemented at a higher level than at a lower level, since an end-to-end service requires all intermediate components to work properly and higher level design is better positioned to ensure correct operation. Essential network functions include:

Packet routingmechanisms for determining the set of best paths for routing packets, which requires the collaboration of network elements
Forwardingtransfer of packets from inputs to outputs
Priority and schedulingdetermining order of packet transmission in each network element

Other important but optional functions are congestion control, segmentation & reassembly, security, etc.



Multiplexing and Oversubscriptions

User demand can undergo dramatic change, for instance peer-to-peer applications stimulate huge growth in traffic volume. Also Internet structure is highly decentralized, paths traversed by packets can go through many networks controlled by different organizations, no single entity is responsible for end-to-end services.

In packet networks, individual packet streams are highly bursty, so statistical multiplexing is used to concentrate streams. The main purpose of the multiplexer is to combine the typically bursty traffic flows from the individual computers into aggregated flows, so that the transmission lines to the packet network is used more efficiently.

Oversubscription is a commonly used technique in multiplexing. Suppose there are N subscribers each with max bandwidth c bits/second to the multiplexer. So aggregated maximum bandwidth of all subscribers is therefore N ร— c. However not all subscribers are always active. Oversubscription provides a smaller bandwidth say m ร— c from the multiplexer to packet network, where m is smaller than n. So the oversubscription ratio is calculated as N / m.

host1 \
host2  \
host3   - - N ร— c - - [multiplexer] - - m ร— c - - [packet network]
...    /
hostN /

There would be overflow if unfortunately that some time all N stations transmit all at the maximum rate c. The question here becomes “what is the value of m so that the overflow probability is smaller than a certain percentage, say 1%?” Studies shows that a feasible oversubscription rate increases with size of the multiplexing.

Packet Switching

Packet switching networks provide for the interconnection between sources and destinations on a dynamic basis. Network resources are typically allocated onto an information flow only when needed, therefore are shared among many users, resulting in high efficiency and low cost.

There are two fundamental approaches to transferring information over a packet switching network. Both approaches involve the use of packet switches to direct packets across the network.

ConnectionlessDo not need to setup connection, packets are routed independently from node to node until the packet arrive at its destination.
Connection-orientedSetup a virtual circuit connection across the network before information can be transferred.

The Problem of Message Switching

Packet switching has its origin in the message switching for telegraph, which typically operates in the store-and-forward fashion, which means a message has to be completely received by a switch before it can be forwarded to the next switch.

Recall the overall delay has two components:

  1. transmission delay T (in total related to the number of hops)
  2. propagation delay ฯ„ (in total related to the number of hops)
  3. queuing delay (because the transmission lines are shared, the message may have to wait until previously queued messages are transmitted)

Example 1

In an example like this, there are 2 switches between source and destination, so there are 3 hops, the minimum delay will be 3 (ฯ„ + T) (without considering any queuing delay and any other error checking delay). Long message switching usually suffers long delay, it is also more vulnerable to errors.

Source --- Switch 1 --- Switch 2 --- Destination

     Source ---------------------------------------
             \         \
   Switch 1 -ฯ„----T--------------------------------
                        \         \
   Switch 2 ---------------------------------------
                                   \         \
Destination ---------------------------------------

Example 2

Consider another example, suppose we want to transmit a large message of 1 megabits over two hops. The bit error rate at each hop is 10-6.

Source (1 Mbits) ------ Switch 1 ------ Destination
                BER = 10-6      BER = 10-6

The question is “how many bits is needed to deliver the messages successfully?” By messages switching, the source sends the 1-megabits message at once. The probability of transmission success at each hop is about 33%.

P = (1 - BER)^length of message
  = (1 - 10-6)^(106) โ‰ˆ e^(-10-6)(106) = e-1 โ‰ˆ 1/3

So on average it takes about 3 transmissions per hop, and the total number of bits transmitted over two hops is approximately 6 megabits.



Datagrams Packet Switching

In packet switching, a long message is broken into smaller packets, source and destination addresses are given in the packet header. It’s connectionless, packets are routed independently, packets may arrive at the destination out of order. Pipelining all packets across network can reduce delay and increase throughput.

Example 1

Consider the example 1 as above, but this time we partition the message into 3 packets, assuming the 3 packets follow the same path and no queuing delay and error checking delay. The transmission delay for each packet is T/3. Propagation delay is the same as before, ฯ„, for each link. In total, there are 3 ฯ„ because there are 3 hops. This packet pipelining reduces total delay of message delivery to 3 ฯ„ + 5 (T/3).

Source --- Switch 1 --- Switch 2 --- Destination

     Source ---------------------------------------
             \ 1 \ 2 \ 3 \
   Switch 1 -ฯ„-T/3---------------------------------
                  \ 1 \ 2 \ 3 \
   Switch 2 ---------------------------------------
                       \ 1 \ 2 \ 3 \
Destination ---------------------------------------
                        |   |       | last bit released
                        |   | fist bit released
                        | first bit received

One can further derive the total delay for k-packet message over L hops, where T = k P.

first bit receivedL ฯ„ + (L - 1) P
fist bit releasedL ฯ„ + L P
last bit releasedL ฯ„ + L P + (k - 1) P

While packet switching cannot reduce the total propagation delay, it can reduce the packet transmission delay significantly by packet pipelining.

Example 2

Consider the example 2 above again, this approach partitioned the 1 megabits message into 10 smaller packets (100 kilobits each packet). The probability that packet arrives correctly per hop is about 90%.

P = (1 - BER)^length of packet
  = (1 - 10-6)^(105) โ‰ˆ e^(-10-6)(105) = e-1/10 โ‰ˆ 0.9

So on average it takes about 1.1 transmissions per hop, and the total number of bits transmitted over two hops is approximately 2.2 megabits.

Virtual Circuit Packet Switching

Virtual circuit packet switching aims to provide a connection for packet switching. It establishes a fixed path often called a virtual circuit between a source and a destination, prior to the packet transfer. Then all packets of a connection follow the same path.

First a route is determined through the network. Every router along the route is involved in the exchange of signal messages (connection requests and connection confirm) to setup the forwarding tables. Typically, each connection is identified by a local tag called a virtual circuit identifier (VCI).

Each input port has a forwarding table. Each router only needs to know how to relate incoming tags from one input port to outgoing tags in the corresponding output ports. The table lookup provides the Output port to which the packet is to be forwarded and the Output VCI that is to be used in the input port of the next router.

Forwarding table for an input port

Input VCI       Output port     Output VCI
   12                13              44
   15                15              23
   27                13              16
   ...               ...             ...

Once tables are setup, packets can flow along the path. As a table look up can be implemented by hardware, very high speed are possible for virtual circuit switching.



Connection setup delay is incurred before any packet can be transferred. The delay may be unacceptably high if only a few packets are being transferred.

Source --- Switch 1 --- Switch 2 --- Destination

     Source ---------------------------------------------
             \      / \ 1 \ 2 \ 3 \            /
   Switch 1 ---------------------------------------------
               \   /       \ 1 \ 2 \ 3 \      /
   Switch 2 ---------------------------------------------
                 \/             \ 1 \ 2 \ 3 \/
Destination ---------------------------------------------
             โ†‘      โ†‘                         โ†‘ release
             |      | connection confirm
             | connection request

Cut-Through Packet Switching

Cut-through packet switching is a modified version of the virtual circuit packet switching. This type of networks apply error checking on headers only, so packets can be forwarded as soon as the header is received and processed. Cut-through approach achieves lower delay.

Switching methodsDelay
Message switchingL ฯ„ + L T
= L ฯ„ + (L - 1) T + T
Packet switching (Store-and-forward)L ฯ„ + L P + (k - 1) P
= L ฯ„ + (L - 1) P + T
Packet switching (Cut-through)L ฯ„ + T

Datagrams vs Virtual Circuit

Virtual CircuitDatagram
Route SetupRequiredNot needed
AddressingUse VCI (very short)Use full source and destination address
State informationUse forwarding tablesNot needed
RoutingRoute is fixed when setupEach packet is routed independently
Router failureVirtual circuit is terminatedPacket loss
Quality of serviceEasyDifficult
Congestion controlEasyDifficult


My Certificate

For more on Frame Switching and Packet Switching, please refer to the wonderful course here https://www.coursera.org/learn/packet-switching-networks-algorithms


Related Quick Recap


I am Kesler Zhu, thank you for visiting my website. Check out more course reviews at https://KZHU.ai

Don't forget to sign up newsletter, don't miss any chance to learn.

Or share what you've learned with friends!

Leave a Reply

Your email address will not be published. Required fields are marked *