Network Performance Measures
- Throughput
- How much data travels across the network
- Average packet delay
- How long does it take for a packet to arrive at its destination
- How responsive is the system to user commands
- Can the network support real-delivery such as audio and video
Routing Algorithm
“Good” path:
- The minimum cost path
- Other definitions are possible
Hop count
The number of routers a packet must go through
Least-cost routing
Associate a cost with each link
- Bandwidth
- Delay
- Reliability
To make routing decision:
Topology of the network
Traffic load
Link cost
Information should always keep up-to-date
More information
Fixed Routing
Central Directory is usually stored at a network control center
Matrix table
No different between Datagram and VC
Advantages
- Simplicity
- Work Well in a reliable network with a stable load
(IPLC?)
Disadvantages
- Lack of flexibility
- Do not react to network congestion or failures
Flooding Algorithm
Packet sent to every neighbor node
No network information required
Evenually a number of copies will arrive at destination
Guarantees the packet reaches the destination in the shortest time
Duplicate packets are generated.
Node can remember packets already forwarded
Advantage
- Very rebust
- Used for sending emergency messages
Disadvantage
- High traffic load
Random Algorithm
The outgoing link is chosen at random
Round-robin?
- Advantages
- Robust and simple
- no network information
- Less traffic load compare to flooding
- Disadvantages
- Longer path
- Performance not guaranteed
Adaptive Routing
Used by almost all packet switching network
** routing decision changes as network conditions change**
Failure Link
Network congestion
Require network information
Network information must be exchanged among the nodes
Decisions are more complex
Advantages
- Impoved performance
- Congestion control
Disadvantages
- Substantial processing burden on nodes
- Increased network traffic traffic due to the exchange of network information
- Reacting too quickly can cause oscillation
Distance Vector Routing
Each node communicates only with directly-attached neighborsA routing table is created by building up a common set of routers in close proximity to each other, hence the term “distributed”.
Each router on the network must maintain a two-dimensional Vector Table, which records the best known distance from its own router to each router.
A router periodically builds a routing table by exchanging vector tables with neighboring routers (not broadcast to all routers).
When a router receives a vector table from its neighbors and then corrects its own vector table, the contents of the vector table are continually corrected and retransmitted, and the entire network state is gradually passed to each router.
As the routing tables on the routers become more complete, it becomes possible to find the best path. The vector table is sent only to the neighboring routers, which consumes less bandwidth and does not cause broadcast oscillation.
Link State Routing
Information sharing - each router shares its knowledge of its neighbourhood with all routers in the network.
After all LASs from all nodes are gathered, the entire map of the network can be constructed.
Least-Cost Algorithms
- Dijkstra’s Algorithm
- Bellman - Ford Algorithm
We Will come back for the Algorithm later
