Packet Switching Networks part1

What is a Computer Network?

• Communication Networks: “Sets of nodes that are interconnected to allow the exchange of information such as voice, sound, graphics, pictures, video, text, data, etc…”

• Telephone Networks: “ The first well established and most widely used communication networks which are used for voice transmission”

– Telephone networks originally used analog transmission as a transmission technology for the information. However, digital transmission started to evolve replacing a lot of the analog transmission techniques used in telephone networks.

• Computer Networks: “Collection of autonomous computers interconnected by a technology to allow exchange of information”

A network is a series of connected devices. Whenever we have many devices, the interconnection between them becomes more difficult as the number of devices increases . Some of the conventional ways of interconnecting devices are

a. Point to point connection between devices as in mesh topology.

b. Connection between central device and every other device – as in star topology

c. Bus topology-not practical if the devices are at greater distances.

The solution to this interconnectivity problem is switching. A switched network consists of a series of interlinked nodes called switches. A switch is a device that creates temporary connections between two or more systems. Some of the switches are connected to end systems (computers and telephones) and others are used only for routing.

Taxonomy of switched networks

Circuit switching

• Traditional telephone networks operate on the basis of circuit switching

• In conventional telephone networks, a circuit between two users must be established for a communication to occur

• Circuit switched networks requires resources to be reserved for each pair of end users

• The resources allocated to a call cannot be used by others for the duration of the call

• The reservation of the network resources for each user results in an inefficient use of bandwidth for applications in which information transfer is bursty or if the information is small

Packet Switching

• Packet switched networks are the building blocks of computer communication systems in which data units known as packets flow across the networks.

• It provides flexible communication in handling all kinds of connections for a wide range of applications e.g. telephone calls, video conferencing, distributed data processing etc...

• Packet switched networks with a unified, integrated data infrastructure known as the Internet can provide a variety of communication services requiring different bandwidths.

• To make efficient use of available resources, packet switched networks dynamically allocate resources only when required.

• The form of information in packet switched networks is always digital bits.

Network services and internal network operation

Essential function of network:

• The essential function of network is to transfer information among the users that are attached to the network.

• Transfer of information may be single block of information or sequence of blocks as shown in below figure.

• In case of single block of information, we are interested in having the block delivered correctly to destination and also interested in delay experienced in traversing the network.

• In case of sequence of blocks, we are interested not only in receiving the blocks correctly and in right sequence.

 

Network service can be Connection-oriented service or connectionless service Connectionless service:

• Connectionless service is simple with two basic interactions (1) a request to network layer that it send a packet (2) an indication from the network layer that a packet has arrived

• It puts total responsibility of error control, sequencing and flow control on the end system transport layer

Connection-oriented service

· The Transport layer can not request transmission of information until a connection is established between end systems

· Network layer must be informed about the new flow

· Network layer maintains state information about the flows it is handling

· During connection set up, parameters related to usage and quality of services may be negotiated and network resources may be allocated

· Connection release procedure may be required to terminate the connection

It is also possible for a network layer to provide a choice of services to the user of network like:

· best-effort connectionless services

· Low delay connectionless services

· Connection oriented reliable stream services

· Connection oriented transfer of packets with guaranteed delay and bandwidth

Keeping the core of the network simple and adding the necessary complexity at the edge enhances the scalability of the network to larger size and scope

Internal network operation

The fig above shows the relation between the service offered by the network and the internal network operation

• The internal operation of the network is connectionless if packets are transferred within the network as datagrams

• Each packets are routed independently

• Packets follow different paths from end to end and arrive out of order

• The internal operation of the network is connection-oriented if packets follow a virtual circuit along a path that has been established from source to destination.

• Virtual circuit setup is done once, then packets are simply forwarded

• If resources are reserved then bandwidth, delay and loss guarantees are provided.

Network layer essentials

The Functions that need to be carried out at every node in the Network Layer are:-

· Routing: mechanisms for determining the set of best paths for routing packets requires the collaboration of network elements

· Forwarding: transfer of packets from NE inputs to outputs

· Priority & Scheduling: determining order of packet transmission in each NE

