The term routing refers to the process of choosing a path over which we wish to send packets.

Router refers to choosing a certain computer in a certain network . Routing occurs at several levels.

The network itself is responsible for routing packets from the time they enter until they leave.

Such internal routing is completely independent of any outside hosts . Hosts merely see the network as an entity that delivers packets.

First,we will show networks connection protocols.

The ISO took the task of putting a protocol to connect different networks through it.

It was called The ISO-OSI Model (International Standard Organization Open System Interconnection) . This model is based on The Seven Layers concept .

The ISO Seven Layers is a protocol for layers and is organized as shown in fig(1) .

The first layer is Hardware and the rest 6 layers are Software .

Each layer has its own protocol and knows exactly the rules of communication between preceeding and following layers.

It is a physical connection between host computers and network packet . It is used to transfer packets from one host to another by means of wires and cards .

It is responsible of checking that received data is correct by adding aTrailer to the data .

It is considered as the sum of binary data .The other link layer will check Sum and compare it with Trailer . If they are equal it accepts it , else it sends it back .

It carries the transport protocol packets and receives data which may be partitioned.. Then it gives the data destination and source address .

As data bandwidth becomes large (1 Mega bits for example) , we cannot transport it in one time because there will be an error due to noise and electromagnetic waves .

So the transport layer will partition the data to small packets , each having a header holding the packet number to enable it to be in order again at the receiver transport layer .

It is responsible of the management of communication resources used by application .

It is considered as a manager for application task . It performs synchronization of application activities to ensure that both end points work in steps .

For each application type , there is a model for the data types that application uses and that can be carried out on that data .

So it takes the application according to its type and transforms it to its code wether it is ASCII code or IBM code or other .

The user uses this layer to invoke application programs from which he can select anyone.

From previous discussion of the seven layers model , we saw that all 6 layers protocol are considered as software , and only the physical layer is hardware .

After each layer terminates its work , it gives a signal to reset layer for work again .

The Government Agencies have realized the importance of INTERNET technology .

Researhes resulted in what is called “The DARBA Technology” .

DARBA stands for Defense Advanced Projects Research Agency” .

The DARBA Technology includes a set of network standards that specify in details how computers communicate .

Commonly referred to as TCP/IP , it can be used to communicate across any set of interconnected networks .

Now , we will consider the fundamental principle of connectionless delivery and discuss how it is provided by IP , one of two major protocols used in Internet .

The second major layering model the ISO model can be stretched to describe the TCP/IP layering scheme.

0. the TCP/IP protocol software is organized into four conceptual layers that build on a fifth layer of hardware

1. Application layer : at the highest level users invoke application programs that access the internet. An application interacts with the transport level protocol to send or receive data .
2. transport layer : The primary duty of the transport layer is to provide communication from one application program to another. The transport layer may regulated flow of information. Ensuring that data arrives without error and in sequence. The transport software divides the stream of data being transmitted into packets and passes each packet with a destination address to the next level for transmission.

The transport layer must accept data from several user programs. Soit adds additional information to each packet “Header – destination” header to identify which application program sent it destination to identify which application program would received it.

3. Internet layer : It accepts a request to sent a packet from the transport layer along, with an Identification of the machine to which the packet should be sent. The Internet layer also handles incoming data grams, checking their validity, deleting the header, and using the voting algorithm to decide whether the data gram should be processed locally or forwarded. For data grams addressed to the local machine, the internet layer software chooses from among several transport protocols the one that will handle the packet.
4. Network Interface layer : Responsible for accepting IP data grams and transmitting them over a specific network interface may consist of a device driver “When the network is a local area network to which the machine attaches directly” or a complex subsystem that uses it a own data link protocol “When network consists of packet switches that communicate with hosts using HDLC”.

The internet is a universal communication system allows any host to communicate with any other one, hence we have to establish an accepted method to identifying computers for machine langugh we use binary addressing code.

3. the question that we will goring to answer is how to use this addresses in routing?

6.2.1. Classes of internet addresses :

- Each host on the internet is assigned a unique 32 – bit internet address that is used in all communication with that host, this bits share a common prefix.

0. There are three address classes listed a as follows class A, B $ C.

Any class consists of a pair (netid & hostid)

Netid : which identifies the primary classes

Hostid : which identifies the computer it self.

Each address consists of 32 – bit devides in (netid & hostid) as shown in fig (1).

 

 

