Computer Networks_Unit 2

SWITCHING

What is a switch and its function?

A switch is a multi-input, multi-output device, which transfers packets from an input to one or more outputs. Large networks can be built by interconnecting a number of switches. Hosts are connected to the switch using point-to-point link. A switch receives packets on one of its links and transmits them on one or more other links. This is known as switching or forwarding.

List the different types of switching.

Discuss packet switched networks in detail.

Datagram networks

Ø  The datagram networks are referred to as connectionless networks.

Ø  The term connectionless means that the switch does not keep information about the connection state.

Ø  In a datagram network, the message is divided into packets of fixed or variable size.

Ø  There is no resource allocation for a packet. There is no reserved bandwidth on the links, and no scheduled processing time.

Ø  Resources are allocated on demand. The allocation is primarily done on a FCFS basis.

Ø  When a switch receives a packet, no matter what is the source or destination, the packet must wait if there are other packets being processed.

Ø  The lack of reservation creates delay.

Ø  Each packet is treated independently of all others regardless of its source or destination.

Ø  Packets belonging to the same message may travel different paths to reach their destination.

Ø  Packets can arrive out of order at the destination

Ø  Packets may also be lost or dropped because of a lack of resources.

Ø  It is the responsibility of an upper-layer protocol to reorder the datagrams or ask for lost datagrams before passing them on to the application.

Ø  Datagram switching is done at the network layer.

Routing table

Ø  In datagram network, packets are routed to their destinations by means of a routing table.

Ø  Each switch has a routing table which is based on the destination address.

Ø  The routing tables are dynamic and are updated periodically.

Ø  The destination addresses and the corresponding forwarding output ports are recorded in the routing table.

Ø  Every packet in a datagram network carries a header that contains the destination address

Ø  When the switch receives the packet, destination address is examined, the routing table is consulted to find the corresponding port through which the packet should be forwarded.

Analysis

Ø  The efficiency of a datagram network is better than that of a circuit-switched network; resources are allocated only when there are packets to be transferred.

Ø  The resources can be reallocated if it's idle, for other packets.

Ø  Each packet experiences a wait at a switch before it is forwarded. 

Virtual Circuit Switching networks

Ø  A virtual-circuit network (VCN) is a connection-oriented model.

Ø  It is implemented in the data link layer.

Ø  A virtual connection from the source to the destination is established before any data is sent. This is known as connection setup phase

o   Each switch should contain an entry in VC table that has four columns.

o   The entry contains incoming port and VCI, outgoing port and VCI

Ø  A Virtual Circuit Identifier (VCI) uniquely identifies a connection at a switch.

o   A VCI is a small number that has only link local scope.

o   A frame arrives at a switch with a VCI and when it leaves, it has a different VCI.

o   VCI configured by the administrator is known as permanent virtual circuit (PVC)

o   VCI set by a host through messages is known as switched virtual circuit (SVC)

Ø  In the teardown phase, the source requests the switches to delete the corresponding entry. 

Permanent Virtual Circuit

The figure shows a frame from source A on its way to destination B and how its VCI changes during the trip as configured by the network administrator. The frame arrives at port 1 with a VCI of 14. The switch looks in its table to find port 1 and a VCI of 14. When it is found, the switch knows to change the VCI to 66 and send out the frame from port 3. Each switch changes the VCI and routes the frame. The data transfer phase is active until the source sends all its frames to the destination. The procedure at the switch is the same for each frame of a message. The process creates a virtual circuit between the source and destination.

Switched Virtual Circuit

Two steps are involved in the setup phase namely setup request and acknowledgment.

Setup Request—A setup request frame is sent from the source to the destination.

a)      Source A sends a setup frame to switch 1.

b)      Switch 1 receives the setup request frame. It knows that a frame going from A to B goes out through port 3. The switch creates an entry in its table for this virtual circuit, but it is only able to fill three of the four columns. The switch assigns the incoming port (1), chooses an available incoming VCI (14) and the outgoing port (3). It does not know the outgoing VCI.

c)      Switch 2 receives the setup request frame. The table entries are incoming port (l), incoming VCI (66), and outgoing port (2).

d)     Similarly when switch 3 receives setup request frame, the entries are incoming port (2), incoming VCI (22), and outgoing port (3).

e)      Destination B receives the setup frame, and if it is ready to receive frames from A, it assigns a unused VCI to the incoming frames that come from A, say 77. This VCI lets the destination know that frames come from A, and not other sources as shown in figure.

Acknowledgment—A special frame, called the acknowledgment frame, completes the entries in the switching tables.

a)      The destination sends an acknowledgment to switch 3. The acknowledgment carries the global source and destination addresses so the switch knows which entry in the table is to be completed. The frame also carries VCI 77, chosen by the destination as the incoming VCI for frames from A. Switch 3 uses this VCI to complete the outgoing VCI column for this entry. 77 is the incoming VCI for destination B, but the outgoing VCI for switch 3.

