Network Level (II)

Network Level (II)

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

Content

• Network level

• Routing activity

• Preliminaries

• Characterization

• Routing

• Routing protocols – RIP & OSPF

– BGP & EGP

• Network Congestion – general discussions

Routing|Preliminaries

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

destination

- 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

Terminology

- 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]

Routing

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

Routing

• 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]

Routing

• 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)

Routing

Comparison between datagram subnet and virtual-circuit subnet

[Computer Networks, 2003

Routing

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

Routing

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]

Routing

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

Routing

• 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

• 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

Routing

• 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

– D^x(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:

D^x(Y,Z)=c(X,Z) + min_w{D^z(Y,w)}

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

Routing

Routing algorithms – classification:

• Static (nonadaptive)

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

– Disadvantages:

• 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

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

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

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

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

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

Example:

– As a metric we consider the delay (msec);

– The routers will know the delays associated with their neighbors

Routing

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:

Routing

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

Routing

Problem:

Topology

modification (routing

algorithms convergence depreciation)

Routing

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

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

Routing algorithms - classification:

• Dynamic (adaptive) – Broadcast routing

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

Ways:

– 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

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

Routing

Example:

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

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

[http://docstore.mik.ua/orelly/networking_2ndEd/tcp/ch02_04.htm]

Routing

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

Routing

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

Routing

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

Routing

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

Routing

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

Routing

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)

Routing

OSPF (Open Shortest Path First)

An AS and its domains, connected through routers

Routing

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

Routing

BGP (Border Gateway Protocol)

Routing

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

Routing

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

Routing

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

• Close-loop

• 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

Obs.:

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

Summary

• Network level

• Routing activity

• Preliminaries

• Characterization

• Routing

• Routing protocols – RIP & OSPF

– BGP & EGP

• Network Congestion – general discussions

Bibliography

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.tuxick.net/linux/ip6routing.html

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

Questions?