Which two statements are true about the router ID in a single area OSPF network

Routing in Packet Switching Networks • Key design issue for (packet) switched networks  • Select route across network between end nodes • Characteristics required:

– Correctness – Simplicity – Robustness – Stability  – Fairness  – Optimality – Efficiency

Internet Routing Protocols • Routers are responsible for receiving and forwarding packets through the interconnected set of networks – Makes routing decisions based on knowledge of the topology and traffic/delay conditions of the internet – Routers exchange routing information using a special routing protocol Ø Two concepts in considering the routing function: – Routing information Ø Information about the topology and delays of the internet – Routing algorithm Ø The algorithm used to make a routing decision for a particular datagram, based on current routing information

Performance Criteria • Used for selection of route • “minimum hop” • “least cost” routing  • “least cost” is more flexible it is more common than “minimum hop”

Decision Time and Place : Decision time • Packet (datagram)  or virtual circuit basis • Fixed or dynamically changing Decision placee• Distributed - made by each node • More complex, but more robust • Centralized – made by a designated node • Source – made by source station

Network Information Source and Update Timing • Routing decisions usually based on knowledge of network, traffic load, and link cost – Distributed routing • Using local knowledge, information from adjacent nodes, information from all nodes on a potential route – Central routing • Collect information from all nodes Issue of update timing • Depends on routing strategy • Fixed - never updated • Adaptive - regular updates

Routing Strategies - Fixed Routing • Use a single permanent route for each source to destination pair of nodes • Determined using a least cost algorithm • Route is fixed

– Until a change in network topology – Based on expected traffic or capacity • Advantage is simplicity • Disadvantage is lack of flexibility – Does not react to network failure or congestion

Routing Strategies - Flooding • Packet sent by node to every neighbor • Eventually multiple copies arrive at destination • No network information required • Each packet is uniquely numbered so duplicates can be discarded • Need to limit incessant retransmission of packets – Nodes can remember identity of packets retransmitted – Can include a hop count in packets

Properties of Flooding :  All possible routes are tried // Highly robust // Can be used to send emergency messages /// At least one packet will have taken minimum hop route /// Nodes directly or indirectly connected to source are visited /// Disadvantages: High traffic  load generated // Security concerns

Routing Strategies - Random Routing • Simplicity of flooding with much less traffic load • Node selects one outgoing path for retransmission of incoming packet • Selection can be random or round robin • A refinement is to select outgoing path based on probability calculation  • No network information needed • Random route is typically neither least cost nor minimum hop

Routing Strategies - Adaptive Routing • Used by almost all packet switching networks • Routing decisions change as conditions on the network change due to failure or congestion • Requires information about network Disadvantage : The routing decision is more complex   : Oscillation

Adaptive route advantage : Improved performance / Aid in congestion control

Classification of Adaptive Routing Strategies • A convenient way to classify is on the basis of information source  Local (isolated) • Route to outgoing link with shortest queue • Can include bias for each destination • Rarely used - does not make use of available information Adjacent nodes • Takes advantage of delay and outage information • Distributed or centralizedAll nodes • Like adjacent

Advanced Research Projects Agency Network ARPANET  Routing Strategies 1st Generation : Distance vector routing • Distributed adaptive using estimated delay 

– Queue length used as estimate of delay • Version of Bellman-Ford algorithm • Node exchanges delay vector with neighbors • Update routing table based on incoming information • Doesn't consider line speed, just queue length and  responds slowly to congestion

ARPANET Routing Strategies 2nd Generation : Link-State routing • Distributed adaptive using delay criterion (measure) – Using timestamps of arrival, departure and ACK times • Re-computes average delays every 10 seconds • Any changes are flooded to all other nodes • Re-computes routing using Dijkstra’s algorithm • Good under light and medium loads • Under heavy loads, little correlation between reported delays and those experienced 

ARPANET Routing Strategies 3rd Generation • Link cost calculation changed –  Damp routing oscillations – Reduce routing overhead • Measure average delay over last 10 seconds and transform into link utilization estimate • Normalize this based on current value and previous results • Set link cost as function of average utilization 

Autonomous Systems (AS) • Exhibits the following characteristics: – Is a set of routers and networks managed by a single organization – Consists of a group of routers exchanging information via a common routing protocol – Except in times of failure, is connected (in a graphtheoretic sense); there is a path between any pair of nodes

Interior Router Protocol (IRP) • A shared routing protocol which passes routing information between routers within an AS  • Custom tailored to specific applications and requirements 

Exterior Router Protocol (ERP) • Protocol used to pass routing information between routers in different ASs • Will need to pass less information than an IRP for the

following reason: – If a datagram is to be transferred from a host in one AS to a host in another AS, a router in the first system need only determine the target AS and devise a route to get into that target system – Once the datagram enters the target AS, the routers within that system can cooperate to deliver the datagram – The ERP is not concerned with, and does not know about, the details of the route Examples : Border gateway protocol (BGP) / Open shortest path first (OSPF)

Approaches to Routing IRP Internet routing protocols IRP Interior routing protocols • Internet routing protocols employ one of three approaches to gathering and using routing information:  Distance-vector routing  / Path-Vector Routing / Link-state routing 

Distance-Vector Routing • Requires that each node exchange information with its neighboring nodes – Two nodes are said to be neighbors if they are both directly connected to the same network • Used in the first-generation routing algorithm for ARPANET • Each node maintains a vector of link costs for each directly attached network and distance and next-hop vectors for each destination • Routing Information Protocol (RIP) uses this approach