Tuesday, August 19, 2014

Foundations of Computer Networking chapter-5


Chapter 5 Network        Layer

Network layer - concerned with delivering packets from source to destination, often through many intermediate routers, called Internet Message Processor on the Internet. IP is the routing protocol of the Internet but is often used to mean all the protocols. Used here, IP means the protocol of the network layer.
Router/gateway/bridges
  • Routers form the connection point between the same type of networks (e.g. connect two Internet subnets) by determining where a message should be sent.
    • Would you need a router to connect two LANs on a campus?
       
  • Gateways perform the hardware and software translation necessary to connect dissimilar networks (e.g. X.25 to ATM, Internet to Microsoft Network, broadcast LAN to point-to-point).
     
  • Bridges are simpler versions of gateways, translating only at the MAC level and forwarding frames (e.g. Ethernet to Ethernet, Ethernet to wireless, etc.).

  1. Connectionless - Internet view using the routing protocol IP.
    • No flow control or error handling by subnet.
    • Primitives SEND/RECEIVE PACKET. Each packet contains full address and routed independently.
    • Reliable connections responsibility of higher level transport protocol (TCP).
    • Usually implemented on packet switching network by sending datagrams.
    • Complexity on each host rather than subnet.
  2. Connection-oriented - Phone company view.
    • Connection setup, send/receive data, connection held till disconnect by either end.
    • Subnet responsible for establishing connection.
    • Data delivered in sequence.
    • Flow control.
    • No need for complete address on each packet.
    • Usually implemented on virtual circuit switched network.
    • Complexity on network subnet.
  3. Subnet internal organization
    • Virtual circuit
      • Connection established through set of routers from source to destination, once established all data sent through same routers.
      • Router maintains table of connections to other machines, can have multiple virtual circuits over single physical channel.
      • Using simplex circuit connection process merely needs to pick lowest available outgoing circuit number to next router.
      • When data arrives on a circuit at router, sent out on circuit from table containing outgoing circuit much like time division switch.
      • The router table below forms a full duplex connection between 2 and 3 by routing data arriving on 2 out on 3 and arriving on 3 out on 2 as long as the connection is maintained. Channels 1 and 4 are not in use.

        •  
        In channel  1 2 3 4 5 6
        Out channel 
        		3 2
        		6 5

    • Datagram
      • No fixed set of routers, route determined independently for each packet.
      • Each packet contains full address, router maintains table of destination machines not just those directly connected.
      • Packet routed on best line leading to destination. Best may mean least congested, highest bandwidth, or other criteria.
         
  4. Comparison of Datagram and Virtual Circuit Subnet

    5.     Issue                                                           Datagram                                                 Virtual Circuit
    Connection Setup None Required
    Addressing Packet contains full source and destination address Packet contains short virtual circuit number identifier.
    State information None other than router table containing destination network Each virtual circuit number entered to table on setup, used for routing.
    Routing Packets routed independently Route established at setup, all packets follow same route.
    Effect of router failure Only on packets lost during crash All virtual circuits passing through failed router terminated.
    Congestion control Difficult since all packets routed independently router resource requirements can vary. Simple by pre-allocating enough buffers to each virtual circuit at setup, since maximum number of circuits fixed.
Routing algorithms - determines on which output line an incoming packet should be transmitted. Virtual circuit determines once at setup, datagram for each packet.
  1. Issues
    1. Changing topology due to router crashes, line failures, subnet modification.
       
    2. Fairness and optimality often contradictory. At right, A to A', B to B' and C to C' is optimal but unfair to X and X'.
       
    3. Reducing hops through routers tends to reduce delay and bandwidth consumed, improving throughput of network.
       
    4. Static routing methods do not adapt to changes on traffic, topology, etc. Routes determined off-line and loaded to routers.
       
    5. Adaptive routing methods change routes with traffic, topology, etc. in attempt to optimize on some criteria.
       
  2. Optimality Principle - If router J lies on optimal path from I to K, then J to K also optimal. Diagram below has optimal path I to K of I-C-J-K, hence I-C-J optimal to J since J lies on optimal path I-K.

  3. Sink Tree (minimum spanning tree) - Set of all optimal paths from all sources to a given destination (e.g. the root). Can be found using the shortest path algorithm from destination to all sources giving optimal though not necessarily unique route. Note that a tree has no cycles. Figure a) at right is network b) is sink tree with root at B.
     
  4. Shortest Path Algorithm - Determines the optimal path through a graph based upon the criteria of  number of hops, distance, cost, etc.
    • Topology based, that is it determines connections to use from one router to another.
    • Static, must be recomputed as routers added/deleted.
    • Can be used to construct a sink tree with the destination the sink tree root. One possible application would be for each router to compute the sink tree of a network with itself as the root to determine the optimal output line incoming packets should be transmitted to reach their destination.

Routing methods

  1. Flooding
    • Every incoming packet sent on every outgoing line except the one of arrival, generates duplicate packets.
    • Requires flood damping, usually by each router decrementing a hop counter, discarding packets that have made too many hops. Hop counter must be initialized to the network diameter or the greatest number of valid hops in network. For example, in the figure above (a) above the greatest number of hops needed to traverse the network is 4 (e.g. O-N-J-C-B).
    • Selective flooding - Floods in most likely direction, would require table relating a range of destination addresses to an output line.
    • Uses - Where major failures likely as in warfare, update distributed databases, compare with other methods since flooding chooses all paths, guarantees shortest path selected (ignoring flooding overhead).
       
  2. Distance-vector routing - Used on Internet till 1979.
    1. Distance may be any metric (measure).
    2. Routing table - indexed by each router in subnet, contents is estimate of best output line and distance metric to router.
    3. Method using delay time as metric
      • Send ECHO packet to immediate neighbors which respond back ASAP, record response time in table.
      • Regularly send table with estimate of time to each subnet router to all neighbors.
      • On receiving table from neighbor X and time to X for each table entry (all subnet routers) compute time estimate for going through X to another router Y.
      • If lower to go through X to Y than going through another neighbor, add X to table so packets destined to Y are routed through X.
Router J is connected to A, I, K, and H. J sends ECHO to connected routers and measures delay time of each to respond back with routing table. The delay is added to the time required to route through a router connected to J to another router, the minimum delay route is added to the routing table of J.

    • Problems
      • Used queue length as metric rather than time delay, did not take into account line bandwidth.
      • Takes long time to converge, spreading good news (shorter metrics) quickly, but bad news (failure on subnet) slowly.
        • Count to Infinity Problem - Can occur when a router becomes unreachable. Basic problem that when router X tells Y that it has a path somewhere, Y has no way of knowing that it itself is on the path.
        • For diagram (a), good news from A propagates to E after 4 exchanges (4 hops).
        • For diagram (b), bad news propagates slowly.
          • For example the link from A to B is broken, B discovers that A is unreachable but that C has a metric of 2 to A, possibly through B itself or perhaps through an alternate route.
          • B assumes that A can now be reached in 3 hops through C. B has no way of knowing the path through C to A includes B since it only has information from directly connected routers.
          • On the next exchange, C discovers that A is reachable through B or D in 3 hops so updates table to A in 4 hops.
          • As you can see, the information that A is unreachable propagates slowly, converging toward infinity. The choice of infinity should be the maximum hops + 1 to determine that a router is unreachable.

  1. Link State Routing  - Currently widely used on Internet. Determines complete topology and delays to neighbors, then distributes to all other routers so that each can compute shortest path to any router.
    1. Discover neighbors addresses by sending ECHO packet on all outgoing lines.
    2. Measure the cost to each of its neighbors (time to receive ECHO response divided by two).
      • To include load as a factor the timer is started when ECHO packet placed in queue, to ignore load the timer is started when ECHO packet reaches head of queue.
      • Using load can cause oscillation when two parallel paths are available since the load will be shifted back and forth to the lowest delay channel.
    3. Construct packet containing all information about neighbors just learned. The packet from A would include information about B and E.
    4. Distribute packet to all other routers. Tricky because routers will receive packet at different times so will use different information for routing. Flooding used to distribute with a sequence number for each new packet sent.
      • Routers keep track of (router, sequence number, age), remembering and forwarding the highest sequence numbered ones and discarding duplicates and lower sequence numbered ones as a means of stemming the flood.
      • Aging - Since a rebooted router would start at sequence number 0, all other routers would discard the new but low sequence numbered packets.
        • Age field is initialized to an arbitrary value, perhaps 60, then decremented one by each router forwarding the packet  to prevent packets from circulating forever.
        • A router holding a packet decrements the age once per second. When age = 0 for a packet, the packet is discarded and routing information for that router forgotten so that packets from a rebooted router will eventually be accepted.
    5. Each router computes shortest path to all other routers using most current information from other routers, store in table containing router and output line to router to use.
    6. OSPF (Open Shortest Path First)  - Used on Internet, based on link state, more later.
Differences between link state and distance vector
Distance vector
  • Information indirectly through connected routers
  • Count to infinity problem
  • Convergence routing
 Link state
  • Information directly from all routers
  • No count to infinity problem
  • Shortest path routing
From the link state packets broadcast in (b) between each router of (a)
  • Router B would construct a table with the following entries.
    • The best path to E is through router C,
    • B-C is cost 2
    • C-E is cost 1
    • the total cost of 3 of B-C-E,
    • all other paths are greater cost.
Destination A B C D E F
Router A - C C C F
Cost 4 - 2 5 3 6

Give the table for D.
  1. Hierarchical Routing - Router tables grow proportionally with number of routers, reach point where not feasible for all routers to have full knowledge of network. Used on Internet.
    1. Divide network routers into groups called regions where each router can route packets anywhere within region.
    2. Send all out of region packets to router that connects region to other regions. May have multiple out of region routers depending upon destination.
    3. Benefit - Reduced router table size.
      • The two level network below 17 routers require 4 entries for each region and 2 to 5 entries for routers within a region 3 and 5 respectively, a total of 6 to 9 table entries.
      • A flat network of 17 routers would require 16 table entries for each router.
    4. Cost
      • Increased path length required to route through a router hierarchy.
      • Possible congestion point at router if inter-region traffic heavy.
    5. Optimal - For N routers optimal levels is ln N requiring e ln N table entries per router.
  • Router 1A in Region 1 is connected to Region 4 through router 1C.
    • A packet arriving at 1A destined for 4C would be routed:
    • 1A-1C-3B-4A-4C at a cost of 4 hops = 3 hops 1A to Region 4 + 1 hop to 4C.

  1. Broadcast Routing - Sending packet to all destinations simultaneously. Possible approaches:
    1. Send packet to individual destinations, wastes bandwidth and requires source to have complete list of destinations.
    2. Flooding but generates too many packets and consumes too much bandwidth. Burden on network.
    3. Multi-destination routing, a packet includes list of destinations, router generates new packet with destination list reachable on the output line used. Distribute bandwidth use through routers. Burden on source.
    4. Sink tree or any spanning tree from source router. All routers must know spanning tree used and broadcast received packet on all but the arrival channel. Uses minimum number of packets but global spanning tree information may not be available (for link state shortest path determined from each router not globally, no spanning tree for distance-vector).
    5. Reverse path forwarding attempts to approximate spanning tree routing without tree information.
      1. Source router broadcasts on all channels.
      2. A router receiving broadcast packet notes source router and the arrival channel.
        • If broadcast arrives on channel normally used for sending packets to source router it is assumed to be first time seen so forwarded on all other channels.
        • If broadcast arrived on different channel to source than in router table assumed to be duplicate and discarded.
        • If the source router is not in the table, the packet is broadcast on all but arrival channel with source router and arrival channel of broadcast packet noted in table.
      3. The text considers an example (p369, Fig.5-16).
        • For comparison (b) has source router I at the root of a sink tree.
        • All routers would normally send packets to the source router along the sink tree using the optimal path (e.g. I-B would follow I-F-D-C-B).
        • Using reverse path forwarding the path may differ from the sink tree, on receiving a broadcast packet from the source router on the usual channel, each router would forward packet on all channels except the one received under the assumption the receiving channel was optimal.
        • In this case was simply the reverse of the sink tree path normally used for sending to the packet source.
        • In diagram (c) H sends a packet to K but K expects to receive packets from M so the packet is discarded rather than forwarded.
        • The optimal case using the sink tree requires a maximum of 4 hops maximum (I-N-M-K-L) and 14 total packets.
        • Using reverse path forwarding requires a maximum of 5 hops (4 for I-N-M-K-L plus 1 to B) and 23 total packets with the extra, duplicate packets sent to the leaf nodes.

  • Note that the text in diagram (c) performs too well since the diagram follows the sink tree precisely.
  • A more realistic example is above where the reverse path forwarding (e.g. a packet traveling I-E follows I-H-E) differs from the sink tree path (e.g. I-E follows I-F-A-E).
  • The leaf nodes of the tree are discarded packets.
  • For example, assume O had never received a packet sourced from I.
  • O would receive the I packet from both N and J, assuming that J packet arrived first at O it would be forwarded to N which would discard having already received a packet from I on I channel.
  • When O received the packet from N, having already noted that packets sourced from I arrive first on J, O discards the packet from N.
