Routing(Packet switching)
A system(either a multihomed host computer or a router) that switches a packet
is called
a router, although the older term IP gateway is also used.
An incoming IP datagram that specifies a destination IP address other than one of the local host's IP address(es), is treated as a normal outgoing IP datagram. This outgoing IP datagram is subject to the IP routing algorithm of the local host/router, which selects the next hop for thedatagram (the next host to send it to). This new destination can be located on any of the physical networks to which the intermediate host is attached.
Characteristics of Routing
Routing algorithms should be designed with the following factors in consideration:
-Correctness
-Simplicity
-Robustness
-Stability
-Fairness
-Optimality
-Efficiency
Ultimate goal is "Shortest Path Routing"( = Least-Cost Routing )
Meaning of Shortest Path?(Least-Cost?)
To give a meaning to "Shortest Path", we need to define a set of parameters to be used in measuring a path = called "Metrics"(Routing Metrics)
List of commonly used metrics
Path Length=hop count
Reliability
Delay
Bandwidth
Load
Communication Cost
Using some combinations of the above metrics, routers calculate
Link weight = A function of metrics= f ( , , , ...)
After Link weights are calculated, we can calculate the shortest path to a destination
Some considerations about routers:
* They do not know about all IP networks except Internet backbone routers
* They allow local sites autonomy in establishing and modifying routes. In other
words, a local site is manageable by the local administrators for the choice
of routing protocols and the configurations
* A routing entry error in one of the routers can introduce inconsistencies,
thereby making part of the network unreachable.
* Some error reporting mechansim should be implemented by routers via the Internet
Control Message Protocol (ICMP). They should be able to report the following
errors back to the source host:
-Unknown IP destination network by an ICMP Destination Unreachablemessage.
-Redirection of traffic to more suitable routers by sending ICMP Redirect messages.
-Congestion problems (too many incoming datagrams for the available buffer space)
by an ICMP Source Quench message.
-The Time-to-Live field of an IP datagram has reached zero. This is reported
with an ICMP Time Exceeded message.
-Also, the following base ICMP operations and messages should be supported:
– Parameter problem
– Address mask
– Time stamp
– Information request/reply
– Echo request/reply
Direct Delivery vs Indirect Delivery
Static vs Dynamic routing
Static routing---fixed routes--used only in special cases such as Point-to-point
links, ...
Dynamic routing--routing decision made for each IP Datagram--routing table updated
dynamically
Routing Tables
Typical entries in a routing table:
Examples:
a) The following is the routing table on a Unix workstation(132.241.4.14)
###The entries for 63.x.y.z & 64.x.y.z are Host-speicfic routes--these
are DSL connections###
###132.241.4.14 is the IP address of itself###
###132.241.4.1 is the Default Gateway###
(b) The following is the routing table on a Windows NT workstation(132.241.3.49)
F:\>netstat -rn
Route Table
--------------------------------------------------------------
Interface List
0x1 ........................... MS TCP Loopback interface
0x2 ...00 10 4b 2f ef 44 ...... 3Com 3C90x Ethernet Adapter
--------------------------------------------------------------
--------------------------------------------------------------
Active Routes:
Network Destination Netmask Gateway
Interface Metric
-----------------------------------------------------------------------------
0.0.0.0
0.0.0.0 132.241.3.1
132.241.3.49 1
127.0.0.0 255.0.0.0
127.0.0.1
127.0.0.1 1
132.241.3.0 255.255.255.0
132.241.3.49 132.241.3.49 1
132.241.3.49 255.255.255.255
127.0.0.1 127.0.0.1 1
132.241.255.255 255.255.255.255
132.241.3.49 132.241.3.49 1
224.0.0.0 224.0.0.0
132.241.3.49
132.241.3.49 1
255.255.255.255 255.255.255.255
132.241.3.49 132.241.3.49 1
Default Gateway: 132.241.3.1
--------------------------------------------------------------------
Persistent Routes:
None
F:\>
###Loopback address--when you do "ping 127.0.0.1"###
###Network Destination 0.0.0.0 =This host on this network###
###132.241.255.255 = Direct Broadcast address=to send a message to every host
on a local network--132.241.0.0 network--routers ususally will not pass this###
###255.255.255.255=Limited Broadcast address=to every host on the same subnet--routers
will not pass this one###
###Any destination that is not listed in the table will be passed to Default
Gateway###
Routing Algorithms & Protocols
Read from http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/routing.htm
Algorithm Types
Static Versus Dynamic
Single-Path Versus Multipath
Flat Versus Hierarchical
Host-Intelligent Versus Router-Intelligent
Intradomain Versus Interdomain
Link State Versus Distance Vector
Algorithms can be classified by
-Where algorithms are run(Centrally(old) or distributed)
-How information is shared between routers(Next neighbors only, Every routers
in a region, …)
-How often the information is shared(Every X seconds, Whenever status changes,
…)
From: http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/routing.htm
"Confusion about the terms routed protocol and routing protocol
is common. Routed protocols are protocols that are routed over an internetwork.
Examples of such protocols are the Internet Protocol (IP), DECnet, AppleTalk,
Novell NetWare, OSI, Banyan VINES, and Xerox Network System (XNS). Routing protocols,
on the other hand, are protocols that implement routing algorithms. Put simply,
routing protocols direct protocols through an internetwork. Examples of these
protocols include Interior Gateway Routing Protocol (IGRP), Enhanced Interior
Gateway Routing Protocol (Enhanced IGRP), Open Shortest Path First (OSPF), Exterior
Gateway Protocol (EGP), Border Gateway Protocol (BGP), Intermediate System to
Intermediate System (IS-IS), and Routing Information Protocol (RIP)."
Routing Boundaries
A dynamic routing protocols can be divided into two groups:
* Interior Gateway Protocols(IGP)--Examples of these protocols are RIP(Routing
Information Protocol) & RIPv2, OSPF(Open Shortest Path First)
* Exterior Gateway Protocols(EGP)--Examples of these protcols is BGP-4(Border
Gateway Protocol)
Routing protocols are referred to as Interior or Exterior depending upon whether they are within or between Autonomous Systems.
Autonomous System: A group of networks and routers under the authority of a
single administration.
ISO's terminology
Host(computer) is called "End System(ES)"
A router is called "Intermediate System(IS)
So, ISO say about ES-IS, IS-IS communications
Protocols for routing http://www.cisco.com/univercd/cc/td/doc/product/software/ios103/acscg103/78618.htm
*Between routers in one AS(IGP)--Interior routing--Popular: RIPv2, OSPF, IGRP,
EIGRP
*Between routers in different ASs(EGP)--Exterior routing--Popular:BGP
Interior Routing(within one AS)---Exterior Routing(between AS's) covered
later
Current Routing Algorithms
Two common Routing Algorithms(Both are adaptive(dynamic) algorithms)
(a) "Distance Vector Routing"--Each router shares its knowledge(distance
to destination networks) about the entire network(in an AS) with its neighbors-Example:
RIPv2
***EVERYTHING to NEIGHBORS ONLY***
(b) "Link State Routing"-Each router shares its knowledge about its
links to the neighbors(link state) with every routers in the area.-Example:
OSPF
***LINK STATES to EVERYBODY***
(a) RIP(Rourting Information Protocol)
- An IGP(Interior Gateway Protocol) developd by XEROX(XNS-Xerox Network Systems)
- RIP widely adopted in Internet with 1982 4BSD UNIX even before the standard--RFC
1058(1988)-later revised with RFC1388(RIP V.2)
- Popular in small networks
- Also popular for PC networking
- AppleTalk's routing = version of RIP
- Novell, 3COM, Banyan
- RIP is a Distance Vector Routing---Hop Count is used as the metric--How many
hops(each router is a hop) to the destination network?
Operation
- Each router initializes with a distance vector table containing zero for
itself, one for directly attached networks, and infinity for every other destination.
- Each router periodically (typically every 30 seconds) transmits its distance
vector table to each of its neighbors. A router sends it's knowledge about the
entire Autonomous system(=it's entire routing table(Netid, Hop Count entries))
to its neighboring routers(only to its neighbors). It can also transmit the
table when a link first comes up or when the table changes.
- Each router saves the most recent table it receives from each neighbor and
uses the information to calculate its own distance vector table. (=Each router
maintains the distance from itself to every known destination network in a "distance
vector table")
- Hop count is used as the metric--distance=how many hops
Example:
RIP Updating Algorithm
Receive: A RIP message from a neighbor
1. Add one hop to the hop count for each advertised destination
2. Repeat the following steps for each advertised destination:
1. If(destination not in the routing table),
then Add the advertised information to the table
2. Else
1. If(next-hop field
is the same as the sender's address), then Replace entry in the table with the
advertised one
2. Else
1.
If(advertised hop count smaller than one in the table), then Add it to the routing
table
2.
Else do nothing
3. Return
Requests and Responses
Request: Sent by a router that has just come up or by a router that has entries
that are timed-out, request can ask specific entries or all entries
Response: A response can be either
"solicited" --Sent as a response to a Request
or
"unsolicited"--A RIP router broadcasts its routing table to all adjacent
routers at every 30 seconds
- Eventually, all routers will learn about entire network
- When new routing info is received from a neighbor, the routing table is updated(routing
table is recalculated to reflect any changes)
-RIP is a distributed routing
-RIP uses Hop Count as the distance vector which is not an accurate metric
RIP Routing Table
-------------------------------------------------------------------------
Destination Hop Count Next Hop
Other Info (timers, flags)
-------------------------------------------------------------------------
Timers:t1, t2, t3
t1: Periodic timer--Advertising interval=30 sec.--Every 30 seconds, send routing
table to neighbors
t2: Expiration timer--RIP ages routes--when info about a route does not come
within 180 seconds, the route is marked with Hop Count of 16(meaning invalid
route)
t3: Garbage collection timer--when a route becomes invalid(when t2 expires),
it(the route) is still advertised(with Hop count=16), if a route stays invalid
for more than 120 seconds, then the route is purged from the table
Advantages of RIP-----Simplicity=low overhead
Disadvantages:
(a) The limit to the size of an internetwork imposed by maximum hop count(15).
(b) Slow Convergence problem
Changes in routes propagates slowly.
For example, suppose there is a change in local LAN to which a router is connected.
The router updates itself immediately. Then it will advertise the change in
30 seconds, so the next neighboring routers will know, then they will advertise
within 30 seconds, ……
Assuming a remote router is n hops away, then it could take 30*n seconds. This
is why RIP limits the maximum hop count to 15. RIP is designed for small networks
(c) Instability problem(Also called "count to infinity problem")
Counting to infinity occurs when a network becomes unreachable, but erroneous
routes to that network persist because of the time for the distance vector tables
to converge.
Suppose:
Now, Net1 goes down, then RouterA enters (Net1 16 - ***hop count 16 means infinitely
remote***) immediately but after that routerA receives an advertisement from
RouterB(which says that it can reach Net1 by 2 hops), then routerA updates its
route entry with (Net1 3 B)
Now when routerA advertises, routerB changes its entry to (Net1 4 A)
The above process will repeat until entries on both routers reach 16 hops.
Now both A & B learns that Net1 is not reachable and propagate the information
to neighboring routers, so it will take long time for all the routers learn
the fact.
Remedies to Instability problem
Triggered Update--When there is no change, then send the routing table every
30 seconds but if there is any change then send the table immediately.
Another solution: "Split Horizons"--A router will not send out routing info on an interface(link) that it learned from that interface. In other words, RouterA says "I learned this route from RouterB, so it does not make sense to send this route info to RouterB".
A variation to "Split Horizons"---called "Poison Reverse Update"--Instead of not advertising routes to the source, routes are advertised back to the source with a hop count of 16(which will make the source router ignore the route).
(d) RIPv1 does not support Variable Length Subnet Mask(VLSM) or CIDR
RIPv2 is a replacement for RIPv1 that can be used on small to medium size networks
and supports VLSM & CIDR
RIPng(RIP next generation)--designed for IPv6