حساب المسار الأفضل وكلفة المسار الكلية

TL;DR

Routing is a key network layer function that finds the best (least-cost) path between a source and a destination. The total cost of a path is the sum of costs of its individual links. Algorithms like Link State (global) and Distance Vector (decentralized) are used to determine these optimal paths.

1. The Mental Model

Think of finding the quickest route on a map from your home to a friend's house. Each street segment has a "cost" (like time or traffic), and you want to pick the path that minimizes the total "cost" to get there.

2. The Core Material

In networking, finding the أفضل مسار (best path) is about identifying the (ذو الكلفة الأقل) (least-cost path) between a source and a destination node. When a router receives a packet, it reads the header to find the destination and then uses its local جدول التمرير (forwarding table) to choose the correct output port. This local forwarding works together with other routers' tables to achieve overall التوجيه (routing).

A عقدة مجاورة (neighbor) y is directly connected to node x via a link (x,y).
The الكلفة الكلية لمسار (total cost of a path) is simply the sum of the costs of all the individual links (sub-paths) that make up that path. If a link doesn't show a cost, you can assume its cost is 1.

There are two main categories of routing algorithms:

Global (Centralized) Routing Algorithms: (خوارزميات التوجيه المركزية)

These algorithms calculate the least-cost path with a complete, global understanding of the entire network. They need all link costs and connectivity information between all nodes beforehand. Routers using these algorithms have tables containing full network state information, including topology, links, connected nodes, and link costs. This information must be gathered before calculations begin. They are also called خوارزميات حالة الوصلة (Link State (LS) Algorithms) because they become aware of every link's cost by broadcasting a Link State Routing message at the start. Dijkstra's algorithm is commonly used here. These are typically applied within a single Internet Service Provider (ISP).

graph TD
    A["Router (Source)"] --> B{{"Collect All Network Info (Link State Broadcast)"}}
    B --> C["Knows All Node Costs & Connectivity (Global View)"]
    C --> D{"Run Dijkstra's Algorithm"}
    D --> E["Calculate Least-Cost Path to Destination"]
    E --> F["Update Local Forwarding Table"]
    F --> G["Send Packet Along Best Path"]

Decentralized Routing Algorithms: (خوارزميات التوجيه الغير مركزية)

These algorithms calculate the least-cost path interactively and in a distributed manner among routers. No single node has complete knowledge of all network link costs. Each node starts knowing only the costs of its directly connected links. Through an iterative process of calculations and information exchange with its neighbors, each node progressively computes the least-cost path to a destination (or multiple destinations). These are known as خوارزميات شعاع المسافة (Distance Vector (DV) Algorithms). Each node maintains a "distance vector" (cost estimate) to all other nodes in the network. They are suitable for very large networks with many routers where storing complete global network information in each router's memory wouldn't be practical.

3. Worked Example

Let's use the example from your source material to find the best path from u to z.
The network diagram provides the costs for each link:

• u --(5)--> w
• w --(5)--> z
• u --(2)--> v
• v --(3)--> w
• v --(1)--> x
• x --(2)--> y
• y --(1)--> z

Let's calculate the cost for each identified path:

1. Path 1: u → w → z

   • Cost = c(u,w) + c(w,z) = 5 + 5 = 10 units of cost.

2. Path 2: u → v → w → z

   • Cost = c(u,v) + c(v,w) + c(w,z) = 2 + 3 + 5 = 10 units of cost.
   • Note: Same cost as Path 1, but with more hops.

3. Path 3: u → v → x → y → z

   • Cost = c(u,v) + c(v,x) + c(x,y) + c(y,z) = 2 + 1 + 2 + 1 = 7 units of cost.

4. Path 4: u → x → y → z (This assumes there is a direct link u-x with a cost of 1, as implied by the source material's calculation c(u,x)=1)

   • Cost = c(u,x) + c(x,y) + c(y,z) = 1 + 2 + 1 = 4 units of cost. (The diagram shows a direct u to x connection with cost 1.)

Comparing all path costs: 10, 10, 7, 4.

The least-cost path, or المسار الأفضل (best path), is Path 4 (u → x → y → z) with a total cost of 4 units.

4. Key Takeaways

• Routing aims to find the least-cost path between a source and a destination in a network.
• The total cost of a path is the sum of costs of all individual links it comprises.
• A "neighbor" is a node directly connected to another node via a link.
• Global (Link State) routing algorithms require full network information initially and often use Dijkstra's algorithm.
• Decentralized (Distance Vector) routing algorithms build path knowledge iteratively by exchanging info with neighbors, suitable for large networks.
• Forwarding tables at routers use the best path information to send packets to the correct output port.

5. Now Try It

Using the provided network diagram (or drawing a new simple one), imagine the cost of the link (u,x) changes to 5 instead of 1. Recalculate the cost for Path 4 and determine if it's still the best path to z from u, compared to the other paths. What was the new best path and its cost?