Network Layer: Addressing, Routing & Congestion Control

• The study notes cover the topic of "Network and Systems Architecture" and specifically focuses on "Unit 2: The Network Layer".

Network Layer Functionalities

• Addressing: Requires a proper addressing system outside the LAN.
• Routing: Involves directing packets from source to destination and demands awareness of network topology. Each node has a routing table and factors like traffic, topology changes, resource limitations, and QoS affect routing.
• Routing Table: Determines the output interface for forwarding each received packet.
• Interconnection of Heterogeneous Networks: Packet fragmentation may rise due to different MTU sizes, and varying frame requirements.
• Congestion Control: Involves awareness, anticipation, and management of congestion to avoid network disruptions.
• End to End Delivery Characteristics: Includes best effort, reliable delivery with or without bounded delay, in-order packet delivery and guaranteed minimal bitrate.
• Security: Requires confidentiality and integrity of communications.

Organization of The Network Layer

• Communications Network: Interconnects source and destination end stations consisting of switching nodes and transmission links.
• Purpose of Nodes: To route packets.
• LAN Implementation: Utilizes switched network design, along with L2 communications.
• Internal Organization Models:
• Virtual Circuits (VC): Connection-oriented.
• Datagrams: Typically, connectionless.

Virtual Circuits Model

• Use Case: Generally used in subnets where the primary service is connection-oriented.
• Addressing: An ID is assigned to the VC during connection establishment that packets carry to identify the VC.
• Routing: A route is selected and sustained throughout the connection with all packets following this route.
• Routing Tables: Network nodes use tables to keep a record of VC IDs passing through them. Upon VC establishment, an item is added to the table, and removed upon disconnection; nodes foward packets based on these tables.

Datagram Model

• Path Determination: The path packets take is not decided beforehand.
• Nature: Usually connectionless, but can provide connection-oriented service as well.
• Addressing: Each packet carries complete source and destination information, specified in network layer addresses.
• Routing: Packets are routed independently, allowing those destined for the same place to travel via various routes and potentially arrive in no particular order.
• Routing Tables: Every network node uses a table that contains data, about the output interface, is used to reach a destination.

Virtual Circuits vs. Datagrams

• Consumption: The usage of network capacity and the memory usage of the nodes are essential aspects to consider.
• Small Packets: In datagram subnets, small packets can lead to wasted bandwidth due to the inclusion of full source and destination addresses.
• Datagram Robustness: Datagram-based subnets display greater node failure reliability.
• Datagram Failures: A failure affects only queued packets. This differs from virtual circuits, where a node failure could cause all the circuits which pass through it to be lost.
• Congestion: Datagrams provide flexibility for congestion because routes can change mid-connection, allowing individual packets to take varied routes.
• Datagram Calls: Packet delivery is generally quicker in datagrams since call setup is not needed.

Services Offered to The Upper Layer (Transport)

• Connection-Oriented service: A station requests a logical connection, and all packets are identified for that connection.
• Connection-Oriented Phases: Such service goes through three phases: connection establishment, data transfer, and connection termination with different functions used for each phase.
• Connectionless service: Packets are handled independently via an external datagram service
• Organizational Model Independence: Service types are not determined by the organization model.

Routing Function

• Network's Primary Use: To get packets from the source station to the destination.
• Path/Route Determination: A route must be determined through the network, while meeting requirements.
• Correctness: The routing function must use correct data.
• Simplicity: The routing function must be simple.
• Robustness: The routing function must ensure reliable delivery, when failures and overloads are encountered.
• Stability: The routing function must converge prior to network changes.
• Fairness: Services must be distributed equally among all users.
• Optimality: Behavior must be optimal, no matter the number of nodes.
• Routing Algorithm: The goal is to find the best path between two nodes using some performance criteria. The algorithm will decide which output interface a node uses to forward a packet.
• Routing Protocol: Defines exchanging control information between nodes (e.g. RIP, OSPF, EIGRP, IS-IS, BGP).

Elements of Routing Techniques

• Performance Criteria: Includes number of hops, cost, delay, throughput, and so on.
• Decision Time: Packet (datagrams model) vs. Session (Virtual circuits model, during connection establishment).
• Decision Place: Each node (distributed routing), central node (centralized routing), or originating node (source routing).
• Network Information Source: None, local, adjacent node, nodes along the route, and all nodes.
• Network Information Update Timing: Never, continuous, periodic, or in response to major load/topology changes.

