Chapter III

Network Layer
2 Contents

 Introduction
 Internet protocol and IP addressing
 Address mapping, error reporting and Group Management Protocols
 Routing algorithms
 Asynchronous Transfer Mode (ATM) (Example for WAN Protocol)
3
4
 Introduction
5

 It is the lowest layer that deals with end-to-end packet (i.e. Network layer data unit) transmission.
 The first duty of the network layer is packetizing: encapsulating the payload in a network-layer packet at the
source and decapsulating the payload from the network-layer packet at the destination.
 Forwarding:- involves the transfer of a packet from an incoming link to an outgoing link within a single router.
 Routing:- involves all of a network’s routers, whose collective interactions via routing protocols (algorithms)
determine the paths that packets take on their trips from source to destination node.
6 Introduction cont….
 Connection setup:
 Connection-oriented communication (virtual circuit network) and
 Connectionless communication (datagram network)
 Store-and-Forward Packet Switching: A host with a packet to send transmits it to the nearest
router. The packet is stored there until it has fully arrived and the link has finished its
processing by verifying the checksum.
 Then forwarded to the next router along the path until it reaches the destination host, where it
is delivered. This mechanism is store-and-forward packet switching.
 Security: network layer provide a security for a connectionless service, for this purpose we
need to have another virtual level (IPsec) that changes the connectionless service to a
connection-oriented service.
7 Introduction cont….
 Services Provided to the Transport Layer:
 The services provided to the transport layer by the network layer can be carefully designed by considering the following transport layer
requirements in mind:
1.The services should be independent of the router technology.
2. The transport layer should be shielded from the number, type, and topology of the routers present.
3. The network addresses made available to the transport layer should use a uniform numbering plan, even across LANs and WANs.
 The network layer should provide connection oriented or connectionless service to transport layer.
 Connectionless and Connection-oriented
8
Communication
 Comparison of Datagram and Virtual-Circuit
9
Networks
Issue Datagram network Virtual-circuit network
Circuit setup Not needed Required
Addressing Each packet contains the full source and destination Each packet contains a short VC number
address
State information Routers do not hold state information about Each VC requires router table space per connection
connections
Routing Each packet is routed independently Route chosen when VC is set up; all packets follow it.
Effect of router None, except for packets lost during the crash All VCs that passed through the failed router are terminated
failures
Quality of service Difficult Easy if enough resources can be allocated in advance for each VC
Congestion control Difficult Easy if enough resources can be allocated in advance for each VC
10 Network-Layer Performance Measures
 The performance of a network can be measured in terms of delay, throughput, and packet loss (sometimes congestion control can
also be consider to improve the performance).
 The delays in a network can be divided into four types: transmission delay, propagation delay, processing delay, and queuing delay.
 Throughput is the number of bits passing through the point in a second, which is actually the transmission rate of data at that point.
 Another issue that severely affects the performance of communication is the number of packets lost during transmission.
 Introduction cont….
11
Router
 Router cont….
12
 Two main functions:
 Run routing algorithms/protocols (e.g., RIP, OSPF, IGRP and others).
 Forwarding datagrams from incoming to outgoing links
 Input ports
13  An input port performs the following key functions.
 It performs the physical layer function of terminating an incoming physical link at a router.
 An input port also performs link-layer functions needed to interoperate with the link layer at the other side of the incoming
link, and
 The lookup function is also performed at the input port. It is here that the forwarding table is consulted to determine the router
output port to which an arriving packet will be forwarded via the switching fabric.
 Control packets (for example, packets carrying routing protocol information) are forwarded from an input port to the routing
processor.
 Switching fabric
14 It is the heart of the router, it can be used to forward data from incoming port to outgoing port. Switching fabric can be
implemented in the following ways: Switching via memory, Switching via bus and Switching via interconnection
network (Crossbar).
15 Output ports
 An output port stores packets received from the switching fabric and transmits these packets
on the outgoing link by performing the necessary link-layer and physical-layer functions.
 When a link is bidirectional, an output port will typically be paired with the input port for
that link on the same line card (a printed circuit board containing one or more input ports,
which is connected to the switching fabric).
 Scheduling discipline chooses among queued datagrams for transmission by considering the