Give the reverse path tree for a broadcast from D assuming no routers have any forwarding information about other routers.
  1. Multicasting - Sending to a select group. Might be used for selecting video on demand channels.
    • Could use broadcast but inefficient when only a fraction of network is receiver.
    • Multicast routing - Algorithm for multicasting. Requires that destination hosts join multicast group by informing their connected routers. Each router informs neighbor routers so that information about group membership propagates through network. When any group host member sends all other members would receive since each router knows its member hosts and which neighbor routers are part of the multicast subnet.
      1. Each router computes spanning tree for full network with itself as root.
      2. When host sends multicast packet, the first router prunes spanning tree, retaining only those lines leading to group member hosts.
      3. Multicast packets are forwarded only on those lines along the spanning tree.
    • Problems - Scales poorly for large networks since based on n group spanning trees each with m members requiring storage for mn spanning trees.

Dijkstra's Shortest Path Algorithm

The shortest path algorithm is in fact a general graph minimization algorithm where the metrics of the graph edges can represent distance, cost, time, etc. It is important in networking because of the desirability of minimizing network resources and is therefore employed by many routing algorithms.

The general idea behind the algorithm is to compute the shortest path from the destination node to other nodes until the starting node is reached. When complete each node points to its predecessor node on its own shortest path to the destination. From the starting node, the shortest path to the destination is then through the list of predecessor nodes.
Briefly, the algorithm given here is:
  1. k = destination
  2. At the k node,
    • Examine only nodes connected to k not already with shortest path to the destination.
    • Of those nodes, make k the predecessor node if the the path through k to the destination is shorter than previously examined paths to the destination.
  3. Find the new node k with the shortest connection that is not already on the shortest path to the destination and make it part of the shortest path.
  4. If k is the starting node then finished, otherwise go back to 2.
In the following, note in panels (c) that node G reached A through A at a distance of 6 and in (d) that node G reached A through E at a distance of 5. Since that produced the shortest distance of any connections (all eventually back to A) the G node was placed permanently with its shortest path to A through E.
Another approach is to consider 3 abstract data structures:
  1. queue ordered by minimum cost to reach a node, unexpanded nodes are added when a new node is expanded
  2. path list containing node and predecessor pairs
  3. closed list that contains nodes that have been expanded, we'll clean duplicates from the queue also.
The node at the head of the queue is always chosen for expansion and is added to the path and closed lists.
We halt when the goal is reached.
Queue Path Closed
A    
B2, G6   A
E4,G6,C9 (B,A) A, B
G5,G6,F6,C9 (E,B),(B,A) A,B,E
F6,C9,H9 (G,E),(E,B),(B,A) A,B,E,G
H8,C9,H9,C9 (F,E),(G,E),(E,B),(B,A) A,B,E,G,F
C9,C9,D10 (H,F),(F,E),(G,E),(E,B),(B,A) A,B,E,G,F,H
D10,D12 (C,F),(H,F),(F,E),(G,E),(E,B),(B,A) A,B,E,G,F,H,C
  (D,H),(C,F),(H,F),(F,E),(G,E),(E,B),(B,A) A,B,E,G,F,H,C,D

What is the final path for A-D?
 



Use Dijkstra's Algorithm to find the shortest path from A-D for 

Dijkstra's Shortest Path Algorithm 
 #include <iostream.h>                           //  Network from Tanenbaum text
 #define MAX_NODES 8                           //  Distance from i to j node
 #define INFINITY 1000000000                 //  0 if i=j or not connected
 int n;                                                   //         0  1  2  3  4  5  6  7
 int dist[MAX_NODES][MAX_NODES] =    { //         A  B  C  D  E  F  G  H
                                                                     {0, 2, 0, 0, 0, 0, 6, 0 }, //A 0 
                                                                     {2, 0, 7, 0, 2, 0, 0, 0 }, //B 1
                                                                     {0, 7, 0, 3, 0, 3, 0, 0 }, //C 2
                                                                     {0, 0, 3, 0, 0, 0, 0, 2 }, //D 3
                                                                     {0, 2, 0, 0, 0, 2, 1, 0 }, //E 4
                                                                     {0, 0, 3, 0, 2, 0, 0, 2 }, //F 5
                                                                     {6, 0, 0, 0, 1, 0, 0, 4 }, //G 6
                                                                     {0, 0, 0, 2, 0, 2, 4, 0 }  //H 7
                                      };
 typedef enum {permanent, tentative} labelID;
 //                        start  destination
 void shortest_path(int s, int t, int path[]){

        struct state {
                 int       predecessor;
                 int       length;
                 labelID label;
         } state[MAX_NODES];

         int i, k, min;                    

         n = MAX_NODES;
         for(i=0; i<n; i++) {                                 // Initialize state
                 state[i].predecessor = -1;
                 state[i].length = INFINITY;
                 state[i].label = tentative;
         }

         state[t].length = 0;
         state[t].label=permanent;   
         k=t;                                                    // Start at destination.

         do {                                                    // Label current shortest nonzero tentative paths  
            for(i=0; i<n; i++)                              // from all i connected to the current k node
                 if(dist[k][i] != 0 && state[i].label == tentative) 
                     if(state[k].length+dist[k][i] < state[i].length) {
                         state[i].predecessor = k;
                         state[i].length = state[k].length+dist[k][i];
                     }

            min = INFINITY;                                // Find tentatively labeled node with smallest length
            for (i=0; i<n; i++) 
                  if( state[i].label == tentative && state[i].length < min) {
                      min=state[i].length;
                      k=i;
                  }

            state[k].label = permanent;                // Make smallest path length permanent
         } while(k != s);                                    // k=current node, s=start

         i=0;
         k=s;
         do {    path[i++]=k;                             // Copy path from start to destination
                   k=state[k].predecessor;
         } while (k>=0);
 }

 void main(void) {
         int i, s=0, t=3;                                     // s=start node t=destination node
         int path[MAX_NODES];

         shortest_path(s, t, path);
         i = 0;
         cout << "Path ";
         do {    cout << path[i] << " ";
         } while (path[i++] != t );
 }