Classification of Routing Techniques

• Adaptive vs. Non-Adaptive:
• Non-Adaptive Routing: Changes in topology or traffic are ignored and routes remain generally fixed.
• Adaptive Routing: The route dynamically adjusts with topology or traffic.
• Sources of Network Information:
• Isolated Routing: Nodes use no network information other than what is locally available, like queue lengths.
• Distributed Routing: Nodes use local along with global information gathered from adjacent nodes.
• Centralized Routing: Nodes share and get information from a central node.

Adaptive vs. Non-Adaptive Routing

• Adaptive Routing Advantages: Flexible to adapt to failure and congestion.
• Adaptive Routing Disadvantages: Complex routing decisions increase processing burden on nodes, dependent on status information and involves potential overhead.
• Adaptive Routing Reaction: Too fast can cause oscillation and too slow can cause irrelevancy.

Isolated and Distributed Routing

• Isolated Routing: Routing tables are made with available information but without exchanging data across nodes, usually non-adaptive. These involve static, random, flooding, hot-potato and backpropagation algorithms.
• Distributed Routing: Nodes exchange network data, filling routing tables using that data alongside a least-cost routing technique; typically adaptive and raises traffic while needing an exchanging mechanism.

Centralized Routing

• Routing Control Center (RCC): Is designated/central node that calculates routes.
• Periodic Status: Nodes regularly give the RCC the status of their nodes, such as list of adjacent nodes, queue lengths, and traffic.
• Least-Cost Algorithm: The RCC uses least-cost algorithms and delivers routing tables to nodes individually as an advantage.
• Centralized Routing Disadvantages: Time and resource intensive, single point of failure, delay on RCC-distant nodes and heavy traffic issues.

Routing Strategies: Fixed (Static) Routing

• Configuration: A single permanent path, for each source-destination pair, is configured.
• Attributes: The routes do not change. It is isolated and non-adaptive.
• Path: All packets are sent to a destination along the same path.
• Use Case: May act as a backup for other techniques.
• Static Routing Advantages: Simplicity and effectiveness, on networks with stable loads and topology.
• Static Routing Disadvantages: Inability to adapt to factors (failure and congestion).

Routing Strategies: Flooding Routing

• Network Information: Does not use network information, remaining isolated with a non-adaptive nature.
• Packet Retransmission: Each node retransmits an incoming packet on all outgoing links excluding to the link from which it came.
• Flood Routing: Involves generating duplicated packets with a unique identifier that lets nodes drop copies.
• Packet Count: To stop continuous packet retransmission, include a hop count field and decrement each packet, discarding when it hits 0.
• Use Case: Set the hop count at a maximum.

Routing Strategies: Pros and Cons of Flooding Routing

• Flooding Routing Advantages: All possible source and destination routes are considered, and when at least one connection exists, one packet can reach the destination.
• Flooding Routing: Useful for military applications and disseminating routing information.
• Flooding Routing Disadvantages: High traffic load, directly proportional to the network's connectivity (link counts).

Routing Strategies: Random Routing

• Network Information: Does not use any network information and is non-adaptive.
• Node Path: Nodes choose one outgoing path, for the retransmission process of an incoming packet (excluding the original link).
• Random Routing Selection: Performed at random, follows a round-robin approach or assigning probabilities with the choice determined by those probabilities.
• Route: Involves a route that lacks both optimum cost and minimum hops, potential failure and needs optimum traffic load.

Routing Strategies: Hot-Potato Routing

• Routing: Does not involve network information and is sometimes adaptive.
• Node Reception: A node receiving a packet will try to forward it at its fastest.
• Forwarding Measures: Followed by link speeds, the shortest output queue, and all unused links, amongst other things.
• Use Case: Used in nodes, without packet buffering(aka deflection routing), or used with other techniques, such as fixed routing.
• Performance: Deflecting packets will never lead to the least-cost routes, and the destination may never be reached as the network operates past its optimal capacity.

Routing Strategies: Backpropagation Routing

• Use of Network Information: The strategy does not use any formal network information (more or less...).
• Data Packets: There is data, as well as a hop count.
• Node Receipt of Packet: The node will use the hop count to determine node distance, from source, for instance interface k with hop count four means the source is less than four hops away on k.
• Current Hop Adjustment: When the current best route is exceeded.
• Communication Overhead: Increased overhead as data packets get more data added.
• Node Knowledge: Each node knows its minimum distance and the network can fail.

Least-Cost Algorithms

• Pair Aim: For each node pair, it seeks to determine the cheapest path usually found in non-isolated and adaptive settings.
• Link Value: Can compare the value of each link relative to the present load, to the capacity of a specific link etc.
• Hop Minimisation: Every connection is given a cost of 1, if there is a minimum number of hops.

Nodes Connected Through Bidirectional Links

• Path Cost: Defined by the cost sum from every link traversed.
• Link Difference: Cost can vary by direction, such when cost is decided by transmission queue length.
• Primary Algorithms: Dijkstra and Bellman-Ford.

Dijkstra's Algorithm

• Developed By: Edsger W. Dijkstra, in 1959.
• Usefulness; Used to determine short paths in weighted graph.
• Shortest Path: The algorithm creates short path cost in order of length.
• Stage Specifics: The k nodes closest, and their cost will have been established in the kth stage.
• Stage Names: These nodes will then be added to set T.
• Action for K+1 : When in the K+1 stage, add the node outside the set T, to T. The node must come with a short path from the source node.
• Adding to T: Define every path, from the source.
• Convergence: When all nodes are in T, there has been convergence.

Dijkstra’s Algorithm: Formal Description I

• N is the set of nodes, in the network
• s: Is the source node.
• T: Set of nodes incorporated, by the algorithm.
• link cost w(i, j) - Link cost from node i to node j
• L(n) equals cost of the lowest path from the node s, to node n.

Dijkstra’s Algorithm: Formal Description II

• Initialization: Contains source node. Assigns cost of links to neighbours.
• Get Next Node: Finds node outside T, but ensures lowest cost and is part of incident on x.
• Update L(n): Defines least cost and shortens.
• Repeat: The second and third steps will be repeated again, and again up until every node is added.

Bellman-Ford Algorithm

• Proposal: Alfonso Shimbel in 1955, but published by Richard Bellman and Lester Ford Jr. in 1956
• Speed: the Bellman-Ford Algorithm is slower than Dijkstra's Algorithm.,
• Goal: Stage 1 finds the shortest path with 1 link. Stage 2, 2 links. Stage k, k links.
• Outcome: an additional hop must enhance previous paths ( to be converged ).

Bellman-Ford Algorithm: Formal Description I

• N: This is the set of nodes.
• H: This symbolizes the maximum number of links.
• Lh (n): Cost from node s, to n when there are h+1 links .

Bellman-Ford Algorithm: Formal Description II

• Initialization: Denotes infinity to all but s.
• Update: The algorithm computes the Lh+q(n) value,. Connect n's predecessor is the costs is lowest. If there needs to be removal of any node .
• Result: Repeat until no change to Lh(n) occurs.

Dijkstra's vs. Bellman-Ford Algorithm

• Importance: Processing time and data to be gathered from nodes must be compared,
• Dijkstra: Needs info, about each link across the all .
• Bellman-Ford: Needs only known links, with every neighbour.
• Convergence state: These algorithms must catch data, as it is changed; but instabilities can result.

Congestion

• Definition Occurs upon the number of packets being sent, or transmitted and it begins to match the packet amount..
• Performance Degredation: Throughput decreases and packets are lost.
• Strategy: Restrict amount the packets and keep them under the amount needed before they can be dramatic.

Effects of Congestion

• Temporary Packet Buffers: Nodes retain incoming packets, in queues.
• Queue Existence: Each outgoing queue contains it's channel.
• Routing decision: A decision, related or not,. Packets received are put into storage after the interface is received. A buffer has been made.
• Packet Transmission: Packets already within the line must be transmitted, immediately, as quickly as possible.

Rate Exceeding Situation

• Exceeded Transmission Limits: The amount of packets is higher than what they can transmit
• Queue Result : Is unrestricted, for growing sizes. Delays are increased.
• Packet Discards: Limited space will cause data, or message loss and will go over point threshold over 80%.
• Control: Using congestion is a way, to keep everything under control .

