FunkyMonk's solution is still the right thing to do for the data structure. The only thing this new requirement adds is that you need to save every line you see somewhere; the last match determines the "where".

Sample script:

#!/usr/bin/perl -w
use strict;

my ($state, %data);

for (<DATA>){
    $state = $1 if /^(Router|Network|Extern)/;
    push @{$data{$state}}, $_;
}

# Display the saved data
for my $st (sort keys %data){
    print "$st:\n";
    for (@{$data{$st}}){
        print "\t$_";
    }
}

__DATA__
Router
abc
def
ghi jkl
Network
Extern
foo
bar
qux
zotz
Router
blah
Network
[download]

Update: I had originally thought to number the lines, so I had the innermost loop in the 'display' section traverse the indexes. Since I'm just displaying the lines, I've gone back to walking the list itself - so rather than 'for my $line (0 .. $#{$data{$st}}){ print "\t$data{$st}->[$line]"; }', that loop becomes simply 'for (@{$data{$st}}){ print "\t$_"; }'.

Update^2: Whoops, I missed the fact that the keys were supposed to be at the beginning of the line. Fixed the regex.

-- 
Human history becomes more and more a race between education and catastrophe. -- HG Wells