Solution: Path 0 1 4 5 7 3

Congestion Control Algorithms

Congestion occurs when demand exceeds capacity at any point in network. Demand could be for any resource such as channel bandwidth or router buffer storage.
 
Router internal buffer use

When available buffers exhausted router forced to drop incoming packets causing  sharp reduction in number of packets delivered.		 Congestion causes performance degradation
  1. Common reasons for congestion on router - Congestion can occur on a router when packets arrive at a greater rate than possible to forward. Congestion can be sporadic or long term. When congestion occurs, packets must be discarded by the router. Congestion occurs at a bottleneck when:
    1. Packets arrive on several channels to be forwarded on a single channel.
    2. Incoming channel has a higher bandwidth than outgoing channel.
    3. Channel bandwidth is sufficient but router CPU processing is too slow to handle bookkeeping (queuing, routing table updates, etc).
    4. Router lacks sufficient memory buffer space.
    5. Under an end-to-end reliable protocol (e.g. TCP), even with infinite memory, congestion can get worse because packets have timed out (e.g. moving from queue back to front on router or due to delay in acknowledging on a receiver) resulting in duplicates, adding to the congestion.
      Is it worse for congestion to discard a data or an acknowledgement packet?
     
  2. Self Feeding - Congestion gets worse.
    1. One router becomes congested, starts discarding packets.
    2. Sending router waiting for acknowledge cannot discard packet until acknowledge received, times out and resends. Its buffers cannot be released so that it also becomes congested. Not the case of Internet, is the case of a reliable network.
       
  3. Congestion and Flow Control
    1. Congestion control is concerned with ensuring the subnet can accept the requested traffic, a global issue.
      • Can be managed by rerouting packets dynamically over network, possibly around congestion.
      • Best managed by routers.
      • Recall that link state routing exchanges a metric such as delay among routers allowing them to calculate the best route to a subnet destination.
    2. Flow control is concerned with whether the receiver can accept the traffic from the sender, an issue only between the two ends.
      • Best managed between the two ends.
    3. Congestion control is sometimes implemented using flow control, when the congestion occurs the host sources are told to slow down.
      • One possible problem with this approach is that under network congestion the slow down message adds to the traffic and may itself be discarded.
      • Another is that routers along the path leading to the congested router should participate in congestion control by routing around congestion or otherwise reducing the traffic at the congested router.
         
  4. General Principles of Congestion Control
    1. Open loop - Example: doctors office that schedules patients into time slots with no information about future office congestion state attempting to prevent congestion by estimating the time the doctor will spend with each patient.
      • Design attempts to prevent congestion from occurring through decisions on accepting new traffic, when to discard packets, and scheduling.
      • Decisions made without regard to current state depending upon good design to avoid congestion.
    2. Closed loop - Example: heating control system. Uses feedback to adjust to traffic changes. Has three parts:
      • Monitor system to detect when and where congestion occurs. Congestion measured by percentage of packets discarded, average packet delay, etc.
      • Pass information to places where action can be taken, usually along the path back to the traffic source. Congested router sending notice to source increases traffic.
      • Adjust system operation to correct the problem.
        • If router claims congestion too soon and source stops sending completely on receipt of congestion notice but restarts at same rate, traffic will oscillate and never converge to a steady rate.
        • Waiting too long makes system sluggish, nullifying benefit of congestion control.
        • Averaging of congestion over time can provide better overall measure of when to act.
           
5.3.2 Congestion Prevention Policies - Implemented at several levels, policies that affect congestion are:
Layer Policies
Transport 
  • Retransmission policy - go back n heavier load due to number of retransmits than selective repeat
  • Out-of-order caching policy -  go back n discards, selective repeat keeps
  • Acknowledge policy - Piggybacking ACKs versus separate but waiting to piggyback may result in timeout causing retransmit.
  • Flow control policy - Small window limits number of outstanding packets reducing data rate.
  • Timeout determination - Waiting too long causes packets to back up at source. Timing out too soon can produce retransmit duplicates adding to traffic.
Network
  • Virtual circuits versus datagram inside the subnet
  • Packet queuing and service policy - Number of queues per input/output line, order packets processed in queue.
  • Packet discard policy - Choice of which packet to discard.
  • Routing algorithm - Can avoid congestion by spreading traffic.
  • Packet lifetime management - Time to live used to discard packets, if too long orphans may clog network, too short may discard valid but slow packets. 
Data Link
  • Retransmission policy - same as transport layer
  • Out-of-order caching - same as transport layer 
  • Acknowledgment policy - same as transport layer
  • Flow control policy - same as transport layer
5.3.3 Traffic Shaping - Bursty traffic one cause of congestion. Open loop solution requires predictable rates that do not exceed some maximum.