issues like:
 Ordering (First Come First Served), Quality of Service (QoS), fairness (protecting monopoly of
resources).
16 Routing Processor

 The routing processor:

 Executes the routing protocols (which we’ll study in the next classes and demonstrated in
the laboratory sessions),
 Maintains routing tables (by sharing routing table information among routers) and
attached link state information (dependent on the routing algorithm used), and
 Computes the forwarding table for the router
 It also performs the network management functions.
17 Internet protocol and IP addressing
 IP is part of the TCP/IP suite and is the most widely used internetworking protocol.
 As with any protocol standard, IP is specified in two parts:
 The interface with a higher layer (TCP/UDP), specifying the services that IP provides
 The actual protocol format and mechanisms
 IP basic characteristics:
 Connectionless - No connection is established before sending data packets.
 Best Effort (unreliable) - No overhead is used to guarantee packet delivery.
 Media Independent - Operates independently of the medium carrying the data.
 IP Header
18
 IPv4 Addressing
21
 IP address: it is a 32-bit identifier for host and router interfaces (both physical and logical interfaces have an ip
address).
 Interface is a boundary between the host and the physical link in computer networking.
 An IP address is technically associated with an interface, rather than with the host or router containing that
interface.
 These addresses are typically written in so-called dotted-decimal notation, in which each byte of the address is
written in its decimal form and is separated by a period (dot) from other bytes in the address.
Example:
 These addresses cannot be chosen in a willy-nilly manner, however. A portion of an interface’s IP address will
be determined by the subnet to which it is connected.
22 IPv4 Addressing cont…
 IPv4 Addressing cont….
23
 Network Classes: the address is coded to allow a variable allocation of bits to specify network and host. This encoding provides
flexibility in assigning addresses to hosts and allows a mix of network sizes on an internet.
 The three principal network classes are best suited to the following conditions:
 Class A: Few networks, each with many hosts
 Class B: Medium number of networks, each with a medium number of hosts
 Class C: Many networks, each with a few hosts
 IPv4 Addressing cont…..
24
 The Internet’s address assignment strategy is known as Classless Interdomain Routing (CIDR).
 CIDR generalizes the notion of subnet addressing. As with subnet addressing, the 32-bit IP address is divided into two parts and
again has the dotted-decimal form a.b.c.d/x (x is a network prefix).
 The x most significant bits of an address of the form a.b.c.d/x constitute the network portion of the IP address.
 The number of bits used in host portion determines the number of hosts that we can have within the network.
 Types of Addresses in IPv4 Network
 Network address ‐ The address by which we refer to the network
 Broadcast address ‐ A special address used to send data to all hosts in the network
 Host addresses ‐ The addresses assigned to the end devices (including router interfaces) in the network
 Subnet and Network Prefixes (Subnet
25 Masking)
 Subnetting is the process of splitting the larger network into a number of smaller networks.
 Within the subnetted network, the local routers must route on the basis of an extended network number consisting of the network
portion of the IP address and the subnet number.
 Because of Subnetting we get the following advantages:
 Network traffic was reduced
 Network performance become optimized
 Network management become simple
 Network supports large geographic area
 The prefix length (x in the previous slide) is the number of bits in the address that gives us the network portion.
 Subnet cont…
26
Example
27 Subnet cont…
How to Create Subnets
 To create a subnet answer the following questions:
 How many subnets does the chosen subnet mask produced? It can be calculated using 2 n-dp,
where n is the given network prefix and dp is the default prefix for the given class (i.e. class A, B
or C) when IP address is a Classful IP or dp is the network prefix given from ISP.
 How many valid hosts per subnet are available? It can be calculated using 2 32-n-2.
 What are the valid subnets addresses?
 What’s the broadcast address of each subnets?
 What are the valid hosts in each subnet?
28 Subnet cont….
Example 1. consider the following class C Ip-address: 192.168.1.0/25 (255.255.255.128)
192.168.1.0 = Network address
255.255.255.128 = Subnet mask (i.e. 11111111.11111111.11111111.10000000)
 How many subnets? Since 128 is 1 bit exceeded from the default 24 bits on (10000000), the
answer would be 225-24=21=2.
 How many hosts per subnet? We have 7 (32-25) host bits off (10000000), so the equation would
be 27-2 = 126 hosts.
 What are the valid subnets? 256-128 = 128. Remember, we’ll start at zero and count in our