b)      Switch 3 sends an acknowledgment to switch 2 that contains its incoming VCI in the table. Switch 2 uses this as the outgoing VCI in the table.

c)      Switch 2 sends an acknowledgment to switch 1. The process is the same and outgoing VCI is updated

d)     Finally switch 1 sends an acknowledgment to source A.

e)      The source uses the incoming VCI from switch 1 as its outgoing VCI for the data frames to be sent to destination B.

Setup Request	Acknowledgement

Analysis

Ø  There is at least one RTT of delay before data is sent due to setup request and acknowledgement

Ø  The per-packet overhead (header) is reduced relative to the datagram model since VCI is a small number.

Ø  If a switch or a link in a connection fails, the connection is broken and a new one needs to be established. Also, the old one need to be torn down to free up table storage space in the switches.

Bring out the differences between circuit and packet switching.

Circuit switching	Packet switching
Source and destination host are physically connected	No such physical connection exists
Switching takes place at the physical layer	Switching takes place at network (datagram) or data link layer (VCN)
Resources are allocated in advance	Resources are allocated on demand
Data transferred between the two stations is a continuous flow of signal	Data is transferred as discrete packets
Example: Telephony	Example: Internet

.

What is source routing?

Ø  All the information about network topology that is required to switch a packet across the network is provided by the source host.

Ø  For each packet that arrives on an input, the switch reads the port number in the header and transmits the packet on that output.

Ø  Source routing can be used in both datagram and virtual circuit networks

INTERNETWORKING PROTOCOL

Ø  Internetwork is an arbitrary collection of networks interconnected to provide host-to-host packet delivery service.

Ø  Internet is a logical network built out of a collection of physical networks, i.e., networks of networks. The nodes that interconnect the networks are called routers.

Ø  The Internet Protocol (IP) is used to build scalable, heterogeneous internetworks.

Ø  The ability of IP to run over any networking technology is its strength.

Ø  IP does nothing when a packet gets lost or corrupted. It is an unreliable service.

Ø  If reliability is required, then IP must be paired with a reliable protocol such as TCP.

Ø  IP provides no error control or flow control

Ø  The IP Service model has two parts

o   Addressing scheme that identifies all hosts in the internetwork uniquely

o   Datagram (connectionless) model of data delivery

Datagram Delivery

Ø  The IP datagram carries enough information to enable the network forward the packet to its destination correctly in a connectionless manner.

Ø  Each node compares the network part of the destination address with the network part of the address of each of its network interfaces.

Ø  If a match occurs, then the destination lies on the same physical network as the interface, and the packet is directly delivered.

Ø  Otherwise, the packet is forwarded to the next hop router after consulting its forwarding table. In case of no match, then the packet is forwarded to the default router.

IPv4 Packet Format

Ø  A IPv4 datagram is a variable-length packet consisting of two parts, header and data.

Ø  The header is 20 to 60 bytes in length and contains information essential to routing and delivery

Ø  The minimum packet length is 20 bytes and a maximum of 65,536 bytes.

Ø  Version―specifies version of the IPv4 protocol, i.e. 4.

Ø  Header length (HLen)―defines length of the datagram header in 4-byte words. When there are no options, the value is 5 (5 × 4 = 20)

Ø  Type of Service (TOS)―allows packets to be treated differently based on application needs. It is based on one of the parameters delay, throughput, reliability and cost

Ø  Length―specifies the total packet length (header plus data). The total length of the IPv4 datagram is restricted to 65,535 bytes (2¹⁶ - 1). If the length is large for certain lower layer protocols then fragmentation is done. Some lower layer protocols impose minimum payload length, in such case padding is done.

Ø  Identification―The 16-bit identifier uniquely identifies a datagram.

Ø  Flags―It is a 3-bit field. The first bit is reserved. The second bit (D) is called the do not fragment bit. The third bit (M) is called the more fragment bit.

Ø  Offset―shows relative position of this fragment with respect to the whole datagram. It is offset of the data in the original datagram measured in units of 8 bytes.

Ø  Time to live―defines lifetime of the datagram (default value 64). It is used to control the maximum number of hops visited by the datagram. Each router decrements TTL by 1 before forwarding. If the value is zero, the datagram is discarded to avoid looping.

Ø  Protocol―specifies the higher-level protocol that uses the services of the IPv4 layer such as TCP(6), UDP(17), etc.

Ø  Checksum―contains 16-bit checksum for the packet header to ensure that header information is correct

Ø  Source address―32-bit field source address identifying the sender.

Ø  Destination address―32-bit field destination address for delivery of the datagram

Ø  Options―If HLen > 5, then it indicates presence of options up to a maximum of 40 bytes. It can be used for network testing and debugging. Some options are:

o   Record Route―used to record the routers that handle the datagram.

o   Strict Source Route―used by the source to predetermine a route for the datagram.

IPv4 Addressing