Optional: congestion control, segmentation & reassembly, security

Packet Network Topology

How users access packet networks?

Example -1 – Access Multiplexing

· The diagram above shows an access network with a point to point topology where computer in homes are connected to an access multiplexer located in service provider network.

· The main purpose of the access multiplexer is to combine the bursty traffic flows from individual computers into aggregated flows.

· Eg1. DSL traffic multiplexed at DSL Access Mux

· Eg2. Cable modem traffic multiplexed at Cable Modem Termination System

· Private IP addresses in Home is done using Network Address Translation (NAT).

Example -2- Campus Network

• LANs are interconnected through use of LAN switches identified by letter ‘S’ in the figure.

• Resources such as servers and databases that are primarily use are kept within the subnet. This reduces delay in accessing resources.

• Subnet has access to rest of organization through router R that access campus backbone network.

• Subnet uses campus backbone to reach outside world such as Internet through a border router.

• Servers containing critical resources that are required by entire organization are located in a data center where it can be easily maintained and security can be enforced

• Critical Servers maybe provided with redundant paths to campus backbone network

• The routers in the campus network are interconnected to form the campus backbone network.

Example -3 Connecting to Internet Service Provider

• Domain: the routers running the same routing protocol

• Autonomous System: one or more domains under the single administration.

• The campus network maybe connected to internet service provider (ISP) through one or more border routers.

• To communicate with other networks, the autonomous system must provide information about its network routes in border routers.

• The border router communicates on an interdomain level, whereas other routers operate at an intradomain level.

Example -4:- Internet Backbone

• National ISP provides points of presence (POPs) where customer can connect to their network

• The ISP has its own national backbone network for interconnecting its POPs

• The ISPs exchange traffic at public peering points called network access points (NAPs)

• NAP is a collocated set of high-speed routers through which the routers from different ISPs exchange traffic.

• Private peering points can be used to connect ISPs to exchange traffic directly with agreement routing polices.

Datagram and Virtual Circuits

Message Switching

• In message switching, a message is relayed from one switch to another until the message arrives at the destination

• A message switch operates in storeandforward fashion (a message has to be completely received by the switch before it can be forwarded to next switch)

• At the source each message has header attached to it to provide source and destination address.

• CRC check bits are attached to detect errors

• Each switch performs an error check, and if no errors are detected, the switch examines the header to determine the next hop in the path to the destination.

• Loss of messages may occur when a switch has insufficient buffering to store the arriving message.

• above figure shows the minimum delay that is incurred when a message is transmitted over a path that involves two intermediate switches.

• The message has to traverse the link to the first switch

• We assume

– the link has propagation delay in seconds,

T – the transmission time

• The message must traverse the link that connect two switches and from second switch to the destination.

• It follows that the minimum delay is 3 + 3T

• In general, the delay incurred in message switching involving L hops is L + LT

Disadvantages of message switching

• The probability of error increases with the length of the block. Thus long messages are not desirable

• Not suitable for interactive applications

Datagram or Connectionless Packet Switching

· Messages broken into smaller units (packets)

· Source & destination addresses in packet header

· Connectionless, packets routed independently (datagram)

· When a message arrives at the packet switch, the destination address is examined to determine the next hop.

· Packet may arrive out of order

· Re-sequencing maybe required at destination.

· Pipelining of packets across network can reduce delay, increase throughput

· Lower delay that message switching, suitable for interactive traffic

Packet Switching Delay

Assume three packets corresponding to one message traverse same path

• · Before the transmission of packets , it involves establishment of virtual circuit between source and destination
• · All packets follow the same path
• · Abbreviated header identifies connection on each link
• · Packets queue for transmission
• · Variable bit rates possible Connection Setup

• · Signaling messages propagate as route is selected
• · Signaling messages identify connection and setup tables in switches
• · Typically a connection is identified by a local tag, Virtual Circuit Identifier (VCI)
• · Each switch only needs to know how to relate an incoming tag in one input to an outgoing tag in the corresponding output
• · Once tables are setup, packets can flow along path

Connection Setup Delay