Leaky Bucket - uses a finite queue as buffer where host packets enter queue at anytime but forwards packets to router at constant rate, creating an even flow from host.
  • Packets discarded if queue size exceeded.
  • Leaky bucket metaphor is that water can be added in bursts to the bucket (queue) but leaks out of a hole (channel) in steady stream and overflows when full discards packets).
     
5.3.4 Congestion Control in Datagram Subnets
Choke Packets - Router monitors output line utilization (why monitor output line?) to determine if utilization threshold exceeded using:
unew = auold + (1-a)f
where
   a - rate forgets recent history, 1 forgets nothing, 0 forgets all.
   f - 0 when not in use or 1 when in use, the instantaneous line utilization
   u - 0.0 to 1.0 recent line utilization
Example: a=1, f=0 no change unew = uold
Example: a=0, f=1 then unew = 1 or 100% utilization
 
When u > threshold enters warning state:
  • new packet for congested output line triggers sending of choke packet to source
  • new packet tagged choked so it won't cause more choke packets on down the router line to destination.
  • Source host required to reduce traffic by about 1/2 each choke packet received, after some fixed time (e.g. timeout interval) without choke packet host can slowly increase traffic.

IP uses two windows on source host
Smaller windows utilize less available network capacity. Why?
  • Uses fast stop/slow start which halves window each time choked packet received, increases at slower rate whenever fixed time interval expires without additional choke packets or acknowledge received. More details in Chapter 6.
Hop-by-Hop choke packets
  • High bandwidth over long distances make returning choke packets the congestion source too slow.
  • A 100 Mbps channel with an end-to-end propagation time of 10 ms. would hold 1,000,000 bits.
  • During the time a choke packet traveled to the source 1,000,000 additional bits could arrive at a router and 1,000,000 would be on the way.
Hop-by-Hop requires each router to reduce packet rate when a choke packet arrives providing immediate relief. The choke packet eventually reaches the source to reduce the overall packet rate.

5.5 Interworking - Connecting two or more networks, may be same or different networking protocols (IP, SNA, IPX, AppleTalk, etc.)
  1. Important terms - Gateway means any device that connects two or more different networks.
    • Repeaters copy individual bits between segments of same LAN such as between segments on same 802.3
    • Bridges store and forward (buffer) data link frames between LAN's such as 802.3 to 802.5
    • Multiprotocol routers similar to bridges, forward packets between different networks such as IP to IPX.
    • Transport gateways connect byte streams in the transport layer.
    • Application gateways allow interworking above layer 4, such as mail systems.
  2. Half gateway - Two gateways connected by wire running an agreed upon protocol between and other protocol on either network side.
  3. Bridges vs Routers
    4. Bridge handles data link frames whose data load contains a network packet, examines MAC address. Cannot examine data load to determine whether IP, IPX, etc.
    Nesting of Frame/Packet/Segment

    Ethernet Frame at Bridge
    Internet Packet at Router  - does not handle frames but the data load from the frame. Can determine whether IP, IPX, etc. networking protocol.
    • Often bridge and router combined in one system. Key difference is how far up the protocol stack the data is handled.
5.5.1 How Networks Differ
Item Some Possibilities
Service offered Connection-oriented vs connectionless
Protocols IP, IPX, SNA, AppleTalk, ETC.
Addressing Flat (802.x) vs hierarchical (IP)
Multicasting Yes or no (also broadcasting)
Packet size Every network has its own maximum
Quality of service May be present or absent (IP)
Error handling Reliable, ordered, and unordered delivery
Flow control Sliding window, rate control, other or none
Congestion control Leaky bucket, choke packets, etc.
Security Privacy rules, encryption, etc.
Parameters Different timeouts, flow specifications, etc.
Accounting By connect time, by packet, by byte, or not at all
5.5.2 How Networks can be Connected
  • Physical - Hubs or repeaters perform electrical or other physical connections
  • Data Link - Bridges and switches (on Ethernet what is the difference between hub and switch?).
    • In the figure below (a) connects two Ethernet LANs via a switch.
    • S encapsulates IP packet in frame addressed to D and transmits on LAN1.
    • Switch examines frame address and forwards onto LAN2 to D, no changes to frame.
  • Network - Routers examine packet to determine where to forward.
    • In the figure below (b) connects two Ethernet LANs via two routers connected point-to-point.
    • S encapsulates IP packet in frame addressed to router and transmits on LAN1.
    • Source router examines packet address, locating destination network in routing table and forwards onto point-to-point connection, no changes to packet.
    • Destination router examines packet address, translates into frame address of D (using ARP table) and transmits on LAN2.
  • Transport - Gateway that translates between two transport protocols (TCP and SNA).
  • Application - Gateway that translates between two application protocols (Internet email format to X.400 use different addressing scheme, etc.)

5.5.3 Concatenated Virtual Circuit - All packets traverse same path.


  1. Host - connected to subnet, to establish connection to host in remote external subnet sends full destination address to router.
  2. Router - builds circuit to gateway providing access to external subnet nearest destination.
  3. Gateway - records circuit, builds circuit to next subnet. Process continue till destination reached. Relays packets converting formats and circuit numbers as required.

    4. Advantages
    1. Buffers can be reserved in advance.
    2. Sequencing automatic.
    3. Short headers.
    4. avoids delayed, duplicate packets.
    Disadvantages
    1. Table space required for each open connection.
    2. No alternate routing to avoid congestion.
    3. Vulnerable to router failures.
    Note that quality of service is that of the lowest providing network. If one of them does not provide reliable delivery then circuit is unreliable.
5.4.3 Connectionless Internetworking
  1. Host - injects packet on subnet, fully addressed to destination.
  2. Router - Selects output line to gateway leading to destination.
  3. Gateway - Converts from one network format to another.
    • Generally not possible to convert one protocol to another due to addressing, size of packets, etc. incompatibilities.
    • Consider IP to IPX would require every IPX router and host in the world to have IP address and vice versa, and a database of converting between addresses.
  4. Advantages
    • Can be used over subnets that do not use virtual circuits.
    • More robust to router failure.
    • Can route around congestion giving better response.
  5. Disadvantages
    • More potential for congestion but more opportunity to adapt
    • Long headers since each packet routed individually.