Ø  IP addresses are hierarchical, i.e., it corresponds to hierarchy in the internetwork.

Ø  IP addresses consist of two parts, a network part and a host part.

Ø  The network part of an IP address identifies the network to which the host is attached

Ø  All hosts attached to the same network have the same network part in their IP address

Ø  The host part then identifies each host uniquely on that particular network

Ø  The routers have an address on each network, one for each interface.

Ø  IPv4 uses  32-bit addresses,  i.e.,  address  space  is  2³²  (more than 4 billion)

Ø  IPv4 address is expressed compactly as four octets (each ranging from 0 to 255) in dotted decimal notation. For eg., 117.149.29.2

Classful Addressing

Ø  In classful addressing, the address space is divided into five classes: A, B, C, D, and E.

Ø  The class of an IP address is identified by seeing the MSBs in binary notation or first byte in decimal notation.

Class	Binary	Decimal	Application
A	0	0–127	Unicast
B	10	128–191	Unicast
C	110	192–223	Unicast
D	1110	224–239	Multicast
E	1111	240–255	Reserved

Ø  Classes A, B and C are used for unicast addressing. Class D was designed for multicasting and class E is reserved.

Ø  Classes A, B, C have a certain number of bits for the network part and rest for the host part i.e., networks belonging to a class and number of hosts attached to it are fixed.

Class A	Class B	Class C

Class	No. of networks	No. of hosts per network	Designed for
A	126	224 – 2	WAN
B	16,382	65,534	Campus networks
C	221	254	LAN

Ø  In c1assful addressing, a large part of the available addresses were wasted, since Class A and B were too large for most organization.

Ø  Class C was suited only for very small organization and reserved addresses (class E) were sparingly used.

Explain fragmentation in IP

Ø  The maximum length of IPv4 datagram as 65,535 bytes.

Ø  Each physical network has its own Maximum Transmission Unit (MTU) which is the largest IP datagram that it can carry in a frame. For example, MTU for FDDI is 4500 bytes, Ethernet is 1500, point-to-point is 532, etc.

Ø  If the datagram payload is greater than MTU, then it is fragmented to fit the link-layer frame. The fragmented packets are each of size MTU, except the last one.

Ø  If the D flag bit is set, the datagram would not be fragmented. In such case, if it cannot pass through any other available network, then it is discarded.

Ø  The router usually fragments the datagram, when it has to forward the packet over a network that has a smaller MTU. Each fragment is routed independently.

Ø  A fragmented datagram may be fragmented if it encounters a network with an even smaller MTU.

Ø  IP does not attempt to recover from missing fragments. In such case, the host discards all other fragments.

Consider the following network

Ø  Suppose host H1 sends a datagram to host H8 with a payload of 1400 bytes.

Ø  The datagram goes through the ETH and FDDI network without any fragmentation.

Ø  When the packet arrives at router R2, which has an MTU of 532 bytes, it is fragmented with a maximum payload of 512 (plus 20 bytes for IP header)

Ø  These three fragments are then forwarded by router R3 across the second Ethernet to the destination host.

Ø  Reassembly is done at the receiving host and not at each router.

The fields in IPv4 packet header that are affected by fragmentation are:

Ø  When a datagram is fragmented, the value in the identification field is copied to all fragments. The identification number helps the destination in reassembling the datagram.

Ø  On fragmentation the router changes three fields:  flags, fragmentation offset, total length.

Ø  The router sets the M bit in the flags field sets the Offset to 0 for the first fragment

Ø  The data carried in the second fragment starts with the 513^th byte, so the Offset field in this header is set to 64 (count of 8-byte chunks)

Ø  The third fragment contains the last 376 bytes of data, and the offset is set to 128.  For the last fragment M bit is not set.

before fragmentation	after fragmentation at router R2

Give the block diagram of a router and brief its components.

Ø  The control processor is responsible for implementing the routing protocols.

Ø  The switching fabric transfers packets from one port to another

Ø  Routers are designed to handle variable-length packets

Ø  packetsize × pps = linerate, i.e, packet size at which the router can forward at line rate.

ADDRESS TRANSLATION PROTOCOL (ARP)

Ø  A host or a router to send a IP datagram, needs to know both the logical and physical address of the receiver.

Ø  The IP address is obtained from DNS (host) or from its routing table (router).

Ø  The physical address of the receiver is needed to pass through the physical network.

Ø  The address resolution protocol (ARP) enables to know the physical address of a node when the logical address is known.

Ø  ARP enable each host on a network to build up a table of mappings between IP addresses and link-level addresses

Ø  ARP takes advantage of the broadcast support rendered link-level networks, such as Ethernet and token ring.

Packet Format

0                         8		16	31
Hardware Type			Protocol Type
Hardware length	Protocol length		Operation
Sender hardware address
Sender protocol address
Target hardware address
Target Protocol address

  

Ø  Hardware type―defines the type of the network on which ARP is running. Each LAN has been assigned an integer based on its type. Ethernet has value 1.

Ø  Protocol type―specifies the protocol value. ARP can be used with any higher-level protocol. For IPv4 the value is 0x0800.

Ø  Hardware length―specifies length of the physical address in bytes. For Ethernet, the value is 6.

Ø  Protocol length―specifies length of the logical address in bytes. For IPv4 protocol, the value is 4.

Ø  Operation―defines the type of packet. It is either ARP request (1) or ARP reply (2).

Ø  Sender hardware address―a variable-length field contains physical address of the sender.

Ø  Sender protocol address―a variable-length field contains logical address of the sender.

Ø  Target hardware address―a variable-length field contains physical address of the target.

Ø  Target protocol address―a variable-length field contains logical address of the target.

Address Translation

The host checks its ARP table with the logical address. If an entry exists, then the corresponding physical address is used to construct a datagram. Otherwise, it finds physical address using ARP as follows:

1. An ARP request packet is created with value for operation field as 1.
2. The target physical address field is unknown and is filled with 0s (broadcast).
3. The ARP request is encapsulated in a IP packet and broadcasted on the physical network.
4. Every host or router receives it. All nodes except the target discard the packet.
5. The target node constructs an ARP reply packet with value of 2 for operation.
6. The ARP reply is unicast, sent back to the sender.
7. The sender receives the reply message and stores the target logical-physical address pair in its ARP table for sending future packets.

The following example shows how host A discovers the ethernet address of B, knowing B's ip address using ARP mechanism.

Ø  If the target node does not exist on the same network, then ARP request is sent to the default router, which then forwards it to the next hop router and so on till the packet reaches the destination.

How does ARP mechanism works in case of network that does not support broadcasting such as ATM.

Ø  ARP mechanism relies on broadcasting ARP request packets.

Ø  ATM network do not support broadcasting

Ø  LAN  emulation for large networks such as ATM do not yield desirable results

Ø  The ARP procedure for ATM network is known as ATMARP or Classical IP over ATM

Ø  The concept used in ATMARP is logical IP subnet (LIS)

Ø  In LIS, the ATM network is divided into several subnets.

Ø  All nodes on the same subnet have the same IP network number.

Ø  Two nodes that are on the same subnet can communicate directly, whereas nodes on different subnets communicate via one or more routers.

The ATM network has two subnets. Host H1 has a network number 10 and is connected to the router interface that connects to LIS 10. Similarly H2 is connected to interface LIS 12.

The ARP mechanism on ATM is as follows:

Ø  Each node in the LIS is configured with the ATM address of the ARP server to establish a virtual circuit to the ARP server when it boots.

Ø  The node sends a registration message to the ARP server that contains both the IP and ATM addresses of the registering node.

Ø  Thus ARP server builds up a complete database of all node (IP address, ATM address) pairs

Ø  Any node that wants to send a packet to some IP address asks the ARP server to provide the corresponding ATM address.

Ø  The ARP server performs a lookup operation and returns the ATM address.

Ø  The node can also maintain a cache of IP-to-ATM address mappings.

Ø  Thereafter the node establishes VC with the other node and sends packets.

Ø  For hosts on different subnets (say from H1 to H2), the hosts have to establish a virtual circuit to the router.

REVERSE ADDRESS RESOLUTION PROTOCOL (RARP)

Ø  To create an IP datagram, a host or a router needs to know its own IP address.

Ø  The IP address of a machine is usually read from its configuration file stored on the disk.

Ø  The machine can get its physical address (by reading its NIC).

Ø  A host knowing its physical address needs to know its logical address in case of a diskless station booted from its ROM.

Ø  The host does not know its IP address as it is assigned by the network administrator.

Ø  It can then use the physical address to get the logical address by using the RARP protocol.

Ø  A RARP request is created and broadcast on the local network.

Ø  Another machine on the local network that knows all the IP addresses will respond with a RARP reply.

Ø  The requesting machine must be running a RARP client program whereas the responding machine must be running a RARP server program.

Ø  In RARP, broadcasting is done at the data link layer. The broadcast address does not pass the boundaries of a network.

Ø  If an administrator has several networks / subnets, then a RARP server is required for each network/subnet.

Ø  RARP is replaced by protocols such as BOOTP and DHCP.

DYNAMIC HOST CONFIGURATION PROTOCOL (DHCP)

Ø  Most host operating systems provide a way for a system administrator to manually configure the IP information

Ø  Manual configuration is tedious and error-prone.

Ø  DHCP is derived from an earlier protocol called BOOTP

Ø  DHCP enables auto configuration method by relying on the existence of DHCP server.

Ø  DHCP provides static and dynamic address allocation that can be manual or automatic.

Ø  In static allocation, a DHCP server has a manually created static database that binds physical addresses to IP addresses.

Dynamic address allocation

Ø  The DHCP server maintains a pool (range) of available addresses that it hands out to hosts on demand