• · Connection setup delay is incurred before any packet can be transferred
• · Delay is acceptable for sustained transfer of large number of packets
• · This delay may be unacceptably high if only a few packets are being transferred
• · The minimum delay in virtual circuit packet switching is similar to that in datagram packet switching, except for an additional delay required to setup the virtual circuit.

Cut-Through switching

• · It is the modified form of virtual circuit packet switching
• · Some networks perform error checking on header only, so packet can be forwarded as soon as header is received & processed
• · Delays reduced further with cut-through switching

· A packet switch performs two functions 1) routing 2) forwarding.

◆ Routing functions uses algorithm to find a path to each destination and store the result in routing table.

◆ Forwarding function processes each incoming packet from an input port and forwards the packet to appropriate output port based on the information stored in routing table.

· The above fig (a) shows a generic packet switch consisting of input ports, output ports, an interconnection fabric and switch controller.

· Input ports and output ports are normally paired.

· Line card contains several input, output ports so that the capacity of the link connecting the line card to the interconnection fabric , which is typically of high speed, and is fully utilized.

· Line card is concerned with symbol timing, line coding, framing, physical addressing and error checking.

· The line card is made up of various chipsets as shown in fig (b) .

· The programmable network processor performs packet-related tasks such as table lookup and packet scheduling.

· The Controller in a packet switch contains a general-purpose processor to carry out a number of control and management functions.

· The controller also communicates with line card and the interconnection fabric

· The function of the Interconnection fabric is to transfer packets between the line cards.

· If there are high speed line cards the interconnection fabric is likely to be the bottleneck, since all traffic go through it.

· A bus type interconnection structure (whereby packets are transmitted serially) does not scale to large size, since the speed of the bus has to be about N times faster than the port speed.

· A cross bar interconnection fabric can transfer packets in parallel between input ports and output ports.

· The buffers need to be added to the crossbar to accommodate packet contention.

· The buffers can be located at input ports or output ports as shown in figure below

· Only one packet is allowed to proceed to a particular output in case of input buffering.

· Input buffering causes a problem head-of-line (HOL) blocking.

· Consider a situation where there are two packets at input buffer 2 as shown in fig. above.

· The first packet would like to go to output 3 and the second packet to output 8.

· Suppose that the packet from input buffer 1 would like to go output 3 at the same time.

· Suppose that the fabric arbiter decides to transmit the packet from input buffer 1. Then the first packet from input buffer 2 needs to wait until output 3 has transferred the packet from input buffer1. Meanwhile, the second packet has to wait behind the first packet even though output 8 is idle.

· This results in performance degradation of crossbar with input buffering.

· The problem of the first packet holding back other subsequent packets behind it is called head-of-line (HOL) blocking.

· One way to eliminate HOL blocking is to provide N separate input buffers at each input port. Such an input buffer is called virtual output buffer.

Routing in Packet Networks

· Routing: it is concerned with determining feasible path for packets to follow from each source to destination.

· Which path is “best”? The term best depends on the objective function that network operator tries to optimize which maybe Min delay, Min hop, Max bandwidth, Min cost, Max reliability

Goals of routing algorithm

1. Rapid and accurate delivery of packets

2. Adaptability to changes in network topology resulting from node or link failures.

3. Adaptability to varying source-destination traffic loads

4. Ability to route packets away from congested links

5. Ability to determine the connectivity of the network

6. Ability to avoid routing loops.

7. Low overhead

Classification of routing algorithms

Hierarchical Routing

· The hierarchical approach reduces the size of the routing tables at the routers in assigning the addresses.

· Hosts that are near each other (i.e. a group) should have addresses that have common prefixes. The routers examine only part of the address (i.e.. the prefix) to decide how a packet should be routed.

· Figure below gives an example of hierarchical address assignment and a flat address assignment.

FIG (a) Hierarchical Routing and (b) Flat Routing

· In figure (a) the hosts at each of the four sites have the same prefix. Thus the two routers need only maintain tables with four entries as shown.

· On the other hand, if the addresses are not hierarchical (Figure 7.27b), then the routers need to maintain 16 entries in their routing tables.