Link State Routing

Every node knows how to reach its directly connected neighbors, and if we make sure that the totality of this knowledge is disseminated to every node, then every node will have enough knowledge of the network to determine correct routes to any destination.

 Reliable Flooding is the process of making sure that all the nodes participating in the routing protocol get a copy of the link-state information from all the other nodes. As the term " flooding" suggests, the basic idea is for a node to send its link-state information out on all of its directly connected links, with each node that receives this information forwarding it out on all of its link. This process continues until the information has reached all the nodes in the network. 

Link State Packet(LSP) contains the following information:

1.The ID of the node that created the LSP;

2. A list of directly connected neighbors of that node, with the cost of the link to each one;

3. A sequence number;

4. A time to live(TTL) for this packet.

Flooding works in the following way. When a node X receives a copy of an LSP that originated at some other node Y, it checks to see if it has already stored a copy of an LSP from Y. If not, it stores the LSP. If it already has a copy, it compares the sequence numbers; if the new LSP has a larger sequence number, it is assumed to be the more recent, and that LSP is stored, replacing the old one. The new LSP is then forwarded on to all neighbors of X except the neighbor from which the LSP was just received.

Each switch computes its routing table directly from the LSPs it has collected using a realization of Dijkstra's algorithm.

Every 10 S the average delay of all packets is computed.

( A longer measurement period = less adaptive routing if conditions actually change. A shorter measurement period = less optimal routing because of inaccurate measurement.) The delay is considered to have changed "by a significant amount" whenever the absolute value of the change exceeds a certain thershold. Threshold is a decreasing function of time. Threshold is decreased by 12.8 ms.

When the delay changes by only a small amount, it is not important routing changes. However, whenever a change in delay is long lasting, it is important that it should be reported eventually, even if it is small; otherwise, additive effects can introduce large inaccuracies into routing. A threshold value which is initially high but which decreases to zero over a period time has this effect. In this paper, the initial threshold is 64 ms. After each measurement period, the newly measured average delay is compared with the previously reported delay. If the difference does not exceed the threshold, the threshold is decreased by 12.8 ms. 

Whenever a change in average delay equals or exceeds the threshold, an update is generated, and the threshold is reset to 64 ms. Since the threshold will eventually decay to zero, an update will always be sent after a minute, even if there is no change in delay. 

Link state routing

A link-state routing protocol is one of the two main classes of routing protocols used in packet switching networks for computer communications (the other is the distance-vector routing protocol). Examples of link-state routing protocols include open shortest path first (OSPF) and intermediate system to intermediate system (IS-IS).

Distance-Vector Routing

 Each node constructs a one-dimensional array containing the "distances"(costs) to all other nodes and distributes that vector to its immediate neighbors.

1. The starting assumption for distance-vector routing is that each node knows the cost of the link to each of its directly connected neighbors.

2. A link that is down is assigned an infinite cost.

Example.

Information                                  Distance to Reach Node

Stored at Node              A      B      C     D     E      F        G

A                                    0        1       1      ?      1       1         ?

B                                     1        0       1      ?      ?       ?        ?

C                                    1          1       0      1     ?       ?        ?

D                                     ?         ?       1       0    ?        ?       1

E                                      1        ?       ?      ?      0      ?        ?

F                                      1         ?       ?        ?      ?      0      1

G                                     ?         ?     ?        1      ?       1       0

Table 1. Initial distances stored at each node(global view).

We can represent each node's knowledge about the distances to all other nodes as a table like the one given in Table 1. Note that each node only knows the information in one row of the table.

1.Every node sends a message to its directly connected neighbors containing its personal list of distance. ( for example, A sends its information to its neighbors B,C,E, and F. )

2. If any of the recipients of the information from A find that A is advertising a path shorter than the one they currently know about, they update their list to give the new path length and note that they should send packets for that destination through A. ( node Blearns from A that node E can be reached at a cost of 1; B also knows it can reach A at a cost of 1, so it adds these to get the cost of reaching E by means of A. B records that it can reach E at a cost of 2 by going through A.)

