6.829 Computer
Networks (Fall 2003)
FAQ Archive for Problem Set 2
You guys may find this tool useful for PS2. Data processing, especially
for Q3 may take long - hours. The routeview table dump is 21MB
compressed. Unless you have ample disk space, you may want to
use pipelining (e.g. gzip -dc *.gz | ...).
Please be advised to start pset earlier this time.
Jaeyeon
----- Forwarded message from Nick Feamster <feamster@CSAIL.MIT.EDU> -----
From: Nick Feamster <feamster@CSAIL.MIT.EDU>
To: Jaeyeon Jung <jyjung@lcs.mit.edu>
Cc: Hari Balakrishnan <hari@lcs.mit.edu>
----- Forwarded message from David Meyer <dmm@1-4-5.net> -----
Date: Thu, 18 Sep 2003 09:50:38 -0700
From: David Meyer <dmm@1-4-5.net>
Subject: New routeviews service available (Address/Prefix -> AS/ASPATH mappings)
To: nanog@merit.edu
All,
In response to requests from many folks asking for prefix
to AS mappings, routeviews is now providing 2 new services
mapping and address or prefix to its origin AS and to its
ASPath. These services are available via two zones:
(i). asn.routeviews.org
asn.routeviews.org maps an address or prefix into
its origin AS, prefix, and prefix length, as seen by
route-views2.routeviews.org (the data is held in
TXT records).
For example, the following command
% dig txt 223.128.asn.routeviews.org
returns (among other things)
223.128.asn.routeviews.org. 86400 IN TXT "3582" "128.223.0.0" "16"
The syntax here is: "AS" "Prefix" "Prefix Length"
(ii). aspath.routeviews.org
aspath.routeviews.org is similar to asn.routeviews.org,
except that it maps an address or prefix into the ASpath
(rather than origin AS), prefix, and prefix length, as
seen by route-views2.routeviews.org (again, the data
is held in TXT records).
For example, the following command
% dig txt 223.128.aspath.routeviews.org
returns (among other things)
223.128.aspath.routeviews.org. 86400 IN TXT "286 209 3356 3701 3582" "128.223.0.0" "16"
The syntax here is: "ASPath" "Prefix" "Prefix Length"
These zones are built twice per-day, 11:45 and 23:45 UTC.
Finally, please let us know (help@routeviews.org) if you
have questions, comments or suggestions for ways we might
otherwise improve this service. One note: note that these
zones are quite large, and reloading these produces a
period of a few minutes during which the server may not
reply.
Thanks,
Dave
----- End forwarded message -----
----- End forwarded message -----
Dear 6.829 student,
To assist your TAs in giving you good grades for your problem sets, we would be
most grateful if you can draw boxes on the top of the FIRST page of your
solutions to all future problem for us to record the points awarded for each
question. There should be (n+1) boxes where n is the number of questions in the
problem set. For problem set 2, n would be 4. Label the boxes "1","2",...,"n"
and "Total".
Crude Example for PS 2:
------------------------------------------
| 1 | 2 | 3 | 4 | Total |
------------------------------------------
| | | | | |
| | | | | |
------------------------------------------
Those who fail to follow these instructions will incur the wrath of the TAs...
which is a very bad thing. Thanks.
Warmest Regards,
Ben
Mike Salib pointed out that MIT BGP file
was slightly corrupted -- missing line
terminators btw some records. Based on the copy of the file
that he fixed the problem (thanks Mike!), I did
some clean-up so that now each line corresponds to
each routing table record (after first few lines
of headers).
Please download mit.bgp.20030915.gz again
from the course web page, if you already
have your local copy and haven't started pset yet.
Don't worry if you already finished PS2 with
the old file. They are exactly the same,
but the old one has some entries that are
broken into two lines and such.
Jaeyeon
Hi Peter,
The reason for this is that a node will only advertise its best route to its
neighbors. So, X and Y would advertise XW and YW to Z respectively and NOT XYW
and YXW, so Z doesn't know about XYW and YXW. Thanks and have a good weekend.
Warmest Regards,
Ben
Peter D. VanBuskirk wrote:
In Question 1.3, why does node Z not know about t
he routes
XYW and YXW? Do X and Y not advertize YW and XW respectively?
Or is it just considered redundant because Z already knows about
XW and YW?
Thanks!
Peter VanBuskirk
--
Home: 70 Pacific Street Office: MIT Laboratory for Computer Science
Room 560B 200 Tech Square, +ACM-536
Cambridge, MA 02139, USA Cambridge, MA 02139, USA
(617) 452-4462 (617) 253-6023
Hi Mike,
Actually, Q2 was made a few days before the MIT BGP dump was taken,
and the route from MIT to routeviews was 10578 11537 4600 at that
moment.
Problem 2 1e should be based on the ASPATH provided in the question.
FYI, AS 3701 and AS 4600 are both the routers in University of Oregon.
Following is the whois information.
Jaeyeon
athena% whois -h whois.arin.net as3701
OrgName: Oregon Joint Graduate Schools of Engineering
OrgID: OJGSE
Address: University of Oregon
Address: Computing Center
Address: 1225 Kincaid St.
City: Eugene
StateProv: OR
PostalCode: 97403
Country: US
ASNumber: 3701
ASName: NERONET
ASHandle: AS3701
nms# whois -h whois.arin.net as4600
[whois.arin.net]
OrgName: Univeristy of Oregon
OrgID: UNIVER-499
Address: Computing Center
Address: 1225 Kincaid St.
City: Eguene
StateProv: OR
PostalCode: 97403
Country: US
ASNumber: 4600
ASName: UO-TRANSIT
ASHandle: AS4600
On Tue, 23 Sep 2003, Michael J Salib wrote:
Hi,
I had a quick question about Problem 2, section 1e. It claims that the
ASPATH from MIT to routeviews is 10578 11537 4600, but when I look in
the MIT BGP dump, it shows the ASPATH as being 10578 11537 4600 3701.
Which one of these is correct?
Thanks,
Mike Salib
whois is a useful tool to pull out information about
specific ASes or IP address block. You may find
it useful for PS2.
localhost# whois -h whois.arin.net "?"
will tell you the usage.
For example,
localhost# whois -h whois.arin.net GNTY-1
[whois.arin.net]
OrgName: Genuity
OrgID: GNTY
Address: Genuity
Address: 225 Presidential Way
City: Woburn
StateProv: MA
PostalCode: 01888
Country: US
ASNumber: 1
ASName: GNTY-1
ASHandle: AS1
Comment:
RegDate: 2001-09-20
Updated: 2001-09-20
...
localhost# whois -h whois.ra.net 4.0.0.0
[whois.ra.net]
route: 4.0.0.0/8
descr: NET-SATNET
origin: AS1
mnt-by: BBNPLANET
changed: ops@bbnplanet.com 19980203
source: RADB
Jaeyeon
The Metric means Multi-Exit Discriminator
and Weight is similar to local preference in that higher numbers are
preferred. Check http://www.cisco.com/warp/public/459/25.shtml and
Table 1 in the Lecture 4 notes for a more detailed description of the
route choosing algorithm.
In the two given datasets, the weights are all zero, so I think it's
safe to ignore weight for the problemset.
- Alex
Hi,
Can you explain what the "Metric" and "Weight" of the entries mean? For
finding the best next hop, do we just consider the number of nodes on the
Path?
Winnie
10578 is right.
whois.ra.net gives you an answer based on Routing Registry
and looks like their entry for 192.5.89.0/24 is outdated.
Look at "changed: ops@bbnplanet.com 199
80203", which means
the record is last updated back in 1998.
This will better explan the mismatch. 192.5.89.0 used to be maintained
by BBNPLANET (which was acquired by Genuity and now by Level3),
but now belongs to AS10578 (Harvard).
Hope this answers your question.
Jaeyeon
On Wed, 24 Sep 2003, Winnie W. Cheng wrote:
Hi,
I got different AS numbers using WHOIS and dig. For example, the IP
address 192.5.89.10 (which is also in problem 2.1e) belongs to AS1
according to WHOIS and AS10578 according to dig.
w20-575-66:PS2> whois -h whois.ra.net 192.5.89.10
route: 192.5.89.0/24
descr: NET-HARV-APOLLO
origin: AS1
mnt-by: BBNPLANET
changed: ops@bbnplanet.com 199802
03
source: RADB
w20-575-66:PS2> dig txt 10.89.5.192.asn.routeviews.org
; <<>> DiG 9.2.1 <<>> txt 10.89.5.192.asn.routeviews.org
;; global options: printcmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 24670
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 1, ADDITIONAL: 0
;; QUESTION SECTION:
;10.89.5.192.asn.routeviews.org. IN TXT
;; ANSWER SECTION:
10.89.5.192.asn.routeviews.org. 86400 IN TXT "10578" "192.5.89.0" "24"
;; AUTHORITY SECTION:
asn.routeviews.org. 86400 IN NS routeviews.org.
;; Query time: 485 msec
;; SERVER: 127.0.0.1#53(127.0.0.1)
;; WHEN: Wed Sep 24 19:38:51 2003
;; MSG SIZE rcvd: 94
Thanks,
Winnie
Hi Winnie,
You only need to give us the relationship between the ASs in the
paths listed in the question. However, in order to deduce the relationship between the ASs, you should scan through the entire routeview dump and consider ALL the paths that include the ASs of interest.
Perhaps I can give you a fictious example to make this clearer. You are given the ASPATH 7911 209 19092 3908 10947. Since you have computed the degrees of all the ASs, you may find that 3908 has the highest degree, so based on the above ASPATH, you conclude that: 7911->209->19092->3908<-10947. However, there might be another ASPATH in the routeview dump 3908 19092 323 2342 123 such that 2342 has the highest degree and you thereby conclude that 3908->19092->323->2342<-123. Combining these 2 pieces of information yields:
7911->209->19092<->3908<-10947
Once again, this is a fictious example, so please do not submit this as an
answer for Problem Set 2. Thanks.
Warmest Regards,
Ben
Winnie W. Cheng wrote:
Hi,
For Prob 3 part 2, when we are asked to find the "commutative transit
relationship", do we consider the only the paths given in the question or
do we have to compute the transit relationships of all paths in the
routeview dump?
Winnie
Sorry for the confusion.
Q2.3 asks you to answer for the following three cases:
1. Ben gets a series of snapshots containing only (a)
2. Ben gets a series of snapshots containing only (b)
3. Ben gets a series of snapshots containing only (c)
Jaeyeon
On Fri, 26 Sep 2003, Mike Afergan wrote:
Question 2.3 asks us about what we can infer from the partial dump. What confuses me however is the wording "from each type of partial snapshot". Is this to imply that Ben gets 3 _different_ (and non-correlatable) snapshots -- (a), (b), and (c)? Or a series of snapshots containing the three pieces of information (a), (b), and (c) ?
Thanks,
-- Mike
Hi Winnie,
243 832 {12354,23455} i
- It is as-set, and you can refer to
http://www.cisco.com/warp/public/459/aggregation.html for details.
54 23 23 23 3
- AS path prepend (23 23 23) is used to make
AS_PATH length longer, so regarding topology, it
is equivalent to 54 23 3
Jaeyeon
On Sat, 27 Sep 2003, Winnie W. Cheng wrote:
Hi Ben,
There are some ASPATH that looks like:
243 832 {12354,23455} i
54 23 23 23 {3} i
I'm wondering how I should consider the AS inside the bracket for degree
and transit relationship calculation. Do I assume that the above gives 3
paths:
243 832 12354
243 832 23455
54 23 23 23 3
Hi Mike,
(2) please. Thanks.
- Ben
Michael M. Afergan wrote:
In order to do 3.2 we clearly need the degree information from 3.1.
However, when we make inferences re: peering relationships are we supposed
to:
1) With the degree data in hand, examine only the 5 lines (a-e) given
OR
2) With the degree data in hand, examine all lines in the file, infer
AS relationships, and then incorporate this into what we can learn from
the 5 lines?
Thanks,
-- Mike
Simple answers for simple questions should apply for this
case. For 2.1.(a), giving a correct MIT AS number will get you
a full credit.
Jaeyeon
On Sun, 28 Sep 2003, Alexey A Radul wrote:
Hello,
Here's a question about the problem set: How much support should we
provide for our answers? For example, for 2.1, should we just write
"*", or would you like the pipeline that yielded the information that
let me conclude that, or the pipeline and the information, or
the pipeline, the information, and a paragraph arguing that that information
permits that conclusion?
Thanks,
~Alexey Radul
Neha,
Addresses without a network mask are chosen according to
the old classful masks. Note that for addresses < 128.0.0.0,
those masks are /8 (class A), for those < 192.0.0.0, those
masks are /16 (class B), etc.
Jaeyeon
On 29 Sep 2003, Neha Singh wrote:
Hi,
I have a question about the longest prefix matching in #4. In the MIT
routing table, there are many entries that don't have the A/m form,
meaning they are just specific addresses like
150.65.0.0
150.66.0.0
150.67.0.0
So if we are trying to match an address like 150.66.236.70, will it
match to 150.66.0.0, coz there doesn't seem to be any other appropriate
match? Is it implied that m = 16?
Thanks for your help,
Neha
Jim,
2.1.(h) has two sub-questions. 1. common AS's for ALL of the different
routes to MIT? 2. other than the common AS's, the most frequent
AS's?
Sorry for the confusion.
Jaeyeon
On Mon, 29 Sep 2003, James Psota wrote:
Hi All--
On 2.1.h, it seems like there isn't an AS other than AS3 that is common to
ALL routes from Routeviews to MIT. It seems like Level 3 (i.e., AS3356)
is common to a lot of the routes, but the question states ALL... am I
missing something?
Thanks,
Jim
Jim,
class C network is supposed to have 2^8 hosts and the question
is intended to ask you guys to find the first CIDR address block
that has aggregated N (>= 1) number of class C networks.
Hope this makes the question clear.
Jaeyeon
On Mon, 29 Sep 2003, James Psota wrote:
Hi All,
In 2.2.b, we're asked to find the first "class C" CIDR range. Running
some shell commands produces
2282662 * 192.0.2.1/32 141.142.12.1 0 1224
22335 10764 1213 ?
2282663 *> 206.220.240.95 0 10764
1213 ?
2282664 * 192.0.32.0/21 195.219.96.239 0 8297
6453 2914 226 26711 i
(note: line numbers prepended to original file)
The output shown above is the first CIDR addresses shown in the 192.* range.
The first CIDR range that can be seen is a /32, which seems to make the
subsequent questions regarding how many routing table entries we save with
CIDR a bit awkward. Should I procede to answer with the first entry, or
turn my attention to the second with the /21?
Thank you.
Jim
Hi Neha,
Sorry we didn't state this clearly. For Q2, 1(f), count each routing entry
(ending with a newline) as a route, so if the ASPATHs are the same, but the
NextHops are different, that's TWO (or more) routes. Thanks for clarifying.
Warmest Regards,
Ben
Neha Singh wrote:
Hi,
I have a question regarding the number of routes from the router in
problem 2 to MIT (question 1 (f)). For some of the routes, the ASPATH is
the same but the next hop is different. Does this mean they are the same
route or will we consider them as different routes when we count?
Thanks,
Neha
Hi Tazeen,
2 modifications required: (1) You need to produce the ccdf, so k
is the number
of entries with length >= n. (2) Finally, the plot (x,y) should be (log n, log
k/N). Thanks.
Warmest Regards,
Ben
Tazeen Mahtab wrote:
Hi,
I wanted to know if I understand correctly what I'm supposed to produce
for part 1 of problem 3. Here is what I think I need to do.
For each AS in the routing table, we need to find its degree, the number
of other ASs it connects to. We obtain this by examining the ASPath in
each entry of the routing table and creating a table of AS -> List of
connected ASs.
For example, if an entry has ASPath 4513 701 3908 10947, fill in the table
as follows:
AS List of connected ASs
4513 701
701 4513 3908
3908 701 10947
10947 3908
The total number of ASs, N, is the number of entries in the table. To get
the fraction of ASs that have degree n, count the number of entries in the
table that have a List of length n. If this number is k, the fraction is
k/N. Produce the graph by plotting (log k/N, log k/N) for each n >= 0.
Does this seem right?
Thanks a lot,
Tazeen
For Q4, you have to keep in mind that there is a two-year gap
between the time that the MIT routing table snapshot was taken
and the byte-related trace was captured.
For the traffic destined to non-existent routing entries, you
can define another category, "unknown", and calculate percentage
accordingly.
For example, it can be like Internet2 X%, Genuity/Level 3: Y%,
and unknown: Z% where X+Y+Z = 100% .
Jaeyeon
OIX routing table is very long. It took me a few hours
to process the file with my Perl prgram for Q3.
Jaeyeon
On Tue, 30 Sep 2003, Timothy Chan wrote:
the OIX routing table is too long.
i'm trying to find the length of this file with "grep -c".
it has been an hour.
my c-program spent 2 hours and it never returned, though did occasionally
spit out some output.
is this expected?
-Tim
No, that's not the question is intended for. If you have a
program that finds a closes prefix for a given IP address,
I think it might not be that hard to hack it to flag IP
addresses that don't have a corresponding routing entry
in the table.
Then, you can compute how much traffic those IP addresses
account for (unknown %) and excluding those IP addresses,
you can run the same program to find
out Internet 2% and Genuity %.
Jaeyeon
On Tue, Sep 30, 2003 at 04:10:32PM -0400, I-Ting A. Lee wrote:
Hi:
Can we just use the closest prefix instead of having another unknown
category? It's just so much trouble to go through in order to find the
unknown ones if we are not using the Patricia module.
Thanks,
Angelina
You do not need to apply route damping.
- Alex
Hi,
For question 1.3 in pset 2, do we have to apply route damping or can we
assume that there is no route damping?
Thanks,
Mike
Shan,
Hope the following example clarifies the question.
Let us assume that the CIDR address you found contains 2 class C networks.
Currently, the CIDR address takes one routing entry. But, without
CIDR, there should have been 2 routing entries for two individual class
C networks, even though the routing information is exactly the same.
In this case, you save 1 routing table entry at best.
Jaeyeon
On Wed, 1 Oct 2003, Shan Sinha wrote:
When you ask how "the maximum number of routing table entries that this
single CIDR address saves?" do you mean the number of routing table
entries that this entry "conserves" or "stores" in the table?
Cheers-
Shan
Vinod,
Decisions should be made based only on _adjacent_ AS pairs.
a->b->c<-d tells you
a->b
b->c
d->c
c->a->e<-f tells you
c->a (*)
a->e
f->e
In terms of a relationship btw a and c,
you can infer only c->a from (*) based on those
two ASpath examples.
Jaeyeon
On Wed, 1 Oct 2003, vinodv@theory.lcs.mit.edu wrote:
Hi
In question 3.2, assume we have two aspaths a->b->c<-d and
c->a->e<-f. Since a is downhill of c in the first ASPATH and
c is downhill of a in the second, am I right if I conclude that
c and a are siblings ? Or do we make our decisions based only
on _adjacent_ AS pairs ?(c is adjacent to a in the second
ASPATH but not in the first).
Sorry for the trouble
Vinod
No. They should be contiguous in a way that they
can be aggregated without adding additional prefixes.
Jaeyeon
On Wed, 1 Oct 2003, Tim Olsen wrote:
For problem 3.2.c.ii, is it ok to provide continguous prefixes that
cannot be aggregated without adding additional prefixes? For example,
18.0.1.0/24 and 18.0.2.0/24 are contiguous, but cannot be aggregated
without also pulling in 18.0.0.0/24 and 18.0.3.0/24.
-Tim