Interaction of Queues

• Propagation: congestion can start in a area and or spread.

Effects of Congestion on Performance and Delay

• Light Traffic: Throughput grows.
• Moderate Congestion Signs Delays: Are high, and put an upper limit, or place limit on throughput.
• Heavy Congestion: Packet loss. Throughput is low while average speeds are high.

Congestion Control Techniques

• Signaling: In congestion scenarios, it is important to have choke packets by providing feedback.

Backpressure

• Slow/Stopping Processes: A point, may decide to slow traffic down.
• Restriction: It is then, propagated, (to the source).
• Speed: A node needs to be able, to maintain the rates.
• Applications ; Can involve real and virtual pathways.
• Selective Application: To apply the most traffic.
• Connection Oriented Network: Allow connections as well.

Choke Packets

• Packets that are controlled and sent to congested source, then transmitted to origin.
• Example: The process ICMP source quench, to its source if their are any input buffers, with messages sent with deleted datagrams
• Sophistication: Is quite simplified, but ICMP is outdated.

Implicit Congestion Signalling

• Signalling Source: Detection and action for congestion.
• Reducing flows and traffic is accomplished.
• Signalling Evidence : There can be implicit signs of packet drops.
• Source Reaction: All the end systems and components will react , without more infrastructure.

Explicit Congestion Signaling

• Network nodes gives end equipment growing explicit data and the network nodes.
• Data/Control Flow: Can use data, but this controls the traffic by individual links or connections but does work with some data links
• Signalling Directions: This can be back or forward.
• Forward Signalling: Packet information going, the same direction and will echo the signal for its high process speed.

Explicit Congestion Signalling Techniques

• Binary Feedback: A flag is forwarded from the congested node.
• Credit System: It is what the source sends, so there are no additional data.
• Rate Feedback: This can change the data, that can pass through the entire data rate.

Traffic Management

• Congestion Control : Focuses on efficiency and dealing , or interacting with excessive loads..
• Handling Drops : It is then put out by policy. Aspects are considered.
• Fair Allocation: In traffic management, there must be fair allocation of rates.
• Quality Measures : Elasticity takes into account traffic.
• Reservations : QoS parameters are handled.
• Parameters, are checked for certain contract situations. Excess traffic is discarded with some marking.

Traffic Management Tools

• Requires categorization to determine, and implement certain aspects of traffic.
• Can be determined for use with data in specific levels.
• May need to note use of level 2.
• Congestion Avoidance: Predictive early pre emptive models
• Traffic Policing: Controls and marks use of committed information .
• Traffic Shaping: Handles excess at later transmission
• Control: The packets there will need priorities.

Overlay Tunnels

• Tunneling Protocols: Give connections to networks using other networks.
• End Point Actions , Decapsulation and encapsulation as part of tunnel actions.
• Network Support: It allows tunneling, runs over those, which can not be normally run or supported..
• Traffic Control: Is used for traffic and VPN..

Overlay Tunnels

• Different Technologies: Used for implement for routing. such as GRE.
• Common Tunnels : Is implement as service (VPN or Virtual Private Network);.
• Security : Using encryption, peer data, authentication and etc.
• Primary VPN formats : point to point and remote access as well as no network as well.

X.25

• A standard by the ITU, created in 1976, which acts as a interface.
• Public Networks: Used public networks not inside the networks.
• Connection service: It, like virtual pathways include sequence packet mechanism.
• Congestion Control: flow is performed (backpressure).

X.25 Virtual Circuits

• Multiplexing: Virtual channels are used across physical connections.
• Virtual Service : These are given to an external service. Logical connections are between two users, where there are two virtual channels and are bidirectional.
• Types: Are two virtual paths and circuit paths.

X.25 Layers and PDUs

• The architecture three layers are: one, physical two, data link layers and HDLC sub sets three, network.
• Routing Data : Data is passed with a circuit ID with an LAPB protocol.

X.25 Disadvantages

• Features: Reliable connections, fibre technology and speed.
• Output : Outputs overhead for packets and layers.
• Process : Handles data, for call and link flow. These protocols may hamper data rates.