subnetting

A subnetwork, or subnet, is a logically visible subdivision of an IP network. The practice of dividing a network into two or more networks is called subnetting. All computers that belong to a subnet are addressed with a common, identical, most-significant bit-group in their IP address. This results in the logical division of an IP address into two fields, a network or routing prefix and the rest field or host identifier. The rest field is an identifier for a specific host or network interface.

For the purpose of network management, an IP address is divided into two logical parts, the network prefix and the host identifier or rest field. All hosts on a subnetwork have the same network prefix. This routing prefix occupies the most-significant bits of the address. The number of bits allocated within a Tnetwork to the internal routing prefix may vary between subnets, depending on the network architecture. While in IPv6 the prefix must consist of a set of contiguous 1-bits, in IPv4 this is not enforced, though there is no advantage to using non-contiguous 1-bits. The host part is a unique local identification and is either a host number on the local network or an interface identifier.

 This logical addressing structure permits the selective routing of IP packets across multiple networks via special gateway computers, called routers, to a destination host if the network prefixes of origination and destination hosts differ, or sent directly to a target host on the local network if they are the same. Routers constitute logical or physical borders between the subnets, and manage traffic between them. Each subnet is served by a designated default router, but may consist internally of multiple physical Ethernet segments interconnected by network switches or network bridges. 

The routing prefix of an address is written in a form identical to that of the address itself. This is called the network mask, or netrmask, of the address. For example, a specification of the most-significant 18 bits of an IPv4 address, 11111111.11111111.11000000.00000000, is written as 255.255.192.0. If this mask designates a subnet within a larger network, it is also called the subnet mask. This form of denoting the network mask, however, is only used for IPv4 networks. 

The modern standard form of specification of the network prefix is CIDR notation, used for both IPv4 and IPv6. It counts the number of bits in the prefix and appends that number to the address after a slash (/) character separator:

192.168.0.0, netmask 255.255.255.0 is written as 192.168.0.0/24 In IPv6, 2001:db8::/32 designates the address 2001:db8:: and its network prefix consisting of the most significant 32 bits. 

This notation was introduced with Classless Inter-Domain Routing (CIDR) In IPv6 this is the only acceptable form to denote network or routing prefixes

In classful networking in IPv4, prior to the introduction of CIDR, the network prefix could be directly obtained from the IP address, based on its highest order bit sequence. This determined the class (A, B, C) of the address and therefore the network mask. Since the introduction of CIDR, however, assignment of an IP address to a network interface requires two parameters, the address and its network mask. 

In IPv4, on-link determination for an IP address is given simply by the address and netmask configuration, as the address cannot be disassociated from the on-link prefix. For IPv6, however, on-link determination is different in detail and requires the Neighbor Discovery Protocol (NDP). IPv6 address assignment to an interface carries no requirement of a matching on-link prefix and vice versa, with the exception of link-local addresses. 

While subnetting may improve network performance in an organizational network, it increases routing complexity, since each locally connected subnet must be represented by a separate entry in the routing tables of each connected router. However, by careful design of the network, routes to collections of more distant subnets within the branches of a tree-hierarchy can be aggregated by single routes.Variable-length subnet masking (VLSM) functionality in commercial routers made the introduction of CIDR seamless across the Internet and in enterprise networks.

Address Resolution Protocol.

Resolution Protocol (ARP) is a telecommunications protocol used for resolution of network layer addresses into link layer addresses, a critical function in multiple-access networks. ARP is used to convert an IP address to a physical address such as an Ethernet address

The Address Resolution Protocol uses a simple message format that contains one address resolution request or response. The size of the ARP message depends on the upper layer and lower layer address sizes, which are given by the type of networking protocol (usually IPv4) in use and the type of  hardware or virtual link layer that the upper layer protocol is running on. The message header specifies these types, as well as the size of addresses of each. The message header is completed with the operation code for request (1) and reply (2). The payload of the packet consists of four addresses, the hardware and protocol address of the sender and receiver hosts.

 The principal packet structure of ARP packets is shown in the following table which illustrates the case of IPv4 networks running on Ethernet. In this scenario, the packet has 48-bit fields for the sender hardware address (SHA) and target hardware address (THA), and 32-bit fields for the corresponding sender and target protocol addresses (SPA and TPA). Thus, the ARP packet size in this case is 28 bytes. The EtherType for ARP is 0x0806