block size, so our subnets are 0, 128.
29 Subnet cont…..
Example 1. cont……
 What is the broadcast address for each subnet? The number right before the next subnet address equals the
broadcast address. For the zero subnet 127 and for 128 subnet 255 are a broadcast addresses.
 What are the valid hosts? These are the numbers between the subnet and broadcast address.

Subnet One Subnet Two

Subnet 0 128
First host 1 129
Last host 126 254
Broadcast 127 255
30 Subnet cont….

Example 2: 168.22.0.0/20 (255.255.240.0) class B network

Example 3: 42.0.0.0/10 (255.192.0.0) class A network
Example 4: 172.26.0.0/23 (255.255.254.0) in a classless Ip-address with /19 prefix.
Example 5: 192.168.64.0/27 (255.255.255.224) in a classless IP-address with /22 prefix.
 Subnet cont…..
31
Variable Length Subnet Masks (VLSM)
32 Reserved IPv4 Address Ranges
 Experimental Addresses: it ranges from 240.0.0.0 to 255.255.255.254. Currently, these addresses are listed as reserved for future use.
 Multicast Addresses: it ranges 224.0.0.0 to 239.255.255.255. It is also subdivided into two types of addresses: reserved link local
addresses and globally scoped addresses.
 The IPv4 multicast addresses 224.0.0.0 to 224.0.0.255 are reserved link local addresses. These addresses are to be used for
multicast groups on a local network. Packets to these destinations are always transmitted with a time ‐to ‐live (TTL) value of 1.
 The globally scoped addresses are 224.0.1.0 to 238.255.255.255. They may be used to multicast data across the Internet. For
example, 224.0.1.1 has been reserved for Network Time Protocol (NTP) to synchronize the time ‐of ‐day clocks of network
devices.
33 Reserved IPv4 Address Range cont….
 Private Addresses: the address blocks belongs to this category are:
 10.0.0.0 to 10.255.255.255 (10.0.0.0 /8)
 172.16.0.0 to 172.31.255.255 (172.16.0.0 /12)
 192.168.0.0 to 192.168.255.255 (192.168.0.0 /16)
 Default Route: it is used as a "catch all" route when a more specific route is not available
(0.0.0.0/8).
 Broadcast Address (255.255.255.255/32)
34 Reserved IPv4 Address Range cont
 Loopback (127.0.0.1/8) : the loopback is a special address that hosts use to direct traffic to themselves.
 Link‐Local Addresses : the address block 169.254.0.0 to 169.254.255.255 (169.254.0.0 /16) are designated as link ‐local addresses
(private DHCP address range). These addresses can be automatically assigned to the local host by the operating system in
environments where no IP configuration is available.
NOTE: When the device get ip-address either statically or using a DHCP server link local address is automatically replaced by this new
address.
 TEST‐NET Addresses : the address block 192.0.2.0 to 192.0.2.255 (192.0.2.0 /24) is set aside for teaching and learning purposes.
These addresses can be used in documentation and network examples. However, network devices will accept these addresses in their
configurations.
 IPv6: Structure and Address Space
35

 The IP (IPv4) has been the foundation of the Internet and virtually all multivendor private
internetworks.
 This protocol is reaching the end of its useful life and a new protocol, known as IPv6 (IP version
6), has been defined to ultimately replace IP.
 The driving motivation for the adoption of a new version of IP was the limitation imposed by
the 32-bit address field in IPv4.
 With a 32-bit address field, it is possible in principle to assign 232different addresses, which is
over 4 billion possible addresses.
36 IPv6 cont……
 Reasons for the inadequacy of 32-bit addresses include the following:
 The two-level structure of the IP address (network number, host number) is convenient but
wasteful of the address space.
 Networks are multiplying rapidly.
 Growth of TCP/IP usage into new areas will result in a rapid growth in the demand for
unique IP addresses.
Examples: Internet of Things (IoT), TCP/IP to interconnect electronic point-of-sale terminals,
sensor networks, cable television receivers and other new technologies require IP addresses.
 Typically, a single IP address is assigned to each host. A more flexible arrangement is to allow
multiple IP addresses per host. This, of course, increases the demand for IP addresses.
 IPv6 cont……
37
 IPv6 includes the following enhancements over IPv4:
 Expanded address space: IPv6 uses 128-bit addresses.
 Improved option mechanism: IPv6 options are placed in separate optional headers that are located between the IPv6 header and the
