Google Answers Logo
View Question
 
Q: "Internet Engineering" ( Answered,   0 Comments )
Question  
Subject: "Internet Engineering"
Category: Reference, Education and News > Teaching and Research
Asked by: sam7074-ga
List Price: $60.00
Posted: 19 Oct 2004 06:26 PDT
Expires: 18 Nov 2004 05:26 PST
Question ID: 416927
Consider a LAN segment with n nodes (E1, E2, ?En). Suppose that En is incorrectly
configured and it thinks that its data link address is all 1?s, i.e.
the data link layer broadcast address. Assume
an implementation where a node that receives a packet (datagram) with
a network layer address (i.e. IP
address) of another node attempts to forward the packet (datagram) to
the appropriate destination IP address .
Describe what happens when some node (e.g. E1) attempts to transmit an
IP datagram to node En. Give the
sequence of events. (Hint: assume that E1 wants to send IP datagrams
to En, and first sends ARP request to
obtain the link layer address of En).
Answer  
Subject: Re: "Internet Engineering"
Answered By: maniac-ga on 20 Oct 2004 17:19 PDT
 
Hello Sam7074,

The short answer is a "broadcast storm" or "network meltdown"
  http://www.webopedia.com/TERM/B/broadcast_storm.html
  http://www.webopedia.com/TERM/N/network_meltdown.html
There is a similar phrase in the Jargon file at
  http://catb.org/~esr/jargon/html/C/Chernobyl-packet.html
which basically describes a situation like this.

The third sentence:
  "Assume an implementation where a node that receives a packet
  (datagram) with a network layer address (i.e. IP address) of
  another node attempts to forward the packet (datagram) to the
  appropriate destination IP address"
is key in this interpretation. Because of this sentence, the broadcast
storm will occur.

The longer answer follows.

Let us start with the definiton of the Address Resolution Protocol
(ARP) and how this misconfigured system will cause the broadcast
storm.
  http://www.faqs.org/rfcs/rfc826.html
This RFC defines the sequence of actions for Ethernet (and by similar
ways - for implementation on other data links). You may want to follow
along with the example about two thirds of the way down the RFC.

[1] The first message (from E1) is a data link broadcast, requesting
the data link address of EN.
 - E2 gets it and discards it.
 - E3 gets it and discards it... repeat ...
 - EN gets it and processes it.
The first message is discarded by all other hosts (even with the third
sentence) because ARP requires that behavior.

[2] Based on this message, EN knows how to respond to E1. EN will
respond directly to E1 with a message that includes its (EN's) data
link address (broadcast).
 - E1 gets it and processes it.
 - E2 (and all other hosts) ignores it 
[the hardware should do the ignore step unless in a "promiscuous mode"]
E1 then takes the action to map EN's IP address to the data link broadcast address.

[3] Now, E1 transmits that IP datagram to EN. It encodes the data with
EN's IP address and sends it to the data link broadcast address (as
specified in the ARP mapping table).
 - E2 gets it, notes it is for another IP address and forwards it
 - E3 gets it, notes it is for another IP address and forwards it ... repeat
 - EN gets it and processes it.

At this point, only 3 messages have been exchanged but the storm will grow rapidly.

[4] Each system (E2, E3, ..., EN-1) must determine EN's data link
address before it can forward the wayward message. Each of those
systems will repeat step [1], requesting EN's data link address.

Now we have (N-2)+3 messages transmitted.

[5] EN responds to each ARP request with a direct message, just like
step [2]. Each system (E2, E3, ..., EN-1) adds EN to its table that
maps EN's IP address to EN's data link address (broadcast). Now each
of these systems is ready to forward the message.

Now we have 2*(N-2)+3 messages transmitted.

[6] Each system (E2, E3, ..., EN-1) forwards the IP datagram to EN. EN
processes each received message but the other systems respond as noted
below.

Each system E1, E2, ..., EN-1 receives a message from every other
sender. E1 receives N-1 such messages. E2 through EN-1 receives N-2
such messages. All of these messages must be forwarded to EN.

Now we have 3*(N-2)+3 messages transmitted.

[7] Let's do a little arithmetic at this point.
  - E1 must send N-1 messages to EN
  - E2 through EN-1 must send N-2 messages to EN or a total of
(N-2)*(N-2) messages to send

When those are sent, the hosts have sent (N-2)*(N-2)+(N-1)+3*(N-2)+3 messages.

A typical host (e.g., E3) at this point receives (N-1) messages from
E1, (N-2) from E2, (N-2) from E4, and so on. This is roughly N*N
messages at each host. Each of those messages must be forwarded to EN.

[8] The cycle repeats, with N-1 hosts sending roughly N*N messages (a
little less than N*N*N messages) to be sent to EN's data link address
(broadcast) to be processed further.

This cycle grows at an exponential rate until the capacity of the data
link is exceeded. At this point, what occurs will depend on the type
of data link. Assuming IP datagrams and an Ethernet (e.g., CDMA) type
network, the following will occur:
 - each host (except EN) will get a continuous stream of incorrectly
addressed IP datagrams to be forwarded.
 - each host (except EN) will run out of buffer space in its transmit
queue since it cannot send them (roughly 1/N of total wire capacity)
as fast as it receives them. As a result, almost all of the messages
to forward will be discarded [(1-1/n)% of them].
 - EN will get a steady stream of repeated IP datagrams with the same
information, basically at the total wire capacity.

The wire will be basically at capacity with the retransmissions of
these forwarded messages. All as a result of sending a single message
to a misconfigured server.

Note: if a node dropped each misdirected message (instead of
forwarding), the broadcast storm would be prevented. This is because
the forwarding at [3] and all subsequent steps would not occur.

For more information on broadcast storms and their causes, I suggest a
search using phrases such as:
  cause broadcast storm
  broadcast storm network failure
  network meltdown broadcast
and similar phrases.

If any part of this answer is unclear or you need further explanation,
please make a request for clarification.

  --Maniac
Comments  
There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy