Shortest path algorithm

Shortest path algorithm
2.2.4 This page will explain how OSPF uses the shortest-path algorithm to determine the best path to a destination.
In this algorithm, the best path is the lowest cost path. Edsger Wybe Dijkstra, a Dutch computer scientist, formulated the shortest path-algorithm, also known as Dijkstra's algorithm. The algorithm considers a network to be a set of nodes connected by point-to-point links. Each link has a cost. Each node has a name. Each node has a complete database of all the links and so complete information about the physical topology is known. All router link-state databases, within a given area, are identical. The table in Figure

shows the information that node D has received. For example, D received information that it was connected to node C with a link cost of 4 and to node E with a link cost of 1.
The shortest path algorithm then calculates a loop-free topology using the node as the starting point and examining in turn information it has about adjacent nodes. In Figure

, node B has calculated the best path to D. The best path to D is by way of node E, which has a cost of 4. This information is converted to a route entry in B which will forward traffic to C. Packets to D from B will flow B to C to E, then to D in this OSPF network.
In the example, node B determined that to get to node F the shortest path has a cost of 5, through node C. All other possible topologies will either have loops or a higher cost paths.
The next page will explain the concept of OSPF networks.

Comments

OSI layers / Peer-to-peer communications / TCP/IP model

OSI layers 2.3.4 This page discusses the seven layers of the OSI model. The OSI reference model is a framework that is used to understand how information travels throughout a network. The OSI reference model explains how packets travel through the various layers to another device on a network, even if the sender and destination have different types of network media. In the OSI reference model, there are seven numbered layers, each of which illustrates a particular network function. - Dividing the network into seven layers provides the following advantages: • It breaks network communication into smaller, more manageable parts. • It standardizes network components to allow multiple vendor development and support. • It allows different types of network hardware and software to communicate with each other. • It prevents changes in one layer from affecting other layers. • It divides network communication into smaller parts to make learning it easier to understand. In the foll...

Advantages and disadvantages of link-state routing

Advantages and disadvantages of link-state routing 2.1.5 This page lists the advantages and disadvantages of link-state routing protocols. The following are advantages of link-state routing protocols: Link-state protocols use cost metrics to choose paths through the network. The cost metric reflects the capacity of the links on those paths. Link-state protocols use triggered updates and LSA floods to immediately report changes in the network topology to all routers in the network. This leads to fast convergence times. Each router has a complete and synchronized picture of the network. Therefore, it is very difficult for routing loops to occur. Routers use the latest information to make the best routing decisions. The link-state database sizes can be minimized with careful network design. This leads to smaller Dijkstra calculations and faster convergence. Every router, at the very least, maps the topology of it...

Symmetric and asymmetric switching / Memory buffering

Symmetric and asymmetric switching 4.2.8 This page will explain the difference between symmetric and asymmetric switching. LAN switching may be classified as symmetric or asymmetric based on the way in which bandwidth is allocated to the switch ports. A symmetric switch provides switched connections between ports with the same bandwidth. An asymmetric LAN switch provides switched connections between ports of unlike bandwidth, such as a combination of 10-Mbps and 100-Mbps ports. Asymmetric switching enables more bandwidth to be dedicated to the server switch port in order to prevent a bottleneck. This allows smoother traffic flows where multiple clients are communicating with a server at the same time. Memory buffering is required on an asymmetric switch. The use of buffers keeps the frames contiguous between different data rate ports. The next page will discuss memory buffers. Memory buffering 4.2.9 This page will explain what a memory buffer is...

CCNA :) Be a Good Network Administrator

Search This Blog