5.4.4 Tunneling - Avoids interwork conversion problems. When source and destination networks same, at gateway place packet inside intermediate network packet, deliver to destination gateway using intermediate network, remove unchanged packet and forward using original network protocol.

Example: IPX networks can be connected by tunneling through an IP network by connecting:
IPX network-------IPX/IP gateway--------IP network--------IP/IPX gateway--------IPX network
 
  1. Host - inserts packet on IPX subnet.
  2. Source IPX/IP Gateway - Accepts IPX packet and wraps IPX packet in IP packet data load, sends to destination gateway over IP network.
  3. IP Routers - Examine only IP packet for routing to destination IP/IPX gateway.
  4. Destination IP/IPX Gateway - Extracts IPX packet from IP packet data load, inserts IPX packet onto IPX subnet.

5.4.5 Internetwork Routing
  • Two level - Interior and Exterior
    • Interior Gateway Protocol (IGP) - Subnet routing within subnet, all subnet routers use same protocol. Uses routing metric to determine best path.
    • Exterior Gateway Protocol (EGP) - Internet routing through subnets using standard routing algorithms. Gateways share a common EGP but packet received at a gateway tunneled through intervening subnet. EGP routers cannot determine best path because different metrics may be used on each subnet through which packet is tunneled.
5.4.6 Fragmentation - All packet networks have a finite packet size
  • Problem
    1. Limit packet size to minimum of any intervening subnet OR
    2. Break up packet and reassemble (fragment)

    • Fragmentation Strategies and Their Problems
      1. Transparent
        • Gateway breaks up oversized packets, addressing each fragment to same exit gateway where reassembled.
        • Problems
          1. Exit gateway must know when all packets received requiring count bits or end of fragment bits in each fragment.
          2. Overhead of fragmenting and reassembly.
          3. May be reassembled at exit gateway only to be fragmented again at a later gateway later.
      2. Nontransparent - Used on Internet
        • Gateway breaks up oversized packets, each fragment treated as original, addressed through any gateway to destination host.
        • Problems
          1. All hosts must be capable of reassembly.
          2. Increased overhead due to smaller packets with full addressing.
          3. Header must have enough room to hold sequence numbers of fragment needed for reassembly. Recall that each packet already carries a sequence and possibly an acknowledgment number. Since fragments may themselves be fragmented, the first fragmentation might use numbers 0, 1, 2, 3, ..., the second fragmentation 0.0, 0.1, 0.2, ..., and the third 0.0.0, 0.0.1, 0.0.2, etc.
          4. If single fragment fails to arrive entire packet must be resent.
            • Cause seen when  fragment 2 of 10 fragments lost, sending host times out and resends entire packet since it had no knowledge of fragmentation. New packet may take different route where the original packet results in a fragment 2 of 5 fragments.
        • Sequence number solution
          1. Define elementary packet size that all can handle, say a byte. A packet with 100 data bytes would be considered to have 100 fragments.
          2. Each internet header contains sequence, fragment number, and end of fragment bit. For byte size fragments, fragment number and the number of starting byte of packet the same.
          3. All fragments same size except perhaps last.

          Original packet
          Packet 27 Fragment 0 End of Packet bit 1 A B C D E F G H I J K L
          Fragment into two packets
          Packet 27 Fragment 0 End of Packet bit 0 A B C D E F G H
          Packet 27 Fragment 8 End of Packet bit 1 I J K L
          Fragment into 12 packets
          Packet 27 Fragment 0 End of Packet bit 0 A
          Packet 27 Fragment 1 End of Packet bit 0 B
          Packet 27 Fragment 2 End of Packet bit 0 C
          Packet 27 Fragment .... End of Packet bit 0 ....
          Packet 27 Fragment 11 End of Packet bit 1 L
 
5.4.7 Firewalls - Filter traffic based on some criteria
Packet filter - Standard router that inspects incoming/outgoing packets forwarding those that satisfy some criteria.
  • Criteria - Typically allowing/disallowing access to specific addresses/ports. Usually table driven, configured by system administrator.
  • Incoming - Simple since can block all incoming packets for ports used by Telnet, FTP, HTTP, etc.
  • Outgoing - More difficult since off-site locations can use any port or assign dynamically
Application filter - Examine content of packet data to determine how to process. Operates at application layer.
  • Example - Block access to certain words in Web page title.
  • Problems - Access usually not limited to single entity (e.g. dialups)
The architecture of a firewall with a secure computer bracketed by two packet filters. To secure a host one filter restricts packets from outside and another restricts packets from inside. Known as the double moat approach.
Only restricting outside packets implies that inside is fully trusted, that none of the organization computers have been compromised.
5.5 Internet Network Layer
5.5.1 IP Protocol

    • Header specification - 20 or more bytes
      1. Version - Protocol version
      2. IHL - Header length in 32-bit bytes, not constant. Between 32-bit units of 5 (20 bytes) and 15 (60 bytes)
      3. Type of service - Combination of reliability and speed.
      4. Precedence - Delay, Throughput, Reliability. In practice is ignored.
      5. Total length - Length of entire datagram, maximum 65535.
      6. Identification - All fragments have same identity.
      7. DF - Don't Fragment, destination cannot reassemble. 576 minimum all machines must accept.
      8. More Fragments - When clear (0)  means this is the last fragment.
      9. Fragment offset - Fragment number within a datagram, minimum of 8 byte fragments, 13 bits allow maximum of 8192 fragments per datagram, giving 65,526 data bytes per datagram maximum.
      10. Time to live - Maximum of 255, counter decremented each router hop until 0 then datagram discarded. Used to kill orphan packets.
      11. Protocol - Used by destination after reassembling datagram to determine which transport process should receive, TCP, UDP, etc.
      12. Header checksum - Verifies header only. Recomputed at each hop since TTL field changes.
      13. Source and Destination Address - 32-bit from the IP form xxx.xxx.xxx.xxx where each xxx is 0-255 value (8-bits).
      14. Options - Escape to allow later versions to include new information.
        • Strict source routing - List of routers to follow.
        • Record route - Routers append address, limited to 10 32-bit addresses (difference between 5 and 15 byte headers).