Ø  To  contact  a  DHCP  server,  a  booted  or  attached  host  sends  a DHCPDISCOVER message to a broadcast IP address (255.255.255.255).

Ø  The server checks its static database first. If the lookup is successful, the corresponding IP address is returned.

Ø  Otherwise, the server selects an IP address from the available pool, assigns the address to the client, and adds the entry to the dynamic database.

Ø  The addresses assigned from the pool are temporary addresses.

Ø  The DHCP server issues a lease for a specific time.

Ø  When the lease expires, the client must renew the lease. The server has the option to agree or disagree with the renewal.

Ø  DHCP is a application layer protocol. Both the server and client need not exist on the same network. In such case, a relay agent exists on each network.

o   The relay agent knows the IP address of DHCP server.

o   It intercepts the client's broadcast message and unicast it to DHCP server.

o   The DHCP server's response is sent back to the client.

DHCP packet format

Ø  A DHCP message is encapsulated within a UDP packet.

Ø  The client puts its hardware address (e.g., its Ethernet address) in the chaddr field.

Ø  The DHCP server replies by filling the yiaddr (“your” IP address) field and sends it to the client.

INTERNET CONTROL MESSAGE PROTOCOL (ICMP)

Ø  The IP protocol is a best-effort delivery service.

Ø  It has no error-reporting or error-correcting mechanism and also lacks mechanism for host and management queries. ICMP is designed to handle these lacunae.

Ø  ICMP messages are classified into error-reporting / query messages. It is encapsulated within an IP packet.

Ø  Error reporting messages are used to report errors to the source host, whereas query messages are used to diagnose network problems.

Ø  An ICMP message has an 8-byte header that includes type and data section.

Ø  The type value identifies the ICMP message.

Ø  The data carries information either for the source to indicate error or a query response.

Error Reporting

Ø  Destination Unreachable―When a router cannot route a datagram, the datagram is discarded and the router sends a destination unreachable message (type 3) back to the source host.

Ø  Source Quench―The source-quench message in ICMP was designed to add a kind of flow control to the IP. When a router or host discards a datagram due to congestion, it sends a source-quench message (type 4) to the sender of the datagram.

Ø  Time Exceeded―When a datagram visits a router, the value of TTL field is decremented by 1. When the value reaches 0, after decrementing, the router discards the datagram and a time-exceeded message (type 11) is sent to the original source.

Ø  Parameter Problem―If a router discovers an ambiguous or missing value in any field of the datagram, it discards the datagram and sends a parameter problem message (type 12) back to the source.

Ø  Redirection―A host may send a datagram to the wrong router. When the default router receives the datagram it forwards the datagram to the correct router and updates the routing table of the host by sending a redirection message (type 5) to the host.

Query

Ø  Echo Request and Reply―The combination of echo-request and echo-reply messages (type 8 & 0) determines whether two systems can communicate at the IP level.

Ø  Timestamp Request and Reply―Two machines can use the timestamp request and timestamp reply messages (type 13 & 14) to determine the round-trip time needed for a datagram.

Ø  Address-Mask Request and Reply―A host to obtain its mask, sends an address-mask request message (type 17) to a router on the LAN. The router responds with an address-mask-reply message (type 18), providing the necessary mask for the host.

Ø  Router Solicitation and Advertisement―For the host to know if the routers are functioning, it can broadcast a router-solicitation message (type 10). The router then broadcast its routing information using the router-advertisement message (type 9).

QUEUING DISCIPLINE

Routers implement some queuing discipline that governs how packets are buffered while waiting to be transmitted.  The common queuing algorithms are:

Ø  First-In-First-Out (FIFO)

Ø  Fair Queuing (FQ)

FIFO Queuing

Ø  FIFO queuing is also known as First-Come First-Serve (FCFS). The first packet that arrives at a router is the first packet to be transmitted.

Ø  When a packet arrives, it is queued up at the router's buffer space. The buffer space at each router is finite.

Ø  If a packet arrives and the queue is full, then the router discards that packet. This is known as Tail drop since packets arriving at tail end of queue is dropped.

Ø  Thus FIFO queuing is a combination of FIFO scheduling discipline and Tail drop policy.

FIFO queuing	Tail Drop

Advantages

Ø  Its implementation is very simple and widely used.

Disadvantages

Ø  Packets are dropped without regard to its flow type or its importance.

Ø  Routers do not help in congestion control and it is left to TCP at the end hosts.

Priority Queuing

Ø  Priority queuing is a variation of FIFO queuing

Ø  Each packet is marked with a priority. The priority can be set in TOS field.

Ø  Routers have a FIFO queue, one for each type of priority

Ø  The router always transmits packets out of the highest-priority queue. If that queue is empty, then packets in the next high priority queue is taken for processing.

Ø  Packets in the lowest-priority queue are processed last.

Ø  The network can charge more to deliver high-priority packets than low-priority ones.

Advantages

Ø  A priority queue can provide better QoS than FIFO queue because high priority traffic such as multimedia, can reach the destination with less delay.