transport-layer header. It also makes it easier to add additional options.
 Address auto-configuration (dynamic assignment)
 Increased addressing flexibility: IPv6 includes the concept of an anycast address in addition to the existing casting mechanisms in
IPv4 (i.e. Unicast, Multicast and Broadcast).
 Support for resource allocation: IPv6 enables the labeling of packets belonging to a particular traffic flow for which the sender
requests special handling. This aids in the support of specialized traffic such as real-time video.
 IPv6 Header
38

 The following fields are defined in IPv6:

 Version: this 4-bit field identifies the IP version number. IPv6 carries a value of 6 in this field.
 Traffic class: this 8-bit field is similar in spirit to the TOS field we saw in IPv4.
 Flow label: this 20-bit field is used to identify a flow (the datagram that needs special treatments due to
different reasons) of datagrams.
39 IPv6 Header cont……
 Payload length (16 bits): the number of bytes in the IPv6 datagram following the fixed-length datagram header.
 Next header: transport protocol to which the contents of this datagram will be delivered.
 Hop limit: the total number of routers in transmission. If the count reaches zero, the datagram is discarded.
 Source and destination addresses
 Data
 Several fields appearing in the IPv4 datagram are no longer present in the IPv6 datagram:
 Fragmentation/Reassembly: IPv6 does not allow for fragmentation and reassembly at intermediate routers.
If an IPv6 datagram received by a router is too large to be forwarded over the outgoing link, the router
simply drops the datagram and sends a “Packet Too Big” ICMP error message back to the sender.
 Header checksum
 Options
 IPv6 Addresses
40
 IPv6 addresses are 128 bits in length. Addresses are assigned to individual interfaces on nodes, not to the nodes
themselves.
 IPv6 allows three types of addresses:
 Unicast: An identifier for a single interface.
 Anycast: An identifier for a set of interfaces (typically belonging to different nodes). A packet sent to an
anycast address is delivered to one of the interfaces identified by that address (the “nearest” one, according to
the routing protocols’ measure of distance).
 Multicast: An identifier for a set of interfaces.
 IPv6 Addresses cont.….
41
 IPv6 addresses are represented by treating the 128-bit address as a sequence of 8 16-bit numbers, and representing this in the form of
eight hexadecimal numbers divided by colons, for example:
2001:0DB8:0055:0000:CD23:0000:0000:0205
 One to three zeroes that appear as the leading digits in any colon-delimited hexadecimal grouping may be dropped
(2001:0DB8:55:0:CD23:0:0:0205)
 A group of all zeroes, or consecutive groups of all zeroes, can be substituted by a double colon, but this may only be done once in an
address. Example: 2001:0DB8:55::CD23:0:0:0205 or 2001:0DB8:55:0:CD23::0205
Structure of IPv6
ipv6-address/prefix-length
 prefix-length is a decimal value specifying how many of the leftmost contiguous bits of the address comprise the prefix. Example:
2001:0DB8:55:0:CD23::0205/48 or ::/64 or ABC::B:0:1234/80
 Internet Control Message Protocol (ICMP)
42
 ICMP provides a means for transferring messages from routers and other hosts to a host. In essence, ICMP provides feedback about
problems in the communication environment.
Examples: of its use are when a datagram cannot reach its destination, when the router does not have the buffering capacity to forward a
datagram.
 In most cases, an ICMP message is sent in response to a datagram, either by a router along the datagram’s path or by the intended
destination host.
 Although ICMP is, in effect, at the same level as IP in the TCP/IP architecture, it is a user of IP.
 An ICMP message is constructed and then passed down to IP, which encapsulates the message with an IP header and then transmits
the resulting datagram in the usual fashion.
 ICMP cont….
43

 An ICMP message starts with a 64-bit header consisting of the following:

 Type (8 bits): Specifies the type of ICMP message.
 Code (8 bits): Used to specify parameters of the message that can be encoded in one or a few bits.
 Checksum (16 bits): Checksum of the entire ICMP message.
 Parameters (32 bits): Used to specify more lengthy parameters.
 ICMP cont….