5.5.2 IP Addresses - 32 bit in form of Network/Host

    • Address Formats
      • A - Few networks (127) with many hosts (16,777,216) 1.0.0.0 to 127.255.255.255
      • B - More networks (16,382) with fewer hosts (65,536) 128.0.0.0 to 191.255.255.255
      • C - Many networks (2,000,000) with few hosts (256) 192.0.0.0 to 223.255.255.255
      • D - Multicast 224.0.0.0 to 239.255.255.255
      • E - Future 240.0.0.0 to 247.255.255.255
    • Booting - 0.0.0.0 used for booting.
    • Broadcast - Address of all 1's broadcasts on local network.
    • Loopback - 127.xxx.yyy.zzz used for loopback testing, transmitted packets processed locally as though incoming.
IP routing
Each router has table of (network,0) for distant networks and (this-network, host IP addresses) for local hosts.
When packet arrives at router:
  • Destination address looked up in routing table
    • If for distant network, forwarded to next router
    • If local host sent directly onto LAN
    • If unknown network sent to default router
5.5.3 Subnet and Classless Addressing - Appear as one network to outside but consists of multiple networks inside.

  • Problem - All hosts must have same network address for routing packets. A Class C network limited to 254 hosts, more hosts need new network and new router. LAN can easily have more than 254.
  • Solution - For Class B all 65,536 hosts have same network address
    1. Main router has table with all 65,536 entries with address of sub-router. Requires large table and manual entry of host addresses.
    2. Group hosts into subnets using any organization of the host bits. All hosts on sub-router have same subnet address.
  • How - Routers maintain two level hierarchy table of a mix of distant network (network, 0) and local host (this network, host) addresses associated with a network interface.
    • Arriving packets either forwarded to next router when destined for another network or directly to subnet of local host.
    • Class B using subnets has association of (this network, subnet , 0) or (this network, this subnet, host) number for network interface. Creates three level hierarchy on subnet which gateway router uses to route packet to subnet router or host if on this subnet.
  • Mask -  Router AND's the IP with subnet mask to recover the network and subnet number. Reduces size of router table since does not contain all hosts on this network.
    • Class C network routers often have a subnet mask of 255.255.255.000 so that the router can direct packet to interface on which host 1-254 is connected.
    • For example, 194.160.25.3 when ANDed with 255.255.255.0 by the router produces 194.160.25.0, the network and subnet having 254 hosts (0 and 255 are reserved). IPs in the range of 194.160.25.0-194.160.25.255 would be routed to this subnet for delivery to a host.
    • Class B network routers mask using 255.255.0.0 for network address.
    • For example, to determine packet destination
               149.160.023.147
      AND   255.255.000.000
               149.160.000.000
      Main router ANDs address with mask to determine destination is on its network 149.160.0.0.
    • CIDR Notation (Classless InterDomain Routing) - Specifies mask associated with address by appending a / and size of mask in decimal.
      • Does away with classes because of number of wasted IPs, Class B often too big, Class C too small.
      • Allocates variable sized blocks, can allocate in blocks of powers of 2.
      • Makes routing more complicated.
        • Each router must now contain network address and mask.
        • Extracts destination IP and applies mask. Possible for result to match several networks, longest mask used.
      • A CIDR number 128.211.0.0/16 would imply a 16-bit mask of 255.255.0.0 for 128.211.0.0 subnet.
      • 128.211.0.16/28 specifies a 28-bit mask of 255.255.255.240 for subnetting addresses 128.211.0.16-128.211.0.31.
      • 128.211.0.8/29 specifies a 29-bit mask of 255.255.255.248 for subnetting addresses 128.211.0.8-128.211.0.15.
      • Note that host address with only 0's or 1's are not allowed so the 128.211.0.8/29 subnet has 8 host addresses 0-7 (binary 000-111) but only 6 valid host addresses 1-6 (binary 001-110).
  • Example - Class B
    149.160.23.147 is 10010101.10100000.00010111.10010011
                      Class B|  Network   | Subnet |       Hosts             |
    Determine destination network at main router
             149.160.023.147
    AND   255.255.000.000
             149.160.000.000
    Main router determines which of 256 destination subnets to route packet
             149.160.023.147
    AND   255.255.255.000
             149.160.023.000
    Subnet router determines which of 256 destination hosts to route packet, on LAN table would be in form of (host IP, destination LAN)
  • Example - Table diagramming IP subnetting courtesy David Seckinger.
For a Class B network, what mask is needed for 16 subnets?How many hosts would be on each?

5.5.4 Internet Control Protocols - IP used for packet transfer
  • ICMP - Used to test and control the Internet. ICMP encapsulated within IP packet. Some examples:
    • Source Quench - A choke packet router sends to host when packet discarded due to no more buffer space available. Treated by source as a timeout.
    • Time Exceeded - Sent to host when TTL (Time To Live) field reaches zero or from host if reassembly timer exceeded before all fragments arrive.
    • Destination Unreachable - Sent to host when packet cannot be delivered.
    • Echo Request/Reply - On receipt of a request, any computer must reply with the same data. Used by ping and traceroute (Microsoft tracert).

  • ARP - Learn destination datalink address of a receiver on a LAN by broadcasting destination IP address. Datalink does not understand higher level IP addressing (it may be 802.3 or 802.5 on LANs). Each host builds ARP table containing (IP, datalink) correspondence. Table entries grow stale and are deleted after a few minutes to allow changes to LAN hosts.
    1. If sender does not know datalink address of receiver, broadcast to all LAN stations ARP request containing receiver IP. Host W broadcasts request on LAN.
    2. If receiver on LAN responds with ARP containing datalink address. Host Y responds to host W with datalink address.
    3. If receiver NOT on LAN, router responds  to ARP sending its datalink address (proxy ARP) and the router would itself ARP the receiver to learn its datalink address. Sending host uses the router's datalink address, the router unpacks frame, determines destination LAN for receiving host IP, and forwards packet.
  • RARP - Reverse ARP, knows datalink address but needs IP. Useful when booting diskless host that knows its datalink address but needs IP to download memory image boot records from an IP server. Requires a RARP server that contains datalink to IP address table, server must be on LAN since datalink broadcasts are not forwarded by IP routers but by bridges.
  • Bootp - Allows a single boot server on the Internet versus a LAN. Uses UDP which contains IP of destination boot server, booting host has IP of boot server and default router address.