Ø  In internet, routing updates after a topological change are marked in TOS field, as it is important for stabilization of routing tables.

Disadvantages

Ø  The potential drawback is that packets in lower-priority queues may never be processed, if there is a continuous flow in high-priority queues. This condition is called starvation.

Fair Queuing (FQ)

Ø  Fair Queuing addresses the problems of FIFO queuing such as non-discrimination of traffic sources and lack of congestion-control.

Ø  In fair queuing, a separate queue is maintained for each type of flow.

Ø  Router services these queues in a round-robin manner.

Ø  When a flow's queue gets filled up, further packets are discarded. Thus all flows have a fair share of the bandwidth.

Ø  FQ segregates traffic so that ill-behaved traffic sources do not interfere with the legitimate traffic sources.

Ø  FQ enforces fairness among a collection of flows managed by a well-behaved congestion control algorithm.

Round-robin servicing

Ø  Round-robin servicing needs to be done in terms of bit-by-bit, but interleaving bits from different packets is not feasible.

Ø  FQ simulates bit-by-bit RR by first determining when a given packet would finish being transmitted and then using it to sequence the packets for transmission as follows:

o   Let P_i denote the length of packet i

o   Let S_i denote the time when the router starts to transmit packet i

o   Let F_i denote the time when the router finishes transmitting packet i  (F_i = S_i + P_i)

Ø  A packet can be transmitted after its arrival time A_i and not before its predecessor i-1 has been transmitted. Therefore S_i = max (F_i-1 , A_i) and F_i = max (F_i-1 , A_i) + P_i

Ø  The packet with the lowest F_i timestamp is the next to be transmitted.

Ø  A newly arriving packet can preempt a packet that is currently being transmitted.

The following examples demonstrate the above concept.

Shorter packets sent first	Non-preemptive of packet in progress

In first example, packets from flow1 are selected before flow2, whereas in the second example, transmission of flow2 is not preempted by the arrival of a short packet onto flow1.

Advantages

Ø  The link is never idle as long as there is at least one packet in any of the flow. This characteristic is known as work-conserving.

Ø  If there are n flows, then a flow cannot use more than 1/nth of the bandwidth

Ø  If some flows are not using their shares then the free bandwidth is also shared amongst the available flows.

Weighted Fair Queuing (WFQ)

Ø  Weighted Fair Queuing is a variation of fair queuing.

Ø  In WFQ, each flow is assigned a weight, whereas FQ gives each queue a weight of 1.

Ø  The weight specifies how many bits to transmit each time the router services that queue

Ø  The weight also implies the percentage of the link’s bandwidth that flow will get.

Ø  In this technique, the packets are assigned different classes and admitted to different queues, but are weighted based on the priority of the queues.

Ø  The system processes packets in each queue in a round-robin fashion with the number of packets selected from each queue based on the corresponding weight.

In figure, the weights are 3, 2, and 1 respectively. Thus three packets are processed from the first queue, two from the second queue, and one from the third queue.

ROUTING PROTOCOLS

Internet is so large that no one routing protocol can handle the task of updating the routing tables of all routers. Internet is divided into autonomous systems. An autonomous system (AS) is a group of networks and routers under the authority of a single administration. Routing inside an autonomous system is referred to as intra-domain routing. Routing between autonomous systems is referred to as inter-domain routing.

DISTANCE VECTOR ROUTING

Ø  Each node knows the distance (cost) to each of its directly connected neighbors

Ø  A node's table is distributed to all its neighbors.

Ø  Each node computes a vector (table) of minimum distance (cost) to every other node using the information from its neighbors.

Ø  The table at each node guides a packet to the desired node by showing the next hop.

Example

Consider a system of seven nodes named as A, B, C, D, and E.

Initial State

Ø  Each node sets a distance of 1 to its immediate neighbors and 0 to itself.

Ø  The distance for non-neighbors is marked as infinity (unreachable).

Ø  For example, the initial routing table stored at A is

Destination	Cost	Next Hop
B	1	B
C	1	C
D	∞	—
E	1	E
F	1	F
G	∞	―

Sharing & Updation

Ø  Each node shares its cost list (distance) to all of its directly connected neighbors.

Ø  Node A receives distance vectors from B, C, E and F.

Ø  For example the tables from C and F sent to A are:

Destination	Cost	Next Hop		Destination	Cost	Next Hop
A	1	A		A	1	A
B	1	B		B	∞	―
D	1	D		C	∞	―
E	∞	―		D	∞	―
F	∞	―		E	∞	―
G	∞	―		G	1	G
C's table				F's table

Ø  Now node A can use information from its neighbors to reach other unreachable nodes. For example, node F tells node A that it can reach node G at a cost of 1.

Ø  Node A updates its routing table by comparing with one of its neighbor table as follows

o   For a corresponding destination:
Total cost = Cost between itself and neighbor + neighbor's cost to that destination.