“The Three primary forms of internet addresses”

6.2.2. Specifying network connections

consider a gate way that attaches to two physical network we have to identify the host’s network connections.

Therefore for any gate way connecting n-networks has n-distinct internet addresses one for each network connection.

3. Refering to some important network address any advantages :
0. one of the most important advantage of the internet addresses is that addresses can refer to networks as well as hosts, By convention the network address has hostid with all leros”
1. another advantage is that includes a broad cost addresses that refers to all hosts on the network.

6.2.3. Refering to addressing disadvantages :

2. the most important disadvantage of the network addresses is that this addresses refer to connections not to hosts, therefore if a host moves from one network to another it must changes it’s internet address.
3. Another disadvantage is that if any class network grows to more than 255 hosts it must have it’s address changed to class B.

This internet address is the base of routing.

 

6.3. INTERNET ARCHITECTURE & PHILOSOPHY:

Internet software is designed around three networking services arranged in a hierarchy as shown in fig (2) .

 

 

 

 

 

 

6.3.1. Connectionless Delivery System :

The most fundamental Internet service consists of an unreliable connectionless packet delivery system . The service is unreliable because delivery is not guaranteed .

The packet may be lost , duplicated or delivered out of order .

The service is connectionless because each packet is treated independently from all other packets .

 

 

 

 

6.3.2. Purpose of Internet Protocol :

The protocol defining the unreliable connectionless delivery mechanism is called “Internet ” or “IP” . IP defines the basic unit of data transfer and includes a set of rules specifying how packets should be processed and how errors should be handled Particularly , IP embodies the idea of unreliable delivery and the associated ideas of packet routing .

 

6.4.THE INTERNET DATAGRAM:

The Internet calls its basic transfer unit an Internet datagram , this datagram is divided into header and data areas , the datagram header contains the source and destination addresses . Figure (3) shows the general form of a datagram.

 

 

 

 

 

 

6.4.1.Data Size &Network (MTU) :

Each packet switching network places a fixed upper bound on the size of data that can be transfered in one physical frame , for example the Ethernet limits trasfers to 1500 byte . We refer to these limits as the network’s maximuim transfer unit or MTU Thus, the large datagram must be divided into small pieces called Fragments .Each Fragment contains a header that duplicates most of the original datagram header except for a few bits that show it is a fragment , the fragments usually travels as a separate datagram all the way to the ultimate dsetination , where they must be reassembled. If any fragment is lost ,the datagram can not be reassembled and it will be discarded without processing .

 

 

 

 

 

6.4.2.Datagram Format :

Now we will look at the fields in more details . Figure (4) shows the arrangment of fields in a datagram :-

 

 

The u-bit version (VERS) specfies the IP protocol version and is used to verify that the sender , receive and gateway in between them agree on the format of the datagram . If standards changes ,hosts will reject datagrams .

The Leugnth field (LEN) -u bits ,gives the datagram header length measured in 32 bit words. The most common header contains 20 byte and has a lenght field equal to 5- without

options.

The Total Length field gives the length of IP datagram measured in bytes including the length of header and data.

6.4.3.Datagram Type of Service :

The 8-bit Type of Service field specifies how the datagram should be handled according to the importance , low delay , high through put and reliability . The type of srevice is a hint to the routing algorithm that helps it choose among various paths to a destination based on its knowledge of hardware technologies available on these paths . The Intrenet can not guarantee the type of srevice requested.

6.4.4.Fragmentation Control :

Three fields in datagram header , IDENT , FLAGES , and FRAGMENT OFFSET, control fragmentation and reassembly of datagram .

FIELD IDENT contains a unique integer that identifies the datagram . As a fragment arrives , the dsetination uses the IDENT FIELD along with the source address to identify the datagram to which the fragment belong s.

The 3 -bit Flags field control fragmentation. The first bit if setting it to 1 specifies that the datagram should not be fragmented . The low order two bits specfies whether this is the last fragment .

Field Fragment Offset spesifies the offset of this fragment in the original datagram.Fragments do not necessarily arrive in order . If one or more fragments is lost ,the entire datagram must be discarded .

6.4.5.Time To Live (TTL) :

The time to live field (time) specifies how long the datagram is allowed to remain in the Intrenet system . Whenever a host injects a datagram into the system ,each gateway along the path from source to destination checks the time and decrement it by one . When the to live reaches zero the datagram must be discarded.

 

