FIT3165 / FIT4165 COMPUTER NETWORKS
WEEK 5 – NETWORK LAYER
Faculty of Information Technology © 2022 Monash University
Copyright By PowCoder代写 加微信 powcoder
3.1 INTRODUCTION
3.2 NETWORK-LAYER PROTOCOLS
3.3 INTRODUCTION TO UNICAST ROUTING 3.4 NEXT GENERATION IP
INTRODUCTION
Objectives
❑ We first discuss services that can be provided at the network layer: packetizing, routing, and forwarding.
❑ We then discuss the network layer at the TCP/IP suite: IPv4 and ICMPv4. We also discuss IPv4 addressing and related issues.
❑ We then concentrate on the unicast routing and unicast routing protocols.
❑ Wefinallydiscussthenewgenerationof network-layer protocols, IPv6 and
Figure : Introduction: Communication at the network layer
Network-Layer Services
❑ Packetizing
❑ Forwarding
❑ Error & Flow Control
❑ Congestion Control
❑ Security
Figure : Forwarding process
Packet Switching
• From the discussion of routing and forwarding in the previous section, we infer that a kind of switching occurs at the network layer.
• A router, in fact, is a switch that creates a connection between an input port and an output port (or a set of output ports), just as an electrical switch connects the input to the output to let electricity flow.
Figure: A connectionless packet-switched network
Figure: Forwarding process in a router when used in a connectionless network
Datagram Approach
Virtual-Circuit Approach
❖ Setup Phase
❖ Data-Transfer Phase
❖ Teardown Phase
Packet switched network – Virtual Circuit
Figure: A virtual-circuit packet-switched network
Figure: Forwarding process in a router when used in a virtual circuit network
Packet switched network – Virtual Circuit
Figure: Sending request packet in a virtual-circuit network
Figures: Sending acknowledgments in a virtual-circuit network
Network-Layer Performance
• The upper-layer protocols that use the service of the network layer expect to receive an ideal service, but the network layer is not perfect.
• The performance of a network can be measured in terms of • delay
• throughput, and
• packet loss
• We first define these three terms in a packet-switched network before we discuss their effects on performance. ❑ Delay
❖ Queuing Delay: time waiting for its turn at output link
❖ Processing/ : Check for packet error & routing decision
❖ Transmission Delay: time to pump the packet onto a link at link speed
❖ Propagation Delay: router/node–to-router/node propagation
Total Delay=sum of all the delays-above
❑ Throughput
Figure: A path through the Internet backbone
Figure : Throughput in a path with three links in a series
Figure: Effect of throughput in shared links
Network-Layer congestion and congestion control
• Although congestion at the network layer is not explicitly addressed in the Internet model, the study of congestion at network layer may help us to better understand the cause of congestion at the transport layer and find possible remedies to be used at the network layer.
• Congestion at the network layer is related to two issues: throughput and delay, which we discussed previously.
❑ Congestion Control
Congestion control refers to techniques and mechanisms that can either prevent congestion before it happens or remove congestion after it has happened.
Open Loop Congestion Control:
• In this method, policies are used to prevent the congestion before it happens. • Congestion control is handled either by the source or by the destination.
• The various methods used for open loop congestion control are:
• Retransmission Policy: The sender retransmits a packet, if it feels that the packet it has sent is lost or corrupted. The retransmission policy and the retransmission timers need to be designed to optimize efficiency
• Window Policy: To implement window policy, selective reject window method is used for congestion control. Selective Reject method is preferred over Go-back-n window as in Go-back-n method, when timer for a packet times out, several packets are resent, although some may have arrived safely at the receiver. Thus, this duplication may make congestion worse. Selective reject method sends only the specific lost or damaged packets.
• Acknowledgement Policy: positive and negative acknowledge approaches can be used,
• Discarding Policy: A router may discard less sensitive packets when congestion is likely to happen.
• Admission Policy: An admission policy, which is a QoS (quality-of-service) mechanism, can also prevent congestion in virtual circuit networks.
Closed Loop Congestion Control:
• Closed loop congestion control mechanisms is to mitigate/reduce the congestion after it happens. The various methods used for closed loop congestion control are:
• Backpressure: Backpressure is a node-to-node congestion control that starts with a node and propagates back, in the opposite direction of data flow. (to each node)
• Choke Packet: In this method of congestion control, congested router or node sends a special type of packet called choke packet to the source to inform it about the congestion. (from choke router straight to source and not to the intermediate nodes)
• Implicit Signalling: In implicit signalling, there is no communication between the congested node or nodes and the source. The source guesses that there is congestion somewhere in the network when it does not receive any acknowledgment. This type of congestion control policy is used by TCP.
• Explicit Signalling: In this method, the congested nodes explicitly send a signal to the source or destination to inform about the congestion. Explicit signalling can occur in either the forward direction or the backward direction .
Closed Loop Congestion Control:
Backpressure: Backpressure is a node-to-node congestion control that starts with a node and propagates back, in the opposite direction of data flow. (to each node)
Choke Packet: In this method of congestion control, congested router or node sends a special type of packet called choke packet to the source to inform it about the congestion. (from choke router straight to source and not to the intermediate nodes)
Packet delay and throughput as functions of load
Structure of A Router
Layer-3 Network Layer Device – forwarding and routing
• That accepts incoming packets from one of the input ports (interfaces)
• Uses a forwarding table to find the output port from which the packet departs, and sends the packet from this output port.
❑ Components
❖ Input Ports
❖ Output Ports
❖ Routing Processor
❖ Switching Fabrics
▪ Crossbar Switch
▪ Banyan Switch
▪ Batcher-Banyan Switch
Router components
Components of a router – Input & Output Ports:
● An input port performs the physical and data-link functions of the packet switch.
● The bits are constructed from the received signal.
● The packet is decapsulate from the frame.
● Errors are detected and corrected.
● The packet is now ready to be routed by the network layer.
● In addition to a physical-layer processor and a data-link processor, the input port has buffers
(queues) to hold the packet before it is directed to the switching fabric.
Figure: Input port
Figure: Output port
Crossbar switch
• A crossbar switch is a switch connecting multiple inputs to multiple outputs in a matrix manner.
• Architecture of a unidirectional crossbar switch: The crossbar switch can switch inputs to the outputs – imagine each box is a CPU or a memory module.
Banyan switch
• The first stage routes the packet based on the high-order bit of the binary string.
• The second stage routes the packet based on the second high-order bit, and so on.
• Figures show a banyan switch with eight inputs and eight outputs. The number of stages is Log2(8) = 3.
Batcher – Banyan switch
• Batcher-Banyan switch: On each switch cycle, each input line at the top puts one cell into the Batcher sorter switch.
• The Batcher sorting switch: Sorts the cells and passes them onto the trap module.
• The trap module: detects duplicate cells to the same destination and selects one cell for each destination to pass on to the banyan.
• The trap module then compresses the list of sorted cells so there are no gaps and place’s the cells on the input lines into the banyan switch.
• The banyan switch routes the cells to their appropriate outputs.
• The feature that tends to differentiate Batcher-Banyan designs is the design of their trap modules.
• The challenge of the trap module is to avoid discarding cells when there is more than one cell for the same destination while making sure cells do not get reordered.
NETWORK LAYER PROTOCOLS
IPv4 Datagram Format
• Packets used by the IP are called IP_datagrams.
• A datagram is a variable-length packet consisting of two parts:
■ header and
■ payload (data)
• The header is 20 to 60 bytes in length and contains information essential to routing and delivery. It is customary in TCP/IP to show the header in 4-byte sections.
❑ Fragmentation
❖ Maximum Transfer Unit (MTU)
❖ Fields Related to Fragmentation
Security of IPv4 Datagrams
❖ Packet Sniffing
❖ Packet Modification
❖ IP Spoofing
IPv4 Datagram Format
Figure: IP datagram
Multiplexing and demultiplexing
Figure: Multiplexing and demultiplexing using the value of the protocol field (8-bits)
Fragmentation
Figure : Maximum transfer unit (MTU)
Offset = 175 x 8 bytes (measured in chunks of 8 Bytes)
Offset = 350 x 8 bytes (measured in chunks of 8 Bytes)
Figure : Fragmentation example
IPv4 Addresses
• The identifier used in the IP layer of the TCP/IP protocol suite to identify the connection of each device to the Internet is called the Internet address or IP address.
• An IPv4 address is a 32-bit address that uniquely and universally defines the connection of a host or a router to the Internet.
• The IP address is the address of the connection, not the host or the router, because if the device is moved to another network, the IP address may be changed.
❑ Address Space ❑ Notation
❑ Classless Addressing
❖ Prefix Length: Slash
❖ Extracting information from
an address
❖ Address Mask
❖ Network Address
❖ Subnetting
❖ Address Aggregation
❖ Special Addresses
Dynamic Host Configuration Protocol (DHCP)
❖ DHCP Message Format
❖ DHCP Operation
❖ Two Well-Known Ports
❖ Using FTP
❖ Error Control
❖ Transition States
Address Translation Translation Table0
Hierarchy in Addressing
Classful Addressing
❖ Address Depletion
❖ Subnetting and Supernetting
❖ Advantage of Classful Addressing
IPv4 Addresses
Figure : Three different notations in IPv4 addressing Figure : Hierarchy in addressing
IPv4 Addresses – Classful addressing
Figure : Occupation of the address space in classful addressing
IPv4 Addresses – Classless addressing
Figure: Slash notation (CIDR-Classless Inter-Domain Routing)
Set all suffix bits to 0s
Set all suffix bits to 1s
Figure : Information extraction in classless addressing
A classless address is given as 167.199.170.82/27. We can find the above three pieces of information as follows. The number of addresses in the network is 232− n = 25 = 32 addresses, where n=27
The first address can be found by keeping the first 27 bits and changing the rest of the bits to 0s.
The last address can be found by keeping the first 27 bits and changing the rest of the bits to 1s.
Network address
Figure : Network address
Example -1
An organization is granted a block of addresses with the beginning address 14.24.74.0/24. The organization needs to have 3 sub-blocks of addresses to use in its three subnets:
1. one subblock of 10 addresses,
2. one subblock of 60 addresses, and
3. one subblock of 120 addresses.
Design the sub-blocks.
Solution:-
☞ Total # of addresses are 232– 24 = 256 addresses in whole complete block.
☞ The first address is 14.24.74.0/24; the last address is 14.24.74.255/24.
☞ To satisfy the third requirement, we assign addresses to sub-blocks, starting with the largest and ending with the smallest one.
Continued ….
Example – 2
Solution (continued..)
a. one subblock of 10 addresses,
b. one subblock of 60 addresses, and
c. one subblock of 120 addresses.
☞ c.Thenumberofaddressesinthelargestsub-block,whichrequires120addresses,isnotapowerof2.Weallocate 128 addresses. The subnet mask for this subnet can be found as netmask1 = 32 − log2128 = 25
☞ the first address in this block is 14.24.74.0/25;
☞ the last address is 14.24.74.127/25.
☞ b.Thenumberofaddressesinthesecondlargestsub-block,whichrequires60addresses,isnotapowerof2either. We allocate 64 addresses. The subnet mask for this subnet can be found as netmask2 = 32 − log264 = 26.
☞ The first address in this block is 14.24.74.128/26;
☞ the last address is 14.24.74.191/26.
☞ a. The number of addresses in the smallest sub-block, which requires 10 addresses, is not a power of 2. We allocate 16 addresses. The subnet mask for this subnet can be found as netmask3= 32 − log216 = 28.
☞ The first address in this block is 14.24.74.192/28;
☞ the last address is 14.24.74.207/28.
Example – 3
14.24.74.192/28
☞ If we add all addresses in all the subblocks, the result is 208 addresses, which means 48 addresses are left in reserve or unused.
☞ The first address of unused range is 14.24.74.208.
☞ The last address is 14.24.74.255.
☞ Figure 4.36 shows the configuration of sub-blocks. Figure shows the first address in
each block.
Address aggregation
✔ The figure shows how four small blocks of addresses are assigned to four organizations by an ISP. The ISP combines these four blocks into one single block and advertises the larger block to the rest of the world.
✔ Any packet destined for this larger block should be sent to this ISP.
✔ It is the responsibility of the ISP to forward the packet to the appropriate organization.
✔ This is similar to routing. All packages coming from internet are sent first to the
ISP and then distributed to the corresponding networks behind the ISP.
DHCP – Message format and option format
DHCP message format
DHCP Option format
DHCP – Operation
Figure : Operation of DHCP
Network Address Translation (NAT)
Figure: NAT
Figure: Address translation
NAT – Operation
Reference: https://commons.wikimedia.org/wiki/File:Network_Address_Translation_(file2).jpg Reference: https://upload.wikimedia.org/wikipedia/commons/a/a4/NAT3.jpg
Forwarding of IP Packets
• Concept of forwarding packet at the network layer.
• Extend the concept to include the role of IP addresses in forwarding.
• Forwarding means to placing the packet in its route to its destination.
• Since the Internet is complex combination of links (networks), forwarding means to deliver the packet to the next hop (which can be the final destination or the intermediate connecting device).
Figure: Forwarding by Address aggregation
● The traceroute program in UNIX or
● The tracert in Windows
It can be used to trace the path of a packet from a source to the destination. It can find the IP addresses of all the routers that are visited along the path. The program is usually set to check for the maximum of 30 hops (routers) to be visited.
The ping program gets help from two query messages;
two error-reporting messages:
• time-exceeded and
• destination-unreachable
Figure shows an example in which; n = 3 or three intermediate routers.
• The traceroute program also sets a timer to find the round-trip time for each router and the destination.
• Most traceroute programs send three messages to each device, with the same TTL value, to be able to find a better estimate for the round-trip time.
• The following output shows an example of a traceroute program, which uses three probes for each device and gets three RTTs.
UNICAST ROUTING
Unicast Routing – General Idea
• In unicast routing, a packet is routed, hop by hop, from its source to its destination by the help of forwarding tables.
• The source host needs no forwarding table because it delivers its packet to the default router/gateway in its local network.
• The destination host needs no forwarding table either because it receives the packet from its default router in its local network.
• This means that only the routers that glue together the networks in the internet need forwarding tables.
❑ An Internet as a Graph
❑ Least-Cost Routing
❑ Least-Cost Trees
Internet as a graph
A weighted graph is a graph that has a numeric label w(e) associated with each edge e.
Edge weight can be integers, connection costs, or affinity.
When an internet is modelled as a weighted graph, one of the ways to interpret the best route from the source router to the destination router is to find the least cost between the two.
Figure: An internet as a graph – its graphical representation
Least- cost trees
Figure: Least-cost trees for nodes in the internet
If there are N routers in an internet, there are (N − 1) least-cost paths from each router to any other router. This means we need N × (N − 1) least-cost paths for the whole internet. If we have only 10 routers in an internet, we need 90 least-cost paths. A better way to see all of these paths is to combine them in a least-cost tree.
Routing Algorithm
• We have discussed the general idea behind least-cost trees and the forwarding tables that can be developed from them.
• Let’s now concentrate on the routing algorithms.
• Several routing algorithms have been designed in the past. The differences between these methods
are in the way they interpret the least cost and the way they create the least-cost tree for each node.
• In this section let’s discuss the common algorithm; later we show how a routing protocol in the
Internet implements one of these algorithms.
○ Distance vector routing algorithm
○ Link state routing algorithm
○ Path vector routing algorithm
Distance- Vector Routing
● In distance-vector routing, the first thing each node creates is its own least-cost tree with the rudimentary information it has about its immediate neighbours.
● The incomplete trees are exchanged between immediate neighbours to make the trees more and more complete and to represent the whole internet.
● We can say that in distance-vector routing, a router continuously tells all of its neighbours what it knows about the whole network (although the knowledge can be incomplete).
❖ Bellman-Ford Equation
❖ Distance-Vectors & Routing Algorithm
❖ Count to Infinity
❖ Two-Node Loop
▪ Split Horizon
▪ Poisoned Reverse
❖ Three-Node Instability
Link-State Routing
A routing algorithm that creates least-cost trees and forwarding tables is link-state (LS) routing.
❖ Link-State Database (LSDB)
❖ Least-Cost Trees (Dijkstra’s Algorithm)
Path-Vector Routing
A path vector protocol is a network routing protocol which maintains the path information that gets updated dynamically. Updates which have looped through the network and returned to the same node are easily detected and discarded.
❖ Spanning Trees
❖ Creation of Spanning Trees
❖ Path-Vector Algorithm
Distance- Vector Routing – equation
Bellman-Ford Equation: The heart of distance-vector routing is the famous Bellman-Ford equation. This equation is used to find the least cost (shortest distance) between a source node, x, and a destination node, y, through some intermediary nodes (a, b, c, . . .) when the costs between the source and
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com