o   If Total cost is less than its Cost, then the Cost is changed to Total cost and its Next Hop is set to neighbor node

Ø  For example, A compares its table with C's table

o   Total cost for B = Cost(A,B) + Cost (B, C) = 2

§  Since 2 > 1, there is no change

o   Total cost for D = Cost (A,C) + Cost(C,D) = 1 + 1 = 2.

§  Since 2 < ∞, entry for destination D in A's table is changed to (D, 2, C)

o   Similarly other entries are checked and there is no change.

Ø  In a similar manner, A updates its routing table. The final routing table at A is

Destination	Cost	Next Hop
B	1	B
C	1	C
D	2	C
E	1	E
F	1	F
G	2	F

Ø  It only takes a few exchanges of information between neighbors before each node has a complete routing table.

Ø  The process of obtaining complete routing information to all nodes is called convergence.

Ø  The sharing & updation process take place periodically and in case of triggered update.

Ø  Periodic updation is normally done every 30sec, but depends on the protocol used.

Ø  Triggered update happens whenever a node's routing table is affected due to changes in the network (such as link failure). This forces the node to update its neighbors, neighbors update their neighbors and so on.

Triggered Update

Ø  A node can test link status by using control packets. Alternatively a link or node failure is presumed, if it does not receive periodic updates from its neighbor for a while.

Ø  Assume that F detects that its link to G has failed. F sets its new distance to G to ∞ and shares its table with A.

Ø  Node A updates its distance to G as ∞.

Ø  Node A also receives periodic update from C which advertises its distance to G as 2.

Ø  Node A updates its distance to G as 3 through C.

Loop Instability

Ø  Certain circumstances can prevent the network from stabilizing, known as loop instability.

Ø  Consider a system with three nodes. Initially nodes A and B know how to reach node X.

Ø  Suppose, the link between A and X fails, Node A changes its table and shares this information with B.

Ø  If B sends its routing table to A before receiving A's routing table, node A receives the update and updates its routing table.

Ø  Based on the triggered update strategy, A sends its new update to B.

Ø  Thus A and B update each other until cost to X reaches a large number termed as infinity

Ø  This problem is also known as count-to-infinity. Solutions are

Defining Infinity

Ø  Infinity is redefined to a small number. Most implementations define 16 as infinity.

Ø  The drawback is that distance vector routing cannot be used in large networks. Distance between any two nodes should not exceed 15 hops.

Split Horizon

Ø  When a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor.

Ø  For example, if B has the route (E, 2, A) in its table, then it does not include the route (E, 2) in its update to A.

Split Horizon and Poison Reverse

Ø  The split horizon strategy has one drawback. In distance vector routing if there is no news about a route for a specific period, the node deletes the route from its table.

Ø  In split horizon with poison reverse, Node B can still advertise the value of (E, 2) to A, but with a warning message.

Ø  This approach delays the convergence process.

Ø  The split horizon methods do not work well for large number (> 2) of nodes.

Routing Information Protocol (RIP)

Ø  RIP is the canonical example of a routing protocol built on the distance-vector algorithm

Ø  RIP is an intra-domain routing protocol used inside an autonomous system.

Ø  It is extremely simple and widely used.

Ø  The routers advertise the cost of reaching networks, instead of reaching other routers.

Consider the following network

Ø  Router C advertises to router A that it can reach networks 2 and 3 at a cost of 0, networks 5 and 6 at cost 1 and network 4 at cost 2.

Ø  RIP takes the simplest approach, with all link costs being equal to 1.

Ø  The distance is defined as the number of links to reach the destination. The metric in RIP is called a hop count.

Ø  Infinity is defined as 16, i.e., any route in an AS using RIP cannot have more than 15 hops. It is limited to run on only smaller networks.

Ø  Routers running RIP send their advertisements every 30 seconds

Ø  The RIP packet format is given below. The majority of the packet contains (network-address, distance)  pairs

LINK STATE ROUTING

Ø  Link-state routing protocols rely on two mechanisms:

o   Reliable dissemination of link-state information

o   calculation of routes from all the accumulated link-state knowledge

Reliable Flooding

Ø  Reliable flooding is the process of ensuring all nodes having a copy of the link-state information from all the other nodes

Ø  Each node creates an update packet called a link-state packet (LSP) that contains

o   ID of the node

o   List of directly connected neighbors of that node and the cost to each one

o   Sequence number

o   Time to live for this packet

Ø  Each node sends its LSP out on each of its directly connected links except from the link which it came from.

Ø  Transmission of LSPs between adjacent routers is made reliable using acknowledgments

Ø  Each node that receives a LSP checks to see whether it has a copy.

o   If not, it stores and forwards the LSP on all of its links

o   If it has a copy, it compares the sequence numbers.

§  If the received LSP has a bigger sequence number, then it is stored and forwarded, since it is a recent LSP. The old one discarded.

