Advanced Computer Network
ITec5101 1
Chapter 2- IP Routing
IP Addressing
Forwarding and Routing
BGP and Adaptive Routing
Congestion Control
ITec5101 2
IP Addressing
• IP address contains sufficient information to uniquely identify a
network and a specific computer on the network
• IP address is an address used to uniquely identify a device on an
IP network
• Types of IP Addresses
• Private & Public
• Special IP Addresses
• Types of IP address Assignment
• Static & Dynamic
ITec5101 3
IPv4 Vs IPv6
• Ipv6 has an expanded address space, from 32 bits to 128 bits.
• IPv6 uses hexadecimal notation instead of dotted-decimal notation
(as in IPv4).
• IPv6 addresses are globally unique due to the extended address space,
eliminating the need for NAT.
• IPv6 offers address autoconfiguration, providing for dynamic
assignment of IP addresses.
• IPv6 has security capabilities built in, including authentication and
privacy via IPSec.
• IPv6 supports site multi-homing.
• IPv4 and IPv6 use different routing protocols.
• IPv6 provides for Anycast addressing but does not support broadcast
addressing
ITec5101 4
Routing
• Primary function of internet is to accept packets from a source
station and deliver them to a destination station
• To do so, the best route or routes must be determined (Routing
function must be performed)
• The selection of a route is based on some performance criteria
such as
• Hop count,
• Delay and
• Bandwidth/Data rate
• A routing policy may enforce certain types of traffic be restricted to
certain routes for security concerns
• A route with minimum least cost will be selected as best route.
Cost is associated with each link.
ITec5101 5
Cont.
• For example: the shortest path from N1 to N6 is 1-3-6 (Cost 5+5=10)
but the least cost path is 1-4-5-6(1+1+2=4)
• the cost could be inversely related to the data rate (that is, the
higher the data rate on a link, the lower the assigned cost of the link)
or the current link delay
ITec5101 6
Packet Forwarding
• The key function of any router is to accept incoming packets and
forward them.
• To make this happen a router maintains forwarding tables
• The table shows, for each destination, the identity of the next
node on the router
• Who creates the forwarding tables?
• Each router may be responsible for discovering the appropriate routes.
• Network control center may design routes for all routers, maintaining a
central forwarding table and provide each router with individual
forwarding tables relevant only to that router
• It is not necessary to store the complete route for each possible pair of
nodes. Rather, it is sufficient to know, for each pair of nodes, the identity of
the first node on the route.
ITec5101 7
Cont.
• Example: A network with 6 nodes (routers)
ITec5101 8
Cont.
• Additional information is often used to determine the
forwarding decision, such as the source address, packet flow
identifier, or security level of the packet:
• Failure: remove a route if the link fails.
• Congestion: When a particular portion of the network is heavily
congested, it is desirable to route packets around rather than through the
area of congestion.
• Topology change: The insertion of new links or nodes affects routing.
• For adaptive routing, information about the state of the
network must be exchanged among the nodes or between the
nodes and a central controller.
ITec5101 9
Cont.
Routing Protocols
• Routers are responsible
• For receiving and forwarding packets .
• Avoid portions of the network that have failed and congested.
• To make these decisions the routers exchange routing
information using a routing protocol.
• Autonomous Systems
• It is a set of routers and networks managed by a single organization.
• It consists of a group of routers exchanging information via a common
routing protocol.
• Except in times of failure, an AS is connected (in a graph-theoretic sense);
i.e., there is a path between any pair of nodes.
ITec5101 10
Cont.
Based on the concepts of AS routing protocols are categorized into
two as:
• Interior Routing Protocol (IRP) or IGP
• Passes routing information between routers within AS
• It includes protocols like RIP, IGRP, EIGRP, OSPF, IS-IS
• Exterior Routing Protocol (ERP) or EGP
• used to pass routing information between routers in different
autonomous systems
• the routers in one AS need at least a minimal level of information
concerning networks outside the system that can be reached
• BGP is an example of ERP
ITec5101 11
Cont.
• How routers in different ASs exchange information?
• a router in the first system need only determine the target AS and devise
a route to get into that target system.
• Once the packet enters the target AS, the
routers within that system can cooperate to
deliver the packet; the ERP is not concerned
with, and does not know about, the details
of the route followed within the target AS
ITec5101 12
Cont.
• Elements of a router
• I/O ports: on which packets arrive and depart
• Input / Output Buffer: can be fixed –size for
each port or can be pool of memory available
for buffering activities. (FIFO is used during
packet forwarding)
• Forwarding Tables (FT):
• Routing Policies: influence construction of
forwarding tables
• Routing Control: includes execution of routing
protocols, adaptive maintenance of the routing
tables, and supervising congestion control policies
ITec5101 13
Border Gateway Protocol(BGP)
• Is used to connect and find routes to and from autonomous systems
• TCP port 179 to propagate and update the routing tables to its neighbors
• BGP routers must establish a TCP connection to exchange information.
The connection between these routers is known as BGP Peers or
Neighbors
• It is also referred to as an Advanced Distance Vector Protocol.
• Routers that advertise their prefixes or routes are known as BGP
speakers
• Types of BGPs
• internal Border Gateway Protocol (iBGP) –routers that belongs to the same AS
and use BGP to exchange routing information. (AD-200)
• external Border Gateway Protocol (eBGP)-routers that belongs to the different
AS and use BGP to exchange routing information (AD-20)
ITec5101 14
Cont.
• There are four types of messages that are used to exchange routing
information between BGP peers. These are:
• Open Message:
• Sent as soon as a TCP session is established between BGP Peers
• Used to identify the AS of routers, to match the protocol parameters and
decide the protocol timers
• Update Message:
• Used to exchange the topology information between BGP speakers (only one
route status change is advertised)
• Notification Message:
• Sent out when error occur during BGP session. Good for troubleshooting
• Keepalive Message:
• Used to confirm the status of session between BGP peers- (KAT – 60sec and
HDT-180sec)
ITec5101 15
Cont.
• Basic BGP Configuration
• Specify AS number
Router(Config)#router bgp ASNumber
• Specify BGP Neighbor
Router(Config-router)#neighbor nexthop-address Remote-as RemoteASNumber
• Advertise routes
Router(Config-router)#network NetworkAddress mask SubnetMask
ITec5101 16
Adaptive Routing
• It is also known as dynamic routing
• Routing decisions change as conditions on the network
change
• Failure
• Congestion
• New node or link
• Requires info about network
• Decisions are more complex
• Tradeoff between quality of network info and overhead
• Protocols such as RIP, IGRP, OSPF, IS-IS etc support this feature
ITec5101 17
Congestion Control
• Congestion
• is a situation in Communication Networks in which too many packets are
present in a part of the subnet, performance degrades
• Congestion occurs
• when the load on the network is greater than the capacity of the network
• Causes of Congestion
• The input traffic rate exceeds the capacity of the output lines
• The routers are too slow to perform bookkeeping tasks (queuing buffers,
updating tables, etc.).
• The routers' buffer is too limited.
• The processors are slow
• Have slow links
ITec5101 18
Cont.
• Congestion Control Techniques
• Open Loop – Prevent congestion
• Closed Loop – Remove Congestion
• Open Loop Congestion Control
• Retransmission Policy
• The sender retransmits a packet, if it feels that the packet it has sent is lost or
corrupted.
• Implement good retransmission policy and timers to optimize efficiency and prevent
the congestion.
• Window Policy
• Selective Reject method is preferred over Go-back-n window as in Go-back-n method
worse the congestion by retransmitting the packet when timer expires
• Selective reject method sends only the specific lost or damaged packets.
ITec5101 19
Cont.
• Acknowledgement Policy
• Acknowledgement by itself may worse the congestion.
• To reduce the congestion the receiver may send an acknowledgement only if it has a
packet to be sent or when a timer expires or only N packets at a time.
• Discarding Policy
• A router may discard less sensitive packets when congestion is likely to happen.
• Such a discarding policy may prevent congestion and at the same time may not harm the
integrity of the transmission.
• Admission Policy
• Switches in a flow first check the resource requirement of a flow before admitting it to
the network.
• A router can deny establishing a virtual circuit connection if there is congestion in the
network or if there is a possibility of future congestion.
•.
ITec5101 20
Cont.
• Closed Loop Congestion Control
• Backpressure
• node-to-node congestion control that starts with a node and propagates,
in the opposite direction of data flow.
• can be applied only to virtual circuit networks. In such virtual circuit each
node knows the upstream node from which a data flow is coming.
• As shown in fig node 3 is congested and it stops receiving packets and informs
its upstream node 2 to slow down. Node 2 in turns may be congested and
informs node 1 to slow down. Now node 1 may create congestion and informs
the source node to slow down. In this way the congestion is alleviated. Thus,
the pressure on node 3 is moved backward to the source to remove the
congestion
ITec5101 21
Cont.
• Choke Packet
• In this method, congested router or node sends a special type of
packet called choke packet to the source to inform it about the
congestion.
• In choke packet method, congested node sends a warning
directly to the source station i.e. the intermediate nodes
through which the packet has traveled are not warned.
ITec5101 22
Cont.
• Implicit Signaling
• The source guesses that there is congestion somewhere in the network
when it does not receive any acknowledgment and slows down. Used by
TCP
• Explicit Signaling
• the congested nodes explicitly send a signal to the source or destination to
inform about the congestion. (forward or backward direction)
• It is not like choke packet method because here the signal is included in the
packets that carry data .
• In backward signaling, a bit warns the source about the congestion and informs
the source to slow.
• In forward signaling, a bit warns the destination about the congestion. The
receiver in this case uses policies such as slowing down the acknowledgements to
remove the congestion.
ITec5101 23
Cont.
• Congestion Control Algorithms
• Leaky Bucket Algorithm
• It controls the amount and the rate of the traffic sent to the
network i.e. bursty traffic into fixed rate traffic by averaging
the data rate.
• The rate at which the water is poured into the bucket is not
fixed and can vary but it leaks from the bucket at a constant
rate. Thus (as long as water is present in bucket), the rate at
which the water leaks does not depend on the rate at
which the water is input to the bucket.
• Also, when the bucket is full, any additional water that
enters into the bucket spills over the sides and is
lost.(weakness)
ITec5101 24
Cont.
ITec5101 25
Cont.
• The same concept can be applied to packets in
the network. Consider that data is coming from
the source at variable speeds. Suppose that a
source sends data at 12 Mbps for 4 seconds.
Then there is no data for 3 seconds. The source
again transmits data at a rate of 10 Mbps for 2
seconds. Thus, in a time span of 9 seconds, 68 Mb
data has been transmitted. If a leaky bucket
algorithm is used, the data flow will be 8 Mbps
for 9 seconds. Thus constant flow is maintained.
• (traffic shaping or policing)
ITec5101 26
Cont.
• Token bucket Algorithm
• The leaky bucket algorithm cannot deal with bursty data and does
not consider the idle time of the host.
• To overcome these problems, a token bucket algorithm is used.
• In this algorithm, a token(s) are generated at every clock tick. For a
packet to be transmitted, system must remove token(s) from the
bucket.
• Thus, a token bucket algorithm allows idle hosts to accumulate
credit for the future in the form of tokens.
• For example, if a system generates 100 tokens in one clock tick and
the host is idle for 100 ticks. The bucket will contain 10,000 tokens.
Now, if the host wants to send bursty data, it can consume all 10,000
tokens at once for sending 10,000 cells or bytes.
• Thus a host can send bursty data as long as bucket is not empty.
ITec5101 27
Cont.
• Weakness- Dependent on the token
ITec5101 28
Further Reading
• Automatic configuration of IPv6
• Basic Router Configuration Commands
• Implement Interior Gateway Protocols
ITec5101 29