There are several ways of interconnecting networks, at different layers, there are different types of devices:
| Layers | Devices | If LANs are interconnected |
| Application | Application gateway | |
| Transport | Transport gateways | |
| Network | Router | Inter-routing All traffic stays in its own LAN |
| Data Link | Bridge or switch | MAC address filtering Local traffic stays in its own LAN |
| Physical | Repeater 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:
- transparent bridges (usually in Ethernet)
- 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:
- It discards a frame if source and destination are in the same LAN.
- It forwards a frame if source and destination are in different LANs.
- 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:
- Addressing: where should information be directed to?
- 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 services | Internal network operations | |
| Connectionless | Datagram transfer | IP |
| Connection-oriented | Reliable and possibly constant bit rate transfer | ATM |
Various “service over operation” combinations are possible. Context and requirements determine what combination makes sense, for instance:
- Connection-oriented service over connectionless operation
- 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 routing | mechanisms for determining the set of best paths for routing packets, which requires the collaboration of network elements |
| Forwarding | transfer of packets from inputs to outputs |
| Priority and scheduling | determining 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.
| Connectionless | Do not need to setup connection, packets are routed independently from node to node until the packet arrive at its destination. |
| Connection-oriented | Setup 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:
- transmission delay T (in total related to the number of hops)
- propagation delay Ο (in total related to the number of hops)
- 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-6The 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/3So 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 received | L Ο + (L - 1) P |
| fist bit released | L Ο + L P |
| last bit released | L Ο + 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.9So 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 requestCut-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 methods | Delay |
| Message switching | L Ο + 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 Circuit | Datagram | |
| Route Setup | Required | Not needed |
| Addressing | Use VCI (very short) | Use full source and destination address |
| State information | Use forwarding tables | Not needed |
| Routing | Route is fixed when setup | Each packet is routed independently |
| Router failure | Virtual circuit is terminated | Packet loss |
| Quality of service | Easy | Difficult |
| Congestion control | Easy | Difficult |
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