Frame Relay

• Version: It is a light version of X.25.
• Connection service: Provides services with with permanent and switched frames.
• Architecture and Retransmission: Features two layers and also performs the re-transmissions.
• Control and Links: Takes extra advantage to reliability.
• Rates: Can work up to 2 Mps by shortening delay and improving performance.

Frame Relay Features

• Layer 2 Multiplexing and Switching , A process which cuts down.
• Handling of Contention: This handling may contribute traffic, in high-demand and contract areas.
• Bandwidth: Does not have error control in between links .
• Acknowledgment State: Can ack the source for being delivered.

Frame Relay: Protocol Architecture

• Data and Signal Transmission: Separates transmissions from signally
• The architecture differs for user and network nodes.

Frame Relay: LAPF Frame Format

• Components: DLCI( ID ); C/ R , command or response; EA , addressing bit ; FECN/ BECN; DE, allows discard eligibility bit.

Frame Relay: Congestion Control

• Information on End Systems: Provides information with bits from FECN and BECN.
• Queue Monitoring: The frame switching will check queues.
• The signals are meant to, and are responded with signalling and adjustments.

Frame Relay: Congestion Control and Information Rates I

• Mitigation: The face of bad congestion, where discards are limited and can only occur through particular events; and are still based in rates.
• In agreement with data (bits/s) set within the network and on each data stream that is not maintained, nodes will decide whether or not to discard or select frames, from connections and will look to the total amount of resources.
• Frames passing beyond these bounds will have the bit selected.

Frame Relay: Congestion Control and Information Rates II

• Time intervals: Traffic is given a rate and interval that can contain measurement and a burst size..
• Burst Calculation: volume for any burst which requires excess. Be may alter with a volume depending on conditions which range, or it needs to handle greater of what's admitted.

ATM (Asynchronous Transfer Mode)

• Switching: Technology which uses cells set for 53 data volumes in, for its packets
• Design: It's aimed at convergent communication with video and audio.
• Connection: This type is used for connection oriented, and channels on its path.. it handles on high end channels even with minimal error. This allows faster rate.
• Services are provided for real and non times

ATM Protocol Architecture

• Control: A component, which is handled with control and the connection at the same time
• Management the lane requires managing all levels..
• Layer also needs infrastructure.

ATM : Protocol Architecture

• ATM Adaptation Layer: The AAL (ATM adaptation layer) enables information transfer protocols regardless of ATM.
• Group or fragment : Breaks groups into 48 octet packets and encapsulates and then into cells, such IP information.

ATM. Logical Connections

• Connections: Referred to as virtual channels or a duplex, that path data flows through.

ATM - VPI & VCI

Virtual Path Identifier (VPI). Virtual Channel Identifier (VCI).

ATM: Logical Connections

• Paths: Two virtual links that are switched and are semiparmanent. Control Signalling: Establishes the semi-permanent VPCs which are custom or network controlled. Also is control as well as the signal which comes to from the end.

ATM: Logical Connections

• Traffic Contracts: Is set of cells and can include. PCR, CDV. and SCR.

ATM Traffic Management and Congestion Control

• High Demand Issues. More difficult because of the need to balance speed, cell sizes, and limited flow control.
• Congestion is not correct for ATM.
• Traffic cannot stop congestion . Has limited space and high volume, for various applications where switching is used.

ATM: Traffic Management and Congestion Control

• Resources are handled utilizing multiple routes with allocated traffic, demands admission of usage.
• Traffic contract, levels, and policing cells occur. Discard is used to apply cells. Smoothness is acquired and traffic, needs to be smooth as well as a, "TOKEN".

MPLS (Multiprotocol Label Switching)

• Set: Is specs by IT that adds route and traffic metrics into packets.
• Protocol Suite- Composes protocols which are inter related.
• Traffic Routing-Is ensure that flow stays the course but the link route
• QoS. QoS SLA

MPLS

• Protocols: It can be used with Protocols levels that can be used. It supports QoS through features with minimal examination .
• Supports: Mechanism for supporting VPNs as well as the label..

MPLS Traffic Engineering

• Utilisation: It improves traffic. And routes throughout to optimize. Has awareness and algorithms for the connections too. These signals will work for allocated traffic stream.