• Nu S-Au Găsit Rezultate

Network Level (II)


Academic year: 2022

Share "Network Level (II)"

Arată mai multe ( pagini)

Text complet


Network Level (II)

Lenuta Alboaie ([email protected]) Andrei Panu ([email protected])



Network level

Routing activity




Routing protocolsRIP & OSPF


Network Congestion – general discussions



- The software part of the network level that chooses the path on which a received packet must be sent in order to reach the


- If datagrams are used, the routing decision must be taken for each packet

- If virtual circuits are used, the routing decision is taken when the circuit is established

- Requirements for a routing algorithm: correct, simple, robust, optimal, fast-converging

- Activities

- Determine the optimal routing path - Packet switching



- end systems – network devices which do not have forwarding capabilities of packets to other sub-networks

- intermediate systems – network devices which have packet forwarding capabilities

- Intradomain IS – communication within a routing domain - Interdomain IS – communication between routing domains - autonomous system – a set of networks which share the same

routing strategy and are managed by a unique administrative authority


Network level | …let’s remember

• At the network layer, the Internet can be seen as a collection of subnetworks or autonomous systems connected to each other

• IP makes this interconnection possible (see Course 2)

• The network level handles packet transmission from source to destination (mechanism which involves the passing through a series of intermediate nodes) => the network level is the

lowest layer which deals with end-to-end transmission

Obs.: The role of host-to-network layer is to transport the frames from a point to another


Network level | …let’s remember

End-to-end communication between a client host and a server at network layer


Packet Switching

• A host needs to send a packet to another host

• The source host sends the packet to a router, using the router’s MAC address; this packet contains the network address of the destination host

• The router examines the network address of the destination and if it does not know where to send the packet further, it will destroy it

• Otherwise, it will modify the address contained in the packet with the address of the next hop (intermediate transmission point – Intermediate System) and will send the packet to it

• If the next hop is not the final destination, then the process is


Packet Switching

The switching process

[Retele de calculatoare – curs 2007-2008, Sabin Buraga]



Network layer:

must know the routers’ topology and choose the path through which a packet must be send to destination

must make the choice in a way to avoid overloading communication lines or routers (details on next slides)

The set of all communication subnets

Context for network layer protocols

Determine the optimal routing path



• In case of connectionless services at network level, the packets (datagrams) are sent individually and are routed independently

Routing inside a datagram subnet The routing algorithms

manage routing tables

[Computer Networks, 2003 Andrew S. Tanenbaum]



• In case of connection oriented services at network level, virtual circuits are used and the routing decision takes place when the circuit is established

Routing inside a virtual-circuit subnet (session routing)



Comparison between datagram subnet and virtual-circuit subnet