44  ICMP error report kinds:
 The destination unreachable message covers a number of contingencies.
 A router will return a time exceeded message if the lifetime of the datagram expires.
 A syntactic or semantic error in an IP header will cause a parameter problem message.
 The echo and echo reply messages (pinging and replaying the ping message)provide a mechanism for testing that communication is possible between entities.
45 ICMP cont.…..
 The source quench message provides a rudimentary form of flow control. Either a router or a destination host may send this
message to a source host, requesting that it reduce the rate at which it is sending traffic to the internet destination.
 A router sends a redirect message to a host on a directly connected router to advise the host of a better route to a particular
destination.
 The timestamp and timestamp reply messages provide a mechanism for sampling the delay characteristics of the internet.
 The address mask request and address mask reply messages are useful in an environment that includes subnets. The address mask
request and reply messages allow a host to learn the address mask for the LAN to which it connects.
 ICMPv6
46  ICMPv6 is used by IPv6 nodes to report errors encountered in processing packets, and to
perform other internet-layer functions, such as diagnostics (ICMPv6 "ping"). ICMPv6 is an
integral part of IPv6 and MUST be fully implemented by every IPv6 node.
 ICMPv6 messages are grouped into two classes: error messages and informational messages.

ICMPv6 error messages ICMPv6 informational messages:

1 Destination Unreachable 128 Echo Request
2 Packet Too Big 129 Echo Reply
3 Time Exceeded
4 Parameter Problem
 Address Mapping
48

 Logical address (IP address): it is a network address uniquely identify networks in the wide area
network.
 Physical address: it is a MAC (Medium Access Control) address, which provides a physical address
for a host port attached to the LAN.
 To deliver an IP datagram to a destination host, a mapping must be made from the IP address to the
subnetwork (MAC) address for that last hop.
 If a datagram traverses one or more routers between source and destination hosts, then the mapping
must be done in the final router, which is attached to the same subnetwork as the destination host.
 If a datagram is sent from one host to another on the same subnetwork, then the source host must do
the mapping.
 Address Mapping cont….
49
 For this purpose, a number of approaches are possible, it include:
 Each system can maintain a local table of IP addresses and matching subnetwork addresses for possible
correspondents.
 A centralized directory can be maintained on each subnetwork that contains the IP-subnet address
mappings.
 An address resolution protocol can be used.
 Address Resolution Protocol (ARP)
50  ARP allows dynamic distribution of the information needed to build tables to translate an IP address A into a 48-bit Ethernet address; the protocol
can be used for any broadcast network. ARP exploits the broadcast property of a LAN.
 ARP works as follows:
1. Each system on the LAN maintains a table of known IP-subnetwork address mappings.
2. When a subnetwork address is needed for an IP address, and the mapping is not found in the system’s table, the system uses ARP directly on top
of the LAN protocol (e.g., IEEE 802) to broadcast a request. The broadcast message contains the IP address for which a subnetwork address is
needed.
3. Other hosts on the subnetwork listen for ARP messages and reply when a match occurs. The reply includes both the IP and subnetwork addresses
of the requested and replying host.
4. The original request includes the requesting host’s IP address and subnetwork address. Any interested host can copy this information into its local
table, avoiding the need for later ARP messages.
5. The ARP message can also be used simply to broadcast a host’s IP address and subnetwork address, for the benefit of others on the subnetwork.
 Internet Group Management Protocol (IGMP)
51  IGMP interaction is limited to a host and its attached router, another protocol is required to coordinate the multicast
routers throughout the Internet, so that multicast datagrams are routed to their final destinations. This latter
functionality is accomplished by network-layer multicast routing algorithms. Network-layer multicast in the
Internet thus consists of two complementary components: IGMP and multicast routing protocols.
 IGMP has only three message types. IGMP messages are encapsulated within an IP datagram, with an IP
protocol number of 2.
 The membership_query message is sent by a router to all hosts on an attached interface to determine the set
of all multicast groups that have been joined by the hosts on that interface.
 membership_report messages can be used by the host to replay the router message or joins a multicast group
without waiting for a membership_query message.
 The final type of IGMP message is the leave_group message (this message is optional).
 How does a router detect the host leaves the group? The router infers that a host is no longer in the multicast
group if it no longer responds to a membership_query message with the given group address.
Example:
52
Network Address Translation (NAT)
 NAT cont….
