Dijkstra Algorithm
Dijkstra's algorithm, sometimes called the shortest path algorithm or forward search algorithm, is a centralized, static algorithm, although it can be made adaptive by executing it periodically. It also requires that a node executing it has information regarding link costs among the network nodes.
Each node executes Dijkstra's algorithm to determine the cheapest route to each network node. In cases where a route cost is simply the number of intermediate nodes, the cheapest route is also the shortest one. The algorithm is an iterative one, building
a set of nodes, one by one, with each iteration. Each node in the set has the property that the cheapest route to it from the given node is known. (Nodes are of two types:networks and routers; arcs are the connections between a router and a network). Cost is applied only to the arc from router to network and cost of arc from network to router is always zero.
The Dijkstra algorithm follows four steps to discover what is called the shortest path tree for each router.

  INTERNETWORK PROTOCOL (IP)
IP is the transmission mechanism used by the TCP/IP protocols. It is an unreliable and connectionless datagram protocol-a best-effort delivery service. The term best-effort means that IP provides no error checking or tracking. IP assumes the unreliability of the underlying layer and does its best to get a transmission through to its destination, but with no guarantees.
If the reliability is important, IP must be paired with a reliable protocol such as TCP. An example of a more commonly understood best-effort delivery service is the post office. The post office does its best to deliver the mail but does not always succeed. If an unregistered letter is lost, it is up to the sender or the intended recipient to discover the loss and rectify the problem. The post office itself does not keep track of ?very letter and cannot notify a sender of loss or damage. An example of a situation similar to pairing IP with a protocol that contains reliability functions is a self­addressed, stamped postcard included in a letter mailed through the post office. When the letter is delivered, the receiver mails the postcard back to the sender to indicate success. If the sender never receives the postcard, he or she assumes the letter was lost and sends out another copy.
IP transports data in packets called datagrams, each of which is transported separately. Datagrams may travel along different routes and may arrive out of sequence or duplicated. IP does not keep track of the routes and has no facility for recording datagrams once they arrive, because it is a connectionless service. There is no call setup to alert the receiver to an incoming transmission.
  IP Services
The services to be provided across adjacent protocol layers (for example between IP and (TCP) are expressed in terms of primitives and parameters. A primitive specifies the function to be performed, and the parameters are used to pass data and control information. The actual form of a primitive is implementation dependent. IP provides two service primitives at the interface to the next layer. Figure 10.6 shows IP service primitives and parameters. The send primitive is used to request transmission of a data unit. The deliver primitive is used by IP to notify a user of the arrival of a data unit.

Figure 10.6 IP service primitives and parameters.
Note that the identification, don't fragment identifier, and time to live parameters are present in the send primitive but not in the deliver primitive. These three parameters provide instructions to IP that are not of concern to the recipient IP user.
The sending IP user includes the type of service parameter to request a particular quality of service. The user may specify one or more of the services listed as below: Precedence: A measure of a datagram's relative importance. Eight levels of precedence are used. IP will attempt to provide preferential treatment for higher­precedence datagrams.
Reliability:     One of the two levels may be specified: normal or high. A high value indicates a request that attempts be made to minimize the likelihood that this datagram will be lost or damaged.
Delay:      One of the two levels may be specified: normal or low. A low value indicates a request to minimize the delay that this datagram will experience.
Throughput:     One of the two levels may be specified: normal or high. A high value indicates a request to maximize the throughput for this datagram.
  Datagram
Packets in the IP layer are called datagrams. The protocols between IP entities are best described with reference to the IP datagram format, shown in Figure 10.7. A brief description of each field is given in order.
Version: The first field defines the version number of IP. The current version is 4 (IPv4), with binary value of 0100.
Header length (HLEN): The HLEN field defines the length of the header in

multiples of four bytes. The four bits can represent a number between 0 and 15, which when multiplied by 4, gives a maximum of 60 bytes.
Service type:    Specifies reliability, precedence, delay and throughput parameters.
Total length:  The total length field defines the total length of the IP datagram. It is a two-byte field (16 bits).
Identification: The identification field is used in fragmentation. A datagram, when passing through different networks, may be divided into fragments to match the network frame size. When this happens, each fragment is identified with a sequence number in this field (16 bits). A sequence number that, together with the source address, destination address, and user protocol, is intended to identify a datagram uniquely.
Flags: The bits in the flag field deal with fragmentation (the datagram can or cannot be fragmented; can be first, middle or last fragment, etc.).
Fragmentation offset:  The fragmentation offset is a pointer that shows the offset ,   of the data in the original datagram (if it is fragmented).
Time to live:   Specifies how long, in seconds, a datagram is allowed to remain in the internet. Every router that processes a datagram must decrease the time to live (TTL) by at least one, so the TTL is somewhat similar to a hop count.
Protocol:  Indicates the next higher level protocol that is to receive the data field at the destination.
Header checksum:  This is a 16-bit field used to check the integrity of the header, not the rest of the packet.
Source address:   The source address field is four-byte (32-bit) Internet access. It identifies the original source of the datagram.
Destination address:    The destination address field is a four-byte (32-bit) Internet address. It identifies the final destination of the datagram.
Options: The options field gives more functionality to the IP datagram. It can carry fields that control routing, timing, management and alignment.

Data (variable):    The data field must be an integer multiple of 8 bits in length. The maximum length of the datagram (data field plus header) is 65536 octets or 65536 bytes.

BACK