Please enable JavaScript.

Coggle requires JavaScript to display documents.

5-6. Network Layer (Routing algorithms (Adaptive algorithms (Link state…

- - - - Start with sink, set distance to other nodes to infinity
      - Relax distance to neighbouring nodes
      - Pick the lowest distance node, add it to sink tree
      - Repeat until all nodes are in the sink tree
    - - Every incoming packet is sent out on every outgoing line except the one it arrived on
      - Generates vast numbers of duplicate packets
      - Selective flooding: routers send packets on links which are in approximately the right direction
      - Advantages
        
        Robust: will find a path if it exists
        
        Ensures that a packet is delivered to every node in the network -> good for broadcasting
        
        Requires little in the way of setup: only need to know neighbours
        
        Always chooses the shortest path as it chooses every possible path in parallel: used as a metric against other algorithms
      - Has a hop count that is decremented each time it is sent out again. Discarded when hop count = 0
  - - - Each router maintains a table with the best known distance to each destination and which line to use to get there
      - Tables exchanged with neighbouring routers
      - Global information shared locally
      - Took too long to converge after the network topology changed
    - - More computation but simpler dynamics
      - Local information shared globally
      - Build at regular intervals or when some significant event occurs
      - Packet contains
        
        Sequence: incremented for each new packet sent. Routers keep track of all (source router, sequence) pairs
        
        New -> forward on all lines
        
        Duplicate -> discarded
        
        Lower sequence number -> rejected
        
        Cost to each neighbour
        
        Age: decrement once per second. Discarded when it hits zero
      - Use flooding to distribute packets
      - Problems
        
        Confusion if sequence numbers wrap around -> use 32-bit sequence number
        
        Crashed routers lose track of sequence number
        
        Corrupted sequence number
  - - - Each router knows other routers in the same region only
      - Routers that connect two regions act as exchange points for routing decisions
  - - - Send a distinct packet to each destination
        
        Source needs to have complete list of destinations
        
        Wasteful of bandwidth; slow
      - Multidestination routing
        
        Each packet contains list of destinations / bit map indicating desired destinations
        
        Router checks all dest. to determine set of output lines needed
        
        Router generates a new copy of the packet for each output line and includes in each packet only those dest. that are to use the line
      - Flooding #
      - Reverse path forwarding
        
        When a broadcast packet arrives at a router, the router checks to see if the packet arrived on the line normally used for sending packets to the source of the broadcast
        
        If so, there is a high probability that the route used to transmit the received packet is the best route
        
        the router then forwards the packet onto all other lines
        
        If packet arrived on a link other than the preferred one, discarded as a likely duplicate
        
        Efficient and easy to implement
        
        Sends packet over each link once in each direction
        
        Requires routers to know how to reach all destinations
        
        No need to know sequence numbers
        
        No need to list all destinations in the packet
      - Spanning tree
        
        Subset of network
        
        Contains all routers
        
        No loops
        
        Sink trees are spanning trees
        
        Each router knows which line is in the spanning tree -> copy packet onto all spanning tree lines except the one it arrived on
        
        Excellent use of bandwidth -> generate minimum #packets
        
        Router must know the spanning tree
        
        Link state routing can
        
        Distance vector routing cannot
- - - - Hardware
      - OS
      - Protocols
      - Standards compliance
      - Desire to reduce transmissions due to errors
      - Desire for efficiency in communication channel
    - - Transparent
        
        Packets fragmented / reassembled in each network
        
        Route constrained, more work
        
        Diagram
      - Non-transparent
        
        Fragments reassembled at destination
        
        Less work
        
        Diagram
    - - Header
        
        Packet number: ID of packet
        
        Where is the start of the fragment in the original packet (starts at 0)
        
        End of packet: Is this the last fragment of the packet? (0 or 1)
  - - - Data from transport layer passed to network layer
      - Add dest IP address
      - Add Layer 2 header
    - - Take out layer 2 header
      - Inspect dest address of IP packet
      - Include connection identifier
    - - Take out previous connection identifier header
      - Inspect dest IP address
      - Include ethernet header
    - - Take out ethernet header
      - Inspect IP address
      - Take out network layer header
      - Pass on to transport layer
- - - - IPv4 Header length: 32 bits (Network + host) i.e 2^32 max different addresses
      - Header
        
        20 bytes fixed
        
        Variable bits (optional)
      - 2 versions: IPv4 or IPv6
      - Identification: all fragments of the same datagram will have same ID
      - DF: Don't Fragment byte (now used in path MTU)
      - MF: More Fragment byte (are there more fragments)
      - Fragment offset: where in the datagram the current fragment belongs
      - TTL (time to live)
      - Protocol
      - Header checksum (verify header at receiver's end; payload info already in the header in the transport layer)
      - Source & Dest IP
    - - Given a network prefix by ISP
      - Lowest address / Length (Total 32 bits)
    - - Routing tables
        
        IP address
        
        Subnet Mash
        
        Outgoing Line (physical or virtual)
      - Join multiple IP prefixes into a single larger prefix to reduce the size of a routing table
      - Techniques
        
        Routing within datagram subnet #
        
        Longest matching prefix
        
        Complicates forwarding
        
        Adds flexibility
        
        Check address if it matches the longest prefix i.e. /22
    - - Box that maps one external IP address to many internal (private) IP addresses
      - Need a NAT box/firewall between public and private premises to translate this
      - Amount of IPv4 addresses is limited to 2^32
    - - Diagram
      - Carries size as part of address, but lacks flexibility
  - - - Used for testing and monitoring ambient conditions between hosts and routers
      - Returns error info for traceroute
      - Diagram
    - - Find MAC address of a local IP address
      - When you deploy a system on a network, you can easily set the network address of gateway router in the network -> external routers send messages to the gateway router
    - - Assign a local IP address to a host
      - Gets host started by automatically configuring it
- - - - Services independent of router technologies
      - Transport layer should be shielded from number, type and topology of router
      - Network addressing should use a uniform numbering plan (network identifier)
    - - Packets injected into subnet independently
      - Packets individually routed to destination
      - Internet: Quality of service not easily implemented
      - Flow and error control done by the hosts
    - - Packets travelling between destinations all use the same route
      - Telco: Quality of service is important
  - - - Address associated with each packet
      - Router store packets, get their address
      - Router forwards it on
    - - Post office model
      - Packets routed individually based on destination addresses
      - Packets can take different paths
      - Routing table fixed/vary over time
      - Routing algorithm manages routing table
      - Diagram
      - Remote database access; P2P, VPN, video streaming don't care about lost packets
    - - Telephone network model
      - Packets routed through virtual circuits based on tag number/connection identifier
      - Packets take the same path
      - E.g. multi-protocol label switching (MPLS) network
      - Diagram
      - Cannot lose packets: File transfer protocol, remote login, web surfing (HTTP), email
  - - - Memory vs bandwidth
        
        VC require more space in router memory
        
        Save potential overhead in full addressing of each packet
      - Setup time vs address parsing time
        
        VC require setup time and resources
        
        Fast packet transmission
      - Amount of memory
        
        Datagram require large tables for every possible route
        
        VC needs identifier (hard to compare)
      - QoS vs congestion avoidance
        
        VC use tighter QoS
        
        VC reserve CPU, bandwidth and buffer in advance
      - Longevity
        
        VC can exist for a long time
      - Vulnerability
        
        VC vulnerable to hardware/software crashes: all VCs aborted and no traffic until they are rebuilt
        
        Datagram uses an alternative route
    - - Size of network
      - Failure rate
      - Utilization rate