53
 The basic idea behind NAT is for the ISP to assign each home or business a single (few) public IP address(es) for Internet traffic.
 Within the customer network, every computer gets a unique IP address, which is used for routing in the intranet traffic. However, just before a
packet exits the customer network and goes to the ISP, an address translation from the unique internal IP address to the shared public IP address
takes place.
 This translation makes use of three ranges of IP addresses that have been declared as private. The only rule is that no packets containing these
addresses may appear on the Internet itself.
 If all datagrams arriving at the NAT router from the WAN have the same destination IP address, then how does the router know the internal host to
which it should forward a given datagram?
 The router uses a NAT translation table, and to include port numbers as well as IP addresses in the table entries.
54 NAT cont….
 NAT has enjoyed widespread deployment in recent years. But it has some limitations:
 First port numbers are meant to be used for addressing processes, not for addressing hosts.
 Second routers are supposed to process packets only up to layer 3.
 Third the NAT protocol violates the so-called end-to-end argument; that is, hosts should be talking directly with each other,
without interfering nodes modifying IP addresses and port numbers.
 Fourth we should use IPv6 to solve the shortage of IP addresses, rather than recklessly patching up the problem with a stopgap
solution like NAT.
 Fifth it interferes with P2P applications, including P2P file-sharing applications and P2P Voice-over-IP applications.
 Routing Algorithm
55
 It is that part of the network layer software responsible for deciding which output line an incoming
packet should be transmitted on.
 If the network uses datagrams internally, this decision must be made a new path for every arriving
data packet.
 If the network uses virtual circuits internally, routing decisions are made only when a new virtual
circuit (sometimes called session) is being set up.
 A host is attached directly to one router, the default router for the host. We refer to the default
router of the source host as the source router and the default router of the destination host as the
destination router.
 The purpose of a routing algorithm is then simple (but technically it is difficult due to different
reasons): given a set of routers, with links connecting the routers, a routing algorithm finds a “good”
path from source router to destination router. Typically, a good path is one that has the least cost.
56 Routing Algorithm cont….
 The design of routing algorithm may have the following properties into consideration:
correctness, simplicity, robustness, stability, fairness, and efficiency.
 Routing algorithms can be grouped into two major classes: non-adaptive and adaptive.
 Non-adaptive (static) algorithms do not base their routing decisions on any measurements or
estimates of the current topology and traffic. Instead, the choice of the route to use to get from I to
J is computed in advance, offline, and downloaded to the routers when the network is booted.
 Adaptive (dynamic) algorithms, change their routing decisions to reflect changes in the topology,
and sometimes changes in the traffic as well. These dynamic routing algorithms differ in where
they get their information, when they change the routes , and what metric is used for optimization.
 Others classify routing algorithms into: global or decentralized, link-state or distance-vector and
load sensitive or load-insensitive.
 Routing Algorithm cont….
57
The Optimality Principle
 It states that if router J is on the optimal path from router I to router K, then the optimal path from J to K
also falls along the same route.
 To see this, call the part of the route from I to J r1 and the rest of the route r2.
 As a direct consequence of the optimality principle, we can see that the set of optimal routes from all
sources to a given destination form a tree rooted at the destination. Such a tree is called a sink tree and is
illustrated in the next slide.
58 Shortest Path Algorithm
 The idea is to build a graph of the network, with each node of the graph representing a
router and each edge of the graph representing a communication line, or link.
 To choose a route between a given pair of routers, the algorithm just finds the shortest path
between them on the graph.
 The concept of a shortest path deserves some explanation.
 One way of measuring path length is the number of hops.
 Another metric is the geographic distance in kilometers.
59 Flooding
 In this algorithm every incoming packet is sent out on every outgoing line except the one it arrived on.
 Flooding obviously generates vast numbers of duplicate packets, in fact, an infinite number unless some
measures are taken to damp the process.
 One such measure is to have a hop counter contained in the header of each packet that is decremented at each
hop, with the packet being discarded when the counter reaches zero.
 A better technique for damming the flood is to have routers keep track of which packets have been flooded, to
avoid sending them out a second time.
 It is effective for broadcasting information, tremendously robust and requires little in the way of setup.
60 Flooding cont….
61 Distance Vector Routing
 A distance vector routing algorithm operates by having each router maintain a table (i.e., a vector)