5.5.5 Interior Gateway Routing Protocols
  • RIP (Routing Information Protocol)
    • Based on distance vector routing, works well for small systems but suffers from count-to-infinity and generally slow convergence.
    • Implemented as daemon routed on most Unix systems.
    • Main advantage is requires little configuration.
    • Use UDP for messaging so unreliable.

    Format of a RIP update message. Message contains a list of destinations and a distance metric to each. RIP measures distance in hops.
  • OSPF (Open Shortest Path First) - Used within an organization where all routers run same routing algorithm
    • Open (non-proprietary).
    • Supports variety of distance metrics from link-state routing information using shortest path algorithm.
    • dynamic algorithm changing routing as topology changes since routers exchange routing information.
    • Supports routing based on type of service by running shortest path multiple times based on different metrics, delay, throughput, and costs
    • Load balancing, uses multiple routes rather than shortest in hops.
    • Hierarchical network support since networks have grown too large for one router to maintain table. Each router configured to know which other outers are in its hierarchy. To connect hierarchy, one router in each hierarchy configured to communicate with one or more routers in other hierarchies.
    • Authenticated Message Exchange between two routers to ensure messages only accepted from trusted source as security to prevent spoofing by bogus routing information.
5.5.6 Exterior Gateway Routing Protocol: BGP (Border Gateway Protocol) - Used to connect organization networks running own version of an interior gateway routing protocol, must deal with politics. May not allow certain transit traffic, etc.
5.5.8 Mobile IP - When IP's move to different network but keep same IP
    Each site with mobile users must support home agent that acts on behalf of the mobile user, essentially forwarding any packets received for the mobile IP to its new network.
  1. Mobile IP
    1. When mobile IP arrives in new area listens for advertisement of services from foreign routing agents or broadcasts its arrival and waits for foreign agent response.
    2. Registers with foreign routing agent giving IP home routing agent address and data link address.
  2. Foreign routing agent
    1. Foreign agent contacts home routing agent sending in-care-of address to home routing agent.
    2. Receives packets for mobile IP from home routing agent, forwards to mobile IP.
  3. Home routing agent
    1. Routes packets for mobile IP to a willing foreign routing agent where mobile IP has moved, packet essentially tunneled through Internet (an IP packet inside an IP packet) from home router to foreign routing agent.
    2. When a packet arrives at home network for mobile IP the router ARP is responded to by the home agent with its data link address. Home agent may also send gratuitous ARP to router to replace mobile IP data link address with its own so that it will receive any packets destined for the mobile IP.
    3. To reduce latency due to tunneling through the home agent, the sender is given the IP address of the foreign agent to tunnel packets directly to the mobile IP.

5.5.9 CIDR IPv4 - Classless InterDomain Routing - Delaying the IP network explosion problem
  • Problem - Routers use two level table of all other routers on other networks and hosts on own. Class C networks require 2,000,000 table entries for routers and 256 for hosts; 512,000,000 Class C addresses. Routers must exchange table information periodically.
  • Possible Solutions
    • Deeper Heirarchy - Have IP address contain country, state, etc. Requires larger IP number and wasteful for small countries.
    • CIDR - Allocate contiguous, variable sized blocks of Class C addresses totaling 2,000,000*256, among regions. An additional 32-bit mask is assigned with the block that is ANDed by routers to extract the base Class C block address. All routers for that region would receive the starting block and mask. Can be used for A, B, and C networks. North America has addresses 198.0.0.0 to 199.255.255.255. Any router in the world receiving a packet starting with 198 or 199 routes the packet to its North American router. 
      • Suppose IUS needed 1024 addresses (210) and IUPUI needed 4096 (212) . IUS could be given addresses 198.24.128.0 through 198.24.131.255 and mask 255.255.252.0; IUPUI 198.24.0.0 through 198.24.15.255 and mask 255.255.240.0. 
      • All routers would need to be informed of the IUS network address and mask.
      • A packet arriving at a router would have destination address ANDed with each mask until the result matched an assigned subnet. Router forwards to nearest router to subnet or, if connected to subnet, to host directly.

      •             255.255.252.0 = 11111111 11111111 11111100 00000000
     AND 198.024.130.5 = 11000110 00011000 10000010 00000101
     IUS  198.024.128.0 = 11000110 00011000 10000000 00000000
5.5.10 IPv6
  • Support billions of hosts - uses 16 byte addresses, (e.g. 8000:0000:0000:0000:0123:5678:CDEF), IPv4 addresses could be written as ::192.31.20.46
  • Reduce size of routing tables - 16 byte addresses allow deeper hierarchy.
  • Simplify protocol so routers can process packets faster - header reduced to 7 fields from 13 in IPv4. Removed checksum field since transport and data link protocols normally have own and network communication highly reliable.
  • Provide better security - supports state-of-the-art checksum authentication and user optional encoding algorithm for privacy. Encryption is essentially an end-to-end issue.
  • Attention to type of service, particularly real-time data - Priority field defining slow and fast data.
  • Aid multicasting by allowing scopes to be defined - Multicast addresses with 4-bit scope field and 112-bit group field.
  • Support roaming hosts - not supported directly, still possible via foreign/home agents
  • Allow protocol to evolve - Much of IPv4 header pushed into higher level, end-to-end protocols (e.g. checksum) which can be implemented independent of routing issues.
  • Permit old and new protocols to coexist - not compatible with IPv4 but is with TCP, UDP, ICMP, DNS, etc. except for larger addresses. Initially islands of IPv6 tunnel through IPv4 networks until eventually merge into a complete IPv6 network. Current investment in IPv4 routers too large.

 
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)