Hardware type (HTYPE) This field specifies the network protocol type. Example: Ethernet is 1. Protocol type (PTYPE) This field specifies the internetwork protocol for which the ARP request is intended. For IPv4, this has the value 0x0800. The permitted PTYPE values share a numbering space with those for EtherType.[3][4][5]

 Hardware length (HLEN) Length (in octets) of a hardware address. Ethernet addresses size is 6. Protocol length (PLEN) Length (in octets) of addresses used in the upper layer protocol. (The upper layer protocol specified in PTYPE.) IPv4 address size is 4. 

Operation Specifies the operation that the sender is performing: 1 for request, 2 for reply.

 Sender hardware address (SHA) media address of the sender. Sender protocol address (SPA) internetwork address of the sender.

 Target hardware address (THA) media address of the intended receiver. This field is ignored in requests. Target protocol address (TPA) internetwork address of the intended receiver.

ARP protocol parameter values have been standardized and are maintained by the Internet Assigned Numbers Authority (IANA).

structure of an IP header.

The fields in the IP header and their descriptions are

 Version - 

A  4-bit field that identifies the IP version being used. The current version is 4, and this version is referred to as IPv4.

 Length -

 A 4-bit field containing the length of the IP header in 32-bit increments. The minimum length of an IP header is 20 bytes, or five 32-bit increments. The maximum length of an IP header is 24 bytes, or six 32-bit increments. Therefore, the header length field should contain either 5 or 6.

 Type of Service (ToS) - 

The 8-bit ToS uses 3 bits for IP Precedence, 4 bits for ToS with the last bit not being used. The 4-bit ToS field, although defined, has never been used. 

 IP Precedence -

 A 3-bit field used to identify the level of service a packet receives in the network.

 Differentiated Services Code Point (DSCP) -

 A 6-bit field used to identify the level of service a packet receives in the network. DSCP is a 3-bit expansion of IP precedence with the elimination of the ToS bits.

  Total Length - 

Specifies the length of the IP packet that includes the IP header and the user data. The length field is 2 bytes, so the maximum size of an IP packet is 216 – 1 or 65,535 bytes.

  Identifier, Flags, and Fragment Offset - 

As an IP packet moves through the Internet, it might need to cross a route that cannot handle the size of the packet. The packet will be divided, or fragmented, into smaller packets and reassembled later. These fields are used to fragment and reassemble packets. 

 Time to Live (TTL) - 

It is possible for an IP packet to roam aimlessly around the Internet. If there is a routing problem or a routing loop, then you don't want packets to be forwarded forever. A routing loop is when a packet is continually routed through the same routers over and over. The TTL field is initially set to a number and decremented by every router that is passed through. When TTL reaches 0 the packet is discarded.

  Protocol - 

In the layered protocol model, the layer that determines which application the data is from or which application the data is for is indicated using the Protocol field. This field does not identify the application, but identifies a protocol that sits above the IP layer that is used for application identification. 

Compare circuit switching and packet switching

Circuit switching:

Circuit switching is used in public telephone networks and is the basis for private networks built on leased-lines. Circuit switching was developed to handle voice traffic but also digital data (although inefficient) With circuit switching a dedicated path is established between two stations for communication Switching and transmission resources within the network are reserved for the exclusive use of the circuit for the duration of the connection The connection is transparent: once it is established, it appears to attached devices as if there were a direct connection Dedicated communication path between two stations Path is a connected sequence of links between network nodes Communication via circuit switching involves three phases:

— Circuit Establishment

— Data Transfer