Ø  Since a node passes a recent LSP to its neighbors and who in turn forward it their neighbors, the recent LSP eventually reaches all nodes.

Ø  LSP is generated either periodically or when there is a change in the topology detected using hello packets.

Consider the flooding in a small network

Ø  LSP arrives at node X, which sends it to neighbors A and C.

Ø  A and C do not send it back to X, but send it on to B.

Ø  Since B receives two identical copies of the LSP, it will accept whichever arrived first and ignore the second as a duplicate.

Ø  It then passes the LSP on to D. Since D has no neighbors to flood the process is complete.

Reducing Overhead

Ø  Flooding creates traffic and is an overhead to the network. Mechanisms to reduce are:

Ø  Timers―using long timers, in terms of hours for periodic generation.

Ø  Sequence numbers―64-bit sequence numbers ensure that they do not wrap around so soon and is used to discard old LSPs.

Ø  Time to live―A router always decrements TTL before forwarding a LSP. When the TTL reaches 0, the node refloods the LSP with a TTL of 0, to which all the nodes in the network delete that LSP

Route Calculation

Ø  Once a node has copy of the LSP from every other node, it knows the entire  network

Ø  Each node computes its routing table directly from the LSPs using a realization of Dijkstra’s algorithm called forward search algorithm

Ø  Each node maintains two lists namely Tentative and Confirmed.

Ø  Each of these lists contains a set of entries of the form (Destination, Cost, NextHop)

Forward Search algorithm

1. Initialize the Confirmed list with an entry for the node with a cost of 0.
2. For the node just added to the Confirmed list, call it node Next, select its LSP.
3. For each neighbor of Next, calculate the cost to reach as the sum of the cost from itself to Next and from Next to Neighbor.
1. If Neighbor is currently on neither the Confirmed nor the Tentative list, then add (Neighbor, Cost, NextHop) to the Tentative list.
2. If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for Neighbor, then replace the current entry with (Neighbor, Cost, NextHop), where NextHop is the direction to reach Next.
4. If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to step 2.

For the following network, the process of building routing table for node D is tabulated

Step	Confirmed	Tentative	Comment
1	(D,0,-)		D is moved to the Confirmed list initially
2	(D,0,-)	(B,11,B) (C,2,C)	Based on D's LSP, its immediate neighbors B and C are added to Tentative list
3	(D,0,-) (C,2,C)	(B,11,B)	The lowest-cost member C of Tentative list is moved onto Confirmed list. C's LSP is to be examined next.
4	(D,0,-) (C,2,C)	(B,5,C) (A,12,C)	Cost to reach B through C is 5, so the entry (B,11,B) is replaced. C's neighbor A is also added to Tentative list
5	(D,0,-) (C,2,C) (B,5,C)	(A,12,C)	The lowest-cost member B is moved to the Confirmed list. B's LSP is to be examined next
6	(D,0,-) (C,2,C) (B,5,C)	(A,10,C)	Since A could be reached B at a lower cost than the existing one, the Tentative list entry (A,12,C) is replaced to (A,12,C).
7	(D,0,-) (C,2,C) (B,5,C) (A,10,C)		The lowest-cost and only member A is moved to Confirmed list. Processing is over.

Open Shortest Path First Protocol (OSPF)

OSPF is one of the most widely used link-state routing protocols. The features added to link-state algorithm are:

Ø  Authentication of routing messages: Misconfigured hosts are capable of bringing down a network by advertising to reach every host with the lowest cost 0. Such disasters are averted by mandating routing updates to be authenticated.

Ø  Additional hierarchy: In OSPF, a domain is partitioned into areas, i.e., a router need not know the complete network, instead only its area.

Ø  Load balancing: OSPF allows multiple routes to the same place to be assigned the same cost and will cause traffic to be distributed evenly over those routes

OSPF Header

Ø  Version―represents the current version, i.e., 2.

Ø  Type―represents the type value (1–5) of OSPF message.

Ø  SourceAddr―identifies the sender of the message

Ø  AreaId―32-bit identifier of the area in which the node is located

Ø  Checksum―16-bit checksum

Ø  Authentication type―has value 0 if no authentication is used, 1 for simple password and 2 for cryptographic authentication checksum.

Ø  Authentication―contains password or cryptographic checksum

Type1 Link State Advertisement

Ø  LS Age―is incremented at each node until it reaches a maximum (expiry)

Ø  Type―defines type of LSA. Type1 LSAs advertise the cost of links between routers.

Ø  Link-state ID―32-bit identifier of the router.

Ø  Advertising router―For type 1 LSA, it is same as Link-state ID

Ø  LS sequence number―used to detect old or duplicate packets

Ø  LS checksum―covers all fields except LS Age

Ø  Length―length of the LSA in bytes

Ø  Link ID and Link Data―identify a link

Ø  Metric―specifies cost of the link.

Ø  Type―specifies type of link (for example, point-to-point)

Ø  TOS―allows OSPF to choose different routes based on the value in TOS field