6.4.6.Other Datagram Header Field :

1. Field Proto specifies the format and contents of the data by identifying the highlevel protocol type.
2. Field Header Checksum treating the header as a sequance of 16 bit integers adding them together and then the result for purpose of computing the checksum.
3. Field Source IP Address and Destination Address contain the 32 bits Internet address of the datagram’s sender and intended recipient.
4. The field labeled DATA shows the beginning of the data area of the datagram .
5. The last field labeled represents bytes containing zero that may be needed to ensure that the Internet header extends to an exact multiple of 32 bits

6.4.7.Internet Datagram Option :

The OPTIONS field is not required in every datagram and the length of this field varies depending on which option are selected. Each option consists of a single byte option code, single byte length and a set of data bytes for the option .

The routing and time stamp option are the most interesting because they provide a way to control how Internet gateways route datagrams. The record route

option allow the source to create an empty list of IP address and arrange for each gateway that handles the datagram to add its name to the list . The timestamp option contains initially empty list and this list contains the time and data at which a gateway handles the datagram , expressed as milliseconds.

 

6.5.THE ROUTING TABLE :

Destination	Route Mask	Next Hop	Port	Metr	Typ	Src	Age
0.0.0.0	0.0.0.0	172.16.3.65	J3.1	1	REM	MGMT	0
172.16.0.0	255.255.0.0	172.16.3.65	J3.1	1	REM	MGMT	0
172.16.3.0	255.255.255.192	172.16.3.1	J5	0	DIR	LOC	72177
172.16.3.6	255.255.255.192	172.16.3.126	J3.1	0	DIR	LOC	68994
172.16.3.128	255.255.255.192	172.16.3.190	J1	0	DIR	LOC	72184
172.16.3.192	255.255.255.192	172.16.3.254	J1	0	DIR	LOC	72184
172.16.4.0	255.255.255.192	172.16.3.4	J5	115	REM	OSPF	29766
172.16.4.64	255.255.255.192	172.16.3.4	J5	90	REM	OSPF	13662
172.16.4.128	255.255.255.192	172.16.3.4	J5	100	REM	OSPF	29766
172.16.6.64	255.255.255.192	172.16.3.65	J3.1	576	REM	OSPF	17268
172.16.8.0	255.255.255.0	172.16.3.65	J3.1	621	REM	OSPF	29766
172.16.8.0	255.255.255.192	172.16.3.65	J3.1	90	REM	OSPF	68985
172.16.8.64	255.255.255.192	172.16.3.65	J3.1	130	REM	OSPF	13662
172.16.8.64	255.255.255.192	172.16.3.62	J5	720	REM	OSPF	52002
172.16.8.128	255.255.255.192	172.16.3.65	J3.1	75	REM	OSPF	68982
172.16.25.0	255.255.255.192	172.16.3.62	J5	50	REM	OSPF	71289
172.16.25.128	255.255.255.192	172.16.3.62	J5	35	REM	OSPF	71294
172.16.25.192	255.255.255.192	172.16.3.62	J5	35	REM	OSPF	71294

Explanation of different fields :

1. Destination : The IP address of the destination network or host .
2. Route Mask :The mask that defines which bits of the destination field are significant in the route decision .
3. Next Hop : The IP address of a router that is the next to the destination network.
4. Port : The physical port that the TCP/IP packet must be sent out of in order to reach the next hop router.
5. Metric : A value assigned to the route to assist in determining the routing preferences to determine which router is prefer .
6. Type : A value that refers to the type of route : DIR = direct ( the router is directly connected to the destination network) or REM = remote ( the destination is reachable through another router).
7. Source : The routing protocol that caused the route to be created : MGMT = management (static routes), LOC = Local (direct routes), OSPF = open shortest path first ( dynamic route created by OSPF) .
8. Age : The amount of time in seconds since the route was last updated.

When a router receives a packet the destination IP address is examined. If the packet is not destined for the router, i.e., the destination address is not equal to one of the router’s IP interfaces, the packet is queued for forwarding.

1. Assuming that the packet must be forwarded, three possibilities exist
2. The destination address is a unicast address. The address is a Class A,B, or C address and is not a special case broadcast address.
3. The destination address is a broadcast address.
4. The destination address is a multicast address. The address is a Class D address.