— Circuit Disconnect Connection path must be established before data transmission begins Nodes must have switching capacity and channel capacity to establish connection

Packet switching:

 Packet switching was designed to provide a more efficient facility than circuit-switching for bursty data traffic With packet switching, a station transmits data in small blocks, called packets Each packet contains some portion of the user data plus control info needed for proper functioning of the network

A key element of packet-switching networks is whether the internal operation is datagram or virtual circuit (VC).

— With internal VCs, a route is defined between two endpoints and all packets for that VC follow the same route

— With internal diagrams, each packet is treated independently, and packets intended for the same destination may follow different routes Examples of packet switching networks are X.25, Frame Relay, ATM and IP.

Subnetting - two Marks

1. What is virtual circuit? 

In computer networks, a virtual circuit (VC), synonymous with virtual connection and communication service that is delivered by means of packet mode communication. After a connection or virtual circuit is established between two nodes or application processes, a bit stream may be delivered between the nodes; a virtual circuit protocol allows higher level protocols to avoid dealing with the division of data into segments, packets, or frames. Virtual circuit communication resembles circuit switching, since both are connection oriented.

2. What is a datagram?

 A datagram is a basic transfer unit associated with a packet-switched network in which the delivery, arrival time, and order of arrival are not guaranteed by the network service. A datagram has the following characteristics: Data is transmitted from source to destination without guarantee of delivery Data is frequently divided into smaller pieces and transmitted without a defined route or guaranteed order of delivery

3. What is the use of TTL packet in IP header? 

The time-to-live (TTL) is the number of hops that a packet is permitted to travel before being discarded by a router. Originally TTL was set to a specific number of seconds that the packet would be allowed to live. The TTL is set in an eight binary digit field in the packet header by the sending host and is used to prevent packets from endlessly circulating on the Internet or other network. When forwarding an IP packet, routers are required to decrease the TTL by at least one. If a packet's TTL field reached zero, the router detecting it discards the packet and sends an ICMP (Internet control message protocol) message back to the originating host.

4. What is DHCP? 

DHCP - Dynamic Host Configuration Protocol DHCP is a network protocol that enables a server to automatically assign an IP address to a computer from a defined range of IP addresses configured for a given network so that it can communicate on that network using the Internet Protocol (IP). The protocol is implemented in a client-server model, in which DHCP clients request configuration data, such as an IP address, a default route, and one or more DNS server addresses from a DHCP server.

5. What are salient features of IPv6?

Major Features of IPv6: New Packet Format and Header Expanded Addressing (Large address space) Address Autoconfiguration and Neighbor Discovery Header Format Simplification Improved Support for IP Header Options Multicasting Built in Integrated Internet Protocol Security (IPSec)

Link Level Flow Control

Flow control is a technique that a transmitting entity does not conquer a receiving entity with data. Two fundamental mechanisms are acknowledgement and timeouts.

Ø  After getting each frame the receiver will send ACK to sender.

Ø  If the sender does not receive ACK up to reasonable amount of time then it retransmit the original frame waiting for reasonable amount of time is called timeout.

The two flow control mechanisms are

Ø  Stop and wait Flow Control

Ø  Sliding Window Flow Control

Stop and Wait Algorithm

Ø  After transmitting one frame, the sender waits for an                  acknowledgment before transmitting the next frame.

Ø  If the acknowledgment does not arrive after a certain period of time, the sender times out and retransmit the original frame.

            a) The ACK is received before

                  the timer expires    

                                    

      

 b) The original frame is lost

                        c) The ACK  is lost

d)The timeout fires too soon

Fig: illustrates four different scenarios that result from this basic algorithm. The sending side is represented on the left, the receiving side is depicted on the right, and time flows from top to bottom.

Ø  In Fig (a) ACK is received before the timer expires, (b) and (c) show the situation in which the original frame and the ACK, respectively, are lost, and (d) shows the situation in which the timeout fires too soon..