[Computer Networks, 2003



Determining the routing path

- For each path, a cost is determined (metric)

- Path length, reliability, transmission delay, bandwidth, load, communication cost

- The routing algorithms initialize and keep (for each host) routing tables that contain routing information

– Routes to specified hosts

– Routes to specified networks – A default route



A router creates a logical path between subnetworks

An application which executes on host 1.1 does not need to know the path towards the application on host 4.3 in

order to send data to it [Retele de calculatoare – curs 2007-2008, Sabin Buraga]



Characteristics of the routing algorithms:

Accuracy: an algorithm must operate correctly and quickly to find the destination

Reduced complexity: important for routers with limited hardware capabilities

Optimality: the ability to find the optimal route

Robustness: the capacity to correctly operate for a long period of time in different circumstances

Adaptability: when a network error occurs, the algorithms must adapt (e.g., nodes failure or corruption of routing tables)

Convergence: the algorithms must rapidly converge when routing messages announcing updates are distributed

Load balancing: an algorithm weights different routing possibilities in order to avoid slow links or congestions



• Abstract notions

– Network = graph

– Routing = finding the shortest path from a source node to a destination node

Routing types:

Centralized – the shortest path can be determined by having all the information about the network -> link state routing algorithms

Decentralized – the shortest path is determined iteratively, distributed (there is not a single node which possesses

complete information about the costs of the network links) -> distance vector routing algorithms



• Routing using link state

– The network’s topology & the costs for all links are known

– A node must know the identities & costs of its neighbor nodes

– Each node broadcasts the identities and costs of all

links from it to others



Distance vector routing

Each node receives information from its neighbor nodes, does some calculations and distributes the results back to its direct neighbors – the algorithm is distributed and asynchronous Each node maintains a distance table

X: the node that wants to do a routing to node Y via neighbor node Z

Dx(Y,Z): the sum of the direct link’s cost between X and Z (c(X,Z)), plus the current cost of the shortest path from the neighbors of Z to Y:

Dx(Y,Z)=c(X,Z) + minw{Dz(Y,w)}

A node’s routing table can be built by knowing its distance table



Routing algorithms – classification:

Static (nonadaptive)

The topology of the links is loaded for a period of time in the routing tables of each node


The network must be of reasonable (optimal) size in order to be controllable

If network errors occur, there can not be an immediate reaction

Dynamic (adaptive)

The network state is “learned” through the communication of the routers with their neighbors; the state of each network region is propagated in the whole network after all the nodes update their routing tables => each router can find the best path based on the information from the neighbor nodes



Routing algorithms – classification:

• Static (nonadaptive)

– Shortest path routing – Flooding

– Deflecting routing (or hot-potato routing)

• Dynamic (adaptive) – Distance vectors – Using link state

– Hierarchical routing – Through broadcast – Through multicast



Routing algorithms – classification:

Static (nonadaptive)

Shortest path routing

Dijkstra’s algorithm (calculates the minimum cost path)

• Is used by OSPF protocol

“shortest path”: no. of hops => ABC and ABE are equal

Other possible metrics: geographic distance, bandwidth, communication costs etc.



Routing algorithms – classification:

Static (nonadaptive) Flooding

A received packet is copied and sent through all communication links (except the one it came from)

The problem: packet reflection (a node can receive an unwanted copy of a packet)

Usages of flooding algorithms: military applications, distributed databases etc.



Routing algorithms – classification:

• Static (nonadaptive) – Deflection routing

• At each step, a packet is examined in relation to the

destination address; if the requested link is free, the packet is sent, otherwise it is deflected to another communication link chosen randomly

• A packet has a field associated, containing a value

representing a priority, which can help it in the future to win the “dispute” with other packets



Routing algorithms – classification:

Dynamic (nonadaptive) Distance vector

Each router maintains a table (vector) with the distance and the communication link towards the destination; the tables are updated with information received from the neighbors Bellman-Ford algorithm

Used by RIP, BGP, IGRP protocols


As a metric we consider the delay (msec);

The routers will know the delays associated with their neighbors



Routing algorithms – classification:

• Dynamic (adaptive) – Distance vector

J wishes to compute the route to G J -> A -> G = 26 (18 + 8) msec


J->H->G 18 msec Example:



Problem: in case of the distance vector algorithm, on each update of the routes, the routing tables must be sent to each neighbor;

some packets containing information regarding routing go through the same route they came from (reverse route) Question: Can reverse routes be avoided?

Answer: using the split horizon technique

- When the router sends route updates using a certain network interface, they will not be sent to the networks whose routes were learned from updates received via that interface





modification (routing

algorithms convergence depreciation)



Routing algorithms - classification:

Dynamic (adaptive) Using link state Each router must:

Discover its neighbors and “learn” their network addresses Measure the delay or the cost associated with each neighbor Create a packet through which it announces everyone about

what it learned

Dilemma: when must the packets be created? (e.g., periodically or when a special event occurs)

Send the packet

Calculate the shortest path to each router



Routing algorithms - classification:

• Dynamic (adaptive)

Hierarchical routing

Necessity: in large networks it is not feasible for a router to have an entry about every other router;

Mechanism: Routers know details about a region, but they do not possess information about the internal structure of other regions Obs.:

For large networks, a level 2 hierarchy is not sufficient, thus the regions are grouped in clusters, the clusters in zone, the zones in groups etc.

Which is the optimum number of levels?

For a subnet with N routers, the optimum number: ln N



Routing algorithms - classification:

• Dynamic (adaptive) – Broadcast routing

Use: stock updates (on stock exchanges), multimedia streaming, weather reporting distribution service etc.


The source sends a distinct packet to each recipient Obs.: Ineffective method: does not use the bandwidth;

the source must know the addresses of all the recipients – Flooding useful when other methods can not be applied

Problem: many packets are generated and a lot of bandwidth is used



Routing algorithms - classification:

• Dynamic (adaptive) – Multicast routing Example:

A process wants to send a message to a group of processes which implement a distributed database system

Obs.: Broadcast can be used, but sometimes the information is not intended to be seen by everyone

Mechanism: the router will periodically interrogate the hosts that belong to a group; then the information is

propagated to the routers




Example: For the destination the used router (gateway) is ; Gateway = ->

local network interface

Flags: U(up) – the route is operational; H – indicates a route to a certain host; G – the route uses an exterior gateway

Routing tables creation

Static routes: route UNIX command Discover a router through ICMP




Routing protocols – classification:

- Intradomain routing protocol routes packets inside a domain

– RIP (Routing Information Protocol) – OSPF (Open Shortest Path First)

Interdomain routing protocol – routes packets between domains

– BGP (Border Gateway Protocol) - EGP (Exterior Gateway Protocol)

- RFC 827, 904

- it is not used anymore, being replaced by BGP



RIP (Routing Information Protocol)

• RFC 1058, 1723

• Functioning mechanism:

– Bellman-Ford algorithm is used (for hosts and routers) – For each router, a vector is created, which contains the

cost of the route and other information

– If changes occur in a point, these are periodically

propagated to the neighbor routers and hosts of that point



RIP (Routing Information Protocol)

• Uses IP messages

• Each router sends a broadcast containing the entire routing table of the router – on each 30s

• An entry in a RIP routing table contains:

– IP address

– Metric (number of hops: 1-15) – Timeout (in seconds)

• Networks directly connected have metric = 1 (one hop)

• If a route timeouts, the metric becomes 16 (no connection) and

Routing table A: node B is 1 hop distance (direct

connection), node C is 2 hops



RIP (Routing Information Protocol)

• If a routing information is changed (e.g., a link or a router fails), the propagation of this change takes place slowly – RIP has slow convergence

• RIP:

– Is a mature protocol, stable, widely supported and easy to implement

– Is recommended to be used by autonomous systems with reduced size and without redundant routes

– In practice it is replaced by OSPF in many situations



OSPF (Open Shortest Path First)

RFC 1247, 2328

Each router that uses OSPF knows the state of the entire network topology (algorithm that uses link state) and sends updates to all routers

This generates additional traffic, which can lead to congestions OSPF allows the traffic to be distributed on routes with similar costs (load balancing)

OSPF supports type-of-service (ToS) routing

the IP protocol contains the filed ToS (generally not used)

Faster convergence

Supports the use of many types of metrics



OSPF (Open Shortest Path First)

Operates in a hierarchy of network entities:

Motivation: large networks => a router cannot know the whole topology

Autonomous system (AS) – collection of networks which share the same routing strategy

An AS is divided in areas – contiguous groups of networks and hosts; the routers have the same information regarding the topology and use the same algorithm

Backbone (or area 0) – responsible with the distribution of routing information between domains; any router connected to two or more domains is part of the backbone (these routers will use algorithms corresponding to each domain)



OSPF (Open Shortest Path First)

An AS and its domains, connected through routers



OSPF (Open Shortest Path First) OSPF message types:

Using a “hello” message, a routers discovers its neighbors (e.g., all LAN routers)

Each router periodically floods with a message (that has associated a sequence

number) of type Link state update; for these messages, Link state ack confirmations are sent

Database description provides the sequence numbers associated to the link entries that the transmitter have



BGP (Border Gateway Protocol)



BGP (Border Gateway Protocol)

• Used for the communication between routers in different autonomous systems

• Major functions:

Neighbor relationship – refers to the agreement between the routers belonging to two autonomous systems to exchange information based on some rules (a router can refuse

establishing such a relationship depending on: domain’s rules, overload etc.)

Neighbor maintenance - the routers will send keep-alive messages

Network maintenance – each router keeps a database with the existing subnets for an efficient routing in that subnet



BGP (Border Gateway Protocol)

There are four types of BGP packets:

Open: used for establishing a relationship between two routers

Update: contains updates about routes

Keep-alive: used for confirming previously established relationships

Notification: used when errors occur

BGP router pairs communicate between them using TCP connections

BGP is a protocol based on distance vector, with the following differences:

beside the cost associated with a destination, the path to it is also stored

the neighbors are not provided only with the estimated cost, but also with the exact path

RFC 1771-1774, 4271



Other protocols:

- Interior Gateway Routing Protocol (IGRP) - a RIP improvement by CISCO

- Enhanced IGRP (EIGRP)

- Simple Multicast Routing Protocol ( SMRP)

- Multimedia streams routing from Apple (via AppleTalk)

Obs.: Since 2009, AppleTalk is not supported anymore, being replaced by TCP/IP

• Resource Reservation Protocol (RSVP) (RFC 2205)

• It is not a routing protocol, bot offers similar functionalities

• Ensures IP QoS (quality of service)


Routing | overview

• Internal routing:

• RIP (Routing Information Protocol)

• IGRP (Interior Gateway Routing Protocol)

• EIGRP (Enhanced IGRP )

• OSPF (Open Shortest Path First)

• IS – IS (Intermediate System to Intermediate System) for ISO/OSI

• External routing:

• BGP (Border Gateway Protocol)

• EGP (Exterior Gateway protocol)


Congestion | Discussions

• Occurs when a network’s resources are overloaded

In case of high traffic, congestion can appear and the performance drops sharply


Congestion can appear:

At data link layer: when there is not enough bandwidth

At network layer: when the queue from the nodes can not be controlled

At transport layer: when the logical link between two routers having a

Congestion | Discussions


Congestion | Discussions

• Congestion control – solutions

Open-loop: the solution means preventing the occurrence of congestions through good decisions and design


• System monitoring for detecting congestions

Metrics: the percent of removed packets due to lack of space in buffer, packet delay etc.

• Sending this information to the nodes that can make decisions

• Adjust the operations to correct the problem


Congestion | Discussions


congestion control != stream control

• Congestion control ensures that the network has the

capacity to transport the traffic; involves the actions of all hosts and routers

• Stream control handles the point-to-point communication between a sender and a receiver and ensures the fact that the sender does not transmit data faster than the receiver can process



Network level

Routing activity




Routing protocolsRIP & OSPF


Network Congestion – general discussions



Content Networking Fundamentals, Silvano Da Ros, Publisher: Cisco Press Pub Date: March 30, 2006 Print ISBN-10: 1-58705-240-7 Print ISBN-13: 978-1- 58705-240-8 Pages: 576

Computer Networks, Andrew S. Tanenbaum, Publisher : Prentice Hall

Computer and Communication Networks, Nader F. Mir, Publisher: Prentice Hall Pub Date: November 02, 2006 Print ISBN-10: 0-13-174799-1 Print ISBN- 13: 978-0-13-174799-9 Pages: 656


http://www.6diss.org/workshops/see-2/routing-external.pdf http://www.ip6.com/us/book/Chap7.pdf

http://www.nanog.org/meetings/nanog44/presentations/Monday/SmithBonic a_IPv6_N44.pdf





(M.O. Also, in the case of TBC patients, although the medical system provides free specific medicines they hardly access these services because of the distance

The study results concluded that the ACEIs are effective in lowering systolic and diastolic blood pressure, they reduce global cardiovascular risk through

permanent tension between the possibilities of human nature and the spiritual valences of human condition, the human essence displays itself within the current political

Henotheism was also characteristic of the Roman religion in the beginning; then, during the era of Augustus, a rapid religious evolution took place throughout the Roman empire, the

During the period 1992-2004, for criminal offenses with elements of abuse in the field of real estate turnover in Kosovo there were accused in total 35 persons and none

The Constitution of the Republic of Albania regulates three situations that require extraordinary measures: war situation, state of emergency and state of natural

Abstract: Creation of the modern epoch, the state law is mainly governed by the supremacy of law, but of a fair law, equal for all citizens and exerting positive effects not only

Keywords: trickster discourse, meaning, blasphemy, social change, transgression of social norms.. The Myth of the trickster and its

public void doFilter(ServletRequest request, ServletResponse response, FilterChain chain) throws IOException, ServletException {.

research and modeling efforts in some specific fields of AI (ontologies and knowledge sharing, knowledge processing, intelligent databases, knowledge discovery, data

We then go on to examine a number of prototype techniques proposed for engineering agent systems, including methodologies for agent-oriented analysis and design, formal

De¸si ˆın ambele cazuri de mai sus (S ¸si S ′ ) algoritmul Perceptron g˘ ase¸ste un separator liniar pentru datele de intrare, acest fapt nu este garantat ˆın gazul general,

The best performance, considering both the train and test results, was achieved by using GLRLM features for directions {45 ◦ , 90 ◦ , 135 ◦ }, GA feature selection with DT and

Key Words: American Christians, Christian Right, Christian Zionism, US-Israel Relations, Conservative Christians Theology, State of Israel, Jews, Millennial beliefs,

Un locuitor al oglinzii (An Inhabitant of the Mirror), prose, 1994; Fascinaţia ficţiunii sau despre retorica elipsei (On the Fascination of Fiction and the Rhetoric of Ellipsis),

I use a ConcurrentHashMap to store for every thread a HashMap of all the methods it calls and the statistics associated with

units, it is worth noting that the fundamental reference quantities in the British system of units (foot, pound, second) are based on the primary dimensions of length (L), force

•  A TS groups a sequence of events of one character or a stable group of characters over a period of. story Kme, which is uninterruptedly told in a span

However, the sphere is topologically different from the donut, and from the flat (Euclidean) space.. Classification of two

The purpose of the regulation on volunteering actions is to structure a coherent approach in order to recognise the period of professional experience as well as the

The number of vacancies for the doctoral field of Medicine, Dental Medicine and Pharmacy for the academic year 2022/2023, financed from the state budget, are distributed to

The university as a training and development environment offers to students, regardless of the profession for which they decided to prepare, a lot of learning

The methods can be used to meet the demands of network traffic imposed on a multi- layer network with a base transport layer and a layer of logical or overlay Internet Protocol