How to Calculate Minimum Cost using Routing algorithm

IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
How to Calculate Minimum Cost using
Routing algorithm
Renu Dangi
Santosh Vishwakarma
rd
M. Tech III Semester Student
GGCT, Jabalpur,
RGPV University, Bhopal (India)
ABSTRACT
In this paper, we analyze the packet delivery reliability of
routing protocols for loss and delay sensitive applications. Since
a typical flooding-based route discovery used in routing
protocols. Open shortest path first (OSPF) had been recognized
as a de facto standard for inter-domain Internet protocol (IP)
routing. Its hierarchical architecture and the introducing of area
border router (ABR) had been proved to be an effective solution
to the scalability problem. However, manual selection of ABR
may fail to accommodate the dynamic change in the network
load and therefore lead to sub-optimal solution. In the article, a
new scheme is proposed for the dynamic appointment of ABR
for OSPF. Based on observed traffic demands and knowledge
on link capacities, the proposed scheme will dynamically switch
to a new ABR from an old one to avoid incipient link
congestion and accompanying performance degradation. In
response to traffic change, the proposed approach will locate an
adequate ABR for the new traffic pattern and then direct traffics
to the new ABR. System performance, in terms of link
utilization, throughput, and delay, is expected to benefit from
the proposed scheme, as demonstrated in the simulation results.
HOD, Information Technology
GGCT, Jabalpur,
RGPV University, Bhopal (India)
3.
4.
Static and Dynamic tables.
Unicast Routing and Multicast Routing.
2. INTRA & EXTRA DOMAIN
ROUTING
1.
2.
3.
4.
5.
Because an internet can be so large, one routing
protocol cannot handle the task of updating routing
tables of all routers [6, 7, 11].
So, an internet is divided into autonomous systems.
An autonomous system (AS) is a group of networks
and routers under the authority of a single
administration.
Intradomain routing. [9,10,12]
a. It is used for the routing inside an
autonomous system.
Interdomain routing
a. It is used for the routing between
autonomous systems.
Keywords
Routers, Autonomous System, Link Utilization using Routing
Algorithm
1. INTRODUCTION
Routers are fundamental devices for IP (Internet protocol)
networks [3, 8]. An internet is a combination of networks
connected by routers. A
metric is a cost assigned for passing through a network. The
total metric of a particular route is equal to the sum of the
metrics of networks that comprise the route. The router chooses
the route with the shortest (smallest) metric.RIP (Routing
Information Protocol): treating each network equals. The cost of
passing through each network is the same. So if a packet passes
through 10 networks to reach the destination, the total cost is
hop counts.
1.
2.
OSPF (Open Shortest Path First)[1,2]
a. Allowing the administrator to assign a cost
for passing through a network based on the
type of service required.
b. A route through a network can have
different costs (metrics).
BGP (Border Router Protocol) [4,5]
a.
Criterion is the policy, which can be set by
the administrator.
b. Policy defines what paths should be
chosen.
3. DISTANCE VECTOR ROUTING
1.
2.
In distance vector routing, the least cost route between
any two nodes is the route with minimum distance. In
this protocol each node maintains a vector (table) of
minimum distances to every node.
Distance Vector Routing
6
IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
a.
b.
Each router periodically shares its
knowledge about the entire internet with
neighbors.
The operational principles of this algorithm
i.
Sharing knowledge about the entire
autonomous system.
ii. Sharing only with neighbors.
iii. Sharing at regular intervals (ex,
every 30 seconds).
7
IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
4. RIP
1.
2.
3.
4.
The Routing Information Protocol (RIP) is an
intradomain routing protocol used inside an
autonomous system. It is a very simple protocol based
on distance vector routing.[17]
The destination in a routing table is a network, which
means the first column defines a network address.
A metric in RIP is called a hop count; distance;
defined as the number of links (networks) that have to
be used to reach the destination.
Timers in RIP
a.
Periodic
timer:
controlling
the
advertisements of regular update messages.
b. Expiration timer: governing the validity of a
route.
c.
The garbage collection timer: advertising the
failure of a route.
4.1. RIP Version 2
1.
2.
5.
Expiration timer
a.
b.
c.
6.
In normal situation, the new update for a
route occurs every 30 seconds.
But, if there is a problem on an Internet and
no update is received within the allotted 180
seconds, the route is considered expired and
the hop count of the route is set to 16.
Each router has its own expiration timer.
Garbage Collection Timer
a.
b.
When the information about a route
becomes invalid, the router continues to
advertise the route with a metric value of 16
and the garbage collection timer is set to
120 sec for that route.
When the count reaches zero, the route is
purged from the table.
3.
4.
5.
Designed for overcoming some of the shortcomings
of version 1.
Replaced fields in version 1 that were filled with 0s
for the TCP/IP protocols with some new fields.
It can use classless addressing.
Multicasting
Using the multicast address 224.0.0.9 to
multicast RIP messages only to RIP routers
in the network.
Encapsulation of RIP messages
a. It is encapsulated in UDP user datagram.
b. It is not included a field that indicates the
length of the message.
c. Well-known port assigned to RIP in UDP is
port 520.
5. LINK STATE ROUTING
In link state routing, if each node in the domain has the
entire topology of the domain, the node can use Dijkstra’s
algorithm to build a routing table.
8
IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
Summarizes the information about the
sends it to other areas.
5.
Building Routing Tables:
a. Creation of the states of the links by each node, called
the link state packet or LSP.
b. Dissemination of LSPs to every other router, called
flooding, in an efficient and reliable way.
c. Formation of a shortest path tree for each node.
d. Calculation of a routing table based on the shortest
path tree.
2. Creation of LSP
When there is a change in the topology of the domain
on a periodic basis 60 minutes or 2 hours.
area and
Backbone
i.
All of the areas inside an AS must be
connected to the backbone.
ii.
Serving as a primary area.
iii.
Consisting of backbone routers.
iv.
Back bone routers can be an area border
router.
1.
6.
Metric
i.
OSPF protocol allows the administrator to
assign a cost, called the metric, to each route.
ii. Based on a type of service (minimum delay,
maximum throughput, and so on).
iii. A router can have multiple routing tables, each
based on a different type of service.
7.
Link State Routing
i.
OSPF uses Link State Routing to update the
routing tables in an area.
ii.
Each router shares its knowledge about its
neighborhood with every router in the area.
iii.
Sharing knowledge about the neighborhood.
iv.
Sharing with every other router by flooding.
v.
Sharing when there is a change.
a. cf. Distance Vector Routing: sending the
information at regular intervals regardless of
change.
So, every router can calculate the shortest path
between itself and each network.
8.
Types of Links
In OSPF terminology, a connection is called a
link.
6. OSPF
1.
2.
3.
4.
The Open Shortest Path First (OSPF) protocol is an
intradomain routing protocol based on link state
routing. Its domain is also an autonomous
system.[1,2,18]
Dividing an AS into areas
To handle routing efficiently and in a timely
manner.
Areas
i.
It is a collection of networks, hosts, and
routers in AS.
ii.
AS can be divided into many different areas.
iii.
All networks inside an area must be
connected.
iv.
Routers inside an area flood the area with
routing information.
Area Border Router
9
IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
a.
Point-to-point Link
i. Routers are represented by nodes
and the link is represented by a
bidirectional edge connecting the
nodes.
ii. Each router has only one neighbor at
the other side of the link.
d.
9.
b.
Virtual Link
When the link between two routers is
broken, the administration may create a
virtual link between them using a longer
path.
Graphical Representation
Transient Link
i. It is a network with several
routers attached to transient Link.
ii. In “C”, each router has only one
neighbor, the designated router
(network).
iii. The designated
neighbors.
router
has
five
i.
An internet with 7 networks and 6
routers.
ii. AS
and
its
Graphical
Representation in OSPF.
iii. N1: transient, N2: Stub.
iv. Using square nodes for the routers
and ovals for the networks.
iv. Number of neighbor announcements is
reduced from 20 to 10.
v. There is no metric from the designated
router to any other node.
c.
Stub Link
i. It is a network that is connected to
only one router.
ii. It is a special case of transient
network.
iii. The link is only one-directional,
from the router to the network.
10. Encapsulation of OSPF Packets.
11. Encapsulation
i. OSPF packets are encapsulated in
IP datagram.
ii. These
packets
contain
the
acknowledgment mechanism for
flow and error control.
7. PATH VECTOR ROUTING
1.
2.
3.
It is similar to distance vector routing.
Assuming that there is one node in each AS that acts
as on behalf of the entire AS: Speaker Node.
Speaker node creates a routing table and advertises it
speaker nodes in the neighboring Ass.
10
IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
a.
Advertising the path, not the metric of the
nodes.
8. BGP
1.
Border Gateway Protocol is an interdomain routing
protocol using path vector routing.[13-15]
2. Distance vector routing and link state routing.
a.
Distance vector routing: just considering
the number of hops.
b. Link state routing: requiring each router to
have a huge link state database.
3. Path Vector Routing
a.
Each entry in the routing table contains the
destination network, the next router, and the
path to reach the destination.
b. The path is usually defined as an ordered
list of autonomous systems that a packet
should travel through to reach the
destination.
4. Stub AS [16]
It has only one connection to another AS.
5. Multihomed AS
It has more than one connection to other
AS.
6. Transit AS
It is a multihomed AS that also allows
transient traffic.
Example: national and international ISPs.
7. Path attributes
a.
Well-known attributes.
b. Well-known mandatory: ORIGIN (RIP,
OSPF, and so on), AS-PATH, NEXT_HOP
well-known discretionary.
c.
Optional attributes.
i. Optional transitive: must be passed to the
next router by the router has not
implemented this attribute.
ii. Optional non transitive: must be discarded
if the receiving router has not
implemented this attribute.
8. Open message
To create a neighborhood relationship, a router
running BGP opens a TCP connection with a
neighbor and sends an open message.
9. Update message
a. It is used by a router to withdraw
destinations that have been advertised
previously, announce a route to a new
destination, or both Keepalive message.
b. It exchange keep alive messages regularly
(before their hold time expires) to tell each
other that routers are alive.
10. Notification message
It sent by a router whenever an error condition is
detected or a router wants to close the connection.
9. CONCLUSION
Conventionally, the appointment of Area Border Router in a
stub-area is done manually. This implies that it will be less
flexible, less responsive, and less robust when facing with
possible device failure and traffic changes. As traffic demands
change over time, when the utilization of links connected to the
default ABR approach the edges of congestion, the overall
throughput and routing delay will degrade accordingly. To this
problem, a scheme for the dynamic appointment of ABR is
proposed in this article. The proposed scheme make the
decision on ABR switching based on observed traffic changed.
The system is identified to be in a critical state if the link
utilizations approach a pre-defined threshold a. A system in
critical state can gain performance improvement, in terms of
throughput and routing delay, by switching the default ABR to
a new candidate router. In addition, the mechanism of switching
threshold b had been introduced to accommodate the switching
overhead and to offer good timing for the ABR switching.
Under the framework of OSPF, the proposed scheme can be
easily integrated into existing systems and supposed to bring
about significant improvement in system performance. An
important feature of OSPF is its ability in dealing with the
scalability problem in large size ASs. The operational cost of
OSPF, the number of control messages and the execution time
of the Dijkstra’s algorithm, is proportional to the number of
participated routers in an AS. To limit the operational cost to a
reasonable level and for administrative purposes, OSPF
incorporates the concept of hierarchical routing into large-scale
ASs to resolve the scalability problem Hierarchical architecture
is an effective measure in dealing with complex systems. With
OSPF, an AS is partitioned into nonoverlapped stub areas. Each
stub area is in effect an isolated routing domain. That is, the
propagation of link-state advertisement (LSA) is limited to
within the same stub area. For each stub area, one particular
router is selected from possible candidates and acts as the
default area border router (ABR) for the stub area. Default
ABRs from each stub areas form the so called back bone area,
which is in charge of inter stub area routing.
10. REFERENCES
[1]. A.V. Aho, D. Lee, Hierarchical networks and the LSA Nsquared problem in OSPF routing, in: Proceedings of the
IEEE
Global
Telecommunications
conference
(GLOBECOM-20’00), vol. 1, 2000, pp. 397–404.
[2]. R. Coltun, D. Ferguson, J. Moy, OSPF for IPv6, RFC 2740
(1999).
[3]. S. Deering, R. Hinden, Internet protocol Version 6 (IPv6)
addressing architecture, RFC 3513 (2003).
[4]. N. Feamster, J. Rexford, Network-wide prediction of BGP
routes, IEEE/ACM Transactions on Networking 15 (2007)
253–266.
[5]. E. Fleischman, W. Furmanski, Mobile exterior gateway
protocol: extending IP scalability, in: Proceedings of the
Military Communications Conference (MILCOM-2005),
vol. 4, 2005, and pp. 2055–2061.
[6]. Behrouz A. Forouzan, TCP/IP Protocol Suite, Third
Edition, Tata McGraw-Hill Edition, New Delhi, pp.386394.
[7]. B. Fortz, J. Rexford, M. Thorup, Traffic engineering with
traditional IP routing protocols, IEEE Communications
Magazine 40 (2002) 118–124.
[8]. Wei Kuang Lai , Chen-Da Tsai , Chin-Shiuh Shieh
,Dynamic appointment of ABR for the OSPF routing
protocol, Computer Communications 31 (2008) 3098–
3102, 25 April, 2008.
[9]. R. Malbotra, IP Routing, O’Reilly & Associates, 2002.
[10]. J. Moy, OSPF Version 2, RFC 2328 (1998).
[11]. Y. Ogawa, A. Nakaya, K. Takamura, K. Yamaha, S.
Saitou, K. Iwanaga, T. Koita, Estimating the performance
of a large enterprise network for the updating of routing
11
IJCA Special Issue on “Network Security and Cryptography”
NSC, 2011
information, Proceedings of the IEEE Workshop on IP
Operations and Management (2002) 161–165.
networks, IEEE/ACM Transactions on Networking 13
(2005) 234–247.
[12]. R. Puzmanova, Routing and Switching, Addsion-Wesley,
2002.
[16]. W. Richard Stevens, G. Gabrani, TCP/IP Protocol
Illustrated, Volume1: The Protocol, Pearson Education, pp.
152-153.
[13]. F. Skivee, S. Balon, G. Leduc, A scalable heuristic for
hybrid IGP/MPLS traffic engineering – case study on an
operational network, in: Proceedings of the 14th IEEE
International Conference on Networks, (ICON ’06), 2006,
pp. 1–6.
[14]. B.R. Smith, J.J. Garcia-Luna-Aceves, Efficient security
mechanisms for the border gateway routing protocol,
Computer Communications 21 (1998) 203– 210.
[17]. Y. Wang, S.E. Butner, RIPS: a platform for experimental
real-time sensorybased robot control, IEEE Transactions
on Systems, Man and Cybernetics 19 (1989) 853–860.
[18]. W.V. Wollman, Y. Barsoum, Overview of open shortest
path first, version 2 (OSPF V2) routing in the tactical
environment, in: Proceedings of the Military
Communications Conference, vol. 3, 1995, pp. 5–8.
[15]. A. Sridharan, R. Guerin, C. Diot, Achieving near-optimal
traffic engineering solutions for current OSPF/IS-IS
12