giving the best known distance to each destination and which link to use to get there.
 These tables are updated by exchanging information with the neighbors.
 In distance vector routing, each router maintains a routing table indexed by, and containing one entry
for each router in the network.
 This entry has two parts:
 The preferred outgoing line to use for that destination and
 An estimate of the distance to that destination.
 The commonly used distance vector routing protocols are: RIP (Routing Information Protocol), BGP
(Border Gateway Protocol), EIGRP (Enhanced Interior Gateway Routing Protocol) and the original
ARPAnet.
 Distance Vector Routing cont….
62
63 Link State Routing
 The idea behind link state routing can be stated as five parts. Each router must do the following
things to make it work:
1. Discover its neighbors and learn their network addresses.
2. Set the distance or cost metric to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to and receive packets from all other routers.
5. Compute the shortest path to every other router.
 In effect, the complete topology is distributed to every router.
70 Hierarchical Routing
 As networks grow in size, the router routing tables grow proportionally. It affects router
memory, CPU time and bandwidth to send status reports to others.
 At a certain point, it is no longer feasible for every router to have an entry for every other
router, so the routing will have to be done hierarchically.
 When hierarchical routing is used, the routers are divided regions.
 Each router knows all the details about how to route packets to destinations within its own
region but knows nothing about other regions.
 When a single network becomes very large, an interesting question is ‘‘how many levels should
the hierarchy have?’’
 Asynchronous Transfer Mode (ATM)
71  Asynchronous transfer mode is a switching and multiplexing technology that employs small, fixed-length packets called cells.
 A fixed-size packet makes switching and multiplexing efficient and a small cell size was chosen to support delay-intolerant interactive voice
service.
 ATM is a connection-oriented packet-switching technology that was designed to provide the performance of a circuit-switching network
and the flexibility and efficiency of a packet-switching network.
 ATM was intended to provide a unified networking standard for both circuit-switched and packet-switched traffic, and to support data,
voice, and video with appropriate QoS mechanisms.
 ATM is used by ISP to implement wide area networks. Many DSL implementations use ATM over the basic DSL hardware for
multiplexing and switching, and ATM is used as a backbone network technology in numerous IP networks and portions of the Internet.
 ATM cont…..
72
ATM Logical Connections
 Virtual channel connections (VCCs) is analogous to a virtual circuit; it is the basic unit of switching in an ATM
network.
 A VCC is set up between two end users through the network, and a variable-rate, full-duplex flow of fixed-size
cells is exchanged over the connection. VCCs are also used for user–network exchange (control signaling) and
network–network exchange (network management and routing).
 A virtual path connection (VPC) is a bundle of VCCs that have the same endpoints. Thus, all of the cells
flowing over all of the VCCs in a single VPC are switched together.
 ATM cont….
73
 Advantages of using a virtual paths:
 Simplified network architecture
 Increased network performance and reliability
 Reduced processing and short connection setup time
 Enhanced network services
 Virtual Path/Virtual Channel Characteristics ITU-T recommend the following as characteristics:
 Quality of service (QoS)
 Switched and semipermanent virtual channel connections
 Cell sequence integrity
 Traffic parameter negotiation and usage monitoring
 Virtual channel identifier restriction within a VPC (unique for Virtual Path)
 ATM Cell Format
74
 ATM Cell Format cont…
75
 The Generic Flow Control (GFC): it can be used for control of cell flow only at the local user–network interface.
The field could be used to assist the customer in controlling the flow of traffic for different qualities of service. In
any case, the GFC mechanism is used to alleviate short-term overload conditions in the network.
 The virtual path identifier (VPI) constitutes a routing field for the network. In the network cell allows support for
an expanded number of VPCs internal to the network, to include those supporting subscribers and those required
for network management. The virtual channel identifier (VCI) is used for routing to and from the end user.
 The Payload Type (PT) field indicates the type of information in the information field (the detail codes found in the
next slide).
 The Cell Loss Priority (CLP) bit is used to provide guidance to the network in the event of congestion. A value of 0
indicates a cell of relatively higher priority, which should not be discarded unless no other alternative is available. A
value of 1 indicates that this cell is subject to discard within the network.
 The Header Error Control (HEC) field is an 8-bit error code that can be used to correct single-bit errors in the
header and to detect double-bit errors.
76 ATM Cell Format cont…..
 Next Chapter II
Data Link Layer
77