Ø  Suppose the sender sends a frame and the receiver acknowledges it, but the acknowledgment is either lost or delayed in arriving. This situation is in (c) and (d). In both cases, the sender times out and retransmit the original frame, but the receiver will think that it is the next frame, since it correctly received and acknowledged the first frame.

Ø  This makes the receiver to receive the duplicate copies. To avoid this two sequence numbers (0 and 1) must be used alternatively.

Ø  The main drawback of the stop-and-wait algorithm is that it allows the sender have only one outstanding frame on the link at a time.

Error Detection and Correction

Now imagine the received data has 7th bit changed from 1 to 0.

Single-bit error

The receiver takes the transmission and recalculates four new data using the same set of bits used by the sender plus the relevant parity (r) bit for each set.

Error detection

Ø  Then it assembles the new parity values into a binary number in order of r position (r8,r4,r2,r1).

Ø  This step gives us the binary number 0111(7 in decimal) which is the precise location of the bit in error.

Ø  Once the bit is identified, the receiver can reverse its value and correct the error.

Hamming Distance

     One of the central concepts in coding for error control is the idea of the Hamming distance.

Ø  The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits. The Hamming distance between two words x and y is d(x, y).

Ø  The Hamming distance can be found by applying the XOR operation on the two words and count the number of 1’s in the result.

Ø  In a set of words, the minimum Hamming distance is the smallest Hamming distance between all possible pairs. We use dmin to define the minimum Hamming distance in a coding scheme. 

Error Correction

Error Correction can be handled in two ways

1.     When an error is discovered, the receiver can have the sender to retransmit the entire data unit.

2.     A receiver can use an error correcting code, which automatically correct certain errors.

Error correcting codes are more sophisticated than error-detection codes and require more redundancy bits.

In single bit error detection only two states are sufficient.

1) error

2) no error

Two states are not enough to detect an error but not to correct it.

Redundancy Bits

Ø  To calculate the number of redundancy bit(r) required to correct a given number of data bits (m), we must find a relationship between m and r.

Ø  Add m bits of data with r bits. The length of the resulting code is m+r.

Data and Redundancy bits

Ø  If the total number of bits are m+r, then r must be able to indicate at least m+r+1 different states. r bits can indicate 2^r different states. Therefore, 2^r must be equal to or greater than m+r+1

2^r >=m+r+1

Ø  For example if the value of m is 7 the smallest r value that can satisfy this equation is 4.

 Relationship between data and redundancy bits

Number of Data Bits (m)	Number of redundancy Bits(r)	Total bits (m+r)
1	2	3
2	3	5
3	3	6
4	3	7
5	4	9
6	4	10
7	4	11

Hamming Code

R.W. Hamming provides a practical solution for the error correction.

Positioning the Redundancy Bits

For example, a seven-bit ASCII code requires four redundancy bits that can be added to the end of the data or intersperse with the original data bits. These redundancy bits are placed in positions 1, 2, 4 and 8. We refer these bits as r1, r2, r3 and r4

Position of redundancy bits in Hamming code

The combination used to calculate each of the four r values for a seven-bit data sequence are as follows

Ø  The r1 bit is calculated using all bits positions whose binary representation include a 1 in the rightmost position

Ø  r2 is calculated using all bit position with a 1 in the second position and so on

                    r1: bits 1,3,5,7,9,11

                    r2: bits 2, 3, 6, 7, 10, 11

                    r3: bits 4, 5, 6, 7

                    r4: bits 8, 9, 10, 11

Redundancy bits calculation

Calculating the r values

Ø  Place each bit of the original character in its appropriate position in the 11-bit unit.

Ø  Calculate the even parities for the various bit combination.

Ø  The parity value for each combination is the value of the corresponding r bit.

For example,

Ø  The value of r1 is calculated to provide even parity for a combination of bits 3,5,7,9 and 11.

Ø  The value of r2 is calculated to provide even parity with bits 3, 6, 7, 10 and 11.

Ø  The value of r3 is calculated to provide even parity with bits 4,5,6 and 7.

Ø  The value of r4 is calculated to provide even parity with bits 8,9,10 and 11.