If the destination address is a unicast address, the router determines what the IP address is for the next hop router. The time-to-live ( TTL) field is decremented and verified that it is not equal to 0. If TTL equals 0 the packet isn’t sent anymore. The datagram is fragmented if necessary, and the hardware address of tlink layer destination is determined and the link layer header is built for transmission on the physical medium.

If the destination address is broadcast address, the router must determine whether the broadcast is limited broadcast or is a directed broadcast. If it is a limited broadcast (255.255.255.255), the packet cannot be forwarded out to another interface, but it might be used by the router itself. It is queued for local delivery to the router. If the datagram is a directed broadcast, it is treated as a unicast address for forwarding to the network, where it will be broadcast to all stations. That is, the router determines, through examination of the destination’s network, the routing table, the IP address of the next-hop router. The TTL field is decremented and checked whether it is equal to 0 or not, the same steps are continued till the packet is transmitted on the physical medium.

Once a packet has arrived at a router and is determined to be a unicast or a directed broadcast that must be forwarded, it is necessary to determine the interface it should be sent out of and the next-hop router’s IP address. There may not be a next-hop router in all instances. When a packet is destined for a network that is directly defined on one of the router’s interfaces, packet is sent from the router directly to the destination IP address without traversing an additional router (local destination network).

In cases when the IP datagram must be sent to a next-hop router, a procedure is defined to find the most appropriate port and next-hop address. These procedures produce the entire set of route table entries to a subset of routes consisting of zero, one, or more than one route alternatives for the datagram. These procedures are known as pruning rules.

1. Rule 1 - Basic Match : The working set of route entries is equal to the entire route table. For each entry is the route table, the route mask is applied to both the destination IP address of the datagram and the corresponding destination field in the route table. All route entries, except the ones in which the destination route are identical, are removed from the working set of route entries. Default routes are the exception. They are always included in the working set of route entries.

Consider the previous table. Before the Basic Match pruning rule is applied, this routing table is the working set of route entries. Assuming that an IP datagram arrives destined for 172.16.8.66, the working set of route entries after the Basic Match pruning rule is applied as shown in the following table:

1. Rule 2 - longest Match : The working set of route entries is examined to see which entry (entries) has the longest (most specific) route mask. All routes in the working set that have a shorter (more general) route mask are excluded. Even though the default route has a zero-length route mask, the longest match pruning rule applies to it as well. The previous example would be reduced to the working set of route entries, as shown in the following table:

1. Rule 3 - Weak Type of Service : OSPF is an example of routing protocol that can support Type of Service routing. The IP header has a field identified as “Type of Service ( TOS )” that spans the second octet of the header and supports two functions, precedence and Type of Service. The high-order 3 bits of the field are the “precedence” field, and the next 4 bits are the “type of service” flags. These TOS flags can influence how routing decisions are mde for the packet being examined. The flags are :

D - Delay ; T - Throughput ; R - Reliability ; C - Cost.

The three bits that represent the “precedence” field influence the treatment of the packet while it is in queue in a router. Congestion in routers results in a growth of queues and delays. The precedence field permits the router to select certain packets for earlier transmission over other, less time - sensitive packets. Each route in the routing table may have a Type of Service field associated with it. TOS, the TOS flags (bits 3-6 of the TOS field) of the datagram are compared to the TOS field of all candidate routes in the working set. If a match is made, all routes, except those that match, are excluded from the working set. If no match is made, all routes, except the ones that have a Type of Service equal to 0000, excluded from the working set of route entries.

Routers that do not support TOS routing will set the TOS flags in the route table to 0000.

2. Rule 4 - Best Metric : Each route in the working set are route entries is ordered

according to the metric field. The route(s) with the best metric are retained, and the other routes are excluded from the working set of candidate routes. The earlier example will be reduced down to the working set of route entries shown in the following table :

1. Rule 5 - Vendor Policy : In many cases the working set of route entries would have been reduced down to a single candidate route; however, it is possible to end up with a set of candidate routes all with equal metrics. The Vendor Policy pruning rule leaves the choice to the router to how to handle this condition. Possibilities are selection of the route that was less recently used (load splitting), or first in list (exclude others).

After the application of the pruning rules, there should either no routes ion the working set of route entries or one route. If the working set is empty, the packet should be discarded (not sent on the route) and an error should be indicated. Otherwise the packet should be wrapped in a link layer protocol, using the hardware address of the next hop and queued forwarding.

The term routing refers to process of choosing a path to send packets, and router refers to any computer making such a choice. IP routing occurs at a higher level than physical network routing.

We should mention that the Internet is composed of multiple physical networks interconnected by computers called gateway. We can divide routing into two forms:

From one host to another, datagrams are sent using the underlying physical transmission system directly (i.e. the two hosts are exist physically on the same network.)

When we go to another network, the sender pass the datagram to a gateway for delivery.

Transmission of an IP Datagram between two hosts on a single physical network does not involve gateway, the sender encapsulates the Datagram in a physical frame and sends it directly to the destination by maps the destination IP address into a physical address, and uses the network hardware to deliver it by dynamic binding with the Address Resolution Protocol (ARP) protocol.

We assume that each host knows the Internet address of all its network connections, the sender extracts the network portion of the destination Internet address and compares it to the network portion of its own Internet addresses.

The sender must identify a gateway to which the Datagram can be sent, the gateway must then forward the datagram on toward its destination network. Gateways in the Internet form a cooperative, interconnected structure. Datagrams pass from gateway to another until they reach a gateway that can deliver the Datagram directly.

This table contains information about possible destinations addresses. Gateways do not know all details they know the networks interconnections and the receiver network destination.

When the datagram arrives at a gateway, IP software locates the destination Internet address and extracts the network portion from it. The gateway then uses the network id to make routing decisions.

Using destination network addressses instead of destination host addresses make routing efficient and keeps routing tables small. Typically, a routing table contains parameter N, G. where N is a destination Internet network address, and G is the Internet address a gateway to wich to send datagrams destined for network N. All gateways listed in a routing table used by host M must lies on networks to which

M connects directly, making it possible to reach them directly.

The fllowing figure shows an example Internet that consists of 4 networks and 3 gateways. In the figure, the routing table gives the routes that gateway G uses. Because G connects directly to networks 20.0.0.0 and 30.0.0.0, it can reach any host on those networks directly (possibly using ARP to find physical addresses.) Given a datagram destined for a host on network 40.0.0.0 , G routes it to address 30.0.0.7, the address of gateway H. H will then deliver the datagram directly. G can rreach address 30.0.0.7 because it is attached directly to network 30.0.0.0.

(a) An example Internet with 4 networks and 3 gateways.

(b) the routing table for gateway G.

We notice that the size of routing table remains fixed, independent of t he number of hosts in this Internet sample. It only grows when new networks are added. We can summerize the following princples:

All traffic belongs to a given network takes the same path. As a result even when multiple paths exist concurrently. all types of traffic follow the same path without regard to the delay or through put of physical networks.

Second because only the final gateway attempts to communicate with destination host only it learns if the host exists or is operational, because each gateway routs traffic independently traffic traveling from host A to B may follow an entirely different path than traffic travailing from host B back to A.

Another technique used to keep routing table sizes small. The idea is to have the IP routing software first looks in the routing table for the destination network, if no route appears in the table, the routing routines send the datagram to the default next router.

IP routing software allows per-host routes to be specified as a special case. Having per-host routes gives the local network administrator more control over network. It can be used to control access when debugging network connections or routing table problems.

Algorithm:

Route_IP_Datagaram (datagram, routing-table)

{

Extract destination IP address, I_D , from datagram

Check I_D network class A, B or C

Compute IP address of destination network based on which class, I_N ,

If IN matches any direct connected networks address then,

send datagram to destination over that network.

else if I_D appears as host-specific route then,

route datagram as specified in the table

else if I_N appears in routing table then,

route datagram as specified In the table.

else if a default route has been specified then,

route datagram to the default gateway

else declare a routing error to the source IP address.

}

The IP routing algorithm given an IP datagram and routing table, this algorithm selects a next host to which the datagram should be sent. Routing tables always specify a next host which exist on a directly connected network.

1 - Internet working with TCP/IP

( Principles , Protocols and Architecture )

( DOUGLAS Comer )

2 - TCP/IP Addressing

3 - Computer Communications

( ROBERT Cole )

Introduction.......................................................................................................6 - 1

6.1 Protocols For Internet Working.....................................................................6 - 2

6.2 Internet Adresses..........................................................................................6 - 5

6.3 Internet Architecture & Philosophy................................................................6 - 7

6.4 The Internet Datagram..................................................................................6 - 8

6.5 The Routing Table........................................................................................6-11

6.6 Routing Algorithm........................................................................................6-14

References.........................................................................................................6-18