Advanced Networks

Which layer of the OSI model is accountable for transmitting packets to a destination when a computer delivers data to another computer on a different network?

• The Network Layer is responsible for moving packets from a sending host to a receiving host across multiple networks.

• It determines the route or path taken by packets as they flow from a sender to a receiver

• It acts as a carrier, akin to a postal service, ensuring packages are delivered from a sender to a receiver without altering their contents.

• To direct data packets across networks two important functions of the network layer can be identified: Forwarding and Routing.

• The algorithm computed paths are utilized to create and update the routers’ routing tables.

• In networks using datagrams, routing decisions are made for each packet, as routes may change.

• In networks using virtual circuits, routing decisions are made only when a new circuit is set up, allowing packets to follow an established route thereafter. Routing algorithms are categorized primarily into two classes:

  • Non-adaptive routing algorithms :

    • Nonadaptive algorithms make routing decisions without considering current topology or traffic conditions.

    • Routes from S to D are precomputed offline (before network starts operating) and downloaded to routers upon network boot-up

    • This process is known as static routing.

  • Adaptive routing algorithms:

    • Routers modify their routing decisions to adapt to changes in network topology and traffic

    • To find the best route, the algorithms use a metric. This may be, for example, the distance to be covered, the number of hops or the time needed to cross the network Routers exchange routing information and dynamically update their routing tables.

    • This capability is the reason they are referred to as dynamic routing algorithms.

    • Several routing algorithms exist, including:

      • Distance-vector routing

      • Link-state routing

• Today’s computer networks predominantly utilize adaptive routing algorithms (dynamic), with distance-vector routing and link-state routing being the most common types.

• The distance vector refers to the distance (vector) between neighboring nodes and the routing refers to the established route

• It is known as the distributed Bellman-Ford routing algorithm. It was the original routing algorithm for ARPANET and has been utilized in the Internet as RIP (Routing Information Protocol).

• The distance vector routing algorithm employs a separate table for each router, detailing the best-known distance and the output for each destination known as the distance vector.

• Metrics used to measure the distance can include hop counts, transmission time, or other measurements.

• Each router is required to know the distance to its neighboring routers.

• Every Ts seconds, routers transmit their distance vector lists to all neighboring routers

• After obtaining a distance vector from each neighboring router , the router x calculates the cost to reach a destination y by applying the Bellman–Ford formula

• The router calculates the total cost for each destination through all its neighbors and selects the path with the minimum total cost.

• The routing table is updated accordingly.

• Proposed to overcome the limitation of Distance-Vector Routing algorithm, providing faster and more accurate routing decisions.

• Link State Routing is a routing algorithm that enables each router to build a complete map of the network topology.

• With this global view, routers can compute the shortest paths to all destinations.

• The link state reflects its characteristics, particularly the cost associated with that link.

• Links with lower costs are prioritized over those with higher costs.

• A link with a cost of ∞ is deemed broken or nonexistent

• The main steps of the Link-State routing algorithm are:

  1 Discover neighbors:

  • Each router identifies its directly connected routers.

  • This process is initiated by sending special HELLO messages on each interface.

  • The router learns the identity and addresses of its neighbors from the responses it receives.

  2 Measure link costs

  • The router evaluates the cost of the link to each neighbor.

  • Cost can signify delay, bandwidth, or another routing metric.

  • Typically, the router calculates the round-trip time (RTT) of packets and divides it by two to estimate link delay.

  3 Build Link-State Packets (LSPs)

  Each router creates a packet with collected information.

  The packet generally contains: the router ID, the list of neighboring routers, and the cost of each link

  This packet reflects the state of the router’s links.

  LSPs are generated at regular intervals or in response to specific events like a line or neighbor status change.

  4 Flood the LSPs throughout the network

  • Each router uses flooding to distribute LSPs to all routers in the network.

  • Flooding guarantees that all routers acquire the same topology information.

  • Following this exchange, all routers create an identical Link-State Database (LSDB) that reflects the complete network topology

  5 Compute the shortest paths using Dijkstra’s algorithm

  • Each router uses the LSDB to construct a network graph.

  • Dijkstra’s shortest path algorithm is employed to determine the least-cost path to all destinations.

  • The outcome is a Shortest Path Tree (SPT), which is utilized to